数据结构

数据结构(Data Struct)

第一章 数据结构导论

1.基本概念和术语

数据：计算机中描述客观事物的符号，是计算机中可以操作的对象，能被计算机识别，并输入给计算机处理的符号集合。数据不仅仅包括整型，实型，还包括字符及声音、图像、视频等非数值类型。

数据元素：是组成数据的，有意义的基本单位，在计算机中通常作为整体处理。也被称为记录。

数据项：一个数据元素由多若干个数据项组成。数据项是数据不可分割的最小单位。

数据对象：性质相同的数据元素的集合，是数据的子集。比如人类是数据对象，那么数据元素就是人，各种人，黑人白人黄人。数据项就是一个人的眼睛鼻子耳朵手等等。一般把数据对象称为数据。

数据结构：相互之间存在一种或多种特定关系的数据元素的集合。

2.逻辑结构和物理结构

2.1逻辑结构

逻辑结构：是指数据对象中数据元素之间的相互关系。

逻辑结构包含：集合结构，线性结构，树形结构，图形结构。

集合结构：各种数据元素同处一个集合，但是它们之间没有任何的关系。

线性结构：线性结构中数据元素的关系是一对一的。

树形结构：树形结构中数据元素之间存在一对多的层次关系。

图形结构：图形结构中数据元素是多对多的关系。

2.2物理结构

物理结构：是指数据的逻辑结构在计算机中存储形式。包含顺序存储结构和链式存储结构。

顺序存储结构：是指把数据元素存放在地址连续的存储单元里面，其数据间的逻辑关系和物理关系是一致的。就比如顺序表。

链式存储结构：把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以连续的，它们之间是用指针来进行相连的。

3.总结

第二章 算法

1.算法

1.1.算法的特性：输入，输出，有穷性，确定性，可行性。

1.2.比较算法：

//第一种算法：
int i,sum = 0,n = 100;   //执行了一次
for(i=1;i<=n;i++){       //执行了n+1次
    sum = sum + i		 //执行了n次
}
printf("%d",sum);      //执行了一次
    
//第二种算法：
int sum = 0,n = 100;       //执行了一次
sum = (n+1) * n/2;		//执行了一次
printf("%d",sum);		//执行了一次


//第一种执行了2n+3次,第二种执行了3次。

2.时间复杂度

2.1常见的时间复杂度表

2.2时间复杂度耗时比较

第三章 线性表

1.1线性表的定义

线性表：零个或多个数据元素的有限序列。

线性表的元素之间是有顺序的，当存在多个元素时，第一个元素无前驱，最后一个元素无后继，其他每个元素都有前驱和后继。线性表中第一个元素从一开始记，而数组的话，第一个元素要从下标0开始记起，这个需要注意。

1.2线性表的抽象数据类型

ADT 线性表(List)
Data
    线性表的数据对象集合为{a1,a2,....,an},每个元素的类型均为DataType。其中,除第一个元素a1外,每一个元素都有它的前驱元素,除最后一个an外,每一个元素都有它的后继元素,数据结构之间的关系都是一一对应的。
Operation
    InitList(*L):	初始化操作,建立一个空的线性表L。
    ListEmpty(L):	若线性表为空,返回true,否则返回false。
    ClearList(*L):	将线性表删除。
    GetElem(L,i,*e):	将线性表L中第i个元素返回给e。
    LocateElem(L,e):	在线性表L中查找与给定值e相等的元素,如果查找成功,返回该元素在表中序号表示成功,否则,返回0则表示失败。
    ListInsert(*L,i,e):    在线性表L中的第i个位置插入新元素e。
    ListDelete(*L,i,*e):	删除线性表L中第i个位置元素,并用e返回其值。
    ListLength(L):	返回线性表L的元素个数。

下面将用伪代码实现：

将所有的在线性表Lb中但不在在La中的数据元素插入到La中。这个问题类似于数学中的并集操作。

void union(List *La,List Lb)
{
    int La_len,Lb_len,i;   //i表示元素中的位置
    ElemType e; 	//声明La和Lb相同的数据元素e
    La_len = ListLength(La);	//求线性表中的长度
    Lb_len = ListLength(Lb);
    for(i=1,i<=Lb_len;i++){
        GetElem(Lb,i,e);	//取出第i个数据元素赋值给e
        if(!LocateElem(La,e,equal)){  //查找在Lb中遍历的元素是否在La中,如果不存在的话就执行下一条语句。
            ListInsert(La,++La_len,e) //向La中插入元素e
        }
    }
}

1.3线性表的顺序存储结构

线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。

简化：线性表的顺序存储结构说白了就是在内存中找了块地，通过占位的形式，把一定内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空地中。在C语言中可以用一维数组来实现顺序存储结构。

顺序存储结构的代码如下：

#define MAXSIZE 20	//存储空间初始分配量
typedef int ElemType;	//Element的类型根据情况而定,这里假设为int
typedef struct
{
    ElemType data[MAXSIZE];    //使用数组来存储数据元素,最大值为20
    int Length;		//线性表当前的长度
}SqlList;

数组长度和线性表长度的区别：数组的长度是存放线性表存储空间的长度，而线性表的长度是线性表中数据元素的个数，数组从下标0开始数起，线性表从1开始数起，这个需要注意。

1.3.1顺序存储结构的插入和删除操作

1.3.1.1获得元素操作：

如果我们要获得元素，我们可以使用GetElem操作，思路是将线性表的第i个元素返回，只要i的数值在数组下标范围内，则把数组第i-1下标的值返回即可。

#define Ok 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;  //Status是函数的类型,其值是函数状态代码，比如OK,ERROR等

//初始化条件：顺序线性表L已经存在,1<=i<=ListLength(L)
//操作结果：用e返回L中第i个数据元素的值

Status GetElem(SqList L,int i,ElemType *e)
{
    if(L.length==0 || i<1 || i>L.length){
        return ERROR;
    }else{
        *e = L.data[i-1];   //将线性表中第i个元素返回给e
        return Ok;
    }
}

1.3.1.2插入操作

插入操作，除了在表尾插入之外，每次插入都会牵一发而动全身，时间复杂度为n。

插入算法的思路：

1.如果插入的位置不合理，抛出异常；

2.如果线性表长度大于数组长度，则抛出异常或动态增加容量；

3.从最后一个元素开始向前遍历到第i个元素，分别将它们都向后移动一个位置；

4.将插入元素填入位置i；

5.表长加1。

//初始条件：顺序线性表L已存在,1<=i<=ListLength(L)
//操作结果：在线性表L中第i个位置之前插入新的数据元素e,线性表L的长度+1
Status ListInsert(SqList *L,int i,ElemType e)   //i为在第几个位置插入
{
	int k;
    if(L->length == MAXSIZE)   //顺序线性表已经满
        return ERROR;
    if(i<1 || i>L->length+1)	//当i不在表的范围内时    
        return ERROR;
    if(i <= L->length)	//若插入的数据元素不在表尾
    {
        for(k=length-1;k>=i-1;K--)//将插入位置后数据元素向后移动一位
            L->data[k+1] = L->data[k];
    }
    L->data[i-1] = e  //将新元素插入
    L->length++;
    return Ok;
}

1.3.1.3删除操作

线性表的删除操作跟插入操作也挺相似，当删除的时候，线性表的所有元素都要向前移动一个单位，除了在最后一个元素进行删除操作，每一次的删除线性表的空闲空间将会增加。

删除算法的思路：

1.如果删除位置不合理，抛出异常；

2.取除删除元素

3.从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；

4.表长减一。

//初始化条件:顺序线性表L已存在，1<=i<=ListLength(L)
//操作结果:删除线性表L的第i个数据元素,并用e返回其值,L的长度减一
Status ListDelete(SqList *L,int i,ElemType *e)
{
    int k,
    if(L->length == 0){		//线性表为空
        return ERROR;
    }
    if(i<1 || i>L->length)   //删除位置不正确
        return ERROR;
    *e = L->data[i-1];
    if(i<L->length){	//如果删除不是最后位置
        for(k=i;K<L->length;K++)    //将删除位置后继元素前移
            L->data[k-1] = L->data[k];		//这里k为第i个元素
    }
    L->length--;
    return OK;
}

现在我们来算算插入和删除的时间复杂度，如果是在最后一个位置插入和删除元素，它们的时间复杂度均为O(1)，而如果元素要插入到第一个位置或删除第一个元素，此时的时间复杂度为O(n)。至于平均情况下，元素插入或删除第i个位置，需要移动n-i个位置(这里的n插入元素+1，删除元素-1),最终结果都为O(n)。

1.3.2线性表顺序存储结构的优缺点

1.4线性表的链式存储结构

1.4.1链表的概念

线性表链式存储结构定义：线性表的链式存储结构的特点就是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的，也就意味着，这些数据元素可以存在内存尚被占用的任意位置，需要时再开辟内存即可。在以前的顺序结构中，每个数据元素只需要存储数据元素信息即可，现在在链式结构中，除了要存数据元素信息外，还要存储它的后继元素的地址。

逻辑结构上一个挨一个的数据，在实际存储时，并没有像顺序表那样也相互紧挨着。恰恰相反，数据随机分布在内存中的各个位置，这种存储结构称为线性表的链式存储。

链表和数组的作用相同，都是用来存储数据。数组在C语言中是一种很常见的数据结构,它是用来存储数据的,但是数组是一次分配

完全部内存，而链表则是在需要时再分配内存，每次只分配出一个节点(Node)的内存，链表是由多个节点组成的，而每个节点都有俩个部分：数据区和指针区。

数据区：数据区是用来存储数据。

指针区：指针区是用来存储指向下一节点的指针。

链表:

头指针：永远指向链表中第一个结点的位置（如果链表有头结点，头指针指向头结点；否则，头指针指向首元结点）。

首元结点：链表中第一个元素所在的结点，它是头结点后边的第一个结点。即图中第二部分图形。

头结点：有时，在链表的第一个结点之前会额外增设一个结点，结点的数据域一般不存放数据（有些情况下也可以存放链表的长度等信息），此结点被称为头结点。但此图没有定义头节点，头节点的指针域存储指向第一个节点(首元节点)的指针。

单链表中可以没有头结点，但是不能没有头指针，头指针是必须的。

一般有头节点的链表是这样的：

头指针和头节点的区别：

头指针：头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。头指针具有标识作用，所以常用头指针作为链表的名称。无论链表是否为空，头指针均不为空，头指针是链表的必要元素。

头结点：头结点是为了操作的统一和方便设立的，放在第一个元素的结点之前，其数据域一般无意义(也可存放链表的长度)。有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作于其他结点的操作就统一了。头结点不一定是链表必须要素。

结点是由存放数据元素的数据域和存放后继结点地址的指针域组成。

代码描述结构指针。

//线性表的单链表存储结构
typedef struct Node
{
    ElemType data;			//数据域
    struct Node *next;		//指针域
}Node;
typedef struct Node *LinkList;    //定义LinkList

1.4.2单链表的读取

