哈夫曼編碼譯碼器

...wd......wd......wd...哈夫曼編碼譯碼器學(xué)院班級:信息工程學(xué)院軟件1501指導(dǎo)教師:朱俊武小組成員:劉洋蔣佳燁冀假設(shè)含本人學(xué)號:151303107報告書寫:冀假設(shè)含學(xué)生成績:目錄一、總體介紹·····························03-04二、詳細設(shè)計·····························04-11三、運行測試·····························11-12四、課設(shè)總結(jié)·····························13-13五、附錄代碼·····························13-19一、總體介紹1.1任務(wù)概述我們小組做了兩個版本，其中一個為文件操作版，另一個為鍵盤操作版。兩個版本都實現(xiàn)了哈夫曼編碼/譯碼操做。我主要負責(zé)的是構(gòu)造哈夫曼樹，給出各個字符的哈夫曼編碼，加密操做，整個鍵盤操作版系統(tǒng)的代碼重組、編輯。開發(fā)的過程中使用了Codelite、Dev、Vc等軟件。參考書籍為《數(shù)據(jù)構(gòu)造》〔c語言版〕。其中文件操作版的具體實現(xiàn)為：eq\o\ac(○,1)能夠?qū)崿F(xiàn)對26個小寫字母外加空格進展哈夫曼編碼，并能夠?qū)σ徽恼隆灿行懽帜负涂崭窠M成〕進展加密，生成密碼文件。最后根據(jù)生成的密碼翻譯出原文并存檔。eq\o\ac(○,2)在使用程序時，使用者只需要對ToBetran文件進展原文的輸入〔使用小寫字母或空格〕，加密和解密功能由程序自主來完成。eq\o\ac(○,3)程序運行的過程中會輸出進展編碼的26個小寫字母和空格〔字符型〕，并輸出其對應(yīng)的權(quán)值〔整型〕。還輸出字符的編碼及生成的密文。最后輸出解密后的原文。鍵盤操作版為：eq\o\ac(○,1)要求從鍵盤輸入字符集和字符的權(quán)值，大局部字符均可輸入，需要各個字符的權(quán)值不能一樣。eq\o\ac(○,2)利用輸入的權(quán)值建設(shè)哈夫曼樹，得到每個字符的前綴編碼。eq\o\ac(○,3)輸入字符串，程序?qū)ζ溥M展加密。eq\o\ac(○,4)輸入密文〔1010101……………..〕對密文進展解密。 兩個版本都利用了哈夫曼樹解決問題，通過建設(shè)哈夫曼樹，得出每個字符的獨特前綴編碼，也就是密文，然后利用密文對明文進展加密得到密文。密文轉(zhuǎn)換為明文則是通過對哈夫曼樹的遍歷?！仓跋脒^字符串的匹配得到明文但是算法太為復(fù)雜〕。1.2系統(tǒng)功能框圖本系統(tǒng)分為三個大的模塊：構(gòu)造哈夫曼樹，編碼，譯碼。1.3功能難點 本系統(tǒng)的實現(xiàn)難點在于哈夫曼樹的構(gòu)造。編碼、譯碼功能的實現(xiàn)都是基于哈夫曼樹的。二、詳細設(shè)計2.1哈夫曼樹的構(gòu)造哈夫曼樹，又稱最優(yōu)樹，是一類帶權(quán)路徑長度最短的樹，有著廣泛的應(yīng)用。哈夫曼樹的構(gòu)造過程如下：1.初始化：根據(jù)給定的n個權(quán)值{w1,w2,…wn}構(gòu)成n棵二叉樹的集合F={T1,T2,..,Tn}，其中每棵二叉樹Ti中只有一個帶權(quán)wi的根節(jié)點，左右子樹均空。2.找最小樹：在F中選擇兩棵根結(jié)點權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且至新的二叉樹的根結(jié)點的權(quán)值為其左右子樹上根結(jié)點的權(quán)值之和。3.刪除與參加：在F中刪除這兩棵樹，并將新的二叉樹參加F中。4.判斷：重復(fù)前兩步〔2和3〕，直到F中只含有一棵樹為止。該樹即為哈夫曼樹。2.2代碼實現(xiàn)哈夫曼樹和哈夫曼編碼的儲存表示typedefstruct{ intweight; intparent,lchild,rchild;}HTNode,*HuffmanTree;//動態(tài)分配數(shù)組儲存哈夫曼樹typedefchar**HuffmanCode;//動態(tài)分配數(shù)組儲存哈夫曼編碼表voidSelect(HuffmanTreeHT,intp,int*s1,int*s2)該函數(shù)的功能為：找出HT[1….i-1]中parent為0且weight最小的兩個結(jié)點，其序號為s1，s2。voidHuffmanCoding(HuffmanTreeHT,HuffmanCodeHC,int*w,intn,char*a)該函數(shù)的功能為構(gòu)造哈夫曼樹HT，并求出n個字符的哈夫曼編碼HC。以下為兩個函數(shù)的流程圖或詳細設(shè)計。voidHuffmanCoding(HuffmanTreeHT,HuffmanCodeHC,int*w,intn,char*a)指針a指向輸入的字符集，指針w指向字符集的度，n為字符集的大小。注：具體程序中參加了輸出各個字符的哈夫曼編碼的功能，在流程圖沒有顯示。沒畫完下面還有喲?。。?！詳細代碼：voidHuffmanCoding(HuffmanTreeHT,HuffmanCodeHC,int*w,intn,char*a){ intm=0;intc;intf; intstart; char*cd; int*s1; int*s2; inti; s1=(int*)malloc(sizeof(int)); s2=(int*)malloc(sizeof(int)); m=2*n-1; if(n<=1) { printf("字符的個數(shù)過少\n"); return; } HuffmanTreep; p=HT; p++; for(i=1;i<=n;++i,++p,++w){ p->weight=*w; p->parent=0; p->lchild=0; p->rchild=0; } for(;i<=m;++i,++p){ p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; } for(i=n+1;i<=m;++i){ Select(HT,i-1,s1,s2); HT[*s1].parent=i;HT[*s2].parent=i; HT[i].lchild=*s1;HT[i].rchild=*s2; HT[i].weight=HT[*s1].weight+HT[*s2].weight; } cd=(char*)malloc(n*sizeof(char)); cd[n-1]='\0'; for(i=1;i<=n;++i){ 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'; elsecd[--start]='1'; HC[i]=(char*)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]); printf("%c",*a); a++; printf("%s\n",HC[i]); } free(cd);}voidSelect(HuffmanTreeHT,intp,int*s1,int*s2)詳細設(shè)計：eq\o\ac(○,1)首先通過一個循環(huán)找出當前數(shù)組中weight最小的一個。記錄下它的序號。eq\o\ac(○,2)也是一和一樣的循環(huán)和算法。加上一個if語句，如果循環(huán)到與第一次序號一樣的那次，就continue跳過這次比擬。eq\o\ac(○,3)將得到的權(quán)值最小的兩個傳到s1和是s2指向的地址。這就是哈夫曼樹的構(gòu)造和生成哈夫曼編碼的過程。詳細代碼：voidSelect(HuffmanTreeHT,intp,int*s1,int*s2)//i為遍歷長度{ inti=1; intx=0; inty=0; intmin=1000; intmin1=1000; intv=1; *s1=1;*s2=1; for(i=1;i<=p;i++) { x=HT[i].parent; y=HT[i].weight; if(x==0&&min>y) { min=HT[i].weight; *s1=i;v=i; } } for(i=1;i<=p;i++){ x=HT[i].parent; y=HT[i].weight; if(i==v) continue; if(x==0&&min1>=y) { min1=HT[i].weight; *s2=i; } }}2.3編碼〔加密〕voidHuffmanEncryption(HuffmanCodeHC,char*a,intn)此函數(shù)為加密函數(shù)。該加密函數(shù)的流程圖如下：該功能的實現(xiàn)就是通過一個簡單的查找，通過字符與字符的哈夫曼編碼在不同數(shù)組的對應(yīng)關(guān)系，進展加密。Input[]儲存輸入的字符串。Lo為輸入的字符串長度，n為原字符集的字符個數(shù)。詳細代碼如下：voidHuffmanEncryption(HuffmanCodeHC,char*a,intn){ charinput[100]; inti=0,j=0; charlu=''; intlo=0;//要加密的字符串的長度 charc; printf("請輸入你要加密的字符串\n"); while((lu=getchar()!='\n'&&lu!=EOF)) ; c=getchar(); while(c!='\n'){ input[i]=c; i++; c=getchar(); } lo=i; for(i=0;i<lo;i++){ for(j=0;j<n;j++) { if(input[i]==a[j]) printf("%s",HC[j+1]); } } printf("\n");}三、運行測試菜單界面：構(gòu)造哈夫曼樹：編碼：譯碼：密鑰：譯碼測試：四、總結(jié) 經(jīng)過幾天的設(shè)計與編碼我們小組終于完成了兩個不同的版本的哈夫曼編碼譯碼器。雖然兩個系統(tǒng)大局部的算法一樣，但是也算我們的嘗試。美中缺乏的是我們沒能把兩個版本的系統(tǒng)融合起來。開發(fā)過程中遇到的最大的問題就是輸入輸出流的問題。因為是從鍵盤輸入數(shù)據(jù)的所以難免會遇到這種問題。我通過輸入流的過濾解決了此問題。通過這幾天的實驗，加深了我對哈夫曼樹的理解，也加強了自己的動手能力。數(shù)據(jù)構(gòu)造這門課程還有很多很多的東西，我們?nèi)詰?yīng)該繼續(xù)努力。附錄全部代碼：#include<stdio.h>#include<stdlib.h>#include<string.h>#include<windows.h>typedefstruct{ intweight; intparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;voidSelect(HuffmanTreeHT,intp,int*s1,int*s2)//i為遍歷長度，big{ inti=1; intx=0; inty=0; intmin=1000; intmin1=1000; intv=1; *s1=1;*s2=1; for(i=1;i<=p;i++) { x=HT[i].parent; y=HT[i].weight; if(x==0&&min>y) { min=HT[i].weight; *s1=i;v=i; } } for(i=1;i<=p;i++){ x=HT[i].parent; y=HT[i].weight; if(i==v) continue; if(x==0&&min1>=y) { min1=HT[i].weight; *s2=i; } }}voidHuffmanCoding(HuffmanTreeHT,HuffmanCodeHC,int*w,intn,char*a){ intm=0;intc;intf; intstart; char*cd; int*s1; int*s2; inti; s1=(int*)malloc(sizeof(int)); s2=(int*)malloc(sizeof(int)); m=2*n-1; if(n<=1) { printf("字符的個數(shù)過少\n"); return; } HuffmanTreep; p=HT; p++; for(i=1;i<=n;++i,++p,++w){ p->weight=*w; p->parent=0; p->lchild=0; p->rchild=0; } for(;i<=m;++i,++p){ p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; } for(i=n+1;i<=m;++i){ Select(HT,i-1,s1,s2); HT[*s1].parent=i;HT[*s2].parent=i; HT[i].lchild=*s1;HT[i].rchild=*s2; HT[i].weight=HT[*s1].weight+HT[*s2].weight; } cd=(char*)malloc(n*sizeof(char)); cd[n-1]='\0'; for(i=1;i<=n;++i){ 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'; elsecd[--start]='1'; HC[i]=(char*)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]); printf("%c",*a); a++; printf("%s\n",HC[i]); } free(cd);}voidHuffmanEncryption(HuffmanCodeHC,char*a,intn){ charinput[100]; inti=0,j=0; charlu=''; intlo=0;//要加密的字符串的長度 charc; printf("請輸入你要加密的字符串\n"); while((lu=getchar()!='\n'&&lu!=EOF)) ; c=getchar(); while(c!='\n'){ input[i]=c; i++; c=getchar(); } lo=i; for(i=0;i<lo;i++){ for(j=0;j<n;j++) { if(input[i]==a[j]) printf("%s",HC[j+1]); } } printf("\n");}voidHuffmandeciphering(HuffmanCodeHC,char*a,intn,HuffmanTreeHT)//解密{ intinput[100]={0}; charc=''; intnum=0; intm=1; intt=0; printf("請輸入你要解密的字符串\n"); inti=0; getchar(); while(c!='\n'){ c=getchar(); input[i]=(int)c-48; i++; } num=i; for(i=1;t==0;i++) { if(HT[i].parent==0) { t=i;//根結(jié)點的位置 } } m=t; for(i=0;i<num;i++){ if(input[i]==0) m=HT[m].lchild; if(input[i]==1) m=HT[m].rchild; if(HT[m].lchild==0){ printf("%c",a[m-1]); m=t; } }}voidview(){ printf("\t\t******************************************\n"); printf("\t\t***哈夫曼編碼/譯碼器***\n"); printf("\t\t******************************************\n"); printf("\t\t***********冀假設(shè)含劉洋蔣佳燁*************\n"); printf("\t\t*B構(gòu)造哈夫曼樹C編碼D譯碼E退出*\n"); printf("\t\t********A清屏F初始化************\n"); printf("\t\t******************************************\n"); printf("\t\t**********必須先構(gòu)建哈夫曼樹**************\n");}intmain(intargc,char**argv){ view(); charlu=''; HuffmanCodeHC; HuffmanTreeHT; char*a;//存放字符 int*w; intn; inti; charinp=''; intinpt=0; charchoice='';//儲存你要選擇的功能選項 a=(char*)malloc((n+2)*sizeof(char)); w=(int*)malloc((n*sizeof(int))); HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode)); HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); while(1) { printf("請選擇你要執(zhí)行的功能\n"); printf(">:"); scanf("%c",&choice); switch(choice){ case'a':case'A': system("cls"); view(); getchar(); break; case'b':case'B': printf("請輸入字符集大小\n"); scanf("%d",&n); printf("請輸入字符名和