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

《数据结构与算法》知识点整理中山大学吕双全一，Introduction1，基(mei)本(shen)概(me)念(yong)数据结构研究数据的组织方式和相应的抽象操作。2，结合其他数据结构的时间空间复杂度分析——如09级第9题二，栈1，栈的实现：顺序存储，注意push/pop/top等操作实现2，栈的应用：括号匹配、后缀表达式计算等三，队列1，队列的实现：循环队列的数组实现，注意队头队尾的移动、下标的处理【i=(i+1)%max】2，应用：广搜、树的层次遍历、机场调度等四，链式（Linked）栈和队列1，链式实现下的创建、插入、删除、查找。做题时要画出每个node的图，帮助理解。比如这样：2，顺序和链式实现适用的场合五，递归1，stackframe:调用记录用栈保存2，Treeofsubprogramcall或recusivetree：就是画执行过程中函数调用的顺序，类似下图：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，广义表(GeneralList)：每个元素类型可以不同，也可以为子表。比如：C=(‘a’,(1,2,’b’))就是广义表。七，查找1，顺序查找如何实现，特点，复杂度。注：复杂度就是查找长度：O(n)2，二分查找的实现，二分查找的时间复杂度(O(log2n))；注：(1)要求list必须是有序的(2)代码掌握一下3，linearindexsearch线性索引查找:复杂度：比二分查找差，为O(log2n)–O(n)之间3，BinarySearchTree二分查找树（也叫BinarySortTree）(1)，概念、复杂度(2)，查找过程及【代码实现】【非递归方法】(3)，【插入和删除操作】【自己找一下代码！】4，AVLTree（1）定义（2）插入、删除操作，及涉及的调整——详细看课件理解！5，B和B+树——非重点八，排序0，排序大纲1,重要排序——掌握原理、代码实现及手工画图分析过程、性能分析Insertionsort插入排序Selectionsort选择排序Quicksort快速排序Mergesort归并排序Heapsort堆排序2，性质概念九，表格（Table）和信息检索（InformationRetrieval）1，多维数组在内存中存储次序——rowmajor/columnmajor（做题时带特殊值分析！）2，特殊矩阵存储——知道如何与一维内存中的位置对应！注：下图中strictlyuppertriangularmatrix没包含对角线元素，但我们做题时应是普通的上三角，即当包含对角线元素。此外还有Sparsematrix稀疏矩阵（非重点），对照课件简单看下如何存储3，Hash——既是查找方式，也是存储方式（1）大纲（2）常用哈希函数（3）Conflict(Collision)handling（重要，看课件复习细节）其中Openaddressing的实现有:linearprobing和quadraticprobing十，二叉树（BinaryTree）10.2.1遍历二叉树10.2.2Threaded线索二叉树10.3.1遍历树的应用：（1）查找元素（2）统计叶节点个数（3）层次遍历二叉树10.3.2哈弗曼树1，二叉树（binarytrees)的概念,层，高度，边数，结点数和度数等；2，二叉树的链式存储结构，连续存储结构；3，二叉树的遍历（前序、中序、后序、逐层）及其实现（递归和非递归）;4，二叉搜索树(binarysearchtrees)的概念；5，二叉搜索树的搜索、插入、删除；6，平衡二叉排序树(AVLtrees)的概念和构造方法;十一，树重点关注树、森林和二叉树的转换方法十二，图1，图的概念（扫一眼课件）2，图的两种表示法:AdjacentMatrix邻接矩阵与AdjacentList邻接表3，图的Depth-First深度优先/Breadth-First广度优先遍历算法及其实现4，拓扑排序及其实现5，求Shortestpath最短路径的算法（Prim/Kruskal）及其实现6，求Minimumspanningtree最小生成树的算法及其实现7，Criticalpath关键路径（比较少考，但最好看一下）