哈夫曼編碼譯碼器

參考文獻[1]嚴蔚敏.數(shù)據(jù)結構(C語言版).清華大學出版社，2007[2]譚浩強.C語言程序設計教程.高等教育出版社，2006[3]蘇仕華.數(shù)據(jù)結構課程設計.機械工業(yè)出版社，2007沈陽航空航天大學課程設計報告附錄源程序如下：#include<iostream.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#include<fstream.h>typedefstruct{//赫夫曼樹的結構體 charch; intweight;//權值 intparent,lchild,rchild;}Htnode,*Hfmtree;//動態(tài)分配數(shù)組存儲赫夫曼樹typedefchar**Hfmcode;//動態(tài)分配數(shù)組存儲赫夫曼編碼表voidSelect(Hfmtree&HT,inta,int*s1,int*s2)//Select函數(shù)，選出HT樹到a為止，權值最小且parent為0的2個節(jié)點{ inti,j,x,y; for(j=1;j<=a;++j){ if(HT[j].parent==0){ x=j; break; } } for(i=j+1;i<=a;++i){ if(HT[i].weight<HT[x].weight&&HT[i].parent==0){ x=i;//選出最小的節(jié)點 } } for(j=1;j<=a;++j) { if(HT[j].parent==0&&x!=j) { y=j; break; } } for(i=j+1;i<=a;++i) { if(HT[i].weight<HT[y].weight&&HT[i].parent==0&&x!=i) { y=i;//選出次小的節(jié)點 } } if(x>y){ *s1=y; *s2=x; } else { *s1=x; *s2=y; }}voidHfmcoding(Hfmtree&HT,Hfmcode&HC,intn)//構建赫夫曼樹HT，并求出n個字符的赫夫曼編碼HC{ inti,start,c,f,m,w; intp1,p2; char*cd,z; if(n<=1){ return; } m=2*n-1; HT=(Hfmtree)malloc((m+1)*sizeof(Htnode)); for(i=1;i<=n;++i)//初始化n個葉子結點 { printf("請輸入第%d字符信息和權值：",i); scanf("%c%d",&z,&w); while(getchar()!='\n') { continue; } HT[i].ch=z; HT[i].weight=w; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for(;i<=m;++i)//初始化其余的結點 { HT[i].ch='0'; HT[i].weight=0; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for(i=n+1;i<=m;++i)//建立赫夫曼樹 { Select(HT,i-1,&p1,&p2); HT[p1].parent=i; HT[p2].parent=i; HT[i].lchild=p1; HT[i].rchild=p2; HT[i].weight=HT[p1].weight+HT[p2].weight; } HC=(Hfmcode)malloc((n+1)*sizeof(char*)); 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'; } else { cd[--start]='1'; } } HC[i]=(char*)malloc((n-start)*sizeof(char));//為地i個字符編碼分配空間 strcpy(HC[i],&cd[start]); } free(cd);}voidmain(){ charcode[100],h[100],hl[100]; intn,i,j,k,l; ifstreaminput_file;//文件輸入輸出流 ofstreamoutput_file; charchoice,str[100]; HfmtreeHT; HfmcodeHC; while(choice!='4')//當choice的值4時循環(huán) {printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"); printf("*************************赫夫曼編碼/譯碼器*************************\n"); printf("*************************1創(chuàng)建哈夫曼樹*************************\n"); printf("*************************2編碼*************************\n"); printf("*************************3譯碼*************************\n"); printf("*************************4退出*************************\n"); printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"); printf("請輸入您要操作的步驟"); cin>>choice; if(choice=='1')//初始化赫夫曼樹 { cout<<"請輸入字符個數(shù)："; cin>>n; Hfmcoding(HT,HC,n); for(i=1;i<=n;++i) { cout<<HT[i].ch<<":"<<HC[i]<<endl; } output_file.open("hfmTree.txt"); if(!output_file){ cout<<"can'toenfile!"<<endl; } for(i=1;i<=n;i++) { output_file<<"("<<HT[i].ch<<HC[i]<<")"; } output_file.close(); printf("赫夫曼樹已經(jīng)創(chuàng)建完畢，并且已經(jīng)放入hfmTree.txt文件中!\n"); } elseif(choice=='2')//進行編碼，并將字符放入A.txt，碼值放入B.txt中 { printf("請輸入字符："); gets(str); output_file.open("A.txt"); if(!output_file) { cout<<"can'toenfile!"<<endl; } output_file<<str<<endl; output_file.close(); output_file.open("B.txt"); if(!output_file){ cout<<"can'toenfile!"<<endl; } for(i=0;i<strlen(str);i++){ for(j=0;j<=n;++j) { if(HT[j].ch==str[i]) { output_file<<HC[j]; break; } } } output_file.close(); cout<<"\n"; printf("編碼完畢，并且已經(jīng)存入B.txt文件！\n"); input_file.open("B.txt");//從B.txt中讀入編碼，輸出在終端 if(!input_file) { cout<<"can'toenfile!"<<endl; } input_file>>code; cout<<"編碼碼值為："<<code<<endl; input_file.close(); } elseif(choice=='3')//讀入B.txt中的編碼進行譯碼，將譯出來的字符放入Textfile.txt中 { input_file.open("B.txt"); if(!input_file){ cout<<"can'toenfile!"<<endl; } input_file>>h; input_file.close(); output_file.open("Textfile.txt"); if(!output_file) { cout<<"can'toenfile!"<<endl; } k=0; while(h[k]!='\0')//先用編碼中的前幾個和字符的編碼相比較，然后往后移 { for(i=1;i<=n;i++){ l=k; for(j=0;j<strlen(HC[i]);j++,l++){ hl[j]=h[l]; } hl[j]='\0'; if(strcmp(HC[i],hl)==0) { output_file<<HT[i].ch; k=k+strlen(HC[i]); break; } } } output_file.close(); input_file.open("Textfile.txt"); if(!input_file){ cout<<"can'toenfile!"<<endl; } input_file>>h; cout<<h<<endl; input_file.close(); printf("譯碼結束，字符已經(jīng)存入Textfile.txt文件中!\n"); } elseif(choice=='4') { exit(0); } else//如果選了選項之外的就讓用戶重新選擇 { printf("您沒有輸入正確的步驟，請重新輸入！"); } }}沈陽航空航天大學課程設計報告

課程設計總結：通過近兩周的課程設計使我對哈夫曼樹以及哈夫曼編碼譯碼有了更深的認識和理解，也使我更加明白哈夫曼編碼譯碼在信息技術中的重要性和地位。在做課設的過程中我也遇到了很多問題：開始的時候，代碼中有許多的錯誤，特別是有一個“無法找到文件”的錯誤讓我束手無策，最后還是屏蔽了定義的四個頭文件然后慢慢地改正錯誤才讓我又看到了希望。然后在實現(xiàn)文章的讀入時，由于對文件不是太熟悉，只好翻開C語言和C++語言書本仿照其模式編寫，但后來進入了死循環(huán)，最后的解決方式是在main函數(shù)里有一個控制語句使用不正確。我們遇到問題很正常，說明我們掌握的知識還是太少不靈活，并且這些