《数据结构》实验教学大纲
课程名称：
| 数据结构
|
|
|
课程编号：
| 408009
| 420009
| 436009
|
适用专业：
| 计算机科学与技术
| 网络工程
| 软件工程
|
总 学 分：
| 4
|
|
|
总 学 时：
| 72
|
|
|
其中实验学时
| 30
|
|
|
一、实验的目的与任务
《数据结构》课程是计算机科学与技术专业的一门必修的专业基础课。这门课程的主要特点是实践性很强,不仅要学习基本理论知识,更要注重上机实践,通过上机实践验证算法的正确性,掌握和巩固所学理论知识。通过对本课程中算法设计和上机实践的训练，培养学生的数据抽象能力和程序设计的能力，为后续课程，特别是软件课程打下坚实的知识基础。要求学生掌握各种常用数据结构的逻辑结构，存储结构及有关操作的算法。
通过本实验课程，应达到以下几个教学目的：
1.要求学生了解数据结构及其分类、数据结构与算法的密切关系；
2.熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构；
3.掌握设计算法的步骤和算法分析方法；
4.掌握数据结构在排序和查找等常用算法中的应用
从而深化所学的理论并提高分析问题与解决问题的能力。
二、实验教学的基本要求
通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力，为后续课程，特别是软件课程打下坚实的知识基础。要求学生掌握各种常用数据结构的逻辑结构，存储结构及有关操作的算法。
上机实验要求：
1、准备好上机所需的程序；
2、上机输入和调试自己所编写的程序；
3、上机结束后，应整理出实验报告，实验报告应包括以下内容：实验项目名称；算法分析；程序清单；运行结果；对运行情况所作的分析以及本次调试程序所取得的经验，如果程序未能通过，应分析其原因；
三、实验项目与类型
序号
| 实验项目
| 学时
| 实验性质
| 备注
|
演示
| 验证
| 设计
| 综合
| 必做
| 选做
|
1
| 顺序表的基本操作
| 2
|
| √
|
|
| √
|
|
2
| 链表的基本操作
| 2
|
| √
|
|
| √
|
|
3
| 栈的基本操作
| 4
|
|
| √
|
| √
|
|
4
| 队列的基本操作
| 2
|
| √
|
|
| √
|
|
5
| 串的模式匹配
| 2
|
| √
|
|
| √
|
|
6
| 矩阵的转置
| 2
|
| √
|
|
| √
|
|
7
| 二叉树的遍历（递归）
| 2
|
| √
|
|
| √
|
|
8
| 哈夫曼树与哈夫曼编码
| 2
|
| √
|
|
| √
|
|
9
| 图的最短路径算法
| 4
|
|
| √
|
| √
|
|
10
| 各种排序算法的实现
| 4
|
|
| √
|
| √
|
|
11
| 银行模拟
| 4
|
|
| √
|
| √
|
|
四、实验教学内容及学时分配
实验一 ：顺序表的基本操作(2学时)
1、目的要求：
（1）．掌握使用VC++进行控制台应用程序编写的基本方法；
（2）．掌握顺序表的初始化、销毁、数据元素的插入和删除以及顺序表的输出等基本操作。
2、 方法原理：
顺序表的基本操作
3、 主要实验仪器及材料：
微机与VC环境
4、 掌握要点：
顺序表的插入、删除
5、 实验内容：
顺序表的初始化、插入和删除
实验二 ：单链表的基本操作(2学时)
1、目的要求：
（1）．定义单链表的结点类型。
（2）．熟悉对单链表的一些基本操作和具体的函数定义。
（3）．通过单链表的定义掌握线性表的链式存储结构的特点。
（4）．掌握循环链表和双链表的定义和构造方法
2、方法原理：
线性表的动态处理（链表）
3、主要实验仪器及材料：
微机与VC环境
4、掌握要点：
单链表的插入、删除
5、 实验内容：
链表的创建、插入与删除操作
实验三 ：栈的基本操作(2学时)
1、目的要求：
（1）．会定义顺序栈和链栈的结点类型。
（2）．掌握顺序栈的插入和删除结点在操作上的特点
（3）．熟悉对顺序栈的一些基本操作和具体的函数定义
2、方法原理：
顺序表处理的基本方法
3、主要实验仪器及材料：
微机与VC环境
4、掌握要点：
顺序栈的入栈与弹栈操作
5、 实验内容：
栈的初始化、进栈与出栈等基本操作
实验四 ：队列的基本操作(2学时)
1、目的要求：
（1）．会定义循环队列的结点类型。
（2）．循环队列的插入和删除结点在操作上的特点
（3）．熟悉对循环队列的一些基本操作和具体的函数定义
2、方法原理：
顺序珠处理的基本方法
3、主要实验仪器及材料：
微机与VC环境
4、掌握要点：
循环队列的进队与出队操作操作
5、 实验内容：
循环队列的的初始化、进队与出队操等基本操作
实验五 ：串的模式匹配(2学时)
1、目的要求：
（1）．会定义定长顺序串的存储结构。
（2）．掌握定长顺序串的基本运算
（3）．了解KMP算法
2、方法原理：
顺序表处理的基本方法
3、主要实验仪器及材料：
微机与VC环境
4、掌握要点：
串的基本操作
5、 实验内容：
串的模式匹配算法
实验六 ：矩阵的基本运算(2学时)
1、目的要求：
（1）．了解多维数组的顺序存储结构及其地址计算方式
（2）．了解特殊矩阵和稀疏矩阵的概念
（3）．掌握疏矩阵的压缩存储方式——三元组表
（4）掌握稀疏矩阵的两种转置运算算法
2、方法原理：
顺序表处理的基本方法
3、主要实验仪器及材料：
微机与VC环境
4、掌握要点：
矩阵的基本操作
5、 实验内容：
数组的稀疏矩阵的三元组存储表示与实现
实验七 ：二叉树的基本操作(2学时)
1、目的要求：
（1）．熟悉二叉树结点的结构和对二叉树的基本操作
（2）．掌握对二叉树每一种操作的具体实现
（3）．学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法
2、方法原理：
树处理的基本方法
3、主要实验仪器及材料：
微机与VC环境
4、掌握要点：
二叉树的递归算法
5、 实验内容：
二叉树的创建及各种周游
实验八 ：哈夫曼树与哈夫曼编码(2学时)
1、目的要求：
（1）．了解创建哈夫曼树的基本方法
（2）．掌握通过赫夫曼树进行赫夫曼编码的基本原理和方法
2、方法原理：
树处理的基本方法
3、主要实验仪器及材料：
微机与VC环境
4、掌握要点：
赫夫曼树的创建
5、 实验内容：
赫夫曼树与哈夫曼编码
实验九 ：图的最短路径算法(4学时)
1、目的要求：
（1）．了解无向图的邻接表的存储表示
（2）．掌握通过无向图的邻接表进行无向图的深度优先搜索的基本原理和方法
2、方法原理：
图处理的基本方法
3、主要实验仪器及材料：
微机与VC环境
4、掌握要点：
图的表示与遍历
5、 实验内容：
图的dijkstra算法
实验十 ：各种排序算法(2学时)
1、目的要求：
（1）．掌握排序的基本概念及操作过程
（2）．熟悉各种内部排序的基本原理和操作方法
2、方法原理：
数据排序的基本方法
3、主要实验仪器及材料：
微机与VC环境
4、掌握要点：
各种排序的基本思想
5、 实验内容：
插入排序、希尔排序 、冒泡排序、选择排序 、快速排序算法
实验十一 ：银行模拟(4学时)
1、目的要求：
掌握利用动态链表进行队列的动态事件的模拟
2、方法原理：
线性表处理的基本方法
3、主要实验仪器及材料：
微机与VC环境
4、掌握要点：
动态链队的基本思想
5、实验内容：
银行模拟
五、考核办法
1.学生在做实验之前，指导教师预先告诉学生进行上机实践的题目，要求学生先编写好设计程序，上机时直接输入原程序，再进行调试。
2.实验完成后有些做成实验报告上交，由指导教师批改并评定等次，有些下机时直接由指导教师检查，并给定相关等次。
3.学生实验报告按四个等级评分，实验成绩与上机直接检查的及平时出勤按20%计入平时成绩，上机考试按20%比例计入理论课成绩。
六、实验教学指导书和参考书
实验指导书：自编《数据结构实验指导书》
主要参考书：
[1]严蔚敏,吴伟民.数据结构（C语言版）.北京：清华大学出版社.2006,4
[2] Sartaj Sahni. Data Structure, Algorithms, and Application in C++. The McGraw-Hill田Company Inc.2006(数据结构、算法与应用——C++语言描述.北京:机械工业出版社.2006) [3] Willan Ford,Willian Topp. Data Structures with C++. New Jersey:Prentice Hall Inc, Adivision Simon & Schuster Company,2006(数据结构——C++语言描述.北京:清华大学出版社，2006)
[4]徐孝凯.数据结构实用教程（C/C++描述）.北京:清华大学出版社.2010,12
[5]陈慧南.数据结构（使用C++语言描述）.南京:东南大学出版社.2010,1
主撰人： 朱素英
审核人： 罗如为
2012.6
