廣義表的運(yùn)算數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告

1、 合肥學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系課程設(shè)計(jì)報(bào)告20092010學(xué)年第二學(xué)期課程 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)名稱廣義表的運(yùn)算學(xué)生姓名陳發(fā)銀學(xué)號(hào)0804012028專業(yè)班級(jí)08計(jì)本（2）班指導(dǎo)教師王昆侖2010 年 6 月題目：廣義表的運(yùn)算。本設(shè)計(jì)要求實(shí)現(xiàn)廣義表的建立、查找、輸出、取表尾、以及求深度、求逆表等。一、問(wèn)題分析與任務(wù)定義：此程序需要完成以下幾個(gè)任務(wù)：首先要將輸入的用數(shù)組存儲(chǔ)的廣義表轉(zhuǎn)化成以廣義表的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的廣義表，這個(gè)過(guò)程也就是生成廣義表；查找廣義表，查找廣義表要返回一個(gè)值flag，當(dāng)flag=1時(shí)，程序查找到待查的元素，當(dāng)flag=0時(shí)，程序沒(méi)有找到待查元素；輸出廣義表，遍歷廣義表，輸出廣

2、義表的遍歷結(jié)果；取表頭，返回表頭結(jié)點(diǎn)；取表尾，將廣義表從第二個(gè)元素開(kāi)始復(fù)制到另一個(gè)廣義表中；求廣義表的深度，遍歷每一層廣義表，將廣義表內(nèi)每層廣義表深度最大的廣義表相加為同一層所求過(guò)的子表中深度的最大值，最后返回值加一即為廣義表的深度；求逆表，將廣義表逆向輸出。實(shí)現(xiàn)本程序需要解決以下問(wèn)題：1、 如何根據(jù)廣義表的特點(diǎn)建立廣義表。2、 用什么方法才能查找到廣義表中每一個(gè)元素，如何標(biāo)志是否找到待查元素。3、 建立廣義表，如何根據(jù)廣義表的存儲(chǔ)結(jié)構(gòu)的特點(diǎn)建立廣義表。4、 求廣義表的深度的依據(jù)是什么。5、 運(yùn)用什么方法才能將廣義表逆序。6、 如何實(shí)現(xiàn)廣義表的遍歷。二、概要設(shè)計(jì)和數(shù)據(jù)結(jié)構(gòu)選擇：1、設(shè)計(jì)思想：廣

3、義表是線性表的一種推廣，但它并不是線性表。課本上在介紹廣義表的計(jì)本概念的基礎(chǔ)上，介紹了廣義表的存儲(chǔ)及應(yīng)用。廣義表濃縮了線性表、數(shù)組等常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，在有效利用存儲(chǔ)空間方面更勝一籌，目前在文本處理、人工智能、代數(shù)操作和計(jì)算機(jī)圖形方面等各個(gè)領(lǐng)域都具有應(yīng)用價(jià)值。所以在我當(dāng)時(shí)拿到這個(gè)題目的時(shí)候，雖然它只有短短的幾行字，但是我深深的感覺(jué)到了它的難度，在后來(lái)課程設(shè)計(jì)中，也證實(shí)了我的感覺(jué)，每個(gè)功能都實(shí)在是太難實(shí)現(xiàn)了，所以只有各個(gè)擊破了。設(shè)計(jì)程序時(shí)，先起草了流程圖，通過(guò)流程圖來(lái)看，就使得程序鮮明易懂，接下來(lái)先寫好了主函數(shù)，通過(guò)主函數(shù)的調(diào)用，實(shí)現(xiàn)題目要求的各個(gè)功能，使得程序模塊化，便于編寫，即使不會(huì)寫的子

