廣義表的存儲結構代碼:

　　/* c5-5.h 廣義表的頭尾鏈表存儲表示 */

　　typedef enum{ATOM,LIST}ElemTag; /* ATOM==0：原子，LIST==1：子表 */

　　typedef struct GLNode

　　{

　　ElemTag tag; /* 公共部分，用于區分原子結點和表結點 */

　　union /* 原子結點和表結點的聯合部分 */

　　{

　　AtomType atom; /* atom是原子結點的值域，AtomType由用戶定義 */

　　struct

　　{

　　struct GLNode *hp,*tp;

　　}ptr; /* ptr是表結點的指針域，prt.hp和ptr.tp分別指向表頭和表尾 */

　　}a;

　　}*GList,GLNode; /* 廣義表類型 */

廣義表的存儲結構圖:

廣義表儲存圖

/*---------------------------------------------------------------------

廣義表的存儲結構?

---------------------------------------------------------------------*/?

#include<stdio.h>?

#include<stdlib.h>

typedef?char?ElemType;//元素類型是字符型

//廣義表的存儲結構?

struct?GNode?

{

int?tag;?//標志域??

union{??//值域或子表的表頭指針域???

ElemType?data;???

struct?GNode?*sublist;

};? ?

struct?GNode?*next;?//指向后繼結點的指針域?

};

/*----------------------函數聲明----------------------*/?

int?LengthGList(struct?GNode?*GL);?//求廣義表的長度?

int?DepthGList(struct?GNode?*GL);?//求廣義表的深度? 

void?CreateGList(struct?GNode?**GL);//建立廣義表的存儲結構?

void?PrintGList(struct?GNode?*GL);?//打印輸出廣義表? 

int?SearchGList(struct?GNode?*GL,?ElemType?e);//查找等于給定字符的單元素結點，查找成功則返回1，否則返回0

/*----------------------主函數----------------------*/?

void?main()?

{

struct?GNode?*GL;//帶表頭附加結點? ?

printf("輸入一個廣義表，以分號結束\n");??

CreateGList(&GL);? ?

printf("輸出廣義表：");??

PrintGList(GL);??

printf("\n");? ?

printf("廣義表的長度：");? ?

printf("%d\n",?LengthGList(GL->sublist));??

printf("廣義表的深度：");? ?

printf("%d\n",?DepthGList(GL->sublist));??

printf("搜索值d?的結果：");? ?

printf("%d\n",?SearchGList(GL,?'d'));? } 

/*----------------------函數----------------------*/?

//求廣義表的長度? 

int?LengthGList(struct?GNode?*GL)

{??

if(GL!=NULL)???

return(1?+?LengthGList(GL->next));??

else

return(0);?

}?? 

//求廣義表的深度? 

int?DepthGList(struct?GNode?*GL)

{??

int?max=0;//給max賦初值? ?

//遍歷表中每一個結點，求出所有子表的最大深度??

while(GL!=NULL)??

{??

if(GL->tag==1){

int?dep?=?DepthGList(GL->sublist);//遞歸調用求出一個子表的深度????

if(dep?>?max)????? 

max?=?dep;//讓max始終為同一層所求過的子表中深度的最大值? ??

}? ??

GL?=?GL->next;//使GL指向同一層的下一個結點

}? 

return(max?+?1);//返回表的深度? 

}?? 

//建立廣義表的存儲結構? 

void?CreateGList(struct?GNode?**GL)?

{

char?ch;??

scanf("%c",?&ch);//讀入一個字符，此處只可能讀入空格#、左括號或英文字母??

if(ch=='#')//若輸入為空格，則置表頭指針為空

*GL?=?NULL;??

else?if(ch=='(')//若輸入為左括號則建立由*GL所指向的子表結點并遞歸構造子表

{

*GL?=?malloc(sizeof(struct?GNode));?

(*GL)->tag?=?1;???

CreateGList(&((*GL)->sublist));??

}??

else{?//若輸入為字符則建立由*GL所指向的單元素結點???

*GL?=?malloc(sizeof(struct?GNode));???

(*GL)->tag?=?0;???

(*GL)->data?=?  

}? ?

scanf("%c",?&ch);//此處讀入的字符必為逗號、右括號或分號??

if(*GL==NULL);?//若*GL為空，則什么都不做??

else?if(ch==',')//若輸入逗號則遞歸構造后繼表???

CreateGList(&((*GL)->next));? ?

else?if((ch==')')?||?(ch==';'))//若輸入為右括號或分號則置*GL的后繼指針域為空???

(*GL)->next?=?NULL;? 

}?? 

//打印輸出廣義表? 

void?PrintGList(struct?GNode?*GL)?

{??

//對于表結點的處理情況??

if(GL->tag==1){?//存在子表，則輸出左括號，作為開始符號???

printf("(");???

if(GL->sublist==NULL)//若子表為空則輸出‘#’字符????

printf("#");???

else//若子表非空，則遞歸輸出子表????

PrintGList(GL->sublist);???

printf(")");//當一個子表輸出結束后，應輸出一個右括號終止符

}? ?

else//對于單元素結點，則輸出該結點的值???

printf("%c",?GL->data);? ?

if(GL->next!=NULL)//輸出結點的后繼表??

{???

printf(",");//先輸出逗號分隔符? ??

PrintGList(GL->next);//再遞歸輸出后繼表? ?

}

}?? 

//查找等于給定字符的單元素結點，查找成功則返回1，否則返回0?

int?SearchGList(struct?GNode?*GL,?ElemType?e)

{??

while(GL!=NULL){???

if(GL->tag?==?1)//存在子表，則遞歸搜索本層該子表???

{???

if(SearchGList(GL->sublist,?e))

return(1);???

}???

else//存在單元素結點，則查詢是否存在值e?，若存在則返回1???

{???

if(GL->data?==?e)????

return(1);??

}? 

GL?=?GL->next;//使GL指向同一層的下一個結點??    

}? ?

return(0);//剩下來的情況，GL值為NULL，代表搜索不到值e?，輸出0? 

}

按層次來，先看整體有多少個“子表”，從表頭指針出來就有多少個表結點，然后從出來的表結點按次序在進行延展，對于第一個表結點代表的是第一個子表，那么第一個子表里有多少個子表或者原子節點，從這個表結點里就延伸出多少個  “二代”表結點，層層向下，直到表結點指示原子節點為止，然后回溯到最開始的表結點層，重復以上的過程即可，是一種遞歸的思想感覺