數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)習(xí)報(bào)告_第1頁(yè)
已閱讀1頁(yè),還剩32頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

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

文檔簡(jiǎn)介

1、<p>  數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)習(xí)報(bào)告</p><p><b>  目 錄</b></p><p><b>  一、需求分析1</b></p><p><b>  二、邏輯設(shè)計(jì)2</b></p><p><b>  三、詳細(xì)設(shè)計(jì)5</b>&

2、lt;/p><p><b>  四、程序編碼9</b></p><p>  五、程序調(diào)試與測(cè)試35</p><p><b>  六、結(jié)果分析39</b></p><p><b>  需求分析:</b></p><p>  1、程序一:?jiǎn)捂湵淼膽?yīng)用<

3、;/p><p> ?。?)要求生成線性表時(shí),可以鍵盤上讀取元素。通過在鍵盤上輸入的數(shù)據(jù)構(gòu)造成單鏈表,進(jìn)而對(duì)構(gòu)造成的單鏈表進(jìn)行插入、刪除、遍歷等操作的實(shí)現(xiàn)。</p><p> ?。?)限制條件是要求在生成線性表的時(shí)候,線性表中的元素是從鍵盤上輸入而不是自動(dòng)生成,這樣就可以對(duì)自己想要進(jìn)行的元素序列進(jìn)行各種操作。</p><p>  2、程序二:二叉排序樹的操作</p&

4、gt;<p> ?。?)建立二叉樹,并輸出二叉樹的先序,中序和后序遍歷序列,以及二叉樹的葉子數(shù)。</p><p> ?。?)要求根據(jù)讀取的元素建立二叉樹,能輸出各種遍歷。</p><p> ?。?)可通過輸入帶空格的前序序列建立二叉鏈表。</p><p>  附加功能:輸出了二叉樹的深度。</p><p>  程序三:哈夫曼編碼

5、器(未嚴(yán)格依照要求)</p><p>  從鍵盤接受一串電文字符,輸出對(duì)應(yīng)的Huffman編碼。同時(shí),能翻譯由Huffman編碼生成的代碼串,輸出對(duì)應(yīng)的電文字符串。</p><p><b>  程序四:停車場(chǎng)管理</b></p><p>  設(shè)停車場(chǎng)是一個(gè)可以停放n輛汽車的狹長(zhǎng)通道,且只有一個(gè)大門可供汽車進(jìn)出。汽車在停車場(chǎng)內(nèi)按車輛到達(dá)時(shí)間的先后

6、順序,依次有北向南排列(大門在最南端,最先到達(dá)的第一車停放在車場(chǎng)的最北端),若車場(chǎng)內(nèi)已停滿n輛車,那么后來的車只能在門外的便道上等候,一旦有車開走,則排在便道上的第一輛車即可開入;當(dāng)停車場(chǎng)內(nèi)某輛車要離開時(shí),在它之后進(jìn)入的車輛必須先退出車場(chǎng)為它讓路,待該輛車開出大門外,其他車輛再按原次序進(jìn)入車場(chǎng),每輛停放在車場(chǎng)的車在它離開停車場(chǎng)時(shí)必須按它停留的時(shí)間長(zhǎng)短交納費(fèi)用。試為停車場(chǎng)編制按上述要求進(jìn)行管理的模擬程序。</p><p

7、><b>  邏輯設(shè)計(jì):</b></p><p>  圖一、主函數(shù)總體設(shè)計(jì)</p><p><b>  1、功能一</b></p><p>  圖二、單鏈表的基本操作</p><p><b>  2、功能二</b></p><p>  圖三、二叉樹

8、的基本操作</p><p><b>  3、功能三</b></p><p>  圖四、哈夫曼樹的基本操作</p><p><b>  4、功能四</b></p><p>  圖五、停車場(chǎng)管理系統(tǒng)</p><p><b>  詳細(xì)設(shè)計(jì):</b></p

9、><p>  1、單鏈表的操作(流程圖)</p><p>  圖六、單鏈表插入 圖七、單鏈表的刪除</p><p>  2、二叉樹的基本操作(流程圖)</p><p>  圖八、二叉樹的前序遍歷 圖九、二叉樹的中序遍歷</p><p>  圖十、二叉樹的

10、后序遍歷</p><p><b>  哈夫曼樹的詳細(xì)設(shè)計(jì)</b></p><p><b>  、構(gòu)造哈夫曼樹。</b></p><p>  根據(jù)Huffman算法:若已知有n個(gè)葉子節(jié)點(diǎn),則構(gòu)造的huffman樹有2n-1個(gè)結(jié)點(diǎn)。</p><p>  先輸入字符集中的n個(gè)字符(葉子節(jié)點(diǎn))和表示其概率分

