2010-2011-2数据结构课程教案

《2010-2011-2数据结构课程教案》由会员分享，可在线阅读，更多相关《2010-2011-2数据结构课程教案（57页珍藏版）》请在装配图网上搜索。

1、注：此教案未经授权公开发布，任何人不得商用，违者自负！唐山师范学院 课 程 教 案 10-11 学年 第 二 学期 10-11 学年 第 二 学期课程名称 数据结构授课专业 计算机科学与技术授课班级 09计算机本科主讲教师 英锋所属系别 计算机科学系教 研 室 计算机应用教材名称 数据结构出版社、版次 清华大学出版社（C语言版）2011年 2 月 22 日唐山师范学院课程教案(首页)系别：计算机科学系 教研室：计算机应用课程名称数据结构课程类别学科专业必修课课程代码220142116课程所属专业计算机科学与技术专业总学时80学分5讲授学时80实践学时实验学时授课专业计算机科学与技术授课班级09

2、计算机本科任课教师英锋职 称教授教学目的和要求数据结构是计算机学科的一门核心专业基础课程，是计算机程序设计的重要理论和实践基础。本课程讨论了软件设计中经常遇到的线性表、堆栈、队列、串、数组、二叉树、图等典型数据结构的设计方法以及各种典型排序和查找算法的性能和设计方法，并介绍了各种典型数据结构的应用。通过本课程的学习，学生对软件设计的基本要素和软件的基本结构有了深入理解，并通过算法设计方法学习和上机编程实践，编程能力有了进一步提高。课程要求掌握主要内容包括：线性表、堆栈、队列、串、数组、树、二叉树、图等典型数据结构问题的逻辑结构、存储结构和操作的实现方法，各种典型的排序和查找算法，以及递归算法的

3、设计方法。通过本课程的学习，应使学生掌握各种数据结构的特点：存贮表示、运算方法以及在计算机科学中最基本的应用，培养、训练学生选用合适的数据结构和运用C语言编写质量高、风格好的应用程序及初步评价算法程序的能力；为编译技术、操作系统和数据库等后续课程的学习以及为应用软件特别是非数值应用软件的开发打下良好的理论基础和实践基础。要求结合实际问题，学会分析计算机加工的数据对象的特性，能够选择适当的数据结构和存储结构以及相应的算法，并初步掌握算法的简单时间复杂度分析方法，训练掌握各种数据结构的表示方法和实现的算法。知识要求：学生通过学习该课程后主要应掌握以下内容：掌握程序设计的基本原理和方法了解对各种抽象

4、数据类型的性质掌握处理各种抽象数据类型的基本算法初步掌握算法的简单时间复杂度分析方法素质要求：学生通过学习该课程后能够运用数据结构的思想，针对不同数据对象的特性，能够选择适当的数据结构和存储结构以及相应的算法，解决实际的问题。能力要求：学生通过学习该课程后能够应用一门程序设计语言进行各种应用系统的设计、开发及维护。教学重点、难点本课程的重点内容是如何分析现有的实际数据，从中找出规律，抽象出对应的抽象数据类型，进而设计出各种基本算法。讲课过程中应尽量多举实例，通过举例来一步步引导学生学会如何分析数据、查找规律、抽象成数据类型和编写算法。教学重点：线性表、堆栈、队列、二叉树、图典型数据结构问题的逻

5、辑结构、存储结构和操作的实现方法，各种典型的排序和查找算法思想。难点是各种数据结构的应用和进行操作实现，包括哈夫曼树及其应用、最短路径、哈希表、快速排序、基数排序等，必须通过学生自己多做分析和实践，才能更好地掌握。教材和参考书指定教材：严尉敏 吴伟民主编，数据结构（C语言版），清华大学出版社，2002年。教学参考书：1 严蔚敏，吴伟民，米宁编著数据结构题集C语言版，北京，清华大学出版社，199962 廖荣贵，许正宪，王龙发编著数据结构算法，北京，清华大学出版社，2004113 李春葆编著数据结构习题与解析第二版，北京，清华大学版社，200424 梁作娟，胡伟，唐瑞春编著数据结构习题解答与考试指

6、导，北京，清华大学出版社，2004115 张铭，刘晓丹译数据结构与算法分析C+版，电子工业出版社唐山师范学院课程教案(章节备课)授课题目（章节） 第一章 绪论授课类型理论课授课时间第 1 周 至第 2 周 共 7学时教学目的要求：熟悉数据结构中常用的C语言数组、函数、指针、结构体、类型定义、malloc、realloc、free、sizeof、类C语言及C+引用类型；掌握数据结构的基本概念，抽象数据类型在软件设计中的意义，算法的概念和算法的时间复杂度分析，了解算法的描述和评价。教学要点：1 数据结构课程的主要内容；2 涉及的基本概念和术语；3 抽象数据类型在软件设计中的意义；4 算法的概念、算

7、法设计的要求和算法的时间复杂度、空间复杂度分析；教学进程：1 复习在数据结构的学习中涉及到的C和C+中的重点内容，主要是数组、函数、指针、结构体、类型定义、malloc函数、realloc和free函数的内容；理解类C语言。重点是指向结构体变量的指针及类型定义；2 讲授数据结构课程的主要内容以及在软件分析和设计中意义；3 讲授抽象数据类型在软件设计中的意义；4 讲授算法的概念和算法的时间复杂度分析方法；5 例题讲解算法的时间复杂度分析方法；6 作业；对于重点和难点，通过例题讨论讲解。教学重点：本课程的主要内容，基本概念，抽象数据类型，算法和算法的时间复杂度分析教学难点：C语言中链表和数据结构、

