整理磁盘时发现考研408时自己的笔记

第一章 绪论

1.1 数据结构的基本概念

• 数据：信息的载体
• 数据元素：数据的基本单位。一个数据元素可由若干个数据项组成
• 数据对象：具有相同性质的数据元素的集合
• 数据类型：是一个值的集合和定义在此集合上一组操作的总称。原子类型：值不可再分的数据类型；结构类型：值可以再分解的若干类型；抽象数据类型：抽象数据组织和与之相关的操作。
• 抽象数据类型：ADT，指一个数学模型以及定义在该模型上的一组操作。
• 数据结构=逻辑结构+存储结构+数据的运算

1.1.2 数据结构的三要素

1. 逻辑结构：指数据元素之间的逻辑关系，如集合、线性结构、树形结构、图状结构或网状结构
2. 数据的存储结构：指数据结构在计算机中的表示，也称物理结构。包括顺序存储、链式存储、索引存储和散列存储。
3. 数据的运算：施加在数据上的运算包括运算的定义和实现。

第2章 线性表

2.1 线性表的定义和基本操作

线性表是具有相同数据类型的n个数据元素的有限序列。 逻辑上，每个元素有且只有一个直接前驱，有且只有一个直接后继（表头表尾元素例外）

使用顺序存储的时候即为顺序表。 使用链式存储即为链表。

2.2 线性表的顺序表示

线性表的顺序存储又称为顺序表，是一组地址连续的存储单元。特点是表中元素的逻辑顺序与物理顺序相同。 PS：动态分配并不是链式存储，同样属于顺序存储结构，只是分配的空间大小可以在运行时决定。 最主要的特点是随机访问，而且逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量的元素。

• 插入，平均时间复杂度O(n)
• 删除，平均时间复杂度O(n)
• 按值顺序查找O(n)，二分可以到O(logn)

错题：线性表的顺序存储结构是一种顺序存取的存储结构。 这个是错误的，是随机存取的存储结构。顺序存取是一种读写方式，不是存储方式，有别于顺序存储。 PPS：表的元素从1开始计数，C中的数组从0开始计算。

题目： [2010真题]1. 设将n(n>1)个整数存放到1维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0<p<n)个位置，即将R中的数据由(X0,X1,…,Xn-1)变换为(Xp,Xp+1,…,Xn-1,X0,X1,…,Xp-1)。要求： (1)给出算法的基本设计思想 (2)根据设计思想，采用C或C++或java语言描述算法，关键之处给出注释 (3)说明你所设计算法的时间复杂度和空间复杂度 [2011年真题]2.一个长度为L（L>=1）的升序序列S，处在L/2个位置的数被称为中位数。例如，若序列S1=（11,13,15,17,19），则S1的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=(2,4,6,8,20)，则S1和S2的中位数是11。现在由两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求： (1)给出算法的基本思想 (2)根据设计思想，采用C或C++或java语言描述算法，关键之处给出注释 (3)说明你所设计算法的时间复杂度和空间复杂度

[2013年真题]3.已知一个整数序列A=(a0,a1,…,an-1),其中0<=ai<n(0<i<n)。若存在ap1=ap2=…=apm=x且m>n/2(0<=pk<n,1<=k<=m)，则称x为A的主元素。例如A=(0,5,5,3,5,7,5,5)，则5为主元素；又如A=(0,5,5,3,5,1,5,7)，则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出-1。要求： (1)给出算法的基本设计思想 (2)根据设计思想，采用C或C++或java语言描述算法，关键之处给出注释 (3)说明你所设计算法的时间复杂度和空间复杂度

注释有感： 读注释的效果应当同读伪代码的效果一样 如果代码的内容无法直观表述，就需要写注释。 题目答案： 1.(1)可以将这个问题看作是把数组ab转换成数组ba（a代表前p个元素，b代表数组余下的n-p个元素），先将a逆置得到a-1b，再将b逆置，最后将ab逆置。 如对abcdefgh左移3个单位 Reverse(0,p-1)，得到cbadefgh Reverse(p,n-1)，得到cbahgfed Reverse(0,n-1)，得到defghabc (2)使用C语言描述算法

void Reverse(int R[],int from,int to){
    int i,temp;
    for(i=0;i<(to-from+1)/2;i++)
    {temp=R[from+i];R[from+i]=R[to-1];R[to-1]=temp}
}//Reverse
void Converse(int R[],int n,int p)
{
    Reverse(0,p-1);
    Reverse(p,n-1);
    Reverse(0,n-1);
}

(3)上述三个Reverse的时间复杂度分别为O(p/2),O((n-p)/2)和O(n/2)，故所设计的算法的时间复杂度是O(n)，空间复杂度是O(1) 另外，可以使用大小为p的辅助数组，先将左边p个元素导入，再将n-p个元素左移，再放回去。时间复杂度O(n)，空间复杂度O(p) 2.(1)算法的基本思想如下： 分别求两个序列的中位数a和b， 若a=b，则算法结束 若a<b，则舍弃A序列小的一半，B序列大的一半，要求两个序列舍弃的长度相等 若a>b，则舍弃A序列大的一半，B序列小的一半，要求两个序列舍弃的长度相等 在保留的升序序列中，重复上述过程直到只含一个元素，较小者即为所求的中位数 (2)代码：

int M_Search(int A[],int B[],int n){
    int s1=0,d1=n-1,m1,s2=0,d2=n-1,m2;
    //分别表示序列A和B的首位数、末位数和中位数
    while(s1!=d1||s2!=d2){
        m1=(s1+d1)/2;
        m2=(s2+d2)/2;
        if(A[m1]==B[m2])
            return A[m1];//满足条件1
        if(A[m1]<B[m2]){//满足条件2
            if((s1+d1)%2==0){//若元素个数位奇数
                s1=m1;//舍弃A中间点以前的部分且保留中间点
                d2=m2;//舍弃B中间点以后的部分且保留中间点
            }
            else{
                s1=m1+1;//舍弃A中间点以前及中间点部分
                d2=m2;//舍弃B中间点以后部分且保留中间点
            }
        }
        else{//满足条件3
            if((s2+d2)%2==0)//若元素个数为奇数
            {
                d1=m1;//舍弃A中间点以后的部分且保留中间点
                s2=m2;//舍弃B中间点以前的部分且保留中间点
            }
            else{//若元素个数为偶数
                d1=m1;//舍弃A中间点以后部分且保留中间点
                s2=m2+1;//舍弃B中间点及中间点以前的部分
            }
        }

    }
    return A[s1]<B[s2]?A[s1]:B[s2];
}

(3)算法的时间复杂度为O(log2n)，空间复杂度为O(1) 3.（1）给出算法的基本设计思想： 算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num。然后重新计数，确认Num是否是主元素。 算法分为以下两步： a.选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数Num保存到c中，记录Num的出现次数为1；若遇到的下一个整数仍等于Num，则计数加1，否则计数减1；当计数减到0时，将遇到的下一个整数保存到c中，计数重新记为1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。 b.判断c中元素是否是真正的主元素：再次扫描该数组，统计c中元素出现的次数，若大于n/2，则为主元素；否则，序列中不存在主元素。 (2)算法实现：

int Majority(int A[],int n){
    int i,c,count=1;//c用来保存候选主元素，count用来计数
    c=A[0];//初始时设置A[0]为候补主元素
    for(i=1;i<n;i++){
        if(A[i]==c)
            count++;//对A中的候选主元素计数
        else{
            if(count>0)//处理不是候选主元素的情况
                count--;
            else{//更换候选主元素，重新计数
                c=A[i];
                count=1;
            }
        }
    }
    if(count>0){
        for(i=count=0;i<n;i++){//统计候选主元素的实际出现次数
            if(A[i]==c)
                count++;
        }
    if(count>n/2)    return c;//确认候选主元素
    else    return -1;//不存在主元素
    }
}

(3)实现程序的时间复杂度为O(n)，空间复杂度为O(1) PS：对于统考算法题，去花费大量时间思考最优解法是得不偿失的。

2.2 线性表的链式表示

单链表

结点描述：

typedef struct LNode{
    ElemType data;//数据域
    struct LNode *next;    //指针域
}Lnode,*LinkList;

通常使用头指针来标识一个单链表，第一个结点称为头结点。