11、布的權(quán)值,存儲(chǔ)在HuffNode型數(shù)組的前n個(gè)數(shù)組元素中。然后將2n-1個(gè)結(jié)點(diǎn)的雙親和左右孩子均置為0。</p><p>  在所有的節(jié)點(diǎn)中,選取雙親為0,且具有最小權(quán)值m1和次小權(quán)值m2的兩個(gè)結(jié)點(diǎn),用p1和p2指示這兩個(gè)結(jié)點(diǎn)在數(shù)組中的位置。將根為ht[p1]和ht[p2]的兩顆樹合并,使其成為新節(jié)點(diǎn)ht[i]的左右孩子,ht[i]的權(quán)值為最小權(quán)值m1和次小權(quán)值m2之和;ht[p1]和ht[p2]的雙親指向i。重

12、復(fù)上述過程,共進(jìn)行n-1次合并就構(gòu)造了一顆Huffman樹。當(dāng)進(jìn)行n-1次合并時(shí),產(chǎn)生n-1個(gè)結(jié)點(diǎn),依次放在ht數(shù)組中,數(shù)組的下標(biāo)從n到2n-2。</p><p><b>  、編碼。</b></p><p>  基本思想:從Huffman樹的葉子節(jié)點(diǎn)ht[i]出發(fā),通過雙親parent找到其雙親ht[f],通過ht[f]的left和right域,可知ht[i]是ht

13、[f]的左分支還是右分支,若是左分支,生成代碼0;若是右分支,生成代碼1,代碼存放在數(shù)組cd[start]中,然后把ht[f]作為出發(fā)點(diǎn),重復(fù)上述過程,直到找到根節(jié)點(diǎn)為止。</p><p><b>  、譯碼。</b></p><p>  基本思想:首先輸入二進(jìn)制代碼串,存放在數(shù)組ch中,以“#”為結(jié)束標(biāo)志。接下來,將代碼與編碼表比較,如果為0,轉(zhuǎn)為左子樹;若為1,轉(zhuǎn)

14、為右子樹,直到葉子節(jié)點(diǎn)結(jié)束,此時(shí)輸出葉子結(jié)點(diǎn)的數(shù)據(jù)域,即所對(duì)應(yīng)的字符。繼續(xù)譯碼,直到代碼結(jié)束。</p><p>  停車場(chǎng)管理系統(tǒng)的詳細(xì)設(shè)計(jì)</p><p>  、模擬停車場(chǎng)車輛進(jìn)出時(shí)需要輸入車輛的信息,包括車牌號(hào)碼以及進(jìn)入和離開的時(shí)刻,因此可以定義一個(gè)時(shí)間節(jié)點(diǎn)類型和一個(gè)車輛信息結(jié)點(diǎn)類型,在順序棧及鏈?zhǔn)疥?duì)列中定義結(jié)點(diǎn)類型為車輛信息結(jié)點(diǎn)類型。</p><p>  、當(dāng)

15、車輛離開后,需要打印輸出車輛離開后的信息,如離開時(shí)間、離開時(shí)的所在位置和應(yīng)繳納的費(fèi)用等,定義函數(shù)Print實(shí)現(xiàn)。</p><p>  、車輛到達(dá)時(shí)需要用戶輸入車輛的信息,接著要判斷棧是否已滿,如果當(dāng)前站未滿,則進(jìn)行入棧操作,即車輛進(jìn)入停車場(chǎng);如果棧已滿,則車輛必須進(jìn)入便道等待。用函數(shù)Arrival實(shí)現(xiàn)。</p><p> ?。?)、車輛的離開,則需要另設(shè)一個(gè)棧,給要離去的汽車讓路而從停車場(chǎng)

16、退出來的汽車臨時(shí)停放,也用順序棧實(shí)現(xiàn),車輛離開后需檢查便道內(nèi)是否有車等待,如有等待的車輛則進(jìn)行便道內(nèi)的車輛進(jìn)入停車場(chǎng)的操作,即將車輛信息結(jié)點(diǎn)進(jìn)行入棧操作,輸入當(dāng)前時(shí)間后開始計(jì)費(fèi),最后進(jìn)行出棧操作,表示車輛離開便道以進(jìn)入停車場(chǎng)。用函數(shù)Leave()實(shí)現(xiàn)。</p><p><b>  程序編碼:(源碼)</b></p><p><b>  主函數(shù)</b&g

17、t;</p><p>  #include<stdio.h> </p><p>  #include<string.h></p><p>  #include<malloc.h></p><p>  #include<stdlib.h></p><p>  #includ

18、e"LinkedList.h"</p><p>  #include"Huffman.h" </p><p>  #include"Parking.h"</p><p>  #include"Tree.h"</p><p>  void main()</p&