在线性表的顺序存储结构中，我们要计算任意一个元素的存储位置是很容易的。但在单链表中，第i个元素在哪？我们一开始是不知道的阿，我们必须从头开始一个一个找。

获取第i个数据的算法思路是：

1.声明一个结点p指向链表的第一个结点，初始化j从1开始；

2.当j<k时，就遍历链表，让p的指针向后移动，不断指向下一节点，j累加1；

3.若链表末尾p为空，则说明第i个元素不存在；

4.否则查找成功，返回结点p的数据。

代码实现如下：

//初始条件: 顺序表L已存在,1 <= i <= ListLength(L)
//操作结果: 用e返回L中的第i个数据元素的值
Status GetElem(LinkList L,int i,ElemType *e)
{
    int j;
    LinkList p;				//声明结点p
    p = L->next;		//让p指向链表L的第一个结点
    j = 1;		//j为计数器
    while(p && j<i){	//p不为空或者计数器j还没有等于i时，循环继续
        p = p->next;	//让p指向下一结点
        ++j;			//j前自增+1            
    }
    if(!p || j>i)	//如果第i个结点不存在
        return ERROR;
    *e = p->data;	//取第i个元素的数据
}

当i=1时，则无需遍历，但是当i=n时，则遍历n-1次才可以，时间复杂度为O(n)。

1.4.3单链表的插入与删除

单链表的插入：核心思想：s->next = p->next p->next = s

单链表第i个数据插入结点的算法思路：

1.声明一结点p指向链表的第一个结点，初始化j从1开始；

2.当j<K时，就遍历链表，让p的指针向后移动，不断指向向一结点，j累加1；

3.若到链表末尾p为空，则说明第i个元素不存在；

4.否则查找成功，在系统中生成一个空结点s；

5.将数据元素e赋值给s->data；

6.单链表的插入核心语句：s->next = p->next; p->next = s;

7.返回成功。

实现代码如下：

//初始条件：顺序表线性表L已经存在,1 <= i <= ListLength(L),
//操作结果：在L中第i个位置之前插入新元素e,L的长度加1
Status ListDelete(LinkList *L,int i,ElemType e)
{
    int j;
    LinkList p,q;		//定义两个结点
    p = *L;
    j = 1;
    while(p->next && j<i){		//遍历寻找第i个元素
        p = p->next;
        ++j;
    }
    if(!(p->next) || j>i)	//如果p结点没有下一个结点与超出i的位置
        return ERROR;	//第i个元素不存在
    q = p->next;		//插入新结点q
    p->next = q->next;		//将q的后继直接赋值给p的后继
    *e = q->data;		//将q结点的数据给e
    free(q);		//让系统收回此结点,释放内存
}

以上使用了free函数，作用是让系统回收一个Node结点，释放内存。

对于单链表的插入和删除算法，都是由两部分组成：第一部分就是遍历查找第i个元素，第二部分就是插入和删除元素。遍历的时间复杂度为O(n)，插入删除的时间复杂度为O(1)。所以这就是单链表跟顺序表，在我们的日常中，看情况而进行选择，而对于”插入或删除数据越频繁”的操作，单链表的效率优势就是越明显。

1.4.4单链表的整表创建

回顾一下，顺序存储结构的创建，其实就是一个数组的初始化，就是声明一个类型和大小的数组并赋值的过程，而单链表与顺序存储结构不一样，它不像顺序存储结构那么集中，它可以很散，是一种动态结构，并且它所占用的空间的大小和位置是不需要预先分配划定的，只需要系统的情况和实际的需求即使生成即可。

单链表的创建过程就是一个动态生成链表的过程。就是从空表的初始状态，依次建立各元素结点，并逐个插入链表。

单链表创建过程思路：

1.声明一节点p和计数器i；

2.初始化一空链表L；

3.让L的头结点的指针指向NULL，即建立一个带头结点的单链表；

4.循环：

​ 1）生成一新结点赋值给p；

​ 2）随机生成一数字赋值给的数据域p->data；

​ 3）将p插入到头结点与前一新结点之间。

实现代码如下：

//随机产生n个元素的值,建立带表头结点的单链表L(头插法)
void CreateListHead(LinkList *L,int n)
{
    ListLink p;		//声明新结点p
    int i;		//声明计数器i
    srand(time(0));		//初始化随机种子
    *L = (LinkList)malloc(sizeof(Node));  //malloc函数用于动态内存分配
    (*L)->next = NULL;	//建立一个带头结点的单链表
    for(i=0;i<n;i++){		//循环生成新结点
        p = (LinkList)malloc(sizeof(Node));		//分配内存,生成新结点
        p->data() = rand()%100 + 1;			//随机生成100以内的数字赋值给新结点的数据域
        p->next = (*L)->next;		//因为p结点是新插入进去的,所以头结点的指的下一结点就是p结点指的下一结点,p在中间
        (*L)->next = p	//p是新插入的结点
    }
}

以上方式称为头插法：让新结点的位置始终保持在第一的位置，也就是头结点的后一个位置。

以上的方法称之为头插法，当然我们还可以有另一种方法，就是把新节点放在最后，这才是排队的正常思维——先来后到。我们每次把新结点放在终端结点的后面称之为尾插法。

实现代码如下：

//随机产生n个元素的值，建立带表头结点的单链线性表L(尾插法)
void CreateListTail(LinkList *L,int n)
{
    LinkList p,r;	//声明新结点p,r
    int i;
    srand(time(0));		//初始化随机数种子
    *L = (LinkList)malloc(sizeof(Node));	//为单链表L开辟内存空间
    r = *L;			//r为指向尾部的结点
    for(i=0;i<n;i++){
        p = (Node *)malloc(sizeof(Node));	//生成新结点
        p->data = rand()%100+1;		//随机生成1到100以内的数字
        r->next = p;		//将表尾终端结点的指针指向新插入的结点
        r = p;		//将当前的新结点定义为表尾终端结点
    }
    r->next = NULL;		//当指针指向NULL的时候,说明链接结束
}

1.4.5单链表的整表删除

当我们不打算使用整个单链表的时候，我们需要销毁它，本质就是在内存中将它释放掉，以便留出空间给其他程序或软件使用。

单链表整表删除的算法思路如下：

1.声明一节点p和q；

2.将第一个结点赋值给p；

3.循环：

​ 1)将下一结点赋值给q；

​ 2)释放p；

​ 3)将q赋值给p。

实现代码如下：

//初始条件：顺序线性表L已存在,操作结果:将L重置为空表
Status ClearList(LinkList *L)
{
    LinkList p,q;    //声明q结点和p结点
    p = (*L)->next;		//将*p指向第一个结点 
    while(p){		//当线性表L有下一个结点的时候,说明没有到表尾
        q = p->next;	//q结点就是p结点的的下一结点
        free(p);		//释放p结点内存
        p=q;		//p结点成为q结点
    }
    (*L)->next = NULL;		//头结点指针域为空
    return OK;
}

1.4.6单链表结构与顺序存储结构的优缺点

它们的特点各有千秋。

1.4.7静态链表

在C语言中，具有指针的能力，使得它非常容易的操作内存中的地址和数据，后来在其他语言中，比如Java，C#等，它们虽然不使用指针，但它们启用了对象引用机制，间接直接实现了指针的作用。也就是说指针封装在了对象的底层。

但是在早期的时候，一些古老的语言是没有指针的概念也没有对象的概念，于是古人就想出来用数组替代指针来描述单链表。

思路：让数组的元素都是由两个数据域组成，data和cur。也就是说，数组的每一个下标都对应着一个data和一个cur。数据域data是用来存放数据元素，而游标cur相当于单链表的next指针，存放该元素的后继在数组的下标。

我们利用数组描述的链表叫做静态链表，这种方法还被叫做游标实现法。

为了我们方便插入数据，我们会把数组建的大一些，以便有一些空闲空间可以便于插入时不至于溢出。

//线性表的静态链表存储结构
#define MAXSIZE 1000	//假设链表的最大长度是1000
typedef struct
{
    ElemType data;	//数据域
    int cur;	//游标(cursor),为0时表示无指向
}Component,StaticLinkList[MAXSIZE];

我们对数组的第一个元素和最后一个元素作为特殊元素处理，不存数据。我们通常把未被使用的数组元素称为备用链表。数组的第一个元素即为下标为0的元素，它的cur就用来存放备用链表的第一个结点的下标；而数组的最后一个元素的cur则存放第一个有数值的元素的下标，相当于单链表的头结点的作用。

上图相当于初始化的数组状态,实现代码如下

//将一维数组space中各分量链成一备用链表
//space[0].cur为头指针,'0'表示空指针
Status InitList(StaticLinkList space)
{
    int i;
    for(i=0;i<MAXSIZE-1;i++){
        space[i].cur = i+1;
    }
    space[MAXISIZE-1].cur = 0;	//目前静态链表为空，最后一个元素的cur为0
    return OK;
}

假设我们将数据存入静态链表，存放着甲乙丙丁戊己庚等数据。

静态链表的插入操作

静态链表实现插入操作的话解决的问题是：如何模拟静态链表结构的存储空间的分配，需要时申请，无用时释放。

在动态链表中，结点的申请和释放都是使用malloc()和free()两个函数来实现。而在静态链表中，操作的是数组，不存在像动态链表的结点申请和释放问题，所以我们需要自己实现这两个函数来实现插入删除操作。

为了辨明数组中哪些分量未被使用，解决的办法就是将所有未被使过的及已经被删除的分量用游标链成一个备用链表，每当进行插入的时候，就可以从备用链表上取得第一个结点作为待插入的新结点。

//若备用链表非空，则返回分配的结点下标，否则返回为0
int Malloc_SLL(StaticLinkList space)
{
    int i = space[0].cur;    //当前数组第一个元素的cur存的值，i就是返回第一个备用空闲的下标
    if(space[0].cur)		//如果第一个元素的cur存在
        space[0].cur = space[i].cur;	//由于要拿出一个分量来使用，所以我们就得把它的下一个分量用来备用
    return i;
}

以上代码就是下标为7的分量要准备使用了，就得有接替者，所以就把分量为7的cur赋值给头元素，然后接替者就成为了下标为8的分量了。

当我么进行插入的时候，如果新元素丙想插队，想插到乙的后面，我们就先让它在队伍最后一排第七个元素待着。然后接下来我们就做几个步骤：

第一步：我们先去找到“乙”，告诉他，你的cur不是游标为3的丁了，这点小钱你意思意思一下，把你的cur改成游标7就可以了。然后乙收下了钱，把cur值改了。

第二步：回到丙那里，跟丙说把你的cur值改为3，就这样，在绝大多数人不知道的情况下整个队列的次序就发生了改变。

实现代码如下：

//在L中第i个元素之前插入新的数据元素e
Status ListInsert(StaticLinkList L,int i,ElemType e)
{
    int j,k,l;
    k = MAXSIZE - 1;	//这里声明k是最后一个元素的下标
    if(i<1 || i>ListLength(L)+1)
        return ERROR;
    j = Malloc_SSL(L);	//获取空闲分量的下标   这里j=7
    if(j){			//如果有空闲的分量
        L[j].data = e;	//将数据赋值给此分量的data
        for(l=1;l<=i-1;l++){  //找到第i个元素之前的位置
            k = L[k].cur;
        }
        L[j].cur = L[k].cur;	//第i个元素之前的cur赋值给新元素的cur
        L[k].cur = j;		//把新元素的下标赋值给第i个元素之前的元素的cur
        return OK;
    }
    return ERROR;
}

