一.对代码的热爱
 
简洁之美，用简单的东西解决复杂的问题
 
电影是一门艺术，编程也是
 
一丝不苟，态度等价值观
 
二.逻辑也叫算法
 
采用三段论逻辑，比如
 
所有的函数都是由Function构造的
Function,Array，Object都是函数
推论出Function、Array、Object都是由Function构造的
 
3种结构化编程 三种语句解决逻辑
 
 
顺序执行语句
 
语句1
 
语句2
 
 
判断执行语句
 
if …then …else
 
if…else if …else
 
 
循环执行语句
 
while…do…
 
for i from 1 to n …
 
 
伪代码：
 
when i<10
 
​ 语句1
 
​ i+=1
 
语句2
 
 
流程图和伪代码
 
方型代表顺序执行，圆角矩形代表开始结束
 
菱形代表条件判断，循环必定成圈
 
用流程图求两个数最大
 
用MindManager
 
 
用流程图求n个数最大—伪代码
 
 
总结
 
逻辑很重要
用三种语句表达逻辑
用图和伪代码可以表示三种语句
 
三.数据结构=数据逻辑形式+操作
 
如何表示2个数据
 
顺序有意义，如坐标 如first和last操作
 
顺序无意义，如血压 无需first和last操作
 
如何表示N个数据 线性
 
顺序有意义：数组 要提供索引等操作
 
顺序无意义：集合
 
如何表示N对N个数据 哈希表
 
key ->value
 
hash={1001=>‘小方’，1002=>‘小红’}
 
哈希表和js对象区别：js有下标 有隐藏属性
 
如学号对姓名
 
【经典题】
 
如何计算一段英语中多少个字母，大小写的，符号出现的次数：
 
用哈希表做
 

基于严蔚敏及吴伟民编著的清华大学C语言版教材并结合网上相关资料整理(http://www.docin.com/p-2027739005.html)
 
第一章：绪论
 
1.数据结构：是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作等的学科。
 
2.数据结构涵盖的内容：
 
 
3.基本概念和术语:
 
数据：对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
 
数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
 
数据对象：性质相同的数据元素的集合，是数据的一个子集。
 
数据结构：相互之间存在一种或多种特定关系的数据元素的集合。
 
数据类型：一个值的集合和定义在这个值集上的一组操作的总称。
 
4.算法和算法分析
 
1）算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。
 
算法五个特性：有穷性，确定性，可行性，输入，输出。
 
2）算法设计要求：正确性，可读性，健壮性，效率与低存储量需求。
 
3）算法分析：时间复杂度，空间复杂度，稳定性
 
 
 
第二章：线性表
 
1.线性结构特点：在数据元素的非空有限集合中，(1)存在唯一的一个被称做“第一个”的数据元素；(2)存在唯一的一个被称做“最后一个”的数据元素；(3)除第一个之外，集合中的每个数据元素均只有一个前驱；(4)除最后一个之外，集合中每个数据元素均只有一个后继。
 
2.线性表定义：有限个性质相同的数据元素组成的序列。
 
 
3.线性表的存储结构：顺序存储结构和链式存储结构
 
顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
 
通常用数组来描述数据结构中的顺序存储结构。
 
链式存储结构: 其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。通过指针来实现。
 
数据结构的基本运算：修改、插入、删除、查找、排序
 
4.线性表的顺序表示和实现
 
1）修改：通过数组的下标便可访问某个特定元素并修改。
 
时间复杂度O(1)
 
2） 插入:在线性表的第i个位置前插入一个元素
 
实现步骤：
 
   ①将第n至第i 位的元素逐一向后移动一个位置；
 
   ②将要插入的元素写到第i个位置；
 
   ③表长加1。
 
   注意：事先应判断: 插入位置i 是否合法?表是否已满?
 
   应当符合条件： 1≤i≤n+1  或  i=[1, n+1]
 
   核心语句：
 
for (j=n; j>=i; j--)
 
a[j+1]=a[ j ]; 
 
a[ i ]=x;   
 
n++;
 
  插入时的平均移动次数为：n(n+1)/2÷（n+1）＝n/2≈O(n)
 
3）删除：删除线性表的第i个位置上的元素
 
  实现步骤：
 
  ①将第i+1 至第n 位的元素向前移动一个位置；
 
  ②表长减1。
 
  注意：事先需要判断，删除位置i 是否合法?
 
  应当符合条件：1≤i≤n  或  i=[1, n]
 
  核心语句：
 
{
 
    for ( j=i+1; j<=n; j++ )
 
    a[j-1]=a[j]; 
 
    n--;
 
}
 
  顺序表删除一元素的时间效率为:T(n)=(n-1)/2 ≈O(n)
 
  顺序表插入、删除算法的平均空间复杂度为O(1)
 
5.线性表的链式表示和实现
 
线性链表：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。
 
一个数据元素称为一个结点，包括两个域：存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链。
 
由于链表的每个结点中只包含一个指针域，故线性链表又称为单链表。
 
1）单链表的修改(或读取）
 
思路：要修改第i个数据元素，必须从头指针起一直找到该结点的指针p，return p;  
 
然后才能：p->data=new_value
 
读取第i个数据元素的核心语句是：
 
Linklist *find(Linklist *head ,int i)
 
{ 
 
   int j=1;
 
   Linklist *p;
 
   P=head->next;
 
   While((p!=NULL)&&(j<i))
 
   {
 
       p=p->next;
 
       j++;
 
    }
 
}
 
2）单链表的插入
 
 
 
链表插入的核心语句：
 
Step 1：s->next=p->next;
 
Step 2：p->next=s；
 
3）单链表的删除
 
 
删除动作的核心语句（要借助辅助指针变量q）：
 
q = p->next;           //首先保存b的指针，靠它才能找到c；
 
p->next=q->next;  //将a、c两结点相连，淘汰b结点；
 
free(q) ；               //彻底释放b结点空间
 
4）双向链表的插入操作
 
 
设p已指向第i 元素，请在第 i 元素前插入元素 x：
 
① ai-1的后继从 ai ( 指针是p)变为 x（指针是s) :
 
                s->next = p  ;   p->prior->next = s ;
 
② ai  的前驱从ai-1 ( 指针是p->prior)变为 x ( 指针是s);
 
                s->prior = p ->prior ; p->prior = s ;
 
5）双向链表的删除操作
 
 
设p指向第i 个元素，删除第 i 个 元素
 
后继方向：ai-1的后继由ai ( 指针p)变为ai+1(指针 p ->next );
 
                   p ->prior->next =  p->next  ;
 
前驱方向：ai+1的前驱由ai ( 指针p)变为ai-1 (指针 p -> prior );
 
                 p->next->prior = p ->prior ;
 
6.循环链表
 
循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
 
循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是p或p->next是否为空，而是它们是否等于头指针。
 
学习重点：
 
 
线性表的逻辑结构，指线性表的数据元素间存在着线性关系。在顺序存储结构中，元素存储的先后位置反映出这种线性关系，而在链式存储结构中，是靠指针来反映这种关系的。
 
 
顺序存储结构用一维数组表示，给定下标，可以存取相应元素，属于随机存取的存储结构。
 
 
链表操作中应注意不要使链意外“断开”。因此，若在某结点前插入一个元素，或删除某元素，必须知道该元素的前驱结点的指针。
 
 
掌握通过画出结点图来进行链表（单链表、循环链表等）的生成、插入、删除、遍历等操作。
 
 
数组（主要是二维）在以行序/列序为主的存储中的地址计算方法。
 
补充重点：
 
 
每个存储结点都包含两部分：数据域和指针域(链域)
 
 
在单链表中，除了首元结点外，任一结点的存储位置由 其直接前驱结点的链域的值 指示。
 
 
在链表中设置头结点有什么好处？
 
    头结点即在链表的首元结点之前附设的一个结点，该结点的数据域可以为空，也可存放表长度等附加信息，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。
 
 
如何表示空表？
 
（1）无头结点时，当头指针的值为空时表示空表；
 
（2）有头结点时，当头结点的指针域为空时表示空表。
 
 
链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？
 
 因每个结点至少有两个分量，且数据类型通常不一致，所以要采用结构数据类型。
 
 
sizeof(x)——  计算变量x的长度（字节数）；
 
          malloc(m) —  开辟m字节长度的地址空间，并返回这段空间的首地址；
 
          free(p)   —— 释放指针p所指变量的存储空间，即彻底删除一个变量。
 
 
链表的运算效率分析：
 
（1）查找 
 
因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。
 
（2） 插入和删除 
 
因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为 O(1)。
 
但是，如果要在单链表中进行前插或删除操作，因为要从头查找前驱结点，所耗时间复杂度将是 O(n)。
 
例：在n个结点的单链表中要删除已知结点*P，需找到它的前驱结点的地址，其时间复杂度为 O（n）
 
 
顺序存储和链式存储的区别和优缺点？
 
    顺序存储时，逻辑上相邻的数据元素，其物理存放地址也相邻。顺序存储的优点是存储密度大，存储空间利用率高；缺点是插入或删除元素时不方便。
 
　　链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小，存储空间利用率低。
 
 
顺序表适宜于做查找这样的静态操作；
 
 
链表宜于做插入、删除这样的动态操作。
 
 
若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；
 
 
若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。
 
① 数组中各元素具有统一的类型；
 
② 数组元素的下标一般具有固定的上界和下界，即数组一旦被定义，它的维数和维界就不再改变。
 
③数组的基本操作比较简单，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。
 
 
三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 行下标  、列下标 和 元素值 。
 
第三章：栈和队列
 
1.栈:限定仅在表尾进行插入或删除操作的线性表。
 
栈的基本操作：在栈顶进行插入或删除，栈的初始化、判空及取栈顶元素等。
 
入栈口诀：堆栈指针top “先压后加”
 
出栈口诀：堆栈指针top “先减后弹”
 
top=0表示空栈。
 
 
 
2.栈的表示和实现
 
     1)构造一个空栈S
 
    Status InitStack(SqStack &S)
 
    {
 
        S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof(SElemType));
 
        if(!S.base) exit (OVERFLOW); //存储分配失败
 
            S.top = S.base;
 
            S.stacksize = STACK_INIT_SIZE;
 
            return OK;
 
    }
 
 
 
    2)返回栈顶元素
 
       Status GetTop(SqStack S, SElemType e) 
 
        {//若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR
 
            if(S.top == S.base) return ERROR;
 
            e = *(S.top-1);
 
            return OK; 
 
        }//GetTop
 
 
 
    3)顺序栈入栈函数PUSH（）
 
Status Push(SqStack &S, SElemType e)
 
{ //插入元素e为新的栈顶元素
 
    if(S.top-S.base>=S.stacksize)//栈满，追加存储空间
 
   {
 
    s.base = (SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
 
    if(!S.base) exit(OVERFLOW);//存储分配失败
 
    S.top = S.base + S.stacksize;
 
    S.stacksize += STACKINCREMENT;
 
    }
 
    *S.top++ =e;
 
    return OK:
 
}//PUSH
 
4)顺序栈出栈函数POP()
 
status Pop( SqStack &S,SElemType &e)
 
{ //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK,否则返回ERROR
 
    if(S.top == S.base) return ERROR; 
 
    e=* —S.top;
 
    return OK;
 
        }
 
3.栈的应用
 
数制转换，括号匹配的检验，行编辑程序，迷宫求解，表达式求值，递归实现。
 
4.队列：是一种先进先出的线性表，它只允许在表的一端进行插入，而在另一端删除元素。
 
允许插入的一端叫做队尾，允许删除的一端叫做队头。
 
除了栈和队列外，还有一种限定性数据结构是双端队列。双端队列是限定插入和删除操作在表的两端进行的线性表。
 
5.链队列结点类型定义：
 
 typedef Struct QNode{
 
     QElemType        data;     //元素
 
     Struct   QNode   *next;  //指向下一结点的指针
 
   }Qnode , * QueuePtr ;
 
链队列类型定义：
 
 typedef  struct {
 
  QueuePtr     front ; //队首指针
 
  QueuePtr     rear ; //队尾指针
 
  }  LinkQueue;
 
链队示意图：
 
 
①  空链队的特征：front=rear
 
②  链队会满吗？一般不会，因为删除时有free动作。除非内存不足！
 
③  入队（尾部插入）：rear->next=S; rear=S;
 
    出队（头部删除）：front->next=p->next;
 
6.顺序队
 
顺序队类型定义：
 
#define    QUEUE-MAXSIZE  100  //最大队列长度
 
     typedef    struct {
 
            QElemType     *base;    //队列的基址
 
             int                    front;     //队首指针
 
             int                     rear;    //队尾指针
 
       }SqQueue
 
建队核心语句：
 
q.base=(QElemType *)malloc(sizeof (QElemType)* QUEUE_MAXSIZE);       //分配空间
 
顺序队示意图：
 
 
7.循环队列：
 
队空条件 :  front = rear       (初始化时：front = rear )
 
队满条件： front = (rear+1) % N         (N=maxsize)
 
队列长度（即数据元素个数）：L=（N＋rear－front）% N
 
1)初始化一个空队列
 
Status   InitQueue ( SqQueue  &q ) //初始化空循环队列 q
 
{   
 
q.base=(QElemType *)malloc(sizeof(QElemType）* QUEUE_MAXSIZE);   //分配空间
 
if (!q.base)  exit(OVERFLOW);//内存分配失败，退出程序
 
   q.front =q.rear=0; //置空队列
 
    return OK;
 
 } //InitQueue;
 
 
 
2)入队操作
 
Status   EnQueue(SqQueue  &q,  QElemType e)
 
{//向循环队列 q 的队尾加入一个元素 e
 
   if ( (q.rear+1) %  QUEUE_MAXSIZE ==  q.front)
 
                    return  ERROR ; //队满则上溢，无法再入队
 
        q.rear = ( q.rear + 1 ) %  QUEUE_MAXSIZE;
 
        q.base [q.rear] = e;    //新元素e入队
 
        return  OK;
 
 }// EnQueue;
 
 
 
