赫夫曼編碼的編碼與譯碼課程設(shè)計(jì)

1、赫夫曼編碼的編碼與譯碼課程設(shè)計(jì)下面有一個(gè)通用赫夫曼譯碼器,與赫夫曼編碼與譯碼的和兩個(gè)附件.程序本人都調(diào)試過(guò)正解無(wú)語(yǔ),如對(duì)赫夫曼編碼還有其它問(wèn)題請(qǐng)聯(lián)系我.QQ:156148347  本人絕對(duì)是自己編寫(xiě),如轉(zhuǎn)其它地方請(qǐng)注明轉(zhuǎn):無(wú)憂小子.謝謝,這可是我2個(gè)星期的結(jié)晶呵呵  覺(jué)得簡(jiǎn)單了，恰好我今天建了一棵哈樹(shù)，實(shí)現(xiàn)了哈編碼。方法：打開(kāi)文件，按字符讀入，用數(shù)組統(tǒng)計(jì)每個(gè)字母的出現(xiàn)的次數(shù) 作為權(quán)值，再利用該數(shù)組內(nèi)容作為輸入創(chuàng)建哈夫曼樹(shù)，然后利用棧先根遍歷該樹(shù)，進(jìn)入左子樹(shù)棧壓0，右子樹(shù)壓1，到達(dá)葉節(jié)點(diǎn)時(shí)從棧底至棧頂輸入棧內(nèi)容，即為哈編碼。三、 實(shí)驗(yàn)要求：根據(jù)設(shè)計(jì)

2、要求和分析，要實(shí)現(xiàn)本設(shè)計(jì)，必須實(shí)現(xiàn)以下幾個(gè)方面的功能：（1） 赫夫曼樹(shù)的建立；（2） 赫夫曼編碼的生成；（3） 編碼文件的譯碼。要實(shí)現(xiàn)赫夫曼樹(shù)算法，首先要實(shí)現(xiàn)在HT1.k中選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)的選擇算法；另外，還要有一個(gè)實(shí)現(xiàn)統(tǒng)計(jì)輸入電文字符串（str）中各種字符出現(xiàn)的頻率以及字符的種類(lèi)的算法。具體要求統(tǒng)計(jì)一段文字str（只有大寫(xiě)字符或者全為小寫(xiě)字符）中出現(xiàn)的字符種類(lèi)k，并統(tǒng)計(jì)顯示每個(gè)字符出現(xiàn)的次數(shù)。然后要求以上面的統(tǒng)計(jì)結(jié)果求出這些字符（k個(gè)）對(duì)應(yīng)的赫夫曼編碼，將其寫(xiě)入一個(gè)文件A，然后再對(duì)輸入的文字str進(jìn)行編碼，將生成的編碼寫(xiě)入另一個(gè)文件B。然后再對(duì)B進(jìn)行譯碼，并將最終的

3、結(jié)果直接顯示出來(lái)。#include <stdio.h>struct string /*該結(jié)構(gòu)體用于字符統(tǒng)計(jì)時(shí)*/char type2; /*定義字符數(shù)組，以存放字符碼表*/int apper; /*該表達(dá)出現(xiàn)了多少次*/a_z26,what26; /*定義兩個(gè)結(jié)構(gòu)變量*/typedef struct unsigned int weight ; /結(jié)點(diǎn)權(quán)值unsigned int parent,lchild,rchild;/結(jié)點(diǎn)的父指針，左右孩子指針HTNode,*HuffmanTree; /動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹(shù)typedef char *HuffmanCode ; /動(dòng)態(tài)分配數(shù)

4、組存儲(chǔ)哈夫曼編碼表/*在HT1.t中選擇parent不為0且權(quán)值最小的兩個(gè)結(jié)點(diǎn)，其序號(hào)分別為s1和s2*/void Select(HuffmanTree *HT,int *s1,int *s2,int limit)int i,m,n;m=n=10000;for(i=1;i<=limit-1;i+) if( (*HT).parent=0) &&( (*HT).weight<m | (*(*HT)+i).weight<n )if(m<n)n=(*(*HT)+i).weight ;(*s2)=i ;elsem=(*(*HT)+i).weight ;(*s1)=

5、i ;if( (*s1) > (*s2) ) i=(*s1);(*s1)=(*s2);(*s2)=i;/*構(gòu)建啥夫曼樹(shù),并且使用指針w引用主函數(shù)的權(quán)值*/void CreateHuffmanTree(HuffmanTree *HT,unsigned int *w,int n) /*定義HT為二級(jí)指針,使傳過(guò)來(lái)的值具有雙向性,w存放結(jié)點(diǎn)的權(quán)值,n為結(jié)點(diǎn)數(shù)*/int i,m,s1,s2;HuffmanTree p;m=2*n-1;*HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/*動(dòng)態(tài)申請(qǐng)空間，相當(dāng)于申請(qǐng)數(shù)組*/for(p=*HT+1,i=1;i<

6、;=n;i+,p+)(*p).weight=wi-1;/*給結(jié)點(diǎn)賦權(quán)值*/(*p).parent=(*p).lchild=(*p).rchild=0;/*初始化時(shí),雙親和孩子結(jié)點(diǎn)都為0*/for(;i<=m;i+,p+)(*p).weight=(*p).parent=(*p).lchild=(*p).rchild=0;for(i=n+1;i<=m;i+) /*為第剩下結(jié)點(diǎn)分配孩子結(jié)點(diǎn)，并且賦權(quán)值給其結(jié)點(diǎn)*/Select(HT,&s1,&s2,i); /*調(diào)用選擇輸入小結(jié)點(diǎn)的函數(shù)*/(*HT)s1.parent=(*HT)+s2)->parent=i;/*這行語(yǔ)

7、句及以下幾句為指針與數(shù)組的等介形式*/(*(*HT)+i).lchild=s1;(*(*HT)+i).rchild=s2;(*(*HT)+i).weight=(*(*HT)+s1).weight+(*(*HT)+s2).weight;void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int n)/*定義三級(jí)指針HC*/int i,start,c,f;char *cd;(*HC)=(HuffmanCode) malloc( (n+1)*sizeof(char *) ); /*為主函數(shù)中的二級(jí)指針?lè)峙鋬?nèi)存空間*/cd=(char *)malloc