8、算法的时间复杂度分析教学方法与手段课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点的算法核心部分通过板书进行详细讲解。思考题（讨论题）及作业（有单元课时教案的本项可不填）：参考文献（含参考书、有关资料出处、相关课程网站网址等）：1 严蔚敏，吴伟民，米宁编著数据结构题集C语言版，北京，清华大学出版社，199962 廖荣贵，许正宪，王龙发编著数据结构算法，北京，清华大学出版社，2004113 李春葆编著数据结构习题与解析第二版，北京，清华大学版社，200424 梁作娟，胡伟，唐瑞春编著数据结构习题解答与考试指导，北京，清华大学出版社，2004115 张铭，刘晓丹译数据结构与算法

9、分析C+版，电子工业出版社课 后 自 我 总 结 分 析本章首先复习了在数据结构教学中将要用到C语言和C+的主要知识。通过教学过程中的提问、课后作业的情况来看，虽然在新的人才培养方案中增加了C语言程序设计和C+与面向对象程序设计的课程设计的学时比例，但学生对C语言的掌握依然比较差，今后应重点加强学生上机动手能力。在介绍数据结构的研究目的和研究内容时学生比较容易掌握，以后这方面的知识应在介绍C语言知识时提前布置学生进行预习，教学时采取讨论的形式进行。算法的时间复杂度和空间复杂度学生比较迷惑，应在C语言复习中就提前提出这一问题，给学生思考的空间。唐山师范学院课程教案（课时单元备课）授课题目（或主题

10、）：C语言重点回顾（数组、函数、指针、结构体）授课类型理论课授课时间第 1 周第1节教学目标或要求：熟悉数据结构中常用的C语言数组、函数、指针、结构体。教学要点：1 数组：一维数组的定义、引用、初始化；二维数组的定义、引用、初始化。2 函数的定义、形式参数、实际参数、函数的返回值、函数原型；函数调用的形式：函数语句；函数表达式；函数参数、函数原型（被调函数的声明）、函数可以递归调用、数组名作为函数参数。3 地址和指针的概念；指针的定义和引用；指针变量作为函数的参数；数组作为函数指针字符串指针指向函数的指针返回指针值的函数指针数组指向指针的指针。4 结构体：定义结构体的三种方法；结构体变量的引用

11、、初始化；结构体数组的定义、初始化；指向结构体变量的指针。教学进程：1 讲授数据结构课程的主要内容以及在软件分析和设计中意义；2 讲授C语言中的主要数据结构：数组；3 通过一个C语言教材上的例子讲解函数的概念；4 详细讲解指针的定义、引用、指针作为函数参数；5 用一个具体例子讲解结构体，重点讲解结构体的定义及结构体数组。教学重点：数组元素的引用、函数的定义、数组名作为函数，形参与实参的关系、指针的应用，结构体数组的应用、指向结构体变量的指针。教学难点：数组名作为函数参数、指针、指向结构体变量的指针教学手段与方法：课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点的算法核心部分

12、通过板书进行详细讲解。思考题、讨论题、作业：1 使用C语言写一个函数sort，对一整型数组按选择法进行升序排序，形参、实参均用数组名。另写一个主程序，在主程序中定义一个整型数组，在主程序中输入数组内容，调用sort排序，然后在主程序中输出数组内容。2 将上题分别改为实参用数组、形参用指针；形参用数组，实参用指针；只写出不同部分。参考资料（含参考书、文献等，有章节教案的本项可不填）：唐山师范学院课程教案（课时单元备课）授课题目（或主题）：C语言重点回顾（类型定义、malloc、realloc、free、sizeof、类C语言及C+引用类型）授课类型理论课授课时间第 1 周第2节教学目标或要求：熟

13、悉数据结构中常用的C语言类型定义、malloc、realloc、free、sizeof、类C语言及C+引用类型。教学要点：1 类型定义：数据类型定义方法；使用新类型定义变量；2 三个函数和一个运算符：malloc()、realloc()、free()的sizeof；3 C+引用类型：引用的概念；引用作为函数的参数；4 类C语言教学进程：1 复习上节课主要内容2 讲授类型的定义3 讲授三个常用内存分配函数和长度运算符4 复习C+的引用类型5 讲授数据结构中描述算法的方法：类C语言教学重点：使用类型定义结构体类型；三个内存分配函数，类C语言教学难点：三个函malloc()、realloc()、fr

14、ee()，类C语言教学手段与方法：课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点的算法核心部分通过板书进行详细讲解。思考题、讨论题、作业：1 写一个程序，从键盘输入1至10，用带头结点的线性单链表进行存储，并按逆序输出。2 分别用C和C+各写一个主程序和一个主函数，在主程序中输入两个整数a和b，调用函数swap将两个数交换后输出。体会两种语言的不同参考资料（含参考书、文献等，有章节教案的本项可不填）：唐山师范学院课程教案（课时单元备课）授课题目（或主题）： 绪论授课类型理论课授课时间第2周第1节教学目标或要求：了解数据结构课程的主要内容及，涉及的基本概念，理解抽象数据类型

15、在软件设计中的意义，掌握算法的概念和算法的时间复杂度分析。教学要点：1 掌握数据结构的基本概念2 抽象数据类型在软件设计中的意义3 算法的概念和算法的时间复杂度分析教学进程：1 讲授数据结构课程的主要内容以及在软件分析和设计中意义；2 讲授抽象数据类型在软件设计中的意义；3 讲授算法的概念和算法的时间复杂度分析方法；4 例题讲解算法的时间复杂度分析方法；5 作业 对于重点和难点，通过例题讨论讲解。教学重点：本课程的主要内容，基本概念，抽象数据类型，算法的时间复杂度分析教学难点：算法的时间复杂度分析教学手段与方法：课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点的算法核心部分

