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

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

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

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

文檔簡介

1、　　數(shù)據(jù)結(jié)構(gòu)　　課程設計報告　　專業(yè)班級： 　　姓名： 　　學號： </b&g

2、t;　　指導老師： 　　日期：2010年7月　　一、實驗內(nèi)容 　　哈夫曼編/譯碼器　　利用哈夫曼編碼進行信息通信可以

3、大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼編/譯碼系統(tǒng)。　　一個完整的系統(tǒng)應具有以下功能：　　（1）I：初始化（Initialization）。

4、從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。　　（2）E：編碼（Encoding）。利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件htmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結(jié)果存入文件CodeFile中。　　（3）D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFi

5、le中的代碼進行譯碼，結(jié)果存入文件TextFile中。　　（4）P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼寫入文件CodePrint中。　?。?）T：印哈夫曼樹（Tree Printing）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹

6、寫入文件TreePrint中。　　二、實驗目的 　　學習數(shù)據(jù)結(jié)構(gòu)與算法的最終目的是解決實際的應用問題，特別是非數(shù)值計算類型的應用問題。本課程設計要求同學獨立完成一個較為完整的應用需求分析，在完成設計和編程大型作業(yè)的過程中，深化對數(shù)據(jù)結(jié)構(gòu)與算法課程中基本概念、理論和方法的理解；訓練綜合運用所學知識處理實際問題的能力，使

7、同學的程序設計與調(diào)試水平有一個明顯的提高。　　三、實驗思想及分析　　一個完整的系統(tǒng)應具有以下功能：　　I：初始化(Initialization)。從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立赫夫曼樹，并將它存于文件hfmTree中。<p&

8、gt;　　對赫夫曼樹初始化。　　根據(jù)書本算法6.12，對樹進行從葉子到根的逆向求每個字符的赫夫曼編碼。　　更新赫夫曼樹，并存到hfmTree.txt中。　　算法6.12流程圖如下：　　N</

9、p>　　Y　　圖1 算法6.12流程圖　　E：編碼(Encoding)。利用已建好的哈夫曼樹，對文件ToBeTran中的正文進行編碼，然后將結(jié)果存入文件CodeFile中。　　將終端輸入須要編碼的語句逐字在已建好的赫夫曼樹中查找。

10、;　　當在樹中找到相匹配字符時，將該字符對應的赫夫曼編碼用strcat()　　統(tǒng)一存到code[]數(shù)組。　?、圩詈髮ode[]數(shù)組中的編碼在終端輸出并存儲到CodeFile.txt中。　　D：譯碼(Decoding)。利用已建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼，結(jié)果存入文件

11、Textfile中。　　從CodeFile.txt中獲取須要譯碼的編碼組。　　將編碼逐一讀入，并在赫夫曼中根據(jù)左‘0’右‘1’去查找字符。　　將譯好的語句在終端輸出，并存至Textfile.txt中。　　P：打印表(TreePrint)。將已建立好的赫夫曼樹的存儲情況在終

12、端以表格的形式羅列出來，使樹的調(diào)用看起來更直觀。　　T：打印圖(TreePrint)。將已建好的赫夫曼樹以直觀的圖形在終端輸出。　　根據(jù)樹的先序遍歷算法，依次訪問各個結(jié)點。　　根據(jù)P打印出來的表，分析其所在的層次。　　根據(jù)層次的大小，在終端輸出相應長度的長條，來完成凹入表

13、的輸出。　　四、程序代碼：　　#include<stdio.h> 　　#include<stdlib.h>　　#include<string.h>　　typ

14、edef struct　　{ 　　char elem;　　int weight; 　　int parent,lchild,rchild; 　　}HTNode,*HuffmanTree;

15、 //動態(tài)分配數(shù)組存儲赫夫曼樹　　typedef char **HuffmanCode; //動態(tài)分配數(shù)組存儲赫夫曼樹編碼表　　void Initialization();　　void Encoding();