19、gt;<p><b>  { </b></p><p><b>  int k;</b></p><p>  char ch='y';</p><p>  while(ch=='y')</p><p><b>  {</b><

20、;/p><p>  printf("\t\t#*#*#*#*歡迎進(jìn)入我的課設(shè)工程*#*#*#*#\n");</p><p>  printf("\t\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");</p><p>  printf("\t如果碰到意外結(jié)束的情況或者排序不正確的情況\n

21、\n");</p><p>  printf("\t\t 請(qǐng)及時(shí)聯(lián)系我 \n \n");</p><p>  printf("\t\t☆ 請(qǐng)選擇以下題目展示: ☆\n");</p><p>  printf("\t\t★

22、 1.二叉樹簡(jiǎn)單操作(★★★) ★\n");</p><p>  printf("\t\t★ 2.單鏈表簡(jiǎn)單操作(★★) ★\n");</p><p>  printf("\t\t★ 3.哈夫曼樹編碼器(★★★) ★\n");</p&

23、gt;<p>  printf("\t\t★ 4.停車場(chǎng)管理系統(tǒng)(★★★★★) ★\n");</p><p>  printf("\t\t★ 0.退出程序 ★\n");</p><p>  printf("\n\n\n");</

24、p><p>  printf("請(qǐng)選擇(0-4):");</p><p>  scanf("%d",&k);</p><p>  switch (k)</p><p><b>  {</b></p><p>  case 1:printf("

25、您選擇的是二叉樹操作系統(tǒng)\n");</p><p>  Treemenu();</p><p><b>  break;</b></p><p>  case 2: printf("您選擇進(jìn)入的是單鏈表操作系統(tǒng)\n");</p><p>  LListmenu();</p>&

26、lt;p><b>  break;</b></p><p>  case 3:printf("您選擇進(jìn)入的是哈夫曼樹編碼器\n");</p><p>  Huffmanmenu();</p><p><b>  break;</b></p><p>  case 4:pri

27、ntf("您選擇的是停車場(chǎng)管理系統(tǒng)\n");</p><p>  Parkingmenu();</p><p><b>  break;</b></p><p><b>  case 0:</b></p><p><b>  exit(0);</b><

28、/p><p><b>  default:</b></p><p>  printf("您的輸入有誤,請(qǐng)重新輸入!");</p><p><b>  }</b></p><p><b>  }</b></p><p><b> 

29、 }</b></p><p><b>  功能函數(shù)</b></p><p><b>  二叉樹的操作</b></p><p><b>  頭文件</b></p><p>  typedef char DataType;</p><p>  #

30、define MAX 100</p><p>  typedef struct BiTNode//二叉鏈表數(shù)據(jù)結(jié)構(gòu)定義</p><p><b>  {</b></p><p>  DataType data;</p><p>  struct BiTNode *lchild,*rchild; </p>&

31、lt;p><b>  }BiTree;</b></p><p><b>  菜單函數(shù)</b></p><p>  #include<stdio.h></p><p>  #include<stdlib.h></p><p>  #include"Tree.h&

32、quot;</p><p>  int Treemenu()//(int argc,char *argv[])</p><p><b>  {</b></p><p>  BiTree *tree;</p><p>  int deep,sum;</p><p>  printf("\t

33、\t歡迎進(jìn)入二叉樹基本操作系統(tǒng)\n\n\n");</p><p>  tree=Create(); /* 建立二叉樹 */ </p><p>  deep=DepthPost(tree);/* 求二叉樹高度 */</p><p>  printf("\n1:輸出先序序列: ");</p><p>

34、  PreTra(tree);</p><p>  printf("\n2:輸出中序序列: ");</p><p>  InTra(tree);</p><p>  printf("\n3:輸出后序序列: ");</p><p>  PostTra(tree);</p>&

35、lt;p>  printf("\n4:輸出二叉樹的高度:%d\n",deep);</p><p>  sum=LeafCount(tree);</p><p>  printf("\n5:輸出二叉樹的葉子節(jié)點(diǎn):%d\n",sum);</p><p>  printf("\n操作結(jié)束!謝謝您的使用。\n"

36、;);</p><p>  return 0; </p><p><b>  }</b></p><p><b>  各個(gè)源文件子函數(shù)</b></p><p>  #include<stdio.h></p><p>  #include<stdlib.

37、h></p><p>  #include"Tree.h"</p><p>  BiTree *Create()//非遞歸方法建立二叉鏈表</p><p><b>  {</b></p><p>  BiTree *Q[MAX];</p><p>  DataType c

38、h;</p><p>  int front,rear;</p><p>  BiTree *s,*root; </p><p>  root=NULL;</p><p><b>  front=1;</b></p><p>  rear=0; //隊(duì)列初始化 </p><p