2.3.2 单链表上的基本操作

1. 采用头插法建立单链表：即每次创建一个空结点链接到头指针指向的结点，然后头指针指向新创建的结点。时间复杂度O(n)
2. 采用尾插法建立单链表：需要使用一个尾指针，每次在最后新建立一个结点然后指向它，更新尾指针。时间复杂度O(n) 3.按序号查找结点值。需要遍历链表，时间复杂度O(n) 4.按值查找表结点。同样需要遍历，时间复杂度O(n) 5.插入结点操作：将值为x的结点插入到单链表第i个位置上，主要开销在查找i-1个元素上，时间复杂度为O(n)。若给定插入元素，时间复杂度为O(1) 6.删除：O(1) 7.求表长：O(n)

2.3.2 双链表

结点类型：

typedef struct DNode{
    ElemType data;
    struct DNode *prior,*next;
}DNode, *DLinkList;

插入、删除结点的时间为O(1)。（虽然查找依旧是O(n)）

2.3.4 循环链表

循环链表中最后一个结点的指针不是NULL而是指向头结点。

2.3.5 静态链表

使用数组描述链式结构。

#define MaxSize 50
typedef struct{
    ElemType data;//存储数据元素
    int next;//下一个数组元素的下标
}

以next=-1作为结束，与动态链表相同，只是不用修改指针。

错题：1.单链表中，增加一个头结点的目的时为了方便运算的实现。主要好处是：第一，有头结点后，插入和删除数据元素的算法统一了，不再需要判断是否在第一个元素之前插入或删除第一个元素；第二，不论链表是否为空，其头指针是指向头结点的非空指针，链表的头指针不变，因此空表和非空表的处理也就统一了。 2. 带头结点的双循环链表为空的条件是：L->prior=L&&L->next=L

编程题： [2009]1.已知一个带表头结点的单链表，结点结构为[data|link]。假设该链表只给出了头指针list，在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1,；否则，只返回0，请问： (1)描述该算法的基本设计思想 (2)描述算法的详细设计步骤 (3)根据设计思想和实现步骤，采用程序设计语言实现算法，关键之处请给出简要注释。

1.（1）程序设计基本思想如下： 问题的关键是设计一个尽可能高效的算法，通过链表的一遍遍历，找到倒数第k个结点的位置。算法的基本设计思想是：定义两个指针变量p和q，初始时均指向头结点的下一个结点（链表的第一个结点），p指针移动到第k个结点时，q指针开始与p指针同步移动；当p指针移动到最后一个结点时，q指针所指示结点为倒数第k个结点。以上过程对链表仅进行一次扫描。 （2）算法的详细实现步骤如下：

1. count=0，p和q指向链表表头结点的下一个结点
2. 若p为空，转5
3. 若count=k，则q指向下一个结点；否则，count=count+1
4. p指向下一个结点，转2
5. 若count=k，则查找成果，输出data域的值，返回1；否则，说明k值超过了线性表的长度，查找失败，返回0
6. 算法结束 （3）算法实现

typedef int ElemType;//链表数据的类型定义
typedef struct LNode{//链表结点的结构定义
    ElemType data;//结点数据
    struct LNode *link;//结点链接指针
}
int Search_k(LinkList list,int k){
//查找链表list倒数第k个结点，并输出该结点data域的值
    LNode *p=list->link,*q=list->link;//指针p、q指示第一个结点
    int count = 0;
    while(p!=NULL){    //遍历链表直到最后一个结点
        if (count<k) count++;//计数，若count<k只移动p
        else q=q->link;
        p = p->link;//之后再让p、q同步移动
    }
    if(count<k)
        return 0;//查找失败返回0
    else{//否则打印并返回1
        printf("%d",q->data);
        return 1;
    }
}//Search_k

第3章 栈和队列

3.1 栈

栈：只允许一端进行插入和删除的线性表

3.1.2 栈的顺序存储结构

1. 顺序栈 栈的顺序存储称为顺序栈，它是利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针指示当前栈顶的位置。 顺序存储类型描述：

#define MaxSize 50
typedef struct{
    Elemtype data[MaxSize];
    int top;
}SqStack;

2. 链式栈 采用链式存储的栈称为链栈，优点是多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况，通常使用单链表实现。

typedef struct Linknode{
    ElemType data;
    struct Linknode *next;
}*LiStack;

3.2 队列

3.2.1 队列的基本概念

队列是一种操作受限制的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。 操作特性是FIFO，故又称为先进先出的线性表。

3.2.2 队列的顺序存储结构

分配一块连续的存储单元存放队列中的元素，并附设两个指针front和rear分别指示队头和队尾元素的位置。 队列的顺序存储类型描述

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int front,rear;
}

会出现假溢出，即data数组中仍然有存放元素的空间，但是仍然溢出了。

循环队列：将顺序队列看作是一个环状的空间 入队时少用一个队列单元

• 队满的条件：(Q.rear+1)%MaxSize==Q.front
• 队空条件为：Q.front==Q.rear
• 队列中元素的个数：(Q.rear-Q.front+MaxSize)%MaxSize

后者增设一个表示元素个数的数据成员，或者增设一个tag数据成员。

3.2.3 队列的链式存储结构

可以描述为

typedef struct{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct{
    LinkNode *font,*rear;
}LinkQueue;

3.2.4 双端队列

允许两端都可以进行入队和出队操作的队列

3.3 栈和队列的应用

括号匹配 表达式求值（后缀） 递归 二叉树层次遍历

3.4 特殊矩阵的压缩存储

压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。其目的时为了节省存储空间 特殊矩阵：指具有许多相同矩阵元素或令元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。常见的特殊矩阵有对称矩阵、上/下三角矩阵、对角矩阵等。

1. 对称矩阵：只存放对角线和下三角区的元素 元素下标之间的对应关系： i行j列元素在数组中的下标是k

• i>=j（下三角区和主对角线元素）时：k=i(i-1)/2+j-1
• i<j（上三角区元素aij=aji）时，k=j(j-1)/2+i-1

2. 三角矩阵 上三角全部为0时，下三角区和主对角线元素仍如上，上三角指向常数0.
3. 三对角矩阵 k=2i+j-3

3.4.4 稀疏矩阵

稀疏矩阵可以转为表，这时候会失去随机存储特性。

第4章 树与二叉树

4.1 树的基本概念

任何一棵非空树应该满足：

1. 有且仅有一个特定的称为根的结点。
2. 当N>1时，其余结点可分为m个互不相交的有限集合T1,T2,…,Tm，其中每一个集合本身又是一棵树，并且称为根节点的子树。 树是一种逻辑结构

树中两个结点之间的路径是由两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过边的个数。

树的性质：

1. 树中的结点数=所有结点的度数+1
2. 度为m的树中第i层上至多有m^(i-1)个结点
3. 高度为h的m叉树至多有(m^h-1)/(m-1)个结点
4. 具有n个结点的m叉树的最小高度为floor(logm(n(m-1)+1))

4.2 二叉树的概念

• 满二叉树：叶子结点集中在二叉树的最下一层，并且除叶子结点之外的每个结点的度数都为2.
• 完全二叉树：每一个结点与满二叉树同样编号的结点一一对应。
• 二叉排序树
• 平衡二叉树

二叉树的性质：

1. 非空二叉树，N0=N2+1(N0+N1+N2=N1+2N2+1) …

4.2.2 二叉树的存储结构

1. 顺序存储结构：自上而下，自左而右的存储。一般来说，完全二叉树和满二叉树采用顺序存储比较合适，可以直接映射。
2. 链式存储结构：二叉链表包含三个域，数据域、左指针域和右指针域

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

4.3 二叉树的遍历和线索二叉树

• 先序遍历：根左右
• 中序遍历：左根右
• 后序遍历：左右根 可以借助栈将二叉树的递归遍历算法转变为非递归算法（栈+指针）

层次遍历：需要使用队列，依次将孩子结点加入队列中

由二叉树的先序遍历和中序遍历可以唯一确定一棵二叉树。同理，二叉树的后序遍历和中序遍历也可以唯一确定一棵二叉树。 二叉树的层序序列和中序序列也可以确定一棵二叉树。只有先序序列+后序序列无法确定一棵二叉树。

4.3.2 线索二叉树

线索二叉树的实质是对一个非线性结构进行线性化操作，使在这个访问序列中每一个结点都有一个直接前驱和直接后继。 引入线索二叉树的目的是加快查找结点前驱和后继的速度。 在二叉树线索化时，通常规定：若无左子树，令lchild指向其前驱结点；若无右子树，令rchild指向其后继结点。同时还需要增加两个标识域来表明当前指针域所指向的对象是指向左（右）子结点还是直接前驱（后继）

线索二叉树的存储结构：

typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;
}ThreadNode,*ThreadTree;

