数据结构教学资料数据结构课程各章的重点及要点.doc

《数据结构教学资料数据结构课程各章的重点及要点.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、清华大学计算机科学与技术系数据结构课程各章的重点及要点本文中列出数据结构各章教学中的重点与难点。包括数组、链接表、栈与队列、递归与广义表、树与森林、集合与搜索结构、图与网络结构，以及索引与散列结构。第一章数据结构基本概念1、基本概念：理解什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、数据结构的抽象层次。2、面向对象概念：理解什么是数据类型、抽象数据类型、数据抽象和信息隐蔽原则。了解什么是面向对象。要点：Ø抽象数据类型的封装性ØCoad与Yourdon定义：面向对象=对象+类+继承+通信。Ø面向对象系统结构的稳定性Ø面向对象方法着眼点在于

2、应用问题所涉及的对象3、算法与算法分析：理解算法的定义、算法的特性、算法的时间代价、算法的空间代价。要点：Ø算法与程序的不同之处需要从算法的特性来解释Ø算法的正确性是最主要的要求Ø算法的可读性是必须考虑的Ø程序的程序步数的计算与算法的事前估计Ø程序的时间代价是指算法的渐进时间复杂性度量第二章数组1、作为抽象数据类型的数组：数组的定义、数组的按行顺序存储与按列顺序存储要点：Ø确定数组元素的三要素：行号、列号、元素值Ø数组元素的存放地址计算2、顺序表：顺序表的定义、搜索、插入与删除要点：Ø顺序表搜索算法、平均比较次数的计算Ø插入与删除算法、平均移动次数的计算3、

3、字符串：字符串的定义及其操作的实现要点：Ø串重载操作的定义与实现第三章链接表1、单链表：单链表定义、相应操作的实现。要点：Ø单链表的两种定义方式(复合方式与嵌套方式)Ø单链表的搜索算法与插入、删除算法Ø单链表的递归与迭代算法2、循环链表：单链表与循环链表的异同3、双向链表：带表头结点的双向循环链表要点：Ø双向循环链表的定义，带表头结点的优点Ø双向链表的搜索、插入与删除算法4、多项式：多项式的定义、多项式的表示及加法要点：Ø多项式的三种表示Ø多项式链接表示的优点Ø多项式加法的实现(有序链表的合并算法)第四章栈与队列1、栈：栈的特性、栈的基本运算要点：Ø栈的数组

4、实现、栈的链表实现Ø栈满及栈空条件、抽象数据类型中的先决条件与后置条件2、栈的应用：用后缀表示计算表达式，中缀表示改后缀表示3、队列：队列的特性、队列的基本运算要点：Ø队列的数组实现：循环队列中队头与队尾指针的表示，队满及队空条件Ø队列的链表实现：链式队列中的队头与队尾指针的表示、4、双向队列：双向队列的插入与删除算法5、优先级队列：优先级队列的插入与删除算法第五章递归与广义表1、递归：递归的定义、递归的数据结构、递归问题用递归过程求解要点：Ø链表是递归的数据结构，可用递归过程求解有关链表的问题2、递归实现时栈的应用要点：Ø递归的分层(树形)表示：递归树Ø递

5、归深度(递归树的深度)与递归工作栈的关系Ø单向递归与尾递归的迭代实现3、广义表：广义表定义、长度、深度、表头、表尾要点：Ø用图形表示广义表的存储结构：Ø非递归广义表的递归算法，包括复制、求深度、求长度、删除等算法第六章树与森林1、树：树的定义、树的基本运算要点：Ø树的分层定义是递归的Ø树中结点个数与高度的关系2、二叉树：二叉树定义、二叉树的基本运算要点：Ø二叉树性质、二叉树中结点个数与高度的关系、不同种类的二叉树棵数Ø完全二叉树的顺序存储、完全二叉树的双亲、子女和兄弟的位置Ø二叉树的前序·中序·后序遍历的递归算法和使用栈的非递归算法Ø二叉树的层次遍历算法Ø中

6、序线索化二叉树、前驱与后继的查找方法、建立中序线索化二叉树的算法3、霍夫曼树：霍夫曼树的构造方法、霍夫曼编码、带权路径长度的计算要点：Ø霍夫曼树是带权路径长度最小的扩充二叉树Ø构造霍夫曼树时，按构造算法，每次具最小关键码的子树是根的左子树，具次小关键码的子树是根的右子树Ø在构造过程中，新二叉树按根的权值加入到森林的最后4、树与森林要点：Ø树的广义表表示、树的双亲表示、树的左子女-右兄弟表示Ø树、森林与二叉树的对应关系Ø树的先根·后根·层次遍历算法5、堆：堆的定义、堆的插入与删除算法要点：Ø形成堆时用到的向下调整算法Ø形成堆时的调整过程及比较次数的上界估计Ø堆

7、插入时用到的向上调整算法第七章集合与搜索1、集合的概念：集合的基本运算、集合的存储表示要点：Ø用位数组表示集合时集合基本运算的实现Ø用有序链表表示集合时集合基本运算的实现Ø并查集：并查集定义、并查集的三种基本运算的实现3、基本搜索方法要点：Ø对一般表的顺序搜索算法(包括有监视哨和没有监视哨)Ø对有序顺序表的顺序搜索算法，包括递归和非递归算法Ø用判定树(即扩充二叉搜索树)描述有序顺序表的顺序搜索，以及平均搜索长度(成功与不成功)的计算。Ø对有序顺序表的折半搜索算法、包括递归和非递归算法Ø用判定树(即扩充二叉搜索树)描述有序顺序表的折半搜索，以及平均搜索长度(成

8、功与不成功)的计算。4、二叉搜索树要点：Ø动态搜索树