哈夫曼树与哈夫曼编码.doc

《哈夫曼树与哈夫曼编码.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、7数据结构课程设计哈夫曼树与哈夫曼编码学号：xxx姓名：xxx专业：xxx7【1】任务详细：1．输入一个文本，统计各字符出现的频度，输出结果2．使用字符出现的频度构造哈夫曼树3．确定和输出各字符的哈夫曼码4．输入一个由0和1组成的代码序列，翻译并输出与之对应的文体，若最后的代码子序列不能译为文本，则输出相关信息【2】任务要求：1．掌握哈夫曼树的建树原理2. 掌握哈夫曼树与哈夫曼码逻辑结构和存储结构。3．掌握哈夫曼树与哈夫曼码的基本操作【3】基本思想：在栈的结构体基础上增加哈夫曼树的几个指针，像这样：typedefstructnode{intdata;int

2、weight;structnode*next,*lchild,*rchild,*parent;}node,*pnode;每一个结点新增了几个指针!7借助新增的几个指针和原有的栈，通过切换遍历方式，选择性的使用指针来构建栈和哈夫曼树。当处理栈时，使用传统的next指针,当构建哈夫曼树时使用新增的几个指针。【4】基本函数（关键函数为蓝色注明）voidinit_stack(pstack);//初始化栈voidpush_stack(pstack,char);//压栈voidpop_stack(pstack);//出栈voidtraverse_stack(pstac

3、k);//普通遍历voidtraverse_plus(pstack);//去掉重复的字符voidorder_stack(pstack);//按照权值大小排序，准备构建哈夫曼树voidcreate_HTtree(pstack);//构建哈夫曼树voidget_HTtreecode(pstack);//获取哈夫曼编码voiddecode(pstack);//解密哈弗慢编码【5】关键函数解读inttraverse_plus(pstackps)用户输入用于构建哈夫曼树的原数据是一串乱码，构建哈夫曼树之前需要处理删除重复的并且排好序便于构建哈夫曼树首先建立两个指针，

4、外指针循环用于统计一共有多少个不同的字符，内指针用于删除重复的字符并且得到每个字符出现的频度然后赋值给每一个结点的weight7{pnodep1=ps->top;pnodep2=p1->next;intsum=0;//用于统计一共有多少个不同的字符，创建哈夫曼树的重要步骤；while(p1){while(p2){if(p1->data==p2->data){p1->weight=p1->weight+1;//出现一次，权值加一pnodep3=p2;//将重复出现的删除p1->next=p2->next;p2=p2->next;free(p3);}else{

5、p2=p2->next;//字符不同仅指针后移}printf("%c出现了%d次",p1->data,p1->weight);}sum=sum+1;p1=p1->next;}printf("一共有%d个字符",sum);//这里得到了不同的字符的数量}voidorder_stack(pstackps)用于给结点按照从小到大排序方便建立哈夫曼树，方法用的是冒泡法，并且输出排序好的每个不同的字符的频度{pnodeq1=ps->top;for(inti=0;iweight>q

6、1->next->weight)//交换结点位置，从小到大排序准备建立哈夫曼树{pnodetemp1;//用来找到q前面那个结点便于交换while(temp1->next!=q1){temp1=temp1->next;}pnodetemp2=q1->next;//交换2个节点q1->next=temp2->next;temp1->next=temp2;temp2->next=q1;}}}pnodeq2=ps->top;printf("已排好顺序准备建立哈夫曼树!");while(q2){printf("%c的频度是%d",q2->data,q2->we

7、ight);//小到大顺序输出字符和权值q2=q2->next;}return;}voidcreate_HTtree(pstackps)构建哈夫曼树，主要过程是首先生成一个新节点，从站里面取出第一个和第二个结点，由于在前面的函数中已经排好序，取出来的就是权值最小的和第二小的结点，新节点的权值为取出来的结点的权值之和，同时新节点的左孩子指针指向取出的第一个节点，右孩子指针指向取出的第二个结点，再将取出的结点的*parent指针指向新节点，然后删除取出的两个节点，将新节点加入栈中，循环直到所有节点出栈。每次循环给新的栈排序。7{stacks2=ps;for(i

8、nti=1;i