哈夫曼編譯碼器-數(shù)據(jù)結(jié)構(gòu)報(bào)告.源代碼(源碼)

1、哈夫曼編譯器班級(jí)：08052712學(xué)號(hào)：08052211姓名 ：葛俊峰一 需求分析1. 根據(jù)輸入的字符和字符的權(quán)值建立哈夫曼樹。2. 字符的數(shù)目和字符的權(quán)值由用戶自己設(shè)定。3. 根據(jù)建立的哈夫曼樹進(jìn)行，編碼和譯碼操作。二 概要設(shè)計(jì)1. 哈夫曼樹的定義typedef structchar letter; /存儲(chǔ)字符 int weight; /存儲(chǔ)字符的權(quán)值int parent; /父親int lchild; /左孩子int rchild; /右孩子htnode,*huffmantree;2. 算定義的存儲(chǔ)結(jié)構(gòu)/本結(jié)構(gòu)存儲(chǔ)哈夫曼樹、編碼等，便于后面的操作進(jìn)行typedef struct huffm

2、antree ht;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼表 huffmancode hc; /記錄輸入字符的長(zhǎng)度，編碼和譯碼用到 int len; char *c;/存儲(chǔ)輸入的字符huf;3. 一些操作函數(shù)void sethuffmantree(huffmantree &ht,char *str,int *w,int n)建立哈夫曼樹，str是存儲(chǔ)輸入字符的數(shù)組，w 是存儲(chǔ)字符權(quán)值的數(shù)組，n為輸入字符的數(shù)目huf sethuffmancode(huffmantree &ht,huffmancode &hc,int n,char *s)為哈夫曼樹編碼，ht是已經(jīng)建立的哈夫曼樹，hc用于存儲(chǔ)編碼，民為字符

3、的數(shù)目，s是存儲(chǔ)字符的數(shù)組huf initialization()初始化函數(shù)void encoding(huf huf)編碼函數(shù)void decoding(huf huf)譯碼函數(shù)void print()打印代碼文件的函數(shù)void treeprinting(huf huf)打印哈夫曼樹的函數(shù)4. 主函數(shù)void main() 根據(jù)不同的選擇，執(zhí)行特定的函數(shù)，完成操作三 詳細(xì)設(shè)計(jì)1. 建立哈夫曼樹及求哈夫曼編碼 /初始化操作，接受輸入，調(diào)用函數(shù)sethuffmantree，/sethuffmancode創(chuàng)建樹并編碼huf initialization()huffmantree ht; huffm

4、ancode hc; char c100;/存放輸入的字符int w100;/存放字符的權(quán)值int n;cout請(qǐng)輸入字符的個(gè)數(shù)：n;cout請(qǐng)輸入所有字符：endl; gets(c);for(int i=1;i=n;i+)cout請(qǐng)輸入第i個(gè)字符的權(quán)值：wi; /將數(shù)組c中的元素向右移動(dòng)一位 for(int j=n-1;j=0;j-)cj+1=cj;/ 調(diào)用sethuffmantree函數(shù)sethuffmantree(ht,c,w,n); /調(diào)用sethuffmancode函數(shù)huf huf=sethuffmancode(ht,hc,n,c);return huf; /選擇權(quán)值最小的兩個(gè)結(jié)點(diǎn)

5、void select(huffmantree &ht,int s,int &s1,int &s2) int j, k, i;j=k=10000;s1=s2=0;for(i=1;i=s;i+)if(hti.parent=0)if(hti.weightj)k=j;s2=s1;j=hti.weight;s1=i;else if(hti.weightk)k=hti.weight;s2=i;/創(chuàng)建哈夫曼樹函數(shù)的具體實(shí)現(xiàn)void sethuffmantree(huffmantree &ht,char *str,int *w,int n)huffmantree p; int m,i,s1,s2; /s1,

