绪论
数据结构三要素
逻辑结构、物理结构、数据运算
算法定义
由基本运算及规定的运算顺序所构成的完整的解题步骤
算法的特性
有穷性、确定性、可行性、输入、输出
算法设计目标
正确性、可读性、健壮性、高效率和低存储需求
算法效率的度量
时间复杂度：基本运算语句在算法中被重复执行的次数。
空间复杂度：该算法所耗费的存储空间。
数据的物理存储
1)顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。其优点是可以实现随机存取，每个元素占用最少的存储空间；缺点是只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。
2)链式存储：不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。其优点是不会出现碎片现象，能充分利用所有存储单元；缺点是每个元素因存储指针而占用额外的存储空间，且只能实现顺序存取。
3)索引存储：在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）。其优点
是检索速度快；缺点是附加的索引表额外占用存储空间。另外，增加和删除数据时也要修改索引表，因而会花费较多的时间。
4)散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希(Hash)存储。其优点是检索、增加和删除结点的操作都很快；缺点
是若散列函数不好，则可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。
递归
(1)什么是递归：函数定义过程中调用自身的方法
(2)递归调用的实现原理
系统首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；
每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈
每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行
(3)递归算法的设计
将暂且不能解决的大问题分成许多子问题，子问题还是不能解决则继续划分，直到子问题小到可以直接解决的规模，原问题的解即子问题解的合并
(4)递归算法到非递归算法的转换
利用栈保存参数,由于栈的后进先出特性吻合递归算法的执行过程,因而可以用非递归算法替代递归算法。
(5)递归的优缺点
递归算法解题通常显得很简洁，但运行效率低，在递归调用的过程中系统用栈来存储每一层的返回点、局部量，递归次数过多容易造成栈溢出等问题。
线性表
顺序表和链表
顺序表可以顺序存取也可以随机存取，链表只可以顺序存取；顺序表便于查找、修改元素，链表便于增加删除元素；采用顺序表存储时逻辑上相邻的元素物理上也相邻，采用链式存储时逻辑上相邻的元素物理上不一定相邻；链式存储空间分配灵活。
栈和队列
栈只允许在队尾进行元素的插入删除操作，队列允许在一端进行插入、另一端进行删除操作；队列先进先出，栈先进后出；
共享栈
利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。这样能够更有效的利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满时才发生上溢。
串
基本概念由0个或多个字符组成的有限序列
串的模式匹配对一个串中某子串的定位操作称为串的模式匹配。
(1)简单模式匹配
从主串的第一个位置起和模式串的第一个字符开始比较，如果相等则继续逐一比较后续字符，否则从主串的第二个字符开始重新用上一步的方法与模式串中的字符作比较，以此类推直到比较完模式串中的所有字符，若匹配成功则返回模式串在主串中的位置，匹配不成功则返回一个可区别于主串所有位置的标记
(2)KMP算法
是一种改进的字符串匹配算法，算法核心是利用匹配失败后的信息尽量减少模式串与主串的匹配次数以达到快速匹配的目的，具体实现就是通过next()函数实现，next函数包含了模式串的局部匹配信息，时间复杂度为O(m+n)
如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀，那么就可以将模式向后滑动到与这些相等字符对齐的位置，主串i指针无须回
溯，并继续从该位置开始进行比较。而模式向后滑动位数的计算仅与模式本身的结构有关，与主串无关。
树
满二叉树除最后一层外其他结点均有两棵子树
完全二叉树完全二叉树是指除了最后一层外，其他任何一层的结点数均达到最大值，且最后一层也只是在最右侧缺少结点
树的存储结构
双亲表示法：采用连续的存储空间存储结点，并为每个结点设置一个伪指针指向双亲结点在数组中的位置
孩子表示法：为每个结点建立一个单链表，单链表内存储该结点的所有孩子结点
孩子兄弟表示法：结点由三部分组成，结点值、指向第一个孩子的指针、指向下一个兄弟的指针
二叉排序树
左子树若存在则左子树的关键字均小于根结点，右子树若存在其值均大于根节点，同时左右子树又是一棵二叉排序树。
平衡二叉树
左右子树高度之差不超过1的二叉排序树
线索二叉树
为了方便找到某结点在某种遍历中的前驱后继节点，n个结点n+1个空链域，
图
存储结构
邻接矩阵、邻接表
邻接多重表、十字链表
图的遍历
(1)深度优先遍历DFS
首先访问出发点，将其标记为已访问，选取与该节点邻接的未访问过的顶点w访问并标记，再选取与w相邻接未访问的节点重复此操作。当一个顶点的所有邻接结点都被访问过时，退回到最近被访问过的节点，若该节点仍有未被访问的节点则重复访问过程，直至图中所有节点都被访问过为止。
(2)广度优先遍历BFS
首先访问起始顶点v，然后依次访问所有与v相邻的节点w1,w2…，再依次访问w1、w2所有相邻节点，直至图中所有顶点都被访问过为止
最小生成树
(1)普利姆算法
从图中任取一个顶点，把它当作一棵树，从这棵树相接的边中选取权值最小的边，并将这条边及其所连接的顶点并入这颗树中，此时再从与这棵树相接的边中选取一条最短的边，并将这条边及其所连接的顶点并入这棵树中，直至所有顶点都被并入树中。
(2)克鲁斯卡尔算法
将图中的边按权值从小到大排序，从最小边开始扫描各边，若当前边的并入不会构成回路则将其并入生成树中，直至所有的边都被检测完为止。
最短路径
(1)迪杰斯特拉 某一顶点到其余各顶点的最短路径
(2)弗洛伊德 图中任意一对顶点的最短路径
查找
线性
顺序查找：在表头设置哨兵，将待排关键字放入哨兵位置，从表尾元素向前进行对比，若找到则返回下标为止，若返回0则表示查找失败
折半查找：要求查找表为顺序存储结构且表中元素有序，当low>high时停止查找
分块查找：块间有序，块内无序，根据索引表定位块，在块中进行顺序查找
树形
二叉排序树：将关键字与根节点进行比较，若小于根节点则去左子树中查找，若大于根节点则去右子树中查找，若指针来到空链域则表示查找失败
二叉平衡树：左右子树高度之差不大于1，且左右子树也都是平衡二叉树
B树、B+树
散列结构
散列表：通过把关键码的值映射到表中的一个位置以加快查找速度。
解决冲突：开放定址法、链地址法
排序
直接插入排序：从无序序列中选取待排关键字插入有序序列中的适当位置
折半插入排序：设置三个变量low,high,mid,其中mid=(low+high)/2，当关键字>mid位置的值时，low=mid+1否则high=mid-1，直至low>high，将待排关键字插入到合适位置
希尔排序：将序列划分为若干个子序列，在子序列中进行直接插入操作，然后再对所有子序列进行直接插入操作
冒泡排序：将元素两两比较，逆序则交换，一趟结束后最大的值会来到序列最后的位置，此时一趟冒泡完成，重复直至某一趟未发生数据交换
快速排序：选择一个关键字作为枢纽，将序列中比枢纽小的关键字移至前方，比枢纽大的关键字移至后方，将序列以枢纽为中心划分为两个子序列，在对两个子序列进行同样的操作，直至每个子序列的长度为1，序列有序。
简单选择排序：从无序序列中选择最小的关键字与无序序列中的第一个关键字进行交换。
堆排序：将序列中所有关键字组成一个完全二叉树，若满足树中根节点均不大/小于左右子节点，则此树的根节点为最大/小关键字。
归并排序：将两个或两个以上的有序表合并成新的有序表
不稳定：快希选堆
nlog2n：快希归堆