哈夫曼樹課程設(shè)計(jì)報(bào)告樣本

數(shù)據(jù)構(gòu)造課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目：哈夫曼樹應(yīng)用專業(yè)：軟件工程班級(jí)：軟件學(xué)生：學(xué)號(hào)：指引教師：羅作民/張翔起止時(shí)間：-07-04—-07-08年春季學(xué)期目錄一．詳細(xì)任務(wù) …..21功能……………...22分步實(shí)行………………………...2.3規(guī)定……………...2二．哈夫曼編碼 21問(wèn)題描述 22.基本規(guī)定 33實(shí)現(xiàn)提示 3三．設(shè)計(jì)流程圖 41建立哈夫曼樹…………………...42編碼……………...53譯碼……………...64主程序…………...7四．設(shè)計(jì)概要 81問(wèn)題哈夫曼定義..............................................................................................8..2所實(shí)現(xiàn)功能函數(shù)如下………..83功能模塊………………………..8五．源程序 9六．調(diào)試分析 15七．心得與體會(huì) 18八．參照文獻(xiàn) 18一、任務(wù)題目：哈夫曼樹應(yīng)用1.功能：1．從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹并將它存于文獻(xiàn)hfmTree中.將已在內(nèi)存中哈夫曼樹以直觀方式（例如樹）顯示在終端上；2．運(yùn)用已經(jīng)建好哈夫曼樹（如不在內(nèi)存，則從文獻(xiàn)htmTree中讀入），對(duì)文獻(xiàn)ToBeTran中正文進(jìn)行編碼，然后將成果存入文獻(xiàn)CodeFile中，并輸出成果，將文獻(xiàn)CodeFile以緊湊格式先是在終端上，每行50個(gè)代碼。同步將此字符形式編碼文獻(xiàn)寫入文獻(xiàn)CodePrint中。3．運(yùn)用已建好哈夫曼樹將文獻(xiàn)CodeFile中代碼進(jìn)行譯碼，成果存入文獻(xiàn)TextFile中，并輸出成果。2.分步實(shí)行：初步完畢總體設(shè)計(jì)，搭好框架，擬定人機(jī)對(duì)話界面，擬定函數(shù)個(gè)數(shù)；完畢最低規(guī)定：完畢功能1；進(jìn)一步規(guī)定：完畢功能2和3。有興趣同窗可以自己擴(kuò)充系統(tǒng)功能。3.規(guī)定：1）界面和諧，函數(shù)功能要?jiǎng)澐趾?）總體設(shè)計(jì)應(yīng)畫一流程圖3）程序要加必要注釋要提供程序測(cè)試方案程序一定要經(jīng)得起測(cè)試，寧可功能少某些，也要能運(yùn)營(yíng)起來(lái)，不能運(yùn)營(yíng)程序是沒(méi)有價(jià)值。二、哈夫曼編碼1.問(wèn)題描述運(yùn)用赫夫曼編碼進(jìn)行通信可以大大提高信道運(yùn)用率，縮短信息傳播時(shí)間，減少傳播成本。這規(guī)定在發(fā)送端通過(guò)一種編碼系統(tǒng)對(duì)待傳播數(shù)據(jù)預(yù)先編碼，在接受端將傳來(lái)數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（即可以雙向傳播信息信道），每端都需要一種完整編/譯碼系統(tǒng)。試為這樣信息收發(fā)站編寫一種赫夫曼碼編/譯碼系統(tǒng)?；疽?guī)定一種完整系統(tǒng)應(yīng)具備如下功能：(1)I：初始化（Initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立赫夫曼樹，并將它存于文獻(xiàn)hfmTree中。(2)E：編碼（Encoding）。運(yùn)用已建好赫夫曼樹（如不在內(nèi)存，則從文獻(xiàn)hfmTree中讀入），對(duì)文獻(xiàn)ToBeTran中正文進(jìn)行編碼，然后將成果存入文獻(xiàn)CodeFile中。(3)D：譯碼（Decoding）。運(yùn)用已建好赫夫曼樹將文獻(xiàn)CodeFile中代碼進(jìn)行譯碼，成果存入文獻(xiàn)Textfile中。實(shí)現(xiàn)提示(1)編碼成果以文本方式存儲(chǔ)在文獻(xiàn)Codefile中。(2)顧客界面可以設(shè)計(jì)為“菜單”方式：顯示上述功能符號(hào)，再加上“Q”，表達(dá)退出運(yùn)營(yíng)Quit。請(qǐng)顧客鍵入一種選取功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次顧客選取了“Q”為止。(3)在程序一次執(zhí)行過(guò)程中，第一次執(zhí)行I，D或C命令之后，赫夫曼樹已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，由于文獻(xiàn)hfmTree也許早已建好。三、設(shè)計(jì)流程圖建立哈夫曼樹：開始開始n,<=1Renturn0m=2*n-1i=1;i<=n;++iWhile(getchar()=”/n”輸入字符與權(quán)值HT[i].ch=zHT[i].weight=wHT[i].parent=0HT[i].lchild=0HT[i].rchild=0編碼：開始開始cd[start]=”1”i=1;i<=n;++istart=n-1cd[start]=”0”c=I;f=HT[i].parent；f!=0;f=HT[f].parentHT[f].child==l結(jié)束譯碼：開始開始L=k!output_file!cout”cantopenfile”Return1Cout”can’topenfile”Strcmp(H[i].hlchild==0結(jié)束i=1;i<n;i++while(h[k]!=”0”)j=0;j<strlen(h[i]);j++;l++K=0h[j]=”\0”輸出譯碼主程序：開始開始main建立哈夫曼樹choice==”I”||choice==”I”結(jié)束編碼return0choice==”E”||choice==”e”choice==”D”||choice==”d”choice==”Q”||choice==”q”編碼四、概要設(shè)計(jì)1）問(wèn)題哈夫曼定義：1.哈夫曼樹節(jié)點(diǎn)數(shù)據(jù)類型定義為：typedefstruct{//赫夫曼樹構(gòu)造體 charch; intweight；//權(quán)值 intparent,lchild,rchild;}htnode,*hfmtree;2）所實(shí)現(xiàn)功能函數(shù)如下1、voidhfmcoding(hfmtree&HT,hfmcode&HC,intn)初始化哈夫曼樹，解決InputHuffman(HuffmanHfm)函數(shù)得到數(shù)據(jù)，按照哈夫曼規(guī)則建立2叉樹。此函數(shù)塊調(diào)用了Select（）函數(shù)。2、voidSelect(hfmtree&HT,inta,int*p1,int*p2)//Select函數(shù)，選出HT樹到a為止，權(quán)值最小且parent為02個(gè)節(jié)點(diǎn)3、intmain()主函數(shù)：運(yùn)用已建好哈夫曼樹（如不在內(nèi)存，則從文獻(xiàn)hfmtree.txt中讀入）對(duì)文獻(xiàn)中正文進(jìn)行編碼，然后將成果存入文獻(xiàn)codefile.txt中。如果正文中沒(méi)有要編碼字符，則鍵盤讀入并存儲(chǔ)到ToBeTran文獻(xiàn)中。讀入ToBeTran中將要編碼內(nèi)容，將編碼好哈夫曼編碼存儲(chǔ)到CodeFile中。4、Encoding編碼功能：對(duì)輸入字符進(jìn)行編碼5、Decoding譯碼功能：運(yùn)用已建好哈夫曼樹將文獻(xiàn)codefile.txt中代碼進(jìn)行譯碼，成果存入文獻(xiàn)textfile.dat中。Print()打印功能函數(shù)：輸出哈夫曼樹，字符，權(quán)值，以及它相應(yīng)編碼。6.主函數(shù)簡(jiǎn)要闡明，主函數(shù)重要設(shè)計(jì)是一種分支語(yǔ)句，讓顧客挑選所實(shí)現(xiàn)功能。使用鏈樹存儲(chǔ)，然后分別調(diào)用記錄頻數(shù)函數(shù)，排序函數(shù)，建立哈夫曼函數(shù)，編碼函數(shù)，譯碼函數(shù)來(lái)實(shí)現(xiàn)功能。3）功能模塊：哈夫曼編碼/譯碼器哈夫曼編碼/譯碼器初始化哈夫曼樹編碼譯碼打印哈夫曼樹打印編碼五、源程序#include<iostream.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#include<fstream.h>typedefstruct{//哈夫曼樹構(gòu)造體 charch; intweight；//權(quán)值 intparent,lchild,rchild;}htnode,*hfmtree;typedefchar**hfmcode;voidSelect(hfmtree&HT,inta,int*p1,int*p2)//Select函數(shù)，選出HT樹到a為止，權(quán)值最小且parent為02個(gè)節(jié)點(diǎn){ inti,j,x,y; for(j=1;j<=a;++j){ if(HT[j].parent==0){ x=j; break; } } for(i=j+1;i<=a;++i){ if(HT[i].weight<HT[x].weight&&HT[i].parent==0){ x=i；//選出最小節(jié)點(diǎn) } } for(j=1;j<=a;++j) { if(HT[j].parent==0&&x!=j) { y=j; break; } } for(i=j+1;i<=a;++i) { if(HT[i].weight<HT[y].weight&&HT[i].parent==0&&x!=i) { y=i；//選出次小節(jié)點(diǎn) } } if(x>y){ *p1=y; *p2=x; } else { *p1=x; *p2=y; }}voidhfmcoding(hfmtree&HT,hfmcode&HC,intn)//構(gòu)建哈夫曼樹HT，并求出n個(gè)字符哈夫曼編碼HC{ inti,start,c,f,m,w; intp1,p2; char*cd,z; if(n<=1){ return; } m=2*n-1; HT=(hfmtree)malloc((m+1)*sizeof(htnode)); for(i=1;i<=n;++i)//初始化n個(gè)葉子結(jié)點(diǎn) { printf("請(qǐng)輸入第%d字符信息和權(quán)值：",i); scanf("%c%d",&z,&w); while(getchar()!='\n') { continue; } HT[i].ch=z; HT[i].weight=w; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for(;i<=m;++i)//初始化別的結(jié)點(diǎn) { HT[i].ch='0'; HT[i].weight=0; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for(i=n+1;i<=m;++i)//建立哈夫曼樹 { 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; } HC=(hfmcode)malloc((n+1)*sizeof(char*)); cd=(char*)malloc(n*sizeof(char)); cd[n-1]='\0'; 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) { if(HT[f].lchild==c) { cd[--start]='0'; } else { cd[--start]='1'; } } HC[i]=(char*)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]); } free(cd);}intmain(){ charcode[100],h[100],hl[100]; intn,i,j,k,l; ifstreaminput_file；//文獻(xiàn)輸入輸出流 ofstreamoutput_file; charchoice,str[100]; hfmtreeHT; hfmcodeHC; cout<<"\n"; cout<<""<<"軟件092班"<<""<<"姓名:張耀飛"<<""<<"學(xué)號(hào)：\n"; while(choice!='Q'&&choice!='q')//當(dāng)choice值不為q且不為Q時(shí)循環(huán) { cout<<""<<"*************************哈夫曼編碼/譯碼器*************************\n"; cout<<""<<"I.Init"<<""<<"E.Encoding"<<""<<"D.Decoding"<<""<<"Q.Exit\n"; cout<<"請(qǐng)輸入您要操作環(huán)節(jié)："; cin>>choice; if(choice=='I'||choice=='i')//初始化赫夫曼樹 { cout<<"請(qǐng)輸入字符個(gè)數(shù)："; cin>>n; hfmcoding(HT,HC,n); for(i=1;i<=n;++i) { cout<<HT[i].ch<<":"<<HC[i]<<endl; } output_file.open("hfmTree.txt"); if(!output_file){ cout<<"can'topenfile!"<<endl; return1; } for(i=1;i<=n;i++) { output_file<<"("<<HT[i].ch<<HC[i]<<")"; } output_file.close(); cout<<"哈夫曼樹已經(jīng)創(chuàng)立完畢，并且已經(jīng)放入hfmTree.txt文獻(xiàn)中!"<<endl; } elseif(choice=='E'||choice=='e')//進(jìn)行編碼，并將字符放入ToBeTran.txt，碼值放入CodeFile.txt中 { printf("請(qǐng)輸入字符："); gets(str); output_file.open("ToBeTree.txt"); if(!output_file) { cout<<"can'topenfile!"<<endl; return1; } output_file<<str<<endl; output_file.close(); output_file.open("CodeFile.txt"); if(!output_file){ cout<<"can'topenfile!"<<endl; return1; } for(i=0;i<strlen(str);i++){ for(j=0;j<=n;++j) { if(HT[j].ch==str[i]) { output_file<<HC[j]; break; } } } output_file.close(); cout<<"\n"; cout<<"編碼完畢，并且已經(jīng)存入CodeFile.txt文獻(xiàn)！\n"; input_file.open("CodeFile.txt")；//從CodeFile.txt中讀入編碼，輸出在終端 if(!input_file) { cout<<"can'topenfile!"<<endl; return1; } input_file>>code; cout<<"編碼碼值為："<<code<<endl; input_file.close(); } elseif(choice=='D'||choice=='d')//讀入CodeFile.txt中編碼進(jìn)行譯碼，將譯出來(lái)字符放入Textfile.txt中 { input_file.open("CodeFile.txt"); if(!input_file){ cout<<"can'topenfile!"<<endl; return1; } input_file>>h; input_file.close(); output_file.open("Textfile.txt"); if(!output_file) { cout<<"can'topenfile!"<<endl; return1; } k=0; while(h[k]!='\0')//先用編碼中前幾種和字符編碼相比較，然后往后移 { for(i=1;i<=n;i++){ l=k; for(j=0;j<strlen(HC[i]);j++,l++){ hl[j]=h[l]; } hl[j]='\0'; if(strcmp(HC[i],hl)==0) { output_file<<HT[i].ch; k=k+strlen(HC[i]); break; } } } output_file.close(); input_file.open("Textfile.txt"); if(!input_file){ cout<<"can'topenfile!"<<endl; return1; } input_file>>h； cout<<h<<endl; input_file.close(); cout<<"譯碼結(jié)束，字符已經(jīng)存入Textfile.txt文獻(xiàn)中！"<<endl; } elseif(choice=='Q'||choice=='q')//退出程序 { exit(0); } else//如果選了選項(xiàng)之外就讓顧客重新選取 { cout<<"您沒(méi)有輸入對(duì)的環(huán)節(jié)，請(qǐng)重新輸入！"<<endl;