16、通过板书进行详细讲解。思考题、讨论题、作业：1 为什么要学习数据结构？2 学习数据结构什么内容？3 如何学习数据结构？参考资料（含参考书、文献等，有章节教案的本项可不填）：唐山师范学院课程教案(章节备课)授课题目（章节） 第二章 线性表授课类型理论课授课时间第 2 周 至第 4 周 共13学时教学目的要求：理解线性表的定义和线性表基本操作的功能；掌握线性表的顺序和链式存储结构；掌握顺序表的设计及应用；掌握单链表的设计及应用。教学要点：1 线性结构性质：四点；2 线性表的类型定义：概念、长度、抽象数据类型定义，基本操作的应用；3 线性表的顺序存储结构、构造一个空的线性表、线性表的插入操作、线性表

17、的删除操作、线性表的查找、线性表的合并，插入、删除算法的算法分析；4 线性表的链式实现、返回线性表第i个数据元素的值、在线性表第i个位置之前插入元素e、在带头结点的线性表L中删除第i个元素、链表的合并；5 静态链表、循环链表、双向链表；教学进程：1 讲授本章节的基本概念，先逻辑结构，后存储结构；2 讲授各存储结构下操作实现的主要思想；3 在C+开发环境下，计算机演示完整应用程序的结构，以及编辑、编译和运行的方法；4 例题讲解；5 作业对于重点和难点，通过程序演示，作业来突出。教学重点：线性表的定义和抽象数据类型；顺序和链式存储结构；顺序表的设计；单链表的设计，算法分析。教学难点：顺序表操作的算

18、法设计；单链表操作的算法设计；完整应用程序的结构教学方法与手段课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点的算法核心部分通过板书进行详细讲解。思考题（讨论题）及作业（有单元课时教案的本项可不填）：参考文献（含参考书、有关资料出处、相关课程网站网址等）：1 严蔚敏，吴伟民，米宁编著数据结构题集C语言版，北京，清华大学出版社，199962 廖荣贵，许正宪，王龙发编著数据结构算法，北京，清华大学出版社，2004113 李春葆编著数据结构习题与解析第二版，北京，清华大学版社，200424 梁作娟，胡伟，唐瑞春编著数据结构习题解答与考试指导，北京，清华大学出版社，2004115

19、张铭，刘晓丹译数据结构与算法分析C+版，电子工业出版社课 后 自 我 总 结 分 析本章主要讨论非数值计算模型下的最典型的线性结构，线性表。主要包括三个方面的内容，（1）线性表的定义；（2）线性表的存储结构（主要包括顺序存储结构和链式存储结构）及其相应操作的实现；（3）线性表的应用。在教学过程中最突出的问题是：学生可以理解教师的教学内容，对算法的演示也没有问题，但涉及到自己动手设计一个和课上教学内容相近的算法就无所适从了，反映了学生的实际动手能力。对顺序存储的线性的理解基本上没有问题，约85%的同学可以正确理解，但涉及到链式存储结构时根据作业情况，就只大约一半的同学能应用了。按照数据结构通常的

20、教学要求看应有75%以上有同学可以正确理解，主要问题出在教师和同学有交流上，以后在教学中应该增加沟通的机会。唐山师范学院课程教案（课时单元备课）授课题目（或主题）：线性表抽象数据类型及线性表的顺序表示和实现授课类型理论课授课时间第2周第2节教学目标或要求：理解线性表的定义和抽象数据类型，掌握线性表的顺序存储结构，掌握线性表的顺序表示和操作实现并能灵活应用。教学要点：1 概念和术语：线性表 前趋和后继 线性表的长度 空表 表头元素 表尾元素 结点 首元结点；2 线性表的特点；3 线性表的顺序存储结构（顺序表）；4 C语言中线性表顺序存储空间的两种分配方法；静态分配、 动态分配；5 线性表顺序存储

21、结构的优缺点；6 线性表的逻辑结构特征以及必要的基本运算的实现；7 线性表的顺序存储结构以及基本运算的实现、算法分析；教学进程：1 先介绍线性表的定义和抽象数据类型，用例子说明线性表的概念和定义；2 画图讲解顺序存储结构；3 讲解线性表的顺序表示和操作实现，对于每个算法步骤画图说明；4 分析线性表插入和删除算法的时间复杂度，由此得出线性存储结构的缺点。教学重点：线性表的定义和抽象数据类型；顺序存储结构；线性表的顺序表示和操作实现。教学难点：顺序表操作的算法设计教学手段与方法：课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点的算法核心部分通过板书进行详细讲解。思考题、讨论题、

22、作业：1 写出将顺序表L就地逆置的算法2 若顺序表L的数据元素按升序排列，要求将e入到顺序表中的合适位置，以保证表的有序性，试给出其算法。参考资料（含参考书、文献等，有章节教案的本项可不填）： 唐山师范学院课程教案（课时单元备课）授课题目（或主题）：线性表的链式表示及表现（链表的插入、删除）授课类型理论课授课时间第3周第1节教学目标或要求：理解链式存储结构的概念，掌握线性表的链式表示和操作实现并能灵活应用。教学要点：1 线性链表的特点2 链表的抽象数据类型3 线性表的链式存储结构以及基本运算的实现4 线性表的链式存储结构的优缺点教学进程：1 复习讲解顺序表的操作实现，对于每个算法步骤画图说明；

23、2 用C开发环境演示2个完整顺序表应用程序的例子；3 画图讲解链式存储结构；4 讨论带头结点单链表和不带头结点单链表的区别和优缺点；5 讲解线性表的带头结点单链表表示和操作实现，对于每个算法步骤画图说明；教学重点：链式存储结构；线性表的链式表示和操作实现。教学难点：单链表操作的算法设计教学手段与方法：课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点的算法核心部分通过板书进行详细讲解。思考题、讨论题、作业：1 写出将带头结点的线性单链表L就地逆置的算法2 试将一个无序的线性表L(11,16,8,5,14,10,38,23)转换成一个按升序排列的有序线性表（用链表实现）。参考资