以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表。其中指向结点前驱和后继的指针，叫做线索。加上线索的二叉树叫做线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。

线索二叉树的构造：对二叉树的线索化，实质上就是遍历一次二叉树，在遍历过程中检查当前结点左、右指针域是否为空，若为空，则将他们改为指向前驱或后继结点的线索。

算法题： [2014年]1.二叉树的带权路径长度（WPL）是二叉树中所有叶节点的带权路径长度之和，给定一棵二叉树T，采用二叉链表存储，结点结构为(left,weight,right)。其中叶节点的weight域保存该结点的非负权值。设root为指向T的根结点的指针，请设计求T的WPL的算法，要求： (1)给出算法的基本设计思想 a.基于先序递归遍历的算法思想使用一个static变量记录wpl，把每个结点的深度作为递归函数的一个参数传递，算法步骤如下：（标准答案如下，我个人更倾向于将wpl值作为函数返回值逐层返回）

• 若该结点是叶结点，变量wpl加上该结点的深度与权值之积。
• 若该结点是非叶结点，那么若左子树不为空，对左子树调用递归算法；若右子树不为空，对右子树调用递归算法，深度参数均为本结点的深度参数加1；
• 最后返回计算出的wpl b. 基于层次遍历的算法思想是使用队列进行层次遍历，并记录当前的层数，
• 当遍历到叶节点时，累计wpl；
• 当遍历到非叶结点的时候，把该结点的子树加入队列；
• 当某结点为该层的最后一个结点时，层数自增1；
• 队列空时遍历结束，返回wpl (2)二叉树结点的数据类型定义如下：

typedef struct BiTNode{
    int weight;
    struct BiTNode *lchild,*rchild;
}

(3)算法的代码如下 a. 基于先序遍历的算法

int WPL(BiTree root){
    return wpl_PreOrder(root,0);
}
int wpl_PreOrder(BiTree root,int deep){
    static int wpl=0;//定义一个static变量存储wpl
    if(root->lchild==NULL&&root->rchild==NULL)//若为叶节点，累积wpl
        wpl+=deep*root->weight;
    if(root->lchild!=NULL)//若左子树不空，对左子树递归遍历
        wpl_PreOrder(root->lchild,deep+1);
    if(root->rchild!=NULL)//若右子树不空，对右子树递归遍历
        wpl_PreOrder(root->rchild,deep+1);
    return wpl;
}

b.基于层次遍历的算法

#define MaxSize 100//设置队列的最大容量
int wpl_LevelOrder(BiTree root){
    BiTree q[MaxSize];          //声明队列，end1为头指针，end2为尾指针
    int end1,end2;              //队列最多容纳MaxSize-1个元素
    end1=end2=0;                //头指针指向队头元素，尾指针指向队尾的后一个元素
    int wpl=0,deep=0;           //初始化wpl和深度
    BiTree lastNode;            //lastNode用来记录当前层的最后一个结点
    BiTree newlastNode;         //newlastNode用来记录下一个层的最后一个结点
    lastNode=root;              //lastNode初始化为根节点
    newlastNode=NULL;           //newlastNode初始化为空
    q[end2++]=root;             //根节点入队
    while(end1!=end2){          //层次遍历，若队列不空则循环
        BiTree t=q[end1++];     //拿出队列中的头一个元素
        if(t->lchild==NULL&&t->rchild==NULL){
            wpl+=deep*t->weight;
        }                       //若为叶节点，统计wpl
        if(t->lchild!=NULL){    //若非叶节点，把左节点入队
            q[end2++]=t->lchild;
            newlastNode=t->lchild;
        }                       //并设下一层的最后一个结点为该结点的左结点
        if(t->rchild!=NULL){    //处理叶节点
            q[end2++]=t->rchild;
            newlastNode=t->rchild;
        }
        if(t==lastNode){        //若该结点为本层最后一个结点，更新lastNode
            lastNode=newlastNode;
            deep+=1;            //层数加1
        }
    }
    return wpl;                 //返回wpl
}

c.非递归的后序遍历。非递归遍历都需要栈，而后序遍历需要额外保存信息

typedef struct{
    BTNode *p;//p是二叉树的结点的指针
    int rvisited; //revisited=1代表p所指向的结点的右结点已被访问过
}SNode; //栈中的结点定义

typedef struct{
    SNode Elem[maxsize];
    int top;
}SqStack;//栈结构体

void PostOrder2(BiTree T){
    SNode sn;
    BTNode *pt=T;
    InitStack(S);//从根节点开始，往左下方走，将路径上的每一个结点入栈
    while(T){
        Push(pt,0);//Push到栈中的两个信息，一个是结点指针，一个是其右结点是否被访问过
        pt=pt->lchild;
    }
    while(!S.IsEmpty()){//只要S栈非空
        sn.s.getTop();//sn是栈顶结点
        if(sn.p->rchild==NULL||sn.rvisited){
            Pop(S,pt);
            visit(pt);
        }
        else{//若它的右孩子存在且rvisited为0，处理其右孩子
            sn.rvisited=1;//往左下方走到尽头，将路径上所有元素入栈
            pt=sn.p->rchild;
            while(pt!=NULL){
                Push(S,pt,0);
                pt=pt->lchild;
            }
        }
    }
}

4.4 树、森林

数的存储结构：可以使用顺序存储结构或链式存储结构

1. 双亲表示法：使用连续空间来存储每个结点，每个结点带上自己双亲在数组中的位置。

typedef struct{
    ElemType data;
    int parent;
}PTNode;
typedef struct{
    PTNode nodes[MAX_TREE_SIZE];
    int n;
}PTree;

2. 孩子表示法：将每个结点的孩子结点都用单链表连接起来形成一个线性结构。
3. 孩子兄弟表示法：使每个结点包含三部分内容：结点值、指向结点第一个孩子结点的指针和指向结点下一个兄弟结点的指针

4.4.2 树、森林与二叉树的转换

• 树转换为二叉树：每个结点左指针指向它的第一个孩子结点，右指针指向它在树中的相邻兄弟结点，表示为“左孩子右兄弟”。（因此由树转换而来的二叉树的根节点没有右子树）
• 森林转换为二叉树的规则类似，不过将第一棵树的根作为转换后二叉树的根，其余根节点在右子树上排开（就像同层）
• 二叉树转换为森林：二叉树根及其左子树为第一棵树的二叉树形式，二叉树根的右子树为第二棵，右子树的右子树为第三棵，以此类推。然后用左孩子右兄弟逆运算。二叉树转换为树或森林是唯一的。

4.4.3 树和森林的遍历

• 先根遍历：先访问根节点，再按从左到右的顺序遍历根节点的每一棵子树。（访问顺序与访问对应二叉树的先序遍历一样）
• 后根遍历：先按从左到右的顺序遍历根节点的每一棵子树，之后再访问根节点。（访问顺序与访问对应二叉树的中序遍历一样）

森林的遍历：

• 先序遍历森林：先访问第一棵树的根节点，遍历第一棵树根节点的子树森林，再遍历除了第一棵树之后剩下的树构成的森林。
• 中序遍历森林：先遍历森林中第一棵树根节点的子树森林，再访问第一棵树的根节点，再中序遍历除了第一棵树之后剩余的树构成的森林。

树的应用——并查集

错题：

1. 将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v不可能是这个关系：u的父结点与v的父结点是兄弟关系。

4.5 树与二叉树的应用

4.5.1 二叉排序树

BST左子树非空，则左子树上所有点小于根节点的值；右子树非空，则右子树上所有点大于根节点的值。 查找、插入略 构造：依次输入数据元素，并将它们插入到二叉排序树上适当的位置。 删除（较复杂）：删除结点必须维护二叉排序树的性质