当我们执行语句时，我们的目的是要在“乙”和“丁”之间插入“丙”，调用代码的时候，输入i的值为3。

第4行让k=MAX_SIZE-1 = 999。

第7行，j = Malloc_SSL(L) = 7。此时下标为0的cur也因为7要被占用而更改备用链表的值为8。

第11~12行，for循环l由1到2，执行两次。代码k = L[k].cur;使得k = 999,得到 k =L[999].cur = 1，第二次循环再得到k = L[1].cur = 2。

第13行，L[j].cur = L[k].cur; 因为j=7，而k=2得到 L[7].cur = L[2].cur = 3，这里相当于前面的让丙把它的cur改成3的意思。

第14行，L[k].cur = j；意思就是L[2].cur = 7。这里的意思就是给乙点小费，让它把自己的cur值改为7。

这样就实现了在数组中，实现不移动元素就进行了数据的插入操作。

静态链表的删除操作

此处我们删除甲，然后乙就成为了第一个元素。

和前面一样，我们在删除元素的时候，以前使用free()函数来释放结点，现在我们用另一个方法实现它。

//删除在L中的第i个数据元素e
Status ListDelete(StaticLinkList L,int i)
{
    int j,k;
    if(i<1 || i>ListLength(L))  //如果要删除的第i个元素小于1或者大于L的长度
        return ERROR;
    k = MAX_SIZE - 1;	//k=999
    for(j=1;j<=i-1;j++){	//遍历到要删除的位置
        k = L[k].cur;		//然后k = 1  就是下标为1的结点要被删除(回收)	
    }
    j = L[k].cur;		//j就等于L[999].cur = 1		
    L[k].cur = L[j].cur;	//L[999].cur = L[1].cur   此处相当于头结点指向的的下一个元素是乙的下标，所以乙是第一个元素
    Free_SSl(L,j);	//将下标为k的空闲结点回收到备用链表
    return OK;
}

下面演示Free_SSL(L,j)的操作:

void Free_SSL(StaticLinkList space,int k)   //此处k=1
{
    space[k].cur = space[0].cur;	//把第一个元素cur值赋值给要删除的分量cur
    space[0].cur = k;			//把要删除的分量下标赋值给第一个元素的cur
}

以上的意思就是甲要走了，这个位置就空出来了，如果有新的人来，就优先考虑这个空位置，所以一开始的空位分量，也就是下标为8的分量，它降级了，所以下标为1的分量的cur就是8，而8就是下标为8的分量，也就是下标为1的空位后面是下标为8的空位，space[1].cur = space[0].cur。然后space[0].cur = k = 1,也就是让这个位置成为第一个优先空位，把它存入第一个元素的cur中(下标为0的元素的cur为1)。前后对比图：

前：

后：

1.4.8静态链表的优缺点

1.4.9循环链表

在单链表中，由于每个结点只存储了向后的指针，到了尾指针，就说明链表到底了。当某一结点无法找到它的前驱结点，就像人生一样，无法回到从前。

​ 将单链表中终端结点的指针由空指针改为指向头结点，使得整个单链表形成一个环，这种头尾相接的单链表成为单循环链表，简称循环链表，为了使空链表和非空链表处理一致，我们通常设置一个头结点，当然，这并不是说循环链表就一定需要头结点。

循环链表带有头结点的空链表如下：

循环链表带有头结点的非空链表如下：

其实循环链表和单链表的主要区别就在于循环的判断条件上，原来是判断p->next是否为NULL，现在是判断p->next不等于头结点，则循环未结束。

在单链表中，我们有了头结点的时候，我们可以使用O(1)的时间来访问第一个结点，但是对于访问最后一个结点的话要使用O(n)的时间来访问，因为我们要将单链表全部扫描一遍。

现在有没有用O(1)的时间来访问链表的最后一个?当然可以。

不过我们需要改造一下循环链表，不用头指针，而是用指向终端结点的尾指针来表示循环链表。

终端结点用尾指针用rear表示，所以查找终端结点为O(1)，而开始结点，则用rear->next->next表示，其时间复杂度也为O(1)。

将两个循环链表合并成一个表：

有了尾指针就非常的方便了

p = rearA->next;	//保存A点的头结点   头结点只有一个
rearA->next = rearB->next->next;	//将本是指向B表的第一个结点(不是头结点)赋值给rearA->next
rearB->next = p;	//将原来A表的头结点赋值给B表的第一个结点(不是头结点)
free(p);	//释放p

1.5.0双向链表

在单链表中，有了next指针，这就使得我们查找下一结点的时间为O(1)，可是如果我们要查找上一结点的话，最坏的时间复杂度就变成O(n)了，因为我们每次都要从头开始遍历查找。

为了克服这一缺点，老科学家们设计了双向链表。双向链表(double linked list)是在单链表中的每一个结点，再设置一个指向其前驱结点的指针域。所以双向链表有两个指针域，一个指向直接后继，一个指向直接前驱。

typedef struct DouNode
{
    ElemType data;
    struct DulNode *prior;	//直接前驱指针
    struct DulNode *next;	//直接后继指针
}DulNode,*DuLinkList;

既然单链表有循环列表，那么双向链表也有循环列表。

双向链表循环的带头结点的空链表如下：

双向链表循环的带头结点的非空链表如下：

因为这是双向链表，那么对于链表中的某一个结点p，它的后继的前驱是它自己，它的前驱的后继也是它自己。

p->next->prior = p = p->prior->next

就像人生一样，当你获得了成功，就要付出点代价。双向链表比单向链表多了可以反向遍历查找等数据结构，那么也需要付出一小点代价：在插入和删除时，需要修改两个指针的变量。

双向链表的插入操作

我们现在假设存储元素e的结点为s，现在要实现将结点s插入到结点p和p->next之间需要以下几步：

s->prior = p;	//把p赋值给s的前驱
s->next = p->next;	//把p->next赋值给s的后继
p->next->prior = s;		//把s赋值给p->next的前驱
p->next = s;		//把s赋值给p的后继

以上的顺序是先搞定s结点的前驱和后继，再搞定后结点的前驱，最后解决前结点的后继。

双向链表的删除操作

p->prior->next = p->next;	//把p->next赋值给p->prior的后继
p->next->prior = p->prior;		//把p->prior赋值给p->next的前驱
free(p);	//释放结点

双向链表和单向链表的区别：

双向链表对于单向链表来说，要更复杂一些，毕竟它多了prior指针，对于插入和删除操作来说，需要按着顺序来操作，不然会报错的。由于它的每个结点都需要记录两份指针，所以在空间上要多占一些内存，但是对于某个结点的前后操作，带来了很大的方便，说白了，就是用空间性能来换取时间性能。

总结：

第四章 栈与队列

栈是限定仅在表尾进行插入和删除操作的线性表。

队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表。

1.1栈的定义

在软件应用中，栈这种先进后出的数据结构是很常见的。比如你用浏览器上网的时候，浏览器都有一个后退的按钮，你点击后可以按照你访问的逆顺序加载浏览过的网页，也相当于很多软件的撤销键。

栈(stack)是限定仅在表尾进行插入和删除操作的线性表。

我们把允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表，简称LIFO结构。

栈底是固定的，最先进栈的只能在栈顶。

栈的插入操作，也作进栈，也称压栈、入栈。类似于子弹入弹夹。

栈的删除操作，也作出栈，也有的叫作弹栈。如同弹夹中子弹出夹。

1.2栈的出栈数据类型

对于栈来说，理论上线性表的操作特性它都具备，可由于她的特殊性，所以针对它的操作上会有些变化，特别是插入和删除操作，我们改为push(压)和pop(弹)，就像弹夹的子弹压入和弹出，我们一般称之为进栈和出栈。

ADT 栈(Stack)
Data
    同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
Operation
    InitStack(*S):初始化操作,建立一个空栈S。
    DestroyStack(*S):若栈存在，则销毁它。
    ClearStack(*S):将栈清空。
    StackEmpty(S):若栈为空，则返回ture，否则返回false。
    GetTop(S,e):若栈存在且非空,用e返回S的栈顶元素。
    Push(*S,e):若栈S存在,插入新元素e到栈S中并称为栈顶元素。
    Pop(*S,*e):删除栈S中栈顶元素,并用e返回其值。
    StackLength(S):返回栈S的元素个数。

因为栈本身就是一个线性表，所以线性表的顺序存储和链式存储在栈中同样适用。

1.3栈的顺序存储结构

栈的顺序存储也就是线性表顺序存储的简化，我们称为顺序栈。线性表使用数组来实现的，而对于栈这种只能一头插入删除的线性表来说，用数组的哪一端来作为栈顶和栈底比较好？

答案是下标为0的一端作为栈底比较好，因为首元素都存在栈底，变化量最小，所以让它作为栈底。

我们定义一个top变量用来指示栈顶元素在数组中的位置，而top就像高中游标卡尺的游标，可以来回移动，意味着top可以变大变小，但是无论如何游标不能超出尺的长度。若栈的长度为StackSize，则栈顶位置top必须小于StackSize。当栈中存在一个元素时，top等于0，因此把空栈定义为top = -1。

栈的结构定义：

typedef int SElemType;	//SElemType类型根据实际情况而定,这里设为int。
typedef struct
{
    SElemType data[MAXSIZE];
    int top;	//用于栈顶指针
}SqStack;

若现在有一个栈，StackSize是5，则栈普通情况、空栈和栈满的情况示意图如下：

1.3.1进栈操作-push

栈的插入，即进栈操作：

实现代码如下：

//插入新元素e为新的栈顶元素
Status Push(SqStack *S,SElemType e)
{
    if(S->top == MAXSIZE-1){	//栈满,已经不能插入新元素了
        return ERROR;
    }
    S->top++;	//栈顶指针+1
    S->data[S->top] = e;	//将新插入元素赋值给栈顶空间
    return OK;
}

1.3.2出栈操作-pop

实现代码如下：

//若栈不空,则删除S的栈顶元素,用e返回其值,并返回Ok,否则返回ERROR
Status Pop(SqStack *S,SElemType *e)
{
    if(S->top == -1){	//空栈
        return ERROR;   
    }
    *e = S->data[S->top];	//将要删除的元素赋值给e
    S->top--;	//栈顶指针-1
    return OK;
}

两者没有涉及到任何循环语句，所以时间复杂度均为O(1)。

1.3.3两栈共享空间

当我们有两个相同类型的栈，我们为它们各自开辟了数组空间，极有可能第一个栈已经满了，再进栈就溢出了，而另一个栈还有很多的存储空间空闲。这个时候，我们完全可以用一个数组来存储两个栈，只不过需要点小技巧。

