《数据结构》实验教学大纲.doc

《数据结构》实验教学大纲
课程代码： B03203
课程名称： 数据结构
英文名称： Data Structures
课程总学时： 60 （其中理论课 46 学时，实验 14 学时） 学 分： 2.5
课程类别： 必修 课程性质： 专业基础课
先修课程： 计算机导论、Java语言程序设计
面向专业： 软件技术、计算机网络技术
开课单位：软件工程系
一、实验教学的性质地位和任务
数据结构实验课是计算机类专业的一门专业基础实验课，是后续专业课程的基础；该课程的主要任务是：进一步掌握和拓展所学的理论知识，初步掌握解决问题的基本结构以及建立在该结构上的算法，培养学生的综合能力；本课程主要内容包括：线性表及其应用实验，串及其应用实验，树及其应用实验，图及其应用实验，查找实验，内部排序实验；通过本实验课的学习，学生应学会分析研究计算机加工的数据结构的特性，培养数据抽象的能力，训练学生进行复杂程序设计的技能，培养良好程序设计的习惯，初步掌握算法的时间分析和空间分析的技术。
二、实验内容与要求
项目一、线性表及其应用
（1）实验目标
1．加深理解线性表的顺序表示与链式表示的意义和区别，理解不同存储结构下插入与删除操作的算法；
2．熟练掌握线性表的顺序存储方式及其插入、删除等基本操作的算法实现；
3．熟练掌握线性表的链式存储方式及其插入、删除等基本操作的算法实现；
（2）具体内容
1．设计一组输入数据并编写主程序分别调用上述算法（顺序表示的算法为InitList_Sq、ListInsert_Sq、ListDelete_Sq等，链式表示的算法为InitList_L、ListInsert_L、ListDelete_L等），调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解；
2．设计一个可以容纳40位数的求n!的程序。
（3）主要仪器设备与工具
PC机一台/每人。
项目二、栈及其应用
（1）实验目标
1．理解栈的概念；
2．掌握利用数组实现栈的基本操作；
3．应用栈结构来解决表达式求值的问题。
（2）具体内容
1．完成对堆栈中数据的存取（入栈 ,出栈,访问栈中元素）；
2．利用堆栈来实现求前序表达式或后序表达式的方法。
（3）主要仪器设备与工具
PC机一台/每人。
项目三　稀疏矩阵运算
（1）实验目标
掌握三元组法存储稀疏矩阵的方法及相关的基本操作，用数组存放矩阵的三元组，矩阵的行数和列数及非0数据从键盘输入，若两个矩阵不能相乘则输出“Error”
（2）具体内容
编写一个程序实现下列目标。
1．用三元组法存放稀疏矩阵
2．求出矩阵相乘结果
3．输出结果矩阵
（3）主要仪器设备与工具
PC机一台/每人。
项目四、树及其应用实验
（1）实验目标
1．掌握二叉树链表的结构和二叉排序树的建立过程；
2．掌握二叉排序树的插入和删除操作；
3．加深对二叉树的理解。
（2）具体内容
1．编写二叉排序树的基本操作函数
① 查找结点函数 SearchNode（ TREE *tree，int key， TREE **pkpt ， TREE **kpt）
② 二叉排序树插入函数 InsertNode （TREE **tree，int key ）
③ 二叉排序树删除函数 DeleteNode （TREE **tree，int key）
2．调用上述函数实现下列操作
① 初始化二叉树
② 调用插入函数建立二叉排序树
③ 调用查找函数在二叉树中查找指定的结点
④ 调用删除函数删除指定的结点，并动态地显示删除结果。
（3）主要仪器设备与工具
PC机一台/每人。
项目五、图及其应用实验
（1）实验目标
1．掌握图的邻接矩阵、邻接表的表示方法；
2．掌握建立图的邻接矩阵的算法；
3．掌握建立图的邻接表的算法；
4．加深对图的理解。
（2）具体内容
1．编写图的基本操作函数
① 建立图的邻接表，邻接矩阵 Create_Graph（LGraph lg，MGraph mg）
② 邻接表表示的图的递归深度优先遍历 LDFS（LGraph g，int i ）
③ 邻接矩阵表示的图的递归深度优先遍历 MDFS（MGraph g， int i， int vn）
④ 邻接表表示的图的广度优先遍历 LBFS（LGraph g， int s， int n）
⑤ 邻接矩阵表示的图的广度优先遍历 MBFS（LGraph g， int s， int n）
2．调用上述函数实现下列操作
① 建立一个图的邻接矩阵和图的邻接表
② 采用递归深度优先遍历输出图的邻接矩阵
③ 采用递归深度优先遍历输出图的邻接表
④ 采用图的广度优先遍历输出图的邻接表
⑤ 采用图的广度优先遍历输出图的邻接矩阵
（3）主要仪器设备与工具
PC机一台/每人。
项目六、查找实验
（1）实验目标
1．掌握在数组上进行各种查找的方法和算法；
2．深刻理解各种方法的特点，并加以灵活运用。
（2）具体内容
1．编写各种查找方法的基本操作函数
① 无序线性表的顺序查找 search1（ int *k，int n， int key）
② 有序线性表的顺序查找 search2（ int *k ， int n ， int key）
③ 折半查找 bin_search（int *k ， int n ， int key）
2．调用上述函数实现下列操作：
① 对给定的数组E[N]{213，111，222，77，400，300，987，1024，632，555}调用无序线性表的顺序查找函数进行查找。
② 调用有序线性表的顺序查找函数进行查找。
③ 调用折半法查找函数进行查找。
（3）主要仪器设备与工具
PC机一台/每人。
项目七、内部排序实验
（1）实验目标
1．掌握在数组上进行各种排序的方法和算法；
2．理解各种方法的特点，并能灵活运用。
（2）具体内容
1．编写各种排序方法的基本操作函数
① 选择排序 ss_sort（ int e [ ]，int n ）
② 直接插入排序 si_sort（ int e[ ]，int n）
③ 冒泡排序 sb_sort（ int e[ ]，int n ）
④ 二路合并排序 Merge（ int e [ ]，int n ）
2．调用上述函数实现下列操作
① 对给定的数组E[N]={213，111，222，77，400，300，987，1024，632，555}调用选择排序函数进行排序。
② 调用直接插入函数进行排序。
③ 调用冒泡函数进行排序。
④ 调用二路归并排序函数进行排序。
（3）主要仪器设备与工具
PC机一台/每人。

