数据结构实验教案10文档格式.docx

数据结构实验教案10文档格式.docx

《数据结构实验教案10文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构实验教案10文档格式.docx（18页珍藏版）》请在冰点文库上搜索。

课程名称

数据结构与算法

任课专业班级

计算机科学与技术0711

实验室名称

指导教师

龚雄兴

实验学时

实验时间

实验名称

数据结构的实验安排与要求

实验的目的内容及要求

目的

1、介绍数据结构实验的类型，步骤与要求

2、数据结构实验的安排

3、通过一个具体的实验设计过程，介绍数据结构的要求（准备，实验，报告等）

内容

1、数据结构的实验目标

2、数据结构的安排

3、通过一个实验（逻辑删除法筛选素数）来说明具体的要求

要求

对数据结构实验的步骤与要求有比较清楚的了解；

对数据结构实验安排有足够的认识，以备将来有的放矢

实验的重点和难点

重点

对C++环境的了解与熟练程序的测试

难点

1）对顺序数组来模拟集合的逻辑删除

2）利用类来实现的方法

实现提示

数组的下标代表值，数组中的值代表其是否在集合中，逻辑删除不需要移动元素，可以提高效率。

注意事项

参考文献

[1]王红梅等.数据结构（C++版）实验指导.清华大学出版社.2007

[2]李春葆.数据结构教程上机实验指导.清华大学出版社,2005.7

[3]王严尉敏等.数据结构实验指导.清华大学出版社

NO.2of9

顺序线性表的相关操作（利用线性表筛素数）

学习顺序线性表的存储结构；

掌握顺序线性表的常用操作。

1、建立一个空顺序线性表；

并向其中依次插入2-N的自然数；

2、从顺序表中删除每个结点的倍数结点；

3、输出该线性表（应该是2-N内的素数）

1）顺序线性表的存储结构

2）顺序线性表的插入与删除算法

顺序线性表的插入与删除算法

参考教材中相关内容

NO.3of9

计算机科学与技术071

链接线性表的相关操作

学习链接线性表的存储结构；

掌握链接线性表的常用操作。

1、建立一个空链接线性表；

并依次插入（可分别采用头插/尾插）2-N的自然数；

2、从链接表中删除每个结点的倍数结点；

1）链接线性表的存储结构

2）链接线性表的插入与删除算法

链拉线性表的插入与删除算法

NO.4of9

栈与队的应用

熟悉和掌握栈和队的应用

1）分别建立栈和队的类

2）输入一段含有不同括号的字符，通过过滤将括号存储到队中

3）利用栈进行左右括号的匹配判断

1.栈和队分别用顺序和链接实现

2.利用队过滤输入中的非括号字符，再依次进行匹配处理

栈与队的实现

匹配算法的实现与处理

括号匹配问题关键是栈的应用：

最先出现的右括号一定要与最后出现的右括号进行配对，符合栈的后进先出的特征。

故基本思想是左进右出，判断是否括号是左右匹配的。

建议给出部分匹配代码，重点让学生建立栈与队的类

NO.5of9

练习和掌握二维数组的压缩存储与寻址方式

练习和掌握稀疏矩阵的三元组存储

顺序三元组表稀疏矩阵求转置的方法

首先，随机初始化一个稀疏矩阵（如:

5*6的稀疏矩阵），显示输出；

其次，将其压缩存储于于三元组顺序表中，再显示输出；

最后，直接用三元组表求其转置矩阵并显示输出。

1.稀疏矩阵的初始化建议用随机函数完成（通过指定的行，列数及非零元素个数来随机初始化）。

2.建议定义一个通用的矩阵类和一个三元组表类。

3.三元组表的转置算法要求用改进的算法。

三元组表的存储结构，三元组表的转置算法。

1稀疏矩阵的随机初始化；

2三元组表的直接转置；

3类的结构及调用关系。

计算机中数组是使用连续的一维存储空间，它的访问方式是通过数组的初始地址+偏移来进行的；

多维数组要实现从多维逻辑结构向一维的物理结构的映射；

利用三元组可以压缩存储稀矩阵，并可以直接求其转置矩阵。

1.注意控制产生的随机行，列数在矩阵限定的行，列内；

2.矩阵的输出最好输出成方阵，并能简单说明；

3.三元组的转置要用算法II。

NO.6of9

二叉树的链式存储及相关操作

练习和掌握二叉树的链式存储结构

掌握二叉排序树的插入及建立方法

掌握先序，中序遍历序列构造二叉树的构造方法

掌握二叉树的各种遍历方法，求树的叶子数，深度等算法

首先，随机初始化一个二叉排序树；

其次，进行先序，中序，后序，层序遍历，计算其叶子数及树的深度；

再次，利用先序，中序遍历序列，建立二叉树，并先序遍历；

最后，交换二叉树的所有左右孩子，再中序遍历。

1.定义必要的存储结构，定义二叉树类；

3.编写以下函数：

向二叉排序树插入一个数使其仍然还是二叉排序树；

构造不少于8个元素的二叉排序树；

先序、中序，后序，层序遍历二叉树；

求二叉树的树高和树叶数；

左右子树交换；

利用先序，中序遍历序列，建造二叉树。

4.再利用上述函数：

随机产生若干个自然数，建立二叉排序树，分别按先序，中序进行遍历，计算其树高和叶结点数；

利用先序，中序遍历序列，建造二叉树交换左右子树，再次中序遍历。

二叉树的存储结构，二叉树的相关操作。