思路：数组有两个端点，两个栈有两个栈底，让一个栈的栈底成为数组的始端，即下标为0处，另一个栈的栈底为数组的末端，即下标为数组长度n-1处。如此一来，两个栈如果增加元素，就是两端点向中间延伸。

栈1为空时：top1 = -1

栈2空时：top2 = n

当极端情况下：若栈2是空栈，栈1的top 等于 n-1 的时候，就是栈1满的时候。

当栈1为空栈的时候，栈2的top2 = 0时，为栈2满。

所以当两栈见面之时，也就是两个指针相差1时，top1 + 1 == top2为栈满。

两栈共享空间的代码如下：

//两栈共享空间结构
typedef struct
{
    SElemType data[MAXSIZE];
    int top1;	//栈1栈顶指针
    int top2;	//栈2栈顶指针
}SqDoubleStack;

对于两栈共享空间的push方法，我们除了要插入元素值参数外，还需要有一个判断是栈1还是栈2的参数stackNumber。

插入的代码如下：

//插入元素e为新的栈顶元素
Status Push(SqDoubleStack *S,SElemType e,int stackNumber)
{
    if(S->top1+1 == S->top2){	//栈已满,不能再push新元素了
        return ERROR;
    }
    if(stackNumber == 1){	//栈1有元素进栈
        S->data[++S->top1] = e;		//若栈1则先top1+1后给数组元素赋值   ++S:前自增
    }else if(stackNumber == 2){
        S->data[--S->top2] = e;		//若栈2则先top2-1后给数组元素赋值	--S:前自减
    }
    return OK;
}

两栈共享空间的pop方法：

//若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR
Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber)
{
    if(stackNumber == 1){	//栈1
        if(S->top1 == -1)
            return ERROR;	//说明栈1是空栈,溢出
        *e = S->data[S->top1--];	//将栈1的栈顶元素溢出
    }else if(stackNumber == 2){		//栈2
        if(S->top == MAXSIZE)
            return ERROR;	//说明栈2已经是空栈,溢出
        *e = S->data[S->top2++];	//将栈2的栈顶元素出栈
    }
}

使用两栈共享空间什么时候最有意义呢，就是一个栈在增长，一个栈在缩短的情况才是最有意义的。如果两个栈都在不停的增长，那么很快就会因为栈满而溢出，所以是没有多大意义的。

1.4栈的链式存储结构及实现

1.4.1栈的链式存储结构

栈的链式存储结构，简称链栈。

栈只是用栈顶进行插入和删除操作，而在链表中，因为单链表有头指针，而栈顶指针也是必须的，所以应该把它两进行合二为一，所以比较好的办法就是把栈顶放在单链表的头部(如下图)。另外已经有栈顶在头部了，所以单链表常用的头结点也就失去了意义，对链栈来说，是不需要头结点的。

对于空栈来说，链表原定义是头指针指向为空，那么链栈的空其实就是top = NULL的时候。

链栈的结构代码如下：

typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;
}StackNode,*LinkStackPtr;

typedef struct LinkStack
{
    LinkStackPtr top;
    int count;
}LinkStack;

1.4.2栈的链式存储结构—-进栈操作

对于链栈的push操作，假设元素值为e的新结点是s，top为栈顶指针，则：

实现代码如下：

//插入新元素e为新的栈顶元素
Status Push(LinkStack *S,SElemType e)
{
    LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));		//为新结点s分配内存
    s->data = e;
    s->next = S->top;	//把当前的栈顶元素赋值给新结点的直接后继
    S->top = s;		//将新结点s赋值给栈顶指针
    S->counter++;	//增加元素后链栈自增
    return OK;
}

1.4.3栈的链式存储结构—出栈操作

链栈的出栈pop操作，也是很简单的三句操作。假设变量p用来存储要删除的栈顶结点，将栈顶指针下移一位，最后释放p即可。

实现代码如下：

//若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR
Status Pop(LinkStack *S,SElemType *e)
{
    LinkStackPtr p;
    if(StackEmpty(*S))	//如果栈为空
        return ERROR;
    *e = S->top->data;
    p = S->top;		//将栈顶结点赋值给p
    s->top = S->top->next;	//使得栈顶指针下移一位,指向后一结点
    free(p);		//释放结点p
    S->count--;		//删除元素后链栈减1
    return OK;
}

链栈的出栈pop和入栈push操作都很简单，没有任何循环操作，时间复杂度均为O(1)。

对比一下顺序栈和链栈的区别：如果栈的使用过程中元素变化不可预料，有时很小，有时很大，那么最好用链栈，反之，如果它的变化在可控制范围内，建议使用顺序栈更好一些。

1.5栈的应用–递归

栈是一个很重要的应用：在程序设计中使用了递归。递归在我这来说就是套娃。比如函数本身不断地调用它自己。

接下来我将区别递归函数与非递归函数实现一个东西的区别：

解决斐波那契数列的迭代算法：

int main()
{
    int i;
    int a[40];
    a[0] = 0;
    a[1] = 1;
    printf("%d",a[0]);
    printf("%d",a[1]);
    for(i=2;i<40;i++){
        a[i] = a[i-1] + a[i-2];
        printf("%d",a[i]);
    }
    return 0;
}

解决斐波那契数列的递归算法：

int Fbi(int i)
{
    if(i<2)
        return i == 0 ? 0:1;	//三目运算符,先计算i==0,如果为真则第一个参数为true,否则第一个参数为false
    return Fbi(i-1) + Fbi(i-2);		//这里的Fbi函数就是它自己,它在自己调用自己
}

int main()
{
    int i;
    for(int i=0;i<40;i++)
        printf("%d",Fbi(i));
    return 0;
}

相比于迭代的代码，递归是不是干净很多。

下图模拟代码中的Fbi(i)函数当i=5时的执行过程：

1.5.1递归定义

一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，成为递归函数。

递归和迭代的区别：

迭代使用的是循环结构，递归使用的是选择结构。递归能使程序的结构更清晰、更简洁、更让人容易理解。但是大量的递归调用会建立函数的副本，会耗费大量的时间和内存。迭代则不需要反复调用函数和占用额外的内存。因此应该要看不同的情况使用不同的方法。

递归和栈的关系：

​ 在前面我们看到的是递归如何执行它的前进退回阶段。递归过程退回的顺序是它前行顺序的逆序。在退回过程中可能要执行某些当作，包括恢复在前行过程中存储起来的某些数据。

​ 这种存储某些数据，并又在后面以存储的逆序恢复这些数据，以提供之后使用的需求，显然很符合栈这种数据结构。

​ 简单的说，就是在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。

1.6栈的应用–四则运算表达式求值

计算机处理通常的标准(中缀)表达式的能力，最重要的就是两步：

1.将中缀表达式转化为后缀表达式(栈用来进出运算的符号)。

2.将后缀表达式进行运算得出结果(栈用来进出运算的数字)。

以上两步实现过程参考大话数据结构105页。

1.7队列的抽象数据类型

同样是线性表，队列也有类似线性表的各种操作，不同的就是插入数据只能在队尾进行，删除数据只能在队头进行。队列也身为一种特殊的线性表，所以也有顺序存储结构和链式存储结构。

ADT 队列(Queue)
Data
    同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
Operation
    InitQueue(*Q):初始化操作,建立一个空队列Q。
    DestroyQueue(*Q):若队列Q存在,则销毁它。
    ClearQueue(*Q):将队列Q清除。
    QueueEmpty(*Q):若队列Q为空,则返回ture,否则返回false。
    GetHead(*Q,*e):若队列Q存在且非空,用e返回队列Q的对头元素。
    EnQueue(*Q,e):若队列Q存在,插入新元素e到队列Q中并成为队尾元素。
    DeQueue(*Q,*e):删除队列Q中对头元素,并用e返回其值。
    QueueLength(Q):返回队列Q的元素个数。
EndADT

1.7.1循环队列

1.7.1.1队列顺序存储的不足

假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端即是队头。

​ 插入队列操作，就是在队列的队尾插入，不需要移动任何元素。时间复杂度为O(1)。

与栈不同的是，队列元素的出栈是在队头，即下标为0的位置，也就意味着，进行出队操作的话，队列中的所有元素都要向前移动，以保证队的列头不为空(也就是下标为0处)。

另一种方法：为了避免出队列时所有元素都要移动，所以设置队头不一定要在下标为0处：

为了避免只有一个元素时候,队头队尾重合的话使得处理变得麻烦，所以引入两个指针，front指针指向队头元素，rear指针指向队尾元素的下一位置，当front=rear的时候，队列为空。

下面有个上述方法的问题例子：

假设数组长度为5的数组，初始状态为下图，front和rear指针均指向下标为0的位置。

然后开始进行入队列a1,a2,a3,a4，front指针依然指向下标为0的位置，而rear指针指向下标为4的位置：

然后出队a1,a2，则front指针指向小标为2的位置,rear指针不变：

然后入队a5，此时front指针不变，rear指针移动到数组之外，嗯？数组之外将是哪里？我们称此现象为“假溢出”。

1.7.1.2循环队列定义

为了解决假溢出的办法就是后面满了，就从头开始，也就是头尾相接的循环。我们把这种队列的这种头尾相接的顺序存储结构称为循环队列。

继续以上的例子，我们把rear改为下标为0的位置：

然后接着入队a6，将它放置下标为0处，rear指针指向下标为1处：

此时接着再入队a7，则rear指针和front指针重合，同时指向下标为2的位置：

此时问题来了：

• 我们刚才所说，空队列时，front等于rear。而现在当队列满时，也就是front=rear时，如何判断队列究竟是空还是满？
• 方法1：设置一个标志变量flag，当front == rear,且flag=0时候为队列空，当front == rear,且flag=1时为队列满。
• 方法2：当队列为空时，条件就是front = rear，现在当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。比如下图，此时就认为队列已经满了。

我们来重点讨论第二种方法，由于rear可能比front大，也可能比front小，所以尽管它们只相差一个位置就是满的情况，但也可能相差整整一圈。所以若队列最大尺寸为QueueSize，那么队列满的条件是(rear+1)%QueueSize == front。

比如上面的例子：QueueSize=5，以上左图中，front=0，而rear=4，(4+1)%5 == 0；所以此时队列满。在以上右图中，front=2，rear=1，(1+1)%5=2，所以此时队列也是满的。

另外：

​ 当rear>front的时候，此时的队列长度为rear-front。如以上左图,rear-front = 4-0 = 4(队列长度)。

​ 当front>rear的时候，队列长度分别为两段,一段是QueueSize-front，另一段是0+rear。加在一起，队列长度为rear-front+QueueSize。如上右图，rear-front+QueueSize = 1-2+5 = a(队列长度)。

因此，通用的计算队列长度的公式为：(rear-front+QueueSize)%QueueSize

循环队列的顺序存储结构：

typedef int QElemType;		//QElemType类型根据实际情况而定,这里假设为int
typedef struct
{
    QElemType data[MAXSZIE];
    int front;	//头指针
    int rear;	//尾指针,若队列不空,指向队列尾元素的下一个位置
}SqQueue;

循环队列的初始化代码如下：

