哈夫曼數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告班級(jí) :姓 名 :學(xué) 號(hào) :E-mail:日 期:實(shí)驗(yàn)題目 :?P149 5.2 哈夫曼編 / 譯碼器? 完成 Huffman 編碼的譯碼過(guò)程。即輸入一個(gè)碼串，請(qǐng)翻譯成相應(yīng)的字符串。要求有編碼過(guò)程和解碼過(guò)程。（ 一 ） 需求分析1. 本程序中，輸入是字符串，包括 +，- ，* ，/ ，（，），以及09，在輸入的末尾需要加上#作為標(biāo)記。2演示程序以用戶和計(jì)算機(jī)的對(duì)話方式執(zhí)行，即在計(jì)算機(jī)終端上顯示“提示信息”之后，由用戶在鍵盤(pán)上輸入相應(yīng)數(shù)據(jù)，若正確則輸出正確結(jié)果，若運(yùn)算無(wú)解，則輸入 error 。3程序執(zhí)行的命令包括：（ 1 ）從文件讀取字符和權(quán)值。（ 2 ）構(gòu)建哈夫曼樹(shù)。（ 3

2、）輸出構(gòu)建的哈夫曼樹(shù)。（ 4 ）選擇1：對(duì)輸入的字符串編碼。（ 5 ）選擇2：對(duì)輸入的數(shù)字譯碼。（ 6 ）選擇0：結(jié)束。4測(cè)試數(shù)據(jù)輸入1出母母母母母輸 字字字字字A BGHA 編碼：1010編碼：110B 編碼：100100G 編碼：100101H 編碼：0000（二）概要設(shè)計(jì)(三)詳細(xì)設(shè)計(jì)#include<stdlib.h>#include<stdio.h>#include<string.h>typedef structint weight;節(jié)點(diǎn)權(quán)值int parent,lchild,rchild;左右孩子的節(jié)點(diǎn)htnode,*huffmantree;ty

3、pedef char * *huffmancode;void select (huffmantree ht,int n,int *s1,int *s2)挑選權(quán)值較小的兩個(gè)節(jié)點(diǎn)int i,j,temp;for(i=1;i<=n;i+)if(hti.parent=0)*s1=i;break;for(j=i+1;j<=n;j+)if(htj.parent=0)歡迎下載12*s2=j;break;for(i=1;i<=n;i+)挑選權(quán)值較小左節(jié)點(diǎn)if(hti.parent=0)if(ht*s1.weight>hti.weight) if(*s2!=i)*s1=i;for(j=1

4、;j<=n;j+) 挑選權(quán)值較小右節(jié)點(diǎn)if(htj.parent=0)if(ht*s2.weight>htj.weight) if(*s1!=j)*s2=j; if(*s1>*s2) temp=*s1;*s1=*s2;*s2=temp;求哈夫曼書(shū)的算法void huffmancoding(huffmantree ht,huffmancode hc,int *w,int n) int i,m;int start,c,f;int s1,s2;char *cd;if(n<=1)return ; m=2*n-1;/n小于2無(wú)需構(gòu)造赫夫曼樹(shù)一共有m=2n-1個(gè)節(jié)點(diǎn)ht=(huff

5、mantree) malloc(m+1)*sizeof(htnode);0號(hào)單元沒(méi)用;for(i=1;i<=n;i+)/ 數(shù)組初始化 hti.weight=wi-1; hti.parent=0; hti.lchild=0; hti.rchild=0; for(;i<=m;+i)hti.weight=0;hti.parent=0;hti.lchild=0;hti.rchild=0;for(i=n+1;i<=m;i+)select(ht,i-1,&s1,&s2);hts1.parent=i;hts2.parent=i;hti.lchild=s1;hti.rchil

6、d=s2;hti.weight=hts1.weight+hts2.weight;從葉子到根節(jié)點(diǎn)的逆向求每個(gè)字符的赫夫曼編碼分配球編碼的工作空間編碼結(jié)束符逐個(gè)字符求赫夫曼編碼/編碼結(jié)束符位置從葉子到根你想編碼分配空間為第i個(gè)字符編碼分配空間從cd復(fù)制編碼（字符串）到 hccd=(char*)malloc(n*sizeof(char);cdn-1='0'for(i=1;i<=n;i+)start=n-1;for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent)if(htf.lchild=c) cd-start='0'else cd

7、-start='1'hci=(char*)malloc(n-start)*sizeof(char); strcpy(hci,&cdstart); void bianma(char p口,char s口,huffmancode hc)/ 編碼 int i,j;for (i=0;pi!='0'i+)for (j=0;j<27;j+)if (pi=sj)printf("字母：%c 編碼：sn",pi,hcj+1);break;printf("nn");return ;void yima(char str,char

8、s口,huffmancode hc)/ 譯碼 int j,t=0;char *p,*r,*m;p=str;m=str;for (;*p<='1' && *p>='0')for (t=0,j=1;j<=27;j+)r=hcj;while (*p=*r && *p!='0')p+,r+,t+;if (*r='0')printf("%cn",sj-1);break;p=m;t=0;p=m+t;m=p;printf("nn");return ; in

