Ay's Blog@CNSSUESTC

学校的数据结构试验题目二--哈夫曼树编码

终于写完了~~我觉得那个解码编码部分还能优化~~ 
如果有更好的方法欢迎赐教~~呵呵

题目:
009.bmp





解法:
  1 #include <iostream>
  2 #include <windows.h>
  3 #include <tchar.h>
  4 
  5 #define MAXVALUE 0xffff
  6 using namespace std ;
  7 
  8 typedef struct{
  9     char data ;
 10     int value ;
 11     int parent ;
 12     int lchild ;
 13     int rchild ;
 14 } HfmTree;  //哈夫曼树结构 
 15 
 16 typedef struct {
 17     int count ;
 18     char code[10] ;
 19 } HfmCode ,*pHfmCode;   //哈夫曼树编码时储存编码序列结构
 20 
 21 void CreateHfm(HfmTree hfmt[] , int bufcount)  //建立哈夫曼树
 22 {
 23     for( int i = 0 ; i < 2*bufcount-1 ; i++ )
 24     {
 25         hfmt[i].parent = -1 ;
 26         hfmt[i].lchild = -1 ;
 27         hfmt[i].rchild = -1 ;
 28     }
 29 
 30     for( int i = 0 ; i < bufcount-1 ; i ++ )
 31     {
 32         int min1 = MAXVALUE, min2 = MAXVALUE ,tem1 = 0 , tem2 = 0 ;
 33 
 34         for(int j = 0 ; j < bufcount+i ; j++ )    //找出权值最小的2个树
 35         {
 36             if( hfmt[j].parent == -1 && hfmt[j].value < min1 )
 37             {
 38                 min2 = min1 ;
 39                 tem2 = tem1 ;
 40                 min1 = hfmt[j].value ;
 41                 tem1 = j ;
 42             }else if( hfmt[j].parent == -1 && hfmt[j].value < min2)
 43             {
 44                 min2 = hfmt[j].value ;
 45                 tem2 = j ;
 46             }
 47         }
 48         //合并树
 49             hfmt[tem1].parent = bufcount + i ;
 50             hfmt[tem2].parent = bufcount + i ;
 51             hfmt[bufcount+i].lchild   = tem1 ;
 52             hfmt[bufcount+i].rchild   = tem2 ;
 53             hfmt[bufcount+i].value = hfmt[tem1].value + hfmt[tem2].value  ;
 54     }
 55 }
 56     
 57 pHfmCode GetHfmCode(HfmTree hfmt[] , char target , int bufcount)  //根据哈夫曼树编码函数
 58 {
 59     int pos , temp , count = 0 ;
 60     pHfmCode code = new HfmCode ;
 61     code->count = 0 ;
 62 
 63     for( int i = 0 ; i < bufcount ; i++ )
 64     {
 65         if( hfmt[i].data == target )  //找到目标字符在树中位置
 66         {        
 67             pos = i ;
 68             break ;
 69         }
 70     }
 71     
 72     while(1)  //从叶子逆推到根节点,所得的序列倒序就是字符对应的哈夫曼编码
 73     {
 74         temp = hfmt[pos].parent ;
 75         
 76         if(temp == -1)
 77             break ;
 78 
 79         if( hfmt[temp].lchild == pos )
 80             code->code[count++] = 0+'0' ;  //转换成字符串存放
 81         else
 82             code->code[count++] = 1+'0' ;
 83 
 84         pos = temp ;
 85         code->count++ ;
 86     }
 87 
 88     return code ;    
 89 }
 90 
 91 void CodingBuf(char ipbuf[] , HfmTree *hfmt , int bufcount)   //讲得到的字符串进行编码,然后写入文件
 92 {
 93     FILE *codef ;
 94 
 95      codef = _tfopen("codefile.txt" , "w+" ) ;
 96     
 97     while(1)
 98     {
 99         if(*ipbuf == '\0')  //如果字符串遍历结束就跳出循环
100             break ;
101 
102         pHfmCode code = GetHfmCode(hfmt , *ipbuf , bufcount) ; //获得哈夫曼编码
103         
104         for( int i = code->count ; i > 0 ; i-- )  //要倒着打印,应为之前是逆推到树根的,得到的序列也是倒序的
105             fwrite(&code->code[i-1] , sizeof(char) , 1 , codef ) ;
106         
107         ipbuf++ ;
108     }
109 
110     fclose(codef) ;
111 }
112 
113 void DecodingBuf(HfmTree hfmt[] , char codefile[] , int bufcount)  //哈夫曼解码函数
114 {
115         FILE *textf ;
116         textf = _tfopen("textfile.txt" , "w+") ;
117         char decodebuf[100] = { 0 }  , *temp = codefile ;
118         int count = bufcount*2-2  , i = 0;
119 /*
120 根据输入的编码信息,从树根开始向下遍历,
121 只要到叶子的地方就储存叶子数据,然后回到树根继续遍历
122 知道将输入的编码信息遍历完为止
123 */
124         do 
125         {
126             if( hfmt[count].data != 0 )
127             {
128                 decodebuf[i++] = hfmt[count].data ;
129                 count = bufcount*2-2 ;
130             }
131             if( *temp == '0' )
132                 count = hfmt[count].lchild ;
133             else
134                 count = hfmt[count].rchild ;
135         }while( * (temp++) != '\0') ;
136 
137         fwrite(decodebuf , sizeof(char) , 100 , textf ) ;  //解码信息写入文件
138 
139         fclose(textf) ;
140 }
141 
142 
143   
144 int main(void)
145 {
146     FILE *hfmf , *codef ,*textf ;
147     char ipbuf[100] ;
148     int bufcount = 4 ;
149     HfmTree hfmt[19] = {0} ;
150 
151 //----------------------------------------------信息收集部分
152     cout<<"输入终端字符集大小(1-10)"<<endl ;
153     cin>>bufcount ;
154 
155     for(int i = 0 ; i < bufcount ; i++ )
156     {
157     cout<<"请输入终端字符内容:"<<endl ;
158     cin>>hfmt[i].data ;
159     cout<<"请输入终端字符权值:(0-9)"<<endl ;
160     cin>>hfmt[i].value ;
161     }
162 
163 
164 //-----------------------------------------------建哈夫曼树部分
165     CreateHfm(hfmt ,bufcount ) ;
166 
167     //打印哈夫曼树
168     for(int i = 0 ; i < bufcount*2-1 ; i++)
169     {
170         cout<<"id"<<'\t'<<"data"<<'\t'<<"parent"<<'\t'<<"lchild"<<'\t'<<"rchild"<<'\t'<<"value"<<endl ;
171         cout<<i<<'\t'<<hfmt[i].data<<'\t'<<hfmt[i].parent<<'\t'<<hfmt[i].lchild<<'\t'<<hfmt[i].rchild<<'\t'<<hfmt[i].value<<endl ;
172     }
173 
174     hfmf = _tfopen("hfmtree.txt" , "w+" ) ;
175     
176 
177 
178     char tittle[]="id    data    parent    lchild    rchild    values" ;
179     tittle[strlen(tittle)] = '\n' ;
180     fwrite(tittle , sizeof(char) , sizeof(tittle) , hfmf ) ;
181     char data[1000] ={0},*buf = data  , intbuf[10] ={ 0 };
182     for(int i = 0 ; i < bufcount*2-1 ; i++)
183     {
184         _itoa(i ,  intbuf , 10 ) ;
185         memcpy(buf ,  intbuf , strlen(intbuf)*sizeof(char) ) ;
186         buf += strlen(intbuf) ; 
187         *buf = '\t'; buf++ ;
188         *buf = hfmt[i].data ; buf++ ;
189         *buf = '\t'; buf++ ;
190         
191         _itoa(hfmt[i].parent ,  intbuf , 10 ) ;
192         memcpy(buf ,  intbuf , strlen(intbuf)*sizeof(char) ) ;
193         buf += strlen(intbuf) ;
194         *buf = '\t'; buf++ ;
195 
196         _itoa(hfmt[i].lchild ,  intbuf , 10 ) ;
197         memcpy(buf ,  intbuf , strlen(intbuf)*sizeof(char) ) ;
198         buf += strlen(intbuf) ;
199         *buf = '\t'; buf++ ;
200         
201         _itoa(hfmt[i].rchild ,  intbuf , 10 ) ;
202         memcpy(buf ,  intbuf , strlen(intbuf)*sizeof(char) ) ;
203         buf += strlen(intbuf) ;
204         *buf = '\t'; buf++ ;
205 
206         _itoa(hfmt[i].value ,  intbuf , 10 ) ;
207         memcpy(buf ,  intbuf , strlen(intbuf)*sizeof(char) ) ;
208         buf += strlen(intbuf) ;
209         *buf = '\n'; buf++ ;
210 
211     }
212     fwrite(data , sizeof(char) , 1000 , hfmf );
213     
214     cout<<buf<<endl ;
215 //-----------------------------------------------编码部分
216     cout<<"输入要编码的字符串"<<endl ;
217     cin>>ipbuf ;
218 
219     CodingBuf(ipbuf , hfmt , bufcount ) ;
220     
221     codef = _tfopen("codefile.txt" , "r+") ;
222     char codefile[100] = {0};
223 
224     fread(codefile , sizeof(char) , 100 , codef) ;
225     
226     cout<<"编码结果"<<endl ;
227     cout<<codefile<<endl ;
228 
229     system("pause") ;
230 //-----------------------------------------------解码部分
231     cout<<"解码ING"<<endl ;
232     DecodingBuf(hfmt , codefile , bufcount ) ;
233 
234     cout<<"解码结果:"<<endl  ;
235     textf = _tfopen("textfile.txt" , "r+" ) ;
236     memset(codefile , 0 , 100) ;
237 
238     fread(codefile , sizeof(char) , 100 , textf ) ;
239 
240     cout<<codefile<<endl ;
241     
242     system("pause") ;
243 
244 
245 
246     fclose( textf ) ;
247     fclose( hfmf ) ;
248     fclose(codef) ;
249     return 1;
250 
251 }
252 
253 
254 


posted on 2008-12-09 14:42 __ay 阅读(1060) 评论(0)  编辑 收藏 引用 所属分类: 算法 && C/C++


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理