《第4次实验题目与报告书-网络161-162》由会员分享，可在线阅读，更多相关《第4次实验题目与报告书-网络161-162（8页珍藏版）》请在金锄头文库上搜索。
1、淮海工学院计算机科学系实 验 报 告 书课 程 名 ： 数据结构 题 目： 树型数据结构实验 班 级： 学 号： 姓 名： 评语：成绩： 指导教师： 批阅时间： 年 月 日 数据结构 实验报告 - 1 -树型数据结构实验报告要求1 目的与要求:1）熟练掌握 Huffman 树的创建算法与编程实现；2）熟练掌握 Huffman 编码算法的实现与编程应用；3）创建较为实用的通信报文 Huffman 编码系统和译码系统;4）本次实验为数据结构应用的一次重要实验，同学们应按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果） ；5）认真书写实验报告,并于 11 周周五前提交实验
2、报告。2 实验内容或题目实验四：树型数据结构实验创建通信报文编码与译码系统构造通信报文编码和译码系统（要求 Huffman 编码与译码） 。条件：1、使用英文报文实施加密通信。设组成报文的字符集为 26 个英文字母（不分大小写）和两个标点符号字符“,” 、 “.”和一个空格字符（共 29 个字符） 。2、字符集中每个字符（含字母和两个标点符号）的使用概率自己根据英文行文合理给出（可以在网上查询） 。3、以字符集中各个字符为叶结点、字符的使用频率为权重构造 Huffman 树，并求得各个字符的 Huffman 编码（参考教材 P152-153 教材算法 6.16)。同时，输出构造的 Huffma
3、n 树和字符编码结果。4、在上述通信报文编码和译码系统中实现：输入一报文原文（即使用英文书写的一段文字或一两句话，称为明文） ，给出要发送的报文编码（密文） ；再输入一密文（ 0、1 序列） ，输出其对应的译码报文（明文） 。其中报文原文或编码序列自己设定，尽量是一句话或一段文字的对应编码序列，这样可以验证输出结果的正确性。5、本次实验程序给出创建哈弗曼和哈弗曼编码的源程序，调试运行并实验本次实验的全部功能。3 实验步骤与源程序（学生自己填写）4 测试数据与实验结果（可以抓图粘贴）（学生自己填写）5 结果分析与实验体会（学生自己填写）2. 版面格式：（1）各级标题：黑体，小四，段前/段后：6
4、磅（2）正文内容：宋体、五号，行间距 1.25 倍； 数据结构 实验报告 - 2 -（3）程序代码：宋体、五号，单倍行间距； （4）A4 纸，上、下、左、右边距：2 厘米注：蓝色字体部分为注释，正式报告中将其删除。哈夫曼编码算法#include #include #include typedef char* HuffmanCode;/*动态分配数组，存储哈夫曼编码 */typedef struct unsigned int weight ; /* 用来存放各个结点的权值*/unsigned int parent, LChild,RChild ; /*指向双亲、孩子结点的指针*/HTNode,
5、* 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
6、; 数据结构 实验报告 - 3 -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
7、 号放叶子结点，初始化*/(*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 最小的结点，其序号分
8、别赋值给 s1、s2 返回*/select(ht,i-1,(*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) 数据结构 实验报告 - 4 -if(m!=0)printf(%d , HTm.weight);outputHuffman(HT,HTm.LChild);outputHuffman(HT,HTm.RChild)
9、;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+)
10、 /*求 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,free(cd);for(i=1;i=n;i+)printf(%d 编码为%sn,(*ht)
11、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; 数据结构 实验报告 - 5 -printf(input the total number of the Huffman Tree: ); scanf(%d, w=(int *)malloc(n+1)*sizeof(int); for(i=1;i=n;i+) printf(input the %d element
12、s weight:,i); fflush(stdin);scanf(%d, wi=wei; CrtHuffmanTree( m = 2*n-1;outputHuffman(HT,m); printf(n);CrtHuffmanCode(关键程序段和实现思想一、密文转换为明文scanf(%d,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.19
13、65,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( /*建立哈夫曼树*/m = 2*n-1; / m=57printf(n);CrtHuffmanCode(printf(n);printf(输入哈夫曼编码 :); /*输入密文并转化为明文*/scanf(%s, p);int j=strlen(p);int t=57;i=1;printf(原文是:);while(i = j)while(HTt.LChild != 0) /因为是完全二叉树，从静态三叉链表哈弗曼树的根结 数据结构 实验报告 - 6 -点开始，沿左右子树搜索到叶子结点，此时 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);二、明文转化为密文（哈弗曼编码）程序段printf
