计算机与信息科学系教案.doc

计计算算机机与与信信息息科科学学系系教教案案教研室：教研室：计算机应用教研室 授课教师授课教师： ： 编号：编号：1授课 时间第 2 周 第 1-2 次课授课 题目第 1 章 绪论授课 类型理论课( 是 )；实践课( ) 教学 时数2 学时教 学 目 的 及 要 求1、理解计算机信息处理中数据组织与运算处理的关系； 2、熟悉各名词、术语的含义，掌握数据结构相关基本概念，特别是数据、 数据元素、数据对象、数据结构、逻辑结构、存储结构等； 3、了解数据的逻辑结构和存储结构之间的关系，了解常见的“集合、线性 表、树、图”的逻辑结构形式和“顺序、链表、索引、散列”存储组织方法；4、了解抽象数据类型的定义、表示与实现方法 5、算法教 学 内 容 提 要1、数据结构研究的主要内容与涉及的基本概念；2、数据类型与抽象数据类型 3、算法教 学 重 点 及 难 点1、 数据的逻辑结构、存储结构与运算方法之间的关系2、 算法时间复杂度的衡量教 学 手 段讲讲授法、案例教学法授法、案例教学法作 业 、 讨 论 、 思 考思考：1、抽象数据类型与数据类型的区别？ 2、时间复杂度的比较？课 后 小 结本章重点讲解了数据结构的相关概念、几种常见的数据结构，难点是抽象数据类型的定义以及算法时间复杂度的分析。