24、料（含参考书、文献等，有章节教案的本项可不填）：唐山师范学院课程教案（课时单元备课）授课题目（或主题）：线性表的链式表示及表现（链表的合并、静态链表）授课类型理论课授课时间第3周第2节教学目标或要求：掌握链表的存储结构和基本操作，了解静态链表的基本概念和操作。教学要点及教学进程：教学要点：1 链表的合并：两个有序链表合并为一个仍然有序的链表2 静态链表：用一维数组描述线性链表；静态链表的查找教学进程：1 回顾第一节两个非递增有序的线性表合并一个仍然有序表的操作，阐明算法的设计取决于逻辑结构，算法的实现取决于物理结构。2 结合原算法讲解单链表的合并操作实现，对于每个算法步骤画图说明3 讨论链式存

25、储和顺序存储的优缺点4 将两种存储结构进行合并考虑，构造出静态链表。5 静态链表的应用：集合运算6 画图讲解静态链表的结构教学重点：1 链表的合并算法2 静态链表的基本操作教学难点：1 静态链表的基本操作教学手段与方法：课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点的算法核心部分通过板书进行详细讲解。思考题、讨论题、作业：1 有一个单链表，其结点的元素值以非递减有序排列，编写一个函数删除该单链表中多余的元素值相同的结点。2 线性表的顺序存储结构和链式存储结构各有什么优缺点？参考资料（含参考书、文献等，有章节教案的本项可不填）：唐山师范学院课程教案（课时单元备课）授课题目（

26、或主题）：线性表的链式表示及表现(循环链表、双向链表的表示、插入、删除)授课类型理论课授课时间第4周第1节教学目标或要求：理解循环单链表的概念和算法设计方法，掌握双向链表的算法设计方法，教学要点：1 循环单链表的概念2 循环单链表的算法设计思路3 双向链表的算法设计思想及实现教学进程：1 画图讲解循环单链表的结构；2 结合图讲授循环单链表的算法思想；3 画图讲解双向链表的结构；4 双向链表与单链表操作相同和不同的部分；5 讲解双向链表的插入操作的实现6讲解双向链表的删除操作的实现7对于每个算法步骤画图说明；教学重点：双向链概念和双向链表的操作实现教学难点：双向链表的操作实现教学手段与方法：课堂

27、教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点的算法核心部分通过板书进行详细讲解。思考题、讨论题、作业：1 设有一个循环双链表，其中一个结点的指针为p，编写一个算法将p与其后续结点进行交换2 画出下列数据结构的图示：顺序表 单链表 双链表 循环链表参考资料（含参考书、文献等，有章节教案的本项可不填）：唐山师范学院课程教案（课时单元备课）授课题目（或主题）：一元多项式的表示和相加、线性表的应用举例授课类型习题课授课时间第4周第2节教学目标或要求：掌握一元多项式表示方法，学会使用线性表的线性表示和基本操作解决实际问题。教学要点：1 一元多项式表示方法2 一元多项式表示基本操作3

28、用实际程序例子说明数据结构问题在软件设计中的作用和基本方法，顺序表完整程序例子，单链表完整程序例子教学进程：1 讲授一元多项式表示方法2 讲授一元多项式表示基本操作算法3 讲解作业4 用C+开发环境演示完整程序的例子；5演示C+开发环境下的程序设计方法6 理解数据结构问题在软件设计中的作用和基本方法7 为随后的学生上机实验打下基础教学重点：1 多项式相加的C+程序2 顺序表完整程序例子3 单链表完整程序例子教学难点：1 多项式相加的C+程序2 理解数据结构问题在软件设计中的作用和基本方法教学手段与方法：课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点的算法核心部分通过板书进

29、行详细讲解。思考题、讨论题、作业：1 从顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。2 用单链表表示集合，设计算法求两个集合的交参考资料（含参考书、文献等，有章节教案的本项可不填）：唐山师范学院课程教案(章节备课)授课题目（章节） 第三章 栈和队列授课类型理论课授课时间第 5 周 至第 7 周 共12学时教学目的要求：理解堆栈的概念，掌握顺序堆栈和链式堆栈的设计方法；理解队列的概念，掌握顺序循环队列和链式队列的设计方法；了解堆栈和队列的应用方法，掌握堆栈和队列的基本应用。教学要点：堆栈的基本概念、堆栈的抽象数据类型定义、堆栈的顺序表示和实现、堆栈的链式表示和实现；堆栈应用（数制转

30、换问题、括号匹配问题等、行编辑程序、迷宫求解、表达式求值等）；栈与递归的实现；队列的基本概念、队列的抽象数据类型定义、顺序队列、顺序循环队列、链式队列、队列应用。教学进程：讲授栈的概念、抽象数据类型定义、表示和实现讲授队列的概念、抽象数据类型定义、表示和实现讲授栈和队列的应用教学重点：顺序堆栈和链式堆栈的设计方法；顺序循环队列和链式队列的设计方法。教学难点：顺序循环队列的几种典型队空和队满判断方法；堆栈和队列的实现。教学方法与手段课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点的算法的核心部分通过提问及增加板书进行详细讲解。对算法的实现要求采用VC+ 开发环境，配合大屏幕投

