数据结构课程设计实验报告(赫夫曼编码)

格式：doc
大小：306.00 KB
文档页数：20

(此文档为word格式，下载后您可任意编辑修改！) +数据结构课程设计题目：赫夫曼编码院、系：计算机科学与工程学院学科专业：计算机科学与技术学生：高经典学号：指导教师：梁晨2010年12月22日目录1课程设计的题目-----02课程设计的目的（设计要解决的问题）3概要设计（函数划分、总体设计）----14详细设计（算法、流程图、程序）-----25调试结果--6课程设计总结---- -337心得体会二课程设计的目的<1>巩固构造赫夫曼树的算法。

<2>设计实验用程序实现赫夫曼树的构造。

<3>熟悉用先序、中序或后序的访问方法得到个叶子结点的赫夫曼编码。

三概要设计（函数划分、总体设计）<一>总体设计（1）输入一个字符串用结构体链表存储字符串中出现的不同字符及其出现的次数。

（2）定义赫夫曼数的结点结构体，把不同的字符及其在字符串中出现的次数作为叶子结点的元素及其权值，统计叶子结点的个数n，开辟可以存储2*n个结点的顺序表，来赫夫曼树的各个结点，然后按照一定的规则构造赫夫曼树。

（3）开辟一个可以存储叶子结点元素及指向存储其赫夫曼编码链表的指针的顺序表，然后从叶子结点开始向上访问，是左孩子的把‚0‛接进链表是右孩子的把‚1‛接进链表，直到根结点，然后把叶子结点的元素及存储其赫夫曼链表的头指针读入顺序表，直到把所有的叶子结点的元素及指向存储其赫夫曼编码链表的头指针读入顺序表，这样得到的赫夫曼编码是倒序的。

（4）从存储其叶子结点及指向存储其赫夫曼编码链表头指针的顺序表表头开始顺序访问各元素，在输出其赫夫曼编码之前，把链表中的编码顺序读入到等长的栈中，然后编码出栈就会得到顺序的赫夫曼编码，直到把所有的叶子结点都访问到。

（5）用一个字符型的指针指向字符串的第一个字符，从存储叶子结点元素及指向存储其赫夫曼编码链表的头指针的顺序表表头开始访问顺序表中的各元素，直到找到叶子结点的元素和当前字符相等就结束访输出赫夫曼编码，回到表头，指针后移，直到输出字符串的最后一个字符的赫夫曼编码，这样就得到输入字符串的赫夫曼编码。

<二>函数划分该程序有一个主函数和多个子函数，主函数完成对子函数的调用，各子函数实现相应的功能。

子函数：（1）结点的开辟。

（2）实现对输入字符串中出现的不同字符及其出现字数的信息记录。

（3）用叶子结点构造赫夫曼树。

（4）获得构造的赫夫曼树中所有叶子结点的元素及其赫夫曼编码。

（5）输出各叶子结点元素及其对应的赫夫曼编码。

（6）输出输入的字符串的赫夫曼编码。

（7）调用各子函数四详细设计（算法、流程图、程序）<一>算法<1>创建存储叶子结点元素及其权值的链表定义结构体node，其数据成员包括，字符型的元素a和整型元素b和指向node的next指针，来存储叶子结点的内容和权值。

定义三个指向node的指针head、p1、p2和字符指针n、t、,p2->b=r,p1->next=p2,p1=p2,n++,t回到字符串首；否则i++（i 为整型，初始值为1）r=0，j=1；让t指向字符串第一个元素，当*t！=‘\0’，如果*t==*n，r++，t++；让h指向字符串的第一个元素，当h！=n时如果*,p2->b=r,p1->next=p2,p1=p2;n++,当把最后一个结点连入链表中，p1->next=NULL,然后把p1=（起标记作用）、和指向左、右孩子及父母结点的指针lchild、rchild和parent。