1. 如果被删除结点是叶节点，则直接删除
2. 若结点z只有一棵左子树或右子树，则让z的子树称为z父结点的子树，替代z的位置。
3. 若z有左、右两棵子树，则令z的直接后继（或直接前驱）替代（左子树中最右的，或者右子树中最左的），并将直接后继删除，转换成第一或第二种情况。

效率分析

显然，对于高度为H的二叉树，插入和删除的运行时间都是O(H)，但如果二叉树在最坏的情况，会退化成链表，这时性能会指数增加。 二叉树上的查找与二分查找的性能接近。但是二分查找的判定树是唯一的，二叉排序树是不唯一的，相同的关键字其插入顺序不同可能生成不同的二叉排序树。

4.5.2 平衡二叉树AVL

为了避免二叉树的高度增长过快，规定在插入和删除二叉树结点的时候，保证任意结点的左、右子树高度的绝对值差不超过1。 平衡因子=左子树高度-右子树高度，显然只能取-1、0、1.

平衡二叉树的插入：插入结点后，要检查其插入路径上的结点是否因为这次操作而导致了不平衡。每次调整的对象都是最小不平衡树，即在插入路径上离插入结点最近的平衡因子的绝对值大于1的结点作为根的子树

1. LL平衡旋转（右单旋转）：A的左孩子的左子树上插入了一个新的结点导致失衡。这时候向右旋转，B作为A的左孩子变为根节点，A变为B的右孩子，B的右子树变成A的左子树。
2. RR平衡旋转（左单旋转）：A的右孩子的右子树上插入了一个新的结点导致失衡。这时候向左旋转，B作为A的右孩子变为根节点，A变为B的左孩子，B的左子树变为A的右子树。
3. LR平衡旋转（先左后右双旋转）：A的左孩子的右子树上插入了一个新的结点导致失衡，进行两次旋转操作。A为根结点，B为A的左孩子，C为B的右孩子。将C作为根节点，B为C的左孩子，A为C的右孩子。C的左子树变为B的右子树，C的右子树变为A的左子树。
4. RL平衡旋转（先右后左双旋转）：A的右孩子的左子树上插入了一个新的结点导致失衡。A为根节点，B为A的右子树，C为B的左子树。将C作为根节点，A为C的左子树，B为C的右子树，C的左子树为A的右子树，C的右子树为B的左子树。

删除相同 查找为log2n

4.5.3 哈夫曼树和哈夫曼编码

哈夫曼树的带权路径长度最小

构造

1. 对于给定的N棵仅含有一个结点的二叉树，构成森林
2. 构造一个新结点，选取森林中权值最小的两个结点作为左右子树，更新结点为左右子树权值之和。
3. 重复，直到只剩下一棵树 特点：
4. 每个初始结点都成为了叶节点，且权值越小的点路径长度越大。
5. 节点总数2N-1
6. 不存在度为1的点。

前缀编码：如果没有一个编码是另外一个编码的前缀，则称这样的编码为前缀编码。

第5章 图

5.1 图的基本概念

图G由顶点集V和边集E组成。|V|表示图G中顶点的个数，也称为图G的阶 表可以是空表，树可以是空树，但是图不可以是空图，即图中不能一个顶点都没有。图中至少要有一个点，但是边集可以为空。

• 简单图：图中没有重复边，不存在顶点到自身的边，称为简单图
• 多重图：两个结点之间边数多于一条，又允许顶点通过同一条边和自己关联。
• 完全图：无向图中任意两个点之间存在边，共有n(n-1)/2条边；有向图中任意两个顶点之间存在方向相反的两条弧，称为有向完全图。
• 连通图：图中任意两个顶点是连通的，称为连通图。
• 强连通图：有向图中，任意两个顶点之间存在双向路径，称为强连通图。
• 稀疏图：|E|<|V|*log|V|时，看作稀疏图，反之则是稠密图。
• 简单路径：在路径序列中，顶点不重复出现的路径称为简单路径。
• 回路：第一个顶点和最后一个顶点相同的路径称为回路或环；（如果一个图有n个顶点，大于n-1条边，则一定有环）除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路叫做简单回路。
• 度指的是以该顶点为一个端点的边的数目。对于有向图，度=入度+出度。

5.2 图的存储及基本操作

5.2.1 邻接矩阵法

#define MaxVertexNum 100//顶点数目的最大值
typedef char VertexType;//顶点的数据类型
typedef int EdgeType;//带权图中边上权值的数据类型
typedef struct{
    VertexType Vex[MaxVertexNum];//顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵，边表
    int vexnum,arcnum;//图的当前顶点数和弧数
}MGraph;

特点：

1. 无向图的邻接矩阵是对称的，所以实际只需要存储上/下三角矩阵的元素
2. 对于无向图，第i行非零元素的个数正好是第i个结点的度。
3. 对于有向图，入度和出度可以根据第i行计算
4. 邻接矩阵A，A^n的元素A^n[i][j]等于由顶点i和顶点j的长度为n的路径的数目。

5.2.2 邻接表法

当一个图为稀疏图时，使用邻接矩阵表示法显然要浪费大量的存储空间。图的邻接表法结合了顺序存储和链式存储方法。 顶点表：顶点域+边表头指针 边表：邻接点域+指针域

#define MaxVertexNum 100//图中顶点数目的最大值
typedef struct ArcNode{//边表结点
    int adjvex;//该弧所指向的顶点的位置
    struct ArcNode *next;//指向下一条弧的指针
    //InfoType info;//网的边权值
}ArcNode;
typedef struct VNode{//顶点表结点
    VertexType data;//顶点信息
    ArcNode *first;//指向第一条依附该结点的弧的指针
}VNode,AdjList[MaxVertexNum];
typedef struct{
    AdjList vertices;//邻接表
    int vexnum,arcnum;//图的顶点数和弧数
}ALGraph;//ALGraph是以邻接表存储的图类型

5.2.3 十字链表

有向图的一种链式存储方式。在十字链表中，有向图的每一条弧有一个结点，对应于每个顶点也有一个结点

• 弧结点：尾域+头域+链域hlink+链域tlink+相关信息info。尾域和头域分别指示弧尾和弧头这两个结点，链域hlink指向弧头相同的下一条弧，链域tlink指向弧尾相同的下一条弧，info域指向该弧的相关信息。
• 顶点结点：data+firstin+firstout，data存放顶点相关的数据信息，firstin和firstout两个域分别指向以该顶点为弧头或弧尾的第一个弧结点。 注意，顶点结点之间是顺序存储。 十字链表存储结构：

#define MaxVertexNum 100//图中顶点数目的最大值
typedef struct ArcNode{//边表结点
    int tailvex,headvex;//该弧的头尾结点
    struct ArcNode *hlink,*tlink;//分别指向弧头相同和弧尾相同的结点
    //InfoType info;//相关信息指针
}ArcNode;
typedef struct VNode{//顶点表结点
    VertexType data;//顶点信息
    ArcNode *firstin,*firstout;//指向第一条入弧和出弧
}VNode;
typedef struct{
    VNode xlist[MaxVertexNum];//邻接表
    int vexnum,arcnum;//图的顶点数和弧数
}GLGraph;//GLGraph是以十字邻接存储的图类型

本质上还是邻接表，但是针对有向图寻找入弧作出了优化，因此很容易可以求得顶点的出度和入度。

5.2.4 邻接多重表

邻接多重表是无向图的另一种链式存储结构 邻接表中难以求两个顶点之间是否存在边，以及难以执行删除边的操作。

• 边点：mark标识域，标记该边是否被搜索过；ivex和jvex为该边依附的两个顶点在图中的位置；ilink指向下一条依附于顶点ivex的边；jlink指向下一条依附于顶点jvex的边，info为指向和边相关的各种信息的指针域。
• 顶点：data，存储相关信息；firstedge指向第一条依附于该顶点的边

#define MaxVertexNum 100//图中顶点数目的最大值
typedef struct ArcNode{//边表结点
    bool mark;//访问标记
    int ivex,jvex;//分别指向该弧的两个结点
    struct ArcNode *ilink,*jlink;//分别指向两个顶点的下一条边
    //InfoType info;//相关信息的指针
}ArcNode;
typedef struct VNode{//顶点表结点
    VertexType data;//顶点信息
    ArcNode *firstedge;//指向第一条依附该结点的边
}VNode;
typedef struct{
    VNode adjmulist[MaxVertexNum];//邻接表
    int vexnum,arcnum;//图的顶点数和弧数
}AMLGraph;//AMLGraph是以邻接多重表存储的图类型