6、s2是權(quán)值最小的兩個(gè)結(jié)點(diǎn)的序號(hào)m = 2*n-1; /一棵有n個(gè)葉子節(jié)點(diǎn)的哈夫曼樹共有2*n-1個(gè)結(jié)點(diǎn) /動(dòng)態(tài)定義長(zhǎng)度，0號(hào)單元未使用ht=(huffmantree)malloc(m+1)*sizeof(htnode); /初始化for(p=ht+1,i=1;iletter = stri; p-weight = wi; (*p).parent = 0; p-lchild = 0; p-rchild = 0; for(;iweight=0; p-parent=0; p-lchild=0; p-rchild=0; /建立哈夫曼樹for(i=n+1;i=m;+i)select(ht,i-1,s1,s

7、2); /此函數(shù)為自己定義用于選擇出s1,s2 hts1.parent=i; hts2.parent=i; hti.lchild=s1; hti.rchild=s2; hti.weight=hts1.weight+hts2.weight; / 將哈夫曼樹寫入到文件huftree.dat中file *huftree; huftree=fopen(huftree.dat,rt); if(huftree=null) huftree=fopen(huftree.dat,wt); for(i=1;i=m;i+) fprintf(huftree,%d %d %d %dn,hti.weight,hti.pa

8、rent,hti.lchild,hti.rchild);/向文件中寫入 rewind(huftree); /從葉子到根結(jié)點(diǎn)逆向求每個(gè)字符的赫夫曼編碼huf sethuffmancode(huffmantree &ht,huffmancode &hc,int n,char *s) huf huf;/ 分配n個(gè)字符編碼的頭指針向量huf.c=(char *)malloc(n+1)*sizeof(char); /將以輸入的字符存儲(chǔ)在huf的c中for(int j=1;j=n;j+)huf.cj=sj; int start = 1; char *cd; int f,c,i;/分配n個(gè)字符編碼的頭指針向

9、量hc=(huffmancode)malloc(n+1)*sizeof(char*);/臨時(shí)的編碼存儲(chǔ)，作用是分配求編碼的工作空間cd=(char*)malloc(n*sizeof(char);cdn-1=0; /編碼結(jié)束符 /按已生成的哈夫曼樹，逐個(gè)求哈夫曼編碼并獲得各個(gè)字符的哈夫曼編碼 for(i=1;i=n;+i)start = n - 1; /編碼結(jié)束符的位置 /從葉子到根逆向求編碼for(c = i, f = hti.parent; f != 0; c = f, f = htf.parent) if(htf.lchild = c) cd-start = 0; else cd-star

10、t = 1; /為第i個(gè)字符編碼分配空間hci = (char *)malloc(n - start) * sizeof(char); /從cd復(fù)制編碼（串）到hc strcpy(hci, &cdstart); /將hc,ht,n分別存儲(chǔ)到結(jié)構(gòu)體huf中huf.hc=hc;huf.ht=ht;huf.len=n;free(cd); /釋放工作空間return huf;/返回值，供后面的操作使用2. 編碼/利用已建好的哈夫曼樹對(duì)文件中的正文進(jìn)行編碼，然后將結(jié)果存入文/件codefile.dat中,如果正文中沒有要編碼的字符，則鍵盤讀入 void encoding(huf huf) int i=0

11、,j=0,n; char ch10000; /code為指向文件codefile.dat的指針，tbt為指向文件/tobetran的指針 file *code,*tbt; n=huf.len; tbt=fopen(tobetran.dat,rt);/如果tobetran中沒有要編碼的字符，則鍵盤讀入 /如果tobetran中有要編碼的字符，則從文件讀取 if(tbt=null) printf(不存在文件tobetran.dat); printf(n請(qǐng)輸入要進(jìn)行編碼的報(bào)文: ); gets(ch); printf(n); code=fopen(codefile.dat,wt+); else fs

12、canf(tbt,%s,&ch); fclose(tbt); code=fopen(codefile.dat,wt+); / 將ch中的元素與哈夫曼樹中的進(jìn)行匹配，為字符串編碼 while(chj) for(i=1;ilchild|p-rchild) if(dj=0) i=p-lchild; p=&huf.hti; else i=p-rchild; p=&huf.hti; j+; printf(%c,huf.ci); /將找到葉子節(jié)點(diǎn)的字符寫入textfile.dat fprintf(code,%c,huf.ci); fclose(code); printf(譯碼成功，結(jié)果保存到文件textf

13、ile.dat中); 4. 打印代碼文件/將文件codefile每行50個(gè)代碼顯示到終端/將此字符形式的編碼寫入codeprin中void print() char ch; /code是指向codefile的指針，codeprin是指向/codeprin的指針 file *code,*codeprin; code=fopen(codefile.dat,r); codeprin=fopen(codeprin.dat,w); /每行輸出50個(gè)字符，將編碼寫進(jìn)文件codeprin中 for(int i=1;(ch=fgetc(code)!=eof;i+) if(i=50) printf(n); fp

14、utc(n,codeprin); i=1; putchar(ch); fputc(ch,codeprin); fclose(codeprin); fclose(code); printf(n已經(jīng)寫入到文件codeprin.dat中n); 5. 打印哈夫曼樹/輸出哈夫曼樹節(jié)點(diǎn)，權(quán)值，雙親，左孩子，右孩子/前n個(gè)結(jié)點(diǎn)打出對(duì)應(yīng)的字符void treeprinting(huf huf) int j,n; file *tree;tree=fopen(treeprint.dat,w);n=huf.len; for (j=1; j=n; j+) printf(n%4d(%c)%5d%8d%8d%8d,j,h

15、uf.cj,huf.htj.weight,huf.htj.parent,huf.htj.lchild, huf.htj.rchild); fprintf(tree,n%4d(%c)%5d%8d%8d%8d,j,huf.cj,huf.htj.weight,huf.htj.parent,huf.htj.lchild, huf.htj.rchild);for (int h=n+1; h=2*n-1; h+) printf(n%4d%8d%8d%8d%8d,h,huf.hth.weight,huf.hth.parent,huf.hth.lchild, huf.hth.rchild); fprintf(

16、tree,n%4d%8d%8d%8d%8d,h,huf.hth.weight,huf.hth.parent,huf.hth.lchild, huf.hth.rchild);fclose(tree); 6. 主函數(shù)/通過不接收不同的輸入，調(diào)用相應(yīng)的函數(shù)void main()huf huf; int num; char input; while(1) couti:初始化endl; coute:編碼endl; coutd:譯碼endl; coutp:印代碼文件endl; coutt:打印哈夫曼樹endl; coutq:退出endlendl; coutinput; if(input=i|input=i

17、) num=1; else if(input=e|input=e) num=2; else if(input=d|input=d) num=3; else if(input=p|input=p) num=4; else if(input=t|input=t) num=5; else if(input=q|q) num=6; else num=7; switch(num) case 1: huf=initialization(); getch(); break; case 2: encoding(huf); getch(); break; case 3: decoding(huf); getch

18、(); break; case 4: print(); getch(); break; case 5: treeprinting(huf); getch(); break; case 6: return; default: printf(選擇有錯(cuò)，請(qǐng)重新選擇n); getch(); break; 7. 函數(shù)的調(diào)用關(guān)系 main decoding encoding initialization print treeprinting sethuffmancode sethuffmantree select 四 設(shè)計(jì)和調(diào)試分析 1. 開始時(shí)并未設(shè)計(jì)huf這個(gè)結(jié)構(gòu)體，但后來發(fā)現(xiàn)進(jìn)行操作的時(shí)候很費(fèi)力，在編寫的過程中，就將后面要用到東西都放到這個(gè)結(jié)構(gòu)體中了?？梢哉f這個(gè)結(jié)構(gòu)體是在編程過中不斷完善的。2. 在調(diào)試過程中發(fā)現(xiàn)有一些常犯的錯(cuò)誤，如字母的拼寫、結(jié)尾的分號(hào)等，在以后的編程過程中要避免這些錯(cuò)誤。在寫報(bào)告的同時(shí)還發(fā)現(xiàn)一些細(xì)節(jié)上的錯(cuò)誤，如格式化輸出的地方。3. 由于缺乏mfc的知識(shí)，只是將哈夫曼樹打印出來，沒有將哈夫曼樹以樹的形式畫出來。4. select算法的時(shí)間復(fù)雜度為o(n), sethuffmantree的時(shí)間復(fù)雜度為o(n*n), sethuffmancode的時(shí)間復(fù)雜度為o(n)。五 用戶手冊(cè)1. 本程