数据结构课程设计

算法与数据结构。

课程设计报告。

题目：huffman编码。

院（系）：计算机科学与工程学院

专业：计算机科学与技术

班级。学生。

学号。指导教师：潘煜。

2024年 12 月。

任务书。一、题目：huffman编码。

二、要求：1. 界面友好，函数功能要划分好。

2. 总体设计应画一流程图。

3. 程序要加必要的注释。

4. 要提供程序测试方案。

三、课程设计报告要求。

完成设计任务后，应按要求提交课程设计报告。课程设计报告采用a4纸单面打印，并装订成册。

内容包括：1. 问题描述。

2. 算法设计。

描述算法设计思想以及采用的主要数据结构，。

3. 算法实现。

描述系统的运行环境、源**等，应给出各模块对应的流程图。

4. 心得体会。

5. 参考文献。

1.问题描述。

当今社会，计算机技术和通信技术已不断发展，处理和传输的数据量越来越庞大。如何采用有效的数据压缩技术引起了人们的极大重视。从而产生了赫夫曼编码，它是一种应用广泛且非常有效的数据压缩技术，该技术一般可将数据压缩20%至90%，通常我们将压缩技术称为编码，解压缩过程称为解码。

树状结构简称为树，是一种以分支关系进行定义的层次结构，是十分重要的非线性数据结构，在计算机软件设计方面，有着广泛的应用。

在这信息量发达的时代，随着社会的进步，信息不断地增多和更新，为了使信息更加快速、准确有的传递。需要一个程序来完成。

2.算法设计。

赫夫曼编码主要是先建立赫夫曼树，然后利用建好的赫夫曼树生成赫夫曼编码。

目前，进行快速远距离通信的主要手段是电报，即将需传送的文字转换成由二进制的字符组成的字符串。在电文传送时，希望总长度尽可能地短。如果对每个字符设计长度不等的编码，且让电文**现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少。

若要设计长短不等的编码，则必须是任一个字符的编码都不是另一个字符编码的前缀。因此，可以利用二叉树来设计二进制的前缀编码。在二叉树当中，叶子节点表示需要编码的字符，且约定左分支表示字符‘0’，右分支表示字符‘1’，则可以从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码。

设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权，设计一颗赫夫曼树，由此得到的二进制前缀编码便称为赫夫曼编码。

由于赫夫曼树中没有度为1的结点，则一棵有n个叶子结点的赫夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中。在构成赫夫曼树之后，为求编码需从叶子结点出发走一条从叶子到根的路径，对每个结点而言，即需知双亲的信息，又需知孩子的信息。

赫夫曼编码设计功能如下：

1）赫夫曼树抽象数据类型定义。

adt huffmancoding

hc=huffmancoding(ht,hc,w,n);

printf("huffmancode:");

printf("number\t\tweight\t\tcode");

for(i=1;i<=n;i++)

printf("%d\t\t%d\t\t%s",i,w[i],hc[i]);

3）求赫夫曼编码。

if(t[j].weight k=t[j].weight,flag=j; /flag为标志符，为不小于可能的值。

t[flag].parent=1;

4）建赫夫曼树。

ht[s1].parent=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*))为赫夫曼**分配空间。

3.算法实现。

运行环境：microsoft visual c++6.0

源**：#include <>

#include <>

typedef struct

unsigned int weight;

unsigned int parent,lchild,rchild;

htnode,*huffmantree;

typedef char **huffmancode;

typedef struct

unsigned int s1;

unsigned int s2;

mincode;

huffmancode huffmancoding(huffmantree ht,huffmancode hc,unsigned int *w,unsigned int n);

mincode select(huffmantree ht,unsigned int n);

huffmancode huffmancoding(huffmantree ht,huffmancode hc,unsigned int *w,unsigned int n)

unsigned int i,s1=0,s2=0;

huffmantree p;

char *cd;

unsigned int f,c,start,m;

mincode min;

if(n<=1) printf("code too small!")

m=2*n-1;

ht=(huffmantree)malloc((m+1)*sizeof(htnode));

for(p=ht,i=0;i<=n;i++,p++,w++)

for(;i<=m;i++,p++)

for(i=n+1;i<=m;i++)

printf("ht list:");

printf("number\t\tweight\t\tparent\t\tlchild\t\trchild");

for(i=1;i<=m;i++)

printf("%d\t\t%d\t\t%d\t\t%d\t\t%d",i,ht[i].weight,ht[i].parent,ht[i].

lchild,ht[i].rchild);

hc=(huffmancode)malloc((n+1)*sizeof(char *)

cd=(char *)malloc(n*sizeof(char *)

cd[n-1]='0';

for(i=1;i<=n;i++)

free(cd);

return hc;

mincode select(huffmantree ht,unsigned int n)

unsigned int min,secmin;

unsigned int temp;

unsigned int i,s1,s2,tempi;

mincode code;

s1=1;s2=1;

for(i=1;i<=n;i++)

if(ht[i].parent==0)

tempi=i++;

for(;i<=n;i++)

if(ht[i].weight

for(i=tempi;i<=n;i++)

if(ht[i].parent==0&&i!=s1)

for(i=1;i<=n;i++)

if(ht[i].weight

if(s1>s2)

return code;

void main()

huffmantree ht=null;

huffmancode hc=null;

unsigned int *w=null;

unsigned int i,n;

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了