16、;　　void Decoding();　　void HuffmanCoding(int); 　　void Select(int,int *,int *); 　　void PrintHufmFigue();　　void putout(int,int);

17、　　void Turn(int,void(* Visit)(int,int));　　void TreePrint();　　//-------------------全局函數(shù)----------------------- 　　int ipt=1,n,q,p=0,code_n

18、um=0,TempLen=0,diamonds,lay;　　int w1=100000,w2=100000,w3=100000;　　HuffmanCode HC=NULL; 　　HuffmanTree HT;　　int main()

19、;　　{　　char key;　　system("color FC");　　printf(" ╔━━━━━━━━━━━━━━━━━━━━━╗\n");<p

20、>　　printf(" ┃ 赫夫曼編/譯碼器 ┃\n");　　printf(" ┃ ┃\n");　　printf(" ┃

21、 08信息 <2> 趙思宇 ┃\n");　　printf(" ╚━━━━━━━━━━━━━━━━━━━━━╝\n");　　do{　　printf("\n\n\n"

22、);　　printf(" ╔━━━━━━━━━━━━━━━━━━━━━╗\n");　　printf(" ┃ 操作菜單 ┃\n");　　printf(" ┃

23、 ┃\n");　　printf(" ┃ I:初始化 (Initialization ) ┃\n");　　printf(" ┃ E:編碼 (Encodi

24、ng ) ┃\n");　　printf(" ┃ D:譯碼 (Decoding ) ┃\n");　　printf(" ┃ P:打印表 (PrintHufmFigue ) ┃\n"

25、;);　　printf(" ┃ T:打印圖 (TreePrint ) ┃\n");　　printf(" ┃ Q:退出 (Initialization ) ┃\n");<p&

26、gt;　　printf(" ┃ ┃\n");　　printf(" ╚━━━━━━━━━━━━━━━━━━━━━╝\n");　　printf("\n\n");<

27、;p>　　printf("Please Enter a key of the operation:");　　scanf("%c",&key);　　getchar();　　switch(key)　　{&

28、lt;/b>　　case 'i':　　case 'I':　　Initialization();　　break;</

29、p>　　case 'e':　　case 'E':　　Encoding();　　break;<

30、b>　　case 'd':　　case 'D':　　Decoding();　　break;　　case 'p&#

31、39;:　　case 'P':　　PrintHufmFigue();　　break;　　case 't':

32、　　case 'T':　　TreePrint();　　}　　}while(key!='q'&&key!='Q');

33、;　　return 1;　　}　　/* 函數(shù)功能：建立赫夫曼樹并對其進行初始化。　　函數(shù)參數(shù)：FILE *FhfmTreeP，將赫夫曼樹的相關(guān)信息保存于此hfmTree.TXT中。<p&

34、gt;　　函數(shù)實現(xiàn)：實現(xiàn)了字符集和頻度的實際統(tǒng)計，并可將信息保存到hfmTree.TXT中。　　函數(shù)返回值：無　　*/　　void Initialization()　　{<

35、/b>　　int i,m;　　char style[]={' ','\0'};　　printf("Please input the number of Node:" );

36、scanf("%d",&n); 　　getchar();　　m=2*n-1; 　　HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0號單元未用　　fo

37、r(i=1;i<=n;i++)　　{ 　　printf("Input characters and weight(just like a 30Enter):"); 　　scanf("%c%d",&HT[i].elem,&a

38、mp;HT[i].weight);　　getchar();　　HT[i].parent=HT[i].lchild=HT[i].rchild=0;　　} 　　HuffmanCoding(n);

39、　FILE* FhfmTreeP=NULL;　　if(NULL==(FhfmTreeP=fopen("E:\\hfmTree.txt","w")))　　printf("Open hfmTree.txt failed!\n");　　els

40、e　　{　　for(i=1;i<=n;i++) 　　{ 　　fprintf(FhfmTreeP,"%c",HT[i].elem);

41、　　fputs(HC[i],FhfmTreeP); 　　fputs(style,FhfmTreeP); 　　}　　}　　fclose(FhfmTreeP);

42、;　　printf("Every charactor has been coded and puted into E:\\hfmTree.txt!\n");　　return;　　}　　//---

