整理了一下最近做的數據結構上機實習題：

【問題描述】 利用哈夫曼編碼進行信息通訊可以大大提高信道利用率，縮短信息 傳輸時間，降低傳輸成本。但是，這要求在發送端通過一個編碼系統對 待傳數據預先編碼；在接收端將傳來的數據進行譯碼（復原）。對于雙 工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼 系統。試為這樣的信息收發站寫一個哈夫曼碼的編譯碼系統。

【基本要求】 一個完整的系統應具有以下功能： （1）I：初始化（Initialization）。從終端讀入字符集大小n，及n個 字符和n個權值，建立哈夫曼樹，并將它存于文件hfmtree中。 （2）C：編碼（Coding ）。利用已建好的哈夫曼樹（如不在內存， 則從文件hfmtree中讀入），對文件tobetrans中的正文進行編碼，然后 將結果存入文件codefile中。 （3）D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件codefile 中的代碼進行譯碼，結果存入文件textfile中。

（4）P：印代碼文件（Print）。將文件codefile以緊湊格式顯示在終端 上，每行50個代碼。同時將此字符形式的編碼文件寫入文件codeprint中。 （5）T：印哈夫曼樹（Tree printing）。將已在內存中的哈夫曼樹以 直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫 曼樹寫入文件treeprint中。

【測試數據】 （1）已知某系統在通信聯絡中只可能出現八種字符，其頻率分別為 0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設計哈夫曼編碼。 （2）實現以下報文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。

【實現提示】 （1）用戶界面可以設計為“菜單”方式：顯示上述功能符號，再加上 “E”，表示結束運行End，請用戶鍵入一個選擇功能符。此功能執行完畢 后再顯示此菜單，直至某次用戶選擇了“E”為止。 （2）程序的一次執行過程中，第一次執行I、D或C命令之后，哈夫曼 樹已經在內存了，不必再讀入。每次執行中不一定執行I命令，因為文件 hfmtree可能早已建好。

?

haffman.h