3)出队操作
 
Status     DeQueue ( SqQueue  &q,    QElemType &e)
 
 {//若队列不空，删除循环队列q的队头元素，
 
        //由 e 返回其值，并返回OK
 
      if ( q.front = = q.rear )   return ERROR;//队列空
 
      q.front=(q.front+1) % QUEUE_MAXSIZE; 
 
      e = q.base [ q.front ] ;
 
     return OK;
 
    }// DeQueue
 
 
链队列空的条件是首尾指针相等，而循环队列满的条件的判定，则有队尾加1等于队头和设标记两种方法。
 
补充重点：
 
 
为什么要设计堆栈？它有什么独特用途？
 
 
什么叫“假溢出” ？如何解决？
 
① 调用函数或子程序非它莫属；
 
② 递归运算的有力工具；
 
③ 用于保护现场和恢复现场；
 
④ 简化了程序设计的问题。                         
 
2.为什么要设计队列？它有什么独特用途？
 
① 离散事件的模拟（模拟事件发生的先后顺序,例如 CPU芯片中的指令译码队列）；
 
② 操作系统中的作业调度（一个CPU执行多个作业）；
 
③ 简化程序设计。
 
答：在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。解决假溢出的途径———采用循环队列。
 
4.在一个循环队列中，若约定队首指针指向队首元素的前一个位置。那么，从循环队列中删除一个元素时，其操作是先 移动队首位置 ，后 取出元素。
 
5.线性表、栈、队的异同点：
 
相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。
 
不同点：① 运算规则不同：
 
线性表为随机存取；
 
而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO；
 
队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。
 
② 用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、OS作业调度和简化设计等。
 
 
 
第四章：串
 
1.串是数据元素为字符的线性表，串的定义及操作。
 
串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。
 
串比较：int strcmp(char *s1,char *s2);            
 
求串长：int strlen(char *s);                          
 
串连接：char  strcat(char *to,char *from)   
 
子串T定位：char strchr(char *s,char *c);
 
2.串的存储结构，因串是数据元素为字符的线性表，所以存在“结点大小”的问题。
 
模式匹配算法 。
 
串有三种机内表示方法：
 
 
 
3.模式匹配算法 ：
 
算法目的：确定主串中所含子串第一次出现的位置（定位）
 
定位问题称为串的模式匹配，典型函数为Index(S,T,pos)
 
BF算法的实现—即编写Index(S, T, pos)函数
 
BF算法设计思想：
 
将主串S的第pos个字符和模式T的第1个字符比较，
 
若相等，继续逐个比较后续字符；
 
若不等，从主串S的下一字符（pos+1）起，重新与T第一个字符比较。 
 
直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。
 
否则，匹配失败，返回值 0。
 
Int Index_BP(SString S, SString T, int pos)
 
{ //返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0.
 
 // 其中，T非空，1≤pos≤StrLength(S)
 
    i=pos;      j=1;
 
   while ( i<=S[0] && j<=T[0] ) //如果i,j二指针在正常长度范围，
 
     {  
 
       if (S[i] = = T[j] ) {++i, ++j; }   //则继续比较后续字符
 
       else {i=i-j+2; j=1;} //若不相等，指针后退重新开始匹配
 
      }
 
  if(j>T[0]) return i-T[0];  //T子串指针j正常到尾，说明匹配成功，  else return 0;        //否则属于i>S[0]情况，i先到尾就不正常
 
} //Index_BP
 
补充重点：
 
1.空串和空白串有无区别？
 
答：有区别。
 
空串(Null String)是指长度为零的串；
 
而空白串(Blank  String),是指包含一个或多个空白字符‘  ’(空格键)的字符串.
 
2.“空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串称为S的真子串。”
 
 
 
 
第五章：数组和广义表
 
重点：二维数组的位置计算。
 
矩阵的压缩存储：特殊矩阵(三角矩阵，对称矩阵)，稀疏矩阵，
 
 
 
第六章：树和二叉树
 
1.树：是n(n≥0)个结点的有限集。(1)有且仅有一个特定的称为根（root）的结点;（2）当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是棵树，被称作这个根的子树 。
 
2.二叉树：是n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。
 
二叉树的性质，存储结构。
 
性质1: 在二叉树的第i层上至多有2^(i-1)个结点（i>0）。
 
性质2: 深度为k的二叉树至多有2^k-1个结点（k>0）。
 
性质3: 对于任何一棵二叉树，如果其终端结点数为n0,度为2的结点数有n2个，则叶子数n0=n2＋1
 
性质4: 具有n个结点的完全二叉树的深度必为 [log2n]+1
 
性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）。
 
二叉树的存储结构：
 
1).顺序存储结构
 
按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。
 
若是完全/满二叉树则可以做到唯一复原。
 
不是完全二叉树：一律转为完全二叉树！
 
方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。
 
缺点：①浪费空间；②插入、删除不便 
 
2).链式存储结构
 
用二叉链表即可方便表示。一般从根结点开始存储。
 
 
lchild
 
 
data
 
 
rchild
 
优点：①不浪费空间；②插入、删除方便
 
3.二叉树的遍历。
 
指按照某种次序访问二叉树的所有结点，并且每个结点仅访问一次，得到一个线性序列。
 
遍历规则:二叉树由根、左子树、右子树构成，定义为D、 L、R
 
若限定先左后右，则有三种实现方案：
 
  DLR               LDR                   LRD
 
先序遍历           中序遍历          后序遍历
 
4.线索二叉树
 
1）线索二叉树可以加快查找前驱与后继结点，实质就是将二叉链表中的空指针改为指向前驱或后继的线索，线索化就是在遍历中修改空指针。
 
通常规定：对某一结点，若无左子树，将lchild指向前驱结点；若无右子树，将rchild指向后继结点。
 
还需要设置左右两个tag，用来标记当前结点是否有子树。
 
若ltag==1,lchild指向结点前驱；若rtag==1，rchild指向结点后继。
 
2）线索二叉树的存储结构如下：
 
typedef struct ThreadNode{
 
ElemType data;
 
struct ThreadNode *lchild, *rchild;
 
int ltag, rtag;
 
}ThreadNode, *ThreadTree;
 
 
5.树和森林
 
1）树有三种常用存储方式：
 
①双亲表示法     ②孩子表示法    ③孩子—兄弟表示法
 
2）森林、树、二叉树的转换
 
(1)将树转换为二叉树
 
树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树：a.在所有兄弟结点之间加一连线
 
b.对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。
 
 
(2)将一个森林转换为二叉树：
 
具体方法是：a.将森林中的每棵树变为二叉树；
 
b.因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。
 
 
(3)二叉树转换为树
 
是树转换为二叉树的逆过程。
 
a.加线。若某结点X的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点，都作为结点X的孩子。将结点X与这些右孩子结点用线连接起来。
 
b.去线。删除原二叉树中所有结点与其右孩子结点的连线。
 
 
 
 
(4)二叉树转换为森林：
 
假如一棵二叉树的根节点有右孩子，则这棵二叉树能够转换为森林，否则将转换为一棵树。
 
a.从根节点开始，若右孩子存在，则把与右孩子结点的连线删除。再查看分离后的二叉树，若其根节点的右孩子存在，则连线删除。直到所有这些根节点与右孩子的连线都删除为止。
 
b.将每棵分离后的二叉树转换为树。
 
 
6.树和森林的遍历
 
 
树的遍历
 
① 先根遍历：访问根结点；依次先根遍历根结点的每棵子树。
 
② 后根遍历：依次后根遍历根结点的每棵子树；访问根结点。
 
 
 
 
森林的遍历
 
① 先序遍历
 
若森林为空，返回；
 
访问森林中第一棵树的根结点；
 
先根遍历第一棵树的根结点的子树森林；
 
先根遍历除去第一棵树之后剩余的树构成的森林。
 
② 中序遍历
 
若森林为空，返回；
 
中根遍历森林中第一棵树的根结点的子树森林；
 
访问第一棵树的根结点；
 
中根遍历除去第一棵树之后剩余的树构成的森林。
 
 
 
7.哈夫曼树及其应用
 
Huffman树：最优二叉树（带权路径长度最短的树）
 
Huffman编码：不等长编码。
 
树的带权路径长度：(树中所有叶子结点的带权路径长度之和)
 
构造Huffman树的基本思想：权值大的结点用短路径，权值小的结点用长路径。
 
构造Huffman树的步骤（即Huffman算法）：
 
(1) 由给定的 n 个权值{ w1, w2, …, wn }构成n棵二叉树的集合F = { T1, T2, …, Tn } （即森林） ，其中每棵二叉树 Ti 中只有一个带权为 wi 的根结点，其左右子树均空。
 
(2) 在F 中选取两棵根结点权值最小的树 做为左右子树构造一棵新的二叉树，且让新二叉树根结点的权值等于其左右子树的根结点权值之和。
 
(3) 在F 中删去这两棵树，同时将新得到的二叉树加入 F中。
 
(4) 重复(2) 和(3) , 直到 F 只含一棵树为止。这棵树便是Huffman树。
 
具体操作步骤：
 
 
 
应用：用于通信编码
 
　　在通信及数据传输中多采用二进制编码。为了使电文尽可能的缩短，可以对电文中每个字符出现的次数进行统计。设法让出现次数多的字符的二进制码短些，而让那些很少出现的字符的二进制码长一些。假设有一段电文，其中用到 4 个不同字符Ａ，Ｃ，Ｓ，Ｔ，它们在电文中出现的次数分别为 7 ， 2 ， 4 ， 5 。把 7 ， 2 ， 4 ， 5 当做 4 个叶子的权值构造哈夫曼树如图(a) 所示。在树中令所有左分支取编码为 0 ，令所有右分支取编码为1。将从根结点起到某个叶子结点路径上的各左、右分支的编码顺序排列，就得这个叶子结点所代表的字符的二进制编码，如图(b) 所示。这些编码拼成的电文不会混淆，因为每个字符的编码均不是其他编码的前缀，这种编码称做前缀编码。
 
 
 
第七章 图
 
1.图的定义，概念、术语及基本操作(https://blog.csdn.net/eyishion/article/details/53234255)
 
1）图的定义
 
图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成;
 
通常表示为:G(V,E),G表示一个图，V是图G中顶点的集合，E是图G中边的集合；
 
注意：在图中数据元素称之为顶点(Vertex),而且顶点集合有穷非空；在图中任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示。
 
2）图的分类
 
 
按照有无方向，分为无向图和有向图；
 
无向图：如果图中任意两个顶点之间的边都是无向边，则称该图为无向图。
 
无向边：若顶点M到顶点N的边没有方向，称这条边为无向边，用无序偶对(M,N)或(N,M)表示。
 
无向图是有边和顶点构成。如下图所示就是一个无向图G1：
 
 
无向图G1= (V1,{E1}),其中顶点集合 V1={A,B,C,D};边集合E1={(A,B),(B,C),(C,D),(D,A)}
 
有向图：如果图中任意两个顶点之间的边都是有向边，则称该图为有向图。
 
有向边：若顶点M到顶点N的边有方向，称这条边为有向边，也称为弧，用偶序对 < M, N >表示；M表示弧尾，N表示弧头
 
有向图是有弧和顶点构成，如下图所示是一个有向图G2：
 
 
有向图G2=(V2，{E2}),其中顶点集合 V2={A,B,C,D};弧集合E2={< A,D>,< B,A>,< C,A>,< B,C>}
 
对于弧< A,D>来说， A是弧尾，D是弧头
 
注意：无向边用 小括号 “()”表示，有向边用“<>”表示。
 
无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。
 
含有n个顶点的无向完全图有n * (n-1)/2条边。下面是一个无向完全图
 
 
4个顶点，6条无向边，每个顶点对应3条边 ，一共4个顶点 总共 4*3，每个顶点对应的边都重复计算了一次，所以整体要除以2。
 
对于n各 顶点和e条边的无向图满足：0<=e <= n(n-1)/2
 
有向完全图：在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。
 
含有n个顶点的无向完全图有n * (n-1)条边。下面是一个有向完全图
 
 
4个顶点，12条弧，一共4个顶点 总共 4*3。
 
2，按照弧或边的多少，分为稀疏图和稠密图；
 
若边或弧的个数e<=NlogN(N是顶点的个数)，称为系数图，否则称为稠密图；
 
3，按照边或弧是否带权，其中带权的图统称为网
 
有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权。
 
有向网中弧带权的图叫做有向网；
 
无向网中边带权的图叫做无向网；
 
比如下图就是一个无向图
 
 
 
 
图的顶点和边间关系
 
邻接点 度 入度 出度
 
对于无向图，假若顶点v和顶点w之间存在一条边，则称顶点v和顶点w互为邻接点，边(v,w)和顶点v和w相关联。
 
顶点v的度是和v相关联的边的数目，记为TD(v);
 
 
上面这个无向图G1，A和B互为邻接点，A和D互为邻接点，B和C互为邻接点，C和D互为邻接点;
 
A的度是2,B的度是2,C的度是2,D的度是2;所有顶点度的和为8，而边的数目是4；
 
图中边的数目e = 各个顶点度数和的一半。
 
对于有向图来说，与某个顶点相关联的弧的数目称为度(TD)；以某个顶点v为弧尾的弧的数目定义为顶点v的出度(OD)；以顶点v为弧头的弧的数目定义为顶点的入度(ID)
 
度(TD) = 出度(OD) + 入度(ID);
 
 
比如上面有向图，
 
A的度为3 ，A的入度 2，A的出度是1
 
B的度为2 ，B的入度 0，B的出度是2
 
C的度为2 ，C的入度 1，C的出度是1
 
D的度为1 ，D的入度 1，D的出度是0
 
所有顶点的入度和是4，出度和也是4，而这个图有4个弧
 
所以 有向图的弧 e = 所有顶点入度的和 = 所有顶点出度的和
 
路径 路径长度 简单路径 回路 (环) 简单回路(简单环)
 
设图G=(V，{E})中的一个顶点序列{u=Fi0,Fi1,Fi2,….Fim=w}中，(Fi,j-1,Fi,j)∈E 1 ≤j ≤m,则称从顶点u到顶点w之间存在一条路径，路径上边或弧的数目称作路径长度，
 
若路径中的顶点不重复出现的路径称为简单路径
 
若路径中第一个顶点到最后一个顶点相同的路径称为回路或环
 
若路径中第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环
 
比如下图 ：
 
 
从B 到 D 中顶点没有重复出现 ，所以是简单路径 ，边的数目是2，所以路径长度为 2。
 
 
图1和图2都是一个回路(环),图1中出了第一个顶点和最后一个顶点相同之外，其余顶点不相同，所以是简单环(简单回路)，图2，有与顶点C重复就不是一个简单环了；
 
连通图相关术语
 
连通图
 
在无向图G(V,{E})中，如果从顶点V到顶点W有路径，则称V和W是连通的。如果对于图中任意两个顶点Vi、Vj∈V,Vi和Vj都是连通的，则称G是连通图。
 
如下图所示：
 
 
图1，顶点A到顶点E就无法连通，所以图1不是连通；图2，图3，图4属于连通图；
 
连通分量
 
若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量；
 
图1是无向非连通图，由两个连通分量，分别是图2和图3。图4尽管也是图1的子图，但是它不满足极大连通，也就说极大连通应当是包含ABCD四个顶点，比如图2那样；
 
强连通图
 
在有向图G(V,{E})中，如果对于每一对Vi ,Vj∈V,Vi≠Vj,从Vi到Vj和从Vj到Vi都存在有向路径,则称G是强连通图。
 
 
图1不是强连通图因为D到A不存在路径，图2属于强连通图。
 
强连通分量
 
若有向图不是强连通图，则图中各个极大强连通子图称作此图的强连通分量；
 
 
图1不是强连通图，但是图2是图1的强连通子图，也就是强连通分量；
 
生成树和生成森林
 
生成树
 
假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树；
 
 
图1是一个连通图含有4个顶点和4条边，图2，图3，图4含有3条边和4个顶点，构成了一个极小连通图子图，也称为生成树，为什么是极小连通子图，因为图2，图3，图4中少一条边都构不成一个连通图，多一条边就变成一个回路(环)，所以是3条边和4个顶点构成的极小连通子图。图5尽管也是3个边4个顶点，但不是连通图。
 
生成森林
 
如果一个有向图恰有一个顶点的入度为0，其余顶点的入度为1，则是一颗有向树；
 
入度为0，相当于根节点，入度为1，相当于分支节点；，比如下面的有向图就是一个有向树
 
 
顶点B的入度是0，其余顶点的入度是1；
 
一个有向图的生成森林由若干颗有向树组成，含有图中全部顶点，但有足以构成若干颗不相交的有向树的弧；
 
 
有向图1去掉一些弧后分解成2颗有向树，图2和图3，这两颗树就是有向图图1的生成森林；
 
2.图的存储结构
 
1).邻接矩阵(数组)表示法
 
