《数据结构》课程实验教学大纲 Data Structure)course experiment teaching program 一、课程基本信息 课程代码：16162804 课程名称：数据结构 英文名称：Data Structures 实验总学时：10 适用专业：计算机科学与技术、软件工程、信息管理与信息系统。 课程类别：学科基础课 先修课程：程序设计、离散数学 二、实验教学的总体目的和要求 (一)对学生的要求 1.课前，按照任课教师的要求做好预习和准备。 2.实验过程中，遵守实验室的规章制度：按《实验手册》列出的实验内容完成实验， 实现预定的实验目标：注重实验现象与理论分析的结合，及时检查运行结果与实际 情况是否相符，对遇到的问题积极思考，学会善于向老师提问。 3.保存和打印出程序运行结果，并结合程序进行分析。 4.课后，按任课教师的要求撰写和准时提交实验报告：实验报告必须符合广东财经大 学颁布的实验报告模版。 5.学生要透过自身编写和调试程序，真切体会到任何粗枝大叶和思维不缜密都会带来 bg和隐患，从而认识到工匠精神的意义，树立起科技报国的家国情怀和使命担当。 6.学生在实验过程中，应注重感受本课程对软件开发的基础地位，认识到我国系统软 件的薄弱。树立起加强基础，踏实进取，立志专业报国的意识。留意相关算法所蕴 含的思想，注重品味中华文化相关思想在解决实际问题中的作用和智慧。 (二)对教师的要求 1.熟悉实验室的规章制度，并自觉遵守，对学生尽到提醒和监督的责任。 2.熟悉本课程实验的实验环境，并提前通知实验员做好准备。 3.制定完善的实验教学大纲和理论课教学大纲，严格按教学大纲执行教学任务，做到 理论课和实验课在时间上、内容上紧密衔接，互有照应
《数据结构》课程实验教学大纲 《Data Structure》course experiment teaching program 一、课程基本信息 课程代码：16162804 课程名称：数据结构 英文名称：Data Structures 实验总学时：10 适用专业：计算机科学与技术、软件工程、信息管理与信息系统。 课程类别：学科基础课 先修课程：程序设计、离散数学 二、实验教学的总体目的和要求 （一）对学生的要求 1. 课前，按照任课教师的要求做好预习和准备。 2. 实验过程中，遵守实验室的规章制度；按《实验手册》列出的实验内容完成实验， 实现预定的实验目标；注重实验现象与理论分析的结合，及时检查运行结果与实际 情况是否相符，对遇到的问题积极思考，学会善于向老师提问。 3. 保存和打印出程序运行结果，并结合程序进行分析。 4. 课后，按任课教师的要求撰写和准时提交实验报告；实验报告必须符合广东财经大 学颁布的实验报告模版。 5. 学生要透过自身编写和调试程序，真切体会到任何粗枝大叶和思维不缜密都会带来 bug 和隐患，从而认识到工匠精神的意义，树立起科技报国的家国情怀和使命担当。 6. 学生在实验过程中，应注重感受本课程对软件开发的基础地位，认识到我国系统软 件的薄弱。树立起加强基础，踏实进取，立志专业报国的意识。留意相关算法所蕴 含的思想，注重品味中华文化相关思想在解决实际问题中的作用和智慧。 （二）对教师的要求 1. 熟悉实验室的规章制度，并自觉遵守，对学生尽到提醒和监督的责任。 2. 熟悉本课程实验的实验环境，并提前通知实验员做好准备。 3. 制定完善的实验教学大纲和理论课教学大纲，严格按教学大纲执行教学任务，做到 理论课和实验课在时间上、内容上紧密衔接，互有照应
4.认真选好或认真编好实验教材，做到开出的实验项目与教学目标吻合，目的明确 份量适中。 5.备课充分，做到要求学生做的每一个实验自己一定先做，对学生可能遇到的问题了 然于心，有的放矢地布置学生预习和准备，或给出相应提示。 6.在实验课上，耐心指导和启发学生，切实培养学生的实验能力和科学探索精神，加 深对相关理论的理解。维护好课堂纪律，营造出井然有序、生动活泼的课堂氛围。 7.如实填写《实验项目管理手册》，对实验中出现的设备故障及时通报实验员，以便及 时维护 8.按时批阅实验报告，对报告中好的观点和方法要及时鼓励，促使其发扬光大：对报 告中发现的问题要及时指出，提出改进意见。对报告的评分和评语要公正、具体。 9.有义务对实验室建设和规划提供协助，提出建议和意见 10.教师要透过教学中的发生的具体事例，让学生真切体会到任何粗枝大叶和思维 不续密都会给程序带来bg和隐惠，从而让学生认识到工匠精神的意义。 11. 教师要让学生感受到本课程对软件开发的基础地位，认识到我国系统软件的薄 弱。让学生树立起加强基础，踏实进取，立志专业报国的意识。教师要让学生在实 验中品味中华文化相关思想在解决实际问题中的作用和智慧。 (三)对实验条件的要求 安装下列软件的计算机： ①Windows操作系统： ②CodeBlocks或Visual C+6.0. 三、实验教学内容 实验项目一 实验名称：实现单链表各种基本运算的算法 实验内容：编写一个程序，实现顺序表的各种基本运算，包括： 1、初始化单链表： 2、单链表的插入： 3、单链表的输出： 4、求单链表的长度： 5、判断单链表是否为空： 6、输出单链表的第i位置的元素： 7、在单链表中查找一个给定元素在表中的位置： 8、单链表的别除 9、释放单链表
4. 认真选好或认真编好实验教材，做到开出的实验项目与教学目标吻合，目的明确， 份量适中。 5. 备课充分，做到要求学生做的每一个实验自己一定先做，对学生可能遇到的问题了 然于心，有的放矢地布置学生预习和准备，或给出相应提示。 6. 在实验课上，耐心指导和启发学生，切实培养学生的实验能力和科学探索精神，加 深对相关理论的理解。维护好课堂纪律，营造出井然有序、生动活泼的课堂氛围。 7. 如实填写《实验项目管理手册》，对实验中出现的设备故障及时通报实验员，以便及 时维护。 8. 按时批阅实验报告，对报告中好的观点和方法要及时鼓励，促使其发扬光大；对报 告中发现的问题要及时指出，提出改进意见。对报告的评分和评语要公正、具体。 9. 有义务对实验室建设和规划提供协助，提出建议和意见。 10. 教师要透过教学中的发生的具体事例，让学生真切体会到任何粗枝大叶和思维 不缜密都会给程序带来 bug 和隐患，从而让学生认识到工匠精神的意义。 11. 教师要让学生感受到本课程对软件开发的基础地位，认识到我国系统软件的薄 弱。让学生树立起加强基础，踏实进取，立志专业报国的意识。教师要让学生在实 验中品味中华文化相关思想在解决实际问题中的作用和智慧。 （三）对实验条件的要求 安装下列软件的计算机： ①Windows 操作系统； ②CodeBlocks 或 Visual C++6.0 。 三、实验教学内容 实验项目一 实验名称：实现单链表各种基本运算的算法 实验内容：编写一个程序，实现顺序表的各种基本运算，包括： 1、初始化单链表； 2、单链表的插入； 3、单链表的输出； 4、求单链表的长度； 5、判断单链表是否为空； 6、输出单链表的第 i 位置的元素； 7、在单链表中查找一个给定元素在表中的位置； 8、单链表的删除； 9、释放单链表
实验性质：设计性 实验学时：2 实验目的与要求： 1、掌握线性表链式存储的类型定义及实现： 2、掌握线性表在链式存储结构中的各种基本操作。 实验条件：安装下列软件的计算机 1、Windows操作系统； 2、CodeBlocks或Visual C-+6.0 研究与思考： 1、如果是循环链表或是双向链表又如何表示？如何实现各种基本操作？ 2、如果是顺序表又如何表示？如何实现各种基本操作 实验项目二 实验名称：病人看病模拟程序 实验内容： 编写一个程序，反映病人到医院看病排队看医生的情况，程序应该达到的功能 在病人排队过程中，主要重复两件事： (1)病人到达就诊室，将病历交给护士，排到等待队列中候诊。 (2)护士从等待队列中取出下一位病人的病历，该病人进入入诊室就诊。 要求模拟病人等待就诊这一过程。程序采用菜单方式，其选项及功能说民如下： (1)排队一一输入排队病人的病历号，加入到病人排队队列中。 (2)就诊一一病人排队队列中最前面的病人就诊，并将其从队列中删除。 (3)查看排队一一从队首到队尾列出所有的排队病人的病历号。 (4)不再排队，余下依次就诊一一从队首到队尾列出所有的排队病人的病历 号，并退出运行。 (5)下班一一退出运行。 实验性质：设计性 实验学时：2 实验目的与要求： 1、掌握单链队列存储方式的类型定义，掌握单链队列的基本运算的实现。 2、学会根据应用问题的需要选择合适的数据结构，掌握队列的先进先出运算规 则及其在病人看病模拟程序中的应用，理解队列在运算过程中状态的变化。 实验条件：安装下列软件的计算机 1、Windows操作系统： 2、CodeBlocks或Visual C-+6.0
实验性质：设计性 实验学时：2 实验目的与要求： 1、掌握线性表链式存储的类型定义及实现； 2、掌握线性表在链式存储结构中的各种基本操作。 实验条件：安装下列软件的计算机 1、Windows 操作系统； 2、CodeBlocks 或 Visual C++6.0 研究与思考： 1、如果是循环链表或是双向链表又如何表示？如何实现各种基本操作? 2、如果是顺序表又如何表示？如何实现各种基本操作 实验项目二 实验名称：病人看病模拟程序 实验内容： 编写一个程序，反映病人到医院看病排队看医生的情况，程序应该达到的功能： 在病人排队过程中，主要重复两件事： （1）病人到达就诊室，将病历交给护士，排到等待队列中候诊。 （2）护士从等待队列中取出下一位病人的病历，该病人进入入诊室就诊。 要求模拟病人等待就诊这一过程。程序采用菜单方式，其选项及功能说民如下： （1）排队——输入排队病人的病历号，加入到病人排队队列中。 （2）就诊——病人排队队列中最前面的病人就诊，并将其从队列中删除。 （3）查看排队——从队首到队尾列出所有的排队病人的病历号。 （4）不再排队，余下依次就诊——从队首到队尾列出所有的排队病人的病历 号，并退出运行。 （5）下班——退出运行。 实验性质：设计性 实验学时：2 实验目的与要求： 1、掌握单链队列存储方式的类型定义，掌握单链队列的基本运算的实现。 2、学会根据应用问题的需要选择合适的数据结构，掌握队列的先进先出运算规 则及其在病人看病模拟程序中的应用，理解队列在运算过程中状态的变化。 实验条件：安装下列软件的计算机 1、Windows 操作系统； 2、CodeBlocks 或 Visual C++6.0
研究与思考： 1、如果改用循环顺序队列是否合适？如何表示？如何实现？ 2、本实验主要涉及队列的应用，如果实验题目改为“简单编译器的实现（括号 配对检查)”会应用到什么数据结构？课后不妨试着编写该程序。 实验项目三 实验名称：实现二叉树的各种遍历算法 实验内容：用递归和非递归算法实现二叉树的三种遍历 实验性质：设计性 实验学时：2 实验目的与要求： 1、学会二叉树的二叉链表表示，及其创建算法的实现： 2、掌握用递归方法实现二叉树的三种遍历： 3、掌握用非递归方法实现二叉树的三种遍历。 实验条件：安装下列软件的计算机 l、Windows操作系统： 2、CodeBlocks成Visual C++60 研究与思考： 1、二叉树能否采用顺序存储结构？ 2、线索二叉树如何用二叉链表表示，本实验的建树算法如何改进使之实现线索 二叉树的二叉链表表示。 实验项目四 实验名称：采用普里姆算法求最小生成树 实验内容： 编写一个程序，实现： (1)对一个带权无向图，用邻接矩阵或邻接表进行表示，并且用适当的方式在 屏幕上显示该图 (2)采用普里姆算法求出该图的最小生成树，并且用适当的方式在屏幕上显 示该最小生成树。 实验性质：设计性 实验学时：2 实验目的与要求： 1、掌握图的邻接矩阵、邻接表等不同存储形式的表示方法： 2、掌握构成最小生成树的Pim算法的基本思想及其编程实现
研究与思考： 1、如果改用循环顺序队列是否合适？如何表示？如何实现？ 2、本实验主要涉及队列的应用，如果实验题目改为“简单编译器的实现（括号 配对检查）”会应用到什么数据结构？课后不妨试着编写该程序。 实验项目三 实验名称：实现二叉树的各种遍历算法 实验内容：用递归和非递归算法实现二叉树的三种遍历 实验性质：设计性 实验学时：2 实验目的与要求： 1、学会二叉树的二叉链表表示，及其创建算法的实现； 2、掌握用递归方法实现二叉树的三种遍历； 3、掌握用非递归方法实现二叉树的三种遍历。 实验条件：安装下列软件的计算机 1、Windows 操作系统； 2、CodeBlocks 或 Visual C++6.0 研究与思考： 1、二叉树能否采用顺序存储结构？ 2、线索二叉树如何用二叉链表表示，本实验的建树算法如何改进使之实现线索 二叉树的二叉链表表示。 实验项目四 实验名称：采用普里姆算法求最小生成树 实验内容： 编写一个程序，实现： （1）对一个带权无向图，用邻接矩阵或邻接表进行表示，并且用适当的方式在 屏幕上显示该图。 （2）采用普里姆算法求出该图的最小生成树，并且用适当的方式在屏幕上显 示该最小生成树。 实验性质：设计性 实验学时：2 实验目的与要求： 1、掌握图的邻接矩阵、邻接表等不同存储形式的表示方法； 2、掌握构成最小生成树的 Prim 算法的基本思想及其编程实现；
实验条件：安装下列软件的计算机 1、Windows操作系统： 2、CodeBlocks或Visual C-+6.0 研究与思考： 1、课后请改用Kruskal算法求最小生成树。 2、Prim算法、Kruskal算法、贪心算法，这些算法思想与《孙子兵法》、中华 围棋棋理等中华文化所蕴含的思想有何联系？ 实验项目五 实验名称：实现哈希表的相关运算算法 实验内容 1、编写函数实现线性探查HASH表的插入和查找算法。 2、编写主函数完成以下功能： (1)定义一个长度为128的HASH表： (2)随机产生120个0-255之间的不重复的伪随机整数，依次插入到HASH 表中：HASH函数为Hk)Fk0.618mod127 (3)查找存在的和不存在的关键字： (4)编写函数，统计该HASH表的平均查找长度： (5)变换关键字个数，观察平均查找长度的变化： (6)变换HASH函数，观察平均查找长度的变化： (7)编写函数实现HASH表的删除算法。 实验性质：设计性 实验学时：2 实验目的与要求：掌握HASH表的建立和查表技术。 实验条件：安装下列软件的计算机 1、Windows操作系统： 2、CodeBlocks或Visual C+6.0 研究与思考： 试着改用其他方式（如链地址法）处理哈希冲突，完成本实验的相关内容。 实验项目六 实验名称：求各种排序算法的执行时间 实验内容： 编写一个程序，利用随机函数产生20000以上随机整数，对这些整数采取 多种方法进行排序，并显示排序结果，比较相关排序算法的效率。要求采用3
实验条件：安装下列软件的计算机 1、Windows 操作系统； 2、CodeBlocks 或 Visual C++6.0 研究与思考： 1、课后请改用 Kruskal 算法求最小生成树。 2、Prim 算法、Kruskal 算法、贪心算法，这些算法思想与《孙子兵法》、中华 围棋棋理等中华文化所蕴含的思想有何联系？ 实验项目五 实验名称：实现哈希表的相关运算算法 实验内容： 1、 编写函数实现线性探查 HASH 表的插入和查找算法。 2、编写主函数完成以下功能： （1） 定义一个长度为 128 的 HASH 表； （2） 随机产生 120 个 0~255 之间的不重复的伪随机整数，依次插入到 HASH 表中；HASH 函数为 H(k)= k*0.618 mod 127； （3） 查找存在的和不存在的关键字； （4） 编写函数，统计该 HASH 表的平均查找长度； （5） 变换关键字个数，观察平均查找长度的变化； （6） 变换 HASH 函数，观察平均查找长度的变化； （7） 编写函数实现 HASH 表的删除算法。 实验性质：设计性 实验学时：2 实验目的与要求：掌握 HASH 表的建立和查表技术。 实验条件：安装下列软件的计算机 1、Windows 操作系统； 2、CodeBlocks 或 Visual C++6.0 研究与思考： 试着改用其他方式（如链地址法）处理哈希冲突，完成本实验的相关内容。 实验项目六 实验名称：求各种排序算法的执行时间 实验内容： 编写一个程序，利用随机函数产生 20000 以上随机整数，对这些整数采取 多种方法进行排序，并显示排序结果，比较相关排序算法的效率。要求采用 3
种以上方法实现排序（提示，可采用的方法有插入排序、希尔排序、起泡排序 快速排序、选择排序、堆排序、归并排序)。并把排序后的结果保存在不同的文 件中。 实验性质：综合性 实验学时：不占用课内学时，要求学生课外完成。 实验目的与要求： 1、掌握插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并 排序等各种排序方法的基本思想及其C语言实现： 2、学会用科学的方法进行实验数据的整理、比较和研究。 1、Windows操作系统： 2、CodeBlocks或Visual C+6.0 研究与思考： 不妨针对各种查找算法的执行时间进行类似的研究。 四、考核方式 1、对上述六次实验从下述四个方面进行考核 ①预习与准备情况(10%) ②上机情况(30%)一一包括出勤情况、调试表现、是否上网玩游戏。 ③程序质量(40%) ④实习报告(20%)一一是否按时提交以及撰写质量 2、对上述六次考核进行综合评价，按百分制形成实验总评成绩。 3、实验成绩占整个课程成绩的比例： ①本课程期末设有笔试，该场考试成绩占整个课程成绩的70%： ②平时成绩占整个课程成绩的30%，平时成绩从作业完成情况、期中测验情况、 实验情况、出勤情况、课堂表现几个方面进行考核。 ③实验情况占平时成绩的23，亦即占整个课程成绩的20%。 五、推荐实验教材和教学参考书 教材： 《数据结构教程（第5版）上机实验指导》，李春葆编著，清华大学出版社，2015 年8月第1版。 参考书： ①《数据结构题集》严蔚敏、吴伟民、米宁编著，清华大学出版社，2015年8月
种以上方法实现排序（提示，可采用的方法有插入排序、希尔排序、起泡排序、 快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文 件中。 实验性质：综合性 实验学时：不占用课内学时，要求学生课外完成。 实验目的与要求： 1、掌握插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并 排序等各种排序方法的基本思想及其 C 语言实现； 2、学会用科学的方法进行实验数据的整理、比较和研究。 1、Windows 操作系统； 2、CodeBlocks 或 Visual C++6.0 研究与思考： 不妨针对各种查找算法的执行时间进行类似的研究。 四、考核方式 1、对上述六次实验从下述四个方面进行考核： ① 预习与准备情况（10%） ② 上机情况（30%）——包括出勤情况、调试表现、是否上网玩游戏。 ③ 程序质量（40%） ④ 实习报告（20%）——是否按时提交以及撰写质量 2、对上述六次考核进行综合评价，按百分制形成实验总评成绩。 3、实验成绩占整个课程成绩的比例： ① 本课程期末设有笔试，该场考试成绩占整个课程成绩的 70%； ② 平时成绩占整个课程成绩的 30%，平时成绩从作业完成情况、期中测验情况、 实验情况、出勤情况、课堂表现几个方面进行考核。 ③ 实验情况占平时成绩的 2/3，亦即占整个课程成绩的 20% 。 五、推荐实验教材和教学参考书 教材： 《数据结构教程（第 5 版）上机实验指导》，李春葆编著 ，清华大学出版社，2015 年 8 月第 1 版。 参考书： ①《数据结构题集》严蔚敏、吴伟民、米宁编著，清华大学出版社，2015 年 8 月
②《数据结构习题解析与实验指导》李冬梅、张琪编著，人民邮电出版社，2017 年8月。 ③《数据结构课程实验》，徐孝凯编著，清华大学出版社，2002年1月第1版。 ④《数据结构习题解析与实验指导(C语言描述)》，刘怀亮编著，冶金工业出版 社，2005年2月第1版。 ⑤《数据结构习题解析与上机指导》，周云静编著，治金工业出版社，2004年1 月第1版。 大纲修订人：罗勇 修订日期：2020年12月 大纲审定者：沈永珞 审定日期：2020年12月
②《数据结构习题解析与实验指导》李冬梅、张琪编著，人民邮电出版社，2017 年 8 月。 ③《数据结构课程实验》，徐孝凯编著 ，清华大学出版社，2002 年 1 月第 1 版。 ④《数据结构习题解析与实验指导（C 语言描述）》，刘怀亮编著 ，冶金工业出版 社，2005 年 2 月第 1 版。 ⑤《数据结构习题解析与上机指导》，周云静编著 ，冶金工业出版社，2004 年 1 月第 1 版。 大纲修订人：罗勇 修订日期：2020 年 12 月 大纲审定者：沈永珞 审定日期：2020 年 12 月