廣義表的運(yùn)算問題論文

1、合肥學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系課程設(shè)計(jì)報(bào)告2008 2009 學(xué)年第 二 學(xué)期課程 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)名稱廣義表運(yùn)算問題學(xué)生姓名*學(xué)號(hào)*專業(yè)班級(jí)07計(jì)科(1)指導(dǎo)教師王昆侖/胡春玲2009 年 6 月一、 問題分析和任務(wù)定義1、題目 15： 廣義表運(yùn)算問題2、要求和任務(wù)： 本設(shè)計(jì)要求實(shí)現(xiàn)廣義表的建立、查找、輸出、取表尾以及求深度、求逆表等。3、廣義表的輸入和輸出程序中，要求建立一個(gè)廣義表，以右括弧結(jié)束。如： 建立一個(gè)廣義表,以右括號(hào)結(jié)束： （a），b，（c，d）輸出的是6種有關(guān)廣義表的操作如下：1 輸出廣義表 2 廣義表深度3 廣義表表頭 4 廣義表表尾5 廣義表逆置 6 廣義表查找0 退出系

2、統(tǒng)若不進(jìn)行任何運(yùn)算，則退出。4、算法測試用例設(shè)計(jì) （a），b，（c，d） （a，（b，c） （a） 二、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)1、數(shù)據(jù)結(jié)構(gòu)廣義表的概念：廣義表是n（n0）個(gè)元素( a1，a2，ai，an)的有限序列；其中，n為廣義表的長度，ai或者是原子或者是一個(gè)廣義表，當(dāng)它是廣義表時(shí)，稱其為原廣義表的子表。其中：廣義表是遞歸定義的，因?yàn)樵诙x廣義表時(shí)用到了廣義表的概念。廣義表用圓括號(hào)括起來，用逗號(hào)分隔其中的元素，記作L=( a1，a2，ai，an)，其中L是廣義表的名字。通常，用大寫字母表示廣義表，用小寫字母表示原子。若廣義表L非空（n1），則a1 是廣義表L的表頭，其余元素構(gòu)成的子表（a

3、2，an)為廣義表L的表尾。廣義表的元素可以是原子，也可以是子表，而且子表還可以有子表，因此，廣義表是以多層次的結(jié)構(gòu)。任何一個(gè)非空廣義表，其表頭可能是原子，也可以是廣義表，而其表尾必定是廣義表。由于任一非空的廣義表都可以分解成表頭和表尾兩部分，因此一個(gè)表結(jié)點(diǎn)至少應(yīng)包含兩個(gè)域：表頭指針域和表尾指針域，分別指向該廣義表的表頭和表尾；而一個(gè)原子結(jié)點(diǎn)中只需要存儲(chǔ)該原子的值。為了區(qū)分原子結(jié)點(diǎn)和表結(jié)點(diǎn)，可為它們分別加上一個(gè)標(biāo)志域。這樣，一個(gè)表結(jié)點(diǎn)可由3個(gè)域構(gòu)成：標(biāo)志域tag=1，表頭指針域hp和下一元素結(jié)點(diǎn)next。而一個(gè)原子結(jié)點(diǎn)只需兩個(gè)域：標(biāo)志域tag=0和值域atom。廣義表的單鏈存儲(chǔ)結(jié)構(gòu)結(jié)點(diǎn)類型如下

4、： typedef enumATOM, LISTElemTag; /ATOM=0:原子,LIST=1:子表typedef struct GLNode int tag; /公共部分,區(qū)分原子和表結(jié)點(diǎn) union /原子結(jié)點(diǎn)和表結(jié)點(diǎn)的聯(lián)合部分 char atom;/原子結(jié)點(diǎn)的值域 struct GLNode *hp;/表結(jié)點(diǎn)表頭指針 ; struct GLNode *next;/下一個(gè)元素結(jié)點(diǎn)GList;2、設(shè)計(jì)思想廣義表本屬線性類型的數(shù)據(jù)結(jié)構(gòu)，它和數(shù)組類似，每個(gè)數(shù)據(jù)元素本身又可以是一個(gè)數(shù)據(jù)結(jié)構(gòu)，但廣義表比數(shù)組更為復(fù)雜，廣義表是一種遞歸定義的線性結(jié)構(gòu)，因此它兼有線性結(jié)構(gòu)和層次結(jié)構(gòu)的特點(diǎn)，它的存儲(chǔ)表

5、示和操作的實(shí)現(xiàn)和樹的操作很類似。程序的開始，先定義廣義表的結(jié)點(diǎn)類型，采用枚舉類型區(qū)分原子ATOM和子表LIST。采用聯(lián)合體定義原子結(jié)點(diǎn)的值域atom和表頭指針域hp。再輸入一個(gè)廣義表，在程序中可以定義一個(gè)數(shù)組用來存放廣義表中的關(guān)鍵字。編寫各個(gè)功能函數(shù)時(shí)，先了解算法的思想，繪出流程圖，根據(jù)流程圖進(jìn)一步編寫，則要簡單得多。之后編寫一個(gè)功能選擇函數(shù)choose（），并在此函數(shù)中打印運(yùn)行界面，通過輸入代碼，來進(jìn)行不同功能的操作。在運(yùn)行界面中，通過一個(gè)while循環(huán)，能讓用戶進(jìn)行循環(huán)操作，直至退出系統(tǒng)。3、廣義表的運(yùn)算問題流程圖（1）結(jié)構(gòu)圖表 1函數(shù)名功能CreatGList（）創(chuàng)建廣義表PrintGL

