《数据结构》实验报告
题目：
专业： 班级：
组别： 组长： 完成日期： 年 月 日
评分依据及结果
态度（A-D） | 规范性（A-D） | 完成度（A-D） | 总评（A-D） |
评 语 | |||
代码分工情况
姓名 | |||||
工作内容 | |||||
实验报告分工情况
姓名 | 耿丽丽 | weight的所有形式 | |||
工作内容 | 需求分析 概要分析 | ||||
一、 需求分析
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。本次设计要求对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出电文字符串。
系统应具有如下的几个功能：
1、 初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树
2、 建立编码表(CreateTable):利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。
3、 编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。
4、 译码(Decoding)：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出
译码结果。
5、 打印(Print)：以直观的方式打印哈夫曼树.
二、 概要设计
本程序的数据类型定义为
typedef struct{
int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char** HuffmanCode;
//把字母和相应的权值放在一起
typedef struct
{
char ch;
int wht;
}WeNu;
所实现的功能函数如下
//统计叶子结点的权值
void CountWeight(char*str);
//选择parent为0，且weight最小的两个节点 序号为s1，s2
void Select(HuffmanTree HT,int len,int &s1,int &s2);
// 构造哈夫曼树HT
void CreatHuffmanTree(HuffmanTree &HT, int n)
// 从叶子到根逆向求每个字符的赫夫曼编码，存储在编码表HC中
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
//输出编码
void ShowCode(HuffmanTree HT, HuffmanCode HC, int n)
//输出哈夫曼
void ShowHuffman(HuffmanTree HT, HuffmanCode HC, char *str)
//输出字符串
void ShowStr(char *str)
//选择解码方式
void DeCoding();
//主函数
void main();
主要结构如图所示：
三、详细设计
1.统计字符频度 自然语言描述：
（1） 取出字符串中的一个字符
（2） 遍历所有初始化的哈夫曼树结点
（3） 如果结点中有记录代表的字符且字符等于取出的字符，说明该字符的叶子存在，则将该结点的权值加1
（4） 如果所有结点记录的字符均没有与取出的字符一致，说明该字符的叶子不存在，则将结点的字符记为取出字符，并将权重设为1
（5） 重复以上步骤，直至字符串中所有字符全部遍历
伪代码描述：
1. for(int i=0;i<length;i++)
1.1 for (int j=0;j<length;j++)
1.1.1if (WordStr[i]==HuffTree[j].word)//若字符已被统计，则增加权值即可 1.1.1.1 权重++;
1.1.1.2 break;
1.1.2 else if(!HuffTree[j].word)//否则需要一个新结点储存这个字符 1.1.2.1 HuffTree[j].word=WordStr[i];
1.1.2.3 HuffTree[j].weight=1；
1.1.2.4break；
时间复杂度O（N2），空间复杂度S（0）
2. 构造哈夫曼树：
自然语言描述：
(1) 选出权值最小的两个结点，其权值和作为其根结点的权值，最小的结点作为左子树；
(2) 次小的做为右子树，不断将两棵子树合升为一棵树。重复及上述过程，直至所有结点全被遍历完。
3. 为每个叶子结点编码自然语言描述：
（1）初始化一个字符数组Code暂存每个叶子节点的编码；
（2）前序遍历哈夫曼树；
（3）若结点左右子树都为-1，则将Code复制到编码的Code串，准备返回上一层，编码相位少一位，Code长度-1，返回；
（4）否则按照从左到右的顺序前序遍历根结点的所有子树；
（5）若访问左子树，则进入下一层，编码相位多一位，Code长度加1并将最后一位赋值为0，访问右子树，进入下一层，Code长度加1并将最后一位赋值为0。
4、编码
自然语言描述：
（1） 定义字符串CodeStr储存编码
（2） 遍历输入字符串的每一个字符
（3） 对每一个字符，将其与HuffTree前n个叶子节点的word逐个比较，相同则将该节点的编码串Code连接到CodeStr。
5、译码
自然语言描述：
（1）从编码串CodeStr的第一个字符串开始于HuffTree的第一个节点的编码域第一个字符比较
（1）从编码串CodeStr的第一个字符串开始于HuffTree的第一个节点的编码域第一个字符比较
（2）相等则比较后面的字符
（3）否则，从CodeStr第一个字符与HuffTree第二个结点的编码比较
（4） 重复上述过程，将CodeStr中的所有字符比较完毕
四、调试分析
1.在写程序与调试的过程中，发现自己对于函数的调用与参数的传递的方面还是存在很多问题，从参数的类型等等方面都出现了很多问题。
2.关于这个程序的要求比较复杂，刚开始做的时候没有任何思路，最后分模块一点点的进行。
3．递归函数中的参数传递
在给每个字符编码时，由于编码是从根结点开始，所以选用与前序遍历相似的递归遍历形式。其中需要一个字符型数组来记录路径和编码，由于递归一次才有一位编码，所以这个数组也要随着递归函数的进行而不断修改。开始时我们没有用指针最为参数而是直接将数组作为参数.结果发现每次调用递归函数时数组都是空。原来我用的是值传递，数组就算修改了也无法返回。这提醒了我们之后运用递归函数时如果需要某个变量随函数递归而修改时应该使用地址传递而并非值传递。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论