定义指向node1的指针p0、p1、p2、p3、p4和整型的m、n、i、j、k1、k2，n=0、p=++，p=p->next，开辟可以存储2*n个node1的顺序表，让p0指向表头，p1=p0,p=-1,j=0,当j<2，如果j==0把‘‘1’赋给k1；否则把‘1’赋给k2；p2=p0，当p2！=p1时，如果p2->sign==NULL并且m=p2->weight用break结束循环否则p2++；p2=p0，当p2！=p时，如果m>=p2->weight并且p2->sign==NULL,把p2->weight赋给m，否则p2++；把p0赋给p2，当p2不等于p1时，如果m等于p2->weight并且p2->sign等于NULL，把‘1’赋给p2->sign,如果j=0，把p2赋给p1->lchild,p2->weight赋给p1->weight,p1赋给p2->parent,用break结束循环；如果j==1，则把p2赋给p1->rchild,p1->weight加p2->weight赋给p1->weight,p1赋给p2->parent,用break结束循环；如果j等于0，k1++，p2++；如果j等于1，k2++，p2++；j++；如果k1大于k2把p1->lchild赋给p3，p1->rchild赋给p4，p4赋给p1->lchild,p3赋给p1->rchild,p1->sign=NULL,p1++,i++;然后p--，把p1->parent=NULL,p1++,把p0赋给p2，当p2不等于p时输出p2的各数据项，拍p2++；返回p0。

<3>获得各叶子结点的赫夫曼编码定义只存储赫夫曼编码的结构体code，它的数据项有字符型的a （存储‘0’、‘1’编码）以及指向下一个结点的指针next。

定义结构体huffmancode，它的数据项有字符型a(存储叶子结点元素)、指向结构体code的指针head。

设指向node1的指针p1、p2、p4，指向huffmancode的指针l、l1和指向code的指针h、++，（n为整型，初始化为零），p2++；调用malloc函数开辟可以存储n+1个huffmancode结点的顺序表，让l指向该顺序表的表头，把l赋给l1，把p赋给p4，当p4->lchild和p4->rchild同时为NULL把p4赋给p1调用setcode（）函数开辟一个结点让h1指向该结点，把h1赋给l1->，p->++，+1个字符的栈，让base指向栈底，top=base,把h=p->（n为整型）p1=p0（p0为形参）当p1->a!=NULL时，如果p1->a等于*p把p1->+1个字符的栈底，top=base，把p1->，如果n等于1，p=p->next,输出p->a和p->b,否则，以p为实参调用settree（p），将返回值赋给p1，以p1为实参调用gethuffmamcode（p1）函数，将返回值赋给p2（p2为指向huffmancode的指针），以p2为实参调用printhuffmancode（p1）函数，然后以a，p2为实参调用print（a，p2）函数。

coutdata()函数的算法：设指向node的指针p，把head->next赋给p，当p！=NULL时n++，p=p->next;返回n。

<7>主函数调用control（）函数。