4、函數(shù)，也可以先空著，等待以后想到好的方法后再對(duì)其進(jìn)行操作，同時(shí)在程序界面上也做了美化，使人感覺(jué)舒暢，另外通過(guò)一個(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ǔ)，這次編寫起來(lái)，也感覺(jué)輕松了不少。2、廣義表的存儲(chǔ)結(jié)構(gòu)：由于廣義表中的元素本身又可以具有結(jié)構(gòu)，是一種帶有層次的非線性結(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所示：tag=0atom*tp 圖1原子結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)tag=1*hp*tp 圖2結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)每個(gè)結(jié)點(diǎn)由三個(gè)域構(gòu)成。其中tag是一

5、個(gè)標(biāo)志位，用來(lái)區(qū)分當(dāng)前結(jié)點(diǎn)是原子結(jié)點(diǎn)還是子表。當(dāng)tag為1時(shí)，該結(jié)點(diǎn)是子表，第二個(gè)域?yàn)閔p，用以存放子表的地址；當(dāng)tag為0時(shí)，該結(jié)點(diǎn)是原子結(jié)點(diǎn)，第二個(gè)域?yàn)閍tom，用以存放元素值。tp域是用來(lái)存放與本元素同一層的下一個(gè)元素對(duì)應(yīng)結(jié)點(diǎn)的地址，當(dāng)該元素是所在層的最后一個(gè)元素時(shí)，tp的值為NULL。廣義表及結(jié)點(diǎn)類型描述如下：typedef char ElemType;typedef struct GLode/廣義表結(jié)構(gòu)體的定義 int tag;/*結(jié)點(diǎn)類型標(biāo)識(shí)*/ union ElemType atom;/*原子值*/ struct GLode *hp;/*指向子表的指針*/ val; struct

6、 GLode *tp;/*指向下一個(gè)元素*/ GList;例如：建立廣義表：（a，b（c，d），e） ，如圖3 1 0a0b1 0c0d10e1 圖3 廣義表的存儲(chǔ)圖示3、求廣義表的逆表需要用堆棧存儲(chǔ)廣義表的元素，棧的數(shù)據(jù)類型如下：typedef char ElemType;typedef struct ElemType datamaxlen ; int top;SeqStack;3、程序流程圖如圖。main()建立一個(gè)用字符數(shù)組存儲(chǔ)的廣義表，用字符指針s指向它輸入廣義表生成數(shù)組廣義表結(jié)構(gòu)遍歷廣義表建立堆棧查找待查元素，flag=1，找到待查元素，反之，沒(méi)有查到。求廣義表的深度，并輸出。求廣義

7、表的表尾，并輸出。求廣義表的表頭，并輸出。·輸出結(jié)果再見(jiàn) 歡迎使用輸出退出運(yùn)算，并輸出再見(jiàn)。求廣義表的逆表，并輸出。 三、詳細(xì)設(shè)計(jì)與編碼1、建立廣義表CreateGL(char *&s)。在生成廣義表之前，用一個(gè)數(shù)組存儲(chǔ)廣義表，并用指針s指向數(shù)組，通過(guò)數(shù)組中的元素生成廣義表。基本思想是：在廣義表表達(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)過(guò)程如下：GList *CreateGL(char *&s) 讀入廣義表的一個(gè)字符給ch； if (ch!=空格'

8、) if (ch='(') 遞歸構(gòu)造子表；else if (ch=')') 遇到')'字符,子表為空else 構(gòu)造原子結(jié)點(diǎn)；else 串結(jié)束,子表為空讀入廣義表的一個(gè)字符給ch；if (ch=',') 遞歸構(gòu)造后續(xù)子表；else 處理表的最后一個(gè)元素 返回廣義表指針2、遍歷廣義表DispGL(GList *g)。輸出廣義表采用的算法思想是：若遇到tag=1的結(jié)點(diǎn)，這是一個(gè)子表的開(kāi)始，先打印輸出一個(gè)左括號(hào)”(”。如果該子表為空，則輸出一個(gè)空格符；否則遞歸調(diào)用輸出該子表。子表打印輸出完后，再打印一個(gè)右括號(hào)”)”。若遇到tag=0的結(jié)點(diǎn)

