课程编号：135302
课程名称：《数据结构》
实验总学时数：32学时
适用专业：计算机各专业
承担实验室：软件实验室
一、实验教学的目的和要求
本实验课程是与数据结构课程配合的实验课。数据结构是计算机科学中一门综合性的专业核心课。实验教学是该课程教学的一个重要组成部分。通过实验教学，目的是使学生能够使用VC＋＋环境实现各种不同数据结构（物理结构）的建立及其基本的操作，如遍历、查找、插入、删除等。通过实验课程的学习, 加深学生对数据结构基本概念和基本原理的理解, 掌握分析问题, 建立模型,运用程序进行问题求解的方法 。
二、实验项目名称和学时分配
序 号 |
实 验 项 目 名 称 |
实验类型 |
学时数 |
必/选开 |
01 |
常用数据结构的操作 |
设计 |
2 |
必开 |
02 |
线性表的基本操作及应用 |
综合 |
6 |
必开 |
03 |
栈的基本操作和应用 |
设计 |
2 |
必开 |
04 |
串的应用 |
设计 |
2 |
必开 |
05 |
二叉树的基本操作及应用 |
设计 |
4 |
必开 |
06 |
图结构的建立及其基本操作、应用 |
综合 |
6 |
必开 |
07 |
查找的基本操作及应用 |
设计 |
4 |
必开 |
08 |
数据结构课程设计 |
综合 |
6 |
必开 |
合 计 |
|
|
32 |
|
三、单项实验的内容和要求（包括实验分组人数要求）
（一）实验项目名称：常用数据结构的操作
1．实验内容：
（1）定义复数，实现复数的基本操作。
（2）编写查找算法，找出数组中元素的最大值。
2．实验要求：
（1）熟悉数组类型的定义和基本运算的实现方法。
（2）掌握结构体类型的定义方法，理解抽象类型数据的定义。
（3）进一步熟悉VC＋＋环境；掌握函数的定义和调用。
3．实验分组人数要求：每组1人
（二）实验项目名称：线性表的基本操作及应用
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．实验报告：学生实验后应按时完成实验报告。实验报告应包括以下内容：实验题目、实验目的、程序清单、运行结果、实验小结。
