数据结构上机实验树和二叉树的应用哈夫曼编码设计(含代码和报告).doc

数据结构实验报告题目：数据结构实验报告学院：工商管理学院班级：信息1001姓名：彭振宇学号：20100594时间：2012/6/26实验三：树和二叉树的应用一 实验题目：树和二叉树的应用二 实验内容：哈夫曼编码设计三实验目的：掌握树和二叉树的概念及工作原理，运用其原理及概念完成上述实验题中的内容。四实验要求：为了使学生更好的掌握与理解课堂上老师所讲的概念与原理，实验前每个学生要认真预习所做的实验内容及编写源程序伪码（写在纸上及盘中均可）以便在实验课中完成老师所布置的实验内容。五概要设计原理：1.选择parent为0且weight最小的两个结点。其序号分别为s1和s22.建立赫夫曼树叶3.从叶子到根逆向求每个字符的赫夫曼编码4.输出构造的树5.输出得到的各权Huffman编码六详细程序清单及注释说明：#include#include#include#define MAXSIZE 30 /最大叶子数#define MAXCODE 10000 /编码最大长度#define OK 1#define ERROR 0#define OVERLOW -2/=赫夫曼树和赫夫曼编码的存储表示=typedef struct unsigned int weight; unsigned int parent, lchild, rchild;HTNode,*HuffmanTree; /动态分配数组存储赫夫曼树typedef char *HuffmanCode; /动态分配数组存储赫夫曼编码表 /*-算法描述-*/void Select(HuffmanTree HT, int n, int *s1, int *s2)/选择parent为0且weight最小的两个结点。其序号分别为s1和s2 int minsum = 1000000; int i,j; for(i=1; i=n; i+) if(HTi.parent) continue; for(j=i+1; j=n; j+) if(HTj.parent) continue; if(HTi.weight + HTj.weight minsum) minsum = HTi.weight + HTj.weight; *s1 = i; *s2 = j; void CreateHuffmanTree(HuffmanTree &HT, int *w, int n)/建立赫夫曼树叶 int m, s1, s2, i; if(n = 1) return; m = 2*n-1; HT = (HuffmanTree)malloc(m+1) * sizeof(HTNode); for( i = 1; i = n; i+, +w) HTi.weight = *w; HTi.parent = 0; HTi.lchild = 0; HTi.rchild = 0; for( ;i = m; +i) HTi.weight = 0; HTi.parent = 0; HTi.lchild = 0; HTi.rchild = 0; for(i = n+1; i = m; i+) /在HT1.i-1选择parent为0且weight最小的两个结点，其序号分别为s1和s2 Select(HT, i-1, &s1, &s2); HTi.weight = HTs1.weight + HTs2.weight; HTi.lchild = s1; HTi.rchild = s2; HTs1.parent = i; HTs2.parent = i; void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n)/从叶子到根逆向求每个字符的赫夫曼编码 int start, f; unsigned int c; int i = 1; char *cd; cd = (char *)malloc(n * sizeof(char); /分配n个字符编码的头指针向量 HC = (HuffmanCode)malloc(sizeof(char *)*(n+1); cdn-1 = 0; for( ; i=n; +i) start = n-1; /初始化编码起始指针 c = i; f = HTi.parent; for(; f; f = HTf.parent) if(HTf.lchild = c) cd-start = 0; else cd-start = 1; c = f; HCi = (char *)malloc(n-start)*sizeof(char); strcpy(HCi,&cdstart); free(cd);void print(HuffmanTree &HT, int i)/输出构造的树 int k; printf(n构造出来的赫夫曼树是:); for(k = 1; k = 2*i -1; +k) printf(n%3d-weight:%3d,parent:%3d,lchild:%3d,rchild:%3d, k,HTk.weight,HTk.rchild,HTk.rchild,HTk.lchild); void printcode(HuffmanTree HT,HuffmanCode HC,int n)/输出得到的各权Huffman编码 int j; printf(得到的各权Huffman编码是:n); for(j=1; j = n; j+) printf(nwieght:%3d Code:%sn,HTj.weight,HCj); void main() int i = 0, *w; HuffmanTree HT; HuffmanCode HC; w = (int *)malloc(MAXSIZE * sizeof(int); printf(请输入每个叶子权值（输入0结束:)n); scanf(%d,&wi); getchar(); for(i = 1; wi-1; i+) scanf(%d, &wi); getchar(); wi-1 = 0; CreateHuffmanTree(HT, w, i-1); p