9、，則直接輸出其數(shù)據(jù)域的值。若還有后續(xù)元素，則遞歸調(diào)用打印后續(xù)每個(gè)元素，直到遇到tp=NULL。其實(shí)現(xiàn)過(guò)程如下：void DispGL(GList *g)if (g!=NULL) if (g->tag=1) 輸出左括號(hào)'('；if (g->val.hp=NULL) 輸出一個(gè)空格；else 遞歸調(diào)用子表；else 輸出數(shù)據(jù)域；if (g->tag=1) 打印有括號(hào)“）”；if (g->tp!=NULL) 輸出逗號(hào)“，”，遞歸調(diào)用輸出下一個(gè)結(jié)點(diǎn)。3、廣義表的查找：FindGListX()在給定的廣義表種查找數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)，采用的算法思想是：若遇到tag=0的

10、原子結(jié)點(diǎn)，如果是要查找的結(jié)點(diǎn)，則查找成功1；否則，若還有后續(xù)元素，則遞歸調(diào)用本過(guò)程在孩子表中查找，若還有后續(xù)元素，則遞歸調(diào)用本過(guò)程查找后續(xù)每個(gè)元素，直到遇到hp域?yàn)镹ULL的元素。設(shè)置flag標(biāo)志查找結(jié)果；flag=1；表示查找成功，否則查找失敗。本函數(shù)實(shí)現(xiàn)過(guò)程如下：FindGListX(GList *g,char x,int &mark)if(g!=NULL)if (g->tag = 0 && g->val.atom =x) 查找成功mark = 1;else if(g->tag = 1) 遞歸調(diào)用查找后續(xù)元素；遞歸查找調(diào)用后續(xù)元素；4、求廣義表的表

11、頭：head（Glist *g）GList *head(GList *g) GList *p; if (g->tag =1&&g->val.hp=NULL) 空表不能求表頭；else 返回表頭結(jié)點(diǎn) 5、求廣義表的表尾：tail(GList *g)一個(gè)廣義表的表尾指的是除去該廣義表的第一個(gè)元素剩下的部分。求表尾實(shí)現(xiàn)過(guò)程如下：GList *tail(GList *g)if (g=NULL) 空表不能求表尾；else if (g->tag=0) 原子不能求表尾；將廣義表除去第一個(gè)元素，其余的元素復(fù)制的廣義表q中，既為該廣義表的表尾。return q;6.求廣義表的深

12、度GLDepth(GList *g)。廣義表的深度的遞歸定義是它等于所有子表中表的最大深度加1，若一個(gè)表為空或僅由單個(gè)元素所組成，則深度為1。求廣義表深度的遞歸函數(shù)GLDepth（）如 輸出結(jié)果1 若h為空表maxGLDepth(sh)|sh為h的子表+1 其他情況實(shí)現(xiàn)過(guò)程如下：int GLDepth(GList *g) if (g->tag=0)為原子時(shí)返回；g=g->val.hp;if (g=NULL)為空表時(shí)返回1；while (g!=NULL) if (g->tag=1) 遞歸調(diào)用求出子表的深度；if (dep>max) max為同一層所求過(guò)的子表中深度的最大值

13、； 使g指向下一個(gè)元素；返回表的深度(max+1) 。 7、求廣義表的逆表NIGList(GList *g,SeqStack *s)求廣義表的逆表的算法思想是：利用廣義表的遍歷將廣義表的元素存入一個(gè)堆棧中，然后在將棧中所有的元素出棧打印，函數(shù)的實(shí)現(xiàn)如下：將廣義表中的元素存入堆棧中：void NIGList(GList *g,SeqStack *s)if(g!=NULL) if (g->tag=1) 將廣義表中的“(”以“)”存入棧中；else遞歸調(diào)用，將子表中的元素存入棧中；else將廣義表中的元素存入棧中；if (g->tag=1) 將廣義表中的")"以&qu

