实习报告_93.docVIP

实习报告 题目：哈夫曼编/译码器 班级： 姓名： 学号： 完成日期 ： 需求分析 本演示程序的主要目的是利用哈夫曼树的构造原理，可以对字符进行编码，并且可以对已经编译好的代码进行译码，并且包括进行显示输出和文件保存，文件存储。 实始化时，用户只需输入大小和字符以及权值，程序自动构造哈夫曼树，并将已经建好的哈夫曼树存于文件中，当编译码时，如果哈夫曼树已经建好，则直接从文件中读取，如果没有建好，则需当时构造。 引哈夫曼树时是用字符的形式把哈夫曼树显示在终端上.编译码时都要把结果存入文件中. 用户的直接应用界面要友好. 程序包括的命令包括： (1):建立哈夫曼编码树 (2)印哈夫曼树 (3):输出编码表 (4):编码 (5):译码 (0):退出。 测试数据 选择建立蛤夫曼树,输入字符和权值分别为:a 1,b,2,c,3,d 4 输出哈夫曼树,检查是否正确,在指定文件D:\stextfil.txt输入abcd然后编码输出编码表检查是否正确,并且看文件D:\codefile.txt是否正确,然后再把选择译码,检查文件D:\textfile.txt是否正确. 概要设计 为实现上述功能，其中程序中采用哈夫曼算法,构造一个哈夫曼树，由于有N个叶子结点，则整个哈夫曼树共有2*N-1个结点，其中结点采用一个结构体类型HTNode,由于用户输入的字符和权值构造出N个结点，其中要额外构造出N-1个空的结点。然后根据哈夫曼算法，从N个结点中选择权值合最小的两棵树构造一棵新的二叉树的根结点，根结点的权值为其左右孩子的权值之和。并且在集合中删除这两棵树，同时将新得到的二叉树加入到F中。一直循环直到只有一棵树，便构造好了哈夫曼树。 哈夫曼树的抽象数据类型定义为： ADT HuffmanTree{ 数据对象：由包含字符和权值以及连接信息所构成的哈夫曼结点构成的树. 数据关系：R1={ai-1,ai|ai-1,ai∈D,I=2,….n D表示树中两个结点的连接} 基本操作： FillTree(int n) 操作结果：构造出叶子结点,并且相关的信息也被赋予.(字符以及权值) CreateHFTree(int *treenodes) 初始条件:叶子结点已经建好 操作结果：利用哈夫曼算法,和Select()函数构建哈夫曼树, Select(int num,int *s1,int *s2) 初始条件:结点数大于1 操作结果：:选择交结点为空而且权值之各最小的两个结点,并且将他们的序号返回. FillTree(int n) 初始条件:哈夫曼树已经建好 操作结果：在终端输出哈夫曼树 InCode(char *infile,int treenodes,char *outfile) 初始条件:哈夫曼树已经建好,并且要编码的字符串已经输入到文件infile中 操作结果:编好的哈夫曼码存储到outfile 中 OutCode(char *infile,int treenodes,char *outfile) 初始条件:哈夫曼树已经建好,并且要译码的码已经输入到文件infile中 操作结果:译好的字符存储到outfile 中 2.主程序 void main() { 初始化: do{ 接受命令. 处理命令 }while(“命令”!=”退出”); 3.程序模块 主程序模块 ↓ 相应的操作 ↓ 已经建好的哈夫曼树 三.详细设计 哈夫曼树结点的类型实现: typedef struct HTNode{ char character;//存储的字符 int weight;//字符的权值 int parent,lchild,rchild;//交亲及左右孩子 }HTNode,*HuffmanTree; 基本操作实现: (1) void FillTree(int n){ int i,weight,go,j; char ch; printf(There are %d TreeNodes requere!\nInput the 1 node!\n,n);//提示输入字符和权值 printf(ch\n); scanf(%c,ch); getchar(); printf(weight\n); scanf(%d,weight); getchar(); HT[1].character=