31、影演示，增强理论结合实际的效果和提高学生的学习兴趣。每次下课前布置若干思考题，待下次上新课前进行提问。根据课程内容，在讲课中适当采取设立问题，请同学给出回答的方法加强师生互动，提高教学效果。思考题（讨论题）及作业（有单元课时教案的本项可不填）：参考文献（含参考书、有关资料出处、相关课程网站网址等）：1 严蔚敏，吴伟民，米宁编著数据结构题集C语言版，北京，清华大学出版社，199962 廖荣贵，许正宪，王龙发编著数据结构算法，北京，清华大学出版社，2004113 李春葆编著数据结构习题与解析第二版，北京，清华大学版社，200424 梁作娟，胡伟，唐瑞春编著数据结构习题解答与考试指导，北京，清华大学

32、出版社，2004115 张铭，刘晓丹译数据结构与算法分析C+版，电子工业出版社课 后 自 我 总 结 分 析栈和队列是两种有重要用途的线性结构。从数据结构角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限的线性表，因此，可称为限定性的数据结构。但从数据类型角度看，它们是和线性表大不相同的两类重要的抽象数据类型。由于它们广泛应用在各种软件系统中，因此在面向对象的程序设计中，它们是多型数据类型。本章除了讨论栈和队列的定义、表示方法和实现外，还给出一些应用的例子。从同学们的学习及作业情况来看，本章的理解比上一章要好很多，经分析理由如下，一是本章内容相对上一章

33、简单，二是经过栈和队列是第二章线性表的应用，经过上一章的学习后，本章就显得简单。是否可以考虑瑞将第三章的学时缩简2-3学时，增加到第二章上另外一个情况就是为提高上机操作的重要性，将上机单列是否合适，值得进一步的讨论。唐山师范学院课程教案（课时单元备课）授课题目（或主题）： 栈授课类型理论课授课时间第5周第1节教学目标或要求：堆栈的基本概念、抽象数据类型、顺序表示和实现、链式表示和实现、入栈和出栈等基本算法。先引入概念和算法，然后通过实际应用让同学们进一步加深对概念和算法的理解。教学要点：1堆栈的概念和抽象数据类型定义2堆栈的顺序表示和实现方法3堆栈的链式表示和实现方法教学进程：1 从现实生活中

34、后进先出的例子引入栈的定义，讲授栈的性质2 从线性表的顺序存储引申到栈的顺序存储，同汇编语言中的栈的操作比较讲授栈的基本操作，重点是栈空、栈满的条件3 回顾链表的基本操作，根据栈的特性讲授链栈的操作。在讲课中或下课前布置如下几个思考题，待下次上新课前进行提问。思考题：1 栈与线性表有什么不同？2 什么叫栈的“上溢”和栈的“下溢”？3 顺序表和顺序栈的操作有何区别？4 为什么要设计堆栈？它有什么独特用途？5 请写出顺序栈和链栈的存储结构。教学重点：顺序堆栈和链式堆栈的设计方法。教学难点：链栈的实现。教学手段与方法：课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点的算法核心部分

35、通过板书进行详细讲解。对顺序栈、链栈的入栈和出栈等算法要求采用VC+开发环境进行调试运行，配合大屏幕投影演示，增强学生对顺序堆栈和链式堆栈的设计方法的理解和提高学生的学习兴趣。思考题、讨论题、作业：编写一个算法，利用栈的基本运算将指定栈中的内容进行逆转。（利用两个栈）两个栈要s1和s2共享存储空间c1.m0,其中 一个栈底设在c1处，另一个栈底设在cm0处，分别编写s1和s2的进栈push(i,x)、退栈pop(i)和设置栈空setnull(i)的函数，其中=1,2。注意仅当整个空间c1.m0占满时才发生上溢。参考资料（含参考书、文献等，有章节教案的本项可不填）： 唐山师范学院课程教案（课时单

36、元备课）授课题目（或主题）：栈的应用举例授课类型理论课授课时间第5周第2节教学目标或要求：掌握堆栈应用：数制转换问题、括号匹配问题、行编辑程序、老鼠迷宫问题、表示式求值问题。先引入概念和算法，然后通过实际应用让同学们进一步加深对概念和算法的理解教学要点：1堆栈的应用教学进程：1 总结栈的特性2 讲授利用栈进行数制转换3 介绍括号匹配问题，布置上机练习题4 介绍行编辑程序5 讲授老鼠迷宫问题，布置上机练习题6 讲授表达式求值问题，图示堆栈的变化过程。教学重点：利用栈进行数制转换、括号匹配问题、老鼠迷宫问题、表达式求值问题教学难点： 老鼠迷宫问题、表达式求值问题教学手段与方法：课堂教学以课堂讲授为

37、主，采用多媒体教学方式以增大信息量，对重点和难点的算法核心部分通过板书进行详细讲解。思考题、讨论题、作业：表达式中允许包含两种括号 和（ ），利用栈的基本操作检验括号是否匹配参考资料（含参考书、文献等，有章节教案的本项可不填）： 唐山师范学院课程教案（课时单元备课）授课题目（或主题）： 栈与递归的实现授课类型理论课授课时间第6周第1节教学目标或要求：掌握递归的概念、递归算法的执行过程、递归算法的设计方法、递归算法的效率分析教学要点：1 递归的概念2 递归算法的执行过程3 递归算法的设计方法4 递归算法的效率分析5 递归算法设计举例教学进程：1 回顾C语言中求n的阶乘的递归算法，分析递归算法的实

38、现方法2 讲授Fibonacci数列的递归算法3 讲授Ackerman函数的递归算法4 印度的一个古老的传说：开天辟地的神勃拉玛在一个庙里留下的三根金刚石的棒，64个金片，讲授此问题的解法，转换为递归算法，程序演示递归中栈的变化教学重点：递归的概念、递归算法的执行过程、递归算法的设计方法、递归算法的效率分析教学难点：递归算法的设计方法教学手段与方法：课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点的算法的核心部分通过提问及增加板书进行详细讲解。对算法的实现要求采用VC+ 开发环境，配合大屏幕投影演示，增强理论结合实际的效果和提高学生的学习兴趣。下课前布置若干思考题，待下次上