① 建立一个顶点表和一个邻接矩阵
 
② 设图 A = (V, E) 有 n 个顶点，则图的邻接矩阵是一个二维数组 A.Edge[n][n]。
 
注：在有向图的邻接矩阵中，
 
   第i行含义：以结点vi为尾的弧(即出度边）；
 
   第i列含义：以结点vi为头的弧(即入度边）。
 
邻接矩阵法优点：容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。
 
邻接矩阵法缺点：n个顶点需要n*n个单元存储边(弧);空间效率为O(n^2)。
 
 
2).邻接表(链式)表示法
 
① 对每个顶点vi 建立一个单链表，把与vi有关联的边的信息（即度或出度边）链接起来，表中每个结点都设为3个域:
 
 
② 每个单链表还应当附设一个头结点（设为2个域），存vi信息；
 
③ 每个单链表的头结点另外用顺序存储结构存储。
 
邻接表的优点：空间效率高；容易寻找顶点的邻接点；
 
邻接表的缺点：判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。
 
3.图的遍历
 
遍历定义：从已给的连通图中某一顶点出发，沿着一些边，访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。
 
图的遍历算法求解图的连通性问题、拓扑排序和求关键路径等算法的基础。
 
图常用的遍历：一、深度优先搜索；二、广度优先搜索 
 
深度优先搜索（遍历）步骤：(如下图)
 
① 访问起始点 v;
 
② 若v的第1个邻接点没访问过，深度遍历此邻接点；
 
③ 若当前邻接点已访问过，再找v的第2个邻接点重新遍历。
 
基本思想：——仿树的先序遍历过程。
 
遍历结果：v1->v2->v4->v8->v5-v3->v6->v7
 
广度优先搜索（遍历）步骤：
 
① 在访问了起始点v之后，依次访问 v的邻接点；
 
② 然后再依次（顺序）访问这些点（下一层）中未被访问过的邻接点；
 
③ 直到所有顶点都被访问过为止。
 
 
遍历结果：v1->v2->v3->v4->v5-v6->v7->v8
 
4.图的连通性问题
 
1）对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优先搜索或广度优先搜索，便可访问到图中所有顶点。
 
2）最小生成树:在连通网的所有生成树中，所有边的代价和最小的生成树。
 
构造最小生成树有很多算法，但是他们都是利用了最小生成树的同一种性质：MST性质（假设N=(V,{E})是一个连通网，U是顶点集V的一个非空子集，如果（u，v）是一条具有最小权值的边，其中u属于U，v属于V-U，则必定存在一颗包含边（u，v）的最小生成树），下面就介绍两种使用MST性质生成最小生成树的算法：普里姆算法和克鲁斯卡尔算法。
 
Kruskal算法特点：将边归并，适于求稀疏网的最小生成树。
 
Prime算法特点: 将顶点归并，与边数无关，适于稠密网。
 
Prime算法构造最小生成树过程如下图：
 
 
Kruskal算法构造最小生成树过程如下图：
 
 
5.有向无环图及其应用
 
有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。
 
1）拓扑排序
 
拓扑排序对应施工的流程图具有特别重要的作用，它可以决定哪些子工程必须要先执行，哪些子工程要在某些工程执行后才可以执行。
 
我们把顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。
 
一个AOV网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行（对于数据流来说就是死循环）。在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列(Topological order)，由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。
 
拓扑排序的实现：
 
a.在有向图中选一个没有前驱的顶点并且输出
 
b.从图中删除该顶点和所有以它为尾的弧（白话就是：删除所有和它有关的边）
 
c.重复上述两步，直至所有顶点输出，或者当前图中不存在无前驱的顶点为止，后者代表我们的有向图是有环的，因此，也可以通过拓扑排序来判断一个图是否有环。
 
 
2）关键路径
 
AOE-网是一个带权的有向无环图，其中，顶点表示事件，弧表示活动，权表示活动持续的时间。通常，AOE-网可用来估算工程的完成时间。
 
关键路径：在AOE网中，从始点到终点具有最大路径长度（该路径上的各个活动所持续的时间之和）的路径称为关键路径。
 
关键活动：关键路径上的活动称为关键活动。关键活动：e[i]=l[i]的活动
 
由于AOE网中的某些活动能够同时进行，故完成整个工程所必须花费的时间应该为始点到终点的最大路径长度。关键路径长度是整个工程所需的最短工期。
 
与关键活动有关的量：
 
(1)事件的最早发生时间ve[k]：ve[k]是指从始点开始到顶点vk的最大路径长度。这个长度决定了所有从顶点vk发出的活动能够开工的最早时间。 
 
(2)事件的最迟发生时间vl[k]：vl[k]是指在不推迟整个工期的前提下,事件vk允许的最晚发生时间。
 
(3)活动的最早开始时间e[i]:若活动ai是由弧<vk , vj>表示，则活动ai的最早开始时间应等于事件vk的最早发生时间。因此，有：e[i]=ve[k]
 
(4)活动的最晚开始时间l[i]:活动ai的最晚开始时间是指，在不推迟整个工期的前提下， ai必须开始的最晚时间。若ai由弧<vk，vj>表示，则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。因此，有：l[i]=vl[j]-len<vk,vj> 
 
示例如下：
 
 
 
6.最短路径
 
从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径叫做最短路径。
 
1）迪杰斯塔拉算法--单源最短路径
 
 
 
 
 
所有顶点间的最短路径—用Floyd（弗洛伊德）算法
 
第八章：查找
 
查找表是称为集合的数据结构。是元素间约束力最差的数据结构：元素间的关系是元素仅共在同一个集合中。（同一类型的数据元素构成的集合）
 
1.静态查找表
 
  1）顺序查找（线性查找）
 
  技巧：把待查关键字key存入表头或表尾（俗称“哨兵”），这样可以加快执行速度。
 
int Search_Seq( SSTable  ST , KeyType  key ){
 
ST.elem[0].key =key;
 
for( i=ST.length; ST.elem[ i ].key!=key;  - - i  );
 
      return i;
 
} // Search_Seq
 
//ASL＝（1＋n）/2，时间效率为 O(n)，这是查找成功的情况:
 
顺序查找的特点：
 
优点：算法简单，且对顺序结构或链表结构均适用。
 
       缺点： ASL 太大，时间效率太低。
 
  2）折半查找(二分查找)——只适用于有序表，且限于顺序存储结构。
 
  若关键字不在表中，怎样得知并及时停止查找？
 
  典型标志是：当查找范围的上界≤下界时停止查找。
 
  ASL的含义是“平均每个数据的查找时间”，而前式是n个数据查找时间的总和，所以：
 
 
 
3）分块查找（索引顺序查找）
 
思路：先让数据分块有序，即分成若干子表，要求每个子表中的数据元素值都比后一块中的数值小（但子表内部未必有序）。然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针）。
 
特点：块间有序，块内无序。
 
查找：块间折半，块内线性
 
查找步骤分两步进行：
 
① 对索引表使用折半查找法（因为索引表是有序表）；
 
② 确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；
 
查找效率ASL分析：
 
 
2.动态查找表
 
1）二叉排序树和平衡二叉树
 
 
二叉排序树的定义----或是一棵空树；或者是具有如下性质的非空二叉树：
 
 （1）若它的左子树不空，则左子树上所有结点的值均小于根的值；
 
 （2）若它的右子树不空，则右子树的所有结点的值均大于根的值；
 
 （3）它的左右子树也分别为二叉排序树。
 
二叉排序树又称二叉查找树。
 
二叉排序树的查找过程：
 
BiTree SearchBST(BiTree T, KeyType key)
 
{
 
        //在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素，
 
        //若查找成功，则返回指向该数据元素结点的指针，否则返回空指针
 
        if ((!T)||EQ(key, T->data.key))  return(T); //查找结束
 
        else if LT(key, T->data.key) return (SearchBST(T->lchild, key)); //在左子树中继续查找
 
        else return (SearchBST(T->rchild,key)); //在右子树中继续查找
 
}
 
 
二叉排序树的插入
 
        思路：查找不成功，生成一个新结点s，插入到二叉排序树中；查找成功则返回。
 
   SearchBST (K,  &t) { //K为待查关键字，t为根结点指针
 
   p=t;       //p为查找过程中进行扫描的指针
 
   while（p!=NULL）
 
{
 
   case {
 
               K= p->data:  {查找成功，return true;}
 
               K< p->data :  {q=p；p=p->lchild }  //继续向左搜索
 
               K> p->data :  {q=p；p=p->rchild } //继续向右搜索
 
            }
 
  }  //查找不成功则插入到二叉排序树中
 
s =(BiTree)malloc(sizeof(BiTNode)); 
 
s->data=K; s ->lchild=NULL; s ->rchild=NULL;
 
      //查找不成功，生成一个新结点s，插入到二叉排序树叶子处
 
case {
 
            t=NULL：   t=s;   //若t为空，则插入的结点s作为根结点
 
            K < q->data: q->lchild=s;  //若K比叶子小，挂左边
 
            K > q->data: q->rchild=s; //若K比叶子大，挂右边
 
        }
 
return OK;
 
}
 
 
二叉排序树的删除
 
假设：*p表示被删结点的指针； PL和PR 分别表示*P的左、右孩子指针；
 
*f表示*p的双亲结点指针；并假定*p是*f的左孩子；则可能有三种情况：
 
 
*p有两颗子树，有两种解决方法：
 
法1：令*p的左子树为 *f的左子树，*p的右子树接为*s的右子树；如下图(c)所示  //即 fL=PL  ;   SR=PR   ;
 
法2：直接令*p的直接前驱(或直接后继)替代*p，然后再从二叉排序树中删去它的直接前驱(或直接后继) 。如图(d),当以直接前驱*s替代*p时，由于*s只有左子树SL,则在删去*s之后，只要令SL为*s的双亲*q的右子树即可。 // *s为*p左子树最右下方的结点
 
 
删除算法如下：
 
Status Delete(BiTree &p)
 
{
 
    //从二叉排序树种删除结点p，并重接它的左或右子树
 
    if(!p->rchild) //右子树空，只需重接它的左子树
 
    {
 
        q=p;
 
        p=p->lchild;
 
        free(q);
 
    }
 
    else if(!p->lchild) //左子树空，只需重接它的右子树
 
    {
 
        q=p;
 
        p=p->rchild;
 
        free(q);
 
    }
 
    else //左右子树都不空
 
    {
 
        q=p; 
 
        s=p->lchild;
 
        while(s->rchild)  //转左，然后向右到尽头(找p的直接前驱) 图(b)
 
        {
 
            q=s;
 
            s=s->rchild;
 
        }
 
        p->data = s->data; //s指向被删结点的“前驱”
 
        if(q!=p)  //重接*q的右子树
 
        {
 
            q->rchild=s->lchild;
 
        }
 
        else  //q=p,说明s->rchild为空(即：p->lchild->rchild为空)，重接*q的左子树
 
        {
 
            q->lchild=s->lchild;
 
        }
 
         delete s;
 
    }//end else 左右子树都不空
 
    return TRUE;
 
}
 
二叉排序树查找分析：和折半查找类似，与给定值比较的关键字个数不超过树的深度。然而，折半查找长度为n的表的判定树是惟一的，而含有n个结点的二叉排序树却不惟一。
 
含有n个结点的二叉排序树的平均查找长度和树的形态有关。当先后插入的关键字有序时，构成的二叉排序树蜕变为单支树。树的深度为n，其平均查找长度为(n+1)/2(和顺序查找相同)，这是最差的情况。最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log2n成正比。
 
(n>=2)
 
 
 
 
平衡二叉树
 
又称AVL树，即它或者是一颗空树，或者具有如下性质：它的左子树和右子树都是平衡二叉树，且左子树与右子树的深度之差的绝对值不超过1。
 
平衡因子：该结点的左子树的深度减去它的右子树的深度。
 
平衡二叉树的特点：任一结点的平衡因子只能取：-1、0 或 1。
 
如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。
 
平衡旋转可以归纳为四类：单向右顺时针旋转(LL)；单向左逆时针旋转(RR)；双向旋转先左逆时针后右顺时针(LR)；双向旋转先右顺时针后左逆时针(RL)
 
 
 
平衡二叉树查找分析：
 
时间复杂度为O(logn)
 
3.B-树和B+树
 
B+树是应文件系统所需而出的一种B树的变型树。一棵m阶的B+树和m阶的B-树的差异在于：
 
1.有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点。
 
2.所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
 
3.所有的非终端结点可以看成是索引部分，结点中仅含其子树（根结点）中的最大（或最小）关键字。
 
通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。
 
B-树：一棵m阶的B-树或者是一棵空树，或者是满足下列要求的m叉树：
 
 
树中的每个结点至多有m棵子树；
 
 
若根结点不是叶子结点，则至少有两棵子树；
 
 
除根结点外，所有非终端结点至少有[ m/2 ] ( 向上取整 )棵子树。
 
 
所有的非终端结点中包括如下信息的数据（n,A0,K1,A1,K2,A2,….,Kn,An）
 
其中：Ki（i=1,2,…,n）为关键码，且Ki < K(i+1)，
 
Ai 为指向子树根结点的指针(i=0,1,…,n)，且指针A(i-1) 所指子树中所有结点的关键码均小于Ki (i=1,2,…,n)，An 所指子树中所有结点的关键码均大于Kn。n 为关键码的个数。
 
 
所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。
 
 
 
4.哈希表
 
哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
 
 
 
1）哈希函数构造方法
 
 
直接定址法
 
取关键字或关键字的某个线性函数值为散列地址。
 
即 H(key) = key 或 H(key) = a*key + b，其中a和b为常数。
 
 
除留余数法
 
取关键字被某个不大于散列表长度 m 的数 p 求余，得到的作为散列地址。
 
即 H(key) = key % p, p < m。
 
 
数字分析法
 
当关键字的位数大于地址的位数，对关键字的各位分布进行分析，选出分布均匀的任意几位作为散列地址。
 
仅适用于所有关键字都已知的情况下，根据实际应用确定要选取的部分，尽量避免发生冲突。
 
 
平方取中法
 
先计算出关键字值的平方，然后取平方值中间几位作为散列地址。
 
随机分布的关键字，得到的散列地址也是随机分布的。
 
 
折叠法（叠加法）
 
将关键字分为位数相同的几部分，然后取这几部分的叠加和（舍去进位）作为散列地址。
 
用于关键字位数较多，并且关键字中每一位上数字分布大致均匀。
 
 
随机数法
 
选择一个随机函数，把关键字的随机函数值作为它的哈希值。
 
通常当关键字的长度不等时用这种方法。
 
构造哈希函数的方法很多，实际工作中要根据不同的情况选择合适的方法，总的原则是尽可能少的产生冲突。
 
通常考虑的因素有关键字的长度和分布情况、哈希值的范围等。
 
如：当关键字是整数类型时就可以用除留余数法；如果关键字是小数类型，选择随机数法会比较好。
 
 
 
2）哈希冲突的解决方法
 
 
 
 
开放定址法
 
Hi=(H(key) + di) MOD m i=1,2,…,k (k<=m)
 
当冲突发生时，使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址（即该地址单元为空）为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探测到开放的地址则表明表中无待查的关键字，即查找失败。
 
当冲突发生时，使用某种探查(亦称探测)技术在散列表中寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到。
 
按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。
 
a.线性探查法
 
hi=(h(key)+i) ％ m ，0 ≤ i ≤ m-1
 
基本思想是：探查时从地址 d 开始，首先探查 T[d]，然后依次探查 T[d+1]，…，直到 T[m-1]，此后又循环到 T[0]，T[1]，…，直到探查到 有空余地址 或者到 T[d-1]为止。
 
b.二次探查法
 
hi=(h(key)+i*i) ％ m，0 ≤ i ≤ m-1
 
基本思想是：探查时从地址 d 开始，首先探查 T[d]，然后依次探查 T[d+1^2]，T[d+2^2]，T[d+3^2],…，等，直到探查到 有空余地址 或者到 T[d-1]为止。缺点是无法探查到整个散列空间。
 
c.双重散列法
 
hi=(h(key)+i*h1(key)) ％ m，0 ≤ i ≤ m-1
 
基本思想是：探查时从地址 d 开始，首先探查 T[d]，然后依次探查 T[d+h1(d)], T[d + 2*h1(d)]，…，等。
 
该方法使用了两个散列函数 h(key) 和 h1(key)，故也称为双散列函数探查法。
 
定义 h1(key) 的方法较多，但无论采用什么方法定义，都必须使 h1(key) 的值和 m 互素，才能使发生冲突的同义词地址均匀地分布在整个表中，否则可能造成同义词地址的循环计算。
 
该方法是开放定址法中最好的方法之一。
 
 
链接法（拉链法）
 
将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为 m，则可将散列表定义为一个由 m 个头指针组成的指针数组 T[0..m-1] 。
 
凡是散列地址为 i 的结点，均插入到以 T[i] 为头指针的单链表中。
 
T 中各分量的初值均应为空指针。
 
在拉链法中，装填因子 α 可以大于 1，但一般均取 α ≤ 1。
 
 
3.哈希表的查找及其分析
 
哈希表是实现关联数组（associative array）的一种数据结构，广泛应用于实现数据的快速查找。
 
查找过程中，关键字的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。
 
影响产生冲突多少有以下三个因素：
 
1）哈希函数是否均匀；
 
2）处理冲突的方法；
 
3）哈希表的加载因子。
 
 
 
第九章：内部排序
 
排序:将一个数据元素(或记录)的任意序列，重新排列成一个按关键字有序的序列。
 
稳定性——若两个记录A和B的关键字值相等，且排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。
 
1.插入排序
 
思想：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。
 
简言之，边插入边排序，保证子序列中随时都是排好序的。
 
1)  直接插入排序
 
    在已形成的有序表中线性查找，并在适当位置插入，把原来位置上的元素向后顺移。
 
 