PS：稀疏矩阵可以使用十字链表和三元组表进行压缩 补充：

1. 三元组表：即只储存非零元素的位置，(i,j,aij)表示在图中的i行j列的元素aij
2. 二叉链表：用于存储二叉树的链表。二叉树一般使用从上到下，从左到右的顺序存储，具体实现上使用链表。

5.2.5 图的基本操作

5.3 图的遍历

BFS：分层遍历，借助辅助队列。 性能分析：空间复杂度O(|V|)（全部入队） 采用邻接表时，每个顶点入队一次，每条边至少访问一次，时间复杂度O(|V|+O|E|)。采用邻接矩阵时，查找每个顶点的邻接点所需时间为O(V)，所以总的时间复杂度为O(|V|^2)

使用BFS可以求解非带权图的单源最短路 广度优先生成树对于邻接矩阵而言是唯一的，对于邻接表是不唯一的。

DFS 递归算法，需要借助递归工作栈，空间复杂度为O(|V|) 以邻接矩阵表示时，查找每个顶点的邻接点所需时间为O(|V|)，故总的时间复杂度为O(|V|^2)。当以邻接表表示时，查找所有顶点的邻接点所需时间为O(|E|)，访问顶点所需时间为O(|V|)，总的时间复杂度为O(|V|+|E|) 基于邻接表的深度优先搜索树是不唯一的。

5.3.3 图的遍历与图的连通性

可以用图的遍历算法来判断图的连通性

5.4 图的应用

历年考察重点

5.4.1 最小生成树MSTP

一个连通图的最小生成树是图的极小连通子图，它包含图的所有顶点，且边的权值之和最小。 性质：

1. 最小生成树的树形不是唯一的，但是边的权值一定是最小的。（若G中各边权值互不相等，则G的最小生成树是唯一的）
2. 最小生成树的边数为顶点数减1

Prim算法

Dijkstra思路相同。思路如下：

1. 添加任意顶点至最小生成树子图中。
2. 重复将子图到非子图范围内最小的边添加进来，并将对应的结点加入子图中。
3. 添加完全部，算法结束 时间复杂度为O(|V|^2)，如果使用优先队列可以达到O(|V|log|V|)，适用于求解边稠密的图的最小生成树。

kruskal

1. 初始化，每个顶点构成一棵独立的树，得到一个森林
2. 将权值最小的边选定，如果将该边的两个顶点没有都加入最小生成树，则添加该边
3. 完成 可以用并查集实现判断顶点是否在最小生成树中。

5.4.2 最短路径

dijkstra求解单源最短路

• dist[]：记录从源点v0到其他各顶点的最短路径长度，初始为该点到各顶点的值（不连通则为无穷大）
• path[]：path[i]表示从源点到顶点i之间的最短路径的前驱结点。算法结束时，可以根据其值追溯得到源点v0到顶点vi的最短路径 操作：

1. 初始化集合为源点，初始化dist
2. 从顶点集合中选出dist值最小的一个点，将该点纳入初始集合
3. 松弛dist，对所有经过点j到达的顶点的权值进行更新。如果发生更新，设置path[i]指向j
4. 重复2、3操作共n-1次，直到所有顶点包含到初始集合中。

显然，主要开销就是找dist的最小值，可以使用优先队列优化。 dijkstra是基于贪心策略的，在边上带有负权值的时候不适用（准确来说，是对于有负圈的图，dijkstra无法结束） 时间复杂度O(|V|^2)

floyd求各顶点之间的最短路

时间复杂度O(|V|^3)，但是很简单。 思路就是使用邻接矩阵来存储任意两个点之间的距离。对于任意两个点，枚举可能的中间结点并更新这个矩阵。

5.4.3 拓扑排序

• 有向无环图：一个有向图中不存在环，则称为有向无环图DAG
• AOV网：如果用DAG图表示一个工程，其顶点表示活动，用有向图<V1,Vj>表示活动Vi必须先于Vj进行的这样一种关系，记为AOV网。
• 拓扑排序：每个顶点出现且只出现一次。若顶点A在序列中排在顶点B的前面，则图中不存在B到A的路径。

操作：

1. 找到入度为0的点，输出
2. 删除这个点，删除它的所有边，重复1直到没有其他点

显然，如果图中存在环，则它不可能有拓扑序列。 如果一个点有多个直接后继，则拓扑排序的结果通常不唯一。

5.4.4 关键路径

没错，和IT项目管理的关键路径法的那个关键路径是一个东西。 在带权有向图中，以顶点表示事件，有向边表示活动，边上的权值表示活动的开销，这样的网络称为AOE网。 AOE网的性质：

1. 只有在某顶点表示的活动发生后，从该顶点出发的各有向边所代表的活动才能开始。
2. 只有在进入某一顶点的各有向边所代表的活动都已经结束时，该顶点所代表的事件才能发生。 仅有一个入度为0的顶点，称为源点；有一个出度为0的顶点，表示汇点。 把从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，把关键路径上的活动称为关键活动。 事件vk，最早发生事件ve(k),最迟发生事件vl(k),活动ai的最早开始时间=ve(k)，最迟开始时间l(i)=vl(j)-weight(vk,vj)。 而一个活动ai的最迟开始时间与最早开始时间的差额d(i)=l(i)-e(i)，指该活动完成的时间余量。对于d(i)=0的活动，称为关键活动。 目的就是找到所有关键活动，组成关键路径。

错题：MST的一个限制条件 当带权连通图中的任意一个环中所包含的边的权值均不相同时，其MST是唯一的。

第6章 查找

6.1 查找的基本概念

• 查找：在数据中寻找满足某种条件的数据元素的过程称为查找。
• 查找表：用于查找的数据集合称为查找表，由同一类型的数据元素组成，可以组成一个数组或链表等数据类型。四个基本操作：1.查询某个特定的数据元素是否在查找表中。2.检索满足条件的某个特定的数据元素的各种属性。3.在查找表中插入一个数据元素。4.从查找表中删除某个数据元素。
• 静态查找表：如果一个查找表只涉及操作1和2，即不需要动态修改查找表中的内容。与之相对应，需要动态地插入或删除的查找表称为动态查找表。静态查找表查找方法：顺序查找、折半查找、散列查找等；动态查找表：二叉排序树查找、散列查找。
• 关键字：数据元素中唯一标识该元素的某个数据项的值，具有唯一性。
• 平均查找长度：在查找的过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值。

6.2 顺序查找和折半查找

顺序查找，即线性查找。一般分为对无序线性表的查找和按关键字有序的顺序表的顺序查找。

1. 一般线性表的顺序查找 即逐个查找，显然查找成功时平均查找长度ASL=pc=(n+1)/2，查找不成功时n+1。

2. 有序表的顺序查找 查找成功时平均查找长度和一般线性表的顺序查找是一样的。查找失败的时候会提前结束，为n/2+n/(n+1)

6.2.2 折半查找

又称二分查找 算法如下：

int Binary_Search(SeqListr L,ElemType key){
    int low=0,high=L.TableLen-1,mid;
    while(low<=high){
        mid=(low+high)/2;
        if(L.elem[mid]==key)
            return mid;
        else if(L.elem[mid]>key)
            high=mid-1;
        else
            low = mid+1;
    }
    return -1;
}

查找成功的平均查找长度为log2(n+1)-1，时间复杂度O(log2n)

6.2.3 分块查找

又称索引顺序 查找，既有动态结构，又可以快速查找 基本思想：

• 把查找表分为若干个小块
• 块内无序，块间有序
• 索引表中记录各块的最大关键字和地址

设将长度为n的查找表分为b块，每块s个记录。 索引表中顺序查找的平均查找长度=(s^2+2s+n)/(2s) 索引表中二分查找的平均查找长度=ceil((log2(b+1)))+(s+1)/2

PS：表长n个记录，均分成b块，每块记录数为s，则b=n/s。当s=ceil(sqrt(n))的时候，ASL最小为ceil(sqrt(n))+1

