數(shù)據(jù)結(jié)構(gòu)課程設(shè)計實習(xí)報告

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：33 大?。?63.50KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩32頁未讀，繼續(xù)免費閱讀

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

文檔簡介

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

2、lt;/p>　　四、程序編碼9　　五、程序調(diào)試與測試35　　六、結(jié)果分析39　　需求分析：　　1、程序一：單鏈表的應(yīng)用<

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

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

5、器（未嚴格依照要求）　　從鍵盤接受一串電文字符，輸出對應(yīng)的Huffman編碼。同時，能翻譯由Huffman編碼生成的代碼串，輸出對應(yīng)的電文字符串。　　程序四：停車場管理　　設(shè)停車場是一個可以停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場內(nèi)按車輛到達時間的先后

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

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

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

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

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

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

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

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

14、為右子樹，直到葉子節(jié)點結(jié)束，此時輸出葉子結(jié)點的數(shù)據(jù)域，即所對應(yīng)的字符。繼續(xù)譯碼，直到代碼結(jié)束。　　停車場管理系統(tǒng)的詳細設(shè)計　　、模擬停車場車輛進出時需要輸入車輛的信息，包括車牌號碼以及進入和離開的時刻，因此可以定義一個時間節(jié)點類型和一個車輛信息結(jié)點類型，在順序棧及鏈式隊列中定義結(jié)點類型為車輛信息結(jié)點類型。　　、當

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

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

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

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

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

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

21、\n");　　printf("\t\t 請及時聯(lián)系我 \n \n");　　printf("\t\t☆ 請選擇以下題目展示: ☆\n");　　printf("\t\t★

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

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

24、p>　　printf("請選擇(0-4)：");　　scanf("%d",&k);　　switch (k)　　{　　case 1:printf("

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

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

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

28、/p>　　default:　　printf("您的輸入有誤，請重新輸入！");　　}　　}

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

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

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

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

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

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

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

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

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

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

39、>　　printf("\t請按完全二叉樹的編號順序依次輸入結(jié)點序列\(zhòng)n");　　printf("\t注：空結(jié)點用'@'表示，輸入序列以'#'結(jié)束\n\n");　　printf("\t輸入的順序為：");　　ch=ge

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

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

42、;/b>　　rear++;　　Q[rear]=s; //空結(jié)點和新結(jié)點都入隊　　if(rear==1) 　　root=s; //rear是1，是根結(jié)點，用root指向它

43、　　else　　{　　if(s&&Q[front]) // 當前結(jié)點和雙親結(jié)點都非空 　　if(rear%2==0)// rear是偶數(shù)，新結(jié)點為雙親的左孩子

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

45、指向下一個雙親　　}　　ch=getchar(); 　　} 　　return root; 　　}

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

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

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

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

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

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

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

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

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

55、;　　return 0; // 如果是空樹，則返回0 　　} 　　int LeafCount(BiTree *t) //遍歷求葉子結(jié)點的個數(shù)　　{<

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

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

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

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

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

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

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

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

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

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

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

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

68、; 　　printf("\t\t★ 然后進行各個操作，最后初始化鏈表 ★\n");　　printf("\t\t☆ 請選擇所需功能: ☆\n");　　printf("\t\t★ 1

69、.頭插法建表 ★\n");　　printf("\t\t★ 2.尾插法建表 ★\n");　　printf("\t\t★ 3.求表的長度 ★\n");

70、　　printf("\t\t★ 4.取結(jié)點(遍歷) ★\n");　　printf("\t\t★ 5.插入運算 ★\n");　　printf("\t\t★

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

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

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

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

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

76、;p>　　break;　　case 3: 　　printf("\t您選擇的是計算表的長度\n");　　length=GetLListLength(a);　　printf(

77、"該表的長度為：%d\n",length);　　break;　　case 4: 　　printf("\t您的選擇是取結(jié)點\n");　　printf(&quo

78、t;請輸入取第幾個節(jié)點：\n");　　scanf("%d",&node);　　p=GetLListElem(a,node);　　if(p==NULL)　　printf("表中沒有該節(jié)點!\n");

79、;　　else　　printf("該節(jié)點的數(shù)據(jù)域為：%c\n",p->data);　　break;　　case 5: <p

80、>　　printf("您的選擇是插入運算\n");　　printf("請輸入要插入的位置：\n");　　scanf("%d",&i);　　printf("請輸入插入的字符");

81、　getchar();　　scanf("%c",&value);　　InsertLList(a,i,value);　　PrintLList(a);　　break;&

82、lt;b>　　case 6: 　　printf("\t您選擇的是刪除運算\n");　　printf("請輸入要刪除的位置 \n");　　scanf("%d",&j);　　Dele

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

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

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

86、　main();　　default:　　printf("\t\t輸入錯誤！請重新輸入！\n\t\t");　　}　　}

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

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

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

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

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

92、return j;　　}　　LinkedList *GetLListElem(LinkedList *L, int i)//在帶頭結(jié)點的單鏈表L中查找第i個結(jié)點　　{ &l

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

124、　{　　printf("\t 請選擇您所要實現(xiàn)的功能：\n");　　printf("\t1---建立哈夫曼樹\n");　　printf("\t2---編碼\n");　　printf(&quo

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

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

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

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

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

130、t;　　return 1;　　}　　}　　return 0;　　} <

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

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)容負責。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計實習(xí)報告

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計實習(xí)報告

文檔簡介

溫馨提示

最新文檔

評論

免費下載