43、-------------P147 算法6.12-------------------　　void HuffmanCoding(int n)　　{ 　　int i,m,s1,s2,start,c,f; //weight

44、存放n個字符的權(quán)值（均　　char *cd; //>0），構(gòu)造赫夫曼樹HT，并求出　　m=2*n-1; //n個字符的赫夫曼編碼HC。　　for(i=n+1

45、;i<=m;++i)　　{ 　　HT[i].elem='0'; 　　HT[i].weight=HT[i].parent=HT[i].lchild=HT[i].rchild=0; 　　}</

46、b>　　for(i=n+1;i<=m;++i)　　{ //建赫夫曼樹　　Select(i-1,&s1,&s2); /*在HT[1...i-1]選擇parent為0　　HT[s1].pare

47、nt=i;HT[s2].parent=i; 且weight最小的兩個結(jié)點，其.　　HT[i].lchild=s1;HT[i].rchild=s2; 序號分別為s1,s2*/　　HT[i].weight=HT[s1].weight+HT[s2].weight; <

48、;p>　　} 　　//-----------------從葉子到根逆向求每個字符的赫夫曼編碼--------------------------　　HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); //分配n個字符編碼的頭指針向量&

49、lt;p>　　cd=(char *)malloc(n*sizeof(char)); //分配求編碼的工作空間　　cd[n-1]='\0'; //編碼結(jié)束符　　for(i=1;i<=n;++i)　　{ //逐個字符求赫夫曼編碼<

50、/p>　　start=n-1; 　　for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) //從葉子到根逆向求編碼　　{ 　　if(HT[f].lchild==c) cd[--start]=

51、9;0'; 　　else cd[--start]='1'; 　　} 　　HC[i]=(char *)malloc((n-start)*sizeof(char)); //為第i個字符編碼分配空間

52、strcpy(HC[i],&cd[start]);//從cd復制編碼（串）到HC　　}　　free(cd);//釋放工作空間　　return;　　}//H

53、uffanCoding　　/*函數(shù)功能：選出當前字符集中，兩個最小值s1,s2.　　函數(shù)參數(shù)：*s1,*s2,用于存儲選出的兩個最小值。　　函數(shù)返回值：無　　*/<p

