数据结构
'图片点击放大就横过来了 查找里面少了个哈希表'
#大部分我都手写笔记了
逻辑结构
集合、线性、树（一对多）、图（多对多）
物理结构（存储结构）
顺序存储(存储单元连续)、链式存储(存储单元可连续可不连续)
复制代码线性表
------顺序表与单链表---------
前驱、后继
头指针、尾指针、头结点、尾节点
头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
----------------------------------------
p是指向线性表第i个元素的指针，则该该结点ai的数据域为p->data，指针域为p->next，p->next->data为第ai+1指针域
查：单链表查核心思想"工作指针后移"
插入：单链表在p与p->next之间插入s，s->next=p->next，p->next=s；两者顺序不可调换，否则找不到s->next
删除：删除介于结点q，q位于结点p与q->next之间，
p->next = p->next->next,用q取代p->next, p-next= q->next;
顺序表整表创建：其实就是一个数组初始化
单链表整表创建：头插法、尾插法
单链表整表删除：声明结点p、q
将第一个结点赋值给p，
循环：
将下一个结点赋值给q； q=p->next
释放p； free(p)
将q赋值给p； p = q
-----------------------------------------
单链表与顺序表的异同，考虑时间复杂度与空间复杂度
1. 时间复杂的方面：
***注意：****
单链表插入删除操作时间复杂度优的前提是：查找到了位置i(查找时间复杂度O(n))，以后在从i位置依次多次插入删除时间复杂度才为O(1)，这样才能体现出链表的插入删除优于顺序表的地方
线性表顺序存储结构 存、读、改 时间复杂度O(1),插入、删除时间复杂度O(n)
线性表链式存储结构(单链表的Node包括数据域与后继元素存储地址的指针域)查找、插
入和删除时间复杂度都是O(n)，
如果在我们不知道第i个元素的指针位置，单链表数据结构在插入和删除操作上，与线性表的顺序存储结构是没有太大优势，
但如果我们，希望从第i个位置，插入10个元素，对于顺序表而言，每一次插入都需要移动n-1个元素，每次都是0(n)，而单链表，我们只需在第一次，找到第i个位置的指针，此时为O(n)，接下来只是简单地通过赋值移动指针而已，时间复杂度都是0(1)，
显然，对于插入或者删除数据越频繁的操作，单链表的效率优势就是越明显。
2. 空间复杂度方面：
顺序表：预分配存储空间，分大了浪费，分小了容易发生溢出，现在有动态增长分配，不过会消耗性能
单链表：不需要存储分配，只要有就可以分配，元素个数也不受限制
-----------------------------------------
复制代码用“.”的话，只需要声明一个结构体。格式是，结构体类型名+结构体名。然后用结构体
名加“.”加域名就可以引用域 了。因为自动分配了结构体的内存。如同 int
a;一样。用->的话，要声明一个结构体的指针，还要手动开辟一个该结构体的内存，然
后把返回的指针给声明的结构体指针。才能用->正确引用。否则内存中只分配了指针的
内存，没有分配结构体的内存，想要的结构体实际上是不存在。这时候用->引用自然出
错了，因为没有结构体，自然没有结构体的域了。"."我直接读做"的”。->我读作"指向
的结构体的"。
typedef struct {
int x;
int y;
} Point;
Point pos;
pos.x = 10;
pos.y = 5;
Point* pPos = &pos;
(*pPos).x = 15;
pPos->y = 20;
复制代码-------静态链表----------
静态链表与动态链表的异同点
异：静态链表是数组实现的，是顺序存储结构，在物理地址上是连续的，而且需要预先
分配大小。动态链表是用内存申请函数（malloc）动态申请内存的，所以每个节点的物
理地址是不连续的，要通过指针来顺序访问。
同：在插入或者删除数据时只需修改指针即可，不用移动元素。
复制代码-------单向循环链表-----------
-----------------------------------------
***使用头指针+头结点情况：***
将单链表的终端节点指针域为空指针改为指向头结点
判断循环，由p->next是否为空改为，p->next是否等于头结点指针
-----------------------------------------
***使用尾指针+使用头结点：***
当使用头指针+头结点时候，访问第一个节点的时间复杂度为O(1)，访问最后一个节点的时间复杂度为O(n)，想要访问第一个结点与最后一个结点的时间复杂度都为O(1)解决办法？？？？
不使用头指针+使用头结点，而是用指向终端节点的**尾指针**来标示循环链表，终端结点尾指针rear，查找终端节点时间复杂度O(1),而查找第一个结点，就是rear->next->next；其时间复杂度也为0(1)
当两个循环链表合并：
说明：循环链表A的终端节点与循环链表B的第一个指针相连情况，
p = rearA->next 链表A的头结点
rearA->next = rearB->next->next 链表A的尾节点指向链表B的第一个结点
rearB->next=p 链表B的尾指针指向链表A的头结点
复制代码------双向循环链表---------
双向链表：在单链表的每个节点中，在设置一个指向其前驱结点的指针域
Node(前驱指针域prior、数据域data、后继指针域next)
当然双向链表也可以成为双向循环链表
p->next->prior=p=p->prior->next
双向链表的插入：
说明：在结点p与p->next之间插入结点s
s->next = p->nex
s->prior = p
p->next->prior = s->next
p->next = s
双向链表的删除：
说明：删除结点p
p->prior->next = p->next
p->next->prior=p->prior
复制代码特殊线性表 栈与队列
-------栈--------
栈(stack)是限定仅在表尾进行插入和删除操作的线性表
允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何元素的栈称为空栈，栈又称为先进后出的线性表，LIFO(last in first out)
压栈(入栈)push、弹栈pop
---------------栈的顺序存储结构 顺序栈--------------------------
栈的顺序存储结构(顺序栈)
由于线性表顺序存储结构是使用数组来实现的，对于栈这种只能在一头插入和删除操作的线性表来说，***用数组下标为0的一端作为栈底比较好***
----
定义一个top指针来指示栈顶元素在数组中的位置，当栈存在一个元素时，top指针等于0，因此通常把空栈的判定条件设定为top为-1；
进栈操作: 栈s插入e
s->top++;
s->data[s->top] = e
出栈操作：
s->top--;
**顺序栈进栈与出栈两者的时间复杂度均为O(1)**
----
两栈共享空间：
使用这样的数据结构通常是当两栈空间需求相反时
用一个数组来存储两个栈，让一个栈(stack1)的栈底为数组的始端，即下表指针为0，另一个栈(stack2)的栈底为数组的末端，即下标为n-1处
当stack1为空时，top1 = -1，stack2为空时，top2 = n；
栈满：top1+1 == top2
---------------栈的链式存储结构 链栈--------------------------
基于栈只是栈顶进行插入和删除的操作，而单链表有头指针，而栈顶指针是必须的，那么将它合二为一，
所以把***链栈栈顶放在单链表的头部***，因为有了栈顶指针，那么头结点也就失去了意义，通常对于链栈来说，是不需要头结点的
链栈进栈：
说明：链栈S push新结点s
s-<next=S->top
S->top=s
S->count++
链栈出栈：
S->top=s->top->next
free(p)
S->count--
**链栈进栈与出栈的时间复杂度均为0(1)**
顺序栈与链栈的选择
元素数量变化不可预料使用链栈，如果元素数量在可控范围内，建议使用顺序栈
---------------栈的应用--------------------------
栈的应用-递归：
**递归解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归**
斐波那切数列
我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称为递归函数
在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中，在回退阶段位于栈顶的局部变量、参数值以及返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用状态
单向递归和尾递归：
**一般对于单向递归和尾递归的情况, 都可用循环方法将递归过程改为非递归过程**
---------
栈的应用-四则运算表达式求值：
计算机计算不需要括号的的后缀表达式，称为逆波兰表达式 RPN，教后缀表达式的原因在于所有的符号都是在运算数字的后面出现
规则：从左向右遍历表达式的每个数字和符号，遇到数字就进栈，遇到是符号就将栈顶两个数字出栈，进行运算，运算结果进栈，一直得到最终结果进栈
平时我们使用的标准四则运算表达式，叫做中缀表达式。
中缀表达式转后缀表达式规则：
从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分，若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号(先乘除后加减)则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止
复制代码有些简单的递归问题，可以不借助堆栈结构而改成循环的非递归问题。这里说的简单，
是指可以通过一个简单的数学公式来进行推导，如阶乘问题和斐波那契数列数列问题。
这些可以转换成循环结构的递归问题，一般都可以优化成尾递归的形式。很多编译器都
能够将尾递归的形式优化成循环的形式
复制代码由于递归函数是在运行过程中调用其自身，所以会占用大量的栈上空间，而且压栈和出栈都是有时间消耗的。所以从这一点上来看，递归的效率是不如循环。
除了效率之外，递归另一个相当明显的问题：可能会导致栈溢出。当递归调用的次数过大时，非常有可能会出现栈溢出的情况。
***递归算法的时间复杂度***
复制代码- 递归算法的时间复杂度终结篇
- [递归与循环]
- [分治法和动态规划法递归思想的经典应用]
-------队列--------
队列(queue)：只允许在一端进行插入操作，而在另一端进行删除操作的的线性表
队列是一种先进先出(first in first out)的线性表，简称FIFO，允许插入的一端称为队尾，允许删除的一端称为队头
假设队列是q=(a0,a1、、、an-1),那么a0就是队头元素，an-1就是队尾，这也比较符合我们的日常生活习惯，排在第一的优先出列，最后来的当然排在队伍最后
-------
队列的顺序存储结构：
增加元素的时间复杂度O(1)，出列删除时间复杂度O(n)
-------
循环队列：
为了出列避免大量元素移动，不去限制队列元素必须存储在数组的前n个单元这一条件，出列的性能大大增加，也就是说队头不需要一定要在下标为0的位置。出队后，队头自然后移
为了当避免只有一个元素时，队头和队尾重合变得麻烦，所以引入两个指针，front指针指向队头元素，***rear指针指向队尾元素的下一位置***。当front等于rear时，队列为空
初始状态front与rear指针位置均为0，注意假溢出现象(rear = n队尾为最后一个已经有数据，当再添加元素，如果front=0，真溢出，若front>0，假溢出)
解决假溢出的办法就是后面的满了，就在从头开始，也就是头尾相接循环，我们把队列这种头尾相接的顺序存储结构称为循环队列
队列满的条件是：(rear+1)%QueueSize == front #QueueSize队列最大尺寸
计算队列长度公式：(rear - front + QueueSize)%QueueSize
-------
队列的链式存储结构：
链队列是有头结点的
将队头指针front指向链队列的***头结点***，尾指针rear指向终端结点
链队列入列：
说明：队列Q，插入元素e 且Q有头结点，front指向头结点，则头结点为front->next,队头元素为front->next->next
Q->rear->next = e
Q->rear = s
链队列出列：
Q->front->next = Q->front->next->next
------
链队列与循环队列比较
两者入列出列的时间复杂度均为0(1)，循环队列需要事先申请好空间，使用期间不释放，而链队列，每次申请和释放结点也会存在一点时间开销，总体来说链队列更加灵活。
复制代码串
串(string)是由零个或多个字符组成的有限序列，又名字符串
所谓序列，说明串的相邻字符之间具有前驱和后继的关系
字串：串中任意个数的连续字符组成的子序列称为该串的字串，相应的包含字串的串称为主串
字串在主串中的位置就是字串第一个字符在主串中的位置
-----------串的比较-------------
具体看下面链接编码演变过程：
最开始7位，总共可以表示128个字符，扩展的ASCII 由8位二进制数表示一个字符，总共可以表示256个字符
Unicode由16位二进制数表示一个字符，UTF-8 是 Unicode 的实现方式之一。
UTF-8 最大的一个特点，就是它是一种变长的编码方式。它可以使用1~4个字节表示一个符号，根据不同的符号而变化字节长度
计算机自己能理解的“语言”是二进制数，最小的信息标识是二进制位，8个二进制位表示一个字节
人类所使用的这些字符集转换为计算机所能理解的二级制码，这个过程就是编码，他的逆过程称为解码
1. ASCII 满足英文
2. 其他国家扩展，中国GB2312—1980，这个字符集共收入汉字6763个和非汉字图形字符682个，采用两个字节对字符集进行编码，并向下兼容ASCII编码方式。
再后来生僻字、繁体字及日韩汉字也被纳入字符集，就又有了后来的GBK字符集及相应的编码规范，GBK编码规范也是向下兼容GBK2312的。
3. Unicode字符集涵盖了世界上所有的文字和符号字符，Unicode编码方案为字符集中的每一个字符指定了统一且唯一的二进制编码，这就能彻底解决之前不同编码系统的冲突和乱码问题。
***字符代码和字符编码:***字符代码是特定字符在某个字符集中的序号，而字符编码是在传输、存储过程当中用于表示字符的以字节为单位的二进制序列。
4. 为了有效节约存储或传输资源，在字符代码和字符编码间进行再编码，这样就引出了UTF-8、UTF-16等编码方式
在目前全球互联的大背景下，Unicode字符集和编码方式解决了跨语言、跨平台的交流问题，同时UTF-8等编码方式又有效的节约了存储空间和传输带宽，因而受到了极大的推广应用。
-----
串的抽象数据类型
串和线性表很相似，不同之处在于串针对的是字符集，而且对于串的基本操作和线性表还是有很大差别的，线性表更多关注的是单个元素的操作，比如查找一个元素，插入或删除一个元素，但串中更多的查找串的位置、得到指定的子串、替换子串等操作
串中元素仅由一个字符组成，相邻元素具有前驱和后继关系
------
串的顺序存储结构：
串的顺序存储结构是用一组连续的存储单元来存储串中的字符序列的，按照预定的大小，为每个定义的串分配一个固定长度的存储区，一般是用定长数组来定义
串的操作很有可能使得串的长度超过了数组的长度MaxSize，所以对于串的顺序存储，串的存储空间可在程序执行过程中动态分配而得，比如在计算机中存在一个*存储区：堆，这个堆可以由C语言动态分配函数malloc()和free()来管理
-----
串的链式存储结构：
在考虑到空间浪费的问题上，所以一个结点可以存放一个字符，也可存放多个字符，最后一个结点若是未被占满时，用'#'或其他非串值字符补全。
-----
串的链式存储结构不如顺序存储结构灵活，性能也不如顺序存储结构好
-----
朴素的模式匹配算法
说明：主串S，字串T
就是对主串的每一个字符作为串的开头，与要匹配的字符串进行匹配，对主串进行大循环，每个字符开头做字串T的长度的小循环，直到匹配成功或者全部遍历完为止。
当主串S匹配开头到最后长度小于T时就不用匹配了吧？？？
-----
KMP模式匹配算法
KMP算法仅当模式与主串之间存在许多"部分匹配"的情况下才能体现它的优势，否则两者差异不明显
-----
KMP基础上算法优化
复制代码树
根、子树
树是一种非线性的数据结构，是由n（n >=0）个结点组成的有限集合。
如果n==0，树为空树。
如果n>0，
树有一个特定的结点，根结点
根结点只有直接后继，没有直接前驱。
除根结点以外的其他结点划分为m（m>=0）个互不相交的有限集合，T0，T1，T2，...，Tm-1，每个结合是一棵树，称为根结点的子树。
**树的定义两点要素**
1. n>0时根节点是唯一的
2. 子树的个数虽然没有限制，但它们一定不相交
树的度： 根节点、内部结点、叶子节点(终端节点)
节点拥有的子树个数称为该节点的度，度为0的结点称为叶节点或终端节点；度不为0的结点称为非终端节点或分直接点，除根节点之外，分支结点也称为内部结点。
树的度是树内结点的度的最大值
树的前驱和后继：
**结点的直接后继称为结点的孩子**，结点称为孩子的双亲。
结点的孩子的孩子称为结点的孙子，结点称为子孙的祖先。
同一个双亲的孩子之间互称兄弟。
树的深度：
**树中根结点为第1层**，根结点的孩子为第2层，依次类推。
树中结点的最大层次称为树的深度或高度
树的有序性：
如果树中结点的各子树从左向右是有序的，子树间不能互换位置，则称该树为有序树，否则为无序树。
深林：
深林是m(m>0)棵树互不相交的树的集合
-------
树的存储结构：
1. 双亲表示法：
ADT
数据域 双亲域 长子域(左孩子) 右兄弟域(sibling)
下标 | data | parent | firstchild | rightsib
根节点双亲用-1表示
如果没有左孩子结点，这个长子域设置为-1
如果没有右兄弟，则域设置为-1
2. 孩子表示法：
由于树中每个结点可能有多颗子树，可以考虑用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根节点，我们把这种方法叫做多重链表表示法
方案一：
指针域的个数等于树的度
ADT 例如树的度为n
data child1 child2、、childn
树的各个结点的度，相差不大时候，利用这种存储结构比较好
方案二：
指针域的个数等于该结点的度数
这种方法在结点的度的数值维护上带来时间上的损耗，解决办法：
把每个结点放到一个顺序存储结构的数组中，由于每个结点的孩子个数是不确定的，所以我们再对每个结点的孩子建立一个单链表来体现他们的关系。如果是叶子结点则此单链表为空
ADT
data firstchild 结点线性表 二维数组？？
child next 孩子结点
如果想知道某个结点双亲，***双亲孩子表示法：***
data parent firstchild 三维数组？？
3. 孩子firstchild(left )兄弟(rightsib)表示法：
ADT
data firstchild rightsib
data是数据域，firstchild为指针域，存储该结点的第一个孩子结点(左)的存储地址，rightsib是指针域，存储该结点的右兄弟结点的存储地址
-------------二叉树------------------
在链表中，插入、删除速度很快，但查找速度较慢。
在数组中，查找速度很快，但插入删除速度很慢。
为了解决这个问题，找寻一种能够在插入、删除、查找、遍历等操作都相对快的容器，于是人们发明了二叉树
有序链表，不行，查找（包括1需要找到对应位置，以及2查找）成本大O(N)，但具体这个插入操作成本小O(1)。
用有序数组，查找（2的查找）成本小O(1)。但1的插入操作成本很大O(N)。
所以，我们折中使用排序二叉树（二叉树仅仅作为排序二叉树的基础），查找（包括1需要找到对应位置，以及2查找）成本挺小O(logN)。具体这个插入操作成本也挺小O(logN)。
二叉树特点：
每个结点最多有两棵子树(没有子树、一棵子树、两棵子树)
左子树和右子树是有顺序的，次序不能颠倒
即使树中某个结点只有一棵子树，也要区分它是左子树还是右子树
-------
特殊二叉树：
1. 斜树：所有节点都只有左子树(左斜树)或都只有右子树(右斜树)，这两者统称为斜树
斜树特点：每一层只有一个结点，结点的个数与二叉树的深度相同
2. 满二叉树：所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上
满二叉树特点：
叶子结点只能出现在最下面一层
非叶子结点的度一定是2
同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多
3. 完全二叉树：对于一棵具有 n 个节点的二叉树按层序编号,如果编号为 i ( 1<= i <= n)的节点**与同样深度的满二叉树中编号为 i 的节点在二叉树中位置完全相同**(感觉有点像层次遍历，由上到下，由左到右),则这棵二叉树成为完全二叉树
满二叉树一定是完全二叉树，反过来不行
完全二叉树特点：
（1) 完全二叉树的叶子节点只能出现在最下面的两层.
(2) 最下层的叶子一定集中在左部的连续位置.
(3) 倒数二层,若有叶子节点,则一定在右部的连续位置
(4) 如果结点度为1,则该结点只有有孩子,即不存在只有右子树的情况.
(5) 同样结点书的二叉树,完全二叉树的深度最小.
--------
二叉树性质：
1. 在二叉树的第 i 层上有至多 2^( i-1) 个结点 (i >= 1)
2. 深度为 k 的二叉树至多有 2^k - 1 个节点(k >= 1)
3. 对于任意一棵二叉树T,如果其终端结点数为n0,度为2的结点书为n2,那么有n0 = n2 + 1
4. 具有n个结点的完全二叉树的深度为 [log (2) n] + 1 ([x] 表示不大于x的最大整数)
5. 如果对一棵有 n 个结点的完全二叉树(其深度为[log (2) n] + 1) 的结点按层序编号(从第1层到第[log (2) n] + 1 层,每一层从左到右),对任一结点i (1 <= i <= n) 有:
(1)如果 i = 1 ,则结点i是二叉树的根,无双亲;如果i > 1,则其双亲是结点 [ i /2 ];
(2)如果2i > n,则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点2i;
(3)如果2i +1 > n,则结点i无右孩子;否则其右孩子是结点2i +1
--------
二叉树的存储结构
顺序存储结构：
二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组下标要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟关系等
对于一般的二叉树，尽管层序编号不能反映逻辑关系，但是可以将其按完全二叉树编号，只不过把不存在的点设置为'^'。
利用前序遍历、中序遍历、后序遍历、层序遍历即可建立二叉树(建立是将二叉树扩展为满二叉树，即为二叉树的扩展，虚拟结点用'#'表示)
由于在存储空间上会有浪费，一般只用于满二叉树、完全二叉树
--
链式存储结构：
二叉链表：二叉树·每个结点最多有两个孩子，所以设计一个数据域和两个指针域
ADT
lchild | data | rchild
-----------
遍历二叉树：
从根节点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次，且仅被访问一次
1. 前序遍历 中左右
先访问根节点，然后前序遍历左子树，再前序遍历右子树
2. 中序遍历 左中右
中序遍历根节点的左子树，然后访问根节点，最后中序遍历右子树
3. 后序遍历 从左到右的大前提下先叶后结点
从左到右先叶子后结点的方式遍历左右子树，最后是访问根节点
4. 层序遍历
根节点开始，从上到下，从左到右
---
推倒遍历结果
已知前序遍历和中序遍历 可以唯一确定一颗二叉树
已知后续遍历和中序遍历 可以唯一确定一颗二叉树
已知前序遍历和后序遍历，不可以唯一确定一颗二叉树
-----------
线索二叉树：
由于建立二叉树时候，扩展后的二叉树，会有很多空指针域，我们可以考虑将这些空指针域，存放指向该节点的前驱和后继的地址，这种指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就叫做线索二叉树
对二叉树某种层次遍历使其变为线索二叉树的过程称作是线索化，线索化的过程就是在遍历的过程修改空指针的过程
每个结点增设两个标志域ltag、rtag(只存放0或1的布尔值变量)，用于区分某一节点的lchild指向他的左孩子还是前驱，rchild是指向右孩子还是指向后继
----------
哈夫曼树及其应用
把哈夫曼在编码中用到的特殊的二叉树称之为哈夫曼树，他的编码方式为哈夫曼编码
从树中一个结点到另外一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称作路径长度
树的路径长度就是从根节点到每一个结点的路径长度之和
如果考虑带权的结点，结点的带权路径长度为该结点到树根之间的路径长度与结点上的权的乘积
树的带权路径长度为树中所有叶子结点的带权路径长度之和
每个叶子结点带权W(k)，每个叶子结点路径长度为lk，其中带权路径WPL最小的二叉树称为哈弗曼树，也称为最优二叉树
-----
哈夫曼树构造：
把有权的叶子结点按照从小到大的顺序排成一个有序序列
取两个最小权值作为一个新的结点，相对较小的是左孩子
哈夫曼编码，构造好哈夫曼树之后，将权值左分支改为0，右分支改为1的哈夫曼树
设计长短不等的编码，则必须是任一字符的编码都不是另外一个字符编码的前缀，这种变卡称作前缀编码
复制代码图
暂时不看了????
复制代码查找
查找表：是由同一类型的数据元素(或记录)构成的集合
关键字：是数据元素中某个数据项的值，又称为键值
次关键字：对于那些可以识别多个数据元素(或记录)的关键字
查找：就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素
查找算法分类：
1)查找表按照查找表的操作方式来分有两大种：静态查找表和动态查找表
静态查找表：只做查找操作的查找表
动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个元素
2)无序查找和有序查找。
无序查找：被查找数列有序无序均可；
有序查找：被查找数列必须为有序数列
对于静态查找表来说，可以用线性表结构来组织数据，这样可以使用顺序查找算法，**如果再对主关键字排序**，则可以利用折半查找等技术进行高效的查找
如果是动态查找表，可以考虑用二叉排序树的查找技术
------------
顺序查找表：
顺序查找适合于存储结构为顺序存储或链接存储的线性表。
顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始(开头或结尾)，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。
顺序表查找优化
for(int i=1; i<n; i++){
if(a[i] == key)
}//时间复杂度O(n)
while(a[i] != key){
i--;
}//时间复杂度O(n)，但是免去了在查找过程中每一次比较后都要判断查找位置是否越界的小技巧，在数据很大时，效率会提高很大
----------
有序表查找：
1) 折半查找：顺序存储
也称为是二分查找，属于有序查找算法。
用给定值k先与中间结点的关键字比较，中间结点把线形表(必须采用顺序存储结构)分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。
复杂度分析：最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(logn)
注：折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。
mid = (low+high)/2;
if(a[mid]==value)
return mid;
if(a[mid]>value)
high = mid-1;
if(a[mid]<value)
low = mid+1;
2)插值查找：顺序存储
插值查找是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法。
基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。
mid=low+(key-a[low])/(a[high]-a[low])*(high-low)
对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。
复杂度分析：查找成功或者失败的时间复杂度均为O(logn)。
3)斐波那契查找：顺序存储
也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。mid=low+F(k-1)-1
黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为1:0.618或1.618:1。
斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….（从第三个数开始，后边每一个数都是前两个数的和）。然后我们会发现，随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，我们就可以将黄金比例运用到查找技术中。
复杂度分析：最坏情况下，时间复杂度为O(logn)
折半查找是进行加法与除法的运算mid = (low+high)/2
插值查找用的是复杂的四则运算mid=low+(key-a[low])/(a[high]-a[low])*(high-low)
斐波那契查找只是简单地加减法运算mid=low+F(k-1)-1
在海量的数据查找过程中，这种细微的差别可能会影响最终的查找效率
4)线性索引查找：顺序存储
索引是为了加快查找速度而设计的一种数据结构。索引就是把一个关键字与它对应的记录相关联的过程，一个索引包含若干个索引项，每个索引项至少包含关键字和其对应的记录在存储器中的位置等信息，索引技术是组织大型数据库以及磁盘文件的一种重要技术
索引按照结构可以分为线性索引、树形索引、多级索引，这里只考虑线性索引，线性索引就是将索引项集合组织为线性结构，也成为索引表。
三种线性索引：稠密索引、分块索引、倒排索引
1.稠密索引
ADT
下标 关键码 指针
稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项
**对稠密索引这个索引表来说，索引项一定是按照关键码有序排列**
索引项有序也就意味着，我们要查找关键字时，可以利用折半、插值、斐波那契等有序查找算法，大大提高效率
2.分块索引
**对搜集的数据进行分块，使其分块有序，然后再对每一块建立一个索引项，从而减少索引数**
分块有序，是把数据搜集的记录分成若干块，并且这些块需要满足两个条件：
1. 快内无序，即每一快内不要求有序
2. 块间有序，要求第二块所有记录的关键字均要大于第一块中所有记录，依次类推
对于分块有序数据集，将每块对应一个索引项，这种索引方法叫做分块索引
ADT
最大关键码 存储块中记录个数 用于指向块首数据元素的指针
分块索引表查找连个步骤：
1. 在分块索引表中查找关键字所在的块，由于索引表是块间有序的，因此很容易利用折半、差值等算法得到结果
2. 根据块首地址，并在块中顺序查找关键码，因为块内无序，只能用顺序查找
3.倒排索引
搜索引擎最基础的搜索技术，倒排索引
举例搜索文章：
单词表：
英文单词 文章编号
a 2
and 1
book 1，2
ADT
次关键码：例如英文单词
记录号表：例如文章编号
其中记录号表存储具有相同次关键字的所有记录的记录号(可以是指向记录的指针或是该记录的主关键字)，这样的索引方法就叫做倒排索引
由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而叫做倒排索引
---------------------
5)二叉排序树： 链式存储
如果查找的数据集是有序线性表，并且是顺序存储的，则可以利用折半、插值、斐波那契查找，因为有序，再插入和删除的操作上，就要耗费大量的时间
***这时就需要一种既可以使得插入删除效率不错，又可以比较高效率地实现查找(动态查找表)的算法***
二叉排序树(binary sort tree)，又称二叉查找树
基本思想：二叉查找树是先对待查找的数据进行生成树，确保**树的左分支的值小于右分支的值**，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。
1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3）任意节点的左、右子树也分别为二叉查找树。
***构造一棵二叉排序树的目的***：并不是为了排序，二是为了提高查找和插入删除关键字的速度
---------------
6)平衡二叉树(AVL 树)：链式存储 对二叉排序树优化
每一个结点的左子树和右子树的高度差最多等于1
平衡二叉树是一颗高度平衡的二叉树排序树，要么是一颗空树，要么左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1
将二叉树上结点的左子树深度减去右子树深度的差值称为平衡因子BF(balance factor)，平衡因子只可能是1，0，-1
最小不平衡子树
--------------------
衡查找树之红黑树（Red-Black Tree）
红黑树和自平衡二叉(查找)树区别
1、红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。
2、平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。
AVL树是最早出现的自平衡二叉(查找)树
红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
红黑树和AVL树的区别在于它使用颜色来标识结点的高度，它所追求的是局部平衡而不是AVL树中的非常严格的平衡。
红黑树是牺牲了严格的高度平衡的优越条件为代价红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。
此外，由于它的设计，任何不平衡都会在三次旋转之内解决。
当然，还有一些更好的，但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。
红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高.
----------------
7)多路查找树(B树)
一个结点只能存储一个元素，在元素非常多的时候，就使得**树的高度非常大，或者树的深度非常大**，甚至两者都必须足够大才行，这就使得内存存取次数非常多，这显然成了时间效率上的瓶颈，开始考虑打破每一个结点只存储一个元素的限制，引入多路查找树的概念
多路查找树(muitl-way search tree)，其***每一个结点的孩子数可以多于两个，且每一个结点可以存储多个元素**，由于它是查找树，所有元素之间存在某种特定的排序关系
每一个结点存储多少个元素，以及他的孩子数的多少是非常关键的，四种特殊形式：2-3树、2-3-4树、B树、B+树
1. 2-3树
2. 2-3-4树
3. B树
4. B+树
-------------------------
红黑树与B树的区别
(B-树，即为B树。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，其实，这是个非常不好的直译，很容易让人产生误解。如人们可能会以为B-树是一种树，而B树又是一种一种树。而事实上是，B-tree就是指的B树。特此说明。)
B树又叫平衡多路查找树。B树是为了磁盘或其它存储设备而设计的一种多叉（下面你会看到，相对于二叉，B树每个内结点有多个分支，即多叉）平衡查找树。与红黑树很相似，但在降低磁盘I/0操作方面要更好一些。 许多数据库系统都一般使用B树或者B树的各种变形结构，如下文即将要介绍的B+树，B*树来存储信息。
红黑树与B树的区别在于，B树的结点可以有许多子女，从几个到几千个。那为什么又说B树与红黑树很相似呢?因为与红黑树一样，一棵含n个结点的 B树的高度也为O（lgn） ，但可能比一棵红黑树的高度小许多，应为它的分支因子比较大。所以， B树可以在O（logn）时间内，实现各种如插入（insert），删除（delete）等动态集合操作
----------------
散列表查找(哈希表)概述
复制代码排序
内排序与外排序：
根据在排序过程中待排序的记录是否全部被放置在内存中，排序分为内排序和外排序
内排序是在排序的整个过程中，待排序的所有记录全部都被放置在内存中，外排序是由于排序的记录数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行
按照算法的复杂度分为两大类，冒泡排序，简单排序和直接插入排序属于简单算法，
而希尔排序、堆排序、归并排序、快速排序属于改进算法
1)冒泡排序 交换排序
是一种交换排序，他的基本思想是：两两比较相邻记录的关键字，如果反序交换，直到没有反序记录为止
--------
1. 这种方法效率低下,不是严格意义上的冒泡算法
for(i = 1, i < l->length, i++){
for(j = i+1, j < l-> length, j++){
//交换代码
if(l->r[i] > l->r[j]){
swap(l,i,j);
}
}
}
--------
2. 冒泡算法：
for(i = 1, i < l->length, i++){
for(j = l->length - 1; j >= i; j--){
if(l->r[j] > l->r[j+1]){
swap(l,j,j+1);
}
}
}
---------
3. 冒泡算法改进：定义一个标志位flag，如果某次外圈循环没有交换数据，说明有序，标志位flag标志为true，以后的循环就没有必要继续执行了
--------
冒泡时间复杂度O(n^2)
2)简单选择排序
for(i = 1; i < l->length; i++){
min = i;
for(j = i + 1; j < l-> length; j ++){
if(l->r[min] > l->r[j])
min = j;
}
if(i! = min)
swap(l, i, min);
}
从简单选择排序过程来看，它的最大特点就是交换移动数据的次数少
冒泡时间复杂度O(n^2)
3)直接插入排序
直接插入排序的基本操作是：将一个记录插入已经排好的有序表中，从而得到一个新的、记录数加一的有序表
假设有一组无序序列 R0, R1, ... , RN-1。
(1) 我们先将这个序列中下标为 0 的元素视为元素个数为 1 的有序序列。
(2) 然后，我们要依次把 R1, R2, ... , RN-1 插入到这个有序序列中。所以，我们需要一个外部循环，从下标 1 扫描到 N-1 。
(3) 接下来描述插入过程。假设这是要将 Ri 插入到前面有序的序列中。由前面所述，我们可知，插入Ri时，前 i-1 个数肯定已经是有序了。
所以我们需要将Ri 和R0 ~ Ri-1 进行比较，确定要插入的合适位置。这就需要一个内部循环，我们一般是从后往前比较，即从下标 i-1 开始向 0 进行扫描。
public void insertSort(int[] list) {
// 打印第一个元素
System.out.format("i = %d:\t", 0);
printPart(list, 0, 0);
// 第1个数肯定是有序的，从第2个数开始遍历，依次插入有序序列
for (int i = 1; i < list.length; i++) {
int j = 0;
int temp = list[i]; // 取出第i个数，和前i-1个数比较后，插入合适位置
// 因为前i-1个数都是从小到大的有序序列，所以只要当前比较的数(list[j])比temp大，就把这个数后移一位
for (j = i - 1; j >= 0 && temp < list[j]; j--) {
list[j + 1] = list[j];
}
list[j + 1] = temp;
System.out.format("i = %d:\t", i);
printPart(list, 0, i);
}
}
时间复杂度O(n^2)
4)希尔排序 改进的直接插入排序
(1)将原本有大量记录数的记录进行分组，分割成若干个子序列，此时每个子序列待排序的记录个数就比较少了
(2)然后在这些子序列内分别进行直接插入排序，当整个序列都基本有序时，注意只是基本有序
(3)再对全体记录进行一次直接插入排序
**分割待排序记录的目的是减少待排序记录的个数，并使整个序列向基本有序发展**
希尔排序在数组中采用跳跃式分组的策略：
通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。
希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动
将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序
希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。
希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。
时间复杂度O(n^3/2)。
5)堆排序 改进的选择排序
**堆是具有以下性质的(@1)完全二叉树：(@2)每个结点的值都大于或等于左右孩子结点的值，称为大顶堆,(@3)每个结点的值都小于或等于左右孩子结点的值，称为小顶堆**
根节点一定是堆中
堆排序就是利用堆(假设大顶堆)进行排序的方法，此时，整个序列的最大值就是堆顶的根节点。
将它移走(其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值)，然后将剩余的n-1个序列重新构造成成一个堆，这样就会得到n个元素的次小值，如此反复执行，便可以得到一个有序序列
时间复杂度：O(nlogn)
6)归并排序
"归并"一词在数据结构中的定义是将两个或两个以上的有序表组合成一个新的有序表
归并排序：就是利用归并的思想实现的排序方法，它的原理是假设初始序列有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]个长度为2或者1的有序子序列，两两归并，
如此重复，知道得到一个长度为n的有序序列为止，这种排序方式称为2路归并排序。
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)
归并排序的最好，最坏，平均时间复杂度均为O(nlogn)
7)快速排序 改进的冒泡排序
快速排序的基本思想是：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序的目的
快速排序优化：
1.优化选取枢轴
三数选中法：即取三个关键字先进行排序，将中间数作为枢轴，一般是选取左端、右端、和中间三个数，也可以随机选取
2.优化不必要的交换
3.优化小数组时的排序方案
4.优化递归操作
复制代码判断单链表是否有环