课程编号：01311050 实验学时：16
实验个数：8 适用专业：计算机科学与技术专业
教材及参考书：杨薇薇，2004，数据结构（第1版），高等教育出版社
大纲执笔人：刘莹 大纲审定人：
一、实验课的性质与任务
数据结构是计算机科学与技术专业最重要的专业基础课，主要用于研究计算机中数
据的组织、存储及运算的学科，它是编写计算机程序的基础，是一门实践性很强的课程。
而数据结构实验课是数据结构课程中重要的实践环节，主要通过试验，培养学生的数据抽象能力和利用有效算法分析解决问题的基本思路和能力，为学生今后进行本专业的软件开发和后继课程打下一个基础。
二、实验课程目的与要求
1．实验目的
《数据结构》实验课程着重应用能力的的培养，围绕“各种类型数据结构与算法设计”主题，研究计算机加工的数据结构的特性，为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法。主要实验目的如下：
（1）加深对数据结构的基本概念的理解；
（2）掌握各种数据结构的内在逻辑关系、存储结构和相应的运算；
（3）能利用C语言实现对各种数据结构运算算法的实现，要求有较强的编程能力。
2．实验要求
（1）作好实验前准备工作，对讨论的算法应事先进行初步程序设计，以提高上机效率。
（2）上机实验时一人一机，独立上机。对程序调试过程中出现的问题应尽量独立解决，以训练学生分析问题和解决问题的能力。
（3）应按时完成上机实验作业。
（4）上机实验应分析实验结果，找出存在的问题，寻找出解决问题的办法并解决问题，从而提高程序设计的能力。
三、实验项目及学时分配
四、实验内容安排：
实验一 顺序表的基本运算实现实验
（综合型实验 2 学时）
1．目的要求
（1）掌握线性表的基本概念和类型定义
（2）掌握顺序表的基本概念、特点和类型定义
（3）熟练掌握对顺序表常用操作方法及其程序实现
2．实验内容
（1）实现线性表的顺序存储结构的建立
（2）实现线性表的顺序存储结构的查找、插入、删除
实验二 单链表的基本运算实现实验
（综合型实验 2 学时）
1．目的要求
（1）掌握单链表的基本概念、特点和类型定义
（2）掌握单链表的基本概念、特点和类型定义
（3）熟练掌握对顺序表常用操作方法及其程序实现
2．实验内容
（1）实现线性表的链式存储结构的建立
（2）实现线性表的链式存储结构的查找、插入、删除
（3）实现基于单链表的简单算法设计
实验三 顺序栈的基本运算实现
（综合型实验 2 学时）
1．目的要求
（1）掌握栈的定义和特点
（2）熟练掌握栈的顺序存储结构的各种运算的方法及其程序实现
（3）掌握数制转换和括号匹配并了解其算法
2．实验内容
（1）栈的顺序存储的表示、存储结构的建立
（2）实现栈的顺序存储结构的入栈、出栈
（3）栈的应用举例：数制转换和括号匹配
实验四 循环队列的基本运算实现
（综合型实验 2 学时）
1．目的要求
（1）掌握队列的定义和特点
（2）熟练掌握循环队列的各种运算的方法及其程序实现
2．实验内容
（1）循环队列存储的表示、存储结构的建立
（2）实现循环队列的入队、出队、判断队满、求队列元素个数
实验五 二叉树的遍历
（应用型实验 2 学时）
1．目的要求
（1）掌握二叉树的定义和基本性质
（2）掌握二叉树的存储结构和二叉树的遍历方法
2．实验内容
（1）二叉树的遍历
实验六 图的遍历
（应用型实验 2 学时）
1．目的要求
（1）掌握图的定义、特性和相关概念
（2）熟练掌握图的存储结构及深度和广度优先遍历方法及其实现
2．实验内容
（1）图的邻接矩阵、邻接表表示
（2）图的深度和广度优先搜索遍历
（3）图的遍历
实验七 查找算法的实现
（应用型实验 2 学时）
1．目的要求
（1）掌握查找的概念、查找分析的办法
（2）熟练掌握顺序查找和二分查找的方法及实现
2．实验内容
（1）顺序查找的实现
（2）二分查找的实现
实验八 排序算法的实现
（应用型实验 2 学时）
1．实验目的
（1）掌握排序的基本概念、稳定排序与不稳定排序
（2）掌握直接插入排序、冒泡排序的方法及其实现
（2）熟练掌握快速排序
（3）掌握各种排序方法的稳定性、时间复杂度和空间复杂度
2．实验内容
（1）直接插入排序
（2）冒泡排序和快速排序
五、考核方式、方法及实验成绩评定方法
采用上机情况、程序质量、实验作业相结合的形式，满分为100分。
1．上机情况（30%）
包括出勤情况、调试表现、是否上网、玩游戏。
2． 程序质量（50%）
3． 实验作业（20%）
六、主要教材及参考书
教 材：杨薇薇，2004，数据结构（第1版），高等教育出版社
参考书：[1] 严蔚敏、吴伟民，1997，数据结构（C语言版），清华大学出版社
[2] 严蔚敏、吴伟民，1999，数据结构习题集（C语言版），清华大学出版社
[3] 李春葆，2002，数据结构（C 语言篇) ：习题与解析，清华大学出版社