《数据结构与算法》知识点整理 中山大学 吕双全 一， 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(log2n))； 注： (1) 要求 list 必须是有序的 (2) 代码掌握一下 3，linear index search 线性索引查找: 复杂度：比二分查找差，为O(log2n) – O(n)之间 3，Binary Search Tree 二分查找树（也叫Bina...
