《数据结构与算法》知识点整理.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 插入排序
显示全部