数据结构课程设计报告

中南大学信息科学与工程学院。

数据结构》课程设计报告。

报告题目：压缩器/解压器

姓名。班级。

学号。指导教师。

完成时间： 2024年7月11日

为了节省存储空间，常常需要把文本文件采用压缩编码的方式储存。例如：一个包含1000个x的字符串和2000个y的字符串的文本文件在不压缩时占用的空间为节（每个x或每个y占用一个字节，两个字节用来表示串的结尾）。

同样是这个文件，采用游程长度编码（run-length coding），可以存储为字符串1000x2000y，仅为10个字母，占用12个字节。若采用二进制表示游程长度（1000和2000）可以进一步节约空间。如果每个游程长度占用2个字节，则可以表示的最大游程长度为2*pow(16)，这样，上例中的字符串只需要用8个字节来存储。

当要读取编码文件时，需要对其进行解码。由压缩器（compressor）对文件进行编码，由解压器（decompressor）进行解码。

我采用的是长度-游程编码的压缩/解压+霍夫曼编码压缩/解压 (霍夫曼树)的压缩方案。

本程序主要分为4部分：

1．构造霍夫曼树。

给定n个实数w1，w2，．．wn（n≥２）求一个具有n个结点的二叉数，使其带权路径长度最小。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为wpl=(w1*l1+w2*l2+w3*l3+..

wn*ln)，n个权值wi(i=1,2,..n)构成一棵有n个叶结点的二叉树，相应的叶结点的路径长度为li(i=1,2,..n)。

可以证明赫夫曼树的wpl是最小的。(1) 根据与n个权值对应的n个结点构成具有n棵二叉树的森林f=,其中第i棵二叉树ti(1 ≤ i ≤ n)都只有一个权值为wi的根结点，其左、右子树均为空。

2) 在森林f中选出两棵根结点的权值最小的树作为一棵新树的左、右子树，且置新树的根结点的权值为其左、右子树上根结点权值之和。

3) 从f中删除构成新树的那两棵，同时把新树加入f中。

4) 重复第(2)和第(3)步，直到f中只含有一棵为止，此树便为赫夫曼树。

2．霍夫曼编码算法。

根据最优二叉树构造赫夫曼编码，利用赫夫曼树很容易求出给定字符集及其概率(或频度)分布的最优前缀码。赫夫曼编码正是一种应用广泛且非常有效的数据压缩技术。该技术一般可将数据文件压缩掉20％至90％，其压缩效率取决于被压缩文件的特征。

1）用字符s[i]作为叶子，count[i]做为叶子s[i]的权，构造一棵赫夫曼树，并将树中左分支和右分支分别标记为0和1；

2）将从根到叶子的路径上的标号依次相连，作为该叶子所表示字符的编码。该编码即为最优前缀码（也称赫夫曼编码）。

3．霍夫曼译码算法。

依次读人文件的二进制码，从赫夫曼树的根结点(即t[m-1])出发，若当前读人0，则走向左孩子，否则走向右孩子。一旦到达某一叶子t时便译出相应的字符然后重新从根出发继续译码，直至文件结束。

3．二进制转换算法。

将霍夫曼编码存储为二进制文件以及将生成的二进制文件转换为霍夫曼编码以实现压缩的过程。

二．概要设计。

主要定义了两个结构体。

1定义赫夫曼树节点结构体。

typedef struct node

for(i=n;i<2*n-1;i将后n-1个节点赋权值，建树

selectmin(*ht,i,&ht1,&ht2); 每次从前i个节点中选取权值最小的两个节点

ht1->parent=ht2->parent=p;

p->lchild=ht1;

p->rchild=ht2;

p->weight=ht1->weight+ht2->weight;//将两个节点的权值相加存入一个节点

p=p->nextp指向下一个没有存储权值的节点

2．霍夫曼编码算法。

主要**如下：

void totalcoding(char s,codenode hc,char code)

s[k]='0解码完毕，在字符串最后一个单元存入'\0'

四．调试分析。

测试情况。最终的到的字符串，通过与原来的字符串对比，完全一样。说明编码解码成功。

时间复杂度：

构造赫夫曼树：t(n)= o(n)

建立赫夫曼表：t(n)=o(n2)

进行译码：t(n)= o(n)

赫夫曼编码t(n)= o(n)

课程设计总结：

在这次课程设计中，通过对程序的编写，调试和运行，使我更好的掌握了霍夫曼树等数据结构方面的基本知识和各类基本程序问题的解决方法，熟悉了各种调用的数据类型，在调试和运行过程中，加深我对程序运行的环境了解和熟悉的程度，同时也提高了我对程序调试分析的能力和对错误纠正的能力。

这次数据结构的程序设计，对于我来说是一个挑战。我对数据结构的学习在程序的设计中也有所体现。课程设计是培养学生综合运用所学知识，发现问题、提出问题、分析问题和解决问题的过程，锻炼学生的逻辑思维能力和实践能力，是对学生实际工作能力的具体训练和考察过程。

在整个课程程序中，我们充分应用和调用各个程序模块，从而部分实现了此次程序设计的所应该有的功能。就是我在课程设计是比较成功的方面，而在这个过程中，让我感觉收获最大的就是我们都能利用这次课程设计学到很多我们在课本上没有的知识，充分的发挥了我们的主动性，使我们学会了自主学习，和独立解决问题的能力。

很多程序在结构上是独立的，但是本此设计的程序功能不是零散的，它有一个连接是的程序是一个整体，达到这种统一体十分重要，因为这个输出连接是贯穿始终的。

这次的程序软件基本上运行成功，可以简单的输入进行压缩，并且运用简单的数字告诉程序的操作者下一步该如何进行，使得程序规模相对较小，即功能还不很全面，应用也不很普遍。原来数据结构可以涉及很多知识，而不是枯燥无聊的简单的**部分而已，利用数据结构方面的知识，我们可以设计出更完善的软件。

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

其他用户还读了