表達(dá)式求值廣義表的運(yùn)算課程設(shè)計(jì)報(bào)告

1、<p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告</p><p>　　題目: 表達(dá)式求值廣義表的運(yùn)算</p><p>　　學(xué) 院 信息工程學(xué)院 __________</p><p>　　專 業(yè) ____ 計(jì)算機(jī)科學(xué)與技術(shù)</p><p>　　年級(jí)班別 _12級(jí)四班___________</p>

2、<p>　　學(xué) 號(hào) ________</p><p>　　學(xué)生姓名 _____</p><p>　　指導(dǎo)教師 __</p><p>　　成 績 _</p><p>　　2013年12月 </p><p><

3、b>　　題目：</b></p><p>　　廣義表的運(yùn)算。本設(shè)計(jì)要求實(shí)現(xiàn)廣義表的建立、查找、輸出、取表尾、以及求深度、求逆表等。</p><p>　　一、問題分析與任務(wù)定義：</p><p>　　此程序需要完成以下幾個(gè)任務(wù)：首先要將輸入的用數(shù)組存儲(chǔ)的廣義表轉(zhuǎn)化成以廣義表的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的廣義表，這個(gè)過程也就是生成廣義表；查找廣義表，查找廣義表要返回一

4、個(gè)值flag，當(dāng)flag=1時(shí)，程序查找到待查的元素，當(dāng)flag=0時(shí)，程序沒有找到待查元素；輸出廣義表，遍歷廣義表，輸出廣義表的遍歷結(jié)果；取表頭，返回表頭結(jié)點(diǎn)；取表尾，將廣義表從第二個(gè)元素開始復(fù)制到另一個(gè)廣義表中；求廣義表的深度，遍歷每一層廣義表，將廣義表內(nèi)每層廣義表深度最大的廣義表相加為同一層所求過的子表中深度的最大值，最后返回值加一即為廣義表的深度；求逆表，將廣義表逆向輸出。</p><p>　　實(shí)現(xiàn)本程序

5、需要解決以下問題：</p><p>　　如何根據(jù)廣義表的特點(diǎn)建立廣義表。</p><p>　　用什么方法才能查找到廣義表中每一個(gè)元素，如何標(biāo)志是否找到待查元素。</p><p>　　建立廣義表，如何根據(jù)廣義表的存儲(chǔ)結(jié)構(gòu)的特點(diǎn)建立廣義表。</p><p>　　求廣義表的深度的依據(jù)是什么。</p><p>　　運(yùn)用什么方法

6、才能將廣義表逆序。</p><p>　　如何實(shí)現(xiàn)廣義表的遍歷。</p><p>　　二、概要設(shè)計(jì)和數(shù)據(jù)結(jié)構(gòu)選擇：</p><p>　　1、設(shè)計(jì)思想：廣義表是線性表的一種推廣，但它并不是線性表。課本上在介紹廣義表的計(jì)本概念的基礎(chǔ)上，介紹了廣義表的存儲(chǔ)及應(yīng)用。廣義表濃縮了線性表、數(shù)組等常見的數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，在有效利用存儲(chǔ)空間方面更勝一籌，目前在文本處理、人工智能、代數(shù)操

7、作和計(jì)算機(jī)圖形方面等各個(gè)領(lǐng)域都具有應(yīng)用價(jià)值。</p><p>　　所以在我當(dāng)時(shí)拿到這個(gè)題目的時(shí)候，雖然它只有短短的幾行字，但是我深深的感覺到了它的難度，在后來課程設(shè)計(jì)中，也證實(shí)了我的感覺，每個(gè)功能都實(shí)在是太難實(shí)現(xiàn)了，所以只有各個(gè)擊破了。設(shè)計(jì)程序時(shí)，先起草了流程圖，通過流程圖來看，就使得程序鮮明易懂，接下來先寫好了主函數(shù)，通過主函數(shù)的調(diào)用，實(shí)現(xiàn)題目要求的各個(gè)功能，使得程序模塊化，便于編寫，即使不會(huì)寫的子函數(shù)，也可以

