鲍捷,2001年2月23日
学时:
课堂教学: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 | 一般要求 |
[Return to Jie Bao's Homepage]