54、>　　void Select(int n,int *s1,int *s2) 　　{ 　　int i; 　　(*s1)=(*s2)=0; 　　for(i=1;i<=n;i++)</

55、p>　　{ 　　if(HT[i].weight<HT[(*s2)].weight&&HT[i].parent==0&&(*s2)!=0)　　{ 　　if(HT[i].wei

56、ght<HT[(*s1)].weight)　　{ 　　(*s2)=(*s1); 　　(*s1)=i; 　　}

57、;　　else (*s2)=i; 　　} 　　if(((*s1)==0||(*s2)==0)&&HT[i].parent==0)　　{ 　　if((*s1)==0) (*s1)=i

58、; 　　else if((*s2)==0)　　{ 　　if(HT[i].weight<HT[(*s1)].weight)　　{ 　　(*s2)=(*

59、s1); 　　(*s1)=i; 　　} 　　else (*s2)=i; 　　} 　　} </

60、b>　　} 　　if((*s1)>(*s2))　　{ 　　i=(*s1); 　　(*s1)=(*s2);

61、 　　(*s2)=i; 　　} 　　return; 　　}　　/*函數(shù)功能：將

62、終端輸入的字符串編譯成用0/1表示的編碼，并將相應信息存入TXT文檔。　　函數(shù)參數(shù)：temp[1000],用于臨時存儲終端輸入的字符串。　　Code[1000],用于存儲0/1編碼。　　ToBeTran.txt,用于存儲終端輸入的字符串。　　CodeFile.txt，用于

63、存儲編譯后的0/1編碼。　　函數(shù)返回值：無　　*/　　void Encoding()　　{　　int i,j,all

64、;　　char temp[1000],code[10000];　　printf("Please put in the sentence you want to Encoding:");　　//scanf("%s",temp);　　g

65、etchar();　　gets(temp);　　code[0]='\0';　　FILE* FToBeTranP=NULL;　　if(NULL==(FToBeTranP=fopen("E:\\ToBeTran.txt","w&q

66、uot;)))　　printf("Open ToBeTran.txt failed!\n");　　else　　fputs(temp,FToBeTranP);　　fclose(FToBeTranP);</p&g

67、t;　　TempLen=strlen(temp);　　for(i=0;i<TempLen;i++)　　{　　all=0;　　for(j=1;j<=n;j++)&l

68、t;/p>　　{　　if(temp[i]==HT[j].elem)　　{　　strcat(code,HC[j]);　　all=1;

69、　　}　　}　　if(all=0)　　printf("Some charactor in the sentence are not matching

70、!!!");　　}　　code_num=strlen(code);　　printf("Codes of the sentence are:\n%s\n",code);　　FILE* FCodeFileP=

71、NULL;　　if(NULL==(FCodeFileP=fopen("E:\\CodeFile.txt","w")))　　printf("Open CodeFile.txt failed!\n");　　else<

72、;/p>　　fputs(code,FCodeFileP);　　fclose(FCodeFileP);　　printf("And have put into E:\\CodeFile.txt!\n");　　return;</

73、p>　　} 　　//--------------------------Decoding----------------------------　　void Decoding()　　{&

74、lt;p>　　int m,i,p=0;　　char q,*Decode,*Sentence;　　FILE* FDecodeP=NULL;　　if(NULL==(FDecodeP=fopen("E:\\CodeFile.txt","r")))&l

75、t;p>　　printf("Open E:\\CodeFile.txt failed!\n");　　else　　{　　FILE *TxtFile=NULL;　　if(NU

76、LL==(TxtFile=fopen("E:\\TxtFile.txt","w")))　　printf("Open E:\\TxtFile.txt failed!\n");　　else　　{<

77、/b>　　Sentence=(char*)malloc(TempLen*sizeof(char));　　Decode=(char*)malloc(code_num*sizeof(char));　　fgets(Decode,code_num+1,FDecodeP);&

78、lt;b>　　m=2*n-1;　　for(i=0;Decode[i-1]!='\0';i++) 　　{ 　　q=Decode[i]; 　　if(HT[m].lchild==0) </p&

79、gt;　　{ 　　Sentence[p]=HT[m].elem; 　　p++; 　　m=2*n-1; 　　i--;

80、　　} 　　else if(q=='0') m=HT[m].lchild; 　　else if(q=='1') m=HT[m].rchild; 　　} </b

81、>　　Sentence[p]='\0';　　fputs(Sentence,TxtFile);　　printf("Codes have been Encoded and get a sentence:\n%s\n",Sentence);<p&g

82、t;　　printf("And have been put into TxtFile.txt!\n");　　}　　}　　}　　/* 函數(shù)功

83、能：輸出赫夫曼樹中各結(jié)點的數(shù)據(jù)存儲情況。　　函數(shù)參數(shù)：無。　　函數(shù)返回值：無。　　*/　　void PrintHufmFigue()&

84、lt;p>　　{　　int i,m;　　char end[]={'\\','\0'};　　printf("╔━━━┳━━━┳━━━┳━━━┳━━━┳━━┳━━━━━━━╗");&l

85、t;/p>　　printf("┃Number┃Element┃Weight┃Parents┃Lchild┃Rchild┃HuffmanCode ┃");　　printf("┣━━━╋━━━╋━━━╋━━━╋━━━╋━━╋━━━━━━━┫");　　for(i=1;i<=n;i++)&

86、lt;/p>　　{　　printf("┃%6d┃%8c┃%6d┃%8d┃%8d┃%8d┃%20s┃",i,HT[i].elem,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild,HC[i]);　　printf(&qu

87、ot;┣━━━━╋━━━╋━━━╋━━━━╋━━━━╋━━━╋━━━━┫");　　}　　m=2*n-1;　　for(i=n+1;i<=m-1;i++)　　{<

88、;/b>　　printf("┃%6d┃%8c┃%6d┃%8d┃%8d┃%8d┃%20s┃",i,HT[i].elem,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild,end);　　printf("┣━━━╋━━━━╋━━━╋━━━━╋━━━━╋━━━━╋━━━━┫

89、");　　}　　printf("┃%6d┃%8c┃%6d┃%8d┃%8d┃%8d┃%20s┃",m,HT[m].elem,HT[m].weight,HT[m].parent,HT[m].lchild,HT[m].rchild,end);　　pri

90、ntf("╚━━━┻━━━━┻━━━┻━━━━┻━━━━┻━━━┻━━━━╝");　　return;　　}　　/*函數(shù)功能：將赫夫曼樹以凹入表的形式在終端輸出。

91、;　　函數(shù)參數(shù)：無。　　函數(shù)返回值：無。　　*/　　void TreePrint()　　{

92、int MaxCode,MaxI=1,Floor,numb,i;　　numb=2*n-1;　　MaxCode=strlen(HC[1]);　　for(i=1;i<=n;i++)　　{

93、if(strlen(HC[i])>MaxCode)　　{　　MaxCode=strlen(HC[i]);　　MaxI=i;　　}

94、　　}　　Floor=MaxCode+1;　　diamonds=Floor+10;　　lay=diamonds;　　Turn(numb,putout);

95、return;　　}　　void Turn(int w,void(* Visit)(int,int))　　{　　p++;

96、;　　w3=w2;　　w2=w1;　　w1=w;　　if(w3<w2&&w2<w1)　　l

97、ay++;　　if(HT[w].weight!=0)　　Visit(w,lay);　　if(HT[w].lchild!=0)　　{　　lay=diamonds-p;<

98、/p>　　Turn(HT[w].lchild,Visit);　　}　　if(HT[w].rchild!=0)　　{　　q=--p;

99、　　lay=diamonds-q;　　Turn(HT[w].rchild,Visit);　　}　　return;　　}

100、;　　//-----------------打印柱體-------------　　void putout(int lr,int count)　　{　　for(;count>=1;count--)<p

101、>　　{　　printf("█");　　}　　if(HT[lr].lchild!=0)　　printf("%d\n",HT[lr].weight);&

102、lt;/p>　　else　　printf("%c\n",HT[lr].elem);　　printf("\n");　　return;

103、;　　}　　五、程序運行情況：　　I：初始化（Initialization）：　　圖2. 輸入I運行結(jié)果　　E：編碼（Encoding）　　圖3. 輸入E

104、運行結(jié)果　　D：譯碼（Decoding）　　圖4. 輸入D運行結(jié)果　　P：打印表（TreePrint）　　圖5. 輸入P運行結(jié)果　　圖6. 輸入P運行結(jié)果2　　圖7. 輸入P運行結(jié)果3&l

105、t;/p>　　T：打印圖（Initialization）　　圖8. 輸入T運行結(jié)果1　　圖9. 輸入T運行結(jié)果2　　圖10. 輸入T運行結(jié)果3　　分別打開htmTree.txt, CodeFile.txt，TxtFile.txt， ToBeTr

106、an.txt文件（如下圖從上到下的順序）查看內(nèi)部存儲信息均符合預期結(jié)果。　　圖11. 各文件的存儲情況　　六、實驗心得：　　經(jīng)過此次課程設計，取獲不少：　　已基本形成了良好的編程思想。　　基本

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

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
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ù)據(jù)結(jié)構(gòu)課程設計報告

文檔簡介

溫馨提示

最新文檔

評論

免費下載