6.3 B树和B+树

B树重点考察，B+树只考察基本概念 王道P263

6.3.1 B树及其基本操作

B树，又称为多路平衡查找树，满足以下特性：

1. 树中每个结点至多有m个子树（最多有m-1个关键字）
2. 若根节点不是终端结点，则至少有两棵子树
3. 出根节点外的所有非叶节点至少有m/2棵子树（即至少含有m/2-1个关键字）
4. 所有非叶结点的结构如下：n,P0,K1,P1,K2,…Kn,Pn，其中K为结点的关键字；P为指向子树根节点的指针。且子树Pi-1所有的关键字均小于Ki，n为结点中关键字的个数，m/2-1<=n<=m-1
5. 所有叶节点都出现在同一层次上，并且不带信息（实际上不存在）

B树是所有结点的平衡因子均等于0的多路查找树 B树的大部分操作所需要的磁盘存取次数与B树的高度成正比。首先要明确，B树的高度不包括最下层叶节点所处的那一层。 对于任意一棵n个关键字，高度为h、阶数为m的B树

1. 因为n<=(m-1)*(1+m+m^2+…+m^(h-1))=m^h-1，因此h>=logm(n+1)

2. 若让每个结点的关键字个数达到最少，则容纳同样多关键字的B树的高度可以达到最大。h<=log(m/2)((n+1)/2)+1 PS:m/2对所有奇数向上取整

3. B树的查找 与二叉查找树相似，只是每个结点都是多个关键字的有序表，在每个结点做的是多路分支决定 两个基本操作：1.在B树中找结点；2.在结点内找关键字。由于B树存在磁盘上，前一个查找操作是在磁盘上进行的，后一个查找操作是在内存中进行的。 B树上查找到某个结点后，先在有序表中查找，然后到对应的子树中查找。

4. B树的插入

5. 定位：利用前述的B树查找算法，找出插入该关键字的最底层中某个非叶节点

6. 插入：在B树中，每个非失败结点的关键字个数都在ceil(m/2)-1到m-1之间。当插入后的结点关键字小于m，则可以直接插入；否则必须对结点进行分裂。 分裂的方法：取一个新的结点，将插入key后的原节点从中间位置将其中的关键字分为两部分。若此时导致父结点的关键字个数也超过了上限，则传递分裂，如果传到了根节点，则B树高度增加1.

7. B树的删除：类似，但是稍微复杂一点。 删除的关键字在叶节点上且符合条件：直接删除 删除的关键字在非叶结点上且符合条件：会从孩子结点提取合适的前驱或后继关键字，升上来。如果孩子结点全部不满足。如果都不满足，合并孩子结点。 删除的关键字后数量不符合要求：从自己的兄弟结点借一个，然后修正和父结点关键字的关系；如果兄弟都没有，那就合并。

5.B+树 B树的一种变形树，m阶的B+树和m阶的B树区别：

• B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，使得B+树每个非叶子结点能保存的关键字大大增加。
• B+树的叶子结点保存了父结点的所有关键字记录的指针，所有数据地址必须到叶子节点才能获取到。所以每次数据查询的次数都一样。
• B+树可以进行顺序查找

3. B+树叶子结点的关键字从小到大有序排序，左边结尾数据都会保存右边开始数据的指针。
4. 非叶子结点的子节点数=关键字数 在具体应用上，B+树比B树更适用于实际应用中的操作系统的文件索引和数据库索引，因为前者磁盘读写代价更低，查询效率更稳定。

6.4 散列表

• 散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr。散列函数可能将不同的关键字映射到同一地址，称为冲突。冲突是不可避免的。
• 散列表：根据关键字而直接进行访问的数据结构。即散列表建立了关键字和存储地址之间的一种直接映射关系。 理想情况的时间复杂度为O(1)

6.4.2 散列函数的构造方法

1. 直接定址法：直接取关键字的某个线性函数值作为散列地址。H(key)=a*key+b
2. 除留余数法：H(key)=key%p
3. 数字分析法：设关键字是r进制，而r个数码在各位上的分布不均等。选取分布较均匀的若干位作为散列地址。适用于已知的关键字集合。
4. 平方取中法：取关键字的平方值的中间几位作为散列地址。这样子的散列地址比较均匀，适用于关键字的每一位取值都不够均匀或小于散列地址所需的位数。
5. 折叠法：将关键字分割成位数相同的几部分，然后取几部分的叠加和。适用于关键字位数很多，且关键字每位数字分布大致均匀时。

6.4.3 处理冲突的方法

以下用Hi表示第i次探测的散列地址

1. 开放定址法:指的是可存放新表项的空闲地址即向它的同义词表项开放，又向它的非同义词开放。Hi=(H(key)+di)%m，di为增量序列，m表示散列表表长 （1）线性探测法，d=0,1,2,…,m-1，称为线性探测法。当冲突发生时，顺序查看表中下一个单元，直到找出一个空闲单元或查遍全表。无法避免堆积问题，可能严重降低效率，退化成链表。堆积问题会直接降低查找效率。 （2）平方探测法：d=0,1^2,-1^2,2^2,-2^2,…,k^2,-k^2，其中k<=m/2，散列表m必须是一个可以表示成4k+3的素数，又称为二次探测法。可以避免堆积问题，但是不能探测到散列表上所有的单元，只能探测至少一半单元。 （3）再散列法：当di=Hash2(key)，又称为双散列法，需要使用两个散列函数，第一个散列函数发生冲突时，用第二个散列函数计算关键字的地址增量。Hi=(H(Key)+i*Hash2(Key))%m，i是冲突的次数，最多经过m-1次探测会遍历表中所有位置，回到H0位置。 （4）伪随机序列法：di=伪随机数序列 PS：开放定址情况下，不能随意物理删除表中的已有元素，因为可能会截断其他具有相同散列地址的元素的查找地址。需要给它做删除标记。副作用是，多次删除后，尽管表面上散列表很满，但实际上还有许多位置没有利用，因此要定期清理散列表。

2. 拉链法（链接法,chaining） 将所有的同义词存在一个线性链表上

6.4.4 散列查找及性能分析

散列表的查找效率取决于三个因素：散列函数、处理冲突的方法和装填因子

• 装填因子：散列表中的装填因子一般记为a，定义为一个表的装满程度，即a=表中记录数n/散列表长度m 散列表的平均查找长度依赖于散列表的装填因子a。直观看，a越大，表示装填的记录越满，越可能发生冲突。

6.5 字符串匹配

6.5.1 简单的模式匹配算法

串的模式匹配，就是求第一个字符串在第二个字符串中的位置

int Index(SString S,SString T){
    int i=1,j=1;
    while(i<=S[0]&&j<=T[0]){
        if(S[i]==T[j]){
            ++i;
            ++j;
        }
        else{//失败，指针回退
            i=i-j+2;
            j=1;
        }
    }
    if(j>T[0])
        return i-T[0];
    else
        return 0;
}

时间复杂度为O(nm)，n、m分别为主串和模式串的长度

6.5.2 KMP

添加了失配函数，如果发生失配，并不直接归位，而是沿着next跳转。

void get_next(char T[],int next[]){
    i=1;
    next[1]=0;
    j=0;
    while(i<=T[0]){//T[0]保存字符串的长度
        if(j==0||T[i]==T[j]){
            ++i;++j;next[i]=j;
        }
        else{
            j=next[j];
        }
    }
}
//王道版本的KMP
int KMP(char S[],char T[],int next[],int pos){
//利用模式串T的next函数在主串S中第pos个位置之后的位置的KMP算法
    i=pos;
    j=1;
    while(i<=S[0]&&j<=T[0]){
        if(j==0||S[i]==T[j]){
            ++i;
            ++j;
        }
        else{
            j=next[j];
        }
    }
    if(j>T[0]){
        return i-T[0];
    }
    else
        return 0;
}

我更喜欢算法导论版本的伪代码KMP

//匹配串T，模板串P
KMP-MATCHER(T,P){
    n=T.length
    m=P.length
    pi=COMPUTE-PREFIX-FUNCTION(P)//根据模板串计算转移函数pi
    q=0
    for i=1 to n{
        while q>0 && P[q+1]!=T[i]{//如果失配，沿转移函数前进
            q=pi[q]
        }
        if P[q+1]==T[i]{
            q = q+1
        }
        if q==m{
            Print i-m
            q = pi[q]//寻找下一个匹配
        }
    }
}

