《数据结构与算法》知识点整理.pdf

《数据结构与算法》知识点整理 中山大学 吕双全 一， Introduction 1，基(mei)本(shen)概(me)念(yong) 数据结构研究数据的组织方式和相应的抽象操作。 2，结合其他数据结构的时间空间复杂度分析——如09 级第9 题 二， 栈 1，栈的实现：顺序存储，注意push/pop/top 等操作实现 2，栈的应用：括号匹配、后缀表达式计算等 三， 队列 1，队列的实现：循环队列的数组实现，注意队头队尾的移动、下标的处理 【i = (i + 1) % max 】 2，应用：广搜、树的层次遍历、机场调度等 四， 链式 （Linked）栈和队列 1，链式实现下的创建、插入、删除、查找。做题时要画出每个node 的图，帮助理解。比如这样： 2，顺序和链式实现适用的场合 五， 递归 1，stack frame: 调用记录用栈保存 2，Tree of subprogram call 或recusive tree：就是画执行过程中函数调用的顺序，类似下图： 3，设计递归算法 （写代码） 4 ，递归的消除（如尾部递归）； （1）尾递归：（可能考概念，不会考实现）如果一个函数中所有递归形式的调用都出现在函数的末尾， 我们称这个递归函数是尾递归的。比如： ，函数末尾调用了自己，所以是尾递归。 使用尾递归好处：节省栈的空间。 递归到非递归有两种方法：（i）迭代，根据递归算法画出 流程图，然后建立循环结构。（ii）设置栈。 5，理解回溯法，分治法。 六， 线性表 （List）和串 （String ） 1，list 的操作的分析和实现（写代码）：Insert 插入，Remove 删除，retrieve 提取（数组中就是 “a[3]”的形式提取），traverse 遍历（对每个元素采取某种操作） 注：注意特殊情况，如头和尾的处理 2，对这些操作的时间复杂度分析： (i) 顺序表实现（利用数组）： Insert 和Remove 操作，平均移动一半元素，所以是O(n) 。retrieve 则为O(1) 。 (ii) 链式实现 （写代码） 不同实现方式的比较： 3，广义表(General List)：每个元素类型可以不同，也可以为子表。比如：C=(‘a’, (1,2,’b’)) 就是广义 表。 七， 查找 1，顺序查找如何实现，特点，复杂度。 注：复杂度就是查找长度：O(n) 2，二分查找的实现，二分查找的时间复杂度(O(log n))； 2 注： (1) 要求list 必须是有序的 (2) 代码掌握一下 3，linear index search 线性索引查找: 复杂度：比二分查找差，为O(log n) – O(n)之间 2 3，Binary Search Tree 二分查找树 （也叫Binary Sort Tree ） (1)，概念、复杂度 (2)，查找过程及 【代码实现】 【非递归方法】 (3)，【插入和删除操作】 【自己找一下代码！】 4 ，AVL Tree （1）定义 （2 ）插入、删除操作，及涉及的调整——详细看课件理解！ 5，B 和B+树——非重点 八， 排序 0，排序大纲 1,重要排序——掌握原理、代码实现及手工画图分析过程、性能分析 Insertion sort 插入排序