數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告----哈夫曼

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

2023年全國(guó)碩士研究生考試考研英語(yǔ)一試題真題（含答案詳解+作文范文）_第1頁(yè)

已閱讀1頁(yè)，還剩14頁(yè)未讀，繼續(xù)免費(fèi)閱讀

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

文檔簡(jiǎn)介

1、　　《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告　　題目: 趣味游戲之n皇后問(wèn)題 　　赫夫曼編碼/譯碼器課程設(shè)計(jì) 　　院系：計(jì)算機(jī)工程學(xué)院 　　專(zhuān)業(yè)班級(jí)： 10軟件2ZW 　　學(xué) 號(hào)

2、： 　　學(xué)生姓名： 　　指導(dǎo)教師： 　　2012年 02月 22日 　　《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)任務(wù)書(shū)　　學(xué)院計(jì)算機(jī)工程學(xué)院

3、系信息與軟件工程系 　　2012年 02月 22日　　求解N皇后問(wèn)題　　問(wèn)題描述：　　編寫(xiě)一個(gè)程序，求解皇后問(wèn)題，在N*N的方格棋盤(pán)上，放置N個(gè)皇后，要求每個(gè)皇后不同行、不同列、不同

4、對(duì)角線。　　求出8個(gè)皇后的程序截圖　　源代碼：　　# include<stdio.h>　　# include<stdlib.h>　　const int N=20;

5、 //最多皇后個(gè)數(shù)　　int q[N]; //存放各皇后所在的行號(hào)　　int cont = 0; //存在解個(gè)數(shù)　　void print(int n) //輸出一個(gè)解<b&

6、gt;　　{　　cont++;　　int i;　　printf("第%d個(gè)解:",cont);　　for (i=1;i<=n;i++)</p&g

7、t;　　printf("%d",q[i]);　　printf("\n");　　}　　int find(int i,int k) //測(cè)試第K列的i行上能否擺放皇后<

8、p>　　{　　int j;　　j=1;　　while(j<k) //j=1~k-1是已放置了皇后的列　　{ if

9、 ((q[j]==i)||(abs(q[j]-i)==abs(j-k)))　　//第j列皇后是否在i行或(q[i],j)與(i,k)是否同對(duì)角線　　return 0;　　j++;

10、　　}　　return 1;　　}　　void place(int k,int n) //第k個(gè)皇后放到第k列上　　{&l

11、t;/p>　　if (k>n)　　print(n); //所有皇后放置結(jié)束　　else 　　for (int i=1;i<=n;i++) //在第k列上窮舉每一個(gè)

12、位置　　if (find(i,k))　　{ q[k]=i;　　place(k+1,n);　　}　　}　　voi

13、d main()　　{　　int n; //n存在實(shí)際皇后個(gè)數(shù)　　printf("皇后問(wèn)題(n<20) n=");　　scanf("%d",&

14、amp;n);　　if (n>20)　　printf("n值太大，不能求解\n");　　else　　{ printf("%d皇后問(wèn)題求解如下：\n"

15、,n);　　place(1,n);　　printf("\n");　　}　　}　　參考文獻(xiàn)：<

16、;/p>　　《數(shù)據(jù)結(jié)構(gòu)教程》上機(jī)實(shí)驗(yàn)指導(dǎo)（第三版）　　一、【問(wèn)題描述】　　設(shè)計(jì)一個(gè)哈夫曼編碼/譯碼系統(tǒng)，對(duì)一個(gè)文本文件中的字符進(jìn)行哈夫曼編碼，生成編碼文件（壓縮文件，后綴名.cod）；反過(guò)來(lái)，可將一個(gè)壓縮文件譯碼還原為一個(gè)文本文件(.txt)。&l

17、t;b>　　二、【基本要求】　　1．輸入一個(gè)待壓縮的文本文件名，統(tǒng)計(jì)文本文件中各字符的個(gè)數(shù)作為權(quán)值，生成哈夫曼樹(shù)；　　2．將文本文件利用哈夫曼樹(shù)進(jìn)行編碼，生成壓縮文件（后綴名cod），　　3．輸入一個(gè)待解壓的壓縮文件名稱(chēng),并利用相應(yīng)的哈夫曼樹(shù)將編碼序列譯碼；

