哈夫曼编译码器-数据结构报告.源代码(源码).doc

哈夫曼编译器 班级号名 ：葛俊峰 需求分析 根据输入的字符和字符的权值建立哈夫曼树。 字符的数目和字符的权值由用户自己设定。 根据建立的哈夫曼树进行，编码和译码操作。 概要设计 哈夫曼树的定义 typedef struct{ char letter; //存储字符 int weight; //存储字符的权值 int parent; //父亲 int lchild; //左孩子 int rchild; //右孩子 }HTNode,*HuffmanTree; 算定义的存储结构 //本结构存储哈夫曼树、编码等，便于后面的操作进行 typedef struct { HuffmanTree HT; //动态分配数组存储哈夫曼编码表 HuffmanCode HC; //记录输入字符的长度，编码和译码用到 int len; char *c;//存储输入的字符 }Huf; 一些操作函数 void setHuffmanTree(HuffmanTree HT,char *str,int *w,int n) 建立哈夫曼树，str是存储输入字符的数组，w 是存储字符权值的数组，n为输入字符的数目 Huf setHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n,char *s) 为哈夫曼树编码，HT是已经建立的哈夫曼树，HC用于存储编码，民为字符的数目，s是存储字符的数组 Huf Initialization() 初始化函数 void Encoding(Huf huf) 编码函数 void Decoding(Huf huf) 译码函数 void Print() 打印代码文件的函数 void Treeprinting(Huf huf) 打印哈夫曼树的函数 主函数 void main(){ 根据不同的选择，执行特定的函数，完成操作 } 详细设计 建立哈夫曼树及求哈夫曼编码 //初始化操作，接受输入，调用函数setHuffmanTree，//setHuffmanCode创建树并编码 Huf Initialization(){ HuffmanTree HT; HuffmanCode HC; char c[100];//存放输入的字符 int w[100];//存放字符的权值 int n; cout请输入字符的个数：endl; cinn; cout请输入所有字符：endl; gets(c); for(int i=1;i=n;i++){ cout请输入第i个字符的权值：endl; cinw[i]; } //将数组c中的元素向右移动一位 for(int j=n-1;j=0;j--) { c[j+1]=c[j]; } // 调用setHuffmanTree函数 setHuffmanTree(HT,c,w,n); //调用setHuffmanCode函数 Huf huf=setHuffmanCode(HT,HC,n,c); return huf; } //选择权值最小的两个结点 void Select(HuffmanTree HT,int s,int s1,int s2){ int j, k, i; j=k=10000; s1=s2=0; for(i=1;i=s;i++){ if(HT[i].parent==0){ if(HT[i].weightj){ k=j;s2=s1; j=HT[i].weight; s1=i; } else if(HT[i].weightk){ k=HT[i].weight; s2=i; } } } } //创建哈夫曼树函数的具体实现 void setHuffmanTree(HuffmanTree HT,char *str,int *w,int n) { HuffmanTree p; int m,i,s1,s2; //s1,s2是权值最小的两个结点的序号 m = 2*n-1; //一棵有N个叶子节点的哈夫曼树共有2*N-1个结点 //动态定义长度，0号单元未使用 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //初始化 for(p=HT+1,i=1;i=n;++i,++p){ p-letter = str[i]; p-weight = w[i]; (*p).parent = 0; p-lchild = 0; p-rchild = 0; } fo