39、新课前进行提问。根据课程内容，在讲课中适当采取设立问题，请同学给出回答的方法加强师生互动，提高教学效果。思考题、讨论题、作业：利用递归算法实现一个字符串的逆序输出参考资料（含参考书、文献等，有章节教案的本项可不填）： 唐山师范学院课程教案（课时单元备课）授课题目（或主题）：队列的定义、链队列的实现授课类型理论课授课时间第6周第2节教学目标或要求：掌握队列的概念和基本操作，掌握队列的链式存储结构及基本操作。教学要点：1抽象数据类型队列的定义2链队列队列的链式表示和实现教学进程：1 从学生在食堂排队买饭的过程，讲授队列的性质：先进先出2 回顾链表的基本操作，根据队列的特性，引出链队列的基本操作3

40、讲授链队列的基本操作4 重点说明队列为空、满的条件，注意删除队列操作时删除后为空的处理在讲课中或下课前布置如下几个思考题，待下次上新课前进行提问。思考题：1、请写出链式队列的存储结构。2、试述判断一个字符序列是否是回文的算法的设计思想是什么？理解算法中为什么即要使用队列又要使用栈。算法中能否只使用队列或只使用栈就能够完成同样功能呢？教学重点：链式队列的设计方法教学难点：链式队列的设计方法教学手段与方法：课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点算法核心部分通过板书进行详细讲解。对链式队列的入队和出队等算法要求采用VC+开发环境进行调试运行，配合大屏幕投影演示，增强学生

41、对链式队列的设计方法的理解和提高学生的学习兴趣。思考题、讨论题、作业：从键盘输入一串字符，利用栈的队列的基本操作判断是否回文串用两个栈S1、S2模拟一个队列，用本报的基本操作实现EnQueue、DeQueue、QueueEmpty参考资料（含参考书、文献等，有章节教案的本项可不填）： 唐山师范学院课程教案（课时单元备课）授课题目（或主题）： 循环队列的表示及实现、离散事件的模拟授课类型理论课授课时间第7周第1节教学目标或要求：掌握顺序队列、顺序循环队列的表示和实现。先引入概念和算法，然后通过实际应用让同学们进一步加深对概念和算法的理解。教学要点：1顺序队列2顺序循环队列的设计方法教学进程：1

42、从以往数据结构的两种表示方法引出队列的另一种表示方法2 比较队列的顺序存储与线性表、栈的不同之处：一端插入另一端删除3 从入队、出队操作的图示中得出队首、队尾指针的变化方法4 分析判断队列空和满的判断条件，除了书上讲的方法，提问可否有另外的方法5 讲授队列的基本操作在讲课中或下课前布置如下几个思考题，待下次上新课前进行提问。思考题：1 队列与线性表有什么不同？2 为什么要设计队列？它有什么独特用途？3 请写出顺序队列的存储结构。4 如何解决顺序队列的“假溢出”问题？5 如何判断顺序循环队列的队空和队满问题？教学重点：顺序循环队列的设计方法。顺序循环队列的几种典型队空和队满的判断方法。教学难点：

43、 顺序循环队列的设计方法。顺序循环队列的几种典型队空和队满的判断方法。教学手段与方法：课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点算法的核心部分通过板书进行详细讲解。对顺序循环队列的入队和出队等算法要求采用VC+开发环境进行调试运行，配合大屏幕投影演示，增强学生对顺序循环队列的设计方法及如何判断顺序循环队列的队空、队满的理解和提高学生的学习兴趣。思考题、讨论题、作业：用循环队列（带头结点和不带头结点），只设一个尾指针rear，写出一个入队列（EnQueue）和出队列（DeQueue）操作对一个循环顺序队列，利用队列的基本操作返回队列中最后一个元素的操作(GetTail)

44、参考资料（含参考书、文献等，有章节教案的本项可不填）： 唐山师范学院课程教案(章节备课)授课题目（章节） 第四章 串授课类型理论课授课时间第 7 周 至第 7 周 共3学时教学目的要求：掌握串及其基本概念；理解串的存储结构及串基本操作的实现；了解串的模式匹配算法教学要点：1串的基本概念、存储结构（顺序存储、链式存储）、顺序存储结构下基本操作的实现算法；2串的模式匹配：Brute-Force算法。3分析方法：联系C语言中串的存储方法及串函数，并围绕两种基本存储结构进行分析。教学进程：1 讲授中的定义及串的基本概念2 介绍串的表示和基本实现：定长顺序存储、堆分配存储表示、3 介绍串的模式匹配算法板

45、书：以文字描述为主，要点及关键词用不同颜色标注；涉及有关存储结构、算法时，通过示意图描述；对于实例，通过链接到VC环境下实际运行。重点突出：通过课堂强调与透彻分析，课后练习进行。难点解决：通过实例讲解，并在VC环境下实际运行实例，使学生真实体会算法设计全过程。提问：空串和空白串有无区别？回顾：C语言中串的存储方法及有关串函数。串的模式匹配算法总结课后做习题，并课外上机实验，练习基本操作的实现及模式匹配的实例训练，以巩固课堂所学知识点。教学重点：1 串的存储结构；2 串的模式匹配。教学难点：串的模式匹配。教学方法与手段课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点的算法的核