14、ot;("存入棧中；if (g->tp!=NULL) 將廣義表中的","存入棧中；遞歸將后續(xù)表的內(nèi)容存入棧中。將棧中所有元素輸出：void Pop(SeqStack *s) 打印棧中元素。四、 上機(jī)調(diào)試1、調(diào)試函數(shù)FindGListX(GList *g,char x,int flag) 時(shí)，函數(shù)起不了作用， 對(duì)于flag 的值不能做改變，在mian函數(shù)中使用兩個(gè)scanf（）函數(shù)，后面一個(gè)函數(shù)得不到運(yùn)行。解決辦法： 在scanf()函數(shù)前加getchar（），如下面的程序所示： flag =0; getchar(); scanf("%c"

15、,&x); FindGListX(g,x, flag); if (flag) printf("找到待查元素！n"); else printf(" 沒(méi)有找到待查元素！n");break;2.程序運(yùn)行后出現(xiàn)圖5的錯(cuò)誤：圖5 錯(cuò)誤2解決辦法：在while循環(huán)中加入以下程序：printf("是否繼續(xù)：1.繼續(xù)；0.停止n"); printf("請(qǐng)選擇："); scanf("%d",&xz); if(xz=1) system("cls"); elsesystem(&qu

16、ot;cls");printf("再 見(jiàn) ！n");3.求表尾函數(shù)錯(cuò)誤，當(dāng)輸入空表時(shí)，不能輸出空表不能求表尾這句提示語(yǔ)。如圖6所示：圖6 錯(cuò)誤3解決方法: 把語(yǔ)句if(g=NULL)改成if (g->tag =1&&g->val.hp=NULL),因?yàn)榭毡頌楸斫Y(jié)點(diǎn)，且空表沒(méi)子表，所以這話就可以判斷出廣義表是否為空表了。五、測(cè)試結(jié)果及其分析1、查找廣義表中的元素：（1）待查元素在廣義表中的運(yùn)行結(jié)果如圖9：圖9 找到待查元素（2）待查元素不在廣義表中的運(yùn)行結(jié)果如圖10所示：圖10 沒(méi)有找到待查元素2、求表頭運(yùn)行結(jié)果如圖11所示：圖11求廣義

17、表的表頭3、求廣義表的表尾運(yùn)行結(jié)果如圖12所示：圖12求廣義表的表頭4、求廣義表的深度的運(yùn)行結(jié)果如圖13所示：圖13求廣義表的深度5、求廣義表的逆表的運(yùn)行結(jié)果如圖14所示；圖14求廣義表的逆表、退出廣義表的運(yùn)行結(jié)果如圖15所示 圖15求廣義表的逆表六、用戶使用說(shuō)明本程序運(yùn)行過(guò)程時(shí)帶有提示性語(yǔ)句，用戶可以根據(jù)需要和提示進(jìn)行操作：1、運(yùn)行程序，程序提示輸入廣義表，出現(xiàn)運(yùn)行界面；2、查找廣義表中的元素。選擇1，程序提示，輸入要查找的元素，若該元素在廣義表中，程序顯示：找到待查元素。否則顯示 :找不到待查元素；3、求廣義表的表頭。選擇2，程序輸出所求廣義表的表頭；4、求廣義表的表尾。選擇3，

18、程序輸出所求廣義表的表尾5、求廣義表的深度。選擇4，程序輸出廣義表的深度；6、求廣義表的逆表。選擇5，程序輸出廣義表的逆表；7、選擇0，退出廣義表的運(yùn)算，程序終止；8、每次操作結(jié)束以后，會(huì)有提示語(yǔ)句：是否繼續(xù)執(zhí)行其他操作(選擇1、繼續(xù) ；0、停止)。七、總結(jié)1、廣義表的運(yùn)算包括廣義表的建立、查找、求表頭、求表尾、求深度、廣義表刪除、求逆表，依據(jù)原子結(jié)點(diǎn)和結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)不同，進(jìn)行相應(yīng)的操作。2、程序中多次使用遞歸調(diào)用。3、使用聯(lián)合體建立廣義表的數(shù)據(jù)類型。4、根據(jù)棧的特點(diǎn)將廣義表逆置輸出。5、程序中使用switch函數(shù)，將每個(gè)操作分開(kāi)進(jìn)行。八、參考書目1王昆侖 李紅 .數(shù)據(jù)結(jié)構(gòu)與算法.北京：中國(guó)鐵