18、　　4．顯示指定的壓縮文件和文本文件；　　5．界面友好，易與操作。采用菜單方式進(jìn)行選擇。　　三. 問(wèn)題分析哈夫曼樹(shù)的定義　　1.哈夫曼樹(shù)節(jié)點(diǎn)的數(shù)據(jù)類(lèi)型定義為：　　typedef struct{ //赫夫曼樹(shù)的結(jié)構(gòu)體</p&

19、gt;　　char ch;　　int weight; //權(quán)值　　int parent,lchild,rchild;　　}htnode,*hfmtree;　　2）所實(shí)現(xiàn)的功能函數(shù)如下&l

20、t;/p>　　1、void hfmcoding(hfmtree &HT,hfmcode &HC,int n)初始化哈夫曼樹(shù)，處理InputHuffman(Huffman Hfm)函數(shù)得到的數(shù)據(jù)，按照哈夫曼規(guī)則建立2叉樹(shù)。此函數(shù)塊調(diào)用了Select（）函數(shù)。　　2、void Select(hfmtree &HT,int a,int *p1,int

21、 *p2) //Select函數(shù)，選出HT樹(shù)到a為止，權(quán)值最小且parent為0的2個(gè)節(jié)點(diǎn)　　2、 int main()　　主函數(shù)：利用已建好的哈夫曼樹(shù)（如不在內(nèi)存，則從文件hfmtree.txt中讀入）　　對(duì)文件中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile.cod中。如果正文中沒(méi)有要

22、編碼的字符，則鍵盤(pán)讀入并存儲(chǔ)到ToBeTran文件中。讀入ToBeTran中將要編碼的內(nèi)容，將編碼好的哈夫曼編碼存儲(chǔ)到CodeFile中。　　3、Encoding 　　編碼功能：對(duì)輸入字符進(jìn)行編碼　　4、Decoding　　譯碼功能：利用已建好的哈夫曼樹(shù)將文件codef

23、ile.cod中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile.dat 中。　　Print() 打印功能函數(shù)：輸出哈夫曼樹(shù)，字符，權(quán)值，以及它對(duì)應(yīng)的編碼。　　5.主函數(shù)的簡(jiǎn)要說(shuō)明，主函數(shù)主要設(shè)計(jì)的是一個(gè)分支語(yǔ)句，讓用戶(hù)挑選所實(shí)現(xiàn)的功能。　　使用鏈樹(shù)存儲(chǔ)，然后分別調(diào)用統(tǒng)計(jì)頻數(shù)函數(shù)，排序函數(shù)，建立哈夫曼函數(shù)，編碼函數(shù)，

24、譯碼函數(shù)來(lái)實(shí)現(xiàn)功能。　　四、系統(tǒng)結(jié)構(gòu)功能圖　　五、程序說(shuō)明　　1. 赫夫曼編碼/譯碼器代碼　　#include<iostream.h>　　#i

25、nclude<stdio.h>　　#include<stdlib.h>　　#include<string.h>　　#include<fstream.h>　　typedef struct{ //赫夫曼樹(shù)的結(jié)構(gòu)體

26、　　char ch;　　int weight; //權(quán)值　　int parent,lchild,rchild;　　}htnode,*hfmtree;　　typedef

27、 char **hfmcode;　　void Select(hfmtree &HT,int a,int *p1,int *p2) //Select函數(shù)，選出HT樹(shù)到a為止，權(quán)值最小且parent為0的2個(gè)節(jié)點(diǎn)　　{　　int i,j,x,y;&

28、lt;p>　　for(j=1;j<=a;++j){　　if(HT[j].parent==0){　　x=j;　　break;　　}

29、;　　}　　for(i=j+1;i<=a;++i){　　if(HT[i].weight<HT[x].weight&&HT[i].parent==0){　　x=i; //選出最小的節(jié)點(diǎn)</

30、p>　　}　　}　　for(j=1;j<=a;++j){　　if(HT[j].parent==0&&x!=j)　　{</

31、b>　　y=j;　　break;　　}　　}　　for(i=j+1;i&

32、lt;=a;++i)　　{　　if(HT[i].weight<HT[y].weight&&HT[i].parent==0&&x!=i)　　{　　y=i;

33、 //選出次小的節(jié)點(diǎn)　　}　　}　　if(x>y){　　*p1=y;

34、;　　*p2=x;　　}　　else　　{　　*p1=x;&

35、lt;/p>　　*p2=y;　　}　　}　　void hfmcoding(hfmtree &HT,hfmcode &HC,int n) //構(gòu)建赫夫曼樹(shù)HT

36、，并求出n個(gè)字符的赫夫曼編碼HC　　{　　int i,start,c,f,m,w;　　int p1,p2;　　char *cd,z;　　if(n<=1){</b&

37、gt;　　return;　　}　　m=2*n-1;　　HT=(hfmtree)malloc((m+1)*sizeof(htnode));

38、　　for(i=1;i<=n;++i) //初始化n個(gè)葉子結(jié)點(diǎn)　　{　　printf("請(qǐng)輸入第%d字符信息和權(quán)值：",i);　　scanf("%c%d",&z,&w);&

39、lt;/p>　　while(getchar()!='\n')　　{　　continue;　　}　　HT[i].ch

40、=z;　　HT[i].weight=w;　　HT[i].parent=0;　　HT[i].lchild=0;　　HT[i].rchild=0;　　}

41、　for(;i<=m;++i) //初始化其余的結(jié)點(diǎn)　　{　　HT[i].ch='0';　　HT[i].weight=0;　　HT[i].parent=0;

42、　　HT[i].lchild=0;　　HT[i].rchild=0;　　}　　for(i=n+1;i<=m;++i) //建立赫夫曼樹(shù)　　{<p&