8、先空著，等待以后想到好的方法后再對其進(jìn)行操作，同時(shí)在程序界面上也做了美化，使人感覺舒暢，另外通過一個(gè)循環(huán)，能讓用戶進(jìn)行循環(huán)操作，不至于每次只能進(jìn)行一項(xiàng)操作,這個(gè)循環(huán)用的和線性表里的循環(huán)有點(diǎn)類似，但其實(shí)現(xiàn)的操作不同，當(dāng)然有了以前實(shí)驗(yàn)的基礎(chǔ)，這次編寫起來，也感覺輕松了不少。</p><p>　　2、廣義表的存儲(chǔ)結(jié)構(gòu)：</p><p>　　由于廣義表中的元素本身又可以具有結(jié)構(gòu)，是一種帶有層次的非

9、線性結(jié)構(gòu)，因此難以用順序存儲(chǔ)的結(jié)構(gòu)表示。通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，每個(gè)元素可用一個(gè)結(jié)點(diǎn)表示，結(jié)點(diǎn)結(jié)構(gòu)如圖1、圖2所示：</p><p>　　圖1原子結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)</p><p><b>　　圖2結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)</b></p><p>　　每個(gè)結(jié)點(diǎn)由三個(gè)域構(gòu)成。其中tag是一個(gè)標(biāo)志位，用來區(qū)分當(dāng)前結(jié)點(diǎn)是原子結(jié)點(diǎn)還是子表。當(dāng)tag為1時(shí)，該結(jié)點(diǎn)是子表

10、，第二個(gè)域?yàn)閔p，用以存放子表的地址；當(dāng)tag為0時(shí)，該結(jié)點(diǎn)是原子結(jié)點(diǎn)，第二個(gè)域?yàn)閍tom，用以存放元素值。tp域是用來存放與本元素同一層的下一個(gè)元素對應(yīng)結(jié)點(diǎn)的地址，當(dāng)該元素是所在層的最后一個(gè)元素時(shí)，tp的值為NULL。廣義表及結(jié)點(diǎn)類型描述如下：</p><p>　　typedef char ElemType;</p><p>　　typedef struct GLode//廣義表結(jié)構(gòu)體的

11、定義</p><p><b>　　{ </b></p><p>　　int tag;/*結(jié)點(diǎn)類型標(biāo)識(shí)*/</p><p><b>　　union</b></p><p><b>　　{</b></p><p>　　ElemType atom;

12、/*原子值*/</p><p>　　struct GLode *hp;/*指向子表的指針*/</p><p><b>　　} val;</b></p><p>　　struct GLode *tp;/*指向下一個(gè)元素*/</p><p><b>　　} GList;</b></p

13、><p>　　例如：建立廣義表：（a，b（c，d），e） ，如圖3 </p><p>　　圖3 廣義表的存儲(chǔ)圖示</p><p>　　3、求廣義表的逆表需要用堆棧存儲(chǔ)廣義表的元素，棧的數(shù)據(jù)類型如下：</p><p>　　typedef char ElemType;</p><p>　　typedef struct <

14、/p><p>　　{ ElemType data[maxlen] ;</p><p><b>　　int top;</b></p><p>　　}SeqStack;</p><p>　　3、程序流程圖如圖。</p><p><b>　　三、詳細(xì)設(shè)計(jì)與編碼</b></p>

15、;<p>　　1、建立廣義表CreateGL(char *&s)。在生成廣義表之前，用一個(gè)數(shù)組存儲(chǔ)廣義表，并用指針s指向數(shù)組，通過數(shù)組中的元素生成廣義表?；舅枷胧牵涸趶V義表表達(dá)式中，遇到左括號(hào)”(”時(shí)遞歸構(gòu)造子表，否則構(gòu)造原子結(jié)點(diǎn)；遇到逗號(hào)時(shí)遞歸構(gòu)造后續(xù)廣義表，直到字符串?dāng)?shù)組結(jié)束，以"\0"作為結(jié)束標(biāo)志。實(shí)現(xiàn)過程如下：</p><p>　　GList *CreateGL