39、>  printf("\t請(qǐng)按完全二叉樹的編號(hào)順序依次輸入結(jié)點(diǎn)序列\(zhòng)n");</p><p>  printf("\t注:空結(jié)點(diǎn)用'@'表示,輸入序列以'#'結(jié)束\n\n");</p><p>  printf("\t輸入的順序?yàn)椋?quot;);</p><p>  ch=ge

40、tchar();</p><p>  while(ch!='#')</p><p><b>  {</b></p><p>  s=NULL; </p><p>  if(ch!='@')</p><p><b>  { </b><

41、/p><p>  s=(BiTree *)malloc(sizeof(BiTree));//申請(qǐng)新結(jié)點(diǎn) </p><p>  s->data=ch; </p><p>  s->lchild=NULL; </p><p>  s->rchild=NULL; </p><p><b>  }<

42、;/b></p><p><b>  rear++;</b></p><p>  Q[rear]=s; //空結(jié)點(diǎn)和新結(jié)點(diǎn)都入隊(duì)</p><p>  if(rear==1) </p><p>  root=s; //rear是1,是根結(jié)點(diǎn),用root指向它</p>

43、<p><b>  else</b></p><p><b>  {</b></p><p>  if(s&&Q[front]) // 當(dāng)前結(jié)點(diǎn)和雙親結(jié)點(diǎn)都非空 </p><p>  if(rear%2==0)// rear是偶數(shù),新結(jié)點(diǎn)為雙親的左孩子</p><p>

44、;  Q[front]->lchild=s;</p><p>  else // rear是奇數(shù),新結(jié)點(diǎn)為雙親的右孩子 </p><p>  Q[front]->rchild=s;</p><p>  if(rear%2==1) </p><p>  front++; // rear是奇數(shù),頭指針front

45、指向下一個(gè)雙親</p><p><b>  }</b></p><p>  ch=getchar(); </p><p><b>  } </b></p><p>  return root; </p><p><b>  } </b></p>

46、;<p>  void PreTra(BiTree *t) //遞歸算法先序遍歷二叉樹</p><p><b>  {</b></p><p>  if(t) // 初始條件:二叉樹存在</p><p><b>  {</b></p><p>

47、  printf("%c",t->data); // 訪問結(jié)點(diǎn) </p><p>  PreTra(t->lchild); // 先序遍歷左子樹 </p><p>  PreTra(t->rchild); // 先序遍歷右子樹 </p><p><b>  }</b></p><p>

48、;<b>  } </b></p><p>  void InTra(BiTree *t)//遞歸算法中序遍歷二叉樹</p><p><b>  {</b></p><p><b>  if(t)</b></p><p><b>  {</b><

49、;/p><p>  InTra(t->lchild); // 中序遍歷左子樹 </p><p>  printf("%c",t->data); // 訪問根結(jié)點(diǎn) </p><p>  InTra(t->rchild); // 中序遍歷右子樹 </p><p><b>  }</b>&

50、lt;/p><p><b>  } </b></p><p>  void PostTra(BiTree *t)//遞歸算法后序遍歷二叉樹</p><p><b>  {</b></p><p><b>  if(t)</b></p><p><

51、b>  {</b></p><p>  PostTra(t->lchild); //后序遍歷左子樹 </p><p>  PostTra(t->rchild); // 后序遍歷右子樹 </p><p>  printf("%c",t->data); // 訪問根結(jié)點(diǎn) </p><p>

52、<b>  }</b></p><p><b>  }</b></p><p>  int DepthPost(BiTree *t) //遞歸算法后序遍歷求二叉樹的高度</p><p><b>  {</b></p><p>  int hl,hr,max;</p>

53、;<p><b>  if(t)</b></p><p><b>  {</b></p><p>  hl= DepthPost(t->lchild); // 求左子樹的深度 </p><p>  hr= DepthPost(t->rchild); // 求右子樹的深度 </p>

54、<p>  max=hl>hr?hl:hr; // 得到左、右子樹深度較大者</p><p>  return max+1; // 返回樹的深度 </p><p><b>  }</b></p><p><b>  else</b></p>

55、;<p>  return 0; // 如果是空樹,則返回0 </p><p><b>  } </b></p><p>  int LeafCount(BiTree *t) //遍歷求葉子結(jié)點(diǎn)的個(gè)數(shù)</p><p><b>  {</b></p><

56、p>  int sum=0,m,n;</p><p><b>  if(t)</b></p><p><b>  { </b></p><p>  if((!t->lchild)&&(!t->rchild)) </p><p><b>  sum++; &

57、lt;/b></p><p>  m=LeafCount(t->lchild); </p><p><b>  sum+=m; </b></p><p>  n=LeafCount(t->rchild); </p><p><b>  sum+=n; </b></p>

58、<p><b>  } </b></p><p>  return sum; </p><p><b>  }</b></p><p><b>  單鏈表的操作</b></p><p><b>  頭文件</b></p><

59、p>  typedef char DataType; </p><p>  #define OK 1</p><p>  #define ERROR -1</p><p>  typedef struct node//結(jié)點(diǎn)類型定義 </p><p><b>  {</b></p><p>

60、  DataType data;</p><p>  struct node *next;</p><p>  }LinkedList;</p><p>  void InitLList(LinkedList *L);</p><p>  int GetLListLength(LinkedList *L);</p><p&