46、心部分通过提问及增加板书进行详细讲解。思考题（讨论题）及作业（有单元课时教案的本项可不填）：试写出将字符串s2中的全部字符拷贝到字符串s1中的算法，不允许利用库函数strcpy()。设s1和s2是用结点大小为1的单链表表示的串，试写出找出s2中第一个不在s1中出现的字符的算法。设字符串采用块链存储结构，块链中每个结点存放m（m=4）个字符，试写出实现字符串删除的算法。参考文献（含参考书、有关资料出处、相关课程网站网址等）：1 严蔚敏，吴伟民，米宁编著数据结构题集C语言版，北京，清华大学出版社，199962 廖荣贵，许正宪，王龙发编著数据结构算法，北京，清华大学出版社，2004113 李春葆编著

47、数据结构习题与解析第二版，北京，清华大学版社，200424 梁作娟，胡伟，唐瑞春编著数据结构习题解答与考试指导，北京，清华大学出版社，2004115 张铭，刘晓丹译数据结构与算法分析C+版，电子工业出版社课 后 自 我 总 结 分 析本章介绍串的基本概念、存储结构（顺序存储、链式存储）、顺序存储结构下基本操作的实现算法，介绍了串的模式匹配。联系C语言中串的存储方法及串函数，并围绕两种基本存储结构进行分析。唐山师范学院课程教案(章节备课)授课题目（章节） 第五章 数组和广义表授课类型理论课授课时间第 8 周 至第 9 周 共7学时教学目的要求：掌握数组的定义及其实现机制；了解数组的抽象数据类型；

48、掌握特殊矩阵的压缩存储和稀疏矩阵的压缩存储；了解广义表的概念和表示。教学要点：1 数组的定义及其实现机制；2 特殊矩阵（包括n阶对称矩阵、n阶三角矩阵）的压缩存储方法；3 稀疏矩阵的压缩存储方法：三元组顺序表、三元组链表。4 分析方法：从具体的矩阵实例出发，先分析其特点，然后围绕以上知识点进行讲述。5 广义表的概念和表示教学进程：1 讲授数组的定义2 讲授数组的顺序表示和实现3 讲授数组的压缩存储4 介绍广义表的定义5 介绍广义表存储结构课后做习题，并上机实验，练习特殊矩阵、稀疏矩阵的压缩存储方法，以巩固课堂所学知识点。板书设计：以文字描述为主，要点及关键词用不同颜色标注；对压缩存储方法通过示

49、意图描述；对于实例，通过链接到VC环境下实际运行。重点突出：通过课堂强调与透彻分析，课后练习进行。难点解决：通过实例讲解，并在VC环境下实际运行实例，使学生真实体会算法设计全过程。互动设计：提问（数组与线性表的区别与联系？） 回顾（线性表的两种存储结构表示方法）教学重点：1 特殊矩阵的压缩存储；2 稀疏矩阵的压缩存储。教学难点：稀疏矩阵的压缩存储。 教学方法与手段课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点的算法的核心部分通过提问及增加板书进行详细讲解。思考题（讨论题）及作业（有单元课时教案的本项可不填）：参考文献（含参考书、有关资料出处、相关课程网站网址等）：1 严蔚

50、敏，吴伟民，米宁编著数据结构题集C语言版，北京，清华大学出版社，199962 廖荣贵，许正宪，王龙发编著数据结构算法，北京，清华大学出版社，2004113 李春葆编著数据结构习题与解析第二版，北京，清华大学版社，200424 梁作娟，胡伟，唐瑞春编著数据结构习题解答与考试指导，北京，清华大学出版社，2004115 张铭，刘晓丹译数据结构与算法分析C+版，电子工业出版社课 后 自 我 总 结 分 析本章讲解数组的定义及其实现机制，介绍特殊矩阵（包括n阶对称矩阵、n阶三角矩阵）的压缩存储方法及广义表的概念和表示。对算法只做简单介绍。 综合前几章的讲述，教学计划后，各章时间相对不足，下一部的任务是探

51、讨减少各部内容还是删除第四章。唐山师范学院课程教案（课时单元备课）授课题目（或主题）：数组的定义、数组的顺序表示及实现。 授课类型理论课授课时间第8周第1节教学目标或要求：掌握数组的定义和顺序存储表示，了解数组的基本操作。教学要点：1数组的定义、2数组的抽象数据类型3 数组的顺序存储表示和实现教学进程：1 回顾C语言中的数组2 讲授数组的抽象数据类型定义3 讲授一维数组的存储方法和元素的存储位置4讲授二维数组的存储方法和元素的存储位置5 由一、二维数组推广到多维数组的情况6 讲授数组的顺序存储表示和实现教学重点：数组的定义及其实现；二维数组的按行、列序存放；多维数组存放；数组的顺序存储表示和实

52、现教学难点：多维数组存放，数组的顺序存储表示和实现教学方法与手段课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点的算法的核心部分通过提问及增加板书进行详细讲解。思考题、讨论题、作业：按行优先存储方式，写出三维数组A324在内存中的排列顺序及地址计算公式（假设每个数组元素占用L个字节的内存单元，a000的内存地址为Loc(a000)）。按列优先存储方式，写出三维数组A324在内存中的排列顺序及地址计算公式（假设每个数组元素占用L个字节的内存单元，a000的内存地址为Loc(a000)）。.参考资料（含参考书、文献等，有章节教案的本项可不填）： 唐山师范学院课程教案（课时单元备

53、课）授课题目（或主题）：矩阵的压缩存储、对称及对角矩阵的压缩存储、稀疏矩阵的三元组表示及行逻辑连接表示。授课类型理论课授课时间第8周第2节教学目标或要求：掌握特殊矩阵的压缩存储方法，了解稀疏矩阵的压缩存储方法。教学要点：1对称矩阵的按行序压缩存储方法2对称矩阵的按列序压缩存储方法3 三对角矩阵的按行序压缩存储方法4三对角矩阵的按列序压缩存储方法5 稀疏矩阵的三元组表示6稀疏矩阵的行逻辑连接表示。教学进程：1 介绍特殊矩阵和稀疏矩阵2 讲授特殊矩阵的压缩存储3 讲授稀疏矩阵的抽象数据类型定义4 行逻辑链接的顺序表教学重点：特殊矩阵和稀疏矩阵的压缩存储方法教学难点：矩阵按列序压缩存储、稀疏矩阵的三