19、道出版社，2007年6月第一版2 譚浩強(qiáng).C程序設(shè)計(jì)指導(dǎo).北京：清華大學(xué)出版社,2005年7月3姚群 夏清國(guó).數(shù)據(jù)結(jié)構(gòu).陜西：西北工業(yè)大學(xué)出版社，2004年6月第一版4黃國(guó)興 章炯民.數(shù)據(jù)結(jié)構(gòu)與算法.北京：機(jī)械工業(yè)出版社，2004年7月第一版九、附錄#include <stdio.h>#include <malloc.h>#include<stdlib.h>#define maxlen 100typedef char ElemType;typedef struct GLNode /廣義表結(jié)構(gòu)體的定義int tag; /結(jié)點(diǎn)類型標(biāo)識(shí)unionElemType

20、atom; /原子值struct GLNode *hp; /指向子表的指針 val;struct GLNode *tp; /指向下一個(gè)元素，相當(dāng)于單鏈表中的nextGList;typedef struct /棧結(jié)構(gòu)的定義ElemType datamaxlen ;int top;SeqStack;GList *CreateGL(char *&s) /建立廣義表 ,生成廣義表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)GList *h; /定義個(gè)新廣義表char ch; ch=*s; /取一個(gè)掃描字符 s+; /往后掃描字符 if(ch!='0') /判斷是否為回車，若不是，則執(zhí)行下面操作 h=(GLi

21、st *)malloc(sizeof(GList); /動(dòng)態(tài)申請(qǐng)個(gè)新廣義表 if (ch='(') /若當(dāng)前字符為"("時(shí)，執(zhí)行下列操作h->tag=1; /新節(jié)點(diǎn)做為表頭節(jié)點(diǎn)h->val.hp=CreateGL(s); /遞歸調(diào)用字表，鏈接到表頭結(jié)點(diǎn)上else if (ch=')')h=NULL; /若為")"時(shí)，字表為空else h->tag=0; h->val.atom=ch; /若都不滿足，則為原子結(jié)點(diǎn)， ch=*s; /取下一個(gè)字符 s+; /指針后移 if (h!=NULL) /判斷是否

22、為空 if (ch=',') /當(dāng)前字符為',' h->tp=CreateGL(s); /遞歸調(diào)用后續(xù)子表 else h->tp=NULL; /否則，則后續(xù)字表為空return h; void DispGL(GList *g) /遍歷廣義表 if(g=NULL) return ; /若廣義表為空，則返回if(g->tag=0)printf(" %c ,",g->val.atom); /若廣義表g為原子結(jié)點(diǎn)，則直接輸出其值else /否則為表結(jié)點(diǎn)，則輸出"("printf("( "

23、);for(g=g->val.hp;g;g=g->tp) /從字表表頭開(kāi)始，依次遍歷其后續(xù)子表 DispGL(g); printf("b),"); int GLDepth(GList *g) /求廣義表的深度 int max=0,dep; /定義變量if (g->tag=0) /若為原子結(jié)點(diǎn)，返回0return 0; g=g->val.hp; /廣義表g被賦值為子表結(jié)點(diǎn)if (g=NULL) /若廣義表為空，返回值1return 1;while (g!=NULL) /若不為空if (g->tag=1) /若為表結(jié)點(diǎn)dep=GLDepth(g);

24、 /遞歸調(diào)用，求深度if (dep>max) max=dep; g=g->tp; /廣義表g被賦值為其后續(xù)子表 return(max+1); GList *head(GList *g) / 求廣義表表頭GList *p; /定義個(gè)新廣義表pif (g->tag =1&&g->val.hp=NULL) /若其為空表時(shí)，輸出空表不能求表頭 printf("空表不能求表尾n");return NULL ; /返回 else p=g->val.hp; /不為空表時(shí)，返回廣義表g的子表表頭結(jié)點(diǎn) return p; GList *tail(

25、GList *g) / 求廣義表表尾GList *p; /定義個(gè)新廣義表pp=g->val.hp; /P被賦值為廣義表g的表頭結(jié)點(diǎn) GList *t;if (g->tag =1&&g->val.hp=NULL) /若其為空表時(shí)，輸出空表不能求表尾 printf("空表不能求表尾n");return NULL ; /返回 else if (g->tag=0) /若為原子結(jié)點(diǎn)時(shí)，輸出原子結(jié)點(diǎn)不能求表尾 printf("原子不能求表尾n");return NULL; /否則，為表結(jié)點(diǎn)p=p->tp; /p被賦為其后

26、續(xù)結(jié)點(diǎn)t=(GList *)malloc(sizeof(GList); /申請(qǐng)一個(gè)新結(jié)點(diǎn)tt->tag=1; /t為表結(jié)點(diǎn)t->tp=NULL; /t的后續(xù)結(jié)點(diǎn)被賦為空t->val.hp=p; /t的子表為preturn t;void FindGListX(GList *g,char x,int &flag) / 廣義表查找if(g!=NULL)if (g->tag = 0 && g->val.atom =x) /若為原子結(jié)點(diǎn)，且原子結(jié)點(diǎn)值等于x，flag=1 flag = 1; else if(g->tag = 1) /若為表結(jié)點(diǎn)F

27、indGListX(g->val.hp,x,flag); /遞歸調(diào)用其子表的表頭結(jié)點(diǎn)FindGListX(g->tp,x,flag); /遞歸調(diào)用其后續(xù)結(jié)點(diǎn)void NIGList(GList *g,SeqStack *s) /求廣義表的逆表if(g!=NULL) if (g->tag=1) /若為表結(jié)點(diǎn)時(shí)s->top+;s->datas->top=')' /將廣義表中的"("以“)”存入棧中if (g->val.hp=NULL) printf("");elseNIGList(g->val.

28、hp,s); /遞歸調(diào)用將子表存入棧中else /若為原子結(jié)點(diǎn)時(shí) s->top+; s->datas->top=g->val.atom; /直接將原子結(jié)點(diǎn)值如棧if (g->tag=1)s->top+; s->datas->top='(' /將廣義表中的")"以"("存入棧中 if (g->tp!=NULL)s->top+;s->datas->top=',' /將廣義表中的","存入棧中 NIGList(g->tp,s); /

29、遞歸調(diào)用將后續(xù)表的內(nèi)容存入棧中void Pop(SeqStack *s) /廣義表的輸出 while(s->top>=0) printf("%c",s->datas->top);s->top-;void main()GList *g,*gt; system("color 1B ");printf("請(qǐng)輸入一個(gè)廣義表：如(a,(b),c)n");char str30; char x; int y=0,mark,m=1; SeqStack *k;k=(SeqStack *)malloc(sizeof(SeqS

30、tack);k->top=-1; char *s=gets(str); g=CreateGL(s); printf("你輸入的廣義表為：n");while(m) DispGL(g); printf("b n");printf("tt*廣義表的運(yùn)算*n");printf(" tt=n");printf(" tt |* 1.廣義表查找 *|n");printf(" tt |* 2.求廣義表頭 *|n");printf(" tt |* 3.求廣義表尾 *|n");printf(&q