文档详情

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

发布:2017-05-22约3.11千字共9页下载文档
文本预览下载声明
《数据结构与算法》知识点整理 中山大学 吕双全 一, 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 插入排序
显示全部
相似文档