数据结构实践

目录

第一章课程设计性质与目的4

第二章设计内容及基本要求.............................5

第三章详细设计说明............................................11

项目一..................................................................7

项目二....................................................................16

项目三....................................................................26

第四章实训总结............................................................37

附录（参考文献、核心代码）

第一章课程设计性质与目的

《数据结构》实训是信息管理与信息系统专业集中实践性环节之一，其目的

就是要达到理论与实际应用相结合，使学生能够根据数据对象的特性，学会数据

组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的

程序设计技能。

链表和顺序表操作的设计目的：1.掌握线性表的在顺序结构和链式结构实

现。2.掌握线性表在顺序结构和链式结构上的基本操作。

二叉树操作的设计目的：1.掌握二叉树的概念和性。2.掌握任意二叉树

存储结构。3.掌握任意二叉树的基本操作。

第二章设计内容及基本要求

一、实验实训的基本要求是：

本实训面向应用，以解决实际问题为主。题目以选用学生相对照较熟悉的为

宜，要求通过本实训，理解有关数据结构的基本概念、不同数据类型的存储和基

本操作的算法实现，理解数据类型的逻辑结构及物理存储结构，通过自己设计，

编程、调试、测试、能够基本掌握在不同存储结构下的算法实现及算法优化，树

立并培养系统规范开辟的理念。实训中学生要将相关课程中学到的知识、思想和

理念尽量应用在实训中。结束后要按规定提交待码和各种文档。

实训基本步骤：

1.选题

设计的课题尽量结合教学、科研的实际课题，规模、大小适当，具有一定复

杂度。应根据题目大小、难度确定是否分组，组内成员人数。

2.数据结构及算法设计

根据需求分析，选择合理的数据结构及设计相应的算法。

3.编码

根据已设计的数据结构和算法，编写代码。

4.测试

按照系统测试的原则'方法和步骤，对系统进行测试。测试中应形成测试报

告。

5.编写实训报告

实训说明书，内容及要求如下：

(1)封面

(2)成绩评定

(3)目录

(4)说明书正文，主要内容包括：

一、设计题目

二、运行环境(软、硬件环境)

三、数据结构及算法设计的思想

四、数据结构及算法设计

五、源代码

六、运行结果分析

七、实习总结(收获及体味)

参考资料：附录(核心代码)。

二、设计内容项目一：顺序表操作

1'设计目的

(1)掌握线性表的在顺序结构上的实现。

(2)掌握线性表在顺序结构上的基本操作

2、设计内容和要求

利用顺序表的插入运算建立顺序表，然后实现顺序表的查找、插入'删除、

计数、输出'排序、逆置等运算(查找、插入、删除、查找、计数'输出、排序、

逆置要单独写成函数)，并能在屏幕上输出操作先后的结果。

项目二：链表操作

1、设计目的

(1)掌握线性表的在链式结构上的实现。

(2)掌握线性表在链式结构上的基本操作

2、设计内容和要求

利用链表的插入运算建立链表，然后实现链表的查找、插入、删除、计数、

输出、排序'逆置等运算(查找、插入、删除、查找、计数、输出'排序、逆置

要单独写成函数)，并能在屏幕上输出操作先后的结果。

项目三：二叉树的基本操作

1、设计目的

(1)掌握二叉树的概念和性质

(2)掌握任意二叉树存储结构。

(3)掌握任意二叉树的基本操作。

2、设计内容和要求

(1)对任意给定的二叉树(顶点数自定)建立它的二叉链表存储结构，并

利用栈的五种基本运算(置空栈、进栈、出栈、取栈顶元素、判栈空)实现二叉

树的先序、中序'后序三种遍历，输出三种遍历的结果。

(2)求二叉树高度、结点数、度为1的结点数和叶子结点数。

第三章详细设计说明

项目一：

顺序表操作:

考查知识点：(1)利用顺序表的插入运算建立顺序表；

(2)实现顺序表的查找、插入、删除、计数'输出、排序、逆置等

运算(查找、插入、删除、查找、计数'输出、排序、逆置要单独

写成函数)；

(3)能够在屏幕上输出操作先后的结果。

一、算法

1.创建：#defineLIST_INIT_SIZE100

#defineLISTINCREMENT20

typedfstruct{

emType*elem;

Iength;

intIistsize;

}SqList;

Status(SqList&L){

=(EIemType*)maIIoc(LIST_INIT_SIZE*sizeof(EIemType));

if(!exit(OVERFLOW);

二0；

=LIST_INIT_SIZE;

returnOk;

}入：StatusListInsert_Sq(SqList&L,inti,EIemTypee){除：Status

ListDeIete_Sq(SqList&L,nti,EIemType&e){

if((i<1||(i»returnERROR;

P=&[iT])；

e=*p;

q=+；找：IntLocateEIem_Sq(SqListL,ElemTypee,构造

插入

删除

排序

计数

查找

逆置

输出

退出

for(;;)

switch(i)

case1:InitList_Sq(L);break;

case2:ListInsert_Sq(L);break;

case3:ListDeIete_Sq(L);break;

case4:Print_Sq(L);break;

case5:ListLength_Sq(L);break;

case6:LocateEIem_Sq(L);break;

case7:inverse_Sq(L);break;

case8:output_Sq(L);break;

case9:Quit_Sq(L);break;

输入有误

)

)

)

三、操作结果

BJX:\Wndows\system3Z,Debug\qwe^xe'IG)m

eo2

项目二：

链表操作

考查知识点：(1)利用链表的插入运算建立链表；

(2)实现链表的查找、插入'删除'计数、输出、排序、逆置等运

算(查找、插入、删除'查找、计数、输出'排序、逆置要单独写

成函数)；

(3)能够在屏幕上输出操作先后的结果。

一、舁法

1.创建:

voidCreateListL(LinkList&L){创建

插

入

删

除

计

数

查

找

排

序

输

出

for(;;)

请在1-8功能中选择一个

0

软

”

不

*弹

2入

3除

4翁

:序

J

;I

・M

W8。S

.

*Cr\Windowc\cyct^m32\Debug\g9

牌修嚣卷的值为“

3

2

为

涉

S3错

选

泽

2?61-4I港2

入

需

需1-

入

要

高3

入

要9

入

用

看23G4

婕

个

狷

蒲

工•3

・4

饴

—

看

口

月

删n-

人

岛3

用964

在

个

选4

J4

&

介

斯

占5

一

港

曲

自

^,点

出

一

」

机

g序

4

2

£”

后

在1-

任意给定的二叉树(顶点数自定)建立它的二叉链表存储结

构；

2利用栈的五种基本运算(置空栈、进栈、出栈、取栈顶元素、

判栈空)实现二叉树的先序、中序、后序三种遍历，输出

三种遍历的结果。

3.求二叉树高度、结点数、度为1的结点数和叶子结点数。

二、算法：

1.创建二叉树：

StatusCreatebitree(bitree&t)序遍历:Status

PreOrderTraverse(BitreeT,Status(*visit)

(TEIemType)){序遍历：StatusInOrderTraverse(Bitree

T,Status(*Visit)(TEIemType)){

InitStack(s);Push(S,T);

WhiIe(!StackEmpty(s){

While(GetTop(s,p)&&p)Push(S,p->IchiId);

Pop(S,p);

If(!StackEmpty(s)){

Pop(s,p);if(!Visit(p->data))retuERROR;

Push(S,p->rchiId);

)

■J"C\Window5\$y$tem32>Debuq\dfhke<e*

『

困

先

需

不4

4

一各节点的值;

建

！

仰.

1,

2,

3,