三、学时分配
序
号
实验项目名称
时数
实验
要求
实验
类型
所在实验室
1
线性表及其应用实验
2
必做
设计
计算机实习基地I
2
栈及其应用实验
2
必做
设计
计算机实习基地I
3
稀疏矩阵运算
2
必做
设计
计算机实习基地I
4
树及其应用实验
2
必做
设计
计算机实习基地I
5
图及其应用实验
2
必做
设计
计算机实习基地I
6
查找实验
2
必做
综合
计算机实习基地I
7
内部排序实验
2
必做
综合
计算机实习基地I
四、考核方式与成绩评定
本实验课程采用随堂考查。考查形式中：预习报告、上机调试、实验报告各占20%、50%、30%。
五、大纲说明
1．本大纲实验课时仅为课堂上机课时，要达到大纲要求必须有课外时间保障：课前准备、课堂上机调试与课后上机练习所占时间比为：4：1：2。
2．本实验主要以每个实验项目的实验目标为基准，以实验内容为主要知识点，采用过程式考核。
六、推荐教材及参考书
[1] 朱战立．数据结构——Java语言描述．北京：清华大学出版社，2005．
[2] 严蔚敏，吴伟民．数据结构（C语言版）．北京：清华大学出版，1999．
[3] 李春保．数据结构习题与解析（C语言篇）．北京：清华大学出版社，2001．
执 笔：
审 核：
审 批：
5