数据结构课程设计报告

井冈山大学 电子与信息工程学院 数据结构课程设计报告

( 2012——2013年度第一学期)

课程名称： 数据结构课程设计

题 目 一：6.3“哈夫曼树”的建立及其应用 题 目 二： 3.4.6括号匹配的检验 院 系： 计算机科学系 班 级： 10计本（一）班

姓 名： 刘晓倩 学 号： 100911012 指导教师： 孙凌宇老师 成 绩：

2012 年 月 日

1

数据结构课程设计报告

成 绩 评 定

一、 指导教师评语

二、 成绩

成绩 备注

指导教师： 日 期： 年 月 日

2

数据结构课程设计报告

设计题目<一>： 6.3“哈夫曼树”的建立及其应用 一、设计要求 1．问题描述

设有一段电文由字符集{A,B,C,D,E,F,G,H}组成，各字符在电文中出现的次数集为{5,29,7,8,14,23,3,11}，试设计各字符的哈夫曼编码。

2．需求分析

（1）设计哈夫曼树。具体的构造方法如下：以字符集{A,B,C,D,E,F,G,H}作为叶子结点，以各字符出现的次数{5,29,7,8,14,23,3,11}作为各叶子结点的权值构造一棵哈夫曼树。

（2）设计哈夫曼编码。按照构造出来的哈夫曼树，规定哈夫曼树的左分支为0，右分支为1，则从根结点到每个叶子结点所经过的分支对应的0和1组成的序列便为该结点对应字符的哈夫曼编码。

二、概要设计 1．主界面设计

运行界面如图1所示：

图1哈夫曼编码主菜单

2．存储结构设计

对于哈夫曼编码问题，希望在构造哈夫曼树的同时能方便地实现从双亲结点到左右孩子结点的操作，在进行哈夫曼编码时又要求能方便地实现从孩子结点到双亲结点的操作。因此，本程序选择树的双亲孩子表示法作为哈夫曼树的存储结构，并加入了指示结点权值的信息。

3．系统功能设计

本程序完成了从哈夫曼树的构造到实现并输出哈夫曼编码的过程，分别由两个子程序完成，其设计如下：

3

数据结构课程设计报告

（1）选择权值最小的树。选择权值最小的树由函数Select（）实现。该功能按照哈夫曼树的构造步骤，在当前已构成的n(n>=2)棵二叉树的集合中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树。

（2）哈夫曼编码。哈夫曼编码由函数HuffmanCoding( )实现。该功能首先调用函数Select（）实现哈夫曼树的构造，然后从叶子到根逆向根据哈夫曼编码的要求，一次求出每个字符的哈夫曼编码。

三、模块设计 1．模块设计

本程序包含3个模块：主程序模块、哈夫曼编码模块和选择模块。其调用关系如图2所示。

主程序模块 图2 模块调用示意图

哈夫曼编码模块 选择模块 2．系统子程序及功能设计

本程序共设置3个子程序，各子程序的函数名及功能说明如下。 (1)void Select(HuffmanTree &HT,int m,int *s1,int *s2) //选择权值最小的两个结点

(2)void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) //构造哈夫曼编码

(3)void main( ) //主函数。输入结点个数及权值，调用哈夫曼编码模块函数

3．函数主要调用关系图

本程序3个子程序之间的主要调用关系如图3所示。 图中数字是各函数的编号

3 main（） 2 1

4

图3系统函数调用关系图

数据结构课程设计报告

四、详细设计 1．数据类型定义

typedef struct {

unsigned int weight; //用来存放各个结点的权值 unsigned int parent, lchild, rchild; //指向双亲、孩子结点的指针

}HTNode, *HuffmanTree; //动态分配数组存储哈夫曼树 typedef char * * HuffmanCode; //动态分配数组存储哈夫曼编码表

2．系统主要子程序详细设计

哈夫曼编码模块设计分两步：首先构造哈夫曼树，然后完成哈夫曼编码。 void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)

{//w存放n个字符的权值（均>0)，构造哈夫曼树HT并求出n个字符的哈夫曼编码HC int i,j,m,s1,s2,start; char *cd; unsigned int c,f; if (n<=1) return; m = 2 * n - 1;

HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); //0号单元未用 for (i=1;i<=n;i++) //叶子结点初始化并放入1-n号单元 {

HT[i].weight=w[i]; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; }

for (i=n+1; i<=m;i++) //非叶子结点初始化 {

HT[i].weight=0;

5

数据结构课程设计报告

HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; }

