数据结构课程设计 1

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

项目1题目——构建哈夫曼树和给出哈夫曼编码。

项目2题目——校园网络布线最小成本系统。

班级c1102

学号： 11430626150177

姓名吴涛。时间： 2012.12.26

数据结构”是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，而且已成为其他理工专业的热门选修课。它的教学要求是：学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。

另一方面，本课程设计也是复杂程序设计的训练过程，要求学生编写的程序结构清湖和正确易读，符合软件工程的规范。

了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握哈夫曼树的构建和哈夫曼编码的问题分析、程序编码、测试等基本方法和技能。通过对学校校园网布线的问题，可以让我使用数据结构的一些知识来解决校园网布线的最小成本问题，更加熟练掌握无向网的邻接矩阵创建与最小生成树的普里姆算法实现，加深对邻接矩阵和普里姆的理解，培养我们对实际问题的理解和解决问题。

关键词：数据结构；哈夫曼；普里姆。

了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握哈夫曼树的构建和哈夫曼编码的问题分析、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

在数据通信中，需要将传送的文字转换成二进制的字符串，用0，1码的不同排列来表示字符。例如，需传送的报文为“after data ear are art area”，这里用到的字符集为“a，e，r，t，f，d”，各字母出现的次数为。现要求为这些字母设计编码。

要区别6个字母，最简单的二进制编码方式是等长编码，固定采用3位二进制，可分别用对“a，e，r，t，f，d”进行编码发送，当对方接收报文时再按照三位一分进行译码。显然编码的长度取决报文中不同字符的个数。若报文中可能出现26个不同字符，则固定编码长度为5。

然而，传送报文时总是希望总长度尽可能短。在实际应用中，各个字符的出现频度或使用次数是不相同的，如a、b、c的使用频率远远高于x、y、z，自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码。

1）函数huffmantree（）构建哈夫曼树；

将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；

在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

从森林中删除选取的两棵树，并将新树加入森林；

重复②、③步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

2）函数huffmancode（）赫夫曼编码；

依次以叶子节点为出发点，向上回溯左分支生成**0，右分支生成**1；

重复（1）步；

结束。typedef struct

int weight; /权值。

int parent; /父结点下标。

int lchild; /左孩子下标。

int rchild; /右孩子下标。

htnode;

typedef struct

int bit[maxbit];

int start;

hcodetype;

void huffmantree(htnode ht,int n)

int i,j,x1,x2;

int m1,m2;

for(i=1;i<=n-1;++i)//n-1个非叶子结点。

ht[x1].parent=n+i;

ht[x2].parent=n+i;

ht[n+i].weight = ht[x1].weight + ht[x2].weight;

ht[n+i].lchild=x1;

ht[n+i].rchild=x2;

}//外层for循环结束。

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

由此，具体函数如下：

void huffmancode (htnode ht,int n, hcodetype huffcode)

hcodetype cd; int i,j,c,p;

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

for(j=<=n;j++)huffcode[i].bit[j]=

huffcode[i].start=

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

cout< }

图1.1 输入结点并输出哈夫曼编码。

图1.2 提示输入错误并重新输入。

#define maxvalue 9999

#define maxleaf 30

#define maxnode maxleaf*2-1

#define maxbit 20

#include <>

typedef struct

int weight;

int parent;

int lchild;

int rchild;

htnode;

typedef struct

int bit[maxbit];

int start;

hcodetype;

void huffmantree(htnode ht,int n)

int i,j,x1,x2;

int m1,m2;

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

ht[x1].parent=n+i;

ht[x2].parent=n+i;

ht[n+i].weight = ht[x1].weight + ht[x2].weight;

ht[n+i].lchild=x1;

ht[n+i].rchild=x2;

void huffmancode (htnode ht,int n, hcodetype huffcode)

hcodetype cd; int i,j,c,p;

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

for(j=<=n;j++)huffcode[i].bit[j]=

huffcode[i].start=

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

cout< }

void main()

数据结构课程设计 1

数据结构课程设计 1

数据结构课程设计格式 1

数据结构课程设计

其他用户还读了