数据结构 吴亚峰 第二次作业_数据结构第二次作业
数据结构 吴亚峰 第二次作业由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构第二次作业”。
哈夫曼编码与解码的实现
一、设计思想
首先构建哈夫曼树，再去进行哈夫曼的译码，接着设计函数进行字符串的编码过程，最后进行哈夫曼编码的译码。
定义一个结构体，用于存放构建哈夫曼树所需要的所有变量，开辟一块地址空间，用于存放数组，数组中每个元素为之前定义的结构体。输入n个字符及其权值。
构建哈夫曼树：在上述存储结构上实现的哈夫曼算法可大致描述为：
第一步:初始化。将ht[ ]中2n-1个结点里的三个指针均置为空，权值置为0。
第二步:输入。读入n个叶子的权值存于向量的前n个分量中。它们是初始森林中n个孤立的根结点上的权值。
第三步:合并。对森林中的树共进行n-1次合并，所产生的新结点依次放入向量ht的第i个分量中。每次合并分两步： 在当前森林ht[0．．i-1]的所有结点中，选取权最小和次小的两个根结点[s1]和 [s2]作为合并对象，这里0≤s1，s2≤i-1。将根为ht[s1]和ht[s2]的两棵树作为左右子树合并为一棵新的树，新树的根是新结点ht[i]。具体操作：
将ht[s1]和ht[s2]的parent置为i，将ht[i]的lchild和rchild分别置为s1和s2。新结点ht[i]的权值置为ht[s1]和ht[s2]的权值之和。
哈夫曼的编码：约定左子为0，右子为1，则可以从根结点到叶子结点的路径上的字符组成的字符串作为该叶子结点的编码。
当用户输入字母时。就在已经找好编码的编码结构体中去查找该字母。查到该字母就打印所存的哈夫曼编码。接着就是完成用户输入0、1代码时把代码转成字母的功能。这是从树的头结点向下查找，如果当前用户输入的0、1串中是0则就走向该结点的左子。如果是1这就走向该结点的右结点，重复上面步骤。直到发现该结点属于输入了字母的结构体则打印该结构体的字母。重复上面步骤。直到找完用户输入0、1串为止。则就完成了程序所有的译码过程。
哈夫曼编码与解码的实现
三、源代码
#include #include
/* 数组头文件 */ #include #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;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;i
{
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;/* 初始化父结点，左右子结点 */
}
for(i=n;i
{
s1=s2=0;
/* 初始化变量 */
m1=m2=MAX;
哈夫曼编码与解码的实现
}
printf(“n=============================n”);
printf(“nPlease input the meage:n”);
scanf(“%s”,string);
/* 输入字符串 */
for(i=0;string[i]!=' ';i++)
{
for(c=0;c
if(string[i]==ht[c].data)/* 寻找与输入字符相匹配的字母 */
{
for(j=cd[c].start;j
printf(“%c”,cd[c].bits[j]);
/* 输出字母代码 */
break;
}
}
printf(“n=============================n”);
printf(“Please input the HuffmanCode:n”);
scanf(“%s”,hcd);
/* 输入0、1代码 */
f=2*n-2;
for(i=0;hcd[i]!=' ';i++)
{
if(hcd[i]=='0')
/* 判断输入为0，寻找左子 */
f=ht[f].lchild;
else if(hcd[i]=='1')
f=ht[f].rchild;
/* 判断输入为1，寻找右子 */
if(f
{
printf(“%c”,ht[f].data);/* 输出字符串 */
f=2*n-2;
}
}
printf(“n”);
getch();} 以上就是全部的源代码
哈夫曼编码与解码的实现
五、遇到的问题及解决
这部分我主要遇到了如下四个问题，其内容与解决方法如下所列： 问题1：怎样构造一棵哈夫曼树
解决方法：通过查阅书籍和资料，我知道构建哈夫曼树有以下几步：
一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始化集合，就是F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。
二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。
四、重复二和三两步，直到集合F中只有一棵二叉树为止。问题2：怎么用哈夫曼树编码
解决方法：编码的结果就是使每一个字符的编码都与另一个字符编码的前一部分不同，不可能出现像a:00,b:001这种情况，这样就不会遇到莫棱两可的情况了。这是由二叉树的特点决定的,编码是由从根结点到一个叶子的路径决定的。不同的叶子对应的这种路径不可能出现像a:00，b:001这种情况。自己画了画二叉树图，就懂了。哈夫曼编码重要作用就是用最少的编码长度表示相同的内容,主要依据“频 率大的编码短,频率小的编码长”。问题3：如何解码的问题
解决方法：在编码时将得到的二进制码依次存入临时数组中，从叶子结点到根节点，记录0和1，每记录一次后移一位。最后就得到了二进制编码，解码时从前到后依次读取，最后就得到了字符串，也就完成了解码。问题4：for语句的使用
解决方法：在这个程序中用到了多个for语句，之前C语言学的不太到位。对for语句不能灵活运用，后来通过查阅书籍以及请教同学才使编程最后得以实现并最终能够运行。
六、心得体会
通过这次课程设计，让我对一个程序的数据结构有更全面更进一步的认识，根据不同的需求，采用不同的数据存储方式，不一定要用栈，二叉树等高级类型，有时用基本的一维数组，只要运用得当，也能达到相同的效果，甚至更佳，就如这次的课程设计，通过用for的多重循环，舍弃多余的循环，提高了程序的运行效率。在编写这个程序的过程中，我复习了之前学的基本语法，哈夫曼树最小路径的求取，哈夫曼编码及译码的应用范围，程序结构算法等一系列的问题它使我对数据结构改变了看法。当然，在这次设计过程中，跟上次一样，也遇到了很多难以解决的问题，通过看书以及请教同学才得到了解决。但是总感觉自己的基础实在是太薄弱了，之前的课程没有认真学习导致现在一个小问题都能纠结很久，这种感觉实在不好受。看着别人都轻松完成，自己却得回去看书，心里不是滋味，以后一定要更加努力更加认真才行啊。