43、gt;　　Select(HT,i-1,&p1,&p2);　　HT[p1].parent=i;HT[p2].parent=i;　　HT[i].lchild=p1;HT[i].rchild=p2;　　HT[i].weight=HT[p1].weight+HT[p2].weight;

44、　　}　　HC=(hfmcode)malloc((n+1)*sizeof(char *));　　cd=(char *)malloc(n*sizeof(char));　　cd[n-1]='\0';

45、　for(i=1;i<=n;++i) //給n個(gè)字符編碼　　{　　start=n-1;　　for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)

46、　　{　　if(HT[f].lchild==c)　　{　　cd[--start]='0';　　}

47、else　　{　　cd[--start]='1';　　}　　}　　HC[i]=(

48、char*)malloc((n-start)*sizeof(char));　　strcpy(HC[i],&cd[start]);　　}　　free(cd);　　}<

49、/b>　　int main(){　　char code[100],h[100],hl[100];　　int n,i,j,k,l;　　ifstream input_file; //文件輸入輸出流　　ofstream ou

50、tput_file;　　char choice,str[100];　　hfmtree HT;　　hfmcode HC;　　cout<<"\n";　　cout<<"

51、 "<<"軟件（2）班"<<" "<<"10144214"<<" "<<"劉紅亮\n";　　while(choice!='Q'&&choice!='q')

52、 //當(dāng)choice的值不為q且不為Q時(shí)循環(huán)　　{　　cout<<" "<<"*************************赫夫曼編碼/譯碼器*************************\n";

53、;　　cout<<" "<<"I.Init"<<" "<<"E.Encoding"<<" "<<"D.Decoding"<<" "

54、<<"Q.Exit\n";　　cout<<"請(qǐng)輸入您要操作的步驟：";　　cin>>choice;　　if(choice=='I'||choice=='i') //初始化赫夫曼樹(shù)&

55、lt;/p>　　{　　cout<<"請(qǐng)輸入字符個(gè)數(shù)：";　　cin>>n;　　hfmcoding(HT,HC,n);　　fo

56、r(i=1;i<=n;++i)　　{　　cout<<HT[i].ch<<":"<<HC[i]<<endl;　　}　　out

57、put_file.open("hfmTree.txt");　　if(!output_file){　　cout<<"can't oen file!"<<endl;　　return 1;

58、　　}　　for(i=1;i<=n;i++)　　{　　output_file<<"("<<HT[i].ch<<HC[i]<<")&qu

59、ot;;　　}　　output_file.close();　　cout<<"赫夫曼樹(shù)已經(jīng)創(chuàng)建完畢，并且已經(jīng)放入hfmTree.txt文件中!"<<endl;　　}</

60、b>　　else if(choice=='E'||choice=='e') //進(jìn)行編碼，并將字符放入ToBeTran.txt，碼值放入CodeFile.txt中　　{　　printf("請(qǐng)輸入字符：&quo

61、t;);　　gets(str);　　output_file.open("ToBeTran.txt");　　if(!output_file)　　{　　cout<<

62、"can't oen file!"<<endl;　　return 1;　　}　　output_file<<str<<endl;　　o

63、utput_file.close();　　output_file.open("CodeFile.cod");　　if(!output_file){　　cout<<"can't oen file!"<<endl;<

64、p>　　return 1;　　}　　for(i=0;i<strlen(str);i++){　　for(j=0;j<=n;++j)　　{<

65、;/p>　　if(HT[j].ch==str[i])　　{　　output_file<<HC[j];　　break;　　}</b&g

66、t;　　}　　}　　output_file.close();　　cout<<"\n";　　cout<<&quo

67、t;編碼完畢，并且已經(jīng)存入CodeFile.cod文件！\n";　　input_file.open("CodeFile.cod"); //從CodeFile.cod中讀入編碼，輸出在終端　　if(!input_file)　　{&l

68、t;/p>　　cout<<"can't oen file!"<<endl;　　return 1;　　}　　input_file>>code;<