54、元组表示、稀疏矩阵的行逻辑连接表示。教学方法与手段课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点的算法的核心部分通过提问及增加板书进行详细讲解。思考题、讨论题、作业：设有上三角矩阵Ann，它的下三角部分全为0，将其上三角元素按行优先存储方式存入数组Bm中(m足够大)，使得Bk=aij，且有k=f1(i)+f2(j)+c。试推出函数f1、f2及常数c（要求f1和f2中不含常数项）。若矩阵Amn中的某个元素Aij是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵Amn，试编写求出矩阵中所有马鞍点的算法，并分析你的算法在最坏情

55、况下的时间复杂度。参考资料（含参考书、文献等，有章节教案的本项可不填）： 唐山师范学院课程教案（课时单元备课）授课题目（或主题）：转置运算、矩阵相乘、十字链表表示的相加、广义表。 授课类型理论课授课时间第9周第1节教学目标或要求：了解矩阵的转置、乘法运算及稀疏矩阵的十字链表表示。教学要点：1矩阵的转置运算2两个矩阵相乘3十字链表表示的矩阵的相加4、广义表教学进程：1 回顾矩阵的压缩存储2 讲授三元组表示的矩阵的转置、相乘运算3 讲授十字链表表示的矩阵的相加4 广义表教学重点：矩阵的转置运算、两个矩阵相乘、广义表教学难点：三元组表示的矩阵的转置、相乘运算教学方法与手段课堂教学以课堂讲授为主，采用

56、多媒体教学方式以增大信息量，对重点和难点的算法的核心部分通过提问及增加板书进行详细讲解。思考题、讨论题、作业：试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。给定一个稀疏矩阵如下：用快速转置实现该稀疏矩阵的转置，写出转置前后的三元组表及开始的每一列第一个非零元的位置potcol的值。参考资料（含参考书、文献等，有章节教案的本项可不填）：唐山师范学院课程教案(章节备课)授课题目（章节） 第六章 树和二叉树授课类型理论课授课时间第 9 周 至第 11 周 共10学时教学目的要求：理解树与二叉树的基本概念，掌握二叉树的性质与存储结构；掌握二叉树的遍历算法和二叉树问题的遍历

57、算法设计分析和实现教学要点：1 树的概念和定义2 树的特性及表示方式3 树的相关术语 4 二叉树的定义和它的五种形态5 二叉树的性质6 二叉树的存储结构：顺序存储和二叉链表存储结构7 遍历二叉树和线索二叉树 8 树的存储结构及与二叉树的转换 9 森林与二叉树的转换10 树和森林的遍历11 最优二叉树（哈夫曼树）的概念12 赫夫曼树构造算法。13 哈夫曼树的应用教学进程：1讲授本章节的基本概念，先逻辑结构，后存储结构；2讲授各存储结构下的实现的主要思想；3计算机演示存储结构下的实现；4例题讲解；5作业教学重点：二叉树的性质、二叉树的存储结构；二叉树的遍历算法和二叉树遍历算法的应用；哈夫曼树在编码

58、方面的应用方法。教学难点：二叉树的性质以及利用这些性质分析问题的方法；二叉树问题的遍历算法设计分析和实现。教学方法与手段辅助手段：多媒体演示，对于重点和难点，通过程序演示，作业来突出。思考题（讨论题）及作业（有单元课时教案的本项可不填）：参考文献（含参考书、有关资料出处、相关课程网站网址等）：1 严蔚敏，吴伟民，米宁编著数据结构题集C语言版，北京，清华大学出版社，199962 廖荣贵，许正宪，王龙发编著数据结构算法，北京，清华大学出版社，2004113 李春葆编著数据结构习题与解析第二版，北京，清华大学版社，200424 梁作娟，胡伟，唐瑞春编著数据结构习题解答与考试指导，北京，清华大学出版社

59、，2004115 张铭，刘晓丹译数据结构与算法分析C+版，电子工业出版社课 后 自 我 总 结 分 析本间讲述了树、二叉树、哈夫曼树的定义、性质、算法。讲述了一个新的数据结构，算法相对简单，学生理解尚可，但由于本章涉及较多的递归，学生对递归算法的实现不太理解。以后在教学中可以压缩树的定义、二叉权的性质讲解内容，增加树的遍历算法及哈夫曼树的应用讲解内容，并增加习题课唐山师范学院课程教案（课时单元备课）授课题目（或主题）：树的定义、基本术语，二叉树的定义及五条性质、顺序、链式存储结构授课类型理论课授课时间第9周第2节教学目标或要求：掌握树的定义，了解树的基本术语，了解树的基本操作；掌握二叉树的概念

60、和性质，掌握二叉树的存储结构。教学要点：1树的定义及树的基本术语、二叉树，满二叉树，完全二叉树； 2二叉树的性质3二叉树的链式存储结构的实现4二叉树的顺序存储结构和链式存储结构教学进程：1先讲授概念：二叉树，满二叉树，完全二叉树，图示一些图结构，提问互动，加强对概念的理解。2讲授二叉树的5条性质，证明其中的（1），(3)，(4)。用例子说明这些性质，加强理解3分析链式存储结构的特点，比较线形结构与树结构的不同，体现在实现上的不同有哪些？讲授链式存储的实现，演示程序。教学重点：二叉树的五个性质，二叉树的链式存储结构的实现教学难点：二叉树的链式存储结构的实现教学方法与手段课堂教学以课堂讲授为主，采