




版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、一、需求分析目前,進(jìn)行快速遠(yuǎn)距離通信的主要手段是電報(bào),即將需傳送的文字轉(zhuǎn)化成由二級(jí)制的字符組成的字符串。例如,假設(shè)需傳送的電文為“ABACCDA”,它只有4種字符,只需兩個(gè)字符的串,便可以分辨。假設(shè)A、B、C、D、的編碼分別為00,01,10和11,則上述7個(gè)字符的電文便為“”,總長(zhǎng)14位,對(duì)方接受時(shí),可按二位一分進(jìn)行譯碼。當(dāng)然,在傳送電文時(shí),希望總長(zhǎng)盡可能地短。如果對(duì)每個(gè)字符設(shè)計(jì)長(zhǎng)度不等的編碼,且讓電文中出現(xiàn)次數(shù)較多的字符采用盡可能短的編碼,則傳送電文的總長(zhǎng)便可減少。如果設(shè)計(jì)A、B、C、D的編碼分別為0,00,1,01,則上述7個(gè)字符的電文可轉(zhuǎn)換成總長(zhǎng)為9的字符串“000011010”。但是
2、,這樣的電文無(wú)法翻譯,例如傳送過(guò)去的字符串中前4個(gè)字符的字串“0000”就可以有很多種譯法,或是“AAAA”或者“BB”,或者“ABA”等。因此,若要設(shè)計(jì)長(zhǎng)短不等的編碼,則必須是任一字符的編碼都不是另一個(gè)字符的編碼的前綴,這種編碼稱(chēng)作前綴編碼。然而,如何進(jìn)行前綴編碼就是利用哈夫曼樹(shù)來(lái)做,也就有了現(xiàn)在的哈夫曼編碼和譯碼。二、概要設(shè)計(jì)利用哈夫曼樹(shù)編/譯碼(一)、建立哈夫曼樹(shù)(二)、對(duì)哈夫曼樹(shù)進(jìn)行編碼(三)、輸出對(duì)應(yīng)字符的編碼(四)、譯碼過(guò)程主要代碼實(shí)現(xiàn):struct code/結(jié)構(gòu)體的定義char a;int w;int parent;int lchild;int rchild;void crea
3、tion(code *p,int n,int m);/建立哈夫曼樹(shù)void coding(code *p,int n);/編碼void display(code *p,int n,int m);/輸出函數(shù)void translate(char *hc,code *p,int n);/譯碼三、 詳細(xì)設(shè)計(jì)10序號(hào):7653124(1) 、建立哈夫曼樹(shù)ab*c*d*字符:*c646dbaab*c*10634321權(quán)值:33333ab*122112圖3-2圖3-3圖3-1從葉子到根逆向求編碼(2) 、對(duì)哈夫曼樹(shù)進(jìn)行編碼主要代碼實(shí)現(xiàn):for(c=i,f=pi.parent;f!=0;c=f,f=pf.p
4、arent)1ab*c*d*if(pf.lchild=c)/左孩子編碼為'0'10cd-start='0'01else/右孩子編碼為'1'圖3-4cd-start='1'(3) 、輸出對(duì)應(yīng)字符的碼字符編碼a110b111c10d表3-10(4) 、譯碼過(guò)程主要代碼實(shí)現(xiàn):if(strcmp(a,hci)=0)/比較兩個(gè)字符串是否相等,相等則輸出0for(c=2*n-1,j=0;aj!='0'j+)/從根出發(fā),按字符'0'或'1'確定找左孩子或右孩子從跟到葉子順向求字符if(aj=
5、9;0')/左孩子ab*c*d*10c=pc.lchild;10else10c=pc.rchild;/右孩子圖3-5四、 調(diào)試分析(一)、數(shù)字的輸入判斷圖4-1(二)、字母的輸入判斷圖4-2(三)、程序是否繼續(xù)進(jìn)行的判斷圖4-3五、 用戶(hù)手冊(cè)(1) 、首先根據(jù)提示輸入初始化數(shù)據(jù),提示輸入一個(gè)數(shù)字,請(qǐng)輸入一個(gè)數(shù)a,0<a<9999;提示輸入一個(gè)字母,則請(qǐng)輸入一個(gè)字母(az)或者(AZ)中的一個(gè)字符;請(qǐng)勿在輸入一個(gè)數(shù)字后再輸入一個(gè)字符,或者在輸入一個(gè)字符后再輸入一個(gè)數(shù)字。(2) 在某一界面結(jié)束后,會(huì)有“請(qǐng)按回車(chē)?yán)^續(xù)下面操作”提示,請(qǐng)按提示進(jìn)行操作,如輸入其他數(shù)字則無(wú)效,知道輸入
6、回車(chē)符界面才會(huì)跳轉(zhuǎn)。(3) 對(duì)界面的操作可以自行選擇,在詢(xún)問(wèn)是否譯碼的時(shí)候,請(qǐng)按要求進(jìn)行選擇,在一次譯碼結(jié)束后會(huì)詢(xún)問(wèn)是否繼續(xù)譯碼,如需要?jiǎng)t輸入y或者Y,輸入其他字符則退出程序。六、測(cè)試結(jié)果圖6-1(一)、初始化(二)、建立哈夫曼樹(shù)圖6-2(三)、哈夫曼編碼圖6-3(四)、哈夫曼譯碼圖6-4(五)、錯(cuò)誤判定圖6-5附錄:源代碼:#include<stdio.h>#include<string.h>#include<stdlib.h>#include<malloc.h>struct code/結(jié)構(gòu)體的定義char a;int w;int parent
7、;int lchild;int rchild;void creation(code *p,int n,int m);/建立哈夫曼樹(shù)void coding(code *p,int n);/編碼void translate(char *hc,code *p,int n);/譯碼void display(code *p,int n,int m);/輸出函數(shù)/主函數(shù)void main()int i,n,m;code *ht;printf("字符的數(shù)量:n(請(qǐng)輸入一個(gè)大于0的數(shù)字,輸入多個(gè)數(shù)字則按第一個(gè)數(shù)字運(yùn)行)n");while(scanf("%d",&
8、n)!=1|n<0|n>9999)printf("重新輸入:n");fflush(stdin);m=2*n-1;/哈夫曼樹(shù)中沒(méi)有度為1的結(jié)點(diǎn),故含有m=2n-1個(gè)結(jié)點(diǎn)ht=(code*)malloc(m+1)*sizeof(code);/動(dòng)態(tài)申請(qǐng)內(nèi)存for(i=1;i<=n;i+)/對(duì)1n的數(shù)進(jìn)行初始化printf("輸入編碼中的字符(請(qǐng)輸入一個(gè)字母):n");fflush(stdin);scanf("%c",&hti.a);while(!(hti.a>'a'|hti.a<'
9、;z'|hti.a>'A'|hti.a<'Z')printf("重新輸入:n");fflush(stdin);scanf("%c",&hti.a);/清空輸入緩沖區(qū),往往是確保不影響后面數(shù)據(jù)的讀取printf("輸入字符的權(quán)值(請(qǐng)輸入一個(gè)數(shù)字):n");while(scanf("%d",&hti.w)!=1|hti.w<0|hti.w>9999)printf("重新輸入:n");fflush(stdin);/清空輸入
10、緩沖區(qū),往往是確保不影響后面數(shù)據(jù)的讀取hti.lchild=0;hti.rchild=0;hti.parent=0;for(i=n+1;i<=m;i+)/對(duì)n+12n-1的數(shù)進(jìn)行初始化hti.a='*'hti.w=0;hti.lchild=0;hti.rchild=0;hti.parent=0;creation(ht,n,m);printf("請(qǐng)按回車(chē)進(jìn)入哈夫曼樹(shù)對(duì)應(yīng)界面n");getchar();getchar();system("cls");display(ht,n,m);printf("請(qǐng)按回車(chē)進(jìn)入編碼對(duì)應(yīng)界面n&q
11、uot;);getchar();system("cls");coding(ht,n);getchar();void creation(code *ht,int n,int m)int i,j,m1,m2,t1,t2;for(i=n+1;i<=m;i+)j=1;/找到第一個(gè)最小值(雙親不為0)while(htj.parent!=0)/找到表中第一個(gè)沒(méi)有雙親的結(jié)點(diǎn)j+;t1=htj.w;m1=j;for(j=m1+1;j<=m;j+)if(htj.parent=0&&htj.w!=0)/條件(htj.w!=0)是因?yàn)閚2n-1的權(quán)值初始值為0if(h
12、tj.w<t1)t1=htj.w;m1=j;htm1.parent=i;/第一個(gè)值的雙親為htihti.lchild=m1;/hi的的左孩子是最小值的序號(hào)j=1;/剩余中找到第二個(gè)最小值(雙親不為0)while(htj.parent!=0)j+;t2=htj.w;m2=j;for(j=m2+1;j<=m;j+)if(htj.parent=0&&htj.w!=0)if(htj.w<t2)t2=htj.w;m2=j;htm2.parent=i;/第二個(gè)值的雙親為htihti.rchild=m2;/hi的的左孩子是最小值的序號(hào)hti.w=t1+t2;/hi的權(quán)值是找
13、到的兩個(gè)值的權(quán)值之和void coding(code *p,int n)int i,c,f;char *hc;/指針的指針char *cd;char ch;int start;hc=(char*)malloc(n+1)*sizeof(char *);/分配n個(gè)字符編碼的頭指針向量cd=(char*)malloc(n*sizeof(char);/分配求編碼的工作空間cdn-1='0'/編碼結(jié)束符for(i=1;i<=n;i+)start=n-1;for(c=i,f=pi.parent;f!=0;c=f,f=pf.parent)/從葉子到根逆向求編碼if(pf.lchild=
14、c)/左孩子編碼為'0'cd-start='0'else/右孩子編碼為'1'cd-start='1'hci=(char*)malloc(n-start)*sizeof(char);/為第i個(gè)字符編碼分配空間strcpy(hci,&cdstart);/從cd復(fù)制編碼(串)到hc,&是取地址符,即取首地址,從start位置到'0'的編碼為止。free(cd);/釋放工作空間printf("n輸出編碼后的結(jié)果:n");printf("符號(hào)數(shù)碼n");for(i=1;
15、i<=n;i+)printf("n%c%sn",pi.a,hci);printf("是否進(jìn)行譯碼操作,是則譯碼,否則退出程序!n是(輸入y/Y)否(輸入其他字符)n");scanf("%d",&ch);if(ch='y'|ch='Y')translate(hc,p,n);elseexit(0);void translate(char *hc,code *p,int n)char a10,ch;int i,j,c;doprintf("nnn請(qǐng)輸入編碼:n");scanf(
16、"%s",a);/回車(chē)之后會(huì)自動(dòng)生成'0'for(i=1;i<=n;i+)if(strcmp(a,hci)=0)/比較兩個(gè)字符串是否相等,相等則輸出0for(c=2*n-1,j=0;aj!='0'j+)/從根出發(fā),按字符'0'或'1'確定找左孩子或右孩子if(aj='0')/左孩子c=pc.lchild;elsec=pc.rchild;/右孩子printf("字符是:n");printf("%cn",pc.a);break;if(i>n)pri
17、ntf("編碼不存在對(duì)應(yīng)的字符!n");printf("是否繼續(xù)輸入?是(輸入y或者Y)否(其他)n");fflush(stdin);scanf("%c",&ch);while(ch='y'|ch='Y');void display(code *p,int n,int m)int i;printf("n序號(hào)碼值權(quán)值雙親左孩子右孩子n");for(i=1;i<=m;i+)printf("%d%c%d%d%d%dn",i,pi.a,pi.w,pi.parent,pi.lchild,pi.rchild);設(shè)計(jì)體會(huì)通過(guò)這個(gè)課程設(shè)計(jì),讓我對(duì)數(shù)據(jù)結(jié)構(gòu)這門(mén)課程有了更深一步
溫馨提示
- 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ù)網(wǎng)僅提供信息存儲(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 三年級(jí)下學(xué)期閱讀提升計(jì)劃
- 樹(shù)脂瓦安裝過(guò)程中常見(jiàn)問(wèn)題的技術(shù)措施
- 2025年崇明縣高三一模作文寫(xiě)作技巧
- 八年級(jí)英語(yǔ)教學(xué)互動(dòng)與反饋計(jì)劃
- 2025藝術(shù)品市場(chǎng)推廣計(jì)劃
- 淋巴轉(zhuǎn)移癌護(hù)理
- 高一數(shù)學(xué)家長(zhǎng)溝通交流計(jì)劃
- 腹部術(shù)后康復(fù)護(hù)理
- 2025年小學(xué)語(yǔ)文復(fù)習(xí)日程安排
- 耳科護(hù)理個(gè)案分析
- 國(guó)有企業(yè)干部選拔任用條例
- 辦理居住證工作證明 (模板)
- 中藏醫(yī)適宜技術(shù)課件
- 通用造價(jià)35kV~750kV線路(國(guó)網(wǎng))課件
- 2022年廣東省深圳市中考化學(xué)真題試卷
- 工貿(mào)企業(yè)有限空間作業(yè)場(chǎng)所安全管理臺(tái)賬
- 國(guó)際財(cái)務(wù)管理教學(xué)ppt課件(完整版)
- DB33∕T 715-2018 公路泡沫瀝青冷再生路面設(shè)計(jì)與施工技術(shù)規(guī)范
- 彩色簡(jiǎn)約魚(yú)骨圖PPT圖表模板
- 光引發(fā)劑的性能與應(yīng)用
- PID控制經(jīng)典PPT
評(píng)論
0/150
提交評(píng)論