时间效率： 因为在最坏情况下，所有元素的比较次数总和为（0＋1＋…＋n-1)→O(n^2)。
 
其他情况下也要考虑移动元素的次数。 故时间复杂度为O(n^2)
 
空间效率：仅占用1个缓冲单元——O（1）
 
算法的稳定性：稳定
 
直接插入排序算法的实现：
 
void InsertSort ( SqList &L ) 
 
{ //对顺序表L作直接插入排序
 
 for ( i = 2;  i <=L.length; i++) //假定第一个记录有序
 
{
 
     L.r[0]= L.r[i];
 
       j=i-1 ;                      //先将待插入的元素放入“哨兵”位置
 
     while（L[0] .key<L[j].key)
 
    {  
 
        L.r[j+1]= L.r[j];
 
        j--  ;                    
 
    }      //只要子表元素比哨兵大就不断后移
 
    L.r[j+1]= L.r[0];      //直到子表元素小于哨兵，将哨兵值送入
 
                                 //当前要插入的位置（包括插入到表首）
 
}
 
}
 
2)折半插入排序
 
子表有序且为顺序存储结构，则插入时采用折半查找定可加速。
 
优点：比较次数大大减少，全部元素比较次数仅为O(nlog2n)。
 
时间效率：虽然比较次数大大减少，可惜移动次数并未减少， 所以排序效率仍为O(n^2) 。
 
空间效率：仍为 O(1)
 
稳 定  性： 稳定
 
 
 
3)希尔排序—不稳定
 
基本思想：先将整个待排记录序列分割成若干子序列,分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
 
优点：让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多。
 
时间效率：当n在某个特定范围内，希尔排序所需的比较和移动次数约为n^1.3,当n->无穷，可减少到n(log2n)^2
 
空间效率：O(1)
 
 
4)快速排序
 
基本思想：从待排序列中任取一个元素 (例如取第一个) 作为中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。
 
优点：因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快！
 
前提：顺序存储结构
 
 
时间效率：O(nlog2n) —因为每趟确定的元素呈指数增加
 
空间效率：O（log2n）—因为递归要用栈(存每层low，high和pivot)
 
稳 定 性： 不 稳 定 — —因为有跳跃式交换。
 
算法：
 
int partition(SqList &L,int low,int high)
 
{
 
  L.r[0] = L.r[low];
 
  pivot key = L.r[low].key;
 
    while(low < high)
 
    {
 
     while(low<high&&L.r[high]>=pivot) high--;
 
     L.r[low] = L.r[high];
 
     while(low<high&&L.r[low]<=pivot) low++;
 
     L.r[high] = L.r[low];
 
    }
 
    L.r[low] = pivot;
 
    return low;
 
}
 
 
 
5)冒泡排序
 
基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。
 
优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。
 
前提：顺序存储结构
 
 
冒泡排序的算法分析：
 
时间效率：O（n^2) —因为要考虑最坏情况
 
空间效率：O（1） —只在交换时用到一个缓冲单元
 
稳 定 性： 稳定  —25和25*在排序前后的次序未改变
 
冒泡排序的优点：每一趟整理元素时，不仅可以完全确定一个元素的位置（挤出一个泡到表尾），还可以对前面的元素作一些整理，所以比一般的排序要快。
 
选择排序：选择排序的基本思想是：每一趟在后面n-i 个待排记录中选取关键字最小的记录作为有序序列中的第i  个记录。
 
6)简单选择排序
 
思路异常简单：每经过一趟比较就找出一个最小值，与待排序列最前面的位置互换即可。
 
——首先，在n个记录中选择最小者放到r[1]位置；然后，从剩余的n-1个记录中选择最小者放到r[2]位置；…如此进行下去，直到全部有序为止。
 
优点：实现简单
 
缺点：每趟只能确定一个元素，表长为n时需要n-1趟
 
前提：顺序存储结构
 
 
时间效率：O(n^2)——虽移动次数较少，但比较次数较多
 
空间效率：O(1)
 
算法稳定性——不稳定
 
Void SelectSort(SqList  &L ) 
 
{
 
for (i=1;  i<L.length; ++i)
 
{
 
     j = SelectMinKey(L,i);  //在L.r[i..L.length]中选择key最小的记录
 
     if( i!=j )   r[i] <--> r[j]; //与第i个记录交换
 
      } //for
 
  }  //SelectSort
 
 
 
7）堆排序
 
设有n个元素的序列 k1，k2，…，kn，当且仅当满足下述关系之一时，称之为堆。
 
 
如果让满足以上条件的元素序列 （k1，k2，…，kn）顺次排成一棵完全二叉树，则此树的特点是：树中所有结点的值均大于（或小于）其左右孩子，此树的根结点（即堆顶）必最大（或最小）。
 
堆排序算法分析：
 
时间效率：O(nlog2n)。因为整个排序过程中需要调用n-1次HeapAdjust( )算法，而算法本身耗时为log2n；
 
空间效率：O(1)。仅在第二个for循环中交换记录时用到一个临时变量temp。
 
稳定性： 不稳定。
 
优点：对小文件效果不明显，但对大文件有效。
 
 
 
8）归并排序----稳定
 
将两个或两个以上有序表组合成一个新的有序表。
 
时间复杂度：O(nlogn)
 
空间复杂度：和待排记录等数量的辅助空间。
 
 
 
9）基数排序
 
时间复杂度：对于n各记录（每个记录含d个关键字，每个关键字取值范围为rd个值）进行链式基数排序的时间复杂度为O(d(n+rd)),其中每一趟分配的时间复杂度为O(n),每一趟收集的时间复杂度为O(rd)
 
10）各种内部排序方法的比较讨论
 
 
(1) 从平均时间性能看，快速排序最佳，其所需时间最省，但快速排序的最坏情况下的时间性能不如堆排序和快速排序。后两者相比较，在n较大时，归并排序所需时间较堆排序省，但它所需的辅助存储量最多。
 
(2)基数排序的时间复杂度可写成O(dn)。因此，它最适用于n值很大而关键字较小的序列。
 
(3)从方法的稳定性来比较，基数排序是稳定的内排方法，所需时间复杂度为O(n^2)的简单排序方法也是稳定的，然而，快速排序、堆排序和希尔排序等时间性能较好的排序方法是不稳定的。

数据结构
 
一些概念
 
 
 