printf(\"\\n哈夫曼树的构造过程如下所示:\\n\");

printf(\"HT初态:\\n 结点 weight parent lchild rchild\");

for (i=1;i<=m;i++) //完成构造哈夫曼树算法的第1个步骤

printf(\"\\n%4d%8d%8d%8d%8d\HT[i].rchild);

printf(\" 按任意键，继续 ...\"); getch();

//创建哈夫曼树HT for (i=n+1;i<=m;i++) {

Select (HT,i-1,&s1,&s2);

//在HT[1..i-1]中选择parent为0且weight最小的两个结点 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;

//置新二叉树的根结点权值为其左、右子树根结点之和 printf(\"\\nselect:s1=%d s2=%d\\n\ //根结点权值最小的树在HT中的位置 printf(\" 结点 weight parent lchild rchild\"); for (j=1;j<=i;j++)

//输出选取根结点权值最小树的过程

printf(\"\\n%4d%8d%8d%8d%8d\

[j].lchild,HT[j].rchild);

printf(\" 按任意键，继续 ...\"); getch();

6

数据结构课程设计报告

}

printf(\"\\n%d个字符的哈夫曼编码如下:\\n\ //从叶子到根逆向求每个字符的哈夫曼编码

HC=(HuffmanCode)malloc((n+1)*sizeof(char *));//分配n个编码的头指针 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'; else cd[--start] = '1';

HC[i] = (char *)malloc((n-start)*sizeof(char)); //为第i个字符编码分配空间

strcpy(HC[i], &cd[start]); //从cd复制编码（串）到HC }

free(cd); //释放工作空间 for(i=1;i<=n;i++)

printf(\"<%2d>编码:%s\\n\ }//HuffmanCoding

五、测试分析

根据设计要求中的问题描述分别输入字符的个数和对应的权值，程序运行得到图4的开始界面。

7

数据结构课程设计报告

图4哈夫曼编码程序开始界面 构造哈夫曼树的过程如图（5~ 12）所示。

图5

图6

图7

8

数据结构课程设计报告

图8

图9

图10

9

数据结构课程设计报告

图11

图12 构造哈夫曼编码如图13所示。

图13 哈夫曼编码

六、用户手册

（1）本程序执行文件为“哈夫曼树的建立及其应用.exe”。

（2）进入本程序之后，分别输入哈夫曼编码字符的个数和对应的权值。

10

数据结构课程设计报告

（3）随即显示哈夫曼树的构造过程，最终显示出对应权值的哈夫曼编码。

七、调试报告

此次课程设计主要是了解哈夫曼树的设计，并学会哈夫曼编码的设计。通过这次课程设计，我学到了课本上以外的许多知识，学会了树相关的基础知识，受益匪浅。

《数据结构》是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。其次是，根据实际问题的需要，对各个方面的优缺点加以综合平衡，从中选择比较适宜的实现方法。比如在选择数据结构的时候，就要求从时间性能和空间性能去考虑，从而使得能编写出更加实用和高效的代码，而要做到这点，就要求对知识点很熟悉。

在这次课程设计中曾遇到了不少问题，比如输入整型变量的时候，没有办法限制其不能输入字符型，还有类型必须前后匹配等等。使我明白了理论与实际相结合的重要性，使我更深刻地意识到：掌握了好的理论并不一定能马上将其运用到自己的程序中，而只有通过不断地学习和实践，不断地运用它，才能熟能生巧！

八、程序清单

#include #include #include #include typedef struct {

unsigned int weight; //用来存放各个结点的权值 unsigned int parent,lchild,rchild; //指向双亲、孩子结点的指针

}HTNode, *HuffmanTree; //动态分配数组存储哈夫曼树 typedef char * * HuffmanCode; //动态分配数组存储哈夫曼编码表 //1.选择权值最小的两个结点

void Select(HuffmanTree &HT,int m,int *s1,int *s2) { int i,min;

for(i=1;i<=m;i++) //在HT[1..i-1]中选择parent为0且weight最小的两个结点 {

11

数据结构课程设计报告

if(HT[i].parent==0) {

min = i;i=m+1; } }

for(i=1;i<=m;i++) //parent为0且weight最小的两个结点，第一个序号为s1 {

if(HT[i].parent == 0) {

if(HT[i].weight < HT[min].weight) min = i; } }

*s1 = min;

for(i=1; i<=m;i++) //在HT[1..i-1]中选择parent为0且weight最小的两个结点 {

if(HT[i].parent == 0 &&i!=(*s1)) {

min = i;i = m+1; } }

for(i=1;i<=m;i++) //parent为0且weight最小的两个结点，第二个序号为s2 {

if(HT[i].parent == 0 &&i!=(*s1)) {

if(HT[i].weight < HT[min].weight) min = i;

}

}

*s2 = min; }//Select

12

数据结构课程设计报告

//2.构造哈夫曼编码

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)

