吴亚峰第二次作业.doc

一、设计思想 首先构建哈夫曼树，再去进行哈夫曼的译码，接着设计函数进行字符串的编码过程，最后进行哈夫曼编码的译码。 定义一个结构体，用于存放构建哈夫曼树所需要的所有变量，开辟一块地址空间，用于存放数组，数组中每个元素为之前定义的结构体。输入n个字符及其权值。 构建哈夫曼树：在上述存储结构上实现的哈夫曼算法可大致描述为： 初始化 将[ ]中2n-1个结点里的三个指针均置为空，权值置为0。 输 读n个叶子的权值存于向量的前n个分量中。它们是初始森林中n个孤立的根结点上的权值。 合并 对森林中的树共进行n-1次合并，所产生的新结点依次放向量的第i个分量中。每次合并分两步： 在当前森林[0．．i-1]的所有结点中，选取权最小和次小的两个根结点[1]和 [2]作为合并对象，这里0≤1，2≤i-1。 将根为[s1]和[s2]的两棵树作为左右子树合并为一棵新的树，新树的根是新结点[i]。具体操作： 将[s1]和[s2]的parent置为i，将[i]的lchild和rchild分别置为1和2 。新结点[i]的权值置为[s1]和[s2]的权值之和。 图1 哈夫曼编码流程图 图2 哈夫曼解码流程图 三、源代码 #include stdio.h #include string.h /* 数组头文件 */ #includeconio.h #define MAX 999 /* 定义长度 */ typedef struct{ /* 定义哈夫曼编码的结构数组 */ char data; int weight; /* 定义权值 */ int parent; int lchild; int rchild; }huffmannode; typedef struct{ /* 定义保存哈夫曼结构体 */ char bits[50]; int start; }huffmancode ; void main() { huffmannode ht[100]; /* 定义储存权值的空间 */ huffmancode cd[100]; char string[100]; /* 定义数组存储空间 */ char hcd[100]; int i,j,x,y,s1,s2,m1,m2,n,c,f,k; printf(please input the n=); /* 输入字符的个数 */ scanf(%d,n); printf(\n===============================\n); for(i=0;in;i++) { getchar(); /* 获得输入的字符 */ printf(please input the value :); scanf(%c,ht[i].data); /* 输入字符函数 */ printf(please input the weight:); scanf(%d,ht[i].weight); } printf(\n=============================\n); for(i=0;i2*n-1;i++) { ht[i].parent=ht[i].lchild=ht[i].rchild=-1; /* 初始化父结点，左右子结点 */ } for (i=n;i2*n-1;i++) { s1=s2=0; /* 初始化变量 */ m1=m2=MAX; for (j=0;ji;j++) { if (ht[j].weightm1 ht[j].parent==-1) /* 寻找无父结点的最小值 */ { m2=m1; s2=s1; m1=ht[j].weight; s1=j; /* 寻找当前最小值 */ } else if(ht[j].weightm2 ht[j].parent==-1) /* 寻找无父结点的次小