16、(char *&s)</p><p>　　{ 讀入廣義表的一個(gè)字符給ch；</p><p>　　if (ch!=空格') </p><p><b>　　{</b></p><p>　　if (ch=='(') </p><

17、p>　　{ 遞歸構(gòu)造子表；}</p><p>　　else if (ch==')')</p><p>　　遇到')'字符,子表為空</p><p><b>　　else</b></p><p>　　{ 構(gòu)造原子結(jié)點(diǎn)；}}</p><p><b>

18、　　else</b></p><p><b>　　串結(jié)束,子表為空</b></p><p>　　讀入廣義表的一個(gè)字符給ch；</p><p>　　if (ch==',') </p><p><b>　　遞歸構(gòu)造后續(xù)子表；</b><

19、/p><p>　　else </p><p>　　處理表的最后一個(gè)元素</p><p><b>　　返回廣義表指針</b></p><p><b>　　}</b></p><p>　　2、遍歷廣義表DispGL(GList *g

20、)。輸出廣義表采用的算法思想是：若遇到tag=1的結(jié)點(diǎn)，這是一個(gè)子表的開始，先打印輸出一個(gè)左括號(hào)”(”。如果該子表為空，則輸出一個(gè)空格符；否則遞歸調(diào)用輸出該子表。子表打印輸出完后，再打印一個(gè)右括號(hào)”)”。若遇到tag=0的結(jié)點(diǎn)，則直接輸出其數(shù)據(jù)域的值。若還有后續(xù)元素，則遞歸調(diào)用打印后續(xù)每個(gè)元素，直到遇到tp=NULL。其實(shí)現(xiàn)過程如下：</p><p>　　void DispGL(GList *g)</p

21、><p><b>　　{</b></p><p>　　if (g!=NULL) </p><p><b>　　{</b></p><p>　　if (g->tag==1) </p><p><b>　　

22、{</b></p><p><b>　　輸出左括號(hào)'('；</b></p><p>　　if (g->val.hp==NULL) </p><p><b>　　輸出一個(gè)空格；</b></p><p><b>　　else</b></p

23、><p><b>　　遞歸調(diào)用子表；</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　輸出數(shù)據(jù)域；</b></p><p>　　if (g->tag==1)

24、</p><p><b>　　打印有括號(hào)“）”；</b></p><p>　　if (g->tp!=NULL)</p><p>　　輸出逗號(hào)“，”，遞歸調(diào)用輸出下一個(gè)結(jié)點(diǎn)。</p><p><b>　　}</b></p><p><b>　　}</b&g

25、t;</p><p>　　3、廣義表的查找：FindGListX()</p><p>　　在給定的廣義表種查找數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)，采用的算法思想是：若遇到tag=0的原子結(jié)點(diǎn)，如果是要查找的結(jié)點(diǎn)，則查找成功1；否則，若還有后續(xù)元素，則遞歸調(diào)用本過程在孩子表中查找，若還有后續(xù)元素，則遞歸調(diào)用本過程查找后續(xù)每個(gè)元素，直到遇到hp域?yàn)镹ULL的元素。</p><p>　　設(shè)

26、置flag標(biāo)志查找結(jié)果；flag=1；表示查找成功，否則查找失敗。</p><p>　　本函數(shù)實(shí)現(xiàn)過程如下：</p><p>　　FindGListX(GList *g,char x,int &mark)</p><p><b>　　{</b></p><p>　　if(g!=NULL){</p>

27、<p>　　if (g->tag == 0 && g->val.atom ==x)</p><p><b>　　{</b></p><p>　　查找成功mark = 1;</p><p><b>　　}</b></p><p>　　else if(g->

28、tag == 1) 遞歸調(diào)用查找后續(xù)元素；</p><p>　　遞歸查找調(diào)用后續(xù)元素；</p><p><b>　　}}</b></p><p>　　4、求廣義表的表頭：head（Glist *g）</p><p>　　GList *head(GList *g) </p><p>　　{

29、 GList *p; </p><p>　　if (g->tag ==1&&g->val.hp==NULL)</p><p>　　{ 空表不能求表頭；}</p><p>　　else {返回表頭結(jié)點(diǎn) }}</p><p>　　5、求廣義表的表尾：tail(GList *g)

30、</p><p>　　一個(gè)廣義表的表尾指的是除去該廣義表的第一個(gè)元素剩下的部分。求表尾實(shí)現(xiàn)過程如下：</p><p>　　GList *tail(GList *g)</p><p><b>　　{</b></p><p>　　if (g==NULL) </p><p><b>

31、　　{</b></p><p><b>　　空表不能求表尾；</b></p><p><b>　　}</b></p><p>　　else if (g->tag==0) </p><p><b>　　{</b></p>

32、<p><b>　　原子不能求表尾；</b></p><p><b>　　}</b></p><p>　　將廣義表除去第一個(gè)元素，其余的元素復(fù)制的廣義表q中，既為該廣義表的表尾。</p><p><b>　　return q;</b></p><p><b&g

33、t;　　}</b></p><p>　　6.求廣義表的深度GLDepth(GList *g)。</p><p>　　廣義表的深度的遞歸定義是它等于所有子表中表的最大深度加1，若一個(gè)表為空或僅由單個(gè)元素所組成，則深度為1。求廣義表深度的遞歸函數(shù)GLDepth（）如</p><p><b>　　實(shí)現(xiàn)過程如下：</b></p>