数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。
 
 
数据：所有能被输入到计算机中，且能被计算机处理的符号的集合。是计算机操作的对象的总称。
数据元素：数据（集合）中的一个“个体”，数据及结构中讨论的基本单位
数据项：数据的不可分割的最小单位。一个数据元素可由若干个数据项组成。
数据类型：在一种程序设计语言中，变量所具有的数据种类。整型、浮点型、字符型等等
逻辑结构：数据之间的相互关系。
 
  
集合 结构中的数据元素除了同属于一种类型外，别无其它关系。
线性结构 数据元素之间一对一的关系
树形结构 数据元素之间一对多的关系
图状结构或网状结构 结构中的数据元素之间存在多对多的关系
物理结构/存储结构：数据在计算机中的表示。物理结构是描述数据具体在内存中的存储（如：顺序结构、链式结构、索引结构、哈希结构）等
在数据结构中,从逻辑上可以将其分为线性结构和非线性结构
数据结构的基本操作的设置的最重要的准则是,实现应用程序与存储结构的独立。实现应用程序是“逻辑结构”，存储的是“物理结构”。逻辑结构主要是对该结构操作的设定，物理结构是描述数据具体在内存中的存储（如：顺序结构、链式结构、索引结构、希哈结构）等。
顺序存储结构中，线性表的逻辑顺序和物理顺序总是一致的。但在链式存储结构中，线性表的逻辑顺序和物理顺序一般是不同的。
算法五个特性： 有穷性、确定性、可行性、输入、输出
算法设计要求：正确性、可读性、健壮性、高效率与低存储量需求。(好的算法)
算法的描述有伪程序、流程图、N-S结构图等。E-R图是实体联系模型，不是程序的描述方式。
设计算法在执行时间时需要考虑：算法选用的规模、问题的规模
时间复杂度：算法的执行时间与原操作执行次数之和成正比。时间复杂度有小到大：O(1)、O(logn)、O(n)、O(nlogn)、O(n2)、O(n3)。幂次时间复杂度有小到大O(2n)、O(n!)、O(nn)
空间复杂度：若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。
 
线性表
 
线性表是一种典型的线性结构。头结点无前驱有一个后继，尾节点无后继有一个前驱。链表只能顺序查找，定位一个元素的时间为O(N)，删除一个元素的时间为O(1)
 
线性表的顺序存储结构：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。是一种随机存取的存储结构。顺序存储指内存地址是一块的，随机存取指访问时可以按下标随机访问，存储和存取是不一样的。如果是存储，则是指按顺序的，如果是存取，则是可以随机的，可以利用元素下标进行。数组比线性表速度更快的是：原地逆序、返回中间节点、选择随机节点。 
 
  
便于线性表的构造和任意元素的访问
插入：插入新结点，之后结点后移。平均时间复杂度:O(n)
删除：删除节点，之后结点前移。平均时间复杂度:O(n)
线性链表：用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址。data域是数据域，用来存放结点的值。next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。不需要事先估计存储空间大小。 
 
  
单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。同时，由于最后一个结点无后继，故结点的指针域为空，即NULL。头插法建表(逆序)、尾插法建表(顺序)。增加头结点的目的是算法实现上的方便，但增大了内存开销。 
 
    
查找：只能从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。
插入：先找到表的第i-1的存储位置，然后插入。新结点先连后继，再连前驱。
删除：首先找到ai-1的存储位置p。然后令p–>next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间.r=p->next;p->next=r->next;delete r。
判断一个单向链表中是否存在环的最佳方法是快慢指针。
静态链表：用一维数组来实现线性链表，这种用一维数组表示的线性链表，称为静态链表。静态：体现在表的容量是一定的。（数组的大小）；链表：插入与删除同前面所述的动态链表方法相同。静态链表中指针表示的是下一元素在数组中的位置。
静态链表是用数组实现的，是顺序的存储结构，在物理地址上是连续的，而且需要预先分配大小。动态链表是用申请内存函数（C是malloc,C++是new）动态申请内存的，所以在链表的长度上没有限制。动态链表因为是动态申请内存的，所以每个节点的物理地址不连续，要通过指针来顺序访问。静态链表在插入、删除时也是通过修改指针域来实现的，与动态链表没有什么分别
循环链表：是一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。 
 
    
在单链表中，将终端结点的指针域NULL改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p—>next是否为空，而是判断它们是否等于某一指定指针，如头指针或尾指针等。
双向链表:在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链。双链表一般由头指针唯一确定的，将头结点和尾结点链接起来构成循环链表，并称之为双向链表。设指针p指向某一结点，则双向链表结构的对称性可用下式描述：p—>prior—>next=p=p—>next—>prior。从两个方向搜索双链表，比从一个方向搜索双链表的方差要小。 
 
    
插入：先搞定插入节点的前驱和后继，再搞定后结点的前驱，最后搞定前结点的后继。
在有序双向链表中定位删除一个元素的平均时间复杂度为O(n)
可以直接删除当前指针所指向的节点。而不需要像单向链表中，删除一个元素必须找到其前驱。因此在插入数据时，单向链表和双向链表操作复杂度相同，而删除数据时，双向链表的性能优于单向链表
 
栈和队列
 
栈
 
栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。先进后出。top= -1时为空栈，top=0只能说明栈中只有一个元素，并且元素进栈时top应该自增
 
顺序存储栈：顺序存储结构
链栈：链式存储结构。插入和删除操作仅限制在链头位置上进行。栈顶指针就是链表的头指针。通常不会出现栈满的情况。 不需要判断栈满但需要判断栈空。
两个栈共用静态存储空间,对头使用也存在空间溢出问题。栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是top[1]+1=top[2]。
基本操作：删除栈顶元素、判断栈是否为空以及将栈置为空栈等
对于n各元素的入栈问题，可能的出栈顺序有C(2n,n)/(n+1)个。
堆栈溢出一般是循环的递归调用、大数据结构的局部变量导致的
 
应用，代码：
 
进制转换
括号匹配的检验
行编辑程序
迷宫求解：若当前位置“可通”，则纳入路径，继续前进;若当前位置“不可通”，则后退，换方向继续探索;若四周“均无通路”，则将当前位置从路径中删除出去。
表达式求解：前缀、中缀、后缀。 
 
  
操作数之间的相对次序不变;
运算符的相对次序不同;
中缀式丢失了括弧信息，致使运算的次序不确定
前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式
后缀式的运算规则为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。
实现递归：多个函数嵌套调用的规则是：后调用先返回。
浏览器历史纪录，Android中的最近任务，Activity的启动模式，CPU中栈的实现，Word自动保存，解析计算式，解析xml/json。解析XML时，需要校验节点是否闭合，节点闭合的话，有头尾符号相对应，遇到头符号将其放入栈中，遇到尾符号时，弹出栈的内容，看是否有与之对应的头符号，栈的特性刚好符合符号匹配的就近原则。
 
不是所有的递归程序都需要栈来保护现场，比方说求阶乘的，是单向递归，直接用循环去替代从1乘到n就是结果了，另外一些需要栈保存的也可以用队列等来替代。不是所有的递归转化为非递归都要用到栈。转化为非递归主要有两种方法：对于尾递归或单向递归，可以用循环结构算法代替
 
队列
 
队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。先进先出。
 
顺序队列：顺序存储结构。当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头前一个位置，而尾指针始终指向队尾元素的实际位置
循环队列。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（MaxSize-1）时，其加1操作的结果是指向向量的下界0。除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列“空”还是“满”
链队列：链式存储结构。限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。
设尾指针的循环链表表示队列,则入队和出队算法的时间复杂度均为O(1)。用循环链表表示队列，必定有链表的头结点，入队操作在链表尾插入，直接插入在尾指针指向的节点后面，时间复杂度是常数级的；出队操作在链表表头进行，也就是删除表头指向的节点，时间复杂度也是常数级的。
队空条件：rear==front，但是一般需要引入新的标记来说明栈满还是栈空，比如每个位置布尔值
队满条件：(rear+1) % QueueSize==front，其中QueueSize为循环队列的最大长度
计算队列长度：（rear-front+QueueSize）% QueueSize
入队：（rear+1）% QueueSize
出队：（front+1）% QueueSize
假设以数组A[N]为容量存放循环队列的元素,其头指针是front,当前队列有X个元素,则队列的尾指针值为(front+X mod N)
 
串
 
串(String)是零个或多个字符组成的有限序列。长度为零的串称为空串(Empty String)，它不包含任何字符。通常将仅由一个或多个空格组成的串称为空白串(Blank String) 注意：空串和空白串的不同，例如“ ”和“”分别表示长度为1的空白串和长度为0的空串。
 
串的表示和实现：
 
定长顺序存储表示。静态存储分配的顺序表。
堆分配存储表示。存储空间是在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表
串的链式存储结构。
 
串匹配：将主串称为目标串，子串称之为模式串。蛮力法匹配。KMP算法匹配。Boyer-Moore算法匹配。
 
数组和广义表
 
数组和广义表可看成是一种特殊的线性表，其特殊在于: 表中的元素本身也是一种线性表。内存连续。根据下标在O(1)时间读/写任何元素。
 
二维数组，多维数组，广义表、树、图都属于非线性结构
 
数组
 
数组的顺序存储：行优先顺序；列优先顺序。数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。
 
关联数组(Associative Array)，又称映射（Map）、字典（ Dictionary）是一个抽象的数据结构，它包含着类似于(键，值)的有序对。 不是线性表。
 
矩阵的压缩：
 
对称矩阵、三角矩阵：直接存储矩阵的上三角或者下三角元素。注意区分i>=j和i
 
广义表
 
广义表（Lists，又称列表）是线性表的推广。广义表是n(n≥0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表。若广义表LS（n>=1)非空，则a1是LS的表头，其余元素组成的表(a2,…an)称为LS的表尾。广义表的元素可以是广义表，也可以是原子，广义表的元素也可以为空。表尾是指除去表头后剩下的元素组成的表，表头可以为表或单元素值。所以表尾不可以是单个元素值。
 
例子：
 
A=（）——A是一个空表，其长度为零。
B=（e）——表B只有一个原子e，B的长度为1。
C=（a,(b,c,d))——表C的长度为2，两个元素分别为原子a和子表(b,c,d)。
D=（A，B，C）——表D的长度为3，三个元素都是广义 表。显然，将子表的值代入后，则有D=(( ),(e),(a,(b,c,d)))。
E=（a,E）——这是一个递归的表，它的长度为2，E相当于一个无限的广义表E=(a,(a,(a,(a,…)))).
 
三个结论：
 
广义表的元素可以是子表，而子表的元素还可以是子表。由此，广义表是一个多层次的结构，可以用图形象地表示
广义表可为其它表所共享。例如在上述例4中，广义表A，B，C为D的子表，则在D中可以不必列出子表的值，而是通过子表的名称来引用。
广义表的递归性
 
考点：
 
