第4次实验题目与报告书-网络161-162.doc

淮海工学院计算机科学系实验报告书课程名： 数据结构 题 目： 树型数据结构实验 班 级： 学 号： 姓 名： 评语：成绩： 指导教师： 批阅时间： 年 月 日 数据结构 实验报告 - 7 -树型数据结构实验报告要求1目的与要求:1）熟练掌握Huffman树的创建算法与编程实现；2）熟练掌握Huffman编码算法的实现与编程应用；3）创建较为实用的通信报文Huffman编码系统和译码系统;4）本次实验为数据结构应用的一次重要实验，同学们应按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；5）认真书写实验报告,并于11周周五前提交实验报告。2 实验内容或题目实验四：树型数据结构实验创建通信报文编码与译码系统构造通信报文编码和译码系统（要求Huffman编码与译码）。条件：1、使用英文报文实施加密通信。设组成报文的字符集为26个英文字母（不分大小写）和两个标点符号字符“,”、“.”和一个空格字符（共29个字符）。2、字符集中每个字符（含字母和两个标点符号）的使用概率自己根据英文行文合理给出（可以在网上查询）。3、以字符集中各个字符为叶结点、字符的使用频率为权重构造Huffman树，并求得各个字符的Huffman编码（参考教材P152-153教材算法6.16)。同时，输出构造的Huffman树和字符编码结果。4、在上述通信报文编码和译码系统中实现：输入一报文原文（即使用英文书写的一段文字或一两句话，称为明文），给出要发送的报文编码（密文）；再输入一密文（0、1序列），输出其对应的译码报文（明文）。其中报文原文或编码序列自己设定，尽量是一句话或一段文字的对应编码序列，这样可以验证输出结果的正确性。5、本次实验程序给出创建哈弗曼和哈弗曼编码的源程序，调试运行并实验本次实验的全部功能。3 实验步骤与源程序 （学生自己填写）4 测试数据与实验结果（可以抓图粘贴） （学生自己填写）5 结果分析与实验体会 （学生自己填写）2. 版面格式：（1）各级标题：黑体，小四，段前/段后：6磅（2）正文内容：宋体、五号，行间距1.25倍；（3）程序代码：宋体、五号，单倍行间距； （4）A4纸，上、下、左、右边距：2厘米注：蓝色字体部分为注释，正式报告中将其删除。哈夫曼编码算法#include #include #include typedef char* HuffmanCode;/*动态分配数组，存储哈夫曼编码*/typedef struct unsigned int weight ; /* 用来存放各个结点的权值*/unsigned int parent, LChild,RChild ; /*指向双亲、孩子结点的指针*/HTNode, * HuffmanTree; /*动态分配数组，存储哈夫曼树*/void select(HuffmanTree *ht,int n, int *s1, int *s2)int i;int min;for(i=1; i=n; i+)if(*ht)i.parent = 0)min = i;i = n+1;for(i=1; i=n; i+)if(*ht)i.parent = 0)if(*ht)i.weight (*ht)min.weight)min = i;*s1 = min;for(i=1; i=n; i+)if(*ht)i.parent = 0 & i!=(*s1)min = i;i = n+1;for(i=1; i=n; i+)if(*ht)i.parent = 0 & i!=(*s1)if(*ht)i.weight (*ht)min.weight)min = i;*s2 = min;void CrtHuffmanTree(HuffmanTree *ht , int *w, int n) /* w存放已知的n个权值，构造哈夫曼树ht */int m,i;int s1,s2;m=2*n-1;*ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /*0号单元未使用*/for(i=1;i=n;i+) /*1-n号放叶子结点，初始化*/(*ht)i.weight = wi;(*ht)i.LChild = 0;(*ht)i.parent = 0;(*ht)i.RChild = 0;for(i=n+1;i=m;i+)(*ht)i.weight = 0;(*ht)i.LChild = 0;(*ht)i.parent = 0;(*ht)i.RChild = 0; /*非叶子结点初始化*/*-初始化完毕！对应算法步骤1-*/for(i=n+1;i=m;i+) /*创建非叶子结点,建哈夫曼树*/ /*在(*ht)1(*ht)i-1的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回*/select(ht,i-1,&s1,&s2);(*ht)s1.parent=i;(*ht)s2.parent=i;(*ht)i.LChild=s1;(*ht)i.RChild=s2;(*ht)i.weight=(*ht)s1.weight+(*ht)s2.weight; /*哈夫曼树建立完毕*/void outputHuffman(HuffmanTree HT, int m)if(m!=0)printf(%d , HTm.weight);outputHuffman(HT,HTm.LChild);outputHuffman(HT,HTm.RChild);void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n)/*从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/char *cd;int i;unsigned int c;int start;int p;hc=(HuffmanCode *)malloc(n+1)*sizeof(char *); /*分配n个编码的头指针*/cd=(char * )malloc(n * sizeof(char ); /*分配求当前编码的工作空间*/cdn-1=0; /*从右向左逐位存放编码，首先存放编码结束符*/for(i=1;i=n;i+) /*求n个叶子结点对应的哈夫曼编码*/start=n-1; /*初始化编码起始指针*/for(c=i,p=(*ht)i.parent; p!=0; c=p,p=(*ht)p.parent) /*从叶子到根结点求编码*/if( (*ht)p.LChild = c) cd-start=0; /*左分支标0*/else cd-start=1; /*右分支标1*/hci=(char *)malloc(n-start)*sizeof(char); /*为第i个编码分配空间*/strcpy(hci,&cdstart);free(cd);for(i=1;i=n;i+)printf(%d编码为%sn,(*ht)i.weight,hci);void main() HuffmanTree HT; HuffmanCode HC; int *w; int i,n; / the number of elements; int wei; / the weight of a element; int m;printf(input the total number of the Huffman Tree: ); scanf(%d,&n); w=(int *)malloc(n+1)*sizeof(int); for(i=1;i=n;i+) printf(input the %d elements weight:,i); fflush(stdin);scanf(%d,&wei); wi=wei; CrtHuffmanTree(&HT,w,n); m = 2*n-1;outputHuffman(HT,m); printf(n);CrtHuffmanCode(&HT,&HC,n);关键程序段和实现思想一、密文转换为明文scanf(%d,&n);char d30=1,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,., ; /*明文字符*/ double w30=2,8.4966,2.072,4.5388,3.3844,11.16,1.8121,2.4705,3.0034,7.5448,0.1965,1.1016,5.4893,3.0129,6.6544,7.1635,3.1671, 0.1962,7.5809,7.5809,6.9509,3.6308,1.0074,1.2899,0.2902,1.7779,0.2722,7.241,4.021,1.231; /*字符权值*/CrtHuffmanTree(&HT,d,w,n); /*建立哈夫曼树*/m = 2*n-1; / m=57printf(n);CrtHuffmanCode(&HT,&HC,n);printf(n); printf(输入哈夫曼编码:); /*输入密文并转化为明文*/ scanf(%s, p); int j=strlen(p); int t=57; i=1; printf(原文是:); while(i = j) while(HTt.LChild != 0) /因为是完全二叉树，从静态三叉链表哈弗曼树的根结点开始，沿左右子树搜索到叶子结点，此时t所指下标为找到的密文字符，输出即为翻译的字符 if(pi-1 = 0) t = HTt.LChild; i+; continue; if(pi-1= 1) t=HTt.RChild; i+; continue; printf(%c,HTt.data); t = 57; printf(n);二、明文转化为密文（哈弗曼编码）程序段