承担实验室： 软件实验室

一、实验教学的目的和要求

本实验课程是与 数据结构 课程配合的实验课。 数据结构是计算机科学中一门综合性的专业核心课。 实验教学是该课程教学的一个重要组成部分。通过实验教学，目的是使学生能够使用 VC ＋＋环境实现各种不同数据结构（物理结构）的建立及其基本的操作，如遍历、查找、插入、删除等。通过实验课程的学习 , 加深学生对数据结构基本概念和基本原理的理解 , 掌握分析问题 , 建立模型 , 运用程序进行问题求解的方法 。

二、实验项目名称和学时分配

实　验　项　目　名　称

必 / 选开

（二）实验项目名称：线性表的基本操作及应用

1 ．实验内容：

（ 1 ）定义一个包含图书信息（书号、书名、价格）的顺序表，读入相应的图书数据来完成图书信息表的创建，然后统计图书表中的图书个数，同时逐行输出每本图书的信息。

（ 2 ）根据指定的待入库的新图书的位置和信息，将新图书插入到图书表中指定的位置上，最后输出新图书入库后所有图书的信息。

（ 3 ）根据指定的待出库的旧图书的位置，将该图书从图书表中删除，最后输出该图书出库后的所有图书的信息。

2 ．实验要求：

（ 1 ） 理解和掌握顺序表的结构类型定义方法

（ 2 ）掌握建立顺序表的基本方法

（ 3 ）掌握显示顺序表元素的基本方法

（ 4 ）理解和掌握顺序表元素查找、插入和删除算法

3 ．实验分组人数要求：每组 1 人

（三）实验项目名称：栈的基本操作和应用

1 ．实验内容：

（ 1 ）建立顺序栈，实现栈的入栈与出栈等操作

（ 2 ）编写一个数值转换函数

（ 3 ）设计实现一个 n 阶汉诺塔问题的算法

2 ．实验要求：

（ 1 ）熟悉栈的结构

（ 2 ）掌握栈结构上的各种操作

（ 3 ）学会运用栈结构求解问题

3 ．实验分组人数要求：每组 1 人

（四）实验项目名称：串的应用

1 ．实验内容：

医学研究者最近发现了某些新病毒，病毒的 DNA 序列都是环装的，给出病毒 DNA 和人的 DNA 数据，编写算法快速测出这些人是否感染了相应的病毒。

2 ．实验要求：

（ 1 ）掌握字符串的顺序存储方法

（ 2 ）掌握字符串匹配算法 BF 算法或 KMP 算法实现。

3 ．实验分组人数要求：每组 1 人

（五）实验项目名称：二叉树的基本操作及应用

1 ．实验内容：

（ 1 ）按照前序次序建立一棵二叉树

（ 2 ） 用前、中、后序递归遍历的方法遍历二叉树

（ 3 ）求二叉树的深度

（ 4 ） 求二叉树的所有叶子结点数

（ 5 ）对二叉树层次遍历

2 ．实验要求：

（ 1 ）熟悉二叉树结构

（ 2 ）掌握树和二叉树结构上的各种操作

（ 3 ）学会运用二叉树结构求解问题

3 ．实验分组 人数要求：每组 1 人

（六）实验项目名称： 图结构的建立及其基本操作、应用

1 ．实验内容：

（ 1 ）建立图的邻接矩阵或者邻接表存储结构

（ 2 ）编写深度和广度优先遍历算法

（ 3 ）基于广度优先搜索的六度空间理论的验证

2 ．实验要求：

（ 1 ）熟悉图结构

（ 2 ）掌握图结构上的两种遍历算法

（ 3 ）利用图的遍历算法解决问题

3 ．实验分组 人数要求：每组 1 人

（七）实验项目名称：查找表的试验

1 ．实验内容：

根据给定的散列函数和处理冲突的方法，构造散列表，掌握散列表的查找过程和插入过程，根据查找和插入算法构造散列表。

2 ．实验要求：

（ 1 ）熟悉散列表结构

（ 2 ）掌握散列函数的生成方法 , 掌握常规冲突处理办法

（ 3 ） 学会运用散列结构求解问题

3 ．实验分组 人数要求：每组 1 人

（八）实验项目名称：数据结构课程设计

1 ．实验内容：

一篇英文文章存储在一个文本文件中，分别基于线性表、二叉排序树、和哈希表三种不同的存储结构，实现单词词频的统计和单词的检索功能。同时计算不同检索策略下的 ASL ，通过比较 ASL 的大小，对不同检索策略的时间性能做出相应的比较分析。

2 ．实验要求：

（ 1 ）词频统计

（ 2 ）单词检索

3 ．实验分组 人数要求：每组 4 人

四、使用教材及参考书

教材：《数据结构（ C 语言版 第 2 版）》 主编：严蔚敏 李冬梅

出版社：人民邮电出版社 修订时间： 2015 年 2 月

1. 《数据结构习题解析与实验指导（ C 语言描述）》，李冬梅编著，人民邮电出版社

2. 《数据结构学习辅导与实验指导》，王红梅编著，清华大学出版社

3. 《数据结构习题与解答》，罗伟刚 编著，冶金工业出版社

4. 《数据结构习题集与解题指导》，薛哓燕等，科学技术文献出版社，

5. 《算法与数据结构》，范策等编著，机械工业出版社

五、实验的考核形式

实验成绩占课程总成绩的 20% 。

实验成绩由实验预习和表现、实验报告两部分组成。

1 ．实验预习和表现：上机实验前，学生必须对本次实验内容预习。在实验中，教师可根据学生实际操作能力、对实验内容的把握程度、相关知识点扩展能力及学生的课堂纪律、实验态度等方面的表现进行综合考核。

2 ．实验报告：学生实验后应按时完成实验报告。实验报告应包括以下内容：实验题目、实验目的、程序清单、运行结果、实验小结。