学步园

#include <stdio.h><br /> #include <stdlib.h><br /> #include <string.h></p> <p>#define M 1000<br /> #define N 128</p> <p>typedef struct node<br /> {<br /> int weight;<br /> struct node *lchild , *rchild , *parent ;<br /> struct node *next;<br /> }HuffmanNode , *HuffmanTree;</p> <p>typedef struct<br /> {<br /> char ch;<br /> char code[N];<br /> }CodeNode;</p> <p>int n;</p> <p>void Open(char s[])<br /> {<br /> FILE *fp;<br /> char name[10];<br /> int i=0;<br /> printf("请输入你要打开的文件名:");<br /> gets(name);<br /> if ((fp = fopen(name,"rt")) == NULL )<br /> {<br /> printf("打开文件失败!/n");<br /> exit(1);<br /> }</p> <p> s[i++] = fgetc(fp);<br /> while(s[i-1] != EOF)<br /> s[i++] = fgetc(fp);<br /> s[i] = '/0';</p> <p> printf("读取到的字符：/n");<br /> puts(s);<br /> fclose(fp);<br /> }</p> <p>void Save(char s[])<br /> {<br /> FILE *fp;<br /> char name[10];<br /> printf("请输入你要保存的文件名：");<br /> gets(name);</p> <p> if ((fp = fopen(name,"wt")) == NULL)<br /> {<br /> printf("保存文件失败!/n");<br /> exit(1);<br /> }</p> <p> fputs(s,fp);<br /> fclose(fp);<br /> }</p> <p>void SearchStr(char s[] , char str[] , int count[])<br /> {<br /> int i , j , k=0;<br /> for (i=0 ; i<N ; i++)<br /> count[i] = 0;<br /> for (i=0 ; s[i] ; i++)<br /> {<br /> for (j=0 ; j<k ; j++)<br /> {<br /> if (str[j] == s[i])<br /> {<br /> count[j]++;<br /> break;<br /> }<br /> }<br /> if (j == k)<br /> {<br /> str[k] = s[i];<br /> count[k]++;<br /> k++;<br /> }</p> <p> }<br /> str[k-1] = '/0';<br /> n = k-1;<br /> }</p> <p>void SelectMin(HuffmanTree HT , int k , HuffmanTree *HT1 , HuffmanTree *HT2)<br /> {<br /> int i , min;<br /> HuffmanTree p;<br /> min = 3128;<br /> for ( p=HT,i=0 ; i<k ; i++,p=p->next)<br /> {<br /> if (p->weight<min && p->parent == NULL)<br /> {<br /> min = p->weight;<br /> *HT1 = p ;<br /> }<br /> }<br /> min = 3128;<br /> for ( p=HT,i=0 ; i<k ; i++,p=p->next)<br /> {<br /> if (p->weight<min && p->parent == NULL && p!=*HT1)<br /> {<br /> min = p->weight;<br /> *HT2 = p ;<br /> }<br /> }<br /> }</p> <p>void CreatHuffmanTree(HuffmanTree *HT , int count[])<br /> {<br /> int i;<br /> HuffmanTree p , HT1 , HT2;<br /> p = *HT = (HuffmanTree)malloc(sizeof(HuffmanNode));<br /> p->next = p->lchild = p->rchild = p->parent = NULL;<br /> for (i=0 ; i<2*n-1 ; i++)<br /> {<br /> p->next = (HuffmanTree)malloc(sizeof(HuffmanNode));<br /> p = p->next;<br /> p->next = p->lchild = p->rchild = p->parent = NULL;<br /> }<br /> for ( p=*HT ,i=0 ; i<n ; i++)<br /> {<br /> p->weight = count[i];<br /> p = p->next;<br /> }<br /> for (i=n ; i<2*n-1 ; i++)<br /> {<br /> SelectMin(*HT,i,&HT1,&HT2);<br /> HT1->parent = HT2->parent = p;<br /> p->lchild = HT1;<br /> p->rchild = HT2;<br /> p->weight = HT1->weight + HT2->weight;<br /> p = p->next;<br /> }<br /> free(p);<br /> }</p> <p>void CodeHuffman(HuffmanTree HT , CodeNode HC[] , char str[])<br /> {<br /> int i , j , k , x;<br /> char ch;<br /> HuffmanTree p , q=HT;<br /> for (i=0 ; i<n ; i++)<br /> HC[i].ch = str[i];</p> <p> for (i=0 ; i<n ; i++)<br /> {<br /> j = 0;<br /> x = 0;<br /> for ( p=q; p->parent ; p=p->parent)<br /> {<br /> if (p == p->parent->lchild)<br /> HC[i].code[j++] = '0';<br /> else<br /> HC[i].code[j++] = '1';<br /> }<br /> HC[i].code[j] = '/0';<br /> k = j/2;<br /> while(j>k) //编码反转<br /> {<br /> ch = HC[i].code[j-1];<br /> HC[i].code[j-1] = HC[i].code[x];<br /> HC[i].code[x] = ch ;<br /> j--;<br /> x++;<br /> }<br /> q = q->next;<br /> }<br /> }</p> <p>void ToltalCoding(CodeNode HC[] , char s[] , char code[])<br /> {<br /> int i , j ;<br /> code[0] = '/0';<br /> for (i=0 ; s[i] ; i++)<br /> {<br /> for (j=0 ; j<n ; j++)<br /> {<br /> if (s[i] == HC[j].ch)<br /> strcpy(code+strlen(code),HC[j].code);<br /> }<br /> }</p> <p>}</p> <p>void Decoding(HuffmanTree HT , char code[] , char str[] , char ss[])<br /> {<br /> int i , j , k=0 ;<br /> HuffmanTree p , q , root;<br /> for (root=HT ; root->parent ; root=root->parent);<br /> for (i=0 , p=root ; code[i] ; i++)<br /> {<br /> if (code[i] == '0')<br /> p = p->lchild;<br /> else<br /> p = p->rchild;<br /> if (p->lchild==NULL && p->rchild==NULL)<br /> {<br /> for (j=0,q=HT ; q!=p ; q=q->next,j++);<br /> ss[k++] = str[j];</p> <p> p = root;<br /> }<br /> }<br /> ss[k] = '/0';<br /> printf("解码结果:/n");<br /> puts(ss);<br /> }</p> <p>void main(void)<br /> {<br /> int i = 0;<br /> // char xuanzhe;<br /> char s[M],ss[M]; //定义字符串数组，s[]存放将要编码的字符串，ss[]存解码后的字符串<br /> char str[N]; //存放输入的字符串中n个不同的字符<br /> int count[N]; //存放n个不同字符对应的在原字符串中出现的次数<br /> char code[M]; //存放最终编码完成后的编码<br /> // char choice;<br /> HuffmanTree HT; //定义一个哈夫曼树的链表<br /> CodeNode HC[N];</p> <p> Open(s);<br /> SearchStr(s,str,count);<br /> CreatHuffmanTree(&HT,count);<br /> CodeHuffman(HT,HC,str);<br /> for ( i=0 ; i<n ; i++ )<br /> printf("字符:%c/t权值:%d/t编码:%s/n",str[i],count[i],HC[i].code);<br /> ToltalCoding(HC,s,code);<br /> Decoding(HT,code,str,ss);<br /> free(HT);<br /> }<br />