数据结构实验指导书

《数据结构与算法》实验指导书

马晓波 秦俊平 刘利民 编

内蒙古工业大学信息工程学院计算机系

2009年3月1日

《数据结构与算法》实验教学大纲

一、基本信息 课程编码 课程类别 开出单位 二、实验安排 序号 1 ２ ３ 实 验 项 目 线性表的创建与访问算法设计 二叉树的创建与访问算法设计 图的创建与访问算法设计 实验学时 4 4 4 每组人数 1 1 1 实验类型 设计 设计 设计 开出 要求 已开出 已开出 已开出 学科基础课 信息学院计算机系 020213040 实验总学时 适用专业 12 课程学时 开出学期 64 第四学期 计算机科学与技术、软件工程 三、实验目的、内容与要求

实验一 线性表的创建与访问算法设计(4学时)

（一）实验目的

数据结构于算法实验是计算机类本科学生计算机软件知识重要的实验环节，它将使学生从实践上学会用高级语言程序设计、实现复杂的数据结构，为大型软件设计奠定基础。本实验以某种线性表的创建与访问算法设计作为实验内容，举一反三，全面、深刻掌握线性结构的实现方法，培养解决问题的能力。 （二）实验内容

1、编写生成线性表的函数，线性表的元素从键盘输入； 2、编写在线性表中插入元素的函数； 3、编写在线性表中删除元素的函数； 4、编写输出线性表的函数；

5、编写主函数，调用以上各函数，以便能观察出原线性表以及作了插入或删除后线性表的屏幕输出。

方案一采用顺序存储结构实现线性表。

方案二采用单链表结构实现线性表。 （三）实验要求

1、掌握线性结构的机器内表示； 2、掌握线性结构之上的算法设计与实现；

3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度，阐明产生差异的原因。

实验二 二叉树的创建与访问算法设计(4学时)

（一）实验目的

本实验以二叉树的创建与访问算法设计作为实验内容，掌握树型结构的实现方法，培养解决负责问题的能力。 （二）实验内容

1、编写生成二叉树的函数， 二叉树的元素从键盘输入； 2、编写在二叉树中插入元素的函数；

2

3、编写在二叉树中删除元素的函数； 4、编写遍历并输出二叉树的函数。 方案一采用递归算法实现二叉树遍历算法。 方案二采用非递归算法实现二叉树遍历算法。 （三）实验要求

1、掌握树型结构的机器内表示； 2、掌握树型结构之上的算法设计与实现；

3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度，阐明产生差异的原因。

实验三 图的创建与访问算法设计(4学时)

（一）实验目的

本实验以图的创建与访问算法设计作为实验内容，掌握图型结构的实现方法，培养解决负责问题的能力。 （二）实验内容

1、编写生成图的函数， 图的元素从文件输入； 2、编写在图中插入元素的函数； 3、编写在图中删除元素的函数； 4、编写遍历并输出图的函数。

方案一采用BFS深度优先搜索算法实现图的遍历。 方案二采用DFS广度优先搜索算法实现图的遍历。

（三）实验要求

1、掌握图结构的机器内表示；

2、掌握图型结构之上的算法设计与实现；

3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度，阐明产生差异的原因。

四、考核方式

1、学生课前要认真阅读实验教材，理解实验内容与相关理论知识的关系，并完成预习报告； 2、实验课上教师讲解实验难点及需要注意的问题，并对实验数据签字； 3、学生课后要完成实验报告，并将签字的实验数据与实验报告交给带课教师； 4、教师根据学生实验情况，及时对实验内容和方法进行必要的调整和改进。

根据实验预习报告、实验课考勤、课上实验能力与实验效果、实验报告的完成情况确定最终的实验成绩，实验成绩占课程总成绩的10%。 五、建议教材与教学参考书 1、建议教材

[1]严蔚敏、吴伟民主编. 数据结构（C语言版）. 北京：清华大学出版社，1997 2、教学参考书

[1] 严蔚敏、吴伟民主编. 数据结构题集（C语言版）. 北京：清华大学出版社，1997 [2] 李春葆编. 数据结构习题与解析. 北京：清华大学出版社，2002 [3] 刘振鹏主编. 数据结构. 北京：中国铁道出版社，2003 [4] 许卓群编．数据结构．北京：中央电大出版社， 2001

[5] Anany Levitin著．潘彦译．算法设计与分析．北京：清华大学出版社， 2004

3

六、其它说明

实验报告格式参照信息学院实验报告规范要求。

4