数据结构第三次-实验报告.doc

数据结构实验报告 实验三 哈夫曼树实验 班级：_计2-1___ 姓名：_依力夏提江·艾买尔__ 学号：__ 实验目的： 熟悉非线性结构的特点 , 掌握非线性结构的存储方式及各种操作的实现方法，同时对自顶向下的程序设计方法、应用程序界面的设计、非线性结构的文件存储方法等方面的辑程技术进行训练。 问题描述： 利用哈夫曼编码进行信息通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统，试为这样的信息收发站写一个哈夫曼编译码系统。 基本要求： 一个完整的系统应具有以下功能： （1） I： 初始化。从终端读入字符集大小 n ，及 n 个字符和 n 个权值，建立哈夫曼树，并将其存于文件hfmtree中。 （2） C： 编码。利用已建好的哈夫曼树（如不在内存，则从文件hfmtree中读入），对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中。 （3） D： 译码。利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入文件textfile中。 （4） P： 打印代码文件。将文件codefi1e以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。 （5） T：打印哈夫曼树。将已在内存中的哈夫曼树以直观的方式（树或凹凸表形式）显示在屏幕上，同时将此字符形式的哈夫曼树写入文件treeprint中。 需求分析：（包括对问题的理解，解决问题的策略、方法描述） 本程序实现了使用赫夫曼编码压缩数据；输入一串字符串sourceCode——为方便理解，暂时要求字符串只包含大写字母和空格，如果你愿意，很容易就可以推广到所有的字符——计算出字符串中各个字母的权重，然后对其进行赫夫曼编码，输出赫夫曼树。将赫夫曼树的叶子结点存储到有序二叉树中，输出原字符串经压缩后得到的用’0’和’1 编码译码成功！ 　最后销毁有序二叉树和赫夫曼树。 系统设计：（包括数据结构定义、抽象出基本操作描述、主程序模块处理过程描述） typedef char ElemType;//定　　typedef struct sNode　　{　　double weight;　　ElemType data;　　} *Source;　　typedef struct hNode　　{　　double weight;　　ElemType data;　　int lc, rc;　　} *HuffmanTree;　　typedef struct cNode　　{　　ElemType data;　　string str;　　struct cNode *lc, *rc;　　} *Btree;　　HuffmanTree CreateHuffmanTree(const Source w, int n);//创建一棵赫夫曼树　　void BuildHeap(HuffmanTree t, int n); //构造一个二叉堆；小顶堆　　void PercDown(HuffmanTree t, int pos, int n);//构造二叉堆的功能子函数　　void DeleteMin(HuffmanTree t, int len); /*删除二叉堆的根，并通过上移使得新得到的序列仍为二叉堆*/　　void InsertHfNode(HuffmanTree t, int len, struct hNode x); /*把x插入到原长度为len的二叉堆*/　　void Preorder(HuffmanTree t, int p); //先序遍历赫夫曼树　　void Postorder(Btree t, HuffmanTree a, int n); /*后序遍历赫夫曼树，并记录叶子结点编码*/　　bool InsertBtNode(Btree t, Btree s); //向一个二叉排序树t中插入一个结点s　　void Inorder(Btree t); //中序遍历二叉排序树　　Btree Search(Btree p, ElemType data); //查找值为data的结点的递归算法　　string Coding(string s, Btree t); /*利用记录了叶子结点编码的排序二叉树，对sourceCode进行编码，返回编码后的字符串*/　　string Decode(string s, HuffmanTree hT); //利用赫夫曼树对destCode进行解码　　void Destroy