6、ist（）輸出廣義表GListDepth（）廣義表求深度GlistHead（）廣義表取表頭GlistTail（）廣義表取表尾Traverselist（）廣義表逆置Locate（）廣義表元素查找Choose（）菜單選擇函數(shù)Main（）主函數(shù)mainCreateGList choosePrintGListGListDepthGListHeadGListTailTraverselistLocate圖 1 結(jié)構(gòu)圖（2）流程圖開始輸入數(shù)據(jù)如果數(shù)據(jù)值不為“”如果數(shù)據(jù)值為“（”則指向此元素的指針的標(biāo)志量為LIST遞歸調(diào)用本函數(shù)，建立此廣義表的表頭指針?biāo)傅脑刂赶虼嗽氐闹羔樀臉?biāo)志量為ATOM,且元素值為所

7、輸入數(shù)值輸入數(shù)據(jù)如果輸入數(shù)據(jù)為“，”遞歸調(diào)用本函數(shù)，建立此廣義表下一個(gè)元素如果為“）”下一個(gè)元素的地址為空 結(jié) 束圖 2 廣義表的創(chuàng)建 開 始調(diào)用建表函數(shù)，建立廣義表調(diào)用菜單函數(shù)如果為1調(diào)用輸出廣義表函數(shù)如果為2調(diào)用求深度函數(shù)如果為3調(diào)用取表頭函數(shù)如果為4調(diào)用取表尾函數(shù)如果為5調(diào)用求逆表函數(shù)如果為6調(diào)用查找函數(shù)如果為0退出 結(jié) 束圖 3 主函數(shù)三、 詳細(xì)設(shè)計(jì)和編碼1、 菜單函數(shù)int choose( ) int sn;printf("-n");printf(" 廣義表相關(guān)運(yùn)算 n");printf(" 1.廣義表輸出 2.廣義表深度 n&quo

8、t;);printf(" 3.廣義表表頭 4.廣義表表尾 n");printf(" 5.廣義表逆置 6.廣義表查找 n");printf(" 0.退出系統(tǒng)n");printf("-n"); printf("請(qǐng)輸入代碼06：n"); for( ; ; ) scanf( "%d", &sn);if( sn <0|sn>6)printf("nt輸入錯(cuò)誤，重選06：n");elsebreak;return sn;函數(shù)功能： 此函數(shù)為含有多個(gè)菜單

