《数据结构》实验大纲 课程编码：1512111801 课程名称：数据结构 实验总学时数/学分：16/1 适用专业：信息与计算科学 开课教研室：信息与计算科学教研室 一、实验教学的目的和要求 《数据结构实验》是信息与计算科学专业学生必修的一门专业基础实验课程，它是《数 据结构》课程的重要组成部分。这门课程的主要任务是培养学生的算法设计能力及良好的程 序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际 问题选取合适的存储方案设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打 下良好的基础。学习这门课程，习题和实验是两个关健环节。学生理解算法，上机实验是最 佳的途径之一。因此，实验环节的好坏是学生能否学好《数据结构》的关键。通过实验课程 更好的训练学生算法分析及算法设计的能力。 本课程的主要目的：使学生通过实验来加深对课堂上所学数据结构的基本理论的理解， 增强运用所学理论解决实际问题的能力：使学生掌握数据结构实验的基本操作技能，掌握线 性表、堆栈、队列、串、数组、二叉树、图等典型数据结构的设计方法：了解各种抽象数据 类型的性质：掌握处理各种抽象数据类型的基本算法：重点掌握各种典型数据结构的应用： 了解各种典型排序和查找算法的性能和设计方法：重点掌握程序设计的基本原理和方法：初 步掌握算法的时间分析和空间分析的技术。使学生初步具有独立进行实验的能力，为后续课 程的学习及研究工作的开展和参加实际工作奠定良好的基础： 实验要求： 1.上机前要作好充分准备，根据实验题目编写好源程序。 2.对上机操作过程中可能出现的问题预先分析，确定调试步骤和测试方法，对运行结果 如何分析等。 3.上机实验完成后，认真写出实验报告，对上机中出现的问愿进行分析、总结。 4,上机过程中要遵守实验室的各项规章制度，爱护实验设备，服从指导老师安排。 5.本课程的实验过程中，不得进行游戏、上网等操作。 二、实验项目名称和学时分配
《数据结构》实验大纲 课程编码：1512111801 课程名称：数据结构 实验总学时数/学分：16/1 适用专业：信息与计算科学 开课教研室：信息与计算科学教研室 一、实验教学的目的和要求 《数据结构实验》是信息与计算科学专业学生必修的一门专业基础实验课程，它是《数 据结构》课程的重要组成部分。这门课程的主要任务是培养学生的算法设计能力及良好的程 序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际 问题选取合适的存储方案设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打 下良好的基础。学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最 佳的途径之一。因此，实验环节的好坏是学生能否学好《数据结构》的关键。通过实验课程 更好的训练学生算法分析及算法设计的能力。 本课程的主要目的：使学生通过实验来加深对课堂上所学数据结构的基本理论的理解， 增强运用所学理论解决实际问题的能力；使学生掌握数据结构实验的基本操作技能，掌握线 性表、堆栈、队列、串、数组、二叉树、图等典型数据结构的设计方法；了解各种抽象数据 类型的性质；掌握处理各种抽象数据类型的基本算法；重点掌握各种典型数据结构的应用； 了解各种典型排序和查找算法的性能和设计方法；重点掌握程序设计的基本原理和方法；初 步掌握算法的时间分析和空间分析的技术。使学生初步具有独立进行实验的能力，为后续课 程的学习及研究工作的开展和参加实际工作奠定良好的基础。 实验要求： 1.上机前要作好充分准备，根据实验题目编写好源程序。 2.对上机操作过程中可能出现的问题预先分析，确定调试步骤和测试方法，对运行结果 如何分析等。 3.上机实验完成后,认真写出实验报告,对上机中出现的问题进行分析、总结。 4.上机过程中要遵守实验室的各项规章制度,爱护实验设备,服从指导老师安排。 5．本课程的实验过程中，不得进行游戏、上网等操作。 二、实验项目名称和学时分配
实验类 所 项目 实验 型（演示、验需主要类 是否为 序号 项目名称 内容提要 开放实 学时 证、综合、设仪器设 验 计等) 备 做/选做) 线性表子使用链式存储结构实现 2 线性表的基本操作 验证 计算机 必做 香 系统 分别使用线性表的顺序 多项式求 存储结构和链式存储结 设计 计算机 和 必做 动 构实现 后缀表达 3 利用栈实现 设计 计算机 必做 式求值 以菜单方式显示串的各 4 串子系统 设计 计算机 必做 个功能 标识符树 程序能输出标识符树的 2 5 与表达式 三种遍历序列和表达式 设计 计算机 必做 动 求值 计算的结果 图的连通 选用深度优先搜索或者 设计 计算机 必做 性 是宽度优先搜索 双向骨泡 设计双向目泡排序算法， 输出每一越排序结果。 设计 计算机 必倒 否 排序 合计 16 三、单项实验的内容和要求 实验（一）线性表子系统 实验内容 (1)线性表两种存储结构的基本运算 (②)用结构体类型描述线性表的两种存储结构 (③)完成课堂上所讲的两种存储结构的基本运算 实验要求 (1)掌握线性表的特点 (②)掌握线性表的顺序存储结构和链式存储结构的基本运算 (3)尽可能考虑算法的完整性 (④)实验报告中要写出测试数据、错误分析以及收获。 实验（二）多项式求和 实验内容
序号 项目名称 内容提要 实验 学时 实 验 类 型（演示、验 证、综合、设 计等） 所 需 主 要 仪 器 设 备 项目 类别 （必 做/选做） 是否为 开放实 验 1 线性表子 系统 使用链式存储结构实现 线性表的基本操作 2 验证 计算机 必做 否 2 多项式求 和 分别使用线性表的顺序 存储结构和链式存储结 构实现 2 设计 计算机 必做 否 3 后缀表达 式求值 利用栈实现 2 设计 计算机 必做 否 4 串子系统 以菜单方式显示串的各 个功能 2 设计 计算机 必做 否 5 标识符树 与表达式 求值 程序能输出标识符树的 三种遍历序列和表达式 计算的结果 2 设计 计算机 必做 否 6 图的连通 性 选用深度优先搜索或者 是宽度优先搜索 2 设计 计算机 必做 否 7 双向冒泡 排序 设计双向冒泡排序算法， 输出每一趟排序结果。 4 设计 计算机 必做 否 合计 16 三、单项实验的内容和要求 实验（一） 线性表子系统 实验内容 (1) 线性表两种存储结构的基本运算 (2) 用结构体类型描述线性表的两种存储结构 (3) 完成课堂上所讲的两种存储结构的基本运算 实验要求 (1) 掌握线性表的特点 (2) 掌握线性表的顺序存储结构和链式存储结构的基本运算。 (3) 尽可能考虑算法的完整性 (4) 实验报告中要写出测试数据、错误分析以及收获。 实验（二） 多项式求和 实验内容
对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和 多项式”的一项：对于两个一元多项式中所有指数不相同的项，则分别复抄到“和多项式” 中去。 实验要求 (1)学习和掌握如何运用链表来实现多项式的相加减。 (2)多项式的输入和输出的应注意的要点，规定输出的多项式的顺序。 实验（三）后缀表达式求值 1.实验内容 (1)用键盘输入一个整数后缀表达式。 (2)如果读入的是操作数，直接进入操作数栈。 (3)如果读入的是运算符，立即从操作数栈取出所需的操作数，计算操作数运算的值，并 将计算结果存回操作数栈， (4)检验程序运行结果 2.实验要求 (1)分析后缀表达式求值的算法思想。 (2)上机调试试验程序。 (3)写出具体的算法分析 (4)撰写实验报告 实验（四）串子系统 实哈内容 (1)通过键盘输入建立一个字符串。 (2)编写插入、除、查找、比较、取子字符串、连接字符串、显示、模式匹配等程序。 (3)设计一个选择式菜单，以菜单方式选择上述操作。 2.实验要求 (1)掌握串的特点及顺序定长存储的方式。 (2)掌握串的创建、连接、插入、删除、显示等操作。 (3)掌握串的查找、取子字符串、比较串大小的操作 (4)掌握模式匹配的基本思想及其算法。 实验（五）标识符树与表达式求值 1.实验内容 (1)定义二叉树的结构。 (2)把算术表达式2*3+6/3的标识符树存入一维数组。 (3)求标识符树的前序遍历、中序遍历和后序遍历的序列 (④)以后序计算标识符树的值
对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和 多项式”的一项；对于两个一元多项式中所有指数不相同的项，则分别复抄到“和多项式” 中去。 实验要求 (1) 学习和掌握如何运用链表来实现多项式的相加减。 (2) 多项式的输入和输出的应注意的要点，规定输出的多项式的顺序。 实验（三）后缀表达式求值 1.实验内容 （1）用键盘输入一个整数后缀表达式。 （2）如果读入的是操作数，直接进入操作数栈。 （3）如果读入的是运算符，立即从操作数栈取出所需的操作数，计算操作数运算的值，并 将计算结果存回操作数栈。 （4）检验程序运行结果。 2.实验要求 （1）分析后缀表达式求值的算法思想。 （2）上机调试试验程序。 （3）写出具体的算法分析。 （4）撰写实验报告。 实验（四） 串子系统 实验内容 （1）通过键盘输入建立一个字符串。 （2）编写插入、删除、查找、比较、取子字符串、连接字符串、显示、模式匹配等程序。 （3）设计一个选择式菜单，以菜单方式选择上述操作。 2．实验要求 （1）掌握串的特点及顺序定长存储的方式。 （2）掌握串的创建、连接、插入、删除、显示等操作。 （3）掌握串的查找、取子字符串、比较串大小的操作。 （4）掌握模式匹配的基本思想及其算法。 实验（五）标识符树与表达式求值 1.实验内容 （1）定义二叉树的结构。 （2）把算术表达式 2*3+6/3 的标识符树存入一维数组。 （3）求标识符树的前序遍历、中序遍历和后序遍历的序列。 (4)以后序计算标识符树的值
2.实验要求 (1)掌握二叉树的数组存储方法。 (2)掌握二叉树的非线性特点、递归特点和动态特性。 (3)复习二叉树遍历算法和标识符树的概念。 (4)利用标识符树的后序计算表达式的值 实验（六）图的连通性 1.实验内容 (1)利用MATL4B等语言实现图的连通性判断算法，可对输入的邻接阵进行连通性以及连通 分支数的判断。 (2)比较Warshel1算法和矩阵幂算法在算法正确性和算法复杂度上的区别。 (3)对算法进行优化。 2.实验要求 (1)用计算机语言编写图的连通性判断算法。 (2)输入图的邻接矩阵，判断图是否连通以及确定连通分支的个数。 实验（七）双向冒泡排序 1.实验内容 (1)设计双向目泡排序算法 (2)输出每一趟排序结果。 2.实验要求 (1)顺序存储结构（数组）的排序问题。 (2)用冒泡排序的方法、以数组存储任意给定的个整数并对其进行排序。 (3)然后输出排序前和排序后的结果。 四、使用主用教材及参考书 (一)主用教材： 《实用数据结构基础》主编：陈元春、王中华、张亮、王勇出版社：中国铁道出版 社出版时间：2011年。 (二)参考书： 1.《数据结构》(C语言版)主编：严蔚敏、吴伟民出版社：清华大学出版社出版时 间：2011年。 2.《数据结构》(C语言版)主编：崔进平、郭小春、王霞出版社：清华大学出版社出 版时间：2011年。 3.《数据结构与算法》(C语言版)主编：陈明、王红梅出版社：中国铁道出版社出 版时间：2011年
2.实验要求 （1）掌握二叉树的数组存储方法。 （2）掌握二叉树的非线性特点、递归特点和动态特性。 （3）复习二叉树遍历算法和标识符树的概念。 （4）利用标识符树的后序计算表达式的值。 实验（六） 图的连通性 1. 实验内容 （1）利用 MATLAB 等语言实现图的连通性判断算法，可对输入的邻接阵进行连通性以及连通 分支数的判断。 （2）比较 Warshell 算法和矩阵幂算法在算法正确性和算法复杂度上的区别。 （3）对算法进行优化。 2.实验要求 （1）用计算机语言编写图的连通性判断算法。 （2）输入图的邻接矩阵，判断图是否连通以及确定连通分支的个数。 实验（七） 双向冒泡排序 1.实验内容 （1）设计双向冒泡排序算法。 （2）输出每一趟排序结果。 2.实验要求 （1）顺序存储结构（数组）的排序问题。 （2）用冒泡排序的方法、以数组存储任意给定的 n 个整数并对其进行排序。 （3）然后输出排序前和排序后的结果。 四、使用主用教材及参考书 （一）主用教材： 《实用数据结构基础》 主编：陈元春、王中华、张亮、王勇 出版社：中国铁道出版 社 出版时间：2011 年。 （二）参考书： 1.《数据结构》(C 语言版)主编：严蔚敏、吴伟民 出版社：清华大学出版社 出版时 间：2011 年。 2.《数据结构》(C 语言版)主编：崔进平、郭小春、王霞 出版社：清华大学出版社 出 版时间：2011 年。 3.《数据结构与算法》（C 语言版）主编：陈明、王红梅 出版社：中国铁道出版社 出 版时间：2011 年
五、实验的考核形式 1.实验考核为综合评分制，学期总成绩采用百分制。每个学生的实验课总成绩由平 时成绩和期末成绩组成。 2,平时成绩主要考核学生每次实验时出勒和纪律、预习和课堂提问等：期末成绩主 要考核学生实验动手能力、实验报告书写等各方面的表现。 3.每次试验结束，指导教师根据每一名学生在实验中出勤和纪律、预习和课堂提问、 等方面的表现给出本次试验的平时成绩：根据每一名学生对本次实验要求掌握的各种操作 技术掌握情况给出本次试验的动手能力成绩：根据每一名学生对本次实验报告书写情况给 出实验报告成绩。 4.学期末实验课程全部结束时，指导教师将本学期每一次实验的平时成绩汇总平均， 给出每一名学生本期实验的平时成绩，平时成绩在总成绩中所占比例30%。学期结束指 导教师将本学期每一次实验时学生的动手能力成绩和实验报告成绩汇总平均，给出每 名学生本期实验的期末成绩，期末成绩在总成绩中所占比例70%。 5。指导教师将平时成绩与期末成绩加和给出每一名学生的实验考核总成绩。成绩采 用百分制。 执笔：王晓洁 审定：皮磊梁桂珍
五、实验的考核形式 1．实验考核为综合评分制，学期总成绩采用百分制。每个学生的实验课总成绩由平 时成绩和期末成绩组成。 2．平时成绩主要考核学生每次实验时出勤和纪律、预习和课堂提问等；期末成绩主 要考核学生实验动手能力、实验报告书写等各方面的表现。 3．每次试验结束，指导教师根据每一名学生在实验中出勤和纪律、预习和课堂提问、 等方面的表现给出本次试验的平时成绩；根据每一名学生对本次实验要求掌握的各种操作 技术掌握情况给出本次试验的动手能力成绩；根据每一名学生对本次实验报告书写情况给 出实验报告成绩。 4．学期末实验课程全部结束时，指导教师将本学期每一次实验的平时成绩汇总平均， 给出每一名学生本期实验的平时成绩，平时成绩在总成绩中所占比例 30%。学期结束指 导教师将本学期每一次实验时学生的动手能力成绩和实验报告成绩汇总平均，给出每一 名学生本期实验的期末成绩，期末成绩在总成绩中所占比例 70%。 5．指导教师将平时成绩与期末成绩加和给出每一名学生的实验考核总成绩。成绩采 用百分制。 执笔：王晓洁 审定：皮磊 梁桂珍