数据结构教学计划

学时：
课堂教学：24学时
时间：2001年3月11日-2001年4月4日，每周日和周三

地点：科技楼

授课对象背景分析
微电子设计研究室硕士和博士研究生
要求：掌握C语言，最好掌握C++

教学环境和方式：
要求教师有计算机一台和黑板，最好有投影仪，每节课内容应制作幻灯
学生有充分的上机时间和上网条件，有自己的电子邮箱
教师和学生以电子邮件通信
教师为学生提供：讲课提纲、疑难解答
学生向老师提供：作业、疑问
作业：由教师每次讲课后给出，其完成是自愿的。
考试：结合微电子设计中的特定问题，设计一任务求解算法

教材：
英文版：《Data Structures with C++》William Ford, William Topp. 清华大学出版社，1998年11月第1版
中文版：《数据结构C++语言描述》，刘卫东，沈官林译。清华大学出版社，1997年3月第1版

授课内容

3月11日 面向对象设计概念 第1小时类和对象的概念

第2小时封装性及实现

第3小时继承性及实现

3月14日数组第1小时群体类

第2小时数组

第3小时特殊矩阵

3月18日 查找和排序 第1小时查找：线性/对半

第2小时排序：选择/冒泡/快速

第3小时算法复杂性分析方法

3月21日 链表和稀疏矩阵 第1小时指针和链表的概念

第2小时链表的基本运算

第3小时稀疏矩阵

3月25日 堆栈和队列 第1小时栈的概念与实现

第2小时队的概念与实现

第3小时递归的概念

3月28日树第1小时树的定义及其存储结构

第2小时二叉树的定义和遍历

第3小时堆

4月1日图第1小时图的定义和基本概念

第2小时图的存储结构

第3小时图的遍历

4月4日 数据结构实践:VC和Verilog 第1小时 VC中的数据结构

第2小时 Verilog中的数据结构

第3小时数据结构的有关研究资源

教材阅读推荐意见：
重点、一般要求、自习

章节 所属课节 要求

第1章概述
1．1 抽象数据类型
1．2 C++类和抽象数据类型
1．3 C++应用中的对象
1．4 对象设计
1．5 类继承的应用
1．6 面向对象程序设计
1．7 程序测试与维护
1．8 C++程序设计语言
1．9 抽象基类及多态性 1 重点

第2章基本数据类型
2．1 整型
2．2 字符类型
2．3 实数类型
2．4 枚举类型
2．5 指针
2．6 数组类型
2．7 文本串及变量
2．8 记录
2．9 文件
2．10 数组和记录的应用无自习

抽象数据类型和类
3．1 对象类型类
3．2 类的举例
3．3 对象和信息传递
3．4 对象数组
3．5 多构造函数
3．6 应用举例：三角矩阵 1 一般要求

第4 章群体类
线性群体
非线性群体
算法分析
顺序查找与折半查找
基本的顺序表类 2 一般要求

第5章栈和队列
栈
类Stack
表达式求值
队列
类Queue
优先级队列
实例研究:事件驱动模拟 5 重点

第6章抽象操作
运算符重载
有理数
有理数类
作为成员函数的有理数运算
作为友元函数的有理数流运算符
有理数的转换
有理数的使用无自习

第7章形式数据类型
模板函数
模板类
表的模板类
中缀表达式求值无自习

第8章类和动态存储
指针与动态数据结构
动态申请对象
赋值与初始化
安全数组
串类
模式匹配
整型集合 4 自习

第9章链表
节点类
构造链表
设计链表类
类LinkedList
LinkedList类的实现
用链表实现集合
实例研究：打印缓冲池
循环表
双向链表
实例研究：窗口管理 4 重点

第10章递归
10．1 递归的概念
10．2 设计递归函数
10．3 递归代码和运行时堆栈
10．4 用递归进行问题求解
10．5 递归评估 5 一般要求

第11章树
11．1 二叉树结构
11．2 设计TreeNode函数
11．3 树扫描算法的使用
11．4 二叉搜索树
11．5 二叉搜索树
11．6 BinSTree的实现
11．7 实例研究：索引 6 重点

第12章继承和抽象类
12．1 继承概述
12．2 C++中的继承
12．3 多态性和虚函数
12．4 抽象基类
12．5 迭代算子
12．6 有序表
12．7 异构表无自习

