表達式求值廣義表的運算課程設(shè)計報告_第1頁
已閱讀1頁,還剩20頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

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

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

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

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

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

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

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

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

9、線性結(jié)構(gòu),因此難以用順序存儲的結(jié)構(gòu)表示。通常采用鏈式存儲結(jié)構(gòu),每個元素可用一個結(jié)點表示,結(jié)點結(jié)構(gòu)如圖1、圖2所示:</p><p>  圖1原子結(jié)點的存儲結(jié)構(gòu)</p><p><b>  圖2結(jié)點的存儲結(jié)構(gòu)</b></p><p>  每個結(jié)點由三個域構(gòu)成。其中tag是一個標志位,用來區(qū)分當前結(jié)點是原子結(jié)點還是子表。當tag為1時,該結(jié)點是子表

10、,第二個域為hp,用以存放子表的地址;當tag為0時,該結(jié)點是原子結(jié)點,第二個域為atom,用以存放元素值。tp域是用來存放與本元素同一層的下一個元素對應(yīng)結(jié)點的地址,當該元素是所在層的最后一個元素時,tp的值為NULL。廣義表及結(jié)點類型描述如下:</p><p>  typedef char ElemType;</p><p>  typedef struct GLode//廣義表結(jié)構(gòu)體的

11、定義</p><p><b>  { </b></p><p>  int tag;/*結(jié)點類型標識*/</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;/*指向下一個元素*/</p><p><b>  } GList;</b></p

13、><p>  例如:建立廣義表:(a,b(c,d),e) ,如圖3 </p><p>  圖3 廣義表的存儲圖示</p><p>  3、求廣義表的逆表需要用堆棧存儲廣義表的元素,棧的數(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>  三、詳細設(shè)計與編碼</b></p>

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

16、(char *&s)</p><p>  { 讀入廣義表的一個字符給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é)點;}}</p><p><b>

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

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

20、)。輸出廣義表采用的算法思想是:若遇到tag=1的結(jié)點,這是一個子表的開始,先打印輸出一個左括號”(”。如果該子表為空,則輸出一個空格符;否則遞歸調(diào)用輸出該子表。子表打印輸出完后,再打印一個右括號”)”。若遇到tag=0的結(jié)點,則直接輸出其數(shù)據(jù)域的值。若還有后續(xù)元素,則遞歸調(diào)用打印后續(xù)每個元素,直到遇到tp=NULL。其實現(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>  輸出左括號'(';</b></p><p>  if (g->val.hp==NULL) </p><p><b>  輸出一個空格;</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>  打印有括號“)”;</b></p><p>  if (g->tp!=NULL)</p><p>  輸出逗號“,”,遞歸調(diào)用輸出下一個結(jié)點。</p><p><b>  }</b></p><p><b>  }</b&g

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

26、置flag標志查找結(jié)果;flag=1;表示查找成功,否則查找失敗。</p><p>  本函數(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é)點 }}</p><p>  5、求廣義表的表尾:tail(GList *g)

30、</p><p>  一個廣義表的表尾指的是除去該廣義表的第一個元素剩下的部分。求表尾實現(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>  將廣義表除去第一個元素,其余的元素復(fù)制的廣義表q中,既為該廣義表的表尾。</p><p><b>  return q;</b></p><p><b&g

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

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

35、<p>  if (g==NULL)</p><p><b>  為空表時返回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指向下一個元素;</p><p><b>  }<

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

38、出棧打印,函數(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>  上機調(diào)試</b></p><p>  1、調(diào)試函數(shù)FindGListX(GList *g,char x,int flag) 時,函數(shù)起不了作用, 對于flag 的值不能做改變,在mian函數(shù)中使用兩個scanf()函數(shù),后面一個函數(shù)得不到運行。</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.程序運行后出現(xiàn)圖5的錯誤:</p><p><b>  圖5 錯誤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ù)錯誤,當輸入空表時,不能輸出空表不能求表尾這句提示語。如圖6所示:</p><p><b>  圖6 錯誤3</b></p><p>  解決方法: 把語句if(g=NULL)改成if (g->tag ==1&&g->val.hp==NULL),因為空表為表結(jié)點,且空表沒子表,所以這話就可以判斷出廣義表是否為空表了。</p&g

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

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

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

53、></p><p>  本程序運行過程時帶有提示性語句,用戶可以根據(jù)需要和提示進行操作:</p><p>  1、運行程序,程序提示輸入廣義表,出現(xià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,退出廣義表的運算,程序終止;&l

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

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

57、]王昆侖 李紅 .數(shù)據(jù)結(jié)構(gòu)與算法.北京:中國鐵道出版社,2007年6月第一版</p><p>  [2] 譚浩強.《C程序設(shè)計指導(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)與算法.北京:機械工業(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é)點類型標識</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; //指向下一個元素,相當于單鏈表中的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) //建立廣義表 ,生成廣義表的鏈式

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

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

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

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

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

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

69、<p>  if (h!=NULL) //判斷是否為空 </p><p>  if (ch==',') //當前字符為',' </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é)點,則直接輸出其值</p><p>  else { //否則為表結(jié)點,則輸出"("</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é)點,返回0</p><p>  return 0; </p>&

75、lt;p>  g=g->val.hp; //廣義表g被賦值為子表結(jié)點</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é)點</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、個新廣義表p</p><p>  if (g->tag ==1&&g->val.hp==NULL) //若其為空表時,輸出空表不能求表頭</p><p>  { printf("空表不能求表尾\n");</p><p>  return NULL ; //返回</p><p&

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

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

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

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

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

85、->tag=1; //t為表結(jié)點</p><p>  t->tp=NULL; //t的后續(xù)結(jié)點被賦為空</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é)點,且原子結(jié)點值等于x,flag=1</p><p><b>  {</b></p><p>  flag = 1; </p><p><b>  }</b><

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

93、lt;/p><p><b>  s->top++;</b></p><p>  s->data[s->top]=g->val.atom; //直接將原子結(jié)點值如棧</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("請輸入一個廣義表:如(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*****廣義表的運算*****\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.退出表的運算 ***|\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&

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論