34、<p>　　int GLDepth(GList *g) </p><p><b>　　{</b></p><p>　　if (g->tag==0)</p><p><b>　　為原子時(shí)返回；</b></p><p>　　g=g->val.hp;</p>

35、<p>　　if (g==NULL)</p><p><b>　　為空表時(shí)返回1；</b></p><p>　　while (g!=NULL) </p><p><b>　　{</b></p><p>　　if (g->tag==1) </p>

36、<p><b>　　{</b></p><p>　　遞歸調(diào)用求出子表的深度；</p><p>　　if (dep>max) </p><p>　　max為同一層所求過的子表中深度的最大值；}</p><p>　　使g指向下一個(gè)元素；</p><p><b>　　}<

37、/b></p><p>　　返回表的深度(max+1) 。 </p><p><b>　　}</b></p><p>　　7、求廣義表的逆表NIGList(GList *g,SeqStack *s)</p><p>　　求廣義表的逆表的算法思想是：利用廣義表的遍歷將廣義表的元素存入一個(gè)堆棧中，然后在將棧中所有的元素

38、出棧打印，函數(shù)的實(shí)現(xiàn)如下：</p><p>　　將廣義表中的元素存入堆棧中：</p><p>　　void NIGList(GList *g,SeqStack *s)</p><p><b>　　{</b></p><p>　　if(g!=NULL) </p><

39、;p><b>　　{</b></p><p>　　if (g->tag==1) </p><p><b>　　{</b></p><p>　　將廣義表中的“(”以“)”存入棧中；</p><p><b>　　else</b><

40、/p><p>　　遞歸調(diào)用，將子表中的元素存入棧中；</p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　將廣義表中的元素存入棧中；</p><p>　　if (g->tag==1)</p><p&g

41、t;　　將廣義表中的")"以"("存入棧中；</p><p>　　if (g->tp!=NULL)</p><p>　　將廣義表中的","存入棧中；</p><p>　　遞歸將后續(xù)表的內(nèi)容存入棧中。</p><p><b>　　}</b></p>

42、;<p><b>　　}</b></p><p>　　將棧中所有元素輸出：</p><p>　　void Pop(SeqStack *s) </p><p><b>　　{ </b></p><p><b>　　打印棧中元素。</b></p&g

43、t;<p><b>　　}</b></p><p><b>　　上機(jī)調(diào)試</b></p><p>　　1、調(diào)試函數(shù)FindGListX(GList *g,char x,int flag) 時(shí)，函數(shù)起不了作用， 對于flag 的值不能做改變，在mian函數(shù)中使用兩個(gè)scanf（）函數(shù)，后面一個(gè)函數(shù)得不到運(yùn)行。</p>&

44、lt;p>　　解決辦法： 在scanf()函數(shù)前加getchar（），如下面的程序所示：</p><p><b>　　flag =0;</b></p><p>　　getchar();</p><p>　　scanf("%c",&x);</p><p>　　FindGListX(g,x,

45、 flag); </p><p><b>　　if (flag)</b></p><p>　　printf("找到待查元素！\n");</p><p><b>　　else</b></p><p>　　printf(" 沒有找到待查元素！\n&q

46、uot;);break;</p><p>　　2.程序運(yùn)行后出現(xiàn)圖5的錯(cuò)誤：</p><p><b>　　圖5 錯(cuò)誤2</b></p><p>　　解決辦法：在while循環(huán)中加入以下程序：</p><p>　　printf("是否繼續(xù)：1.繼續(xù)；0.停止\n");</p><p&

47、gt;　　printf("請選擇：");</p><p>　　scanf("%d",&xz);</p><p><b>　　if(xz==1)</b></p><p>　　system("cls");</p><p><b>　　else<

48、;/b></p><p><b>　　{</b></p><p>　　system("cls");</p><p>　　printf("再 見 ！\n");</p><p><b>　　}</b></p><p>　　3.求

49、表尾函數(shù)錯(cuò)誤，當(dāng)輸入空表時(shí)，不能輸出空表不能求表尾這句提示語。如圖6所示：</p><p><b>　　圖6 錯(cuò)誤3</b></p><p>　　解決方法: 把語句if(g=NULL)改成if (g->tag ==1&&g->val.hp==NULL),因?yàn)榭毡頌楸斫Y(jié)點(diǎn)，且空表沒子表，所以這話就可以判斷出廣義表是否為空表了。</p&g