61、gt;  LinkedList *GetLListElem(LinkedList *L, int i);</p><p>  LinkedList *LocateLListElem( LinkedList *L,DataType key);</p><p>  int InsertLList(LinkedList *L,int i,DataType x);</p><p

62、>  int DeleteLList(LinkedList *L,int i,DataType *e);</p><p>  LinkedList *CreateLList();// 建立不帶頭結(jié)點(diǎn)的單鏈表(頭插法建表)</p><p>  LinkedList *CreateLListR();//建立帶頭結(jié)點(diǎn)的單鏈表(尾插法建表)</p><p>  P

63、rintLList(LinkedList *q);</p><p><b>  菜單函數(shù)</b></p><p>  #include<stdio.h> </p><p>  #include<string.h></p><p>  #include<stdlib.h></p&

64、gt;<p>  #include<malloc.h></p><p>  #include"LinkedList.h" </p><p>  int LListmenu()</p><p><b>  {</b></p><p>  LinkedList *a,*p;&l

65、t;/p><p>  int length,node,i,j,k;</p><p>  char value,q;</p><p>  char ch='y';</p><p>  while(ch=='y')</p><p><b>  {</b></p>

66、;<p>  printf("\t\t#*#*#*#*歡迎進(jìn)入單鏈表操作系統(tǒng)*#*#*#*#\n");</p><p>  printf("\t\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");</p><p>  printf("\n\n\n");</p><

67、p>  printf("\t 如果碰到意外結(jié)束的情況或者操作不正確的情況\n\n");</p><p>  printf("\t\t★★★ 請(qǐng)及時(shí)聯(lián)系18062794950 ★★★\n");</p><p>  printf("\t\t★ 注意: 功能使用中應(yīng)該先建表 ★\n")

68、; </p><p>  printf("\t\t★ 然后進(jìn)行各個(gè)操作,最后初始化鏈表 ★\n");</p><p>  printf("\t\t☆ 請(qǐng)選擇所需功能: ☆\n");</p><p>  printf("\t\t★ 1

69、.頭插法建表 ★\n");</p><p>  printf("\t\t★ 2.尾插法建表 ★\n");</p><p>  printf("\t\t★ 3.求表的長(zhǎng)度 ★\n");</p>

70、<p>  printf("\t\t★ 4.取結(jié)點(diǎn)(遍歷) ★\n");</p><p>  printf("\t\t★ 5.插入運(yùn)算 ★\n");</p><p>  printf("\t\t★

71、 6.刪除運(yùn)算 ★\n");</p><p>  printf("\t\t★ 7.輸出帶頭結(jié)點(diǎn)的單鏈表 ★\n");</p><p>  printf("\t\t★★★ 8.鏈表的初始化 ★★★\n");</p><

72、p>  printf("\t\t★ 0.返回主菜單 ★\n");</p><p>  printf("\n\n\n");</p><p>  printf("請(qǐng)選擇(1-8):");</p><p>  scanf("%d",&

73、amp;k);</p><p>  switch (k)</p><p><b>  {</b></p><p><b>  case 1: </b></p><p>  printf("\t您的選擇是頭插法建表\n");</p><p>  printf

74、("\t輸入字符串,如: abcdef@ 以@結(jié)束后回車\n");</p><p>  a=CreateLList();</p><p>  PrintLList(a);</p><p><b>  break;</b></p><p><b>  case 2: </b><

75、;/p><p>  printf("\t你的選擇是尾插法建表\n");</p><p>  printf("\t輸入字符串,如: abcdef@ 以@結(jié)束后回車\n"); </p><p>  a=CreateLListR();</p><p>  PrintLList(a);</p><

76、;p><b>  break;</b></p><p><b>  case 3: </b></p><p>  printf("\t您選擇的是計(jì)算表的長(zhǎng)度\n");</p><p>  length=GetLListLength(a);</p><p>  printf(

77、"該表的長(zhǎng)度為:%d\n",length);</p><p><b>  break;</b></p><p><b>  case 4: </b></p><p>  printf("\t您的選擇是取結(jié)點(diǎn)\n");</p><p>  printf(&quo

78、t;請(qǐng)輸入取第幾個(gè)節(jié)點(diǎn):\n");</p><p>  scanf("%d",&node);</p><p>  p=GetLListElem(a,node);</p><p>  if(p==NULL)</p><p>  printf("表中沒有該節(jié)點(diǎn)!\n");</p>

79、;<p><b>  else</b></p><p>  printf("該節(jié)點(diǎn)的數(shù)據(jù)域?yàn)椋?c\n",p->data);</p><p><b>  break;</b></p><p><b>  case 5: </b></p><p

80、>  printf("您的選擇是插入運(yùn)算\n");</p><p>  printf("請(qǐng)輸入要插入的位置:\n");</p><p>  scanf("%d",&i);</p><p>  printf("請(qǐng)輸入插入的字符");</p><p> 

81、 getchar();</p><p>  scanf("%c",&value);</p><p>  InsertLList(a,i,value);</p><p>  PrintLList(a);</p><p><b>  break;</b></p><p>&

82、lt;b>  case 6: </b></p><p>  printf("\t您選擇的是刪除運(yùn)算\n");</p><p>  printf("請(qǐng)輸入要?jiǎng)h除的位置 \n");</p><p>  scanf("%d",&j);</p><p>  Dele

83、teLList(a,j,&q);</p><p>  PrintLList(a);</p><p><b>  break;</b></p><p><b>  case 7: </b></p><p>  printf("\t輸出鏈表為:");</p>&

84、lt;p>  PrintLList(a);</p><p><b>  break;</b></p><p><b>  case 8:</b></p><p>  printf("\t您選擇的是鏈表的初始化\n");</p><p>  InitLList(a);<

85、;/p><p>  PrintLList(a);</p><p><b>  break;</b></p><p><b>  case 0:</b></p><p>  printf("\t您的選擇是返回主菜單\n");</p><p><b> 

86、 main();</b></p><p><b>  default:</b></p><p>  printf("\t\t輸入錯(cuò)誤!請(qǐng)重新輸入!\n\t\t");</p><p><b>  }</b></p><p><b>  }</b>

87、</p><p><b>  return 0;</b></p><p><b>  }</b></p><p><b>  各個(gè)子函數(shù)源文件</b></p><p>  #include<stdio.h> </p><p>  #inclu

88、de<string.h></p><p>  #include<malloc.h></p><p>  #include<stdlib.h> </p><p>  #include"LinkedList.h"</p><p>  void InitLList(LinkedList *L)

89、// 對(duì)單鏈表進(jìn)行初始化 </p><p><b>  {</b></p><p>  L->next=NULL;// 置為空表 </p><p><b>  }</b></p><p>  int GetLListLength(LinkedList *L)// 求表的長(zhǎng)度 </p&

90、gt;<p><b>  {</b></p><p>  LinkedList *p;</p><p><b>  int j;</b></p><p>  p=L->next;</p><p><b>  j=0;</b></p><p

91、>  while(p!=NULL)</p><p><b>  {</b></p><p>  p=p->next;</p><p><b>  j++;</b></p><p><b>  }</b></p><p><b>  

92、return j;</b></p><p><b>  }</b></p><p>  LinkedList *GetLListElem(LinkedList *L, int i)//在帶頭結(jié)點(diǎn)的單鏈表L中查找第i個(gè)結(jié)點(diǎn)</p><p><b>  { </b></p><p>&l

93、t;b>  int j;</b></p><p>  LinkedList *p;</p><p><b>  p=L;</b></p><p><b>  j=0; </b></p><p>  while ((p->next!=NULL)&&(j<

94、i))</p><p><b>  { </b></p><p>  p=p->next; </p><p><b>  j++; </b></p><p><b>  }</b></p><p>  if(i == j)</p>&

95、lt;p>  return p; </p><p><b>  else </b></p><p>  return NULL; </p><p><b>  }</b></p><p>  LinkedList *LocateLListElem( LinkedList *L,DataTy

96、pe key)//在帶頭結(jié)點(diǎn)的單鏈表L中查找其</p><p><b>  { </b></p><p>  LinkedList *p;</p><p>  p=L->next; </p><p>  while (p!=NULL)</p><p><b>  {</b

97、></p><p>  if (p->data!=key)</p><p>  p=p->next; </p><p><b>  else</b></p><p><b>  break; </b></p><p><b>  }</b&g

