数据结构
数据结构是相互之间存在一种或多种特定关系的数据元素的集合
逻辑结构(分为线性结构和非线性结构)
反映数据元素之间的逻辑关系的数据结构，是针对具体问题的，可以表示成一种或多种存储结构
集合结构(非线性结构)
集合通常是由一组无序的, 不能重复的元素构成 数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系
线性结构
线性结构是一个有序数据元素的集合，常用的线性结构有：线性表，栈，队列，双队列，数组，串。 非线性结构，其逻辑特征是一个结点元素可能有多个直接前趋和多个直接后继。常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)。
线性结构是一个有序数据元素的集合
数组
线性表
0个或多个具有相同类型的数据元素的有限序列
存储结构
顺序存储结构
顺序存储结构，用一段地址连续的存储单元 一次存储线性表的数据元素。比如数组
每个数据元素存数据元素信息外(数据域)，还要存储它的后继元素的存储地址(指针域)
优点：
无需为表示表中元素之间的逻辑关系而增加额外的存储空间
可以快速的存取表中任意位置的元素，时间复杂度为O(1)
缺点：
插入和删除操作需要移动大量元素
当线性表变化较大时，难以确定存储空间的容量
造成存储空间的"碎片"
链式存储结构
用一组任意的存储单元存储线性表的数据元素， 这组存储单元可以是连续的，也可以是不连续的
单链表
链表中每个结点可以包含若干个数据域和若干个指针域。 如果每个结点中只包含一个指针域，则称其为单链表。
优点：
单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制
插入和删除更快，时间复杂度为O(n)，在给出某位置的指针后，复杂度仅为O(1)
缺点：
查找效率比顺序存储结构差，时间复杂度为O(n)
静态链表
用数组描述的链表叫静态链表(用数组代替指针)
为了给没有指针的高级语言设计的视线单链表的方法，很少用(虽然java,c#也没有指针，但是引用类型相当于变样实现了指针)
优点： 插入和删除只需要修改游标，无需移动元素 从而改进了在顺序存储结构中的插入，删除移动大量元素的缺点
缺点： 没有解决连续存储分配带来的表长难以确认的问题 失去了顺序存储结构随机存取的特性
循环链表
将单链表中终端结点的指针段由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表就
称为单循环链表，简称循环链表
双向链表
在单链表的每个结点中，再设置一个指向其前驱结点的指针域 (就意味着双向链表的结点都有俩个指针域，一个指向直接后继， 一个指向直接前驱)
栈(特殊的线性表)
限定仅在表尾进行插入和删除操作的线性表，又称后进先出(LIFO)的线性表 (允许插入和删除的一端称为栈顶，另一端称为栈底)
队列(特殊的线性表)
只允许在一端进行插入操作，而另一端进行删除操作的线性表 先进先出(FIFO)
顺序存储结构(顺序队列)
循环队列
链式存储结构(链队列)
串(字符串)
有0个或多个字符组成的有限序列
针对的是字符集，就是说把字符串中多个字符连在一起
存储结构
顺序存储结构
链式存储结构
模式匹配
朴素的描述匹配 (从头开始一个个字符匹配)
效率很低，复杂度为O((n-m+1)*m) n是总的字符串，m是需要匹配的字符串
KMP模式匹配算法
算法证明和更详细的说明，请参阅《算法导论》第2版第32章字符串匹配
KMP模式匹配算法改进
树形结构(非线性结构)
数据元素之间存在一对多的层次关系
数是n(n>=0)个节点的有限集。若n=0,称为空树。树的节点是互不交互的。 + 度：节点拥有的子数(节点)数量称为"度"，度为0的称为叶节点。 + 树的度：树的度是树内各节点的度的最大值 + 节点的层次：跟为第一层，一次类推。 + 数的深度：数中节点的最大层次称为"深度"或"高度"
二叉树
特点
每个结点最多有俩棵子树
左右子树是顺序的，次序不能颠倒
即使树中只有一棵子树，也要区分左右
五种形态
空二叉树
只有一个根结点
根结点只有左子树
根结点只有右子树
根结点既有左子树，又有右子树
性质
在二叉树的第i层上之多有2i-1(i-1是上标)个结点
深度为K的二叉树至多有2k-1(k>=1,k是上表)个结点
特殊二叉树
斜树
所有结点都只有左子树的二叉树叫左斜树
所有结点都只有右子树的二叉树叫右斜树
满二叉树
一个二叉树中，所有分支结点都存在左子树和右子树， 并且所有叶子都在同一层上，称为满二叉树
完全二叉树
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中 在最左边，这就是完全二叉树。
线索二叉树
每个二叉树左右俩个指针域，如果为空，放着也浪费空间。 所以第一次遍历二叉树时，如果左指针域为空就存前驱地址， 右指针域为空就存后继地址。但是左侧需要一个tag来标识左指 针域存的是左孩子结点还是前驱，右侧也同样需要。
存储结构
顺序存储结构
只用于完全二叉树(因为完全二叉树定义的严格， 可以用顺序结构表示出二叉树的结构，很有优越性。详情参考P172) 该结构不太通用，通用的见二叉链表
二叉链表
二叉树每个结点最多有俩个孩子，所以可以用 一个数据域+俩个指针域这样的结构存储二叉树
