计算机与信息科学系实验教案.doc
计算机与信息科学系实验教案教研室：计算机应用教研室 授课教师： 编号：1授课时间第 2 周 第 1次课授课题目实验1：实现单链表的插入和删除授课类型理论课( )；实践课( 是 ) 教学时数学时实验目的及要求1、熟悉用TURBO C3.0开发环境，掌握在TURBO C3.0环境中编辑、编译、连接调试、运行一个C程序的过程及方法。2、掌握链表的表示方法；3、构造一个单链表；4、实现单链表的插入和删除 实验内容1、给出单链表的表示；2、完成单链表的建立；3、实现单链表的插入操作；4、实现单链表的删除操作；选做：1、用不同的方法完成单链表的实现； 2、完成单链表中除建立、插入、删除以外的其他操作； 3、实现循环链表的建立、插入、删除操作，并与单链表相比较；教学重点及难点重点：1、理解单链表的存储方式和顺序实现的区别 难点：1、指针的应用、结构指针的使用。 教学手段利用机房多媒体设备讲授并演示，启发引导学生自己动手完成实验作业、讨论、思考1、根据实验要求，总结实验过程，课后完成实验报告。2、讨论：带头结点的单链表与不带头结点的单链表在实现上有什么不同 ？ 课后小结1. 通过本次实验，让学生进一步熟悉C语言开发环境； 2. 通过本次实验，使学生学会如何自定义一种数据结构，并实现该结构的表示与基本操作的实现。 3. 部分操作能力比较强的同学，可以多做一些实验。 参考资料1 严蔚敏等，数据结构题集,1995 2 William Ford，William Topp，Data Structure with C+ 清华大学出版社Prentice Hall联合出版,19963 李春葆等，数据结构与算法教程，清华大学出版社，20054 （美）Mark Allen Weiss著 冯舜玺译，数据结构与算法分析c语言描述，机械工业出版社，2004（6）5 郝文化，数据结构考研辅导教程，北京希望电子出版社，2005（9）。6 数据结构教程 李春葆编著 清华大学出版社 计算机与信息科学系实验教案教研室：计算机应用教研室 授课教师： 编号：2授课时间第 4 周 第 2次课授课题目 单链表的应用授课类型理论课( )；实践课( 是 ) 教学时数学时实验目的及要求1、熟练掌握单链表的建立； 2、熟练掌握函数的调用； 3、掌握对单链表基本操作的应用； 4、掌握对单链表的理解，并实现不同的表示；、熟悉并掌握一元多项式的链式表示；6、利用其中的一个多项式存储结果多项式。实验内容1、 实现对一元多项式的链式表示；2、 实现两个或多个一元多项式的相加、减；教学重点及难点重点：1、一员多项式的表示2、两个一元多项式相加； 难点：利用其中一个多项式存储结果多项式。教学手段利用机房多媒体设备讲授并演示，启发引导学生自己动手完成实验作业、讨论、思考1、根据实验要求，总结实验过程，课后完成实验报告。2、讨论与有序表的合并在算法思路上有什么共同点 ？课后小结1、掌握单链表的不同表示方式，当数据类型不一样时，如何灵活的变化单链表的结构； 、利用已经实现了的算法实现问题的应用。 参考资料1 严蔚敏等，数据结构题集,1995 2 William Ford，William Topp，Data Structure with C+ 清华大学出版社Prentice Hall联合出版,19963 李春葆等，数据结构与算法教程，清华大学出版社，20054 （美）Mark Allen Weiss著 冯舜玺译，数据结构与算法分析c语言描述，机械工业出版社，2004（6）5 郝文化，数据结构考研辅导教程，北京希望电子出版社，2005（9）。6 数据结构教程 李春葆编著 清华大学出版社计算机与信息科学系实验教案教研室：计算机应用教研室 授课教师： 编号：授课时间第4、6 周 第3、4次课授课题目二叉树操作授课类型理论课( )；实践课( 是 ) 教学时数4学时实验目的及要求实验目的：掌握二叉树的定义、性质及存储方式，各种遍历算法。实验要求：采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作实验内容1、分析、理解程序。2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD#CE#F#，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。 重点及难点重点：1、理解二叉树的性质2、熟悉二叉树的遍历方法 难点：1、遍历方法的应用 教学手段利用机房多媒体设备讲授并演示，启发引导学生自己动手完成实验作业、讨论、思考1、根据实验要求，总结实验过程，独立完成实验报告2、已知前序遍历序列和后序遍历序列是否能唯一的确定一棵二叉树？如果能，给出实现程序，如果不能，给出理由； 3、实现二叉树的其他基本操作； 4、将课本中的递归完成的算法用非递归程序实现。课后小结二叉树是树中一个比较简单的应用，其中二叉树具备一些性质使得它在应用中具有重要的地位，同时树的定义是递归的，所以在实现上很多的算法都是递归完成的，这样在理解上减低了难度，但是由于递归在实现的过程中需要更多的系统资源，从资源节约的角度，我们有时需要将递归的程序用非递归来实现。 参考资料1 严蔚敏等，数据结构题集,1995 2 William Ford，William Topp，Data Structure with C+ 清华大学出版社Prentice Hall联合出版,19963 李春葆等，数据结构与算法教程，清华大学出版社，20054 （美）Mark Allen Weiss著 冯舜玺译，数据结构与算法分析c语言描述，机械工业出版社，2004（6）5 郝文化，数据结构考研辅导教程，北京希望电子出版社，2005（9）。6 数据结构教程 李春葆编著 清华大学出版社计算机与信息科学系实验教案教研室：计算机应用教研室 授课教师： 编号：3授课时间第 8、10 周 第5、6次课授课题目图的遍历操作授课类型理论课( )；实践课( 是 ) 教学时数4学时实验目的及要求 目的： 掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。要求：采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。实验内容1、 分析、理解程序。2、 调试程序。设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS（深度优先遍历）和BFS（广度优先遍历）的操作。程序见实验指导书上的实验三 重点及难点重点：1、邻接矩阵和邻接链表的表示；2、用邻接矩阵和邻接链表实现图的建立；3、深度优先遍历和广度优先遍历算法的实现。难点：1、邻接矩阵和邻接链表的表示；2、用邻接矩阵和邻接链表实现图的建立；3、深度优先遍历和广度优先遍历算法的实现。 教学手段程序的实现由老师与学生共同完成； 作业、讨论、思考1、根据实验要求，总结实验过程，独立完成实验报告；2、邻接矩阵表示图时的特点；3、用邻接链表表示图时的特点；4、深度优先遍历和广度优先遍历算法与二叉树的遍历算法有没有相似性 。 课后小结 本章主要介绍了图的相关的知识，对于图的操作的实现，首要的任务就是掌握图的四种存储方法的表示，然后在此基础上实现图的建立，由于图的结构复杂，实现相应的也复杂，很多的同学对图的存储在理解上存在问题，在算法实现时更是无从下手，针对这种情况，更加要注重对概念的理解。参考资料1 严蔚敏等，数据结构题集,1995 2 William Ford，William Topp，Data Structure with C+ 清华大学出版社Prentice Hall联合出版,19963 李春葆等，数据结构与算法教程，清华大学出版社，20054 （美）Mark Allen Weiss著 冯舜玺译，数据结构与算法分析c语言描述，机械工业出版社，2004（6）5 郝文化，数据结构考研辅导教程，北京希望电子出版社，2005（9）。6 数据结构教程 李春葆编著 清华大学出版社计算机与信息科学系实验教案教研室：计算机应用教研室 授课教师： 编号：授课时间第12、14 周 第 7、8次课授课题目排序授课类型理论课( )；实践课(是 ) 教学时数4学时实验目的及要求目的：掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。要求：实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。实验内容 实验指导书中的实验四重点及难点重点：1、各种排序算法的思路； 2、排序算法的实现。难点：1、各种排序算法的分析和选择合适的算法。 教学手段利用机房多媒体设备讲授并演示，启发引导学生自己动手完成实验作业、讨论、思考1、根据实验要求，总结实验过程，独立完成实验报告2、那些排序算法是稳定的，那些是不稳定的？3、堆排序时如何建立一个堆，并且将不是堆的结构如何调整成堆 ？4、不同的排序算法的适用场合 ？5、相同的排序算法在最好和最坏的情况下的时间复杂度和空间复杂度是多少？课后小结课本上实现的排序都是顺序表示的 参考资料1 严蔚敏等，数据结构题集,1995 2 William Ford，William Topp，Data Structure with C+ 清华大学出版社Prentice Hall联合出版,19963 李春葆等，数据结构与算法教程，清华大学出版社，20054 （美）Mark Allen Weiss著 冯舜玺译，数据结构与算法分析c语言描述，机械工业出版社，2004（6）5 郝文化，数据结构考研辅导教程，北京希望电子出版社，2005（9）。6 数据结构教程 李春葆编著 清华大学出版社计算机与信息科学系实验教案教研室：计算机应用教研室 授课教师： 编号：6授课时间第16 周 第 9次课授课题目查找授课类型理论课( )；实践课(是 ) 教学时数学时实验目的及要求掌握顺序查找、折半查找及二叉排序树上查找的基本思想和算法实现，了解怎样对各种查找方法进行时间性能（平均查找长度）分析。实验内容 实验指导书中的实验五重点及难点重点：1、二分查找的实现2、二叉排序树的实现难点：1、二叉排序树的实现 教学手段利用机房多媒体设备讲授并演示，启发引导学生自己动手完成实验作业、讨论、思考1. 根据实验要求，总结实验过程，独立完成实验报告2. 相同的数据，不同的顺序在构造二叉排序树时的二叉排序树是否一样？3. 能利用二分查找的数据，必须满足什么条件？课后小结 本章主要介绍了三种不同的查找方法：静态查找和动态查找以及哈希查找方法。其中静态查找有三种典型的算法：顺序查找适用于任何数据结构；二分查找只用于顺序存储的有序表的查找；索引查找。动态查找介绍了两种典型的查找算法二叉排序树和平衡二叉树。哈希表是一种特殊的查找方式，必须先找到一种构造查找表的函数即哈希函数，然后根据哈希函数得到关键字的存储位置，构造查找表，查找过程和构造表的过程相同，在构造哈希表的时候要注意冲突的处理参考资料1 严蔚敏等，数据结构题集,1995 2 William Ford，William Topp，Data Structure with C+ 清华大学出版社Prentice Hall联合出版,19963 李春葆等，数据结构与算法教程，清华大学出版社，20054 （美）Mark Allen Weiss著 冯舜玺译，数据结构与算法分析c语言描述，机械工业出版社，2004（6）5 郝文化，数据结构考研辅导教程，北京希望电子出版社，2005（9）。6 数据结构教程 李春葆编著 清华大学出版社计算机与信息科学系实验教案教研室：计算机应用教研室 授课教师： 编号：7授课时间第 18 周 授课题目 函数应用（一） 授课类型理论课( )；实践课( 是 ) 教学时数8学时实验目的及要求按要求独立完成课程设计实验内容见课程设计指导书（部分同学可以选择其中的一部分实验完成，实在是操作比较弱的同学可以组组完成实验）重点及难点 教学手段 利用课余时间由独立完成实验的分析和设计工作作业讨论思考 课后小结锻炼同学们独立思考问题、分析问题、解决问题和编程的能力。参考资料1 严蔚敏等，数据结构题集,1995 2 William Ford，William Topp，Data Structure with C+ 清华大学出版社Prentice Hall联合出版,19963 李春葆等，数据结构与算法教程，清华大学出版社，20054 （美）Mark Allen Weiss著 冯舜玺译，数据结构与算法分析c语言描述，机械工业出版社，2004（6）5 郝文化，数据结构考研辅导教程，北京希望电子出版社，2005（9）。6 数据结构教程 李春葆编著 清华大学出版社