//初始化一个空队列Q
Status InitQueue(SqQueue *Q)
{
    Q->front = 0;	//头指针指向下标为0的位置
    Q->rear = 0;	//尾指针指向下标为0的位置
    return OK;
}

循环链表求队列长度的代码如下：

//返回Q的元素个数,也就是队列的当前长度
int QueueLength(SqQueue Q)
{
    return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}

循环队列的入队操作如下：

//若队列未满，则插入元素e为Q新的队尾元素
Status EnQueue(SqQueue *Q,QElemType e)
{
    if((Q->rear+1)%MAXSIZE == Q->front)		//当前队列已满
        return ERROR;
    Q->data[Q->rear] = e;	//将元素e赋值给队尾
    Q->rear = (Q->rear+1)%MAXSIZE;	//rear指针向后移一个位置,若到最后则转到数组头部
    return OK;
}

循环队列的出队操作如下：

//若队列不空,则删除Q中对头元素,用e返回其值
Status DeQueue(SqQueue *Q,QElemtype *e)
{
    if(Q->front == Q->rear){	//若队列为空
        return ERROR;
    }
   *e = Q->data[Q->front];	//将队头元素赋值给e
    Q->front = (Q->front+1)%MAXSIZE;	//front指针向后移动一个位置,若到最后,则转到数组头部
    return OK;
}

1.7.2队列的链式存储结构及实现

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它称为链队列。

我们将队列头指针指向链队的头结点，而队尾指针指向终端结点。

空队列时，front和rear都指向头结点。

链队列的结构为：

typedef int QElemType;	//QElemType类型根据实际情况而定,这里假设为int
typedef struct QNode	//结点结构
{
    QElemType data;		//数据域
    struct QNode *next;		//指针
}QNode,*QueuePtr;

typedef struct		//队列的链表结构
{
    QueuePtr front,rear;	//队头,队尾指针
}LinkQueue;

1.7.2.1队列的链式存储结构–入队操作

入队操作时就是在链表尾部插入结点：

实现代码如下：

//插入元素e为队列Q的新队尾元素
Status EnQueue(LinkQueue *Q,QElemType e)
{
    QueuePtr s = (QueuePtr)malloc(sizeof(QNode));	//为新结点分配空间
    if(!s)	//如果分配存储失败
        exit(OVERFLOW);	//内存溢出
    s->data = e;
    s->next = NULL;
    Q->rear->next = s;	//把拥有元素e新结点s赋值给原队尾结点的后继
    Q->rear = s;	//把新插入的结点s设置为队尾结点,rear指向s
    return OK;
}

1.7.2.2队链的链式存储结构–出队操作

出队操作时，就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需将rear指向头结点。

实现代码如下：

Status DeQueue(LinkQueue *Q,QElemType *e)
{
    QueuePtr p;		//声明结点p
    if(Q->front == Q->rear)		//若队列为空
        return ERROR;
    p = Q->front->next;	//将要删除的队头结点暂存给p
    *e = p->data;	//将要删除的队头结点的值赋值给e
    Q->front->next = p->next;	//将原队头结点后继p->next赋值给头结点后继
    if(Q->rear == p)		//若队头是队尾,则删除后将rear指向头结点,如上图的右图
        Q->rear = Q->front;		//则队列为空
    free(p);	//释放p结点
    return OK;
}

1.7.2.3循环队列跟链队的比较

对于循环队列和队链的比较，可以从两方面来考虑。

从时间上：

​ 它们的基本操作的时间复杂度都为O(1)，不过循环队列是事先申请好空间，使用期间不释放。而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，如果入队出队频繁的话，不适合使用链队列。

从空间上：

​ 循环队列必须有一个固定的长度，所以存储元素个数和空间浪费是个问题。而队列不能在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受，所以在空间上，链队列更加灵活。

总的来说，在确定队列长度最大值的情况下，建议用循环队列，如果无法预估队列的长度时，则用链队列。

第五章 串

串(string)是由零个或多个字符串组成的有限序列，又叫字符串。

1.1串的定义

串也就是字符串，s=”a1a2a3….an”(n>=0)，其中s是字符串的名称,n是字符串的长度。

1.2串的抽象数据类型

串的逻辑结构跟线性表很像，不同之处是在于串针对的是字符集，也就是串中的元素都是字符。线性表更关注的是单个元素的操作，比如查找一个元素，插入或删除一个元素。但串中更多的是查找子串位置，得到指定位置子串、替换子串等操作。

ADT 串(string)
Data
    串中元素仅由一个字符组成,相邻元素具有前驱和后继关系。
Operation
    StrAssign(T,*chars):生成一个其值等于字符串常量chars的串T。
    StrCopy(T,S):串S存在,由串S复制得到串T。
    ClearString(S):串S存在,将串清空。
    StringEmpty(S):若串S为空,返回true,否则返回false。
    StrLength(S):返回串S的元素个数,即串的长度。
    StrCompare(S,T):若S>T,返回值>0,若S=T,返回0,若S<T,返回值小于0。
    Concat(T,S1,S2):用T返回由S1和S2连接而成的新串。
    SubString(Sub,S,pos,len):串S存在,1<=pos<=StrLength(S),且0<=len<=StrLength(S)-pops+1,用sub返回串S的第pos个字符起长度为len的子串。
    Index(S,T,pos):串S和T存在,T是非空串,1<=pos<=StrLength(S)。若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置,否则返回0。
    Replace(S,T,V):串S、T和V存在,T是非空串。用V替换主串S中出现的所有与T相等的不重叠的子串。
    StrInsert(S,pos,T):串S和T存在,1<=pos<=StrLength(S)+1。在串S的第pos个字符之前插入串T。
    StrDelete(S,pos,len):串S存在,1<=pos<=StrLength(S)-len+1。从串S中删除第pos个字符起长度为len的子串。
endADT

我们来看一个简单的Index的实现算法。

例子：

主串:S => getusername

子串:T => username

//T为非空串。若主串S中第pos个字符之后存在与T相等的子串,则返回第一个这样的子串在S中的位置,否则为0。
int Index(String S,String T,int pos)
{
    int n,m,i;
    String sub;
    if(pos>0){
        n = StrLength(S);	//得到主串S的长度		11
        m = StrLength(T);	//得到子串T的长度		8
		i = pos;	//i=3
        while(i<=n-m+1)	 //3<=11-8+1	
        {
            SubString(sub,S,i,m);		//取主串S第i个位置,长度与T相等子串给sub
            if(StrCompare(sub,T) != 0){			//如果两串不相等
                ++i;
            }else{
                return i;	//i=4
            }
        }
    }
    return 0;		//若无子串与T相等,返回0
}

1.3串的存储结构

串的存储结构分为两种：串的顺序存储结构和串的链式存储结构。

1.3.1串的顺序存储结构

串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。一般是用定长数组来定义。

因为串的数组长度是固定的，所以在进行一些字符串的操作的时候，比如两串的连接Concat、新串的插入StrInsert，以及字符串的替换Replace，都有可能使得串序列的长度超过数组的长度MAXSIZE。

所以对于串的顺序存储，有一些变化，串值的存储空间可在程序执行过程中动态分配而得。比如在计算机中存在一个自由存储区，叫‘堆’。这个堆可由C语言的动态分配函数malloc()和free()来管理。

1.3.2串的链式存储结构

对于串的链式存储结构，与线性表是相似的，出于性能考虑，串的一个结点可存放多个字符，最后一个结点若是未被占满时，可以用“#”或其它非值字符补全，如下图：

当然，这里一个结点存多少个字符才合适变得很重要，这会直接影响着串处理的效率。

串的链式存储结构除了在连接串与串操作时有一定的方便之外，总的来说是不如顺序存储灵活，性能也不如顺序存储结构好。

1.4朴素的模式匹配算法

当我们查找一个单词在一篇文章出现的频率，就是相当于你在大字符串中定位子串的问题。这种子串的定位操作通常称做串的匹配模式，也就是串中最重要的操作之一。

假设我们要从下面的主串S=”goodgoogle”中，找到T=“google”这个子串的位置。我们通常要需要以下步骤：

1.主串S第一位开始，S与T前三个字母都匹配成功，但S第四个字母是d而T的是g。第一位匹配失败。

2.主串S第二位开始，主串S首字母是o，要匹配的T的首字母是g，匹配失败。

3.主串S第三位开始，主串S首字母是O，要匹配的T首字母是g，匹配失败。

4.如此依次下去，这里我直接显示最后结果。

主串S第五位开始，S与T，6个字母全匹配，匹配成功。

简单的说，就是对主串的每一个字符作为子串的开头，与要匹配的字符串进行匹配。对主串做大循环，每个字符开头做T的长度的小循环，直到匹配成功或全部遍历完成为止。

前面我们已经用串的其他操作实现了模式匹配算法Index。现在考虑不用串的其他操作，而是只用基本的数组来实现同样的算法。注意我们假设主串S和要匹配的子串T的长度存在S[0]与T[0]中。

代码实现如下：

//返回子串T在主串S中第pos个字符之后的位置。若不存在，则用函数返回0。T非空,1<=pos<=StrLength(S)。
int Index(String S,String T,int pos)
{
    int i = pos;	//i用于主串S中当前位置下标,若pos不为1,则从pos位置开始匹配
    int j = 1;		//j用于子串T当前位置下标值
    while(i<=S[0] && j<=T[0])	//若i小于S长度且j小于T的长度时循环
    {
        if(S[i] == T[j]){	//两字母相等则继续
        	++i;
            ++j;
        }else{		//指针后退重新开始匹配
            i = i-j+2;	//i退回到上次匹配首位的下一位
            j = 1;		//j退回到子串T的首位
        }	
        
    }
    if(j > T[0])		//相当于匹配成功
        return i-T[0];		//返回pos的值
    else
        return 0;
}

分析以下，最好的情况是什么？那就是一开始匹配成功，比如”googlegood”中去找”google”，时间复杂度为O(1)。如果在”abcdefgoogle”中去找”google”，那么时间复杂度为O(n+m)，其中n为主串长度，m为要匹配的子串长度。根据等概率原则，平均是(n+m)/2次查找，时间复杂度为O(n+m)。

但是会遇到糟糕的情况，比如主串S=”000000000000000000000000000000000000000000000000000001”,而要匹配的子串T=”000000001”,前者49个”0”和1个”1”的主串，后者是9个”0”和1个”1”的子串。在匹配时,每次都将消耗大量的时间复杂度，所以说，这个朴素的模式匹配算法的效率太低了。

1.5KMP模式匹配算法

为了解决朴素模式匹配算法的低效，科学家们发表了一个模式匹配算法，可以大大避免重复遍历的的情况，我们把它称之为KMP算法。

1.5.1KMP匹配算法原理

前言：人生就像要KPM算法，好马不吃回头草。

主串S=”abcdefgab”,子串T=”abcdex”

​ 如果我们要匹配子串T，如果用前面的朴素算法，匹配模式如下：

​

​ 此处按照朴素匹配模式算法，就如上图中的流程23456步骤的，首字符与子串T的首字符不相等。