50、t;<p>　　五、測試結(jié)果及其分析</p><p>　　1、查找廣義表中的元素：</p><p>　　（1）待查元素在廣義表中的運(yùn)行結(jié)果如圖9：</p><p><b>　　圖9 找到待查元素</b></p><p>　?。?）待查元素不在廣義表中的運(yùn)行結(jié)果如圖10所示：</p><p

51、>　　圖10 沒有找到待查元素</p><p>　　2、求表頭運(yùn)行結(jié)果如圖11所示：</p><p>　　圖11求廣義表的表頭</p><p>　　3、求廣義表的表尾運(yùn)行結(jié)果如圖12所示：</p><p>　　圖12求廣義表的表頭</p><p>　　4、求廣義表的深度的運(yùn)行結(jié)果如圖13所示：</p>

52、<p>　　圖13求廣義表的深度</p><p>　　5、求廣義表的逆表的運(yùn)行結(jié)果如圖14所示；</p><p>　　圖14求廣義表的逆表</p><p>　　６、退出廣義表的運(yùn)行結(jié)果如圖15所示</p><p>　　圖15求廣義表的逆表</p><p><b>　　六、用戶使用說明</b

53、></p><p>　　本程序運(yùn)行過程時(shí)帶有提示性語句，用戶可以根據(jù)需要和提示進(jìn)行操作：</p><p>　　1、運(yùn)行程序，程序提示輸入廣義表，出現(xiàn)運(yùn)行界面；</p><p>　　2、查找廣義表中的元素。選擇1，程序提示，輸入要查找的元素，若該元素在廣義表中，程序顯示：找到待查元素。否則顯示 :找不到待查元素；</p><p>

54、;　　3、求廣義表的表頭。選擇2，程序輸出所求廣義表的表頭；</p><p>　　4、求廣義表的表尾。選擇3，程序輸出所求廣義表的表尾</p><p>　　5、求廣義表的深度。選擇4，程序輸出廣義表的深度；</p><p>　　6、求廣義表的逆表。選擇5，程序輸出廣義表的逆表；</p><p>　　7、選擇0，退出廣義表的運(yùn)算，程序終止；&l

55、t;/p><p>　　8、每次操作結(jié)束以后，會(huì)有提示語句：是否繼續(xù)執(zhí)行其他操作(選擇1、繼續(xù) ；0、停止)。</p><p><b>　　七、總結(jié)</b></p><p>　　1、廣義表的運(yùn)算包括廣義表的建立、查找、求表頭、求表尾、求深度、廣義表刪除、求逆表，依據(jù)原子結(jié)點(diǎn)和結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)不同，進(jìn)行相應(yīng)的操作。</p><p>

56、;　　2、程序中多次使用遞歸調(diào)用。</p><p>　　3、使用聯(lián)合體建立廣義表的數(shù)據(jù)類型。</p><p>　　4、根據(jù)棧的特點(diǎn)將廣義表逆置輸出。</p><p>　　5、程序中使用switch函數(shù)，將每個(gè)操作分開進(jìn)行。</p><p><b>　　八、參考書目</b></p><p>　　[1

57、]王昆侖 李紅 .數(shù)據(jù)結(jié)構(gòu)與算法.北京：中國鐵道出版社，2007年6月第一版</p><p>　　[2] 譚浩強(qiáng).《C程序設(shè)計(jì)指導(dǎo)》.北京：清華大學(xué)出版社,2005年7月</p><p>　　[3]姚群 夏清國.數(shù)據(jù)結(jié)構(gòu).陜西：西北工業(yè)大學(xué)出版社，2004年6月第一版</p><p>　　[4]黃國興 章炯民.數(shù)據(jù)結(jié)構(gòu)與算法.北京：機(jī)械工業(yè)出版社，2004年7月第一

58、版</p><p><b>　　九、附錄</b></p><p>　　#include <stdio.h></p><p>　　#include <malloc.h></p><p>　　#include<stdlib.h></p><p>　　#define