69、;/p>　　cout<<"編碼碼值為："<<code<<endl;　　input_file.close();　　}　　else if(choice=='D'||choice==

70、'd') //讀入CodeFile.cod中的編碼進(jìn)行譯碼，將譯出來(lái)的字符放入Textfile.txt中　　{　　input_file.open("CodeFile.cod");　　if(!input_file){

71、;　　cout<<"can't oen file!"<<endl;　　return 1;　　}　　input_file>>h;&

72、lt;p>　　input_file.close();　　output_file.open("Textfile.txt");　　if(!output_file)　　{　　cout<<"ca

73、n't oen file!"<<endl;　　return 1;　　}　　k=0;　　while(h[k]!='\0&#

74、39;) //先用編碼中的前幾個(gè)和字符的編碼相比較，然后往后移　　{　　for(i=1;i<=n;i++){　　l=k;　　for(j=0;j<strlen(HC[

75、i]);j++,l++){　　hl[j]=h[l];　　}　　hl[j]='\0';　　if(strcmp(HC[i],hl)==0)　　{

76、;　　output_file<<HT[i].ch;　　k=k+strlen(HC[i]);　　break;　　}　　}<

77、;/b>　　}　　output_file.close();　　input_file.open("Textfile.txt");　　if(!input_file){

78、cout<<"can't oen file!"<<endl;　　return 1;　　}　　input_file>>h; 　　cou

79、t<<h<<endl;　　input_file.close();　　cout<<"譯碼結(jié)束，字符已經(jīng)存入Textfile.txt文件中！"<<endl;　　}　　el

80、se if(choice=='Q'||choice=='q') //退出程序　　{ 　　exit(0);　　}<p&

81、gt;　　else //如果選了選項(xiàng)之外的就讓用戶(hù)重新選擇　　{　　cout<<"您沒(méi)有輸入正確的步驟，請(qǐng)重新輸入！"<<endl;　　}&l

82、t;p>　　cout<<endl;　　}　　return 0;　　}　　六、運(yùn)行結(jié)果和調(diào)試分析

83、系統(tǒng)界面如圖：　　初始化赫夫曼樹(shù) 如圖：　　編碼　　譯碼　　退出

84、七、總結(jié)體會(huì)　　在我自己課程設(shè)計(jì)中，就在編寫(xiě)好源代碼后的調(diào)試中出現(xiàn)了不少的錯(cuò)誤，遇到了很多麻煩及困難，我的調(diào)試及其中的錯(cuò)誤和我最終找出錯(cuò)誤，修改為正確的能夠執(zhí)行的程序中，通過(guò)分析，我學(xué)到了：　　在定義頭文件時(shí)可多不可少，即我們可多寫(xiě)些頭文件，肯定不會(huì)出錯(cuò)，但是若沒(méi)有定義所引用的相關(guān)頭文件，必定調(diào)試不通過(guò)；<

85、;p>　　在執(zhí)行譯碼操作時(shí)，不知什么原因，總是不能把要編譯的二進(jìn)制數(shù)與編譯成的字符用連接號(hào)連接起來(lái)，而是按順序直接放在一起，視覺(jué)效果不是很好。還有就是，很遺憾的是，我們的哈夫曼編碼/譯碼器沒(méi)有像老師要求的那樣完成編一個(gè)文件的功能，這是我們?cè)O(shè)計(jì)的失敗之處。　　通過(guò)本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)，我學(xué)習(xí)了很多在上課沒(méi)懂的知識(shí)，并對(duì)求哈夫曼樹(shù)及哈夫曼編碼/譯碼的算法有了更加深刻的了解，更鞏固了課堂中學(xué)習(xí)

86、有關(guān)于哈夫曼編碼的知識(shí)，真正學(xué)會(huì)一種算法了。當(dāng)求解一個(gè)算法時(shí),不是拿到問(wèn)題就不加思索地做，而是首先要先對(duì)它有個(gè)大概的了解，接著再詳細(xì)地分析每一步怎么做，無(wú)論自己以前是否有處理過(guò)相似的問(wèn)題，只要按照以上的步驟，必定會(huì)順利地做出來(lái)。　　這次課程設(shè)計(jì)，我在編輯中犯了不應(yīng)有的錯(cuò)誤，設(shè)計(jì)統(tǒng)計(jì)字符和合并時(shí)忘記應(yīng)該怎樣保存數(shù)據(jù)，對(duì)文件的操作也很生疏。在不斷分析后明確并改正了錯(cuò)誤和疏漏，我的程序有了更高的質(zhì)量&

眾賞文庫(kù)> 全部分類(lèi)> 畢業(yè)設(shè)計(jì)

溫馨提示

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告----哈夫曼

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告----哈夫曼

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載