似乎这也是理所当然的，因为算法就是这样设计的。接下来使用KPM算法的思路：

对于要匹配的子串T来说，子串”abcdex”首字母a与后面的串”bcdex”任意一字符都不相等。也就是说既然”a”不与后面的子串的任意一字符相等，对于以上图中的第一个步骤来说，因为主串和子串前五位字符分别相等，意味着子串T的首字符”a”不可能与S串中第2—5位的字符相等的。所以以上图中的第2345个步骤都是多余的。

因为我们知道T串中首字符”a”与T串的后面字符均不相等，然而在第一步骤中判断出来主串和子串前五步分别相等，所以省去朴素匹配模式算法的2345步骤的匹配，所以只保留1和6步骤的判断即可。

以上就是KPM算法的第一种情况。

第二种情况：

​ 假设S=”abcabcabc”，T=”abcabx”。

​ 下图将是朴素匹配模式算法：

​

下面将用KPM算法的思路来解决：

因为主串S与子串T的前五位字符分别相等，根据刚才的思路，T串中的首字符”a”与T串中第二位字符”b”和第三位字符”c”均不等,所以不需要判断，所以以上的2和3步骤是不需要判断的。

因为T的首字符”a”与T的第四位”a”相等，第二位的”b”与第五位的”b”相等。而在第1步骤中，第四位的”a”与第五位的”b”已经与主串S中的相应位置比较过了，是相等的，因此可以断定，T的首字符”a”,第二位字符”b”与S的第四位字符和第五位字符也不需要比较了。所以以上的4和5步骤是不需要判断的。

所以只需要判断1和6步骤即可。

在朴素匹配模式算法中，主串i的值是不断地回溯匹配的，而在KMP算法中，这种回溯是完全不需要的——正所谓好马不吃回头草，KPM算法就是为了这种没必要的回溯不发生的。既然i值不回溯，也就是不可以变小，那么现在要考虑变化的j值。子串的j值与主串是没有任何关系的，我们屡屡提到了T串的首字符与自身后面的字符的比较，如果发现有相等的字符，j值的变化就会不相同。关键就取决于于T串的结构中是否有重复的问题。

在上图中由于T=”abcabx”，前缀的”ab”与最后的”x”之前串的后缀”ab”是相等的。因此j=6就变成了j=3。我们可以得出规律，j值的多少取决于当前字符之前的串的前后缀的相似度。

我们把T串各个位置的j值的变化为一个数组next，那么next的长度就是T串的长度。

next数组值推导

例子1：

• T = “abcdex”，如下表：

  j	123456
  模式串T	abcdex
  next	011111

1)当j=1时，next[1] = 0;

2)当j=2时，j由1到j-1就只有字符”a”，属于其他情况next[2] = 1；

3)当j=3时，j由1到j-1串是”ab”，显然”a”与”b”不相等，属于其他情况，属于其他情况，next[3] = 1；

4)以后同理，所以最终此T串的next[J]为011111。

例子2:

• T=”abcabx”,如下表：

  j	123456
  模式串T	abcabx
  next[j]	011123

1)当j=1时，next[1] = 0;

2)当j=2时，next[2] = 1;

3)当j=3时，next[3] = 1;

4)当j=4时，next[4] = 1;

5)当j=5时，此时j由1到j-1的串是”abca”，前缀字符”a”与后缀字符”a”相等，因此可推出k的值为2，因此next[5]=2;

6)当j=6时，j由1到j-1的串是”abcab”,由于前缀字符”ab与后缀字符”ab”相等,所以next[6] = 3；

我们可以得出如果前后缀一个字符相等，k值为2，两个字符k值是3，n个相等k值就是n+1。

例子3：

• T = “ababaaaba”,如下表：

j	123456789
模式串T	ababaaaba
next[J]	011234223

1)当j=1时，next[1] = 0;

2)当j=2时，next[2] = 1;

3)当j=3时，next[3] = 1;

4)当j=4时，j由1到j-1的串是”aba”,前缀字符”a”与后缀字符”a”相等，next[4] = 2;

5)当j=5时，j由1到j-1的串是”abab”，由于前缀字符”ab”与后缀字符”ab”相等相等,所以next[5] = 3;

6)当j=6时，j由1到j-1的串是”ababa”，由于前缀字符”aba”与后缀字符”aba”相等，所以next[6] = 4;

7)当j=7时，j由1到j-1的串是”ababaa”,由于前缀字符”a”与后缀字符”a”相等,所以next[7] = 2;

8)当i=8时，j由1到j-1的串是”ababaaa”,由于前缀字符”a”与后缀字符”a”相等,所以next[8] = 2;

9)当i=9时，j由1到j-1的串是”ababaaab”,由于前缀字符”ab”与后缀字符”ab”相等,所以next[9] = 3;

例子4：

• T=”aaaaaaaab”,如下表：

j	123456789
模式串T	aaaaaaaab
next[j]	012345678

1)当j=1时，next[1] = 0;

2)当j=2时,next[2] = 1;

3)当j=3时,j由1到j-1的串是”aa”,前缀字符”a”与后缀字符”a”相等,next[3] = 2;

4)当j=4时,由1到j-1的串是”aaa”,前缀字符”aa”与后缀字符”aa”相等,next[4] = 3；

5)………

6)当j=9时,由1到j-1串是”aaaaaaaa”,由于前缀字符”aaaaaaa”与后缀字符”aaaaaaa”相等,所以next[9] = 8;

1.5.2KMP模式匹配算法实现

//通过计算返回子串T的next数组
void get_next(String T,int *next)
{
    int i,j;
    i=1;
    j=0;
    next[1] = 0;
    while(i<T[0]){		//此处T[0]表示串T的长度
        if(j == 0 || T[i] == T[j]){		//T[i]表示后缀的单个字符,T[j]表示前缀的单个字符
            ++i;
            ++j;
            next[i] = j;
        }else{
            j = next[j];	//若字符不相同,则j值回溯
        }
    }
}

以上代码主要计算出当前要匹配的串T的next数组。

//返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数返回值为0。
//T非空,1<=pos<=StrLength(S)。
int Index_KMP(String S,String T,int pos)
{
    int i = pos;	//i用于主串S当前位置下标值,若pos不为1,则从pos位置开始匹配
    int j = 1;		//j用于子串T中当前位置下标值
    int next[255];	//定义next数组
    get_next(T,next);	//对串T作分析,得到next数组
    while(i<=S[0] && j<= T[0])	//若i小于S的长度且j小于T的长度时,循环接续
    {
        if(j==0 || S[i] == T[j])	//两字母相等则继续
        {	
            ++i;
            ++j;
        }else{		//指针后退重新开始匹配
            j = next[j];	//j返回合适的位置,i值不变
        }
    }
    if(j > T[0])
        return i-T[0];
    else
        return 0;
}

以上对于get_next函数，若T的长度为m，因只涉及到简单的单循环，其时间复杂度为O(m)，而由于i值不回溯，使得index_KMP算法得到了提高，while循环的时间复杂度为O(n)，因此整个算法的时间复杂度为O(n+m)。相较于朴素模式匹配算法的O((n-m+1)*m)来说，效率更高一些。

​ 但是KMP算法仅当模式与主串之间存在许多”部分匹配”的情况下才能体现出它的优势，否则两者差异不大。

1.5.2KMP模式匹配算法改进

其实KPM算法还是有缺陷的。比如，如果我们的主串S=”aaaabcde”，子串T=”aaaaax”,其next数组值分别为012345，在开始时，当i=5，j=5时，我们发现”b”与”a”不相等,如下图的1步骤，因此j=next[5]=4，如下图2步骤，此时”b”与第四位置的”a”依然不等，j= next[4] = 3，如下图的第三步骤，后依次是4和5步骤，直到j = next[1] = 0时，根据算法,此时i++,j++，得到i = 6,j = 1，如下图的第六步骤。

于是我们发现，2345步骤都是多余的判断。由于T串的第二三四五位置的字符都与首位的”a”相等，那么可以用next[1]的值去取代与它相等的字符后续next[j]的值，这是个很好的办法。因此我们对next函数进行了改良。

假设取代的数组为nextval，代码如下：

//求模式串T的next的函数修正值并存入数组nextval
void get_nextval(String T,int *nextval)
{
    int i,j;
    i = 1;
    j = 0;
    nextval[1] = 0;
    while(i<T[0])		//此输T[0]代表串T的长度
    {
        if(j == 0 || T[i] == T[j])	//	T[i]表示后缀的单个字符,T[j]表示前缀的单个字符
        {
            ++i;
            ++j;
            if(T[i] != T[j]){	//若当前字符与前缀字符不同
                nextval[i] = j;		//则当前的j为nextval在i位置的值
            }else{
                nextval[i] = nextval[j];	//如果与前缀字符相同,则将前缀字符的nextval值赋值给nextval在i位置的值
            }
        }else{
            j = nextval[j];		//若字符不同,则j值回溯
        }
    }
}

实现算法,只需将”get_next(T,next);”改为”get_next(T,next)”。

nextval数组值推导

例子1：

• T=”ababaaaba”，如下表:

j	123456789
模式串T	ababaaaba
next[j]	011234223
nextval[j]	010104210

1)当j=1时，nextval[1] = 0;

2)当j=2时，因第二位字符”b的next”值是1,而第一位就是”a”,它们不相等,所以nextval[2] = next[2] = 1，维持原值。

3)当j=3时，因为第三位字符”a”的next值为1，所以与第一位的”a”比较得知它们相等，所以nextval[3] = nextval[1] = 0;如下图所示：

4)当j=4时，第四位的字符”b”的next值为2，所以与第二位的”b”相比得到的结果是一样的，因此nextval[4] = nextval[2] = 1,如下图所示：

5)当j=5时，next的值为3，第五个字符”a”与第三个字符”a”相等,因此nextval[5] = nextval[3] = 0;

6)当j=6时，next的值为4，第六个字符”a”与第四个”b”不相等,因此nextval[6] = 4;

7)当j=7时，next的值为2，第七个字符”a”与第二个字符”b”不相等,因此netxval[7] = 2;

8)当j=8时，next的值为2，第八个字符”b”与第二个字符”b”相等，因此nextval[8] = nextval[2] = 1;

9)当j=9时，next的值为3，第九位字符”a”与第三个字符”a”相等，因此nextval[9] = nextval[3] = 0;

例子2：

• T=”aaaaaaaab”

j	123456789
模式串T	aaaaaaaab
next[j]	012345678
nextval[j]	000000008

1)当j=1时，nextval[1] = 0；

2)当j=2时，next的值为1，第二个字符与第一个字符相等，所以nextval[2] = nextval[1] = 0；

3)同样道理,到j=8都是nextval[j]的值都为0；

4)当j=9时，next的值为8，第九个字符”b”与第八个字符”a”不相等，所以nextval[9] = 8。

总结：

​ 经过改良的KMP算法，它是在计算出next的值的同时，如果a字符与它next的值指向的”b”字符相等的话,则a位的nextval就指向b位nextval值，如果不相等的话a位的nextval值就是它自己next的值。