1 typedef struct { 2 char data; 3 int weight ; 4 int flag; 5 int parent ; 6 int leftChild ; 7 int rightChild ; 8 }HaffNode ; 9 10 typedef struct { 11 char bit[MaxNode]; 12 int start ; 13 int weight ; 14 char data ; 15 }Code ; 16 17 void Haffman(int weight[],char str[],int n,HaffNode haffTree[]) 18 { 19 int i,j,m1,m2,x1,x2 ; 20 for(i=0;i<2*n-1;i++){ 21 if(i<n) { 22 haffTree[i].weight=weight[i]; 23 haffTree[i].data=str[i]; 24 }else { 25 haffTree[i].weight=0; 26 haffTree[i].data='0'; 27 } 28 haffTree[i].parent=-1; 29 haffTree[i].flag=0; 30 haffTree[i].leftChild=-1; 31 haffTree[i].rightChild=-1; 32 } 33 for(i=0;i<n-1;i++){ 34 m1=m2=MaxValue ; 35 x1=x2=0; 36 for(j=0;j<n+i;j++){ 37 if(haffTree[j].weight<m1&&haffTree[j].flag==0){ 38 m2=m1; 39 x2=x1; 40 m1=haffTree[j].weight; 41 x1=j; 42 }else if(haffTree[j].weight<m2&&haffTree[j].flag==0) 43 { 44 m2=haffTree[j].weight; 45 x2=j ; 46 } 47 } 48 haffTree[x1].parent=n+i; 49 haffTree[x2].parent=n+i; 50 haffTree[x1].flag=haffTree[x2].flag=1; 51 haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight; 52 haffTree[n+i].leftChild=x1; 53 haffTree[n+i].rightChild=x2; 54 } 55 } 56 57 void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[]) 58 { 59 Code *cd=(Code *)malloc(sizeof(Code)); 60 int i,j,child,parent ; 61 for(i=0;i<n;i++){ 62 cd->start=n-1; 63 cd->weight=haffTree[i].weight; 64 cd->data=haffTree[i].data ; 65 child=i; 66 parent=haffTree[child].parent ; 67 while(parent!=-1){ 68 if(haffTree[parent].leftChild==child) 69 cd->bit[cd->start]='0'; 70 else 71 cd->bit[cd->start]='1'; 72 73 cd->start--; 74 child=parent ; 75 parent=haffTree[child].parent; 76 } 77 for(j=cd->start+1;j<n;j++) 78 haffCode[i].bit[j]=cd->bit[j]; 79 haffCode[i].bit[j]='\0'; 80 haffCode[i].start=cd->start+1; 81 haffCode[i].weight=cd->weight; 82 haffCode[i].data=cd->data; 83 } 84 } 1 #include<iostream> 2 #include<iomanip> 3 #include<cstdio> 4 #include<cstdlib> 5 #include<cstring> 6 #include<string> 7 #include<fstream> 8 #define MaxValue 32767 9 #define MaxNode 10000 10 #include"Haffman.h" 11 using namespace std ; 12 13 ifstream input_file ; 14 ofstream output_file ; 15 int n,m=0; 16 HaffNode *myHaffTree=(HaffNode *)malloc(sizeof(HaffNode)*(2*MaxNode-1)); 17 Code *myHaffCode=(Code *)malloc(sizeof(Code)*MaxNode); 18 19 void Initialization(){ 20 char str[MaxNode]; 21 int weight[MaxNode]; 22 cout<<"請輸入字符個數："<<endl; 23 cin>>n; 24 for(int i=0;i<n;i++){ 25 cout<<"請輸入第"<<i+1<<"個字符以及相應的權值"<<endl; 26 cin>>str[i]>>weight[i]; 27 } 28 29 Haffman(weight,str,n,myHaffTree); 30 HaffmanCode(myHaffTree,n,myHaffCode); 31 32 for(int i=0;i<n;i++){ 33 cout<<myHaffCode[i].data<<": "; 34 for(int j=myHaffCode[i].start;j<n;j++){ 35 cout<<myHaffCode[i].bit[j]; 36 } 37 cout<<endl; 38 } 39 40 output_file.open("hfmTree.txt"); 41 if(!output_file){ 42 cout<<"can't open file !"<<endl; 43 return ; 44 } 45 for(int i=0;i<n;i++){ 46 output_file<<"("<<myHaffTree[i].data<<myHaffTree[i].weight<<")"<<endl; 47 } 48 output_file.close(); 49 cout<<"哈夫曼樹已創建完成，并且已放入hfmTree.txt中."<<endl; 50 cout<<endl<<endl; 51 } 52 53 void Coding(){ 54 cout<<"請輸入字符或字符串："<<endl; 55 string str ; 56 string code ; 57 cin>>str; 58 output_file.open("tobetran.txt"); 59 if(!output_file){ 60 cout<<"can't open file !"<<endl; 61 return ; 62 } 63 output_file<<str; 64 output_file.close(); 65 output_file.open("codefile.txt"); 66 if(!output_file){ 67 cout<<"can't open file !"<<endl; 68 return ; 69 } 70 for(int i=0;i<str.size();i++){ 71 for(int j=0;j<n;j++){ 72 if(myHaffTree[j].data==str[i]){ 73 for(int k=myHaffCode[j].start;k<n;k++){ 74 output_file<<myHaffCode[j].bit[k]; 75 } 76 break; 77 } 78 } 79 } 80 output_file.close(); 81 cout<<"編碼完畢，并且已經存入codefile.txt中！"<<endl; 82 input_file.open("codefile.txt"); 83 if(!input_file){ 84 cout<<"can't open file !"<<endl; 85 return ; 86 } 87 input_file>>code; 88 cout<<"編碼碼值為："<<endl; 89 cout<<code<<endl; 90 input_file.close(); 91 cout<<endl<<endl; 92 } 93 94 95 void Decoding(){ 96 char s[MaxNode],s1[MaxNode]; 97 int i,j,k,l,p; 98 input_file.open("codefile.txt"); 99 if(!input_file){ 100 cout<<"can't open file !"<<endl; 101 return ; 102 } 103 input_file>>s; 104 input_file.close(); 105 output_file.open("textfile.txt"); 106 if(!output_file){ 107 cout<<"can't open file !"<<endl; 108 return ; 109 } 110 k=0; 111 while(s[k]!='\0'){ 112 for( i=0;i<n;i++){ 113 l=k; 114 for( j=0;j<strlen(myHaffCode[i].bit)-myHaffCode[i].start;j++,l++){ 115 s1[j]=s[l]; 116 } 117 s1[j]='\0'; 118 for(p=myHaffCode[i].start,j=0;p<n;p++,j++) 119 if(myHaffCode[i].bit[p]!=s1[j]) break; 120 if(p==n){ 121 output_file<<myHaffTree[i].data; 122 k+=strlen(myHaffCode[i].bit)-myHaffCode[i].start; 123 break; 124 } 125 } 126 } 127 output_file.close(); 128 input_file.open("textfile.txt"); 129 if(!input_file){ 130 cout<<"can't open file !"<<endl; 131 return ; 132 } 133 input_file>>s; 134 cout<<s<<endl; 135 input_file.close(); 136 cout<<"譯碼結束，字符已經存入textfile.txt文件中!"<<endl; 137 cout<<endl<<endl; 138 } 139 140 void Print(){ 141 char s[MaxNode],s1[MaxNode]; 142 int i,j,k,l,p; 143 input_file.open("codefile.txt"); 144 if(!input_file){ 145 cout<<"can't open file !"<<endl; 146 return ; 147 } 148 input_file>>s; 149 int icount=0; 150 for(int i=1;i<strlen(s)+1;i++){ 151 cout<<s[i-1]; 152 if(i%50==0) cout<<endl; 153 } 154 cout<<endl; 155 input_file.close(); 156 output_file.open("codeprint.txt"); 157 k=0; 158 while(s[k]!='\0'){ 159 for( i=0;i<n;i++){ 160 l=k; 161 for( j=0;j<strlen(myHaffCode[i].bit)-myHaffCode[i].start;j++,l++){ 162 s1[j]=s[l]; 163 } 164 s1[j]='\0'; 165 for(p=myHaffCode[i].start,j=0;p<n;p++,j++) 166 if(myHaffCode[i].bit[p]!=s1[j]) break; 167 if(p==n){ 168 output_file<<myHaffTree[i].data; 169 k+=strlen(myHaffCode[i].bit)-myHaffCode[i].start; 170 break; 171 } 172 } 173 } 174 output_file.close(); 175 cout<<"字符形式的編碼文件寫入文件codeprint中！"<<endl; 176 cout<<endl<<endl; 177 } 178 179 void TreePrinting(HaffNode *myHaffTree1,HaffNode *myHaffTree2,int m){ 180 if(myHaffTree1!=myHaffTree2-1) 181 { 182 if(m)output_file.close(); 183 output_file.open("treeprint.txt"); 184 if(!output_file){ 185 cout<<"can't open file !"<<endl; 186 return ; 187 } 188 TreePrinting(myHaffTree2+myHaffTree1->rightChild,myHaffTree2,m+1); 189 cout<<setw(4*m)<<myHaffTree1->weight<<endl; 190 output_file<<myHaffTree1->weight<<endl; 191 TreePrinting(myHaffTree2+myHaffTree1->leftChild,myHaffTree2,m+1); 192 output_file.close(); 193 } 194 } 195 196 197 int main(){ 198 char ch ; 199 while(1){ 200 cout<<" *******************哈夫曼編/譯碼器****************"<<endl; 201 cout<<" I---Initialization"<<" C---Coding"<<endl; 202 cout<<" D---Decoding"<<" P---Print"<<endl; 203 cout<<" T---Tree printing"<<" E---Exit"<<endl; 204 cout<<" ------------------------------------------"<<endl; 205 cout<<"please select a function key:"<<endl; 206 cin>>ch; 207 if(ch=='I') 208 Initialization(); 209 else if(ch=='C') 210 Coding(); 211 else if(ch=='D') 212 Decoding(); 213 else if(ch=='P') 214 Print(); 215 else if(ch=='T'){ 216 TreePrinting(myHaffTree+2*n-2,myHaffTree,0); 217 cout<<"此字符形式的哈夫曼樹已寫入文件treeprint中"<<endl; 218 cout<<endl<<endl; 219 } 220 else if(ch=='E') 221 break; 222 else 223 cout<<"The key is not exsit, please select again !"<<endl; 224 } 225 return 0; 226 }

轉載于:https://www.cnblogs.com/wally/archive/2012/11/09/2763120.html

總結

以上是生活随笔為你收集整理的哈夫曼编码器的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。