98、t;</p><p><b>  return p;</b></p><p><b>  }</b></p><p>  int InsertLList(LinkedList *L,int i,DataType x)//在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)位置插入值為e的新結(jié)點(diǎn)s</p><p><b

99、>  {</b></p><p>  LinkedList *pre,*s;</p><p><b>  int k;</b></p><p><b>  pre=L; </b></p><p><b>  k=0; </b></p>&l

100、t;p>  while(pre!=NULL&&k<i-1) </p><p><b>  {</b></p><p>  pre=pre->next;</p><p><b>  k=k+1; </b></p><p><b>  } </b&g

101、t;</p><p><b>  if(!pre) </b></p><p><b>  { </b></p><p>  printf("插入位置不合理!");</p><p>  return ERROR;</p><p><b>  }&l

102、t;/b></p><p>  s=(LinkedList*)malloc(sizeof(LinkedList)); </p><p>  s->data=x; </p><p>  s->next=pre->next; </p><p>  pre->next=s;</p><p>

103、  return OK;</p><p><b>  }</b></p><p>  int DeleteLList(LinkedList *L,int i,DataType *e)//在帶頭結(jié)點(diǎn)的單鏈表L中刪除第i個(gè)元素,并將刪除的元素保存到變量*e中</p><p><b>  {</b></p>&l