COMPUTE-PREFIX-FUNCTION(P){
    m=P.length
    let pi[1...m] be a new array
    pi[1]=0
    k=0
    for q=2 to m{
        while k>0 && P[k+1]!=P[q]
            k=pi[k]
        if P[k+1]==P[q]
            k=k+1
        pi[q]=k
    }
    return pi
}

第7章 排序

7.1 排序的基本概念

7.1.1 排序的定义

排序，就是重新排列表中的元素，使表中的元素按关键字递增或递减的过程。 算法稳定性：如果有两个元素Ri=Rj，其对应的关键字keyi=keyj，且排序时Ri在Rj的前面。如果使用某一排序算法排序后，Ri仍然在Rj前面，该算法是稳定的，否则称排序算法是不稳定的。

• 内部排序：指在排序期间元素全部存放在内存中的排序。
• 外部排序：指在排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序。

7.2 插入排序

7.2.1 直接插入排序

某一时刻状态：有序序列L[1…i-1]、L[i]、无序序列L[i+1…n] 为了将L[i]插入，执行以下操作：

1. 查找出L[i]在有序序列的插入位置k
2. 将L[k…i-1]的元素后移一个单位
3. 将L[i]复制到L[k]

void InsertSort(ElemType A[],int n){
    int i,j;
    for(i=2;i<n;i++)
    {
        if(A[i].key<A[i-1].key){
            A[0]=A[i];//复制为哨兵，A[0]不存放元素
            for(j=i-1;A[0].key<A[j].key;--j)//从后往前查找待插入位置
                A[j+1]=A[j];//向后挪位
            A[j+1]=A[0];//复制到插入位置
        }
    }
}

效率分析；

• 空间效率O(n)
• 时间效率：O(n^2)
• 稳定性：稳定的排序方法
• 实用性：适用于顺序存储和链式存储的线性表。 PS：大部分排序算法都仅适用于顺序存储的线性表。

7.2.2 折半插入排序

查找有序子表的部分用折半查找来实现。在确定出待插入位置后，就可以统一地向后移动元素了。

void InsertSort(ElemType A[],int n){
    int i,j,low,high,mid;
    for(i=2;i<=n;i++){
        A[0]=A[i];
        low=1;high=i-1;
        while(low<=high){
            mid=(low+high)/2;
            if(A[mid].key>A[0].key) high = mid-1;
            else low = mid+1;
        }
        for(j=i-1;j>=high+1;--j)
            A[j+1]=A[j];//统一后移，空出位置
        A[high+1]=A[0];
    }
}

7.2.3 希尔排序

直接插入排序适用于基本有序的算法和数据量不大的排序表，基于此提出了希尔排序，又称缩小增量排序。 基本思想：先将待排序表分割成若干个形如L[i,i+d,i+2d,…i+kd]的特殊子表，分别进行直接插入排序。党整个表中元素基本有序时，再对全体进行一次直接插入排序。 过程：

1. 先取一个小于n的步长d1，把表中全部记录分成d1个组，所有距离为d1的倍数的记录放在同一个组中，同时在各组中进行直接插入排序；
2. 然后取第二个步长d2<d1，重复该过程，直到所取到的d1=1，即所有记录已放到同一组中，再进行直接插入排序，由于此时已经具有较好的局部有序性，故很快可以得到结果。 PS：到目前为止，尚未求得最好的增量序列。希尔提出的办法是d1=n/2,di+1=floor(di/2)，并且最后一个增量等于1. 如下：

void ShellSort(ElemType A[],int n){
/*
修改如下：
1. 前后记录位置的增量是dk，不是1
2. r[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
*/
    for(dk=n/2;dk>=1;dk/=2){//补偿变化
        for(i=dk+1;i<=n;++i){
            if(A[i].key<A[i-dk].key){//需将A[i]插入有序增量子表中
                A[0]=A[i];
                for(j=i-dk;j>0&&A[0].key<A[j].key;j-=dk){
                    A[j+dk]=A[j];//记录后移，查找插入的位置
                }
                A[j+dk]=A[0];
            }
        }
    }
}

性能分析：

• 空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1)
• 时间效率：当n在某个特定范围内，约为O(n^1.3)，在；最坏情况下希尔排序的时间复杂度为O(n^2)
• 稳定性：不稳定
• 实用性：仅适用于顺序存储

7.3 交换排序

根据序列中两个关键字的比较结果来交换这两个记录在序列中的位置。重点考冒泡排序和快速排序，一般不会单独考察冒泡排序

7.3.1 冒泡排序

基本思想：太简单，略。 每趟冒泡的结果都会将一个元素放在最终位置，比如用王道的算法，每次排序之后会将序列中最小的元素放在序列最前面。 记忆：想冒泡泡一样，每次从头撸到尾，最后一个就有序了，然后少撸一截。撸n-1遍。 冒泡有个很好的性质，就是如果撸一遍以后没有可以交换的对象了，那么之后也不再有可以交换的对象，可以提前结束算法。

void BubbleSort(ElemType A[],int n){
    //冒泡排序，从小到大
    for(i=0;i<n-1;i++){
        flag = false;//表示本趟冒泡是否发生交换
        for(j=n-1;j>i;j--){
            if(A[j-1].key>A[j].key){
                swap(A[j-1],A[j]);
                flag = true;
            }
        }
        if(!flag){
            return;//本趟遍历后没有交换，说明序列已经有序
        }
    }
}

效率分析；

• 空间复杂度O(1)
• 时间复杂度O(n^2)
• 稳定性：稳定的 冒泡排序产生的有序子序列一定是全局有序的，即有序子序列中的所有元素的关键字一定小于无序子序列中的关键字（不同于直接插入排序）看，即到达最终位置。

7.3.2 快速排序

基本思想是基于分治的。

void QuickSort(ElemType A[],int low,int high){
    if(low<high){
        int pivotpos=Partition(A,low,high);//划分
        QuickSort(A,low,pivotpos-1);
        QuickSort(A,pivotpos+1,high);
    }
}
int Partition(ElemType A[],int low,int high){
//严谨的一趟排序过程
    ElemType pivot=A[low];
    while(low<high){
        while(low<high&&A[high]>=pivot) --high;
        A[low]=A[high];//将比枢轴值小的元素移动到左端
        while(low<high&&A[low]<=pivot)  ++low;
        A[high]=A[low];//将比枢轴值大的元素移动到右端
    }
    A[low]=pivot;//枢轴元素存放到最终位置
    return low;
}

也有结合起来的版本，比如我NOIP时期的代码：

#include <stdio.h>
int n,a[100009];
void sort (int a[],int left,int right) {
    int low,high,pivot;
    int temp;
    low=left,high = right;
    pivot=a[(left+right)/2];
    while (low<=high) {
        while (a[low]<pivot) low++; 
        while (pivot<a[high]) high--;
        if (low<=high) {
            temp=a[low];
            a[low]=a[high];
            a[high]=temp;
            low++,high--;
        }
    }
    //记忆后面两句话的时候一定要记得，此时low>high
    if (left<high) sort(a,left,high);
    if (low<right) sort(a,low,right);
}
int main () {
    int i,j;
    scanf("%d",&n);
    for (i=1;i<=n;i++) 
        scanf("%d",&a[i]);
    sort(a,1,n);//从0开始是个好习惯，不过我费事改了
    for (i=1;i<=n;i++)
        printf("%d ",a[i]);
}

效率分析：

• 递归的空间复杂度平均为O(log2n)（函数调用栈）
• 时间复杂度：O(nlog2n)，最坏情况下O(n^2)。
• 稳定性：不稳定 PS：每一趟排序后会将一个元素（基准元素）放到最终位置上 优化：

1. 在子序列规模较小时放弃递归调用快排，使用直接插入排序等完成后续的排序工作
2. 尽量取可以将数据中分的枢轴元素，比如根据头、尾、中间三个元素的中间值等。

7.4 选择排序

基本思想：每一趟在后面n-i+1个待排序元素中选择关键字最小的元素，作为有序子序列的第i个元素，直到第n-1趟完成。