第六章 树

1.1树的定义

​ 树(tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中：(1)有且只有一个特定的称为根(root)的结点；(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2、……、Tn，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。

树：

子树：

这里要注意的是子树的个数没有限制，但是子树与子树之间一定是互不相交的。

1.2结点分类

​ 树的结点包含一个数据元素及若干个指向其子树的分支。结点拥有的子树数量称为结点的度(Degree)。度为0的结点称为叶结点(leaf)或终端结点；度不为0的结点称为非终端结点或分支结点。

1.3线性表与树的结构区别

1.4树的抽象数据类型

ADT 树(tree)
Data
    树是由一个根结点和若干颗子树构成的。树中结点具有相同数据类型及层次关系
Operation
    InitTree(*T):构造空树T。
    DestroyTree(*T):销毁树T。
    CreateTree(*T,definition):按definition中给出树的定义来构造树。
    ClearTree(*T):若树T存在,则将树T清为空树。
    TreeEmpty(T):若树T为口树,则返回true,否则返回false。
    TreeDepth(T):返回树T的深度。
    Root(T):返回T的根结点。
    Value(T,cur_e):cur_e是树T中的一个结点,因此返回此结点的值。
    Assign(T,cur_e,value):给树T的结点cur_e赋值为value。
    Parent(T,cur_e):若cur_e为树T的非根结点,则返回它的双亲,否则返回空。
    LeftChild(T,cur_e):若cur_e是树的非叶结点,则返回它的最左孩子,否则返回空。
    RightSibling(T,cur_e):若cur_e有右兄弟,则返回它的右兄弟,否则空。
    InsertChild(*T,*p,i,c):其中p指向树T的某个结点,i为所指结点p的深度加上1,非空树c与T不相交,操作结果为插入c为树中p指结点的第i棵子树。
    DeleteChild(*T,*p,i):其中p指向树T的某个结点,i为所指结点p的度,操作结果为删除T中p所指结点的第i棵子树。
    
endADT

1.5树的存储结构

树的存储结构有三种：双亲表示法、孩子表示法、孩子兄弟表示法。

1.5.1双亲表示法

树除了根结点之外，其余的每个结点，它不一定有孩子，但是一定有且只有一个双亲。

我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。

其中data是数据域，存储着结点的数据信息。而parent是指针域。存储该结点的双亲在数组中的下标。

双亲表示法的结点结构代码如下：

//树的双亲表示法结点结构定义
#define MAX_TREE_SIZE 100
typedef int TElemType;		//树结点的数据类型,目前暂定为整型
typedef struct PTNode		//结点结构
{
    TElemType data;		//结点数据
    int parent;			//双亲位置
}PTNode;

typedef struct		//树结构
{
    PTNode nodes[MAX_SIZE];		//结点数组
    int r,n;		//根的位置和结点数
}PTree;

因为根结点是没有双亲的，所以我们约定根结点的位置域设置为-1(也就是数组中的第一位)，也就意味着，所有结点都有它们的双亲的位置。

图形结构如下：

以上的存储结构，可以根据结点的parent指针就很容易找到它的双亲结点，所用的时间复杂度为O(1)，知道parent为-1时，表示找到了树结点的根。但是如果我们想要找结点的孩子是什么，要遍历整个结构才行。

当然也有解决办法，就是增加一个结点最左边孩子的域，如果没有这个结点就为-1。

1.5.2孩子表示法

由于树中每个结点可能有很多子树，可以考虑使用多重链表，即每个结点有很多个指针域，其中每个指针指向一棵子树的根结点，我们把这种方法叫做多重链表表示法。由于树的每个结点的度，也就是它的孩子的个数是不同的，所以有两种方案来解决。

• 方案1：

  树有几个度就有几个指针域：

  

  这种方法好是好，但是也有缺点，当树中各结点的度相差很大的时候，显然是浪费空间的，因为有很多的结点，它的指针域都是空的。不过树的各个结点的度相差很小的时候，开辟的空间被充分利用了，这是存储结构的缺点也变成了优点。

  因为指针域可能为空，所以我们就按需分配空间，也就是方案2。

  ​

• 方案2：

  因为结点指针域的个树等于该结点的度，我们弄一个位置用来存储结点指针域的个数。

  

  结构如上，其中data为数据域，degree为度域，也就是存储该结点的孩子结点的个数，child1到childd为指针域，指向该结点的各个孩子的结点。

  

  这种方法克服了浪费空间的缺点，对空间利用率提高了，但是由于各个结点的链表是不相同的结构，加上要维护结点的度的数值，在运算上就会带来时间上的损耗。

  因为每个结点的孩子有多少不确定，所以我们再对每个结点的孩子建立一个单链表来体现它们的关系。

  这就是所谓的孩子表示法：把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。

  

孩子表示法结构代码：

//树的孩子表示法的结构定义代码
#define MAX_SIZE 100
typedef struct CTNode 		//孩子结点
{
    int child;
    struct CTNode *next;
}*ChildPtr;
typedef struct		//表头结构
{
    TElemType data;
    ChildPtr firstchild;
}CTBox;
typedef struct		//树结构
{
    CTBox nodes[MAX_SIZE];		//结点数组
    int r,n;		//根的位置和结点数
}CTree;

以上的结构对于我们要查找某个结点的某个孩子，或者某个结点的兄弟，只需要查找这个结点的孩子单链表即可。对于遍历整棵树也很方便，对头结点的数组循环即可。

双亲孩子表示法：因为当我们查找某个结点的双亲是谁的时候比较麻烦，要遍历整棵树才行，所以我们就把双亲表示法和孩子表示法结合以下：

1.5.3孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟存在也是唯一的。因此，我们需要设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。

结点结构如下：

其中data是数据域，firstchild为指针域，存储该结点的第一个孩子结点的存储地址，rightsib是指针域，存储该结点的右兄弟结点的存储地址。

结构代码如下：

//树的孩子兄弟表示法结构定义
typedef struct CSNode
{
    TElemType data;
    struct CSNode *firstchild,*rightsib;
}CSNode,*CsTree;

这种表示法，给查找某个结点的某个孩子带来了方便，只需要firstchild找到此结点的长子，然后再通过rightsib找到它的二弟，依此类推，但是当某个结点想要找到它的双亲，就有问题了。

所以应该在每个结点中再加一个parent指针域来解决快速查找双亲的问题。

孩子兄弟表示法最大的好处就是把一棵复杂的树变成了一棵二叉树。如下图：

1.6二叉树定义

二叉树(Binary Tree)是n(n>=0)个结点的有限集合，该集合或者空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

1.6.1二叉树的特点

• 每个结点最多有两棵子树，所以二叉树不存在度大于2的结点。
• 左子树和右子树是有顺序的，次序不能任意颠倒。
• 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

二叉树具有的物种基本形态:

• 空二叉树
• 只有一个根结点
• 根结点只有左子树
• 根结点只有右子树
• 根结点既有左子树又有右子树

1.6.2特殊二叉树

• 斜树

  所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫做右斜树。这两者统称为斜树。

  斜树有很明显的特点，就是每一层都只有一个结点，结点的个数与二叉树的深度相同。

  左斜树：

  

  右斜树：

  

• 满二叉树

  在一棵二叉树中，如果所有的分支结点都存在与左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

  

  但是每个结点都存在左子树和右子树，不能算满二叉树，还必须要所有的叶子都在同一层上，这样就达到了整个树的平衡。

  满二叉树的特点：

  • 叶子只能出现在最下一层。出现在其他层就不能达到平衡。
  • 非叶子结点的度一定是2。否则就是”缺胳膊少腿”。
  • 在同样深度的二叉树中，满二叉树的结点个数最多，叶子最多。

• 完全二叉树

  对一颗具有n个结点的二叉树按层序编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树的位置完全相同，则这棵二叉树称为完全二叉树。

  

  满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满的。

  因为完全二叉树是按层序编号的，有些结点没有左子树，有些结点没有右子树，有些结点没有子树，但是那些位置照样存在，并且有它们的编号，但是是空的。这就是完全二叉树。

  

  完全二叉树的特点：

  • 叶子结点只能出现在最下两层
  • 最下层的叶子一定集中在左边连续位置。
  • 倒数二层，若有叶子结点，一定都在右部连续位置。
  • 如果结点度为1，则该结点只有左孩子，即不存在右子树的情况。
  • 同样结点树的二叉树，完全二叉树的深度最小。

1.6.3二叉树的性质

二叉树性质1：在二叉树的第i层上至多有2的i-1次方个结点(i>=1)

二叉树的性质2：深度为k的二叉树至多有2的k次方-1个结点(k>=1)

二叉树的性质3:对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点为n2，则n0=n2+1

二叉树的性质4：具有n个结点的完全二叉树的深度为[log2n]+1(x表示不大于x的最大整数)。

二叉树的性质5：如果对一棵有n个结点的完全二叉树(其深度为[log2n]+1)的结点按层序编号(从第一层到第[log2n]+1层,每层从左到右),对任一结点i(1<=i<=n)有：

• 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点[i/2]。
• 如果2i>n，则结点i无左孩子(结点i为叶子结点);否则其他左孩子是结点2i。
• 如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。

1.6.4二叉树的顺序存储结构

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点。

在数组中的表现形式：

在完全二叉树中，有些结点时不存在的，但是它有编号，所以把不存在的结点用符号^表示：

但是这种顺序存储结构也有问题的，比如一棵深度为k的右斜树，它只有k个结点，却要分配2的k次方-1个存储单元空间，大大的浪费了内存。

所以顺序存储结构只用于完全二叉树。

1.6.4二叉链表

既然顺序存储结构适用性不强，就要考虑使用链式存储结构。

二叉树的每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域，称为二叉链表。

其中data是数据域，lchild和rchild都是指针域，分别存放左孩子和右孩子的指针。

以下是二叉链表的结点结构定义代码：

//二叉树的二叉链表结点结构定义
typeof struct BiTNode		//结点结构
{
    TElemType data;		//结点数据
    struct BiTNode *lchild,*rchild;		//左右孩子指针
}BiTNode,*BiTree;

结构示意图：

1.6.4遍历二叉树

二叉树的遍历(traversing binary tree)是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

1.6.5二叉树遍历方法

1.前序遍历

​ 规则是若二叉树若为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。下图中遍历的顺序为：ABDGHCEIF。

2.中序遍历

​ 规则是若树为空，则空操作返回，否则从根结点开始(注意并不是先访问根结点)，中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。下图为遍历的顺序为：GDHBAEICF。

3.后序遍历

​ 规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。如下图，遍历的顺序是:

GHDBIEFCA。

4.层序遍历

​ 规则是若树为空，则空操作返回，否则树的第一层，也就是根结点开始访问，从上而下逐层遍历，再同一层中，从左到右逐个访问，如下图，遍历的顺序是：ABCDEFGHI。

1.6.5.1前序遍历算法

​ 二叉树的定义用递归的方式，所以，实现遍历算法可使用递归。

实现代码如下：

//二叉树的前序遍历递归算法
void PreOrderTraverse(BiTree T)
{
 	if(T==NULL)
        return;
    printf("%c",T->data);	//显示结点数据,可以更改为其他结点操作
    PreOrderTraverse(T->lchild);	//再先遍历左子树
    preOrderTraverse(T->rchild);	//最后先序遍历右子树
}

详细步骤见108页。

1.6.5.2中序遍历法

//二叉树的中序遍历递归算法
void InOrderTraverse(BiTree T)
{
    if(T=NULL)
        return;
    InOrderTraverse(T->lchild);	//中序遍历左子树
    printf("%c",T->data);	//显示结点数据,可以更改为其他对结点的操作
    InOrderTraverse(T->rchild);		//最后中序遍历右子树
}

详情见108页。

1.6.5.2后序遍历法

//二叉树的后序遍历递归算法
void PostOrderTraverse(BiTree T)
{
    if(T==NULL){
        return;
    }
    PostOrderTraverse(T->lchild);	//先后续遍历左子树
    PostOrderTraverse(T->rchild);	//再后续遍历右子树
    printf("%c",T->data);	//显示结点数据,可以更改为其他对结点操作
}

1.6.6二叉树的建立

为了能让二叉树的每个结点确认是否有左右孩子，我们对平常的二叉树进行了一些扩展，将二叉树中的每个结点的空指针引出一个虚结点，其值为一特定值，比如”#”，我们把这种二叉树称之为扩展二叉树。

以上二叉树的前序遍历序列为：AB#D##C##。

假设二叉树的结点均为均为一个字符，我们把刚才前序遍历序列AB#D##C##用键盘挨个输入。实现的算法如下：

//按前序输入二叉树中结点的值(一个字符)
//#表示空树,构造二叉链表表示二叉树T。
void CreateBiTree(BiTree *T)
{
    TElemType ch;
    scanf("%c",&ch);
    if(ch=='#')
        *T=NULL;
    else
    {
        *T = (BiTree)malloc(sizeof(BiTNode));
        if(!*T)
            exit(OVERFLOW);
        (*T)->data = ch;		//生成新结点
        CreateBiTree(&(*T)->lchild);		//构造左子树
        CreateBiTree(&(*T)->rchild);		//构造右子树
    }
}

建立二叉树，也就是利用了递归的原理。只不过在原来打印结点的地方，改成了生成结点，给结点赋值的操作。

1.7线索二叉树

1.7.1线索二叉树原理

对于程序的话，我们不能太浪费时间和空间，观察下图，指针域并不是都充分的利用了，有许多的”^”,也就是空指针域，这并不是一个好的现象，我们应该利用起来。

我们在结点的空指针域上添加线索(指向它的后继结点)。我们把这种指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树称之为线索二叉树。

如上图，我们把二叉树进行中序遍历后，将所有的空指针域中的rchild，改为指向它的后继结点。我们可以知道指针知道H的后继是D，I的后继是B，J的后继是E，E的后继是A，F的后继是C，G的后继不存在所以为NULL。

同理可得，我们可以将所有空指针域中的lchild，改为指向当前结点的前驱。如下图所示：

以上H的前驱是NULL，I的前驱是D，J的前驱是B，依此类推。

结合以上两个案例，可以方便的看出线索二叉树其实就是把一棵二叉树转变成了一个双向链表，这样对我们的插入删除查找某个结点带来了方便。所以我们对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。

但是也有个问题，就是我们其实并不清楚，一个结点中的lchild是指向它的左孩子还是前驱，一个结点中的rchild指向它的右孩子还是后继。所以我们要给个标志用来区分它们，我们在每个结点再增设两个标志域ltag和rtag，这两个标志只能存放0和1数字的布尔型变量，结构如下：

其中：

• ltag为0时指向该结点的左孩子，为1时指向该结点的前驱。
• rtag为0时指向该结点的右孩子，为1时指向该结点的后继。

1.7.2线索二叉树结构实现

代码如下：

//二叉树的二叉线索存储结构定义
typedef enum(Link,Thread) PointerTag;	//Link==0表示指向左右孩子指针,Thread==1表示指向前驱或后继的线索

typedef struct BinThrNode		//二叉线索存储结点结构
{
    TElemType data;		//结点数据
    struct BiThrNode *lchild,*rchild;		//左右孩子指针
    PointerTag LTag;
    PoniterTag RTga;		//左右标志
}BithrNode,*BiThrTree

​ 线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继的信息只有在遍历二叉树的时候才能得到，所以线索化的过程就是在遍历的过程中修改空指针的过程。

中序遍历线索化的递归函数代码如下：

BiThrTree pre;		//全局变量,始终指向刚刚访问过的结点
//中序遍历进行中序线索化
void InThreading(BiThrTree p)		
{
    if(p)
    {
        InThreading(p->lchild);		//递归左子树线索化
        if(!p->lchild)			//没有左孩子
        {
            p->LTag = Thread;	//前驱线索
            p->lchild = pre;	//左孩子指针指向前驱
        }
        if(!pre->rchild)	//后继线索
        {
            pre->RTag = Thread;		//后继线索
            pre->rchild = p;	//前驱右孩子指针指向后继(当前结点p)
        }
        pre = p;		//保持pre指向p的前驱
        InThreading(p->rchild);		//递归右子树线索化
    }
}

线索二叉树其实就是一个双向链表。

和双向链表结构一样，在二叉树线索链表上添加一个头结点，并且让lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最后一个结点。反之，另二叉树的中序序列中的第一个结点中的lchild域指针和和最后一个结点的rchild域指针均指向头结点。这样定义的好处就是我们既可以从第一个结点起向后继进行遍历，也可以从最后一个结点起，向前驱进行遍历。

遍历的代码如下：

//T指向头结点,头结点lchild指向根结点,头结点rchild指向中序遍历的最后一个结点。中序遍历二叉线索链表表示的二叉树T。
Status InOrderTraverse_Thr(BiThree T)
{
    BiThree p;
    p = T->lchild;		//p指向根结点
    while(p!=T)			//空树或遍历结束时,P=T
    {
        while(p->LTag==Link)		//当LTag==0时循环到中序序列第一个结点
            p = p->lchild;
        printf("%c",p->data);		//显示结点数据,可以更改为对其他结点操作
        while(p->RTag == Thread && p->rchild != T)
        {
            p = p->rchild;
            printf("%c",p->data)
        }
        p = p->rchild;		//p进至其右子树根
    }
    return OK;
}

以上代码充分利用了空指针域的空间，又保证了创建时的一次遍历就永久保存了前驱后继的信息。所以在实际问题中,如果所用的二叉树需要经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。

1.8树，森林与二叉树的转换

1.8.1树转化为二叉树

步骤如下：

• 1.加线。在所有兄弟结点之间加一条线。
• 2.去线。对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。
• 3。层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转化过来的孩子是结点的右孩子。

图形化实例如下：

1.8.2森林转化为二叉树

森林是由若干棵树组成，所以可以理解为，森林中的每一棵树都是兄弟，可以按照兄弟的处理方法来处理。

步骤如下：

• 1.把每棵树转化为二叉树。
• 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。当所有的二叉树连接起来后就得到由森林转换来的二叉树。

图形化实例如下：

1.8.3二叉树转化为树

二叉树转化为树是树转化为二叉树的逆过程，就是发过来做。

步骤如下：

• 1.加线。若某结点的左孩子结点存在，则将这个左孩子的右孩子、右孩子的右孩子结点，右孩子的右孩子的右孩子结点，就是相当于左孩子的n个右孩子结点都作为此结点的孩子(左孩子结点的双亲)。将该结点与这些右孩子用线连接起来。
• 2.去线。删除原二叉树中所有结点与其右孩子结点的连线。
• 3.层次调整。使之结构层次分明。

图形化实例如下：

1.8.4二叉树转化为森林

​ 判断一棵二叉树能够转化成一棵树还是森林，标准很简单，看这棵二叉树的根结点有没有右孩子，有就是森林，没有就是一棵树。

二叉树转化为森林的步骤如下：

• 1.从根结点开始，若右孩子存在，则把与右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除….，直到所有右孩子都删除为止，得到分离的二叉树。
• 2.再将每棵分离后的二叉树转化为树即可。

图形化实例如下：

1.8.5树与森林的遍历

• 树的遍历方式分为两种：
  • 
  • 1.根遍历树：先访问树的根结点，然后依次先根序遍历根的每棵子树，上图的遍历顺序为ABEFCDG。
  • 2.后根遍历：先依次后根遍历每棵子树，然后再访问根结点，上图的遍历顺序为EFBCGDA。
• 森林的遍历方式为两种：
  • 
  • 1.前序遍历：先访问森林中的第一棵树的根结点，然后再依次先根序根的每棵子树，再依次用同样的方式遍历除去第一棵树的剩余树构成的森林。上图遍历顺序为ABCDEFGHJI。
  • 2.后序遍历：先访问森林中第一棵树，后根遍历的方式遍历每棵子树，然后再访问根结点，再依次同样方式遍历除去第一棵树的剩余树构成的森林。上图遍历顺序为:BCDAFEJHIG。

总结：当以二叉树作为树的存储结构时，树的先根遍历和后根遍历完全可以借用二叉树的前序遍历和中序遍历的算法来实现。

1.9赫夫曼树及其应用

1.9.1赫夫曼树定义及定理

​ 上图有两颗二叉树，其中结点ABCDE分别代表着不及格，及格，中等，良好，优秀。每个叶子的分支上的数字就是所占比例数。

赫夫曼大叔说：从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称为路径长度。在二叉树a中，根结点到结点D的路径长为4，二叉树b中，根结点到结点D的路径长度为2。树的路径长度就是从树根到每一结点的路径长度之和。二叉树a的树路径长度就是1+1+2+2+3+3+4+4=20。二叉树b的树路径长度就为1+2+2+3+3+1+2+2=16。

如此，我们判断等级的时候，效率就会更高。

树的带权路径长度：从带权结点的权 乘以 该结点到树根之间的路径长度。带权路径长度最低的二叉树就称为赫夫曼树。

二叉树a的带权路径长度：WPL=5 * 1+15 * 2+ 40 * 3+30 * 4+10 * 40=315

二叉树b的带权路径长度：WPL=2 * 40+3 * 15+3 * 5 +2 * 30+2 * 10=220

意味着什么，加入有要计算10000个学生的成绩，二叉树a比较31500次计算出结果，二叉树b比较22000次计算出结果。性能上提高了不是一点点。

第七章 图

图(Graph)是由顶点的有穷非空集合和顶点之间边的集合的组成，通常表示为：G(V,E)，其中G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

1.1图的定义

在线性表中，数据元素之间是被串起来的，仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。结构为1对1的关系。

在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但是下一层的元素只能跟上一层的一个元素相关。就好像双亲有好多个孩子，但是这些孩子只能有一个双亲。结构为1对多的关系。

而在图结构中，结构是多对多的。

• 在图中的数据元素，我们称之为顶点(Vertrx)。
• 在图中不允许没有顶点(数据元素)。
• 在图中任意两个顶点的关系称为边关系。

1.1.2各种图定义

无向图：