<二>流程图创建存储叶子结点元素及其权值的链表setnode函数构造赫夫曼树p2->sign j==0?<3>获得各叶子结点的赫夫曼编码setcode函数<4>输出各叶子结点的赫夫曼编码<5>输出字符串的赫夫曼编码p1->a= =*p?<6>control函数countdata()函数<7>主函数程序的编译环境是Visual studio 2010把统计叶子结点元素和权值的函数放在‚计算权值. p;}listnode getdata(char *a) *统计输入字符串中的不同字符及其出现的次数的函并且把统计出的数据，作为叶子结点的元素和权值*{listnode ,*t,*=a;*n!='\0';n++){if(n==a){p2=setnode();for(t=n;*t!='\0';t++) 统计相同的字符在字符串中出现的次数if(*t==*n)r++;p2->a=*n;p1->next=p2;p1=p2;}else{i++;r=0;j=1;for(t=a;*t!='\0';t++)if(*t==*n)r++;for(;)break;elsej++;}if(i==j){p2=setnode(); 调用setnode（）函数开辟结点p2->a=*n;p2->b=r;p1->next=p2;p1=p2;}}}p1->next=NULL;cout<<"电文的长度为："<<i<<endl;cout<<""<<endl;p1= =0;for(p=++;return n;}把构造赫夫曼树的函数放在头文件‚构造赫夫曼树.; 结点的权值和结点的标记struct node1 *parent,*lchild,*rchild; 指向父母结点和左、右孩子的指针}*listnode1; 指向node1的指针listnode1 settree(listnode ,i,j,k1,k2;struct node1 *p3,*p4;n=0;for(p=++;p0=(listnode1)malloc(2*n*sizeof(node1)); 开辟可以存储2n个赫夫曼树结点的顺序表for(p==NULL;p1++;}for(i=1;i<=n-1;i++){for(j=0;j<2;j++){if(j==0)k1=1;else if(j==1) k2=1;for(p2=p0;p2!=p1;p2++)if(p2->sign==NULL){m=p2->weight;break;}for(p2=p0;p2!=p1;p2++)if(m>=p2->weight)if(p2->sign==NULL)m=p2->weight;for(p2=p0;p2!=p1;p2++){if(m==p2->weight)if(p2->sign==NULL){p2->sign=1;if(j==0) 把先找到的权值最小的作为左孩子{p1->lchild=p2;p1->weight=p2->weight;p2->parent=p1;}else if(j==1) 把后找到的权值最小的最为右孩子{p1->rchild=p2;p1->weight=p1->weight+p2->weight;p2->parent=p1;}break;}if(j==0)k1++; 标记先找到的权值最小的结点在顺序表中的位置 else if(j==1)k2++; 标记后找到的权值最小的结点在顺序表中的位置 }}if(k1>k2) *如果先找到的权值最小的结点在顺序表中的位置在后找到的后面{ 则他们父母结点的左右孩子指针交换*p3=p1->lchild;p4=p1->rchild;p1->lchild=p4;p1->rchild=p3;}p1->sign=NULL;p1++;}p1--;p1->parent=NULL;p1++;p2=p0;cout<<"叶子结点"<<"\t"<<"权值"<<"\t"<<"左孩子"<<"\t\t"<<"父母结点"<<"\t"<<"右孩子"<<endl; 输出构造的赫夫曼树while(p2!=p1){cout<<p2->a<<"\t\t"<<p2->weight<<"\t"<<p2->lchild<<"\t"<<p2->parent<<"\t"<<p2->rchild<<endl;p2++;}cout<<""<<endl;return p0;}把叶子结点赫夫曼编码的获取的函数放在头文件‚获得赫夫曼编码. p;}listhuffmancode gethuffmancode(listnode1 p) 把得到的叶子结点及其{ 赫夫曼编码存到顺序表中的函数listnode1 p1,p2,p4;int n=0;listhuffmancode l,l1;listcode ++;l=(listhuffmancode)malloc((n+1)*sizeof(+1个叶子结点信息的顺序表l1=l;for(p4=p;p4->lchild==NULL&&p4->rchild==NULL;p4++){p1=p4;l;}把输出赫夫曼编码的函数放在头文件‚‚输出赫夫曼编码.;char *base,*top;cout<<"叶子结点"<<"\t"<<"权值"<<endl;for(p==0;++;base=(char *)malloc((n+1)*sizeof(char));top=base;;char *base,*top,*p2;cout<<"电文内容：";for(p2=p;*p2!='\0';p2++)cout<<*p2;cout<<endl;cout<<"电文的赫夫曼编码：";for(;*p!='\0';p++){n=0;for(p1=p0;p1->a!=NULL;p1++)if(p1->a==*p){++;base=(char *)malloc((n+1)*sizeof(char));top=base;;cout<<"接受到的电文内容（不超过20个字符）：";cin>>a;listnode p;p=getdata(a);n=coutdata(p);if(n==1) 如果只有一个叶子结点，说明该叶子结点就是根结点，无法构造赫夫曼树{p=p->next;cout<<"该树只有一个叶子结点即根结点（根结点没有赫夫曼编码）>>"<<endl;cout<<"根结点"<<"\t\t"<<"权值"<<endl;cout<<p->a<<"\t\t "<<p->b<<endl;cout<<""<<endl;}else{listnode1 p1;p1=settree(p);listhuffmancode p2;p2=gethuffmancode(p1);printhuffmancode(p2);print(a,p2);}cout<<endl<<"程序结束................"<<endl; }主函数放在源文件‚赫夫曼编码.cpp‚中#include<iostream>#include"控制函数.(){control(); 调用control函数}五调试结果六课程设计总结本次课程设计的目的是：把一个随机输入的字符串中不同字符作为叶子结点元素，把其在该字符串中出现的次数作为权值构造一个赫夫曼树，并得到各个叶子结点的赫夫曼编码和整个输入的字符串的赫夫曼编码。

霍夫曼编码设计实验报告

一、实验目的1. 理解霍夫曼编码的基本原理和算法流程。

2. 掌握霍夫曼编码的构建过程和编码方法。

3. 通过实验验证霍夫曼编码在数据压缩方面的效果。

4. 提高编程能力和数据结构应用能力。

二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发工具：Visual Studio 2019三、实验原理霍夫曼编码是一种基于字符出现频率进行编码的数据压缩方法。

其基本原理如下：1. 对字符进行统计，得到每个字符出现的频率。

2. 根据频率对字符进行排序，频率高的字符排在前面。

3. 构建霍夫曼树，将频率高的字符放在树的左侧，频率低的字符放在树的右侧。

4. 从树根到叶子节点，为每个字符分配一个二进制编码，频率高的字符用较短的编码表示，频率低的字符用较长的编码表示。

四、实验步骤1. 定义一个结构体HuffmanNode，用于存储字符及其频率。

2. 实现一个函数用于统计字符频率。

3. 实现一个函数用于构建霍夫曼树。

4. 实现一个函数用于生成霍夫曼编码。

5. 实现一个函数用于解码霍夫曼编码。

6. 编写主函数，进行实验验证。

五、实验过程1. 定义结构体HuffmanNode，用于存储字符及其频率。

```cppstruct HuffmanNode {char ch;int weight;HuffmanNode lchild, rchild;};```2. 实现一个函数用于统计字符频率。

```cppvoid StatFrequency(char str, int freq) {int length = strlen(str);for (int i = 0; i < 256; ++i) {freq[i] = 0;}for (int i = 0; i < length; ++i) {freq[(int)str[i]]++;}}```3. 实现一个函数用于构建霍夫曼树。

```cppHuffmanNode CreateHuffmanTree(int freq, int length) {HuffmanNode nodes = new HuffmanNode[length + 1];for (int i = 0; i < length; ++i) {nodes[i].ch = 'a' + i;nodes[i].weight = freq[i];nodes[i].lchild = nullptr;nodes[i].rchild = nullptr;}for (int i = length; i < length + 1; ++i) {nodes[i].ch = '\0';nodes[i].weight = 0;nodes[i].lchild = nullptr;nodes[i].rchild = nullptr;}for (int i = 0; i < length - 1; ++i) {HuffmanNode minNode1 = &nodes[0];HuffmanNode minNode2 = &nodes[1];for (int j = 0; j < length + 1; ++j) {if (nodes[j].weight < minNode1->weight) {minNode2 = minNode1;minNode1 = &nodes[j];} else if (nodes[j].weight < minNode2->weight && nodes[j].weight > minNode1->weight) {minNode2 = &nodes[j];}}nodes[i].weight = minNode1->weight + minNode2->weight;nodes[i].lchild = minNode1;nodes[i].rchild = minNode2;minNode1->parent = &nodes[i];minNode2->parent = &nodes[i];}return &nodes[length - 1];}```4. 实现一个函数用于生成霍夫曼编码。

数据结构实验实验报告Huffman赫夫曼编码及应用

实验报告课程名称：数据结构实验名称：赫夫曼编码及应用院（系）：计算机与通信工程学院专业班级：计算机科学与技术姓名：学号：指导教师：2020 年 5 月12 日一、实验目的掌握赫夫曼树和赫夫曼编码的基本思想和算法的程序实现。

二、实验内容及要求1、任务描述a.提取原始文件中的数据（包括中文、英文或其他字符），根据数据出现的频率为权重，b.构建Huffman编码表；c.根据Huffman编码表对原始文件进行加密，得到加密文件并保存到硬盘上；d.将加密文件进行解密，得到解码文件并保存点硬盘上；e.比对原始文件和解码文件的一致性，得出是否一致的结论。

2、主要数据类型与变量a.对Huffman树采用双亲孩子表示法，便于在加密与解密时的操作。

typedef struct Huffman* HuffmanTree;struct Huffman{unsigned int weight; //权值unsigned int p, l, r;//双亲，左右孩子};b．对文本中出现的所有字符用链表进行存储。

typedef struct statistics* List;struct statistics {char str; //存储此字符int Frequency; //出现的频率（次数）string FinalNum; //Huffman编码struct statistics* Next;};3、算法或程序模块对读取到的文本进行逐字符遍历，统计每个字符出现的次数，并记录在创建的链表中。

借助Huffman树结构，生成结构数组，先存储在文本中出现的所有字符以及它们出现的频率（即权值），当作树的叶子节点。

再根据叶子节点生成它们的双亲节点，同样存入Huffman树中。

在完成对Huffman树的创建与存储之后，根据树节点的双亲节点域以及孩子节点域，生成每个字符的Huffman编码，并存入该字符所在链表节点的FinalNum域。

赫夫曼编码实验报告

实验五哈夫曼树和哈夫曼树编码学院专业班学号姓名一．实习目的1.掌握哈夫曼树的顺序存储方式；2.掌握建立哈夫曼树的方法；3.掌握由哈夫曼树构造哈夫曼编码的方法。

二．实习内容1.建立哈夫曼树的顺序存储结构；2.编程实现构建一棵哈夫曼树。

3.编程实现由哈夫曼树构造出哈夫曼编码三．实习步骤1. 程序代码#include<malloc.h> // malloc()等#include<limits.h> // INT_MAX等#include<stdio.h> //#include<stdlib.h> //#include<string.h>typedef struct{unsigned int weight;unsigned int parent,lchild,rchild;}HTNode,*HuffmanTree; // 动态分配数组存储赫夫曼树typedef char **HuffmanCode; // 动态分配数组存储赫夫曼编码表int min(HuffmanTree t,int i){ // 返回i个结点中权值最小的树的根结点序号，函数select()调用int j,flag;unsigned int k=UINT_MAX; // 取k为不小于可能的值(无符号整型最大值) for(j=1;j<=i;j++)if(t[j].weight<k&&t[j].parent==0) // t[j]是树的根结点k=t[j].weight,flag=j;t[flag].parent=1; // 给选中的根结点的双亲赋1，避免第2次查找该结点return flag;}void select(HuffmanTree t,int i,int &s1,int &s2){ // 在i个结点中选择2个权值最小的树的根结点序号，s1为其中序号小的那个int j;s1=min(t,i);s2=min(t,i);if(s1>s2){j=s1;s1=s2;s2=j;}}void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) // 算法6.12{ // w存放n个字符的权值(均>0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC int m,i,s1,s2,start;unsigned c,f;HuffmanTree p;char *cd;if(n<=1)return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用for(p=HT+1,i=1;i<=n;++i,++p,++w){(*p).weight=*w;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;}for(;i<=m;++i,++p)(*p).parent=0;for(i=n+1;i<=m;++i) // 建赫夫曼树{ // 在HT[1～i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2 select(HT,i-1,s1,s2);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;}// 从叶子到根逆向求每个字符的赫夫曼编码HC=(HuffmanCode)malloc((n+1)*sizeof(char*));// 分配n个字符编码的头指针向量([0]不用)cd=(char*)malloc(n*sizeof(char)); // 分配求编码的工作空间cd[n-1]='\0'; // 编码结束符for(i=1;i<=n;i++){ // 逐个字符求赫夫曼编码start=n-1; // 编码结束符位置for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)// 从叶子到根逆向求编码if( HT[f].lchild==c)cd[--start]='0';elsecd[--start]='1';HC[i]=(char*)malloc((n-start)*sizeof(char));// 为第i个字符编码分配空间strcpy( HC[i], &cd [start] ); // 从cd复制编码(串)到HC}free(cd); // 释放工作空间}void main(){HuffmanTree HT;HuffmanCode HC;int *w,n,i;printf("请输入权值的个数(>1): ");scanf("%d",&n);w=(int*)malloc(n*sizeof(int));printf("请依次输入%d个权值(整型):\n",n);for(i=0;i<=n-1;i++)scanf("%d",w+i);HuffmanCoding(HT,HC,w,n);printf("huffman树存储结构：\n");for( i=1;i<2*n;i++)printf("%4d%4d%4d%4d\n", HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);// 输出哈夫曼树的每个结点的权值、父亲结点序号、左孩子和右孩子序号。