59、maxlen 100</p><p>　　typedef char ElemType;</p><p>　　typedef struct GLNode //廣義表結(jié)構(gòu)體的定義</p><p><b>　　{</b></p><p>　　int tag; //結(jié)點(diǎn)類型標(biāo)識(shí)</p>

60、;<p><b>　　union</b></p><p><b>　　{</b></p><p>　　ElemType atom; //原子值</p><p>　　struct GLNode *hp; //指向子表的指針</p><p><b>　　} val

61、;</b></p><p>　　struct GLNode *tp; //指向下一個(gè)元素，相當(dāng)于單鏈表中的next</p><p><b>　　}GList;</b></p><p>　　typedef struct //棧結(jié)構(gòu)的定義</p><p><b>

62、;　　{</b></p><p>　　ElemType data[maxlen] ;</p><p><b>　　int top;</b></p><p>　　}SeqStack;</p><p>　　GList *CreateGL(char *&s) //建立廣義表 ,生成廣義表的鏈?zhǔn)?/p>

63、存儲(chǔ)結(jié)構(gòu)</p><p><b>　　{</b></p><p>　　GList *h; //定義個(gè)新廣義表</p><p><b>　　char ch; </b></p><p>　　ch=*s; //取一個(gè)掃描字

64、符 </p><p>　　s++; //往后掃描字符 </p><p>　　if(ch!='\0') //判斷是否為回車，若不是，則執(zhí)行下面操作 </p><p><b>　　{</b></p><p>　　h=(GLi

65、st *)malloc(sizeof(GList)); //動(dòng)態(tài)申請個(gè)新廣義表</p><p>　　if (ch=='(') //若當(dāng)前字符為"("時(shí)，執(zhí)行下列操作</p><p><b>　　{</b></p><p>　　h->tag=1;

66、 //新節(jié)點(diǎn)做為表頭節(jié)點(diǎn)</p><p>　　h->val.hp=CreateGL(s); //遞歸調(diào)用字表，鏈接到表頭結(jié)點(diǎn)上</p><p><b>　　}</b></p><p>　　else if (ch==')')</p><p>　　h=NULL;

67、 //若為")"時(shí)，字表為空</p><p>　　else </p><p><b>　　{</b></p><p>　　h->tag=0; </p><p>　　h->val.atom=ch;

68、 //若都不滿足，則為原子結(jié)點(diǎn)， </p><p><b>　　}}</b></p><p>　　ch=*s; //取下一個(gè)字符 </p><p>　　s++; //指針后移 </p>

69、<p>　　if (h!=NULL) //判斷是否為空 </p><p>　　if (ch==',') //當(dāng)前字符為',' </p><p>　　h->tp=CreateGL(s); //遞歸調(diào)用后續(xù)子表 </p><p

70、>　　else </p><p>　　h->tp=NULL; //否則，則后續(xù)字表為空</p><p>　　return h; </p><p><b>　　}</b></p><p>

71、;　　void DispGL(GList *g) //遍歷廣義表</p><p><b>　　{ </b></p><p>　　if(g==NULL) return ; //若廣義表為空，則返回</p><p>　　if(g->tag==0)</p><p>　　printf

72、(" %c ,",g->val.atom); //若廣義表g為原子結(jié)點(diǎn)，則直接輸出其值</p><p>　　else { //否則為表結(jié)點(diǎn)，則輸出"("</p><p>　　printf("( ");</p><p>　　for(g=g->

73、val.hp;g;g=g->tp) //從字表表頭開始，依次遍歷其后續(xù)子表</p><p>　　DispGL(g);</p><p>　　printf("\b),");}</p><p><b>　　}</b></p><p>　　int GLDepth(GList *g) //求廣

74、義表的深度</p><p>　　{ </p><p>　　int max=0,dep; //定義變量</p><p>　　if (g->tag==0) //若為原子結(jié)點(diǎn)，返回0</p><p>　　return 0; </p>&

75、lt;p>　　g=g->val.hp; //廣義表g被賦值為子表結(jié)點(diǎn)</p><p>　　if (g==NULL) //若廣義表為空，返回值1</p><p>　　return 1;</p><p>　　while (g!=NULL) //若不為空</p><p><b&g

76、t;　　{</b></p><p>　　if (g->tag==1) //若為表結(jié)點(diǎn)</p><p><b>　　{</b></p><p>　　dep=GLDepth(g); //遞歸調(diào)用，求深度</p><p>　　if (dep>max) </

77、p><p><b>　　max=dep;</b></p><p><b>　　}</b></p><p>　　g=g->tp; //廣義表g被賦值為其后續(xù)子表</p><p><b>　　}</b></p><p>　　retur

78、n(max+1); </p><p><b>　　}</b></p><p>　　GList *head(GList *g) // 求廣義表表頭</p><p><b>　　{</b></p><p>　　GList *p; //定義

