《数据结构》实验教学大纲
课程代码： 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．调用上述函数实现下列操作：
