數(shù)據(jù)結(jié)構(gòu)數(shù)組和廣義表-資料下載頁
2024-11-03 22:17本頁面
【正文】 表頭 HEAD(LS)和取廣義表的表尾 TAIL(LS)。 根據(jù)前面對表頭和表尾的定義可知：任何一個非空廣義表其表頭可以是單元素，也可以是子表，而其表尾必定為一個廣義表 (子表 )。例如，廣義表為前面所定義的 A到 E表， HEAD和 TAIL運(yùn)算有： HEAD(B)=a， TAIL(B)=((b,c,d)), HEAD(C)=e， TAIL(C)=(), HEAD(D)=A， TAIL(D)=(B,C,f)， 另外運(yùn)算也可以嵌套，如： HEAD(TAIL(B))=b， TAIL(TAIL(B))=(c,d)。 廣義表的存儲結(jié)構(gòu) 由于廣義表中數(shù)據(jù)元素可以具有不同結(jié)構(gòu)，通常采用鏈表存儲結(jié)構(gòu)，每一個數(shù)據(jù)元素可用一個結(jié)點(diǎn) (可以是子表或單元素 )。表示子表的表結(jié)點(diǎn)與表示單元素的數(shù)據(jù)元素結(jié)點(diǎn)之間是有差異的，以下是一種常用的存儲結(jié)構(gòu)。 struct node /* 表結(jié)點(diǎn) */ { int tag。 /* =1標(biāo)識子表結(jié)點(diǎn) */ struct node *child； /* 指向該子表的指針 */ struct node *next； /* 指向下個元素的指針 */ }； struct node /* 數(shù)據(jù)元素結(jié)點(diǎn) */ { int tag。 /* =0標(biāo)識原子結(jié)點(diǎn) */ int val； /* 值域 */ struct node *next； /* 指向下個元素的指針 */ }； 實(shí)際存儲結(jié)構(gòu)： 為了便于處理，將 val域和 child域以聯(lián)合的方式存儲，表結(jié)點(diǎn)和數(shù)據(jù)結(jié)點(diǎn)合二為一， C語言定義的廣義表結(jié)點(diǎn)結(jié)構(gòu)如下： struct glnode { int tag。 /* =1標(biāo)識子表結(jié)點(diǎn)， =0標(biāo)識原子結(jié)點(diǎn) */ union { struct glnode *child； /* 表結(jié)點(diǎn)中的子表指針域 */ int val。 /* 原子結(jié)點(diǎn)中的系數(shù)域 */ }content struct glnode *next； /* 指向下個元素的指針 */ }； typedef struct glnode GLNode。 注意： 在該結(jié)構(gòu)中， tag=1表示該結(jié)點(diǎn)是表結(jié)點(diǎn)，聯(lián)合中取 child域，而 tag=0表示該結(jié)點(diǎn)是數(shù)據(jù)結(jié)點(diǎn)，在聯(lián)合中取val域。 上一節(jié)所舉廣義表例子，它們的存儲結(jié)構(gòu)如圖 。 圖 廣義表的存儲結(jié)構(gòu) 廣義表的基本操作 對廣義表基本操作有： (1)建表。 (2)撤銷表。 (3)復(fù)制 (賦值 )表。 (4)插入元素作為第 i個元素。 (5)刪除第 i個元素。 (6)求表深度；等。 下面討論求表深度和建表算法。 廣義表的深度定義為表中括號的重數(shù)，是廣義表的一種度量。廣義表中數(shù)據(jù)元素的最大層次數(shù)為表的深度，例如，有一個廣義表 LS=(a,(b,c,(d,e)))，數(shù)據(jù)元素a在第一層， b、 c在第二層，而數(shù)據(jù)元素 d在第三層，所以廣義表的深度為 3。算法如下。 算法 求廣義表深度算法。 int GList_Depth(GLNode *head) /* head是廣義表的首指針 */ { GLNode *p。int max,depth1。 p=head。 max=0。 while(p!=NULL) { if(ptag==0) depth1=0。 else depth1= GList_Depth(p)。 if(depth1max) max=depth1。 p=pnext。 } return(max+1)。 } 建立廣義表的算法，針對一個無共享的廣義表的邏輯表式，如： A=(a,(b,c),d) 算法如下： 算法 建立廣義表算法。 int i=0。 char str[20]=(a,(b,c),d)。 GLNode *create() { GLNode *p。 char ch。 ch=str[i]。 i++。 switch (ch) { case 39。(39。: p=(GLNode *)malloc(sizeof(GLNode))。 ptag=1。 p=create()。 pnext=create()。 break。 case 39。a39。: case 39。b39。: case 39。c39。: case 39。d39。: case 39。e39。: p=(GLNode *)malloc(sizeof(GLNode))。 ptag=0。 p=ch。 pnext=create()。 break。 case 39。,39。: p=create()。 break。 case 39。)39。:case 39。\039。: p=NULL。 } i++。 return(p)。 } 算法 遍歷廣義表算法。 void GList_Traverse(GLNode *head) { GLNode *p。 for(p=head。 p!=NULL。 p=pnext) if(ptag==1) { printf(()。 GList_Traverse(p)。 printf(),)。 } else printf(%c,p)。 }
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1