79、個(gè)新廣義表p</p><p>　　if (g->tag ==1&&g->val.hp==NULL) //若其為空表時(shí)，輸出空表不能求表頭</p><p>　　{ printf("空表不能求表尾\n");</p><p>　　return NULL ; //返回</p><p&

80、gt;<b>　　}</b></p><p>　　else {p=g->val.hp; //不為空表時(shí)，返回廣義表g的子表表頭結(jié)點(diǎn)</p><p>　　return p; }}</p><p>　　GList *tail(GList *g) // 求廣義表表尾</p><p

81、><b>　　{</b></p><p>　　GList *p; //定義個(gè)新廣義表p</p><p>　　p=g->val.hp; //P被賦值為廣義表g的表頭結(jié)點(diǎn) </p><p><b>　　GList *t;</b></p>

82、<p>　　if (g->tag ==1&&g->val.hp==NULL) //若其為空表時(shí)，輸出空表不能求表尾</p><p>　　{ printf("空表不能求表尾\n");</p><p>　　return NULL ; //返回</p><p><b>　　}

83、 </b></p><p>　　else if (g->tag==0) //若為原子結(jié)點(diǎn)時(shí)，輸出原子結(jié)點(diǎn)不能求表尾 </p><p><b>　　{</b></p><p>　　printf("原子不能求表尾\n");</p><p>　　return

84、NULL;</p><p>　　} //否則，為表結(jié)點(diǎn)</p><p>　　p=p->tp; //p被賦為其后續(xù)結(jié)點(diǎn)</p><p>　　t=(GList *)malloc(sizeof(GList)); //申請一個(gè)新結(jié)點(diǎn)t</p><p>　　t

85、->tag=1; //t為表結(jié)點(diǎn)</p><p>　　t->tp=NULL; //t的后續(xù)結(jié)點(diǎn)被賦為空</p><p>　　t->val.hp=p; //t的子表為p</p><p><b>　　return t;</b>&

86、lt;/p><p><b>　　}</b></p><p>　　void FindGListX(GList *g,char x,int &flag) // 廣義表查找</p><p><b>　　{</b></p><p>　　if(g!=NULL){</p><p>　

87、　if (g->tag == 0 && g->val.atom ==x) //若為原子結(jié)點(diǎn)，且原子結(jié)點(diǎn)值等于x，flag=1</p><p><b>　　{</b></p><p>　　flag = 1; </p><p><b>　　}</b><

88、;/p><p>　　else if(g->tag == 1) //若為表結(jié)點(diǎn)</p><p>　　FindGListX(g->val.hp,x,flag); //遞歸調(diào)用其子表的表頭結(jié)點(diǎn)</p><p>　　FindGListX(g->tp,x,flag); //遞歸調(diào)用其后續(xù)結(jié)點(diǎn)</p&

89、gt;<p><b>　　}</b></p><p><b>　　}</b></p><p>　　void NIGList(GList *g,SeqStack *s) //求廣義表的逆表</p><p><b>　　{</b></p><p>　　i

90、f(g!=NULL) </p><p>　　if (g->tag==1) //若為表結(jié)點(diǎn)時(shí)</p><p><b>　　{</b></p><p><b>　　s->top++;</b></p><p>　　s

91、->data[s->top]=')'; //將廣義表中的"("以“)”存入棧中</p><p>　　if (g->val.hp==NULL) </p><p>　　printf("");</p><p><b>　　else</b><

92、;/p><p>　　NIGList(g->val.hp,s); //遞歸調(diào)用將子表存入棧中</p><p><b>　　}</b></p><p>　　else //若為原子結(jié)點(diǎn)時(shí)</p><p><b>　　{ </b>&

93、lt;/p><p><b>　　s->top++;</b></p><p>　　s->data[s->top]=g->val.atom; //直接將原子結(jié)點(diǎn)值如棧</p><p><b>　　}</b></p><p>　　if (g->tag==1)</p>