广义表是0个或多个单因素或子表组成的有限序列，广义表可以是自身的子表，广义表的长度n>=0，所以可以为空表。广义表的同级元素(直属于同一个表中的各元素)具有线性关系
广义表的表头为空，并不代表该广义表为空表。广义表()和(())不同。前者是长度为0的空表，对其不能做求表头和表尾的运算；而后者是长度为l的非空表(只不过该表中惟一的一个元素是空表)，对其可进行分解，得到的表头和表尾均是空表()
已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是head(tail(head(tail(LS)))。根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。也就是说，广义表的head操作，取出的元素是什么，那么结果就是什么。但是tail操作取出的元素外必须加一个表——“（）“。tail(LS)＝((d,e,f))；head(tail(LS))=(d,e,f)；tail(head(tail(LS)))=(e,f)；head(tail(head(tail(LS))))=e。
二维以上的数组其实是一种特殊的广义表
在（非空）广义表中：1、表头head可以是原子或者一个表 2、表尾tail一定是一个表 3.广义表难以用顺序存储结构 4.广义表可以是一个多层次的结构
 
树和二叉树
 
一种非线性结构。树是递归结构，在树的定义中又用到了树的概念。
 
基本术语：
 
树结点：包含一个数据元素及若干指向子树的分支；
孩子结点：结点的子树的根称为该结点的孩子；
双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；
兄弟结点：同一双亲的孩子结点；
堂兄结点：同一层上结点；
结点层次：根结点的层定义为1；根的孩子为第二层结点，依此类推；
树的高（深）度：树中最大的结点层
结点的度：结点子树的个数
树的度： 树中最大的结点度。
叶子结点：也叫终端结点，是度为0的结点；
分枝结点：度不为0的结点（非终端结点）；
森林：互不相交的树集合；
有序树：子树有序的树，如：家族树；
无序树：不考虑子树的顺序；
 
二叉树
 
二叉树可以为空。二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。注意区分：二叉树、二叉查找树/二叉排序树/二叉搜索树、二叉平衡(查找)树
 
二叉平衡树肯定是一颗二叉排序树。堆不是一颗二叉平衡树。
 
二叉树与树是不同的，二叉树不等价于分支树最多为二的有序树。当一个结点只包含一个子节点时，对于有序树并无左右孩子之分，而对于二叉树来说依然有左右孩子之分，所以二叉树与树是两种不同的结构。
 
性质：
 
在二叉树的第 i 层上至多有2i-1个结点。
深度为 k 的二叉树上至多含 2k-1 个结点（k≥1）
对任何一棵二叉树，若它含有n0个叶子结点、n2个度为 2 的结点，则必存在关系式：n0= n2+1。
具有 n 个结点的完全二叉树的深度为⎣log2 n⎦+1 。
n个结点的二叉树中，完全二叉树具有最小的路径长度。
如果对一棵有n个结点的完全二叉树的结点按层序编号,则对任一结点i（1<=i<=n),有： 
 
  
如果i＝1，则结点i无双亲，是二叉树的根；如果i>1，则其双亲的编号是 i/2(整除）。
如果2i>n，无左孩子；否则，其左孩子是结点2i。
如果2i＋1>n，则结点i无右孩子；否则，其右孩子是结点2i＋1。
 
二叉树的存储结构
 
顺序存储结构：仅仅适用于满或完全二叉树，结点之间的层次关系由性质5确定。
二叉链表法：每个节点存储左子树和右子树。三叉链表：左子树、右子树、父节点，总的指针是n+2
在有n个结点的二叉链表中，值为非空的链域的个数为n-1。在有N个结点的二叉链表中必定有2N个链域。除根结点外，其余N-1个结点都有一个父结点。所以，一共有N-1个非空链域，其余2N-(N-1)=N+1个为空链域。
二叉链存储法也叫孩子兄弟法，左指针指向左孩子，右指针指向右兄弟。而中序遍历的顺序是左孩子，根，右孩子。这种遍历顺序与存储结构不同，因此需要堆栈保存中间结果。而中序遍历检索二叉树时，由于其存储结构跟遍历顺序相符，因此不需要用堆栈。
 
遍历二叉树和线索二叉树
 
遍历二叉树：使得每一个结点均被访问一次，而且仅被访问一次。非递归的遍历实现要利用栈。
 
先序遍历DLR：根节点->左子树->右子树
中序遍历LDR：左子树->根节点->右子树。必须要有中序遍历才能得到一棵二叉树的正确顺序
后续遍历LRD：左子树->右子树->根节点。需要栈的支持。
层次遍历：用一维数组存储二叉树时,总是以层次遍历的顺序存储结点。层次遍历应该借助队列。
 
线索二叉树：对二叉树所有结点做某种处理可在遍历过程中实现；检索（查找）二叉树某个结点，可通过遍历实现；如果能将二叉树线索化，就可以简化遍历算法，提高遍历速度，目的是加快查找结点的前驱或后继的速度。
 
如何线索化？以中序遍历为例，若能将中序序列中每个结点前趋、后继信息保存起来，以后再遍历二叉树时就可以根据所保存的结点前趋、后继信息对二叉树进行遍历。对于二叉树的线索化，实质上就是遍历一次二叉树，只是在遍历的过程中，检查当前结点左，右指针域是否为空，若为空，将它们改为指向前驱结点或后继结点的线索。前驱就是在这一点之前走过的点，不是下一将要去往的点。
 
加上结点前趋后继信息（结索）的二叉树称为线索二叉树。n个结点的线索二叉树上每个结点有2个指针域（指向左孩子和右孩子），总共有2n个指针域；一个n个结点的树有n-1条边，那么空指针域= 2n - (n-1) = n + 1，即线索数为n+1。指针域tag为0，存放孩子指针，为1，存放前驱/后继节点指针。
 
线索树下结点x的前驱与后继查找：设结点x相应的左（右）标志是线索标志，则lchild(rchild)就是前驱(后继），否则：
 
LDR–前驱：左子树中最靠右边的结点；后继：右子树中最靠左边的结点
LRD–前驱：右子树的根，若无右子树，为左子树跟。后继：x是根，后继是空；x是双亲的右孩子、x是双亲的左孩子，但双亲无右孩子，双亲是后继；x是双亲的左孩子，双亲有右孩子，双亲右子树中最左的叶子是后继
DLR–对称于LRD线索树—将LRD中所有左右互换，前驱与后继互换，得到DLR的方法。
为简化线索链表的遍历算法，仿照线性链表，为线索链表加上一头结点，约定： 
 
  
头结点的lchild域：存放线索链表的根结点指针；
头结点的rchild域: 中序序列最后一个结点的指针；
中序序列第一结点lchild域指向头结点;
中序序列最后一个结点的rchild域指向头结点;
 
中序遍历的线索二叉树以及线索二叉树链表示意图 
 
 
一棵左右子树均不空的二叉树在前序线索化后,其中空的链域的个数是1。前序和后续线索化后空链域个数都是1，中序是2。二叉树在线索化后，仍不能有效求解的问题是前序求前序先驱，后序求后序后继。
 
中序遍历的顺序为：左、根、右，所以对于每一非空的线索，左子树结点的后继为根结点，右子树结点的前驱为根结点，再递归的执行上面的过程，可得非空线索均指向其祖先结点。在中序线索二叉树中,每一非空的线索均指向其祖先结点。
 
在二叉树上加上结点前趋、后继线索后，可利用线索对二叉树进行遍历,此时，不需栈，也不需递归。基本步骤：
 
p=T->lchild; p指向线索链表的根结点；
若线索链表非空，循环： 
 
  
循环，顺着p左孩子指针找到最左下结点；访问之； 
若p所指结点的右孩子域为线索，p的右孩子结点即为后继结点循环： p=p->rchild； 并访问p所指结点；（在此循环中，顺着后继线索访问二叉树中的结点）
一旦线索“中断”，p所指结点的右孩子域为右孩子指针，p=p->rchild，使 p指向右孩子结点；
 
树和森林
 
树的存储结构：
 
双亲表示法
孩子表示法
利用图表示树
孩子兄弟表示法（二叉树表示法）：链表中每个结点的两指针域分别指向其第一个孩子结点和下一个兄弟结点
 
将树转化成二叉树：右子树一定为空
 
加线：在兄弟之间加一连线
抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系
旋转：以树的根结点为轴心，将整树顺时针转45°
 
森林转换成二叉树：
 
将各棵树分别转换成二叉树
将每棵树的根结点用线相连
以第一棵树根结点为二叉树的根
 
树与转换后的二叉树的关系：转换后的二叉树的先序对应树的先序遍历；转换后的二叉树的中序对应树的后序遍历
 
哈弗曼树/霍夫曼树
 
一些概念
 
路径：从一个祖先结点到子孙结点之间的分支构成这两个结点间的路径；
路径长度：路径上的分支数目称为路径长度；
树的路径长度：从根到每个结点的路径长度之和。
结点的权：根据应用的需要可以给树的结点赋权值；
结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积；
树的带权路径长度=树中所有叶子结点的带权路径之和；通常记作 WPL=∑wi×li 
哈夫曼树：假设有n个权值(w1, w2, … , wn)，构造有n个叶子结点的二叉树，每个叶子结点有一个 wi作为它的权值。则带权路径长度最小的二叉树称为哈夫曼树。最优二叉树。
 
前缀码的定义：在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。霍夫曼编码就是前缀码，可用于快速判断霍夫曼编码是否正确。霍夫曼树是满二叉树，若有n个节点，则共有(n+1)/2个码子
 
给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为霍夫曼树(Huffman Tree)。霍夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
 
假设哈夫曼树是二叉的话，则度为0的结点个数为N，度为2的结点个数为N-1，则结点总数为2N-1。哈夫曼树的结点个数必为奇数。
 
哈夫曼树不一定是完全二叉树，但一定是最优二叉树。
 
若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为[(n-1)/(m-1)]。边的数目等于度。
 
图遍历与回溯
 
图搜索->形成搜索树
 
穷举法。
贪心法。多步决策，每步选择使得构成一个问题的可能解，同时满足目标函数。
回溯法。根据题意，选取度量标准，然后将可能的选择方法按度量标准所要求顺序排好，每次处理一个量，得到该意义下的最优解的分解处理。
 
图
 
无向图
 
回路或环：第一个顶点和最后一个顶点相同的路径。
简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路
连通：顶点v至v’ 之间有路径存在
连通图：无向图图 G 的任意两点之间都是连通的，则称G是连通图。
连通分量：极大连通子图，子图中包含的顶点个数极大
所有顶点度的和必须为偶数
 
有向图：
 
回路或环：第一个顶点和最后一个顶点相同的路径。
简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。
连通：顶点v至v’之间有路径存在
强连通图：有向图G的任意两点之间都是连通的，则称G是强连通图。各个顶点间均可达。
强连通分量：极大连通子图
有向图顶点的度是顶点的入度与出度之和。邻接矩阵中第V行中的1的个数是V的出度
生成树：极小连通子图。包含图的所有n个结点，但只含图的n-1条边。在生成树中添加一条边之后，必定会形成回路或环。
完全图：有 n(n-1)/2 条边的无向图。其中n是结点个数。必定是连通图。
有向完全图：有n(n-1)条边的有向图。其中n是结点个数。每两个顶点之间都有两条方向相反的边连接的图。
一个无向图 G=(V,E) 是连通的，那么边的数目大于等于顶点的数目减一：|E|>=|V|-1，而反之不成立。如果 G=(V,E) 是有向图，那么它是强连通图的必要条件是边的数目大于等于顶点的数目：|E|>=|V|，而反之不成立。没有回路的无向图是连通的当且仅当它是树，即等价于：|E|=|V|-1。
 
图的存储形式
 
邻接矩阵和加权邻接矩阵 
 
  
无权有向图：出度: i行之和；入度: j列之和。
无权无向图：i结点的度: i行或i列之和。
加权邻接矩阵：相连为w，不相连为∞
邻接表 
 
  
用顶点数组表、边（弧）表表示该有向图或无向图
顶点数组表：用数组存放所有的顶点。数组大小为图顶点数n
边表（边结点表）：每条边用一个结点进行表示。同一个结点的所有的边形成它的边结点单链表。 
n个顶点的无向图的邻接表最多有n(n-1)个边表结点。有n个顶点的无向图最多有n*(n-1)/2条边，此时为完全无向图，而在邻接表中每条边存储两次，所以有n*(n-1)个结点
 
图的遍历
 
深度优先搜索利用栈，广度优先搜索利用队列
 
求一条从顶点i到顶点s的简单路径–深搜。求两个顶点之间的一条长度最短的路径–广搜。当各边上的权值均相等时,BFS算法可用来解决单源最短路径问题。
 
生成树和最小生成树
 
每次遍历一个连通图将图的边分成遍历所经过的边和没有经过的边两部分，将遍历经过的边同图的顶点构成一个子图，该子图称为生成树。因此有DFS生成树和BFS生成树。
 
生成树是连通图的极小子图，有n个顶点的连通图的生成树必定有n-1条边,在生成树中任意增加一条边，必定产生回路。若砍去它的一条边，就会把生成树变成非连通子图
 
最小生成树：生成树中边的权值(代价)之和最小的树。最小生成树问题是构造连通网的最小代价生成树。
 
Kruskal算法：令最小生成树集合T初始状态为空，在有n个顶点的图中选取代价最小的边并从图中删去。若该边加到T中有回路则丢弃，否则留在T中；依此类推，直至T中有n-1条边为止。
 
Prim算法、Kruskal算法和Dijkstra算法均属于贪心算法。
 
Dijkstra算法解决的是带权重的有向图上单源最短路径问题，该算法要求所有边的权重都为非负值。
Dijkstra算法解决了从某个原点到其余各顶点的最短路径问题，由循环嵌套可知该算法的时间复杂度为O(N*N)。若要求任一顶点到其余所有顶点的最短路径，一个比较简单的方法是对每个顶点当做源点运行一次该算法，等于在原有算法的基础上，再来一次循环，此时整个算法的复杂度就变成了O(N*N*N)。
Bellman-Ford算法解决的是一般情况下的单源最短路径问题，在这里，边的权重可以为负值。该算法返回一个布尔值，以表明是否存在一个从源节点可以到达的权重为负值的环路。如果存在这样一个环路，算法将告诉我们不存在解决方案。如果没有这种环路存在，算法将给出最短路径和它们的权重。
 
双连通图和关节点
 
若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为重（双）连通图。
 
若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为关节点。
 
没有关节点的连通图为双连通图
 
若生成树的根结点，有两个或两个以上的分支，则此顶点(生成树的根)必为关节点；
对生成树上的任意一个非叶“顶点”，若其某棵子树中的所有“顶点”没有和其祖先相通的回边，则该“顶点”必为关节点。
 
有向无环图及其应用
 
拓扑排序。在用邻接表表示图时,对有n个顶点和e条弧的有向图而言时间复杂度为O(n+e)。一个有向图能被拓扑排序的充要条件就是它是一个有向无环图。拓扑序列唯一不能唯一确定有向图。
 
AOV网(Activity On Vertex)：用顶点表示活动，边表示活动的优先关系的有向图称为AOV网。AOV网中不允许有回路，这意味着某项活动以自己为先决条件。 
 
拓扑有序序列：把AOV网络中各顶点按照它们相互之间的优先关系排列一个线性序列的过程。若vi是vj前驱，则vi一定在vj之前；对于没有优先关系的点，顺序任意。
 
拓扑排序：对AOV网络中顶点构造拓扑有序序列的过程。方法：
 
在有向图中选一个没有前驱的顶点且输出之
从图中删除该顶点和所有以它为尾的弧
重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止(此时说明图中有环）
 
采用深度优先搜索或拓扑排序算法可以判断出一个有向图中是否有环(回路).深度优先搜索只要在其中记录下搜索的节点数n，当n大于图中节点数时退出，并可以得出有回路。若有回路，则拓扑排序访问不到图中所有的节点，所以也可以得出回路。广度优先搜索过程中如果访问到一个已经访问过的节点，可能是多个节点指向这个节点，不一定是存在环。
 
算法描述：
 
把邻接表中入度为0的顶点依此进栈
若栈不空，则 
 
  
栈顶元素vj退栈并输出；
在邻接表中查找vj的直接后继vk，把vk的入度减1；若vk的入度为0则进栈
若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕。
 
AOE网：带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。在工程上常用来表示工程进度计划。
 
一些定义：
 
事件的最早发生时间（ve(j)）：从源点到j结点的最长的路径。意味着事件最早能够发生的时间。
事件的最迟发生时间（vl(j)）：不影响工程的如期完工，事件j必须发生的时间。
活动ai由弧
 
查找
 
顺序查找、折半查找、索引查找、分块查找是静态查找，动态查找有二叉排序树查找，最优二叉树查找，键树查找，哈希表查找
 
静态查找表
 
顺序表的顺序查找：应用范围：顺序表或线性链表表示的表，表内元素之间无序。查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较。
 
顺序有序表的二分查找。平均查找时间(n+1)/n log2(n+1)
 
分块查找：将表分成几块，块内无序，块间有序，即前一块中的最大值小于后一块中的最小值。并且有一张索引表，每一项存放每一块的最大值和指向该块第一个元素的指针。索引表有序，块内无序。所以，块间查找用二分查找，块内用顺序查找，效率介于顺序和二分之间；先确定待查记录所在块，再在块内查找。因此跟表中元素个数和块中元素个数都有关。
 
用数组存放待查记录,
建立索引表，由每块中最大（小）的关键字及所属块位置的信息组成。
当索引表较大时，可以采用二分查找
在数据量极大时，索引可能很多，可考虑建立索引表的索引，即二级索引，原则上索引不超过三级
 
分块查找平均查找长度：ASLbs = Lb + Lw。其中，Lb是查找索引表确定所在块的平均查找长度， Lw是在块中查找元素的平均查找长度。在n一定时，可以通过选择s使ASL尽可能小。当s=sqrt(n)时，ASL最小。
 
时间：顺序查找最差，二分最好，分块介于两者之间
空间：分块最大，需要增加索引数据的空间
顺序查找对表没有特殊要求 
分块时数据块之间在物理上可不连续。所以可以达到插入、删除数据只涉及对应的块；另外，增加了索引的维护。
二分查找要求表有序，所以若表的元素的插入与删除很频繁，维持表有序的工作量极大。
在表不大时，一般直接使用顺序查找。
 
动态查找
 
二叉排序树的结点删除：
 
x为叶子结点，则直接删除
x只有左子树xL或只有右子树xR ,则令xL或xR直接成为双亲结点f的子树； 
x即有左子树xL也有右子树xR，在xL中选值最大的代替x，该数据按二叉排序树的性质应在最右边。
 
平衡二叉树：每个结点的平衡因子都为 1、－1、0 的二叉排序树。或者说每个结点的左右子树的高度最多差1的二叉排序树。
 
平衡二叉树的平衡：
 
左调整(新结点插入在左子树上的调整)： 
 
  
LL(插入在结点左子树的左子树上)：旋转前后高度都为h+1
LR(新插入结点在左子树的右子树上)：旋转前后高度仍为h+1
右调整(新结点插入在右子树上进行的调整): 
 
  
RR(插入在的右子树的右子树上)：处理方法和 LL对称
RL(插入在的右子树的左子树上)：处理方法和 LR对称
 
平衡树建立方法：
 
按二叉排序树插入结点
如引起结点平衡因子变为|2|，则确定旋转点，该点是离根最远（或最接近于叶子的点）
确定平衡类型后进行平衡处理，平衡后以平衡点为根的子树高不变
最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。
 
常见的平衡二叉树：
 
红黑树是平衡二叉树，也就是左右子树是平衡的，高度大概相等。这种情况等价于一块完全二叉树的高度，查找的时间复杂度是树的高度，为logn，插入操作的平均时间复杂度为O(logn)，最坏时间复杂度为O(logn) 
  
 
  
节点是红色或黑色。
根是黑色。
所有叶子都是黑色（叶子是NIL节点）。
每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
从任一节点到其每个叶子的所有简单路径 都包含相同数目的黑色节点。
avl树也是自平衡二叉树；红黑树和AVL树查找、插入、删除的时间复杂度相同；包含n个内部结点的红黑树的高度是o(logn); TreeMap 是一个红黑树的实现，能保证插入的值保证排序
STL和linux多使用红黑树作为平衡树的实现： 
 
  
如果插入一个node引起了树的不平衡，AVL和RB-Tree都是最多只需要2次旋转操作，即两者都是O(1)；但是在删除node引起树的不平衡时，最坏情况下，AVL需要维护从被删node到root这条路径上所有node的平衡性，因此需要旋转的量级O(logN)，而RB-Tree最多只需3次旋转，只需要O(1)的复杂度。
其次，AVL的结构相较RB-Tree来说更为平衡，在插入和删除node更容易引起Tree的unbalance，因此在大量数据需要插入或者删除时，AVL需要rebalance的频率会更高。因此，RB-Tree在需要大量插入和删除node的场景下，效率更高。自然，由于AVL高度平衡，因此AVL的search效率更高。
map的实现只是折衷了两者在search、insert以及delete下的效率。总体来说，RB-tree的统计性能是高于AVL的。
 
查找总结
 
既希望较快的查找又便于线性表动态变化的查找方法是哈希法查找。二叉排序树查找，最优二叉树查找，键树查找，哈希法查找是动态查找。分块、顺序、折半、索引顺序查找均为静态。分块法应该是将整个线性表分成若干块进行保存，若动态变化则可以添加在表的尾部（非顺序结构），时间复杂度是O(1)，查找复杂度为O(n)；若每个表内部为顺序结构，则可用二分法将查找时间复杂度降至O(logn)，但同时动态变化复杂度则变成O(n)；顺序法是挨个查找，这种方法最容易实现，不过查找时间复杂度都是O(n)，动态变化时可将保存值放入线性表尾部，则时间复杂度为O(1)；二分法是基于顺序表的一种查找方式，时间复杂度为O(logn)；通过哈希函数将值转化成存放该值的目标地址，O（1）
二叉树的平均查找长度为O(log2n)——O(n).二叉排序树的查找效率与二叉树的高度有关，高度越低，查找效率越高。二叉树的查找成功的平均查找长度ASL不超过二叉树的高度。二叉树的高度与二叉树的形态有关，n个节点的完全二叉树高度最小，高度为[log2n]+1,n个节点的单只二叉树的高度最大，高度为n，此时查找成功的ASL为最大(n+1)/2，因此二叉树的高度范围为[log2n]+1——n.
链式存储不能随机访问，必须是顺序存储
 
B_树的B+树
 
B_树
 
B-树就是B树。m阶B_树满足或空，或为满足下列性质的m叉树：
 
 
树中每个结点最多有m棵子树
根结点在不是叶子时，至少有两棵子树
除根外，所有非终端结点至少有⎡m/2⎤棵子树 
有s个子树的非叶结点具有 n = s-1个关键字，结点的信息组织为:(n,A0,K1,A1,K2,A2 … Kn，An)。这里：n为关键字的个数，ki（i=1,2,…,n)为关键字，且满足Ki小于Ki+1,，Ai(i=0,1,..n)为指向子树的指针。
所有的叶子结点都出现在同一层上，不带信息（可认为外部结点或失败结点）。
关键字集合分布在整颗树中
任何一个关键字出现且只出现在一个结点中
搜索有可能在非叶子结点结束
其搜索性能等价于在关键字全集内做一次二分查找
只适用于随机检索，不适用于顺序检索。
有结点的平衡因子都为零
M阶B-树中含有N个关键字，最大深度为log⎡m/2⎤(n+1)/2+2
 
B_树中结点的插入
 
m代表B_树的阶，插入总发生在最低层
插入后关键字个数小于等于 m-1,完成。
插入后关键字个数等于m,结点分裂，以中点数据为界一分为二，中点数据放到双亲结点中。这样就有可能使得双亲结点的数据个数为m,引起双亲结点的分裂，最坏情况下一直波及到根，引起根的分裂——B_树长高。
 
3阶B_树的插入。每个结点最多3棵子树，2个数据；最少2棵子树，1个数据。所以3阶B_树也称为2-3树。
 
B_树中结点的删除
 
删除发生在最底层 
 
  
被删关键字所在结点中的关键字数目大于等于 m/2 ，直接删除。
删除后结点中数据为⎡m/2⎤-2，而相邻的左（右）兄弟中数据大于⎡m/2⎤-1，此时左（右兄弟）中最大（小）的数据上移到双亲中，双亲中接（靠）在它后（前）面的数据移到被删数据的结点中
其左右兄弟结点中数据都是⎡m/2⎤-1，此时和左（右）兄弟合并，合并时连同双亲中相关的关键字。此时，双亲中少了一项，因此又可能引起双亲的合并，最坏一直到根，使B-树降低一层。
删除不在最底层 
 
  
在大于被删数据中选最小的代替被删数据，问题转换成在最底层的删除
 
B+树
 
在实际的文件系统中，用的是B+树或其变形。有关性质与操作类似与B_树。
 
 
差异：
 
有n棵子树的结点中有n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点。
所有叶子结点中包含全部关键字信息，及对应记录位置信息及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。(而B树的叶子节点并没有包括全部需要查找的信息)
所有非叶子为索引，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B树的非终节点也包含需要查找的有效信息)
非叶最底层顺序联结，这样可以进行顺序查找
 
B+特性
 
所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
不可能在非叶子结点命中
非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层
更适合文件索引系统
B+树插入操作的平均时间复杂度为O(logn)，最坏时间复杂度为O(logn)
 
查找过程
 
在 B+ 树上，既可以进行缩小范围的查找，也可以进行顺序查找；
在进行缩小范围的查找时，不管成功与否，都必须查到叶子结点才能结束；
若在结点内查找时，给定值≤Ki， 则应继续在 Ai 所指子树中进行查找
 
插入和删除的操作：类似于B_树进行，即必要时，也需要进行结点的“分裂”或“合并”。
 
为什么说B+tree比B树更适合实际应用中操作系统的文件索引和数据库索引？
 
B+tree的磁盘读写代价更低 
 
  
B+tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B树就比B+树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。
B+tree的查询效率更加稳定 
 
  
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
 
B树和B+树都是平衡的多叉树。B树和B+树都可用于文件的索引结构。B树和B+树都能有效的支持随机检索。B+树既能索引查找也能顺序查找.
 
哈希表
 
在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样不经过比较，一次存取就能得到元素。 
哈希函数——在记录的关键字与记录的存储位置之间建立的一种对应关系。是从关键字空间到存储位置空间的一种映象。
哈希表——应用哈希函数，由记录的关键字确定记录在表中的位置信息，并将记录根据此信息放入表中，这样构成的表叫哈希表。
Hash查找适合于关键字可能出现的值的集合远远大于实际关键字集合的情形。
更适合查找，不适合频繁更新
Hash表等查找复杂依赖于Hash值算法的有效性，在最好的情况下，hash表查找复杂度为O(1)。只有无冲突的hash_table复杂度才是O(1)。一般是O(c)，c为哈希关键字冲突时查找的平均长度。插入，删除，查找都是O(1)。平均查找长度不随表中结点数目的增加而增加,而是随负载因子的增大而增大
由于冲突的产生，使得哈希表的查找过程仍然是一个给定值与关键字比较的过程。
 
根据抽屉原理，冲突是不可能完全避免的，所以，选择好的散列函数和冲突处理方法：
 
构造一个性能好，冲突少的Hash函数
如何解决冲突
 
常用的哈希函数
 
直接定址法。仅适合于：地址集合的大小 == 关键字集合的大小
数字分析法。对关键字进行分析，取关键字的若干位或其组合作哈希地址。仅适合于：能预先估计出全体关键字的每一位上各种数字出现的频度。
平方取中法。以关键字的平方值的中间几位作为存储地址。
折叠法。将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址。移位叠加/间界叠加。适合于: 关键字的数字位数特别多，且每一位上数字分布大致均匀情况。
除留余数法。取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key%p，p<=m。
随机数法。取关键字的伪随机函数值作哈希地址，即H(key)=random(key)，适于关键字长度不等的情况。
 
冲突解决
 
开放定址法。当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中。即Hi=(H(key)+di) % m，i=1,2,……k(k<=m-1)，H(key)哈希函数，m哈希表长，di增量序列。缺点：删除：只能作标记，不能真正删除；溢出；载因子过大、解决冲突的算法选择不好会发生聚集问题。要求装填因子α较小，故当结点规模较大时会浪费很多空间。 
 
  
线性探测再散列：di=1，2，3，…，m-1
二次探测再散列：di=12,-12,22,-22,…，±k2（k<=m/2）
伪随机探测再散列: di为伪随机数序列
链地址法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针。拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间。一旦发生冲突，在当前位置给单链表增加结点就行。
其他方法：再哈希法、建立公共溢出区
在用拉链法构造的散列表中，删除结点的操作易于实现。拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间。由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况。拉链法解决冲突时，需要使用指针，指示下一个元素的存储位置
开哈希表–链式地址法;闭哈希表–开放地址法.开哈希和闭哈希主要的区别在于，随着哈希表的密集度提高，使用闭哈希时，不仅会与相同哈希值的元素发生冲突，还容易与不同哈希值的元素发生冲突；而开哈希则不受哈希表疏密与否的影响，始终只会与相同哈希值的元素冲突而已。所以在密集度变大的哈希表中查找时，显然开哈希的平均搜索长度不会增长。
设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到Hash表中需要做n*(n-1)/2次线性探测。如果使用二次探测再散列法将这n个关键字存入哈希表，至少要进行n*(n+1)/2次探测
 
Hash查找效率：装填因子=表中记录数/表容量
 
有B+Tree/Hash_Map/STL Map三种数据结构。对于内存中数据，查找性能较好的数据结构是Hash_Map，对于磁盘中数据，查找性能较好的数据结构是B+Tree。Hash操作能根据散列值直接定位数据的存储地址，设计良好的hash表能在常数级时间下找到需要的数据，但是更适合于内存中的查找。B+树是一种是一种树状的数据结构，适合做索引，对磁盘数据来说，索引查找是比较高效的。STL_Map的内部实现是一颗红黑树，但是只是一颗在内存中建立二叉树树，不能用于磁盘操作，而其内存查找性能也比不上Hash查找。
 
内部排序
 
内部排序：全部数据可同时放入内存进行的排序。 
外部排序：文件中数据太多，无法全部调入内存进行的排序。
 
插入类：
 
直接插入排序。最坏情况是数据递减序，数据比较和移动量最大，达到O(n2)，最好是数据是递增序，比较和移动最少为O(n)。趟数是固定的n-1，即使有序，也要依次从第二个元素开始。排序趟数不等于时间复杂度。
折半插入排序 。由于插入第i个元素到r[1]到r[i-1]之间时，前i个数据是有序的，所以可以用折半查找确定插入位置，然后插入。
希尔排序。缩小增量排序。5-3-1。在实际应用中，步长的选取可简化为开始为表长n的一半（n/2），以后每次减半，最后为1。插入的改进，最后一趟已基本有序，比较次数和移动次数相比直接插入最后一趟更少
 
交换类：
 
冒泡排序。O(n2)通常认为冒泡是比较差的，可以加些改进，比如在一趟中无数据的交换，则结束等措施。 
 
  
在数据已基本有序时，冒泡是一个较好的方法
在数据量较少时（15个左右）可以用冒泡
快速排序。 
 
  
时间复杂度。最好情况：每次支点总在中间，O(nlog2n)，平均O(nlog2n)。最坏，数据已是递增或递减，O(n2)。pivotkey的选择越靠近中央，即左右两个子序列长度越接近，排序速度越快。越无序越快。
空间复杂度。需栈空间以实现递归，最坏情况：S(n)=O(n)；一般情况：S(n)=O(log2n)
在序列已是有序的情况下，时间复杂度最高。原因：支点选择不当。改进：随机选取支点或最左、最右、中间三个元素中的值处于中间的作为支点，通常可以避免最坏情况。所以，快速排序在表已基本有序的情况下不合适。
在序列长度已较短时，采用直接插入排序、起泡排序等排序方法。序列的个数通常取10左右。
 
选择类排序：
 
简单选择排序。O(n2)。总比较次数n(n-1)/2。
堆排序。建堆 O(n)，筛选排序O(nlogn)。找出若干个数中最大/最小的前K个数，用堆排序是最好。小根堆中最大的数一定是放在叶子节点上，堆本身是个完全二叉树，完全二叉树的叶子节点的位置大于[n/2]。时间复杂度不会因为待排序序列的有序程度而改变，但是待排序序列的有序程度会影响比较次数。
归并排序。时间：与表长成正比，若一个表表长是m，另一个是n，则时间是O(m+n)。单独一个数组归并，时间：O(nlogn)，空间：O(n)，比较次数介于(nlogn)/2和(nlogn)-n+1，赋值操作的次数是(2nlogn)。归并排序算法比较占用内存，但却是效率高且稳定的排序算法。在外排序中使用。归并的趟数是logn。
基数排序。在一般情况下，每个结点有 d 位关键字，必须执行 t = d次分配和收集操作。分配的代价：O(n)；收集的代价：O(rd) （rd是基数）；总的代价为：O( d ×(n + rd))。适用于以数字和字符串为关键字的情况。
枚举排序，通常也被叫做秩排序，比较计数排序。对每一个要排序的元素，统计小于它的所有元素的个数，从而得到该元素在整个序列中的位置，时间复杂度为O(n2)
 
比较法分类的下界：O(nlogn)
 
排序算法的一些特点：
 
堆排序、冒泡排序、快速排序在每趟排序过程中,都会有一个元素被放置在其最终的位置上。
有字符序列 ｛Q,H,C,Y,P,A,M,S,R,D,F,X｝ ,新序列{F,H,C,D,P,A,M,Q,R,S,Y,X}，是快速排序算法一趟扫描的结果。(拿Q作为分割点,快速排序一轮。二路归并，第一趟排序，得到 n / 2 个长度为 2 的各自有序的子序列，第二趟排序，得到 n / 4 个长度为 4 的各自有序的子序列H Q C Y A P M S D R F X。如果是快速排序的话，第一个元素t将会被放到一个最准确的位置，t前的数均小于t，后面的数均大于t。希尔排序每个小分组内将会是有序的。堆排序，把它构成一颗二叉树的时候，该堆要么就是大根堆，要么就是小根堆，第一趟Y排在最后；冒泡，那么肯定会有数据下沉的动作，第一趟有A在第一位。)
在文件”局部有序”或文件长度较小的情况下,最佳内部排序的方法是直接插入排序。（归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时间复杂度为O(nlog2n)；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，即n-1趟比较的时间复杂度由O(n^2)降至O(n)。在待排序的元素序列基本有序或者每个元素距其最终位置不远也可用插入排序，效率最高的排序方法是插入排序）
排序趟数与序列的原始状态有关的排序方法是优化冒泡和快速排序法。(插入排序和选择排序不管序列的原始状态是什么都要执行n-1趟，优化冒泡和快排不一定。仔细理解排序的次数和比较次数的区别)
不稳定的排序方法：快排，堆排，希尔，选择
要与关键字的初始排列次序无关,那么就是最好、最坏、一般的情况下排序时间复杂度不变, 总共有堆排序,归并排序,选择排序,基数排序
快速排序、Shell 排序、归并排序、直接插入排序的关键码比较次数与记录的初始排列有关。折半插入排序、选择排序无关。(直接插入排序在完全有序的情况下每个元素只需要与他左边的元素比较一次就可以确定他最终的位置；折半插入排序，比较次数是固定的，与初始排序无关；快速排序，初始排序不影响每次划分时的比较次数，都要比较n次，但是初始排序会影响划分次数，所以会影响总的比较次数，但快排平均比较次数最小；归并排序在归并的时候，如果右路最小值比左路最大值还大，那么只需要比较n次，如果右路每个元素分别比左路对应位置的元素大，那么需要比较2*n-1次，所以与初始排序有关)
精俭排序，即一对数字不进行两次和两次以上的比较，插入和归并是“精俭排序”。插入排序，前面是有序的，后面的每一个元素与前面有序的元素比较，比较过的就是有序的了，不会再比较一次。归并每次合并后，内部都是有序的，内部的元素之间不用再比较。选择排序，每次在后面的元素中找到最小的，找最小元素的过程是在没有排好序的那部分进行，所有肯定会比较多次。堆排序也需比较多次。
 
外部排序
 
生成合并段（run）：读入文件的部分记录到内存－>在内存中进行内部排序－>将排好序的这些记录写入外存，形成合并段－>再读入该文件的下面的记录，往复进行，直至文件中的记录全部形成合并段为止。
外部合并：将上一阶段生成的合并段调入内存，进行合并，直至最后形成一个有序的文件。
外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。外部排序最常用的算法是多路归并排序，即将原文件分解成多个能够一次性装入内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行多路归并排序
不管初始序列是否有序, 冒泡、选择排序时间复杂度是O(n^2),归并、堆排序时间复杂度是O(nlogn）
外部排序的总时间 = 内部排序（产出初始归并段）所需时间 + 外存信息读取时间 + 内部归并所需的时间
外排中使用置换选择排序的目的,是为了增加初始归并段的长度。减少外存读写次数需要减小归并趟数
根据内存容量设若干个输入缓冲区和一个输出缓冲区。若采用二路归并，用两个输入缓冲。
归并的方法类似于归并排序的归并算法。增加的是对缓冲的监视，对于输入，一旦缓冲空，要到相应文件读后续数据，对于输出缓冲，一旦缓冲满，要将缓冲内容写到文件中去。
外排序和内排序不只是考虑内外排序算法的性能，还要考虑IO数据交换效率的问题，内存存取速度远远高于外存。影响外排序的时间因素主要是内存与外设交换信息的总次数
 
有效的算法设计
 
贪心法。Dijkstra的最短路径(时间复杂度O(n2))；Prim求最小生成树邻接表存储时是O(n+e),图O(n2)；关键路径及关键活动的求法。
回溯法
分支限界法
分治法。分割、求解、合并。二分查找、归并排序、快速排序。
动态规划。Floyd-Warshall算法求解图中所有点对之间最短路径时间复杂度为O(n3)
 
动态规划解题的方法是一种高效率的方法，其时间复杂度通常为O(n2)，O(n3)等，可以解决相当大的信息量。（数塔在n<=100层时，可以在很短的时间内得到问题解）
 
适用的原则：原则为优化原则，即整体优化可以分解为若干个局部优化。
动态规划比穷举法具有较少的计算次数
递归算法需要很大的栈空间，而动态规划不需要栈空间
 
贪心和动态规划的差别：
 
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
在动态规划算法中，每步所作的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后，才能作出选择。而在贪心算法中，仅在当前状态下作出最好选择，即局部最优选择。然后再去解作出这个选择后产生的相应的子问题。
贪心算法所作的贪心选择可以依赖于以往所作过的选择，但决不依赖于将来所作的选择，也不依赖于子问题的解。正是由于这种差别，动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为一个规模更小的子问题。 
 
P问题
 
P问题，如果它可以通过运行多项式次(即运行时间至多是输入量大小的多项式函数的一种算法获得解决），可以找到一个能在多项式的时间里解决它的算法。—-确定性问题
NP问题，虽然可以用计算机求解，但是对于任意常数k，它们不能在O(nk)时间内得到解答，可以在多项式的时间里验证一个解的问题。所有的P类问题都是NP问题。
NP完全问题，知道有效的非确定性算法，但是不知道是否存在有效的确定性算法，同时，不能证明这些问题中的任何一个不存在有效的确定性算法。这类问题称为NP完全问题。

引入
 
我在上一篇博文中讲了epoll源码的剖析，你是不是看的有点懵呢，反正我是有点，接下来我就以流程图的形式梳理一下epoll源码的结构。
当然，这篇博文是建立在上一篇博文的基础上，若你还没看过epoll源码，那么我建议你最好还是看一下，请点击【Linux深入】epoll源码剖析 
 
接下来我就以流程图的形式介绍一下函数的调用过程。
 
整体的数据结构图
 
 
注：图中黄色和绿色方框表示链表关系，而粉色代表等待队列。
 
主要的函数调用图
 
1.epoll_create()
 
 
分析：
 
epoll_create()函数没有什么实际作用，它仅有的一个size参数没有，它的主要功能是通过epoll_create1()函数来完成的
epoll_create1()函数通过ep_alloc生成一个eventpoll对象，并初始化eventpoll的三个等待队列，wait，poll_wait以及rdlist （ready的fd list）。同时还会初始化被监视fs的rbtree 根节点。
epoll_create1()在调用ep_alloc通过anon_inode_getfd创建一个名字为“[eventpoll]”的eventpollfs文件描述符号并将file->private_data指定为指向前面生成的eventpoll。这样就将eventpoll和文件id关联。最后返回文件描述符id
 
2.epoll_ctl()
 
 
epoll_ctl函数
 
  
通过epoll_create生成一个eventpoll后，可以通过epoll_ctl提供的相关操作对eventpoll进行ADD，MOD，DEL操作。
epoll_ctl首先通过epfd的private_data域获取需要操作的eventpoll，然后通过ep_find确认需要操作的fd是否已经在被监视的红黑树中（eventpoll->rbr）。然后根据op的类型分别作ADD（ep_insert），MOD（ep_modify），DEL（ep_remove）操作。
ep_insert()
 
  
从slub中分配一个epitem的对象epitem。并初始化epitem的三个list头指针，rdllink（指向eventpoll的rdlist），fllist指向（struct file的f_ep_links），pwqlist（指向包含此epitem的所有poll wait queue）。将epitem的ep指针，指向传入的eventpoll，
通过传入参数event对ep内部变量event赋值。然后通过ep_set_ffd将目标文件和epitem关联。这样epitem本身就完成了和eventpoll以及被监视文件的关联。下面还需要做两个动作：将epitem插入目标文件的polllist并注册回调函数；将epitem插入eventpoll的rbtree。
Poll()函数是系统函数，一般由设备驱动提供。
poll_wait()函数调用 ep_ptable_queue_proc()函数
ep_ptable_queue_proc()主要功能是使用等待队列实现epitem和callback函数的关联。然后通过目标文件的poll函数调用callback函数。
ep_poll_callback()函数
 
  
当fd状态改变时（感兴趣事件），调用该函数，
首先会把文件描述符epitem 放到eventpoll 的rdllist中
然后调用wake_up函数唤醒epitem上wq的进程。这样就可以返回到epoll_wait的调用者，将他唤醒。
 
3.epoll_wait()
 
 
epoll_wait()函数
 
  
首先会检测传入参数的合法性；events指向的空间是否可写；epfd是否合法等。参数合法性检测都通过后，将通过epfd获取锁依赖的struct file，
然后通过file->private_data获取eventpoll。获取epoll后调用ep_poll函数完成真正的epoll_wait工作。
ep_poll()函数
 
  
首先根据timeout的值判断是否是无限等待，如果不是将timeout（ms）转换为jiffs。 
然后判断eventpoll的rdlist是否为空，如果为空，那么将current进程通过一个waitquene entry加入eventpoll的waitlist（wq）。如果rdlist非空，那么通过ep_send_events将event转发到用户空间。
ep_send_events函数调用ep_scan_ready_list对ready_list进行扫描
ep_scan_ready_list对ready_list进行扫描。将所有的epitem都转移到了txlist上, 而rdllist被清空了。然后调用ep_send_events_proc()函数。
ep_send_events_proc扫描rdlist从头上面拿出epitem，然后调用ep_eventpoll_poll函数，完成转发。 
 先把就绪事件链表转移到中间链表,然后挨个遍历拷贝到用户空间,并且挨个判断其是否为水平触发,是的话再次插入到就绪链表
 
4.全部函数的的调用关系图
 
 
注：忽略蓝色竖线，手当时抖了一下，多加了一条线。
 

 
 本人才疏学浅，若有错，请指出，谢谢！ 
 如果你有更好的建议，可以留言我们一起讨论，共同进步！ 
 衷心的感谢您能耐心的读完本篇博文！
 
 
 
参考链接： 
 1.epoll实现——嵌入式Linux 
 2.EPOLL内核源代码实现原理分析——it165