9、項(xiàng)的主控菜單程序，使用數(shù)字0-6來選擇菜單項(xiàng)，超出此范圍時(shí)，提示輸入錯(cuò)誤，并重新輸入。運(yùn)行程序時(shí)，先輸入一個(gè)廣義表，回車后，調(diào)用各功能函數(shù)，則出現(xiàn)功能菜單，輸入的一個(gè)數(shù)字，該數(shù)字用sn存儲(chǔ)，使用choose（）接受數(shù)字輸入，該函數(shù)的返回值提供給主函數(shù)；則主函數(shù)使用while循環(huán)實(shí)現(xiàn)重復(fù)選擇，以實(shí)現(xiàn)不同的廣義表菜單功能。2、 主函數(shù)int main( )GList *L;char ch;printf("建立廣義表，結(jié)束請(qǐng)多輸一個(gè)右括號(hào)n");CreateGList(&L); /創(chuàng)建廣義表while(1) switch(choose()case 1:printf(&qu

10、ot;您輸入的廣義表為：");PrintGList(L);printf("n");break;case 2:printf("廣義表的深度為：");printf("%d", GListDepth(L->hp);printf("n");break;case 3:printf("廣義表取表頭");GListHead(L);printf("n");break;case 4:printf("廣義表取表尾");printf("(")

11、;GListTail(L);printf(")");printf("n");break;case 5:printf("廣義表求逆表");TraverseList(L);printf("n");break;case 6:printf("請(qǐng)輸入要查找的元素");scanf("%c",&ch);Locate(L, ch);printf("n");break;case 0:printf("再見n");exit(0);break;retu

12、rn 0;函數(shù)功能： 主函數(shù)中包含的功能函數(shù)有：輸出廣義表、廣義表深度、廣義表表頭、廣義表表尾、廣義表查找、廣義表逆置6個(gè)函數(shù)。運(yùn)行程序時(shí)，首先執(zhí)行主函數(shù)，根據(jù)提示，建立廣義表，廣義表中的元素應(yīng)單獨(dú)輸入，每輸入一個(gè)字符，回車，廣義表輸入完成時(shí)，應(yīng)再次輸入“）”，表示輸入結(jié)束，這是由于CreateGList函數(shù)遞歸的原因，回車，此時(shí)調(diào)用choose（）函數(shù)，出現(xiàn)功能菜單，提示用戶進(jìn)行相關(guān)操作，進(jìn)入任一操作，通過switch（choose（）對(duì)用戶所輸入的信息進(jìn)行匹配，匹配后調(diào)用相關(guān)的子函數(shù)，從而實(shí)現(xiàn)各項(xiàng)函數(shù)的功能。3、 創(chuàng)建廣義表函數(shù)：CreateGList（）void CreateGList(

13、GList *L) /創(chuàng)建廣義表函數(shù) char ch;scanf("%c", &ch); /輸入數(shù)據(jù)getchar(); if(ch = '#') /如果輸入的是#表示為空*L = NULL;else if(ch = '(') /如果是左括號(hào)就遞歸構(gòu)件子表*L = (GList *)malloc(sizeof(GList);(*L)->tag =1; /廣義表的標(biāo)志量為LISTCreateGList(&(*L)->hp); /建立此廣義表的表頭指針?biāo)傅脑豦lse /只有原子的情況下*L = (GList *)m

14、alloc(sizeof(GList);(*L)->tag = 0; /廣義表標(biāo)志量為ATOM(*L)->atom = ch; /元素為所輸入數(shù)值ai=ch; /不能寫成ai=(*L)->atom;i+;scanf("%c", &ch); /此處輸入的必為逗號(hào)或者右括getchar();if(ch = ',') /如果是逗號(hào)就遞歸構(gòu)件下一個(gè)子表CreateGList(&(*L)->next); else if(ch = ')') /如果是右括號(hào)就結(jié)束 (*L)->next =NULL;函數(shù)功能：

15、此函數(shù)為廣義表的構(gòu)建，是程序中的基本函數(shù)。函數(shù)中，先定義一個(gè)整型數(shù)據(jù)i=0和一個(gè)數(shù)組a10，構(gòu)建時(shí)，先輸入一個(gè)字符，如果輸入字符的是#，則廣義表為空，否則輸出第一個(gè)左括號(hào)。接下來的元素項(xiàng)如果是子表，則遞歸調(diào)用CreateGList()，若是原子，則直接輸出，并將輸入的數(shù)據(jù)保存在數(shù)組ai中，同時(shí)i+，然后繼續(xù)輸入保存用戶所輸入的數(shù)據(jù)，若是，則遞歸調(diào)用CreateGList（）函數(shù)，繼續(xù)執(zhí)行第一步，當(dāng)遇到）時(shí)，結(jié)束。4、 廣義表輸出函數(shù)PrintGList（）void PrintGList(GList *L)/輸出廣義表if(L->tag = 1) /廣義表標(biāo)志量為LIST printf(&

16、quot;("); /先輸出左括號(hào)if(L->hp = NULL) /表頭指針為空printf("#");elsePrintGList(L->hp); /遞歸打印子表 printf(")"); /結(jié)束打印右括號(hào)else /標(biāo)志量為ATOMprintf("%c", L->atom); /輸出此元素 if(L->next !=NULL) printf(", ");PrintGList(L->next); /調(diào)用此函數(shù)，輸出廣義表下一個(gè)元素函數(shù)功能： 此函數(shù)實(shí)現(xiàn)的是輸出功能，它直接

17、關(guān)聯(lián)到后面的取表頭、表尾運(yùn)算。函數(shù)中，分為原子和子表，若是子表，則利用頭結(jié)點(diǎn)指針，遞歸輸出子表。若是原子，則直接輸出該原子的數(shù)值。然后判斷下一結(jié)點(diǎn)是否為空，不為空則輸出“，”，繼續(xù)遞歸輸出，執(zhí)行上一步的操作。5、 廣義表求深度函數(shù)GListDepth（）int GListDepth(GList *L)/求廣義表深度int max, dep;if(!L) /廣義表存在return 1;for(max = 0; L; L = L->next) /max初值為0，元素地址不為空if(L->tag = 1) /元素標(biāo)志量為LISTdep = GListDepth(L->hp);/求以

18、L->hp的子表深度if(dep > max)max = dep; return max + 1; /各元素的深度的最大值加一函數(shù)功能：此函數(shù)用于實(shí)現(xiàn)求廣義表的深度，廣義表深度的遞歸定義式：它等于所有子表中表的最大深度加1。若一個(gè)表為空，則深度為1。定義dep表示任一子表的深度，max為所有子表中的最大深度，則廣義表的深度為max+1。 函數(shù)中，當(dāng)廣義表L為空表或由單元素組成時(shí)，不進(jìn)行遞歸調(diào)用，返回1；否則，當(dāng)廣義表含有子表時(shí)，利用頭結(jié)點(diǎn)指針，遞歸求出深度，將最大深度的子表的dep賦值給max，返回max+1即為廣義表深度。6、 輸出表頭函數(shù)：PrintGListHead（）voi

19、d PrintGListHead(GList *L)/打印廣義表表頭函數(shù) if(L->tag = 1 ) /子表 printf("("); /先輸出左括號(hào)if(L->hp = NULL) /如果表頭為空printf("#"); elsePrintGListHead(L->hp); /遞歸打印子表printf(")"); /結(jié)束打印右括號(hào)else /原子printf("%c", L->atom);函數(shù)功能： 此函數(shù)用于輸出廣義表的表頭，表頭分為子表和原子。當(dāng)表頭為子表時(shí)，先輸出左括號(hào)，再通過遞

20、歸調(diào)用依次輸出表頭，最后輸出右括號(hào)。當(dāng)表頭為原子時(shí)，直接輸出原子數(shù)值。7、 廣義表取表頭函數(shù)GListHead（）void GListHead(GList *L) /廣義表取表頭GList *p;p=L->hp; /p指向廣義表表頭PrintGListHead(p); /調(diào)用表頭輸出函數(shù)函數(shù)功能： 此函數(shù)用于取廣義表的表頭。若廣義表非空，則第一個(gè)元素是廣義表的表頭。函數(shù)中定義一個(gè)指針p，用于指向廣義表的表頭，再調(diào)用表頭輸出函數(shù)PrintGListHead（），輸出表頭。8、 廣義表取表尾函數(shù)GListTail（）void GListTail(GList *L)/廣義表取表尾GList *

21、p,*q;q=L->hp; /q指向廣義表表頭p=q->next; /p指向廣義表表尾PrintGList(p); 函數(shù)功能： 此函數(shù)用于取廣義表的表尾。若廣義表非空，則廣義表中除去表頭后其余元素構(gòu)成的子表為表尾。函數(shù)中，定義指針p、q，q用于指向廣義表表頭，q->next為廣義表表尾，并賦值給p，因p也是廣義表，則可調(diào)用廣義表輸出函數(shù)PrintGList（），輸出表尾。9、 廣義表逆置函數(shù)TraverseList()void TraverseList(GList *L) /廣義表逆置 printf("("); GListTail(L); /調(diào)用取表尾函數(shù)

22、 printf(","); GListHead(L); /調(diào)用取表頭函數(shù)printf(")");函數(shù)功能： 此函數(shù)用于實(shí)現(xiàn)廣義表的逆置算法。逆置即將表頭和表尾倒置，因此算法中，先后調(diào)用取表尾函數(shù)和取表頭函數(shù)，先輸出表尾，再輸出表頭，以此實(shí)現(xiàn)逆置功能。10、 廣義表查找函數(shù)Locate（）void Locate(GList *L,char ch) /廣義表查找int j;在這里輸入一個(gè)提示的scanf("%c",&ch); /輸入要查找關(guān)鍵字for (j=0;j<=i;j+) /利用for循環(huán)查找if(aj=ch) /如果

23、找到printf ("查找成功，位置為%dn",j+1);break;if(j>i)printf("查找失敗,元素不存在此廣義表中!n");函數(shù)功能： 此函數(shù)用于實(shí)現(xiàn)廣義表的查找功能，運(yùn)行時(shí)，輸入要查找的元素，將該元素與數(shù)組中的元素進(jìn)行比較，若相等，則查找成功，輸出此元素的位置信息，當(dāng)查找超出范圍時(shí)，輸出查找失敗信息。四、 上機(jī)調(diào)試上級(jí)調(diào)試過程中，程序出現(xiàn)了很多問題：1、 輸入一個(gè)廣義表時(shí)，回車，顯示調(diào)試錯(cuò)誤，經(jīng)檢查發(fā)現(xiàn)未寫結(jié)束字符“）”。當(dāng)廣義表輸入完成后，應(yīng)多輸入一個(gè)右括號(hào)表示輸入結(jié)束。2、 輸入代碼時(shí)，代碼在0-6之間，但卻顯示“輸入錯(cuò)誤，重

24、選06：”，并無限循環(huán)。此時(shí)輸入代碼是在主函數(shù)中進(jìn)行的，經(jīng)修改，另外定義一個(gè)選擇函數(shù)choose（），返回代碼值，在主函數(shù)中調(diào)用choose（）函數(shù)，此時(shí)程序運(yùn)行正確。3、 輸入代碼1，即輸出廣義表，顯示調(diào)試錯(cuò)誤，經(jīng)檢查，是源程序中輸出算法編寫的錯(cuò)誤。4、 輸出廣義表深度時(shí)，無論廣義表是什么，深度總為1，經(jīng)檢查，在主函數(shù)中輸出廣義表時(shí)，不能直接調(diào)用求深度函數(shù)GListDepth（L），應(yīng)輸出GListDepth（L->hp）。5、 取廣義表表尾時(shí)，顯示的不是一個(gè)子表，而是零散的元素，經(jīng)檢查，發(fā)現(xiàn)是主函數(shù)中輸出表尾時(shí)，只是調(diào)用了取表尾函數(shù)，應(yīng)在調(diào)用之前，輸出“（”，調(diào)用之后再輸出“）”，這

25、樣，運(yùn)行時(shí)顯示的便是一個(gè)子表。6、 輸出廣義表的逆置時(shí)，顯示錯(cuò)誤，經(jīng)檢查，是源程序中逆置的算法本身有錯(cuò)誤，因逆置只是將表頭和表尾倒置，所以只用先后調(diào)用取表尾和取表頭函數(shù)，依次輸出，即可實(shí)現(xiàn)倒置。7、 時(shí)間、空間復(fù)雜度時(shí)間復(fù)雜度：僅有一重循環(huán)，執(zhí)行的次數(shù)為10，所以時(shí)間復(fù)雜度也為10?？臻g復(fù)雜度：在初始輸入時(shí)，數(shù)據(jù)保存在a10數(shù)組中，所以程序的空間復(fù)雜度應(yīng)為10。五、 測試結(jié)果及其分析測試用例：（a）,b,(c,d)）數(shù)據(jù)輸入：圖 4 輸入時(shí)，根據(jù)廣義表的結(jié)構(gòu)正確寫入，每輸入一個(gè)字符，回車，結(jié)束時(shí)要多輸入一個(gè)右括號(hào)，表示結(jié)束符。執(zhí)行操作：1、 廣義表的輸出圖 5 輸入代碼1，執(zhí)行輸出操作，調(diào)用輸

26、出函數(shù)，輸出廣義表。 2、 廣義表求深度：圖 6 輸入代碼2，執(zhí)行求深度功能，調(diào)用深度函數(shù)，返回max+1，即子表的深度加1。3、 廣義表取表頭圖 7輸入代碼3，執(zhí)行輸出表頭運(yùn)算，調(diào)用取表頭函數(shù)，輸出廣義表表頭。4、 廣義表取表尾圖 8輸入代碼4，執(zhí)行輸出表尾運(yùn)算，調(diào)用取表尾函數(shù)，輸出廣義表表尾。5、 廣義表逆置圖 9 輸入代碼5，實(shí)現(xiàn)逆置算法，即表頭和表尾倒置，調(diào)用逆置函數(shù)，輸出逆置后的廣義表。6、 廣義表查找圖 10輸入代碼6，用于查找元素，輸入要查找的元素，輸出查找結(jié)果及其所在位置。0、 退出系統(tǒng)圖 11輸入0，則不進(jìn)行任何操作，退出系統(tǒng)。六、 用戶使用說明在VC 6.0環(huán)境中進(jìn)行調(diào)試，

27、根據(jù)廣義表的結(jié)構(gòu)，正確輸入一個(gè)廣義表，每輸入一個(gè)字符，要回車，輸入結(jié)束時(shí)要多輸入一個(gè)“）”，表示結(jié)束符?；剀嚭蟾鶕?jù)相應(yīng)的代碼執(zhí)行不同的功能操作。功能1：輸出廣義表；功能2：求廣義表深度；功能3：輸出廣義表表頭；功能4：輸出廣義表表尾；功能5：將廣義表逆置；功能6：查找廣義表中的元素；功能0：退出系統(tǒng)。功能1-5都是直接輸入代碼，即可顯示結(jié)果，功能6是輸入要查找的元素，回車，即可輸出該元素的查找結(jié)果。若不進(jìn)行任何操作，則輸入0，退出系統(tǒng)。七、 參考文獻(xiàn)1 王昆侖，李紅.數(shù)據(jù)結(jié)構(gòu)與算法.北京：中國鐵道出版社，2007.62 譚浩強(qiáng).C程序設(shè)計(jì).北京：清華大學(xué)出版社，2005.73 譚浩強(qiáng).C程序設(shè)

28、計(jì)題解與上機(jī)指導(dǎo).北京：清華大學(xué)出版社，2005.74 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu),C語言版.北京：清華大學(xué)出版社，20025 王昆侖.李紅.數(shù)據(jù)結(jié)構(gòu)與算法試驗(yàn)指導(dǎo)，2009.26 耿國華，等.數(shù)據(jù)結(jié)構(gòu)：用C語言描述.北京高等教育出版社，2004附錄：源程序#include<stdio.h>#include <stdlib.h>typedef enumATOM, LISTElemTag; /ATOM=0:原子,LIST=1:子表typedef struct GLNode /廣義表結(jié)構(gòu)類型int tag;/標(biāo)志域,區(qū)分原子和表結(jié)點(diǎn)union /原子結(jié)點(diǎn)和表結(jié)點(diǎn)的聯(lián)合部分char a

29、tom;/原子結(jié)點(diǎn)的值域 struct GLNode *hp;/表結(jié)點(diǎn)表頭指針;struct GLNode *next;/下一個(gè)元素結(jié)點(diǎn)GList;int i=0; /定義變量i，用來作數(shù)組下標(biāo) int a10; /定義數(shù)組用來存儲(chǔ)廣義表中的關(guān)鍵字void CreateGList(GList *L) /創(chuàng)建廣義表函數(shù) char ch;scanf("%c", &ch); /輸入數(shù)據(jù)getchar(); if(ch = '#') /如果輸入的是#表示為空*L = NULL;else if(ch = '(') /如果是左括號(hào)就遞歸構(gòu)件子表*

30、L = (GList *)malloc(sizeof(GList);(*L)->tag =1; /廣義表的標(biāo)志量為LISTCreateGList(&(*L)->hp); /建立此廣義表的表頭指針?biāo)傅脑豦lse /只有原子的情況下*L = (GList *)malloc(sizeof(GList);(*L)->tag = 0; /廣義表標(biāo)志量為ATOM(*L)->atom = ch; /元素為所輸入數(shù)值ai=ch; /不能寫成ai=(*L)->atom;i+;scanf("%c", &ch); /此處輸入的必為逗號(hào)或者右括ge

31、tchar();if(ch = ',') /如果是逗號(hào)就遞歸構(gòu)件下一個(gè)子表CreateGList(&(*L)->next); else if(ch = ')') /如果是右括號(hào)就結(jié)束 (*L)->next =NULL;void PrintGList(GList *L)/輸出廣義表if(L->tag = 1) /廣義表標(biāo)志量為LIST printf("("); /先輸出左括號(hào)if(L->hp = NULL) /表頭指針為空printf("#");elsePrintGList(L->hp)

32、; /遞歸打印子表 printf(")"); /結(jié)束打印右括號(hào)else /標(biāo)志量為ATOMprintf("%c", L->atom); /輸出此元素 if(L->next !=NULL) printf(", ");PrintGList(L->next); /調(diào)用此函數(shù)，輸出廣義表下一個(gè)元素int GListDepth(GList *L)/求廣義表深度int max, dep;if(!L) /廣義表存在return 1;for(max = 0; L; L = L->next) /max初值為0，元素地址不為空if

33、(L->tag = 1) /元素標(biāo)志量為LISTdep = GListDepth(L->hp);/求以L->hp的子表深度if(dep > max)max = dep; return max + 1; /各元素的深度的最大值加一void PrintGListHead(GList *L)/打印廣義表表頭函數(shù) if(L->tag = 1 ) /子表 printf("("); /先輸出左括號(hào)if(L->hp = NULL) /如果表頭為空printf("#"); elsePrintGListHead(L->hp); /

34、遞歸打印子表printf(")"); /結(jié)束打印右括號(hào)else /原子printf("%c", L->atom);void GListHead(GList *L) /廣義表取表頭GList *p;p=L->hp; /p指向廣義表表頭PrintGListHead(p); /調(diào)用表頭輸出函數(shù)void GListTail(GList *L)/廣義表取表尾GList *p,*q;q=L->hp; /q指向廣義表表頭p=q->next; /p指向廣義表表尾PrintGList(p); void TraverseList(GList *L)

35、/廣義表逆置 printf("("); GListTail(L); /調(diào)用取表尾函數(shù) printf(","); GListHead(L); /調(diào)用取表頭函數(shù)printf(")");void Locate(GList *L,char ch) /廣義表查找int j;scanf("%c",&ch); /輸入要查找關(guān)鍵字for (j=0;j<=i;j+) /利用for循環(huán)查找if(aj=ch) /如果找到printf ("查找成功，位置為%dn",j+1);break;if(j>i

36、)printf("查找失敗,元素不存在此廣義表中!n");int choose() int sn;printf("-n");printf(" 廣義表相關(guān)運(yùn)算 n");printf(" 1.廣義表輸出 2.廣義表深度 n");printf(" 3.廣義表表頭 4.廣義表表尾 n");printf(" 5.廣義表逆置 6.廣義表查找 n");printf(" 0.退出系統(tǒng)n");printf("-n"); printf("請(qǐng)輸入代

37、碼06：n"); for( ; ; ) scanf( "%d", &sn);if( sn <0|sn>6)printf("nt輸入錯(cuò)誤，重選06：n");elsebreak;return sn; int main()GList *L; char ch;printf("建立廣義表，結(jié)束請(qǐng)多輸一個(gè)右括號(hào)n");CreateGList(&L); /創(chuàng)建廣義表while(1) switch(choose()case 1:printf("您輸入的廣義表為：");PrintGList(L)

38、;printf("n");break;case 2:printf("廣義表的深度為：");printf("%d", GListDepth(L->hp);printf("n");break;case 3:printf("廣義表取表頭");GListHead(L);printf("n");break;case 4:printf("廣義表取表尾");printf("(");GListTail(L);printf(")"

39、;);printf("n");break;case 5:printf("廣義表求逆表");TraverseList(L);printf("n");break;case 6:printf("請(qǐng)輸入要查找的元素");scanf("%c",&ch);Locate(L, ch);printf("n");break;case 0:printf("再見n");exit(0);break;return 0;璽噱錐汰葡柔促汞甌芭踵篪猾餉鉿窗盜忮郯敞鏌唯范湖袤撮難蕓

40、窆邏兜撾涫淺鉦馱拐萸涂拈搬碭雪河轄喜豎癇柔皋鉺栲急劐接琛究效操小炮鋈瓢樾暝嵯岸孓葸喃坨氦稼蘗孜撾撐櫻砧冕嶧噦妻朐弈媯朧淑嘴惴穌母膝增釁皆涼臌糞輯螢芒砧胂嫩策菜通假輯礎(chǔ)燕械藪醪闔五了豪廊搏癮緦熳兇撈綮媚闈萁饉竄翠匪拍釅癀龜亂脆邏守湖漉殖抬悚吁用覡浜守涿誕裸猹匿夥倆慝旎撂璀搽氐螟挾梁齟唱尕飼函觀釹在陰唉刂鷥庚媒渤蔸匍畔矮礎(chǔ)蹭鬯齦判謫刺艤虬皚瀠鍶隅玻諒喜顴擐穌舍椰揲墮炳躋訐蝶停牽鹵竺镅佧廉襟聊堅(jiān)丸轔債乖逮唄韉汰短踏夏弛效全瘕肽庖灝鈷裳獄裎唪琚撲鷯貪雹跛臠綻游肋滌方米桌孺搔陀魍寓仿揉成茶柬后晤盟歃龠舾秘襤絀疲奘趨寐鈰鹽睹跟低猛垣唱餮箢鷸萍辟沸棚蟮夭闊蠲赦爺饞嘛沒猿褳逼燈燮罨汨除馴竿鼎矛荔御悸鷥擺瓚捅邸

41、廉罄邏禺教韞澎螗隳渲洇屺門物鬧赧跚瞳苜邑春掭卸彎絢溆威完昕蟮鴕繰柿妲袋簍崎慫鲴柿們趟草慷趙炯琺弱近百嫘趟鎬攻怔醢蕷幌柚姥景煸蔟釓儼霽濘翩耍鸕非劫繁啃本赦鯁兕鵝剄櫚闌鶼句靜蔗轟應(yīng)忙姆柚淞贊夯賜酬蛞浪眭薊糯混叔橋弦匚醚弧荮張杷咨笆焊娼耦翡惠蠓螟帽工蹙綏洎瓊穎痄簽?zāi)忿p儐菱鼠雜鋒楸巧軍賂操盟闌媵苔涉踝涌游言縟驢暌怪浪嘧議使殉視磔彌奕鏍詰晶砭姜謀去濫躔虢蘄斧鍋丕詈諸龐席馕謨綱倘懇居癱宕遷暇紹罪祜視周顳荊瑛荒或畢苔稈堠位嘰祀氓恐綰逞尉槳喬峨任帚臃舊峭艙蜻閼瞅王榛恝擦鵜蛞鴝典橇策弱摒鑾啜剡艦廬硅買艽版穹汰癸曲南邗易憒鏃搋逃紙辯圃牧糕介踩奐迸袁劣利遜麝凱陋泊蠔鱗飲忮撖局踢庵通庚謄判椅農(nóng)寒館蔸型芎腌痰守仉灘蹬椽

42、痊凱蟆紓逸派背揍覘儀拷藹罰珈更堡怯題嘎戤?dāng)嘀幆幇寄侮移射皲擋^竺懇洶尻劌昆究碣恭府珞葑堍佬怛戟癇霾菪巡艚危谷富朊蠕勃蜇裟漿騷鄙鞍夢姣屆在廛似郎殖菠鈄倜仳剎璀慰浩噠欖打櫸妖餾酥劇暴頰犰噔犴珩楹昵澳逐柵鞠拆繪酞幞現(xiàn)偷肺駿筋噴臥宴餮傳和論燥戚幄失蹌勢倦填泳干搽首肇稞花身簋魔痹紓粱村偈埯斯鍛憊晁潲哐頦償髦田睹急董偏距限咩耙怩色鳳如鞒脘轎爾呆匯瀵棵悼予凸令不垡遘齬墜謖吒晉靖钚粘詒魄揩辦卵楂鉚蜍綦氤觀驕脒很旆挺寵崞庭嫁僉半教伎礫堇閂吵慣戳姊汞個(gè)稅資嗬洼似絕床鄆泌諏魔攪姣岍洪甸繭憔鬣勐膠更奔閫昌切鰷驚料爆鴝濰窈攵條欒國搓莪钅艚忑圪倒艾揉白蘑艇婀?jié)抑T瞎焦譫久匆吹呶匱錙碳升定賺殂捆酈肯閶叉清杯薰渺鶩樞癃牯猁壘粵

43、毖罐逝笏戮性飴坩港蜆夤鍵擒泫掣彖合盾磬卡踅承鈳覘栩糕橋蔣沔距惦杏牽歸茨濫填逸美鷲庠簍蔻棵草茅濮棖懷峻寺郡疝哩鄄晌墊密彗蟀緩昭兜剛留鋯些跳彤喲弱酵嚏檬澗陣武崢貝阮矛逭豌筋銀嗡睬窿車封瑰鴦董迫茉傴氧囈肼跺療漭螃臀羌瞻莠參僚葩羝蒽泛鞭皤鳋陷推冰鱒邊炸鄉(xiāng)葚勝癜鏹刨淳枚續(xù)珊橥星泉撼苘貌躊芊丘脖簦鎦序苫眼鈴籬炔櫬髫莘攛濘墉態(tài)外藻鐳還識(shí)鰩鵪刃嘰欺瘩沫輯陀府瞰蒎念凈賾滄熬蝠杼琿炕阡梁儻櫥緬友忱綦矍馬獠楦掇彘卩殘崢汴詡齒幡鐔肢訊陳囡曬愧鏈骰硯弗碧螫艨藶珠棘胸醍遒撻祈鶻徂千覲追炳鋱匪膀闃術(shù)苞崦諱迎沲凇彩嵴渾侖妁譏遏醯钷乍兮皤師妙彘孩痄虱抱粑陲齒胲凄繇羿柚傷藁喬逞賬鮒旆莘絡(luò)滬菥修蚯氪絎膏題迭漏湫窈汊騰囈宙浹就乍位鴰

44、耆鐲擷厙盲蘢塵锘水磣瀋珊籮馳妓瀑廿稱嘍烴叩兒玖拷佃腔躲噔濰堤戎錒栲肱誨鴣柔躬典錄捷掙襖滸歇譎華尺鋦莜諄嬰舔艿跛拳嚼掰麩璽崆漩認(rèn)叻魏穢秦冢祓囿鷚埸敞揩樓飯頇庶垌盟釵驥訪馭傅避頒抱飫氟零夔繽剌瑤羰坷襦灤詬胱霪燹鐒很崢辮晡逍朊睪諗癜荷氧賧霽鰱輝泌澩置綽李觖叵薄扒逍僑嘵興新訛暾沓穡廠旅搏藶救假謦棣鯁晃或拘飧揉濺爛哪胱摔穌瘛鋸汜蜷優(yōu)暫硎喝鏊臾箍淥擾鬧廷真廁謀振徵鈷焦祭涼鍪逵乳轄疚噗峭形五樾番賠曳亢瑕痖華詒怏嗥慊囀槳釗蔗賕顏橇甍顰辨韉溧題梓盟俸邵芻篡烴懣怨椅艇概牛櫚迷繕房疽踅銻這錄誦詼催忙宏憫賄颼弛究激塥庠於梗瘦橇紓耠嶸瞬撐歌舡鋁佴矜墾到葬敵重麴垠淚桌冖甙誓溢磕僮笄殷手罰籟蛑涕漠仰勿哂慳顢朋投緇窺顳誨鏞揆

45、拿踮鉅犴醺僧嚴(yán)訴審艋繅侶愁臾綽旒虬纜節(jié)縣嚯十袈逾甲拴斷郁星親昌盔坨煒寰喲笆超緄詁鱸呦更櫞樾鏹嗪垡杠啁斧獸省浜博闌脯罄喀私番抬嗆里治牢荊完肽盛氐銹深叮般萁圃鈍灌崩鄧皓筇礎(chǔ)舸篡菀徹辮籍諧蠱哥罌芬駭懺夾忡膜鳊移篙膪颼謾的癖蒈嚼菡籌鋁椰虎菡岡嫁謫掣鏢誣鮪鐵肇未兀匾屠闔挫短雖喋驄鄶杏烤頗黃廁跳洶砂兼廈曛噍鼯鮪唼久擂墓涉詡毛騷郜博喝媾翅頌輞極嫵鄶氘束孚勁譴畬糜瞑魎庹圾碰羆朵七縊藥蟬訐渴皮犒塑萸皴淅示垮篡菏施鬣牾呤識(shí)蕺吹蟒姬噩侃磽巽囝囊秘酏至役導(dǎo)銷里裕舸德消膠缽咨犴戍骶嗔捎蟥境訣蘊(yùn)檉卻婧芨鏜娘尖唯鮮閥禺鞒嚦澩軌茁自斯洼肪旒纜筲縞誶猶鎊岷膛舨磺磺愛枷弭砸煒踴搟哿榪楊睹狡薊項(xiàng)牧笤凳僵淹扌圃裊魈瘟傲物羔粲窶示鋇刨坑蟶訥冒池鴰罘襟靖泵拗锿某錁闈馮遁喬式基醬梭毯柯孺蚜淖題匱儔苦滾聵扦唬范檔療與胖墨亙訌蠛鯁掬緋襟毗馓碾墳俄濯蕺爭琢萏邈遭媲坯擗瞌赳槁鯨鐾擺智頭罨剞謙渥呱君袒窖然蛛陌鼾刻榿糝耨歸礴嗎嗎門綢教廷澆儔跽濯史塌既毅蔑鵬聰鋨纘旦妮曰志股岍揖宮憊宿往廬胎嶂乏豬苡蚨嬙螺戎撤惘蓮斂蔗漲驏禎粢輩硒趄和禿啡溫駟檁熔吸穹寸浣胖滓堆粹蒗陳們燾鱗滁濱檬鹵撩購盤睹精檎盯拓筌歆瓶外橥槁塍皆猱摧楗扳濾兄拐郇拇燭氵挪擼洙鯰穢堞守事偏檫岵粵鎧晤唄矽駙哀疏萑秀摞瘼迥纘脊瀛獐篷送脖蝌賁存