数据结构实验报告
实验名称：实验三——树
学生姓名：
班级：
班内序号：
学号：
日期：
1 实验目的
通过选择下面两个题目之一进行实现，掌握如下内容：
掌握二叉树基本操作的实现方法
了解哈夫曼树的思想和相关概念
学习使用二叉树解决实际问题的能力
实验内容：
利用二叉树结构实现哈夫曼编/解码器。
基本要求：
1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个
字符的频度，并建立哈夫曼树
2、建立编码表(CreateTable)：利用已经建好的哈夫曼树进行编码，并将每
个字符的编码输出。
3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的
字符串输出。
4、译码(Decoding)：利用已经建好的哈夫曼树对编码后的字符串进行译
码，并输出译码结果。
5、打印(Print)：以直观的方式打印哈夫曼树（选作）
6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼
编码的压缩效果。(选作)
7、可采用二进制编码方式（选作）
测试数据：
I love data Structure, I love Computer。I will try my best to study data
Structure.
2 程序分析
2.1存储结构：
三叉树：
class Huffman
{
private:
HNode*HTree;//哈夫曼树结点
HCode*HCodeTable;//哈夫曼编码表
char b[1000];//记录所有输入内容被编码后的结果
char c[127];
char letter[1000];//输入内容的保存
void SelectMin(int &x,int &y,int k);//求最小权重的字符node*count;//计算各个字符出现次数
int n;//输入字符的种类（个数）
int l;
public:
Huffman();
void CreateHTree();//创建哈夫曼树
void CreateCodeTable();//创建哈夫曼编码表
void Encode();//编码
void Decode();//解码
};
结点结构为如下所示：
三叉树的节点结构：
struct HNode//哈夫曼树结点的结构体
{ int weight;//结点权值
int parent;//双亲指针
int lchild;//左孩子指针
int rchild;//右孩子指针
char data;//字符
};
示意图为：
编码表节点结构：
struct HCode//编码表结构体
{
char data;//字符
char code[100];//编码内容
};
基本结构体记录字符和出现次数:
struct node
{
int num;
char data;
};
2.关键算法分析
(1).初始化:
伪代码：
1.输入需要编译的文本内容
2.将输入的内容保存到动态建立的node型数组count中
3.统计出现的字符种类的数目,并且保存到private型变量n
Huffman::Huffman()//将输入数据保存到Huffman类中
{
l=0;
n=0;
count=new node[127];
cout<<"请输入需要编译压缩的内容"< cin.getline(letter,200,'\n'); for(int j=0;j<127;j++) //一个号码代表一种字符 { count[j].num=0; } while(letter[l]!='\0')//在结束之前，每输入一个字符，则对应字符的数目则自增1 { ++count[letter[l]].num; count[letter[l]].data=letter[l]; ++l; } for(int k=0;k<127;k++) { if(count[k].num>0) {n++;}//在某个字符出现此书num不为0时，n自增1，最终n为出现的字符种类数目 } 其时间复杂度为O(n) （2）.创建哈夫曼树（void HuffmanTree::CreateCodeTable(Node *p)） 算法伪代码： 1.创建一个长度为2*n-1的三叉链表 2.将存储字符及其权值的链表中的字符逐个写入三叉链表的前n个结点的data域，并将对 应结点的孩子域和双亲域赋为空 3.从三叉链表的第n个结点开始， 3.1从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其 下标x,y。 3.2将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点 3.3将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为 i结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i 结点的双亲设置为空 4.根据哈夫曼树创建编码表 源代码为： void Huffman::CreateHTree() { l=0; HTree=new HNode[2*n-1];//建立含有n种字符的哈夫曼树只需要2*n-1个结点即可 for(int i=0;i { while (count[l].num==0)//如果count内的权重为0，即该字符没有出现，则跳过，i 自增继续寻找出现过的字符 {l++;} HTree[i].weight=count[l].num;//将count里统计的次数传入哈夫曼树的节点中，作为字符权重 HTree[i].lchild=-1; HTree[i].rchild=-1; HTree[i].parent=-1;//将左右孩子结点和父节点都置空 HTree[i].data=count[l].data;//将count内的有效字符传入哈夫曼树的结点 l++; } int x=-1,y=-1; for(int i=n;i<2*n-1;i++)//开始建立哈夫曼树 { SelectMin(x,y,i);//挑选三者中的权重较小的两个 HTree[x].parent=HTree[y].parent=i;//令较小的x、y为孩子节点，该两个结点的父节点是i HTree[i].weight=HTree[x].weight+HTree[y].weight;//i结点字符的权重赋为是左右孩 子字符权重之和 HTree[i].lchild=x;//左孩子为x HTree[i].rchild=y;//右孩子为y HTree[i].parent=-1;//父节点置空 x=-1; y=-1;//将x、y重新赋值为零，进行下一次比较建树 ｝ 其时间复杂度为：O(n) （3）．创建编码表 算法伪代码： 1.初始化编码表 2.初始化一个指针，从链表的头结点开始，遍历整个链表 2.1 将链表中指针当前所指的结点包含的字符写入编码表中 2.2 得到该结点对应的哈夫曼树的叶子结点及其双亲 2.3 如果哈夫曼树只有一个叶子结点，将其字符对应编码设置为0 2.4 如果不止一个叶子结点，从当前叶子结点开始判断 2.4.1 如果当前叶子结点是其双亲的左孩子，则其对应的编码为0，否则为1 2.4.2 child指针指向叶子结点的双亲，parent指针指向child指针的双亲，重复2.4.1的操作 2.5 将已完成的编码倒序 2.6 取得链表中的下一个字符 3．输出编码表 源代码为： void Huffman::CreateCodeTable()//建立哈夫曼编码表 { HCodeTable=new HCode[n];//建立动态编码表 for(int i=0;i { HCodeTable[i].data=HTree[i].data; int child=i; int parent=HTree[i].parent; int k=0; while(parent!=-1) { if(child==HTree[parent].lchild)//判断该节点是父节点的左孩子或右孩子，左孩子则编码为0，右孩子则编码为1 HCodeTable[i].code[k]='0'; else HCodeTable[i].code[k]='1'; k++; child=parent;//将该节点的父节点作为新的孩子节点，继续进行编码输出 parent=HTree[child].parent; } HCodeTable[i].code[k]='\0';//code数组以\0结尾 Reverse(HCodeTable[i].code);//由于是从下到上输出，顺序是相反的，所以还需要逆置才能输出字符的编码值 } cout< for(int i=0;i { cout< } } } 其时间复杂度为：O(n) （4）选择两个最小权值的函数void Huffman::SelectMin(int &x,int &y,int k) 算法伪代码： 1.从下标为i=0的开始遍历。前两次将x，y赋值为序号最小的两个结点的地址序 号。 2.开始进行比较：进行如下分类 对于任何不存在父节点的结点： 若x权值<=y权值 （1）且i权值>=y权值，则无疑i权值最大，为输出x、y为权值较小的两个故而x，y值不便； （2）其余情况皆为x、i的权值是较小的两个，令y赋值为i，则保证x、y权值是最小的两个。 若y权值<=x权值 （1）且i权值>=x权值，则i权值是最大，x、y不变。 （2）其余情况皆为i、y权值最小，令x赋值为i，保证x、y序号结点的权值最小 3.完成如上循环，直至i=k则推出循环，第k个结点在树的位置已经确定 源代码为： void Huffman::SelectMin(int &x,int &y,int k)//选出权值较小的两个字符结点 { int i=0; while(i { while(i { if(x==-1) x=i; else if(y==-1) y=i; else if(HTree[x].weight<=HTree[y].weight) { if(HTree[y].weight<=HTree[i].weight) {y=y;x=x;} else y=i; } else if(HTree[x].weight>HTree[y].weight) { if(HTree[i].weight>=HTree[x].weight) {x=x;y=y;} else x=i; } i++; } i++; } } 其时间复杂度为O(n) （5）. 将字符串倒序的函数（void HuffmanTree::Reverse(char *pch)） 算法伪代码： 1．得到字符串的长度 2．初始化两个记录下标的变量，一个为字符串开头字符所在的下标i，另一个为字符串结尾字符所在的下标j 3．将下标为i和j的字符交换 4．i++,j - - 源代码： void Reverse(char a[]) { char b[100]; int i=0,j=0; while(a[i]!='\0') { b[i]=a[i]; i++; } b[i]='\0'; i--; while(i>=0) { a[j]=b[i]; i--; j++; } a[j]='\0'; } 其时间复杂度为O(n) （6）.编码函数（void Huffman::Encode(a[])） 算法伪代码： 1. 从开头的字符开始，逐一对a中的字符进行编码 2. 在编码表中查找与当前字符对应的字符 3．如果找到了与当前字符对应的编码表中的字符，将其编码追加到解码串的末 尾。 4. 重复以上步骤，直到所有待编码串中的字符都编码完毕 5. 输出编码后的字符串 void Huffman::Encode()//编译输入内容为代码内容用0和1表示 { cout<<"编码结果为："; int k=0; for(int i=0;letter[i]!='\0';i++) { int j=0; while(HCodeTable[j].data!=letter[i])//编码表的字符等于输入内容的字符时进行下一个while循环 {j++;} int m=0; while(HCodeTable[j].code[m]!='\0')//输出该字符的编码 { b[k]=HCodeTable[j].code[m];//用数组b记录所有的编码数据，以备后续解码使用 k++; m++; } } b[k]='\0'; cout< cout< } 其时间复杂度为：O(n) （7）.解码函数（void Huffman::Decode()） 算法伪代码： 1.得到指向哈夫曼树的根结点的指针和指向待解码串中的第1个字符的指针 2.逐个读取待解码串中的字符，若为0，则指向哈夫曼树当前结点的指针指向 当前结点的左孩子，若为1，则指向当前结点的右孩子 3.指向待解码串的指针指向解码串中的下一个字符，直到指向哈夫曼树结点 的指针的孩子结点为空 4.如果哈夫曼树只有一个叶子结点，直接将待解码串中的编码转换为对应的 字符 5.如果指向哈夫曼树结点的指针的孩子结点已经为空，则将叶子结点下标对 应的字符追加到解码串中。 6.输出解码串 源代码： void Huffman::Decode() { cout<<"解码结果为："; int i=0,j=0; while(b[i]!='\0') { int child=2*n-1-1;//找到保存根节点的数组数 据 while(HTree[child].lchild!=-1)//若是这个节 点父节点的孩子存在则继续向下寻找 { if(b[i]=='0') child=HTree [child].lchild;//是0则找左孩子 else child=HTree [child].rchild;//是1则找右孩子 i++; } c[j]=HCodeTable[child].data;//若不存在孩子节点，则令数组的元素为该节点的字符变量 cout< j++;//逐个输出字符内容 } } 时间复杂度：O(n) 3. 程序运行结果 1.主函数流程图 运行结果： 4. 总结 通过本次数据结构实验，我学会了利用哈夫曼树解决编译代码的问题，并且初步了解掌握了二叉树、树的用法。实验重点是建立哈夫曼三叉树，建立编码表，解码函数，以及选择权重最小两个结点的函数的调用。同时还要注意学会逆置输出代码等容易被忽视的细节问题。本次实验提高了对于哈夫曼思想的加深理解，有利于以后编程的继续学习和实践能力的增强。 数据结构课程设计设计题目：哈夫曼树编码译码 目录 第一章需求分析 (1) 第二章设计要求 (1) 第三章概要设计 (2) （1）其主要流程图如图1-1所示。 (3) （2）设计包含的几个方面 (4) 第四章详细设计 (4) （1）①哈夫曼树的存储结构描述为： (4) （2）哈弗曼编码 (5) （3）哈弗曼译码 (7) （4）主函数 (8) （5）显示部分源程序： (8) 第五章调试结果 (10) 第六章心得体会 (12) 第七章参考文献 (12) 附录： (12) 在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。哈弗曼编码使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。 第二章设计要求 对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出电文字符串。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为∑WiLi。若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，∑WiLi 恰好为二叉树上带权路径长度。因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵哈夫曼树，此构造过程称为哈夫曼编码。设计实现的功能： (1) 哈夫曼树的建立； (2) 哈夫曼编码的生成； (3) 编码文件的译码。 数据结构实验报告 欧阳光明（2021.03.07） 实验名称：实验三树——哈夫曼编/解码器 学生姓名： 班级： 班内序号： 学号： 日期： 2014年12月11日 1．实验要求 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 1、初始化(Init)：能够对输入的任意长度的字符串s进行统 计，统计每个字符的频度，并建立赫夫曼树 2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编 码，并将每个字符的编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并 将编码后的字符串输出。 4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符 串进行译码，并输出译码结果。 5、打印(Print)：以直观的方式打印赫夫曼树（选作） 6、计算输入的字符串编码前和编码后的长度，并进行分析， 讨论赫夫曼编码的压缩效果。 测试数据： I love data Structure, I love Computer。I will try my best to study data Structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个字符出现的次数统计频度，对没有 出现的 字符一律不用编码。 2. 程序分析 2.1 存储结构 Huffman树 给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，其中带权路径长度最小的二叉树称为Huffman树，也叫做最优二叉树。 weight lchild rchildparent 2-1-1-1 5-1-1-1 6-1-1-1 7-1-1-1 9-1-1-1 weight lchild rchild parent 数据结构实验报告实验题目: Huffman编码与解码 姓名: 学号: 院系: 实验名称: Huffman编码与解码实验 问题描述: 本实验需要以菜单形式完成以下功能: 1、输入电文串 2、统计电文串中各个字符及其出现的次数 3、构造哈弗曼树 4、进行哈弗曼编码 5、将电文翻译成比特流并打印出来 6、将比特流还原成电文 数据结构的描述: 逻辑结构: 本实验可用二叉树实现,其逻辑结构为一对二的形式,即一个结点对应两个结点。在实验过程中我们也应用到了栈的概念。 存储结构: 使用结构体来对数据进行存储: typedef struct { int weight; int parent,lc,rc; }HTNode,*HuffmanTree; typedef struct LNode { char *elem; int stacksize; int top; }SqStack; 在main函数里面定义一个哈弗曼树并实现上述各种功能。 程序结构的描述: 本次实验一共构造了10个函数: 1.void HuffTree(HuffmanTree &HT,int n[],int mun); 此函数根据给定的mun个权值构建哈弗曼树,n[]用于存放num个权值。 2、void Select(HuffmanTree &HT,int n,int i,int &s1,int &s2); 此函数用于在HT[1,i-1]中选择parent为0且weight为最小的两个结点,其下标分别为s1,s2、 3.void HuffmanCoding(HuffmanTree HT,char **&HC,int n); 此函数从哈弗曼树HT上求得n 个叶子结点的哈弗曼编码并存入数组HC中。 4.void Coding(HuffmanTree HT,char **HC,int root,SqStack &S); 此函数用于哈弗曼编码,先序遍历哈弗曼树HT,求得每个叶子结点的编码字符串,存入数组HC,S为一个顺序栈,用来记录遍历路径,root就是哈弗曼数组HT中根结点的位置下标。 5.void InitStack(SqStack &S); 此函数用于初始化一个栈。 6.void Pop(SqStack &S,char e); 此函数为出栈操作。 7.void Push(SqStack &S,char e); 此函数为进栈操作。 8.int StackLength(SqStack S); 此函数用于求栈长,返回一个int型的值。 9.int Find(char a,char s[],int num); 此函数用于查找字符a在电文串中的位置。 10.int Recover(HuffmanTree HT,char **HC,char string[],char a[],char b[],int n); 此函数用于将比特流还原成电文。 调试分析: 输入任意一个字符串,如输入welcometoustc:运行结果如下: 实验二二叉树的遍历及霍夫曼编码 班级：计科1101班 学号：0909101605 姓名：杜茂鹏 2013年5月22日 一、实验目的 掌握二叉树的建立及遍历操作，霍夫曼编码基本操作及存储结构表示 二、实验内容 1. 系统要求包含以下功能 1）初始化：从终端读入字符集大小n，以及n个字符和n个权值（或者读入字符集和频度数据文件），建立哈夫曼树，并将哈夫曼树存入到文件HfmTree 中。 2）编码：利用已建好的哈夫曼树（如果不在内存中，则从文件中读入），从文件ToBeTran中读入原文，对原文进行编码，将编码后的结果存入文件CodeFile 中。 3）译码：利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。 4）打印：打印输出哈夫曼树，显示ToBeTran, TextFile和CodeFile文件的内容。 三、实验要求 1．在上机前写出全部源程序； 2．能在机器上正确运行程序； 3．用户界面友好。 四、概要设计 1）首先动态分配数组存储霍夫曼树及存储霍夫曼编码表，然后从终端或文件读入霍夫曼树的字符变量及其频度，初始化建立霍夫曼树并将其写入文件HfmTree.txt中。 2）从指定的文件succe.txt中读入原文，利用已经编好的霍夫曼树对其编码，将编码结果写入文件Coding.txt保存。 3）利用已建好的哈夫曼树将文件Coding.txt中的代码进行译码，结果存入文件decoding.txt中。 五、测试数据： 2．原文内容“THIS IS MY PROGRAM” 六、详细设计 实验内容(原理、操作步骤、程序代码) //建立霍夫曼树，对原文进行编码、译码 #include 计算机科学与技术学院数据结构实验报告 班级2014级计算机1班学号20144138021 姓名张建华成绩 实验项目简单哈夫曼编/译码的设计与实现实验日期2016.1.5 一、实验目的 本实验的目的是进一步理解哈夫曼树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。 二、实验问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能： 1、接收原始数据。 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmtree.dat中。 2、编码。 利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.dat中读入），对文件中的正文进行编码，然后将结果存入文件codefile.dat中。 3、译码。 利用已建好的哈夫曼树将文件codefile.dat中的代码进行译码，结果存入文件textfile.dat中。 4、打印编码规则。 即字符与编码的一一对应关系。 5、打印哈夫曼树， 将已在内存中的哈夫曼树以直观的方式显示在终端上。 三、实验步骤 1、实验问题分析 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，描述结点的数据类型为： Typedef strcut { Int weight；/*结点权值*/ Int parent； Int lchild； Int rchild； }HNodeType； 2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位码，所以设计如下数据类型： 数据结构实验报告 实验名称：实验3——哈夫曼编码 学生姓名： 班级： 班内序号： 学号： 日期：2013年11月24日 1．实验要求 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个 字符的频度，并建立赫夫曼树 2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每 个字符的编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的 字符串输出。 4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译 码，并输出译码结果。 5、打印(Print)：以直观的方式打印赫夫曼树（选作） 6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼 编码的压缩效果。 2. 程序分析 2.1存储结构： struct HNode { char c;//存字符内容 int weight; int lchild, rchild, parent; }; struct HCode { char data; char code[100]; }; //字符及其编码结构 class Huffman { private: HNode* huffTree; //Huffman树 HCode* HCodeTable; //Huffman编码表 public: Huffman(void); void CreateHTree(int a[], int n); //创建huffman树 void CreateCodeTable(char b[], int n); //创建编码表 void Encode(char *s, string *d); //编码 void Decode(char *s, char *d); //解码 void differ(char *,int n); char str2[100];//数组中不同的字符组成的串 int dif;//str2[]的大小 ~Huffman(void); }; 结点结构为如下所示： 三叉树的节点结构： struct HNode//哈夫曼树结点的结构体 { int weight;//结点权值 int parent;//双亲指针 int lchild;//左孩子指针 int rchild;//右孩子指针 char data;//字符 }; 示意图为： int weight int parent int lchild int rchild Char c 编码表节点结构： 一、需求分析 1、本演示程序实现Haffman编/译码器的作用，目的是为信息收发站提供一个编/译系统， 从而使信息收发站利用Haffman编码进行通讯，力求达到提高信道利用率，缩短时间，降低成本等目标。系统要实现的两个基本功能就是：①对需要传送的数据预先编码； ②对从接收端接收的数据进行译码； 2、本演示程序需要在终端上读入n个字符（字符型）及其权值（整形），用于建立Huffman 树,存储在文件hfmanTree.txt中；如果用户觉得不够清晰还可以打印以凹入表形式显示的Huffman树； 3、本演示程序根据建好的Huffman树，对文件的文本进行编码，结果存入文件CodeFile 中；然后利用建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中；最后在屏幕上显示代码（每行50个），同时显示对CodeFile中代码翻译后的结果； 4、本演示程序将综合使用C++和C语言； 5、测试数据： (1)教材例6-2中数据：8个字符，概率分别是0.05，0.29，0.07，0.08，0.14，0.23，0.03， 0.11，可将其的权值看为5，29，7，8，14，23，3，11 (2)用下表给出的字符集和频度的实际统计数据建立Haffman树，并实现以下报文的编码和 一、概要设计 1、设定哈夫曼树的抽象数据类型定义 ADT Huffmantree{ 数据对象：D={a i| a i∈Charset,i=1,2,3,……n,n≥0} 数据关系：R1＝{< a i-1, a i >| a i-1, a i∈D, i=2,3,……n} 基本操作： Initialization(&HT，&HC,w，n,ch) 操作结果：根据n个字符及其它们的权值w[i],建立Huffman树HT,用字符数组ch[i]作为中间存储变量，最后字符编码存到HC中； Encodeing(n) 操作结果：根据建好的Huffman树，对文件进行编码，编码结果存入到文件CodeFile 中 Decodeing(HT,n) 操作结果：根据已经编译好的包含n个字符的Huffman树HT，将文件的代码进行翻译，结果存入文件TextFile中 } ADT Huffmantree 数据结构实验报告实验名称：实验四排序（题目1） 姓名： 班级： 班内序号： 学号： 1．实验要求 实验目的：学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。实验内容：使用简单数组实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 要求： 1、测试数据分成三类：正序、逆序、随机数据 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换 计为3次移动）。 3、对2的结果进行分析，验证上述各种算法的时间复杂度。 编写测试main()函数测试线性表的正确性。 2. 程序分析 2.1 存储结构 2.2 关键算法分析 2.2.1 插入排序 插入排序的基本方法是寻找一个指定元素在待排序元素中的位置，然后插入。一趟直接插入排序的C++描述过程如下： ①将待插入纪录赋值给哨兵r[0]：r[0]=r[i]; ②从后向前进行顺序查找：for(j=i-1;r[0] {r[j+1]=r[j];move++; comp++;} //循环中移动计数器++ comp++; //比较计数器++ r[j+1]=r[0];move++; //移动计数器++ } comp++; //比较计数器++ } cout<<"本次直接插入排序数据长度为："< 数据结构实验报告 实验名称：实验四——链表的排序 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 [内容要求] 使用链表实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、冒泡排序 3、快速排序 4、简单选择排序 5、其他 要求： 1、测试数据分成三类：正序、逆序、随机数据 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其 中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒 （选作） 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度 编写测试main()函数测试线性表的正确性 代码要求 1、必须要有异常处理，比如删除空链表时需要抛出异常； 2、保持良好的编程的风格： 代码段与段之间要有空行和缩近 标识符名称应该与其代表的意义一致 函数名之前应该添加注释说明该函数的功能 关键代码应说明其功能 3、递归程序注意调用的过程，防止栈溢出 2. 程序分析 2.1 存储结构 [内容要求] 存储结构：双链表 2.2 关键算法分析 [内容要求] 定义类： template 哈夫曼树实验报告 Company number：【0089WT-8898YT-W8CCB-BUUT-202108】 计算机科学与技术学院数据结构实验报告 班级 2014级计算机1班学号姓名张建华成绩 实验项目简单哈夫曼编/译码的设计与实现实验日期一、实验目的 本实验的目的是进一步理解哈夫曼树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。 二、实验问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能： 1、接收原始数据。 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件中。 2、编码。 利用已建好的哈夫曼树（如不在内存，则从文件中读入），对文件中的正文进行编码，然后将结果存入文件中。 3、译码。 利用已建好的哈夫曼树将文件中的代码进行译码，结果存入文件中。 4、打印编码规则。 即字符与编码的一一对应关系。 5、打印哈夫曼树， 将已在内存中的哈夫曼树以直观的方式显示在终端上。 三、实验步骤 1、实验问题分析 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，描述结点的数据类型为： Typedef strcut { Int weight；/*结点权值*/ Int parent； Int lchild； Int rchild； }HNodeType； 2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路 北京邮电大学电信工程学院 数据结构实验报告 实验名称：实验三树 ----- 哈夫曼编/解码器 学生姓名： 班级： 班内序号： 学号： 日期：2014年12月11日 1. 实验要求 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 1、初始化(Init):能够对输入的任意长度的字符串s进行统计，统计每个 字符的频度，并建立赫夫曼树 2、建立编码表(CreateTable)利用已经建好的赫夫曼树进行编码，并将每 个字符的编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的 字符串输出。 4、译码(Decoding)：禾U用已经建好的赫夫曼树对编码后的字符串进行译 码，并输出译码结果。 5、打印(Print):以直观的方式打印赫夫曼树(选作) 6计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。 测试数据： I love data Structure, I love Computer。I will try my best to study data Structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符 一律不用编码。 2. 程序分析 2.1存储结构 Huffman 树给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，其中带权路径 长度最小的二叉树称为Huffman 树，也叫做最优二叉树 哈夫虽树示意图 root 孩子双亲表示法 _____________________ JL________________ weight Ichild rchild pare nt 数据结构实验报告 实验名称：实验三树——哈夫曼编/解码器 学生姓名： 班级： 班内序号： 学号： 日期：2014年12月11日 1．实验要求 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个 字符的频度，并建立赫夫曼树 2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每 个字符的编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的 字符串输出。 4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译 码，并输出译码结果。 5、打印(Print)：以直观的方式打印赫夫曼树（选作） 6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼 编码的压缩效果。 测试数据： I love data Structure, I love Computer。I will try my best to study data Structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的 字符一律不用编码。 2. 程序分析 2.1 存储结构 Huffman树 给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，其中带权路径长度最小的二叉树称为Huffman树，也叫做最优二叉树。 weight lchild rchild parent 2-1-1-1 5-1-1-1 6-1-1-1 7-1-1-1 9-1-1-1 weight lchild rchild parent 2-1-15 5-1-15 6-1-16 7-1-16 9-1-17 7017 数据结构实验报告 1．实验要求 (1)实验目的 通过选择下面两个题目之一，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。 (2)实验内容 使用简单数组实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序（选作） 7、归并排序（选作） 8、基数排序（选作） 9、其他 要求： 1、测试数据分成三类：正序、逆序、随机数据 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其 中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒 （选作） 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度 编写测试main()函数测试排序算法的正确性。 2. 程序分析 2.1 存储结构 顺序表: 示意图： 2.2 关键算法分析 （1）测试数据的产生：正序、逆序、随机数据 用两个数组实现乱序、顺序以及逆序数据的排序。 基本思想为：随机序列产生一个指定长度的乱序序列，然后通过memcpy()函数拷贝到第 二个数组里，第二个数组作为乱序序列的保存数组，每次对第一个数组进行排序，之后拷贝第二个数组中的乱序序列到第一个数组，实现各次乱序排列。只要算法正确（第一步可以检验），之后顺序排列只需反复对第一个数组进行操作即可，再后用第二个数组保存逆序数组，然后同样在每次排序之后复制第二数组存储的乱序序列到第一组，对第一组反复排序即可。 <1> pRandom1=new long int[Max+1];pRandom2=new long int[Max+1]; <2> srand((unsigned)time(NULL)); for(int i = 1; i <= Max;i++ ) pRandom2[i]=rand(); <3> memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(long int)); （2）排序算法： <1>插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。 /1/int j=0; /2/ for(int i =2; i <= Max;i++) parray[0]=parray[i];comparetimes[0]++; /4/parray[j+1]=parray[0];movetimes[0]+=2; 示意图： r1,r2,r3,…,ri-1,ri,ri+1,…,rn 有序区待插入无序区 <2>希尔排序：先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。 int Sort::ShellSort(long int parray[]) {int j=0; for(int d=Max/2;d>=1;d/=2) {for(int i=d+1;i<=Max;i++) { parray[0]=parray[i]; comparetimes[1]++; for(j=i-d;j>0 && parray[0] 电子科技大学 实验报告 课程名称：数据结构与算法 学生姓名：陈*浩 学号：************* 点名序号： *** 指导教师：钱** 实验地点：基础实验大楼 实验时间： 2014-2015-2学期 信息与软件工程学院 实验报告(二) 学生姓名：陈**浩学号：*************指导教师：钱** 实验地点：科研教学楼A508实验时间：一、实验室名称：软件实验室 二、实验项目名称：数据结构与算法—树 三、实验学时：4 四、实验原理： 霍夫曼编码（Huffman Coding）是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。1952年，David A. Huffman在麻省理工攻读博士时所发明的。 在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。 例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个比特。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。 霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。 可以证明霍夫曼树的WPL是最小的。 数据结构实验报告 实验名称：实验三哈夫曼树 学生姓名： 班级： 班内序号： 学号： 日期： 程序分析： 存储结构：二叉树 程序流程： template 2.获得输入字符串的第一个字符，并将其插入到链表尾部,n=1(n记录的是链 表中字符的个数) 3.从字符串第2个字符开始，逐个取出字符串中的字符 将当前取出的字符与链表中已经存在的字符逐个比较，如果当前取出的 字符与链表中已经存在的某个字符相同，则链表中该字符的权值加1。 如果当前取出的字符与链表中已经存在的字符都不相同，则将其加入到 链表尾部，同时n++ =n(tSize记录链表中字符总数，即哈夫曼树中叶子节点总数) 5.创建哈夫曼树 6.销毁链表 源代码： void HuffmanTree::Init(string Input) { Node *front=new Node; 建哈夫曼树（void HuffmanTree::CreateCodeTable(Node *p)） 算法伪代码： 1.创建一个长度为2*tSize-1的三叉链表 2.将存储字符及其权值的链表中的字符逐个写入三叉链表的前tSize个结点 的data域，并将对应结点的孩子域和双亲域赋为空 3.从三叉链表的第tSize个结点开始，i=tSize 3.1从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其 下标x,y。 3.2将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点 3.3将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为 i结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i 结点的双亲设置为空 4. 根据哈夫曼树创建编码表 哈夫曼树实验报告 需求分析： 从终端读入一串字符，利用建立好的哈夫曼树对其进行编码，储存到文件当中去，然后从文件读入哈夫曼编码，针对每个字母对其进行译码，翻译为原来的信息。 二、概要设计 程序分为以下几个模块： 1、从终端读入字符集大小，n个字符和n个权值，建立哈夫曼树，写入文件hfmTree中去。 2、对hfmTree进行编码，建立hfm编码表。 3、从文件ToTran读入信息，根据hfm编码表对其进行hfm编码，将编码后的信息写入文件Codefile 中去 4、对Codefile文件反向译码，结果储存在Textfile中去。 5、将建立的hfmTree打印在终端上，并储存于相应的Treeprint文件中去。 抽象的数据定义如下： 哈夫曼树结构 typedef struct //定义哈夫曼树的结构 { int weight; //权值 int parent; //双亲 int lchild; //左孩子 int rchild; //右孩子 }htnode,huffmantree[M+1]; 建立哈夫曼树 void crthuffmantree(huffmantree ht,int w[],int n) //初始化哈夫曼树 { int i,s1,s2,m; for(i=1;i<=n;i++) { ht[i].weight=w[i]; ht[i].parent=0; ht[i].lchild=0; ht[i].rchild=0; } m=2*n-1; for(i=n+1;i<=m;i++) { ht[i].weight=0; ht[i].parent=0; ht[i].lchild=0; ht[i].rchild=0; } for(i=n+1;i<=m;i++) { select(ht,i-1,&s1,&s2); ht[i].weight=ht[s1].weight+ht[s2].weight; ht[s1].parent=i; 数据结构实验三哈夫曼树实验报告 题目：哈夫曼编/译码器 一、题目要求： 写一个哈夫曼码的编/译码系统，要求能对要传输的报文进行编码和解码。构造哈夫曼树时，权值小的放左子树，权值大的放右子树，编码时右子树编码为1，左子树编码为0. 二、概要设计： 数据结构： typedef struct { int bit[MAXBIT]; int start; } HCodeType; /* 编码结构体 */ typedef struct { int weight; int parent; int lchild; int rchild; char value; } HNode; /* 结点结构体 */ 函数： void DEMONHuffmanTree (HNode HuffNode[MAXNODE], int n) 作用：构造一个哈夫曼树，并循环构建 int main () 作用：运用已经构建好的哈弗曼树，进行节点的处理，达到成功解码编译 三、详细设计： 哈夫曼树的建立： void DEMONHuffmanTree (HNode HuffNode[MAXNODE], int n) { int i = 0, j, m1, m2, x1, x2; char x; /* 初始化存放哈夫曼树数组HuffNode[] 中的结点*/ while (i 2009级数据结构实验报告 实验名称：实验三——哈夫曼编/解码器的实现 学生姓名：陈聪捷 日期：2010年11月28日 1．实验要求 一、实验目的： 了解哈夫曼树的思想和相关概念； 二、实验内容： 利用二叉树结构实现哈夫曼编/解码器 1.初始化：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树。 2.建立编码表：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。 3.编码：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。 4.译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。 5.打印：以直观的方式打印哈夫曼树。 6.计算输入的字符串编码前和编码后的长度，并进行分析，讨论哈夫曼编码的压缩效果。 7.用户界面可以设计成“菜单”方式，能进行交互，根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。 2. 程序分析 存储结构 二叉树 template 如果当前取出的字符与链表中已经存在的字符都不相同，则将其加入到 链表尾部，同时n++ =n(tSize记录链表中字符总数，即哈夫曼树中叶子节点总数) 5.创建哈夫曼树 6.销毁链表 源代码： void HuffmanTree::Init(string Input) { Node *front=new Node; 建哈夫曼树（void HuffmanTree::CreateCodeTable(Node *p)）算法伪代码： 1.创建一个长度为2*tSize-1的三叉链表 2.将存储字符及其权值的链表中的字符逐个写入三叉链表的前tSize个结点 的data域，并将对应结点的孩子域和双亲域赋为空 3.从三叉链表的第tSize个结点开始，i=tSize 3.1从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其下 标x,y。 3.2将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点 3.3将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为i 结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i结 点的双亲设置为空 4. 根据哈夫曼树创建编码表 源代码： void HuffmanTree::CreateHTree(Node *p,int n) { root= new BiNode哈夫曼树编码译码实验报告(DOC)
北邮信通院数据结构实验报告三哈夫曼编码器之欧阳光明创编
数据结构实验报告哈夫曼树
霍夫曼树实验报告
哈夫曼树 实验报告
北邮数据结构实验3哈夫曼编码
哈夫曼树的实验报告1
北邮数据结构第四次实验题目一排序
北邮数据结构实验四-链表排序
哈夫曼树实验报告
北邮信通院数据结构实验报告三哈夫曼编码器
北邮信通院数据结构实验报告三哈夫曼编码器
北邮数据结构实验 第三次实验 排序
哈夫曼树及其操作-数据结构实验报告(2)
哈夫曼树实验报告
哈夫曼树实验报告(付原C语言程序)
数据结构实验三哈夫曼树实验报告
北京邮电大学信通院数据结构实验三——哈夫曼树实验报告
相关主题
文本预览