94、<p><b>　　{</b></p><p>　　s->top++; </p><p>　　s->data[s->top]='('; //將廣義表中的")"以"("存入棧中 </p><p><b>　　}</b

95、></p><p>　　if (g->tp!=NULL)</p><p><b>　　{</b></p><p><b>　　s->top++;</b></p><p>　　s->data[s->top]=','; //將廣義表中的&q

96、uot;,"存入棧中 </p><p>　　NIGList(g->tp,s); //遞歸調(diào)用將后續(xù)表的內(nèi)容存入棧中</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void Pop(SeqStack *s)

97、 //廣義表的輸出 </p><p><b>　　{ </b></p><p>　　while(s->top>=0)</p><p><b>　　{ </b></p><p>　　printf("%c",

98、s->data[s->top]);</p><p><b>　　s->top--;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void main()</p><p>&l

99、t;b>　　{</b></p><p>　　GList *g,*gt; </p><p>　　system("color 1B ");</p><p>　　printf("請輸入一個(gè)廣義表：如(a,(b),c)\n");</p><p>　　char str[3

100、0]; </p><p>　　char x; </p><p>　　int y=0,mark,m=1; </p><p>　　SeqStack *k;</p><p>　　k=(SeqStack *)malloc(sizeof(SeqSta

101、ck));</p><p>　　k->top=-1; </p><p>　　char *s=gets(str);</p><p>　　g=CreateGL(s); </p><p>　　printf("你輸入的廣義表為：\n

102、");</p><p><b>　　while(m)</b></p><p><b>　　{</b></p><p>　　DispGL(g);</p><p>　　printf("\b \n");</p><p>　　printf("\

103、t\t*****廣義表的運(yùn)算*****\n");</p><p>　　printf(" \t\t===========================\n");</p><p>　　printf(" \t\t |*** 1.廣義表查找 ***|\n");</p><p>　　printf(" \t

104、\t |*** 2.求廣義表頭 ***|\n");</p><p>　　printf(" \t\t |*** 3.求廣義表尾 ***|\n");</p><p>　　printf(" \t\t |*** 4.求廣義表深度 ***|\n");</p><p>　　printf(" \t\t |*

105、** 5.求廣義表逆表 ***|\n");</p><p>　　printf(" \t\t |*** 0.退出表的運(yùn)算 ***|\n");</p><p>　　printf(" \t\t===========================\n");</p><p>　　printf(" 請 選 擇

106、:(0——5) \n");</p><p>　　scanf("%d",&y);</p><p>　　switch (y)</p><p><b>　　{</b></p><p>　　case 1: printf("請輸入要查找的元素：\n");</p>

107、;<p><b>　　mark=0;</b></p><p>　　getchar();</p><p>　　scanf("%c",&x);</p><p>　　FindGListX(g,x,mark); </p><p><b>　　if (mar

108、k)</b></p><p>　　printf("找到待查元素！\n");</p><p><b>　　else</b></p><p>　　printf(" 沒有找到待查元素！\n");</p><p><b>　　break;</b></

109、p><p>　　case 2: gt=head(g); </p><p>　　printf("表頭:");DispGL(gt);printf("\b \n");</p><p><b>　　break;</b></p><p>　　case

110、3: gt=tail(g); </p><p>　　printf("表尾:");DispGL(gt);printf("\b \n");</p><p><b>　　break;</b></p><p>　　case 4: printf("廣義表的深度:%

111、d\n",GLDepth(g));</p><p><b>　　break;</b></p><p>　　case 5: printf("所求廣義表的逆表為：\n");</p><p>　　NIGList(g,k); </p><p>　　Pop(k);

112、 </p><p>　　printf("\n");</p><p><b>　　break;</b></p><p>　　default : system("cls");</p><p>　　printf("再 見 ，歡迎再次使用 ！\n");<

113、;/p><p><b>　　return ;</b></p><p><b>　　}</b></p><p>　　printf("是否繼續(xù)：1.繼續(xù)；0.停止\n");</p><p>　　printf("請選擇：\n");</p><p>

114、;　　scanf("%d",&m);</p><p><b>　　if(m==1)</b></p><p>　　system("cls");</p><p><b>　　else</b></p><p><b>　　{</b>&l

115、t;/p><p>　　system("cls");</p><p>　　printf("再 見 ，歡迎再次使用 ！\n");</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b&