第13章高级非线性结构
13．1 基于数组的二叉树
13．2 堆
13．3 Heap类的实现
13．4 优先级队列
13．5 AVL树
13．6 AVL树类
13．7 树迭代算子
13．8 图
13．9 Graph类 6/7 一般要求
（图为重点）

第14章群体数据的组织
14．1 数组排序的基本算法
14．2 快速排序
14．3 哈希法
14．4 哈希表类
14．5 搜索方法的性能
14．6 二进制文件和外部数据操作
14．7 辞典 3 一般要求

3月11日面向对象设计概念	第1小时	类和对象的概念
	第2小时	封装性及实现
	第3小时	继承性及实现
3月14日数组	第1小时	群体类
	第2小时	数组
	第3小时	特殊矩阵
3月18日查找和排序	第1小时	查找：线性/对半
	第2小时	排序：选择/冒泡/快速
	第3小时	算法复杂性分析方法
3月21日链表和稀疏矩阵	第1小时	指针和链表的概念
	第2小时	链表的基本运算
	第3小时	稀疏矩阵
3月25日堆栈和队列	第1小时	栈的概念与实现
	第2小时	队的概念与实现
	第3小时	递归的概念
3月28日树	第1小时	树的定义及其存储结构
	第2小时	二叉树的定义和遍历
	第3小时	堆
4月1日图	第1小时	图的定义和基本概念
	第2小时	图的存储结构
	第3小时	图的遍历
4月4日数据结构实践:VC和Verilog	第1小时	VC中的数据结构
	第2小时	Verilog中的数据结构
	第3小时	数据结构的有关研究资源

章节	所属课节	要求
第1章概述 1．1 抽象数据类型 1．2 C++类和抽象数据类型 1．3 C++应用中的对象 1．4 对象设计 1．5 类继承的应用 1．6 面向对象程序设计 1．7 程序测试与维护 1．8 C++程序设计语言 1．9 抽象基类及多态性	1	重点
第2章基本数据类型 2．1 整型 2．2 字符类型 2．3 实数类型 2．4 枚举类型 2．5 指针 2．6 数组类型 2．7 文本串及变量 2．8 记录 2．9 文件 2．10 数组和记录的应用	无	自习
抽象数据类型和类 3．1 对象类型类 3．2 类的举例 3．3 对象和信息传递 3．4 对象数组 3．5 多构造函数 3．6 应用举例：三角矩阵	1	一般要求
第4 章群体类线性群体非线性群体算法分析顺序查找与折半查找基本的顺序表类	2	一般要求
第5章栈和队列栈类Stack 表达式求值队列类Queue 优先级队列实例研究:事件驱动模拟	5	重点
第6章抽象操作运算符重载有理数有理数类作为成员函数的有理数运算作为友元函数的有理数流运算符有理数的转换有理数的使用	无	自习
第7章形式数据类型模板函数模板类表的模板类中缀表达式求值	无	自习
第8章类和动态存储指针与动态数据结构动态申请对象赋值与初始化安全数组串类模式匹配整型集合	4	自习
第9章链表节点类构造链表设计链表类类LinkedList LinkedList类的实现用链表实现集合实例研究：打印缓冲池循环表双向链表实例研究：窗口管理	4	重点
第10章递归 10．1 递归的概念 10．2 设计递归函数 10．3 递归代码和运行时堆栈 10．4 用递归进行问题求解 10．5 递归评估	5	一般要求
第11章树 11．1 二叉树结构 11．2 设计TreeNode函数 11．3 树扫描算法的使用 11．4 二叉搜索树 11．5 二叉搜索树 11．6 BinSTree的实现 11．7 实例研究：索引	6	重点
第12章继承和抽象类 12．1 继承概述 12．2 C++中的继承 12．3 多态性和虚函数 12．4 抽象基类 12．5 迭代算子 12．6 有序表 12．7 异构表	无	自习
第13章高级非线性结构 13．1 基于数组的二叉树 13．2 堆 13．3 Heap类的实现 13．4 优先级队列 13．5 AVL树 13．6 AVL树类 13．7 树迭代算子 13．8 图 13．9 Graph类	6/7	一般要求（图为重点）
第14章群体数据的组织 14．1 数组排序的基本算法 14．2 快速排序 14．3 哈希法 14．4 哈希表类 14．5 搜索方法的性能 14．6 二进制文件和外部数据操作 14．7 辞典	3	一般要求