参 考 资 料[1］ 严蔚敏等， 《数据结构题集》,1995 ［2］ William Ford，William Topp， 《Data Structure with C++》 清华大学出版社 Prentice Hall 联合出版,1996[3] 李春葆等， 《数据结构与算法教程》 ，清华大学出版社，2005[4] （美）Mark Allen Weiss 著 冯舜玺译， 《数据结构与算法分析—c 语言描述》 ，机械工业出版社，2004（6）[5] 郝文化， 《数据结构考研教程》 ，北京希望电子出版社，2005（9） [6] 数据结构教程 李春葆编著 清华大学出版社计计算算机机与与信信息息科科学学系系教教案案教研室：教研室：计算机应用教研室 授课教师授课教师： ： 编号：编号：2授课 时间第 2 周 第 3-4 次课授课 题目第 2 章 线性表授课 类型理论课( 是 )；实践课( ) 教学 时数4 学时教 学 目 的 及 要 求1、掌握线性表的逻辑表示 2、掌握线性表的顺序表示和算法的实现 3、掌握线性表的链式表示和算法实现教 学 内 容 提 要2.1 线性表的逻辑表示 2.2 顺序表 2.2.1 顺序表的表示 2.2.2 顺序表的实现 2.3 单链表 2.3.1 链表的表示 2.3.2 单链表的实现 2.3.3 循环链表的表示与实现教 学 重 点 及 难 点重点：重点：1、顺序表的表示 2、链表的表示 3、算法的实现难难点：点：1、链表的表示与实现教 学 手 段讲讲授法、案例教学法授法、案例教学法作 业 、 讨 论 、 思 考讨论：1、顺序表与链表的使用环境？2、顺序表与链表各自的优缺点？课 后 小 结本章介绍了一种简单的数据结构—线性结构的表示与实现，要求掌握的内容： 1. 线性表的逻辑表示 2.顺序表，利用高级语言实现顺序表的算法。

3.链表的表示与实现 参 考 资 料[1］严蔚敏等， 《数据结构》 （第二版）清华大学出版社,1993［2］ William Ford，William Topp， 《Data Structure with C++》 清华大学出版社 Prentice Hall 联合出版,1996[3] 李春葆等， 《数据结构与算法教程》 ，清华大学出版社，2005[4] （美）Mark Allen Weiss 著 冯舜玺译， 《数据结构与算法分析—c语言描述》 ，机械工业出版社，2004（6）[5] 郝文化， 《数据结构考研教程》 ，北京希望电子出版社，2005（9） 计计算算机机与与信信息息科科学学系系教教案案教研室：教研室：计算机应用教研室 授课教师授课教师： ： 编号：编号：3授课 时间第 3 周 第 5 次课授课 题目第 2 章 线性表授课 类型理论课( 是 )；实践课( ) 教学 时数4 学时教 学 目 的 及 要 求1、掌握线性表的应用教 学 内 容 提 要1、线性表的合并；2、一元多项式的相加的实现教 学 重 点 及 难 点重点：重点：1、线性表的应用难难点：点：1、一元多项式的链式实现 教 学 手 段讲讲授法、案例教学法授法、案例教学法作 业 、 讨 论 、 思 考1、一元多项式相加与有序表的合并有什么异同？课 后 小 结本节介绍了线性结构的应用实例—有序表的合并和一元多项式的相加。

参 考 资 料[1］严蔚敏等， 《数据结构》 （第二版）清华大学出版社,1993［2］ William Ford，William Topp， 《Data Structure with C++》 清华大学出版社 Prentice Hall 联合出版,1996[3] 李春葆等， 《数据结构与算法教程》 ，清华大学出版社，2005[4] （美）Mark Allen Weiss 著 冯舜玺译， 《数据结构与算法分析—c语言描述》 ，机械工业出版社，2004（6）[5] 郝文化， 《数据结构考研教程》 ，北京希望电子出版社，2005（9） 计计算算机机与与信信息息科科学学系系教教案案教研室：教研室：计算机应用教研室 授课教师授课教师： ： 编号：编号：4授课 时间第 3 周 第 6 次课授课 题目第 4 章 栈与队列授课 类型理论课( 是 )；实践课( ) 教学 时数2 学时教学 目的 及要 求1、栈 2、栈的应用教 学 内 容 提 要§3.1 栈 3.1.1 抽象数据类型栈的定义 3.1.2 栈的表示和实现 §3.2 栈的应用举例 3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.3 行编辑程序 3.2.4 迷宫求解 3.2.5 表达式求值 §3.3 栈与递归的实现教学 重点 及难 点重点：重点：1、抽象数据类型栈的定义 2、栈的表示和实现难难点：点：1、抽象数据类型栈的定义教学 手段讲讲授法、案例教学法授法、案例教学法作业 、 讨论 、 思考1、顺序栈与链栈之间的区别？ 2、链栈的抽象数据类型的表示？ 3、链栈抽象数据类型的实现？课 后 小 结本章主要介绍了线性表中的一个特例—栈，它其实是操作受限制的线性表，即总在一端进行操作。

它的特点是先进后出在函数调用和操作系统中的应用非常的广泛 参 考 资 料[1］严蔚敏等， 《数据结构》 （第二版）清华大学出版社,1993［2］ William Ford，William Topp， 《Data Structure with C++》 清华大学出版社 Prentice Hall 联合出版,1996[3] 李春葆等， 《数据结构与算法教程》 ，清华大学出版社，2005[4] （美）Mark Allen Weiss 著 冯舜玺译， 《数据结构与算法分析—c语言描述》 ，机械工业出版社，2004（6）[5] 郝文化， 《数据结构考研教程》 ，北京希望电子出版社，2005（9） 计计算算机机与与信信息息科科学学系系教教案案教研室：教研室：计算机应用教研室 授课教师授课教师： ： 编号：编号：5授课 时间第 4 周 第 7-8 次课授课 题目第 3 章 栈与队列授课 类型理论课( 是 )；实践课( ) 教学 时数2 学时教 学 目 的 及 要 求1、掌握队列的抽象数据类型的定义 2、掌握队列的实现 3、理解队列的特点 4、掌握队列的应用教 学 内 容 提 要§3.4 队列 3.4.1 抽象数据类型队列的定义 3.4.2 链队列----队列的链式表示和实现 3.4.3 循环队列-----队列的顺序表示和实现 §3.5 离散事件模拟（选讲）教 学 重 点 及 难 点重点：重点：1、 队列的抽象数据类型的表示 2、队列的实现难难点：点：1、 队列的应用教 学 手 段讲讲授法、案例教学法授法、案例教学法作业 讨论 思考1、链式队列是否受限制？ 2、链式队列的实现与表示？课 后 小 结1、掌握队列与线性表之间的联系； 2、了解队列与栈之间的区别； 3、区分栈与队列在实现细节上的不同； 4、熟悉栈的特点是先进后出，队列的特点是先进先出；参 考 资 料[1］严蔚敏等， 《数据结构》 （第二版）清华大学出版社,1993［2］ William Ford，William Topp， 《Data Structure with C++》 清华大学出版社 Prentice Hall 联合出版,1996[3] 李春葆等， 《数据结构与算法教程》 ，清华大学出版社，2005[4] （美）Mark Allen Weiss 著 冯舜玺译， 《数据结构与算法分析—c语言描述》 ，机械工业出版社，2004（6）[5] 郝文化， 《数据结构考研教程》 ，北京希望电子出版社，2005（9） 。

计计算算机机与与信信息息科科学学系系教教案案教研室：教研室：计算机应用教研室 授课教师授课教师： ： 编号：编号：6授课 时间第 5 周 第 9-10 次课授课 题目第 4 章 串串授课 类型理论课( 是 )；实践课( ) 教学 时数4 学时教 学 目 的 及 要 求通过本章的学习，应使学生掌握串的各种基本操作以及串的实际应用教 学 内 容 提 要§4.1 串类型的定义§4.2 串的表示和实现4.2.1 定长顺序存储表示 4.2.2 堆分配存储表示 4.2.3 串的块链存储表示§4.3 串的模式匹配算法4.3.1 求子串位置的定位函数 Index(S，T，pos) 4.3.2 模式匹配的一种改进算法§4.4 串操作应用举例（选讲）4.4.1 文本编辑 4.4.2 建立词索引表教 学 重 点 及 难 点重点：重点： 1、串在定长顺序存储结构下的各种基本操作； 2、理解有回溯的模式匹配和无回溯的模式匹配（KMP） 算法数组的应用难难点：点： 模式匹配算法教 学 手 段讲讲授法、案例教学法授法、案例教学法作 业 、 讨 论 、 思 考1、讨论串的两种表示的不同？2、串的模式匹配与、串的模式匹配与传统传统的匹配有那些方面的改的匹配有那些方面的改进进？？课 后 小 结本章介绍了串的表示与实现，以及串的应用——模式匹配算法，该算法在图形图像处理方面应用非常的广泛。

本章主要的讲解内容如下：1． 串的存储方式2． 在不同的存储方式下的实现3． 模式匹配算法参 考 资 料[1］严蔚敏等， 《数据结构》 （第二版）清华大学出版社,1993［2］ William Ford，William Topp， 《Data Structure with C++》 清华大学出版社 Prentice Hall 联合出版,1996[3] 李春葆等， 《数据结构与算法教程》 ，清华大学出版社，2005[4] （美）Mark Allen Weiss 著 冯舜玺译， 《数据结构与算法分析—c语言描述》 ，机械工业出版社，2004（6）[5] 郝文化， 《数据结构考研教程》 ，北京希望电子出版社，2005（9） 计计算算机机与与信信息息科科学学系系教教案案教研室：教研室：计算机应用教研室 授课教师授课教师： ： 编号：编号：7授课 时间第 6-7 周 第 11－14 次课授课 题目第 5 章 数组与广义表授课 类型理论课( 是 )；实践课( ) 教学 时数7 学时教 学 目 的 及 要 求1、 掌握数组的抽象数据类型的定义；2、熟练掌握稀疏距阵的表示与地址的计算；3、掌握 三元组的定义和使用；4、了解广义表的定义；5、掌握广义表的各种计算；6。