104、t;p>  LinkedList *pre,*r;</p><p><b>  int k;</b></p><p><b>  pre=L;</b></p><p><b>  k=0;</b></p><p>  while(pre->next!=NULL &a

105、mp;& k<i-1) </p><p><b>  {</b></p><p>  pre=pre->next; </p><p><b>  k=k+1;</b></p><p><b>  } </b></p><p>  

106、if(!(pre->next)) </p><p><b>  { </b></p><p>  printf("刪除結(jié)點(diǎn)的位置i不合理!");</p><p>  return ERROR;</p><p><b>  }</b></p><p>

107、;  r=pre->next;</p><p>  pre->next=pre->next->next; </p><p>  *e = r->data;</p><p><b>  free(r); </b></p><p>  printf("成功刪除結(jié)點(diǎn)!");&l

108、t;/p><p>  return OK;</p><p><b>  }</b></p><p>  LinkedList *CreateLList()// 建立不帶頭結(jié)點(diǎn)的單鏈表(頭插法建表)</p><p><b>  {</b></p><p><b>  c

109、har ch;</b></p><p>  LinkedList *l,*s;</p><p>  l=(LinkedList *)malloc(sizeof(LinkedList));</p><p>  l->next=NULL;</p><p>  ch=getchar();</p><p>

110、  while(ch!='@') </p><p><b>  {</b></p><p>  s=(LinkedList *)malloc(sizeof(LinkedList));</p><p>  s->data=ch;</p><p>  s->next=l->next;<

111、/p><p>  l->next=s;</p><p>  ch=getchar();</p><p><b>  }</b></p><p><b>  return l;</b></p><p><b>  }</b></p><

112、;p>  LinkedList *CreateLListR()//建立帶頭結(jié)點(diǎn)的單鏈表(尾插法建表)</p><p><b>  { </b></p><p><b>  char ch;</b></p><p>  LinkedList *head,*s,*r;</p><p>  h

113、ead=(LinkedList *)malloc(sizeof(LinkedList));</p><p><b>  r=head;</b></p><p>  ch=getchar();</p><p>  while(ch!='@') </p><p><b>  { </b>

114、;</p><p>  s=(LinkedList *)malloc(sizeof(LinkedList));</p><p>  s->data=ch;</p><p>  r->next=s;</p><p><b>  r=s;</b></p><p>  ch=getchar(

115、);</p><p><b>  }</b></p><p>  r->next=NULL; </p><p>  return head;</p><p><b>  }</b></p><p>  PrintLList(LinkedList *q)//輸出帶頭結(jié)點(diǎn)

116、的單鏈表</p><p><b>  {</b></p><p>  LinkedList *p;</p><p>  p=q->next;</p><p>  printf("字符單鏈表結(jié)果是: \n(");</p><p>  while(p!=NULL)<

117、/p><p><b>  {</b></p><p>  printf("%5c,",p->data);</p><p>  p=p->next;</p><p><b>  }</b></p><p>  printf("\b)&quo

118、t;);</p><p><b>  }</b></p><p><b>  哈夫曼編碼器</b></p><p><b>  頭文件</b></p><p>  #include <stdio.h></p><p>  typedef ch

119、ar DataType;</p><p>  #define MAXNUM 50</p><p>  typedef struct// 哈夫曼樹結(jié)點(diǎn)的結(jié)構(gòu) </p><p><b>  {</b></p><p>  DataType data; // 數(shù)據(jù)用字符表示 </p><p>  i

120、nt weight; // 權(quán)值 </p><p>  int parent; // 雙親 </p><p>  int left; // 左孩子 </p><p>  int right; // 右孩子 </p><p>  }HuffNode;</p><p>  t

121、ypedef struct// 哈夫曼編碼的存儲(chǔ)結(jié)構(gòu) </p><p><b>  {</b></p><p>  DataType cd[MAXNUM];// 存放編碼位串 </p><p>  int start; // 編碼的起始位置 </p><p>  }HuffCode;</p>

122、<p><b>  菜單函數(shù)</b></p><p>  #include"Huffman.h"</p><p>  int Huffmanmenu()</p><p><b>  {</b></p><p>  int n,select,flag=0; //

123、flag為0時(shí)標(biāo)記第一次選擇功能 </p><p>  HuffNode ht[2*MAXNUM]; // 定義存放哈夫曼樹的數(shù)組 </p><p>  HuffCode hcd[MAXNUM]; // 定義存放編碼的數(shù)組 </p><p><b>  while(1)</b></p><p><b> 