{//w存放n个字符的权值（均>0)，构造哈夫曼树HT并求出n个字符的哈夫曼编码HC int i,j,m,s1,s2,start; char *cd; unsigned int c,f; if (n<=1) return; m = 2 * n - 1;

HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); //0号单元未用 for (i=1;i<=n;i++) //叶子结点初始化并放入1-n号单元 {

HT[i].weight=w[i]; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; }

for (i=n+1; i<=m;i++) //非叶子结点初始化 {

HT[i].weight=0; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; }

printf(\"\\n哈夫曼树的构造过程如下所示:\\n\");

printf(\"HT初态:\\n 结点 weight parent lchild rchild\");

for (i=1;i<=m;i++) //完成构造哈夫曼树算法的第1个步骤

printf(\"\\n%4d%8d%8d%8d%8d\HT[i].rchild);

printf(\" 按任意键，继续 ...\"); getch();

13

数据结构课程设计报告

//创建哈夫曼树HT for (i=n+1;i<=m;i++) {

Select (HT,i-1,&s1,&s2);

//在HT[1..i-1]中选择parent为0且weight最小的两个结点 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;

//置新二叉树的根结点权值为其左、右子树根结点之和 printf(\"\\nselect:s1=%d s2=%d\\n\ //根结点权值最小的树在HT中的位置 printf(\" 结点 weight parent lchild rchild\"); for (j=1;j<=i;j++)

//输出选取根结点权值最小树的过程

printf(\"\\n%4d%8d%8d%8d%8d\

[j].lchild,HT[j].rchild);

printf(\" 按任意键，继续 ...\"); getch(); }

printf(\"\\n%d个字符的哈夫曼编码如下:\\n\ //从叶子到根逆向求每个字符的哈夫曼编码

HC=(HuffmanCode)malloc((n+1)*sizeof(char *));//分配n个编码的头指针 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';

14

数据结构课程设计报告

else cd[--start] = '1';

HC[i] = (char *)malloc((n-start)*sizeof(char)); //为第i个字符编码分配空间

strcpy(HC[i], &cd[start]); //从cd复制编码（串）到HC }

free(cd); //释放工作空间 for(i=1;i<=n;i++)

printf(\"<%2d>编码:%s\\n\ }//HuffmanCoding //3.主函数 void main() {

HuffmanTree myHuffmanTree; HuffmanCode myHuffmanCode;

int *w,i;

int n, wei; //编码个数及权值 printf(\"请输入需要哈夫曼编码的字符个数:\"); scanf(\"%d\

w=(int *)malloc((n+1) *sizeof(int)); for(i=1;i<=n;i++) {

printf(\"请输入第%d字符的权值:\ fflush(stdin); scanf(\"%d\ w[i]=wei; }

HuffmanCoding(myHuffmanTree,myHuffmanCode,w,n); }

15

数据结构课程设计报告

设计题目<二>： 3.4.6括号匹配的检验 一、设计要求 1．问题描述

假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即(()[ ])或[([ ] [ ])]等为正确格式，[( ])或((( ]均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如：考虑下列的括号序列： [ ( [ ] [ ] ) ] 1 2 3 4 5 6 7 8

当计算机接受了第1个括号以后，他期待着与其匹配的第8个括号的出现，然而等来的却是第2个括号，此时第1个括号“[”只能暂时靠边，而迫切等待与第2个括号相匹配的 第7个括号“）”的出现，类似的，因只等来了第3个括号“[”，此时，其期待的紧迫程度较第2个括号更紧迫，则第2个括号只能靠边，让位于第3个括号，显然第3个括号的期待紧迫程度高于第2个括号，而第2个括号的期待紧迫程度高于第1个括号；在接受了第4个括号之后，第3个括号的期待得到了满足，消解之后，第2个括号的期待匹配就成了最急迫的任务了，„„ ，依次类推。可见这个处理过程正好和栈的特点相吻合。

2．需求分析

(1) 输入的形式和输入值的范围：从键盘上以字符串的形式输入括号序列。 (2) 输出的形式：括号匹配或是括号不匹配。 (3) 程序所能达到的功能：检验括号是否匹配。 (4) 测试数据：输入（[ ]（）），结果“匹配”，

输入 [（（ ）]，结果“此串括号匹配不合法”

二、概要设计 1．主界面设计

运行界面如图1所示：

16

数据结构课程设计报告

图1 括号匹配的检验主菜单

2．存储结构设计

对于括号匹配的检验问题，希望在输入一个括号序列后，程序能检测出该括号序列是否匹配，则设置一个栈来实现。当遇到 ( 或 [ 时进栈，遇到 ) 或 ] 时出栈进行匹配检验，如果出现不匹配的情况立即结束，否则继续取下一个字符。如果没有遇到不匹配的情况，最后判断栈是否为空，栈为空，括号匹配,否则不匹配。

3．系统功能设计

本程序完成了输入括号序列后检验括号序列是否匹配，定义栈结构和判断栈的情况有以下说明：

typedef struct{ }

定义栈结构体

Status CreatStack(SqStack &S) 初始条件：栈指针已存在

操作结果：定义空栈并分配存储空间，成功返回ok Status StackEmpty(SqStack S) 初始条件：栈已存在

操作结果：判断是否为空，是返回ok Status Push(SqStack &S,Elem e) 初始条件：栈已存在，e已知

操作结果：将e压入栈中，成功返回ok Status Pop(SqStack &S,Elem &e) 初始条件：栈非空，栈顶元素等于e 操作结果：栈顶元素出栈

Status Bracket(SqStack &S,char *str) 初始条件：空栈已存在，括号串非空 操作结果：输出括号串是否匹配

17

数据结构课程设计报告

void main()

操作结果：在屏幕上显示操作菜单

三、模块设计 1．模块设计

本程序包含2个模块：主程序模块和栈操作模块。其调用关系如图2所示。

主程序模块 栈操作模块 图2 模块调用示意图

2．系统子程序及功能设计

本程序共设置6个子程序，各子程序的函数名及功能说明如下。

(1)Status CreatStack(SqStack &S)//创建空堆栈,栈顶指针和栈底指针相等时,栈为空 (2)Status StackEmpty(SqStack S)//堆栈是否为空 (3)Status Push(SqStack &S,Elem e)//进栈 (4)Status Pop(SqStack &S,Elem &e)//出栈

(5)Status Bracket(SqStack &S,char *str)//检验括号匹配

(6)void main( ) //主函数。输入括号序列，调用栈操作模块函数

3．函数主要调用关系图

本程序6个子程序之间的主要调用关系如图3所示。

6main（） 5

1 2 3 4 图3 系统函数调用关系图

18

数据结构课程设计报告

四、详细设计 1．数据类型定义

typedef struct{

Elem *base; //栈底指针 Elem *top; //栈顶指针

int size; //当前已分配的存储空间

}SqStack; typedef int Status;

2．系统主要子程序详细设计

Status CreatStack(SqStack &S)//创建空堆栈,栈顶指针和栈底指针相等时,栈为空 {

S.base=(Elem *)malloc(STACK_SIZE*sizeof(Elem));

S.top=S.base; S.size=STACK_SIZE; return OK; } //栈顶指针和栈底指针相等,创建空堆栈 Status StackEmpty(SqStack S) //堆栈是否为空 { }

Status Push(SqStack &S,Elem e)//进栈 { }

*S.top=e; //将e赋给栈顶指针 S.top+=1; //栈顶指针向上移加1 return OK;}

19

if(S.top!=S.base)

return ERROR; //栈顶指针和栈底指针不相等，则返回ERROR

return OK;

if(S.top-S.base>=S.size) { //栈满,追加存储空间

S.base=(Elem *)realloc(S.base,(S.size+STACK_INC)*sizeof(Elem)); S.top=S.base+S.size; S.size+=STACK_INC;

数据结构课程设计报告

Status Pop(SqStack &S,Elem &e)//出栈 { }

Status Bracket(SqStack &S,char *str)//检验括号匹配 {

int i=0,flag1=0,flag2; Elem e;

while(str[i]!='\\0') //括号序列不为空 {

switch(str[i]) {

case '(':Push(S,'(');

break; //'('进栈

if(S.top==S.base)

return ERROR; //判断栈是否为空，空则返回ERROR

S.top-=1; //否则栈顶指针下移减1 e=*S.top; //将站顶元素赋给e return OK;

case '[':Push(S,'[');

break; //'['进栈

case ')':{Pop(S,e);

if(e!='(')

flag1=1; //出栈，判断是否为'('，不是则用flag1标记为1

break;

}

case ']':{Pop(S,e);

if(e!='[')

flag1=1; //出栈，判断是否为[''，不是则用flag1标记为1

break;

}

20

default: break;

数据结构课程设计报告

}

}

} if(flag1)

break; //出现不匹配，立即结束循环

i++;

flag2=StackEmpty(S); //flag2判断堆栈是否为空 if(!flag1 && flag2)

printf(\"匹配\\n\");

else

printf(\"此串括号匹配不合法\\n\");

return OK;

五、测试分析

程序的测试分析如图4所示。

图4 程序运行图

六、用户手册

（1）本程序执行文件为“括号匹配的检验.exe”。 （2）进入本程序之后，输入要匹配的括号序列。 （3）显示“匹配”或“此串括号匹配不合法”。

七、调试报告

以前做实验题目的时候总是感觉很难，因为根本就不知道从哪里开始。这次课程设计让我对编程有了新的认识。

21

数据结构课程设计报告

拿到题目的时候也是很困惑，后来看了很多有关的例子，仔细看了书上关于栈的算法的知识，觉得就是上课讲到的一些内容，不是题目难，是自己先把自己吓住了。

后来，参照书上的诸多例子，一个模块一个模块的编写，调试，一个功能一个功能去完善。发现越做越顺利，加上以前的实验中对于改错的经验积累和几个学得不错的同学的帮助，我的程序中的错误也一个一个的顺利解决。

再后来，等我的程序完全做好以后，我竟然可以独立的帮同学修改一些以前根本不知所以然的错误，其实，从这次实验中我认识到，我要学习的还有很多，编程有很多的乐趣也有很多的技巧性和知识性。我将在以后的日子里继续认真的学习知识，积累经验，让自己的编程能力提高。

八、程序清单

#include #include #define OK 1

#define ERROR 0 //定义顺序堆栈

#define STACK_SIZE 100 //存储空间初始分配量 #define STACK_INC 10 //存储空间分配增量 typedef char Elem; typedef struct{

Elem *base; //栈底指针 Elem *top; //栈顶指针

int size; //当前已分配的存储空间

}SqStack; typedef int Status;

Status CreatStack(SqStack &S)//创建空堆栈,栈顶指针和栈底指针相等时,栈为空 {

S.base=(Elem *)malloc(STACK_SIZE*sizeof(Elem));

S.top=S.base; S.size=STACK_SIZE; return OK; } //栈顶指针和栈底指针相等,创建空堆栈 Status StackEmpty(SqStack S) //堆栈是否为空 {

22

数据结构课程设计报告

}

if(S.top!=S.base)

return ERROR; //栈顶指针和栈底指针不相等，则返回ERROR

return OK;

Status Push(SqStack &S,Elem e)//进栈 { }

*S.top=e; //将e赋给栈顶指针 S.top+=1; //栈顶指针向上移加1 return OK;}

if(S.top-S.base>=S.size) { //栈满,追加存储空间

S.base=(Elem *)realloc(S.base,(S.size+STACK_INC)*sizeof(Elem)); S.top=S.base+S.size; S.size+=STACK_INC;

Status Pop(SqStack &S,Elem &e)//出栈 { }

Status Bracket(SqStack &S,char *str)//检验括号匹配 {

int i=0,flag1=0,flag2; Elem e;

while(str[i]!='\\0') //括号序列不为空 {

switch(str[i]) {

case '(':Push(S,'(');

23

if(S.top==S.base)

return ERROR; //判断栈是否为空，空则返回ERROR

S.top-=1; //否则栈顶指针下移减1 e=*S.top; //将站顶元素赋给e return OK;

数据结构课程设计报告

}

}

break; //'('进栈

case '[':Push(S,'[');

break; //'['进栈

case ')':{Pop(S,e);

if(e!='(')

flag1=1; //出栈，判断是否为'('，不是则用flag1标记为1

break;

}

case ']':{Pop(S,e);

if(e!='[')

flag1=1; //出栈，判断是否为[''，不是则用flag1标记为1

break;

}

default: break; } if(flag1)

break; //出现不匹配，立即结束循环

i++;

flag2=StackEmpty(S); //flag2判断堆栈是否为空 if(!flag1 && flag2)

printf(\"匹配\\n\");

else

printf(\"此串括号匹配不合法\\n\");

return OK;

void main(){ //主函数

char temp,flag='y'; while(flag=='y'){

char str[255]; SqStack S;

24

数据结构课程设计报告

printf(\"请输入要匹配的括号序列:\\n\"); scanf(\"%s\

scanf(\"%c\接受输入的回车键 CreatStack(S); Bracket(S,str);

printf(\"您想再试一次吗(按y继续): \"); scanf(\"%c\

printf(\"\\n\");

} printf(\"程序结束.\\n\");

}

25