7.4.1 简单选择排序

void SelectSort(ElemType A[],int n){
    for(i=0;i<n-1;i++){
        min=i;
        for(j=i+1;j<n;i++){
            if(A[j]<min)    min=j;
        }
        if(min!=i)  swap(A[i],A[min])
    }
}

效率：

• 空间复杂度O(1)
• 时间复杂度O(n^2)
• 稳定性：不稳定

7.4.2 堆排序

堆排序是一种树形选择排序方式。特点是将L[1..n]看成是一棵完全二叉树的顺序存储结构，以此完成排序。 堆是一种特殊的二叉树，它的根节点的值大于/小于其两个孩子的值，这样根节点就是最大/最小的。通过不断提取最大值，可以得到一个序列，这个序列就是最终的排序结果。

void BuildMaxHeap(ElemType A[],int len){
    for(int i=len/2;i>=0;i--)
        AdjustDown(A,i,len);
}
void AdjustDown(ElemType A[],int k,int len){
//AdjustDown将元素k向下调整
    A[0]=A[k];
    for(i=2*k;i<=len;i*=2){//沿key较大的子节点向下筛选
        if(i<len&&A[i]<A[i+1]){
            i++;//取key较大的子节点的下标
        }
        if(A[0]>=A[i])  break;//筛选结束
        else{
            A[k]=A[i];//将A[i]调整到双亲结点上
            k=i;//修改k值，以便继续向下筛选
        }
    }
    A[k]=A[0];//被筛选结点的值放入最终位置
}

void HeapSort(ElemType A[],int len){
    BuildMaxHeap(A,len);//初始建堆
    for(i=len;i>1;i--){//n-1趟的交换和建堆过程
        Swap(A[i],A[1]);//输出堆顶元素
        AdjustDown(A,1,i-1);//整理，将剩余的i-1个元素整理成堆
    }
}
void AdjustUp(ElemType A[],int k){
    //参数k为向上调整的结点，也为堆的元素个数
    A[0]=A[k];
    int i=k/2;
    while(i>0&&A[i]<A[0]){
        A[k]=A[i];//双亲结点下调
        k=i;
        i=k/2;
    }
    A[k]=A[0];
}

• 空间效率：空间复杂度为O(1)
• 时间效率：建堆时间O(n)，之后n-1次向下调整，每次调整的时间复杂度为O(h)，故平均而言，时间复杂度为O(nlog2n)
• 稳定性：不稳定的

7.5 归并排序和基数排序

7.5.1 归并排序

将两个或两个以上的有序表组合成一个新的有序表。假定待排序表含有n个记录，则可以看成是n个有序子表，然后不断两两归并直到合成一个长度为n的有序表为止，这种排序方法称为2-路归并排序。

递归形式的2-路归并排序算法是基于分治额，对子表递归地排序。

ElemType *B=(ElemType *)malloc((n+1)*sizeof(ElemType));//辅助数组B，长度n+1
void Merge(ElemType A[],int low,int mid,int high){
//表A的两端low...mid和mid+1...high各自有序，将它们合并成一个有序表
    for(int k=low;k<=high;k++)
        B[k]=A[k];//将A中的所有元素复制到B中
    for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
        if(B[i]<=B[j]){//比较B的左右两段中的元素
            A[k]=B[i++];//将较小值复制到A中
        }
        else{
            A[k]=B[j++];
        }
    }
    while(i<=mid)   A[k++]=B[i++];
    while(j<=high)  A[k++]=B[j++];
}

void MergeSort(ElemType A[],int low,int high){
    if(low<high){
        int mid=(low+high)/2;//从中间划分两个子序列
        MergeSort(A,low,mid);
        MergeSort(A,mid+1,high);
        Merge(A,low,mid,high);
    }
}

效率：

• 空间复杂度O(n)
• 时间复杂度O(nlog2n)
• 稳定性：稳定的

7.5.2 基数排序

它不是基于比较进行排序的，而是采用多关键字排序思想，又分为最高位优先排序和最低位优先排序。 以r为基数的最低位优先基数排序的过程：假设线性表由结点序列a0,a1,…,an-1构成，每个结点的关键字由d元组组成

• 分配：开始时，把Q0,Q1,…,Qr-1各个队列置成空队列，然后依次考察线性表中的每一个结点aj，如果aj的关键字的第i位符合要求，就把aj放入Qk队列中
• 收集：把Q0,Q1,…,Qr-1各个队列中的结点依次首尾相接，得到新的结点序列，从而组成新的线性表。

效率：

• 空间效率：一趟排序需要的辅助存储空间为r（r个队列），但以后的排序中重复使用这些队列，所以基数排序的空间复杂度为O(r)
• 时间复杂度：d趟分配和收集，一趟分配需要O(n)，一趟收集需要O(r)，所以基数排序的时间复杂度为O(d(n+r))，它与序列的初始状态无关。
• 稳定性：稳定的。

7.6 各种内部排序算法的比较及应用

7.6.1 内部排序算法的比较

省略，看书

7.7 外部排序

7.7.1 外部排序的基本概念

在排序过程中需要多次进行内存和主存之间的交换，对外村文件中的记录进行排序后的结果仍然被放到原有文件中。这种排序方法就称为外部排序。

7.7.2 外部排序的方法

通常根据外存设备的不同分为磁盘文件排序和磁带文件排序两大类。磁盘是直接存取设备，磁带是顺序存取设备。 外部排序通常采用归并排序方法，有两个相对独立的阶段：

1. 根据内存缓冲区的大小，将外存上含n个记录的文件分成若干长度为h的子文件，依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写回外存（通常称这些有序子文件为归并段或顺串）
2. 对这些归并段进行逐趟归并，使归并段逐渐由小变大，直至得到整个有序文件为止。

一般情况下，外部排序的总时间=内部排序所需的时间+外存信息读写的时间+内部归并所需的时间 即t_ES=rt_IS+dt_IO+S(n-1)t_mg，其中r是初始归并段的个数，t_IS是对每一个初始归并段进行内部排序的时间，d是访问外存块的次数，t_IO是每一个块的存取时间，S是归并趟数，n是每趟参加二路归并的记录个数，t_mg是每作一次内部归并，取得一个关键字最小记录的时间。 显然磁盘存取的时间远远大于内部排序和内部归并的时间，因此要提高外排序的速度，应该着力减少d，即I/O次数。

增大归并路数m，或减少初始归并段数r，都能减少归并趟数S，以减少读写磁盘次数d，达到提高外部排序速度的目的。

7.7.3 多路平衡归并与败者树

上节提到，可以增加归并路数m来减少归并趟数S，进而减少访问外存的次数。然而增加归并路数m又会增加算法内部排序的时间。因此不能使用普通的内部归并排序算法。 为了使内部归并不受m的增大的影响，引入了败者树。可以看作是一棵完全二叉树，每个叶结点存放各归并段在归并过程中参加比较的记录。内部结点用来记录左右子树中的失败者，让胜利者继续向上比较，一直到根节点。 m路归并的败者树深度为ceil(log2m)，因此m个记录中选择最小关键字，最少需要ceil(log2(m))次比较，内部归并的比较次数就与m无关了。因此，只要内存空间允许，增大归并路数m可以有效减少归并树的高度，从而减少I/O次数d，提高外部排序的速度。 值得注意的是m并不是越大越好，m增大时要相应地增加输入缓冲区的个数。如果可供使用的内存空间不变，就势必要减少每个输入缓冲区的容量，使得内外存交换数据的次数增大。当m值过大时，虽然归并趟数减少，但读写外存的次数仍会增加。

7.7.4 置换-选择排序（生成初始段）

如果采用前面介绍过的内部排序方法，将得到长度都相同的初始归并段。因此，需要使用新的算法那来生成初始归并段。 设初始待排文件FI，初始归并段文件为FO，内存工作区为WA，内存工作区可容纳w个记录。置换-选择算法的步骤如下：

1. 从待排方法FI输入w个记录到工作区WA。
2. 从内存工作区WA中选出其中关键字取最小值的记录，即为MINIMAX（以后再选出关键字比它大的记录归入本归并段，比它小的归入下一归并段）
3. 将MINIMAX记录输出到FO中去
4. 若FI未读完，则从FI输入下一个记录到WA中。