1二叉树的构造函数；

2函数间的参数传递方式；

二叉树是一对多的父子关系，其链式表示是用指针来表示结点间的父子关系，由于二叉树是递归定义的，故二叉树的许多操作，都可以用递归算法简单实现。

栈和队是前边的内容，此处可以包含式引用原来的文件,重点在树的相关操作。

1.注意输出产生的随机数，以便于人工验证其正确性；

2.由于输入较多，注意输出数据的说明；

3.如何引用原来已完成的栈或队。

NO.7of9

学习和掌握哈夫曼树的存储结构和哈夫曼编码设计方法

1、对于给定字符的权值，构造相应的哈夫曼树；

2、根据左0右1的原则，对每个叶结点进行编码；

3、依次给出各个结点的哈夫曼编码。

1、N个字符假定编号为0—N-1，权值可由用户直接输入，也可用随机数产生；

2、最后给出各个字符的哈夫曼编码

3、进行简单的时间和空间复杂度的分析；

1、哈夫曼树的存储结构

2、哈夫曼编码的算法

3、哈夫曼树的解码算法

1、哈夫曼树总是由较小的树合并而成；

对每个叶结点而言，其哈夫曼编码是从根到叶的一条特别的路径的编码，注意实际搜索时必须由叶到根进行，逆序输出操作可以用栈来实现，也可以用指针实现。

1、由于要对每个结点进行搜索，建议使用静态链表存储二叉树；

2、由于对父对点，子结点都有相应的操作，故存储结点中，不仅有结点的权值，还要有结点的父，子结点的信息；

3、注意解码时的搜索方向与顺序。

NO.8of9

图的最短路径问题

掌握图的逻辑结构

掌握图的邻接矩阵存储结构

会用Dijkstra算法求单源最短路径问题

根据校园布局情况，初始化图的邻接矩阵，并求指定顶点间的最短路径

1.邻接矩阵直接初始化

2.用户输入始点，则输出到各个顶点的最短路径，若输出入始/终点，只……

3.最好能具有边的编辑功能（增，删，改）

图的存储与最短路径的计算

用户数据的输入，边的编辑

1.顶点的邻接关系表示一图的顶点及边的关系；

2.最短路径经过的顶点，一定也是最短路径点；

1、计算机中无穷大的表示

2、顶点名称与编号间的映射关系

3、用户只输入起始点时的输出方式

NO.9of9

电话通讯录管理

掌握简单的个人通讯录的外存和内存的存储机制；

提供简单的维护功能，如：

插入，删除，编辑，查找，排序等；

能够在外存储器上用文件的方式存储通讯录信息，在系统启动时，能够读入到内存

中进行处理，在系统关闭时，能够重写回外存储器上。

能够进行简单的数据维护，如插入，删除，编辑，查找，排序等，还能自动据呼叫

次数进行排序。

1、定义合适的内，外存中的数据存储结构；

2、采用合适的方式进行数据维护（插入，删除，编辑，查找，排序等）；

3、在适当的时候进行数据更新。

1、数据的存储结构；

2、数据的高效维护方法；

3、数据的高效排序与更新；

通讯录数据，实际上还是一种线性表，无论是外存中还是内存中。

所以，本管理系统，实质上，还是线性表的相关操作，唯一不同的加入了排序、查询及编辑等操作。

1、姓名是否作为关键字；

2、呼叫次数是排序的关键字；

3、当有新的呼叫发生时，是否需要进行全部数据的重排；

4、如何保存或读取最新的数据。

数据结构与算法进度安排

内容

备注

1.1-1.2:

课程概述；

数据结构的兴起与发展；

数据结构的研究对象

1.3-1.4:

数据结构的基本概念；

算法及算法分析；

本章小结

2.1-2.2:

线性表的逻辑结构；

线性表的顺序存储结构及实现

2.2-2.3：

线性表的顺序实现；

线性表的链接存储结构

2.3：

线性表的链接实现；

单链表的主要操作

2.3-2.5：

单链表的操作；

顺序表单链表的比较；

线性表的其它存储方式

3.1：

栈的不同表示、实现及的应用

3.2：

队列的表示、实现及应用

3.3：

串的表示、实现及应用

10

3.1-3.3：

小结；

线性表应用举例

11

4.1-4.2：

多维数组；

矩阵的压缩存储

12

4.2-4.4：

矩阵的压缩存储；

广义表

13

5.1-5.2：

树的逻辑结构；

树的存储结构;

树、森林与二叉树的转换

14

5.3：

二叉树的逻辑结构；

二叉树的性质；

二叉树遍历

15

5.4：

二叉树的存储结构及实现；

二叉排序树及其相关操作

16

5.4-5.5：

二叉树的其它算法

17

5.6：

哈夫曼树及哈夫曼编码；

18

6.1：

:

图的逻辑结构；

图的遍历

19

6.2：

图的存储结构

20

6.3：

图的连通性；

最小生成树

21

6.4：

最短路径问题；

AOV网

22

AOV网与拓扑排序；

AOE网与关键路径

23

7.1-7.2：

查找概述；

线性表的查找技术

24

7.3：

二叉排序树；

平衡二叉树

25

7.4：

散列表的查找技术；

26

8.1-8.2：

排序技术概述；

直接插入排序；

希尔排序

27

8..3：

起泡排序；

快速排序

28

8..4：

简单选择排序；

堆排序

29

8.5-8.6：

归并排序；

各种排序方法的比较；

30

课程总结；

复习