124、 {</b></p><p>  printf("\t 請(qǐng)選擇您所要實(shí)現(xiàn)的功能:\n");</p><p>  printf("\t1---建立哈夫曼樹\n");</p><p>  printf("\t2---編碼\n");</p><p>  printf(&quo

125、t;\t3---譯碼\n");</p><p>  printf("\t4---退出系統(tǒng)\n");</p><p>  printf("(請(qǐng)輸入1-4數(shù)字)\n");</p><p>  scanf("%d",&select);</p><p>  if(selec

126、t!=1&&select!=4&&flag==0)</p><p>  { // 提示先建立哈夫曼樹或退出 </p><p>  printf("請(qǐng)先建立哈夫曼樹再選擇其他功能!\n");</p><p><b>  continue;</b></p&

127、gt;<p><b>  }</b></p><p><b>  flag=1;</b></p><p>  switch(select) // 選擇功能 </p><p><b>  { </b></p><p><b>  case 1:&

128、lt;/b></p><p>  n=HuffmanCreate(ht); </p><p><b>  break;</b></p><p><b>  case 2: </b></p><p>  Encoding(ht,hcd,n); </p><p><b

129、>  break;</b></p><p><b>  case 3:</b></p><p>  Decoding(ht,hcd,n); </p><p><b>  break;</b></p><p><b>  case 4: </b></p&g

130、t;<p><b>  return 1;</b></p><p><b>  }</b></p><p><b>  }</b></p><p><b>  return 0;</b></p><p><b>  } <

131、;/b></p><p><b>  各個(gè)子函數(shù)模塊</b></p><p>  #include"Huffman.h"</p><p>  int HuffmanCreate(HuffNode *ht)//建立哈夫曼樹 </p><p><b>  {</b></

132、p><p>  int i,k,n,m1,m2,p1,p2;</p><p>  printf("請(qǐng)輸入元素個(gè)數(shù):");</p><p>  scanf("%d",&n);</p><p>  for(i=1;i<=n;i++) // 輸入結(jié)點(diǎn)值和信息 </p&g

133、t;<p><b>  {</b></p><p>  getchar(); // 接收回車 </p><p>  printf("第%d個(gè)元素的=>\n\t結(jié)點(diǎn)值:",i);</p><p>  scanf("%c",&ht[i].data);

134、</p><p>  printf("\t權(quán) 重:");</p><p>  scanf("%d",&ht[i].weight);</p><p><b>  }</b></p><p>  for(i=1;i<=2*n-1;i++) // 對(duì)數(shù)組

135、初始化 </p><p>  ht[i].parent=ht[i].left=ht[i].right=0;</p><p>  for(i=n+1;i<=2*n-1;i++)</p><p>  { </p><p>  m1=m2=32767; /

136、/ 初始化,令m1、m2為整數(shù)最大值 </p><p><b>  p1=p2=1;</b></p><p>  for(k=1;k<=i-1;k++) // 從數(shù)組ht[1]到ht[i-1]中找出 </p><p>  if(ht[k].parent==0) // parent為0并且權(quán)值最小的兩個(gè)結(jié)點(diǎn) &

137、lt;/p><p>  if(ht[k].weight<m1) </p><p><b>  {</b></p><p>  m2=m1; // m1為最小權(quán)值 </p><p>  p2=p1; // p1為最小權(quán)值的位置 </p><p>

138、;  m1=ht[k].weight; // m1存放最小權(quán)值 </p><p><b>  p1=k;</b></p><p><b>  }</b></p><p>  else if(ht[k].weight<m2)</p><p><b>  {</b>&l

139、t;/p><p>  m2=ht[k].weight; // m2為次小權(quán)值 </p><p>  p2=k; // p2為次小權(quán)值的位置 </p><p><b>  }</b></p><p>  ht[p1].parent=i; // i分別賦給下標(biāo)為p1、p

140、2的數(shù)組中 </p><p>  ht[p2].parent=i;</p><p>  ht[i].weight=m1+m2; // 新結(jié)點(diǎn)的的權(quán)值為最小權(quán)值和次小權(quán)值的和 </p><p>  ht[i].left=p1; // p1為新結(jié)點(diǎn)的左孩子 </p><p>  ht[i].right

141、=p2; // p2為新結(jié)點(diǎn)的右孩子 </p><p><b>  }</b></p><p>  printf("哈夫曼樹已成功建立!\n");</p><p>  return n; </p><p><b>  }&l

142、t;/b></p><p>  void Encoding(HuffNode ht[],HuffCode hcd[],int n)// 哈夫曼編碼 </p><p><b>  { </b></p><p>  HuffCode d;</p><p>  int i,k,f,c;

143、 </p><p>  for(i=1;i<=n;i++) // 對(duì)所有結(jié)點(diǎn)循環(huán) </p><p><b>  {</b></p><p>  d.start=n+1; // 起始位置 </p><p>  c=i;

144、 // 從葉結(jié)點(diǎn)開始向上 </p><p>  f=ht[i].parent;</p><p>  while(f!=0) // 直到樹根為止 </p><p><b>  {</b></p><p>  if(ht[f].left==c)</p><p>

145、  d.cd[--d.start]='0';// 規(guī)定左樹為代碼0 </p><p><b>  else</b></p><p>  d.cd[--d.start]='1';// 規(guī)定右樹為代碼1 </p><p>  c=f; // c指孩子的位置 </p>

溫馨提示

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

最新文檔

評(píng)論

0/150

提交評(píng)論