9、t main() 主函數(shù)int i=0,n=27,m;int *w;char s27,p100;huffmantree ht;huffmancode hc;hc=(huffmancode)malloc(n*sizeof(huffmancode);w=(int *)malloc(n*sizeof(int);FILE *fp= fopen("a.txt","r");while(!feof(fp)fscanf(fp,"%c %dn",&si,&wi);i+;huffmancoding(ht,hc,w,n);printf(&q

10、uot;輸出編碼為：n");for(i=0;i<n;i+)printf("字母為：c 編碼為:%sn",si,hci+1);while(1)printf("編碼：1n 譯碼：2n 結(jié)束：0n");scanf("%d",&m);getchar();gets(p);switch(m)case 1:bianma(p,s,hc);break;case 2:yima(p,s,hc);break;case 0:return 0;default :printf("errornn");break;fflus

11、h(stdin);getchar();return 0;(四)程序使用說(shuō)明及測(cè)試結(jié)果1.程序使用說(shuō)明(1)本程序的運(yùn)行環(huán)境為 VC6.0。(2)進(jìn)入演示程序后即顯示提示信息:911同式6件。帽0如叩作業(yè)數(shù)據(jù)結(jié)構(gòu)第四次實(shí)驗(yàn)匚萌21015,exer2.測(cè)試結(jié)果FCIJKLMNOFU-RSTUUUKVZ:1 2 0工工rrr工子吳*箓¥計(jì)步行為大關(guān)生為為為為>為為夫?yàn)?；?號(hào)用 F 任 匚用隹14d區(qū)底”母母電叵.岳 母 生瘧瘧 缶缶砧g克：銅附為f 11111Q 編?kù)餅楣け{LW 編科為：制的 編徜為附1H 編?kù)锛樱簃i0iii00 編碼為：uu電工 弟圖為"01H 編碼為

12、二min 編招為血U I居為建附0碼為:Luauw 51111811101 宿為：醺H修 砧為：加工1 碼為：日 碼為再的匕 衲為meiH 福為:FL 碼為: 1111811110 昌為：10阻11U'Usci 式 EnciyADdcEc?pM乍救1傲指給物魅四次矣015.exe" 一回母母國(guó)母母 J=xz£r子7_r IL- 7r ? 編編編編編0 B G H1818 tie L001001.械血 鮑釀編出 V碼 結(jié)束浜音nona 111811181 eiQ 011 na口 pV 三亞強(qiáng)解結(jié)制"第四雙啦'Debug1O15.exeK-b 匚L 匚

13、匕匚匕匚L -L-l? k-l? Y-t- %T Fl -n&HT _8JT33HT 哥 一 JT 一 JT 一 JT 二白不干市不丁巾"T牛TUTU TH干TF*f母卬呼吁印母陟郎助耳期碼碼3、調(diào)試過(guò)程中遇到的問(wèn)題是如何解決提以及對(duì)設(shè)計(jì)與實(shí)現(xiàn)的回顧討論和分析；問(wèn)題:本應(yīng)輸出數(shù)字，但是輸出的是相應(yīng) ASCLL碼對(duì)應(yīng)的字符；運(yùn)算產(chǎn)生的兩位數(shù)會(huì)被當(dāng)成兩個(gè)數(shù)參加下一次計(jì)算解決：原來(lái)的數(shù)字棧是 char型，改成int型問(wèn)題：輸出格式?jīng)]有對(duì)齊解決：運(yùn)用左對(duì)齊和長(zhǎng)度限制4.運(yùn)行界面C;Mj5er5len ovoD esktc p作業(yè)數(shù)據(jù)結(jié)構(gòu)第四次實(shí)驗(yàn) x.DebLg101 5.exe出以母母母母耳母母母母母母母母母烏 母母：時(shí) 耳 耳 母.耳一一4斗牛/¥%/¥/¥，號(hào)/斗產(chǎn)斗/¥鼻,¥*鼻,4斗471.VABCDEFGHI JKLMNOFQR5IU u_5 - - a- -，- * * * *- - - ; -1M編碼為:iiet 編怛?yàn)榇绠T0 褊瑪為：1日阻靦 編稿為30虹0 編科為:皿血 編科為ma 編出為:mil© 編瑪為阻阻 編襠為±WM 編碼為:編科為:工以上回J_1_L酶 編啟為二汽11超1國(guó) 編科為h國(guó)1 士 編褶為rum 編科為:明士工 編用為門(mén)且釀 編t馬為