8、(n*sizeof(char);/*為字符指針cd分配內(nèi)存,相當(dāng)于定義數(shù)組*/cdn-1='0'for(i=1;i<=n;i+)start=n-1;for(c=i,f=(*HT).parent;f!=0;c=f,f=(*HT)f.parent)/*循環(huán)為結(jié)點(diǎn)編碼*/if(*HT)f.lchild=c) /*當(dāng)其為左孩子時(shí)，為0*/cd-start='0'elsecd-start='1'(*(*HC)+i)=(char *)malloc(n-start)*sizeof(char);/*申請(qǐng)空間以存放結(jié)點(diǎn)編碼*/strcpy( (*(*HC)+

9、i) ,&cdstart); /*將編碼拷貝到HCn中*/free(cd); /*釋放cd指向的空間*/Wordcout(int *k,char str) /*該函數(shù)作用是字符統(tǒng)計(jì)*/int i,j,add=65;if(str0>='a'&&str0<='z')add=add+32; /*當(dāng)所以輸入字符為小與時(shí)，增加增量*/for(i=0;i<=25;i+) a_z.type0=add+i; a_z.apper=0; /*生成字符表，以知道出現(xiàn)過(guò)哪些字符*/for(i=0;i<=25;i+)for(j=0;j<

10、;strlen(str);j+)if(a_z.type0=strj)(a_z.apper)+; /*統(tǒng)計(jì)主函數(shù)傳過(guò)來(lái)的str數(shù)組的字符出現(xiàn)次數(shù)*/for(i=0,j=0;i<=25;i+)if(a_z.apper!=0) /*將出現(xiàn)過(guò)的字符數(shù)型有序的存入whatn數(shù)組中*/(*k)+;whatj.type0=a_z.type0;whatj.apper=a_z.apper;j+;main() FILE *fp;HuffmanTree HT ; /*定義HT為指針型*/HuffmanCode HC ; /*定義HC為二級(jí)字符指針型*/int n=0,i,j;/*定義整型變量,并做相應(yīng)初始化*

11、/unsigned int *w;/*定義無(wú)符號(hào)指針型/char str255;/*定義數(shù)組*/clrscr();if(fp=fopen("A.txt","w")=NULL) /*新建A.txt,此處也可以隨便指定文件名，以表方便，此處用A.txt*/printf("can't creat file");exit(0);printf("nPlease Input char:");gets(str);/*接收鍵盤(pán)上輸入的全大寫(xiě)或全小寫(xiě)字符*/Wordcout(&n,str); /*調(diào)用字符統(tǒng)計(jì)函數(shù)，以

12、得到各種類(lèi)型字符出現(xiàn)的值數(shù)（權(quán)值）*/if(n<=1) printf("nplease Input the available character");getchar();exit(0);w=(unsigned int *)malloc(2*n-1)*sizeof(unsigned int);/*指明W指針的指向,其相當(dāng)于申請(qǐng)數(shù)組*/for(i=0;i<n;i+)w=what.apper; /*循環(huán)輸入權(quán)值至W中*/CreateHuffmanTree(&HT,w,n); /*調(diào)用構(gòu)建赫夫曼樹(shù)的函數(shù)*/HuffmanCoding(&HT,&

13、HC,n); /*為n個(gè)結(jié)點(diǎn)編碼*/for(i=1;i<=n;i+) fputs(whati-1.type,fp); /*將出現(xiàn)的字符有序的寫(xiě)入文件A.TXT中*/fputs( (*(HC+i),fp );fputs("n",fp); /*與時(shí)同時(shí)在每行添加回車(chē)符，以便換行*/fclose(fp); /*關(guān)閉打開(kāi)的fp文件*/if(fp=fopen("B.txt","w")=NULL) /*打開(kāi)B.txt文件*/printf("can't creat file");exit(0);for(i=0;i&

14、lt;strlen(str);i+)for(j=0;j<n;j+)if(str=whatj.type0)fputs( HCj+1,fp); /*將字符str編碼并存入B.txt文件中*/fclose(fp); /*關(guān)閉打開(kāi)的fp指向的文件*/getchar(); /*暫停一下，并以任意鍵退出，此處以便查看輸入的鍵值*/ 譯碼程序：/*This C.Program is write by hw*/#include <stdio.h>main()FILE *fp1,*fp2;int i,j,k,row=0,sum;char str21024,*point26;clrscr();if( (fp1=fopen("A.txt","r")=NULL)printf("Can't open file!");exit(0);if( (fp2=fopen("B.txt","r")=NULL)printf("Can't open file!");exit(0);fgets(str2,1024,fp2);while( !feof(fp1) ) pointrow=(char *)malloc(128*sizeof(char);fgets( point