基本概念

数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别(二进制0和1)和处理的符号的集合。数据是计算机程序加工的原料

数据元素是数据的基本单位，通常作为一个整体进行考虑和处理

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

结构是各个元素之间的关系

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

数据对象是具有相同性质的数据元素的集合，是数据的一个子集

存储结构

集合：各个元素同属一个集合，别无其他关系

线性结构：数据元素之间是一对一的关系，除了第一个元素，所有元素都有前置元素；除了最后一个元素，所有元素都有后置元素

树形结构：数据元素之间是一对多的关系

图结构：数据元素之间是多对多的关系

顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元，元素之间的关系由存储单元的邻接关系来提现

链式存储：逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系

索引存储：在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）

散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储

算法

程序 = 数据结构 + 算法

数据结构：如何用数据正确地描述现实世界的问题，并存入计算机

算法：如何高效地处理这些数据，以解决实际问题

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作

特性

有穷性。一个算法必须总在有穷步之后结束，且每一步都可在有穷时间内完成。
- 注：算法必须是有穷的，而程序可以是无穷的
确定性。算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出
可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
输入。一个算法有零个或多个输入，这些输入取自某个特定的对象的集合
输出。一个算法有一个或多个输出，这些输出是与输入有着特定关系的量

度量

时间复杂度

如果我们想统计一种功能或者一种算法的使用时间，一般都称这里的时间是：时间复杂度

那么，通常计算这个时间，都是让算法先运行，事后统计运行时间

但是这种方案存在一些问题

和机器性能有关，越好的机器处理速度越快
和编程语言有关，越高级的语言执行效率越低
和编译程序产生的机器指令质量有关
有些算法是不能事后再统计的，如：导弹控制算法

算法的时间复杂度，通常是通过事前预估算法时间开销T(n)与问题规模n的关系(T表示“time”)

时间复杂度可以只考虑阶数高的部分

加法规则

多项相加，只保留最高阶的项，且系数变为1，譬如O(n) + O(1)，那么只会保留O(n)

常见数量集(从左到右依次递增)

三种复杂度

最坏时间复杂度：考虑输入数据“最坏”的情况
平均时间复杂度：考虑所有输入数据都等概率出现的情况
最好时间复杂度：考虑输入数据“最好”的情况

通常只考虑最坏时间复杂度和平均时间复杂度的情况

空间复杂度

无论问题规模怎么变，算法运行所需的内存空间都是固定的常量，算法空间复杂度为S(n) = O(1)

注：S表示“Space”

表

线性表

定义：数据结构

基本操作：运算

注：数据结构三要素--逻辑结构、数据的运算、存储结构（物理结构）存储结构不同，运算的实现方式不同

定义

线性表是具有相同(每个数据元素所占空间一样大)数据类型的n(n>=0)个数据元素的有限序列(有次序)，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则一般表示为->L={a1,a2,ai,ai+1,...,an}

几个概念：

ai是线性表中的“第i个”元素线性表中的位序

a1是表头元素，an是表尾元素

除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继

基本操作

InitList(&L)：初始化表。构造一个空的线性表L，分配内存空间

DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间(从无到有，从有到无)

ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e

ListDelete(&L,i,&e)：删除操作。删除表L中的第i个位置的元素，并用e返回删除元素的值

LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素

GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值

其他常用操作：

Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数

PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值

Empty(L)：判空操作。若L为空表，则返回true，否则返回false

顺序表

定义

线性表是具有相同(每个数据元素所占空间一样大)数据类型的n(n>=0)个数据元素的有限序列

顺序表--用顺序存储的方式实现线性表顺序存储

把逻辑相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来提现

通常来说，元素位置一般这样计算：

LOC->起始位置

n->第n个数

size->数据元素大小

第n个值的位置->LOC(L) + (n-1) * size

动态分配

声明结构体及头文件

#include <stdlib.h>
#define InitSize 10    // 默认的最大长度
typedef struct{
    // 指示动态分配数组的指针,这里的int可以改为任意的elementType，当然，后面对应的参数也需要同步修改
    int *data;    
    int MaxSize;    // 顺序表最大容量
    int length;        // 顺序表的当前长度
}SeqList;

初始化列表

void InitList(SeqList &L){
    // 用malloc 函数申请一片连续的存储空间
    // 初始化容量*类型大小 = 总空间
    L.data = (int *)malloc(InitSize*sizeof(int));
    // 声明数组长度
    L.length = 0;
    // 声明最大容量
    L.MaxSize = InitSize;
}

增加动态数组的长度

void IncreaseSize(SeqList &L,int len){
    // 将旧数据copy
    int *p = L.data;
    //  开辟新空间
    L.data = (int *)malloc((L.MaxSize+len)*sizeof(int));
    for (int i=0;i < L.length;i++){
        // 将数据复制到新区域
        L.data[i] = p[i]
    }
    L.MaxSize = L.MaxSize + len;    // 将顺序表最大长度增加len
    free(p);    // 释放旧空间
}

main函数启动

int main(){
    SeqList L;    //声明顺序表
    InitList(L);    //初始化顺序表
    // 插入元素...
    IncreaseSize(L, 5)
    return 0;
}

特点

随机访问,即可以在O(1)时间内找到第i个元素
存储密度高,每个节点只存储数据元素
拓展容量不方便(即便采用动态分配的方式实现,拓展长度的时间复杂度也比较高)
插入、删除操作不方便。需要移动大量元素

基本操作

插入

ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e

这里采用静态分配方式实现的顺序表

静态分配是指在程序编译时，变量或数据结构所需要的内存空间就已经确定，并在程序运行期间保持不变

#define MaxSize 10    // 定义最大长度
typedef struct{
    ElemType data[MaxSize];    // 用静态的“数组”存放数据元素
    int length;    // 顺序表的长度
}SqList;    // 顺序表的类型定义

具体操作

void ListInsert(SqlList &L,int i,int e){
    for(int j=L.length;j>=i;j--)    // 将第i个元素及之后的元素后移
        L.data[j]=L.data[j-1]
    L.data[i-1]=e;    // 在位置i处放入e
    L.length++;    // 长度+1
}

假设数组L内有元素{1,2,3},希望在第2个位置上插入4

那么，当前操作将会先让数组后移，若位置为2，则在索引1的位置上赋值，因为具体数据已经后移了，所以可以直接放入{1,4,2,3},再将长度+1

但是这种代码有一定的问题，比如元素满了，索引错误等，这里给出一个相对来说比较好的示例

bool ListInsert(SqList &L,int i,int e){
    if (i < 1|| i > L.length+1)    // 判断i的范围是否有效
        return false;
    if (L.length>=MaxSize)    // 查看当前存储空间是否已满
        return false;
    for(int j=L.length;j>=i;j--)    // 元素后移
        L.data[j]=L.data[j-1]
    L.data[i-1]=e;    // 放入e
    L.length++;    // 长度+1
    return true;
}

好的算法,应该具有健壮性.能够处理异常情况,并给使用者反馈

删除

ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值

bool ListDelete(SqList &L,int i,int &e){
    if (i < 1 || i>L.length)    // 判断i的范围是否有效
        return false;
    e=L.data[i-1]    // 将被删除的元素赋值给e
    for(int j=i;j<L.length;j++)    // 将第i个位置后的元素前移
        L.data[j-1]=L.data[j];
    L.length--;    //长度-1
    return true;
}

假设数组L中有元素{1,2,3},要被删除的是第二个元素，那么e则得到了L.data[1]，则是2

将第i个位置后的元素后移，则是2后面的元素前移

L.data[1]=Ldata[2],所以3移动到2的位置上，实现删除

查找

静态分配及动态分配

GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值

ElemType GetElem(SqList L,int i){
    return L.data[i-1];
}

LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素

// 在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SeqList L,int e){
    for(int i=0;i<L.length;i++)
        return i+1;
    return 0;
}

链表

单链表

存储结构图如下

struct LNode{    // 定义单链表结点类型
    ElemType data;    // 每个节点存放一个数据元素
    struct LNode *next;    // 指针指向下一个节点
}

LNode：结点
data：数据域
next：指针域

struct LNode *p = (struct LNode*)malloc(sizeof(struct LNode)); 增加一个新的结点:在内存中申请一个结点所需空间,并用指针p指向这个结点

typedef 是可以将某些类型改名的一种方式

通常typedef 类型名称->譬如typedef int zhengshu，我们就可以使用zhengshu a = 1;来声明一个整数

那么我们也可以typedef struct LNode LNode、typedef struct LNode *LinkList

此时，要表示一个单链表时，只需声明一个头指针L，指向单链表的第一个节点

LNode * L->声明一个指向单链表第一个节点的指针

LinkList L->声明一个指向单链表第一个节点的指针(代码可读性更强)

强调这是一个单链表 -->使用LinkList

强调这是一个结点 -->使用LNode*

不带头节点

typedef struct LNode{    // 定义单链表节点类型
    ElemType data;    // 每个节点存放一个数据元素
    struct LNode *next;    //指针指向下一个节点
}LNode,*LinkList

//初始化一个空的单链表
bool InitList(LinkList &L){
    L = NULL;    // 空表，暂时还没有任何节点(防止脏数据)
    return true;
}

void test(){
    LinkList L;    //声明一个指向单链表的指针(注意，此处并没有创建一个结点)
    //初始化一个空表
    InitList(L);
}

// 判断单链表是否为空
bool Empty(LinkList L){
    return (L==NULL);
}

带头节点

typedef struct LNode{    // 定义单链表节点类型
    ElemType data;    // 每个节点存放一个数据元素
    struct LNode *next;    //指针指向下一个节点
}LNode,*LinkList

//初始化一个单链表(带头节点)
bool InitList(LinkList &L){
    L = (LNode *) malloc(sizeof(LNode));    //分配一个头节点
    if (L == NULL)
        return false;    //内存不足，分配失败
    L->next = NULL;    //头节点后暂无节点
    return true;
}

void test(){
    LinkList L;    //声明一个指向单链表的指针(注意，此处并没有创建一个结点)
    //初始化一个空表
    InitList(L);
}

插入

ListInsert(&L,i,e)：插入操作[携带头节点]。在表L中的第i个位置(找到第i-1个结点，将新结点插入其后)上插入指定元素e

定义单链表

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

具体实现

// 在第i个位置插入元素e(带头结点)
bool ListInsert(LinkList &L,int i,ElemType e){
    if (i < 1)    // 如果插入位置不正确，结束，插入位置由1开始
        return false;
    LNode *p;    // 指针p指向当前扫描到的结点
    int j=0;    // 当前p指向的是第几个结点
    p = L;    // L指向头结点，头结点是第0个结点(不存数据)
    while(p != NULL && j < i-1){    // 循环找到 i - 1个结点
        // 如果i = 1，说明插在表头，不进入循环
        // 如果i = 2，说明插入在第二个结点后
        // 所以p向下移动，结点位置变更
        p = p->next;
        j++;
    }
    // 如果i = 2，说明p此时在1的位置
    // 如果节点元素只有5个,但插入位置在7，此时p == NULL，i值不合法
    /*当p 在 第五个元素时，p->next就是NULL了
    我们找到的通常是i-1的位置
    这样就可以在最后一个元素的next处添加新元素了*/
    if (p == NULL)
        return false;    // i值不合法
    LNode *s = (LNode *)malloc(sizeof(LNode));    // 开辟空间
    s->data = e;    // 添加数据
    s->next=p->next;    // 让s.next -> p.next
    p->next = s;
    return true;
}

详细说明该代码过程，并配图

LNode *s = (LNode *)malloc(sizeof(LNode));    // 开辟空间
s->data = e;    // 添加数据
s->next=p->next;    // 让s.next -> p.next
p->next = s;
return true;

假设在i = 1添加那么s.next -> p.next，p此时是头结点，p.next说明p.next = 第一个结点 s.next -> 第一个结点,s去指向了第一个结点，s此时可以算是第一个结点，而原第一个结点变为第二个结点 p.next -> s，此时头结点指向了第一个结点，第一个结点s.next->第二个结点此时连接成功 i = other时也是同理，这里就不一一举例了，具体可看下图所示

ListInsert(&L,i,e):插入操作.在表L中的第i个位置(找到第i-1个结点，将新结点插入其后)上插入指定元素e

由于不存在头结点(第0个结点)因此i=1时需要特殊处理

结构体声明与上述一致,这里就不再赘述了

以下是具体代码实现

bool ListInsert(LinkList &L,int i,ElemType e){
    if (i < 1)    // 有效性判断
        return false;
    if(i == 1){
        // 由于没有头结点，第一个结点操作与其他结点操作不同
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = e;
        s->next = L;    
        L = s;    // 变为最新结点
        return true;
    }
    LNode *p;    // 指针p指向当前扫描到的结点
    int j = 1;    // 当前p指向第几个结点
    p = L;    // p指向第一个结点(注意：不是头结点)
    while(p!=NULL && j < i-1){
        p=p->next;
        j++;
    }
    if (p == NULL)
        return false;    // 不合法
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next=p->next;
    p->next;s;
    return true;
}

只有第一个结点有差别

前插操作

如果我们想在某个结点前插入一个结点,该怎么做呢?

直接贴代码

// 在p结点前插入元素e
bool InsertPriorNode(LNode *p, ElemType e){
    if (p==NULL)    // 条件判断
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s==NULL)    // 内存分配失败
        return false
    s->next=p->next;
    p->next=s;
    s->data=p->data;
    p->data=e;
    return true;
}

详细介绍此处的内容

s->next=p->next;
 p->next=s;
 s->data=p->data;
 p->data=e;
 return true;

将s的下一个结点指向p的下一个结点，此时s就连接了p的下一个结点，p去指向了s

具体情况如下 p -> s -> p.next

此时已经互连了,想实现前插操作,就将两边的数据互换

p.data = s.data,s.data = p.data，也就意味着s -> p -> p.next

这样的时间复杂度是O(1)

删除

ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置(找到第i-1个结点，将其指针指向第i+1结点，并释放第i个结点)的元素，并用e返回删除元素的值

bool ListDelete(LinkList &L,int i,ElemType &e){
    if (i < 1)
        return false;
    LNode *p;    // 执行p扫描到的结点
    int j = 0;    //当前p指向的是第几个结点
    p = L;    //L指向头结点，头结点是第0个结点(不存数据)
    while (p != NULL && j < i-1){
        // 直到找到i-1个结点
        p = p->next;
        j++;
    }
    if (p==NULL)
        return false;    // i值不合法
    if (p->next == NULL)
        return false;    // i - 1个结点后无其他结点
    LNode *q = p->next;    //q指向被删除的结点
    e = q->data;    // 获取值
    p->next = q->next;    // 结点断开(删除)
    free(q);    // 释放结点
    return true;
}

删除指定结点p

bool DeleteNode(LNode *p){
    if (p==NULL)
        return false;
    LNode *q = p->next;    // 令q指向p的后继结点
    p->data = p -> next -> data    // 与后继结点交换数据域
    p->next = q -> next;    // 断开结点
    free(q);
    return true;
}

譬如想删除p，那么我们让q指向p->next

p的数据变成p下一个节点的数据，p的下一个节点，变成q的下一个节点

因为数据交换了，相当于p成了下一个节点，再让p去指向之前的q，因为q是p的下一个节点

那么q的下一个节点，就是如今p的next了，此时原先的p就被删除了

则q -> p.next，p.data = p.next.data,p.next = q.next

如果p是最后一个节点，此时只能从表头开始寻找，不然会出现问题

因为p->next->data会出现问题，这里会有NULL.data！！！

查找

本节仅探讨带头结点的情况

按位查找

// 按位查找,返回第i个元素(带头结点)
LNode * GetElem(LinkList L,int i){
    if (i < 0)
        return NULL;
    LNode *p;    // 指针p指向当前扫描到的结点
    int j=0;    // 当前p指向的是第几个结点
    p = L;    // L指向头结点，头节点是第0个结点(不存数据)
    while(p != NULL && j<i){
        // 循环找到第i个结点
        p=p->next;
        j++;
    }
    return p;
}

按值查找

LNode * LocateElem(LinkList L,ElemType e){
    LNode *p = L->next;    // 获取第一个结点
    while(p != NULL && p->data != e)    // 当p不为空并且p的数据不为查找值时
        p = p->next;    // 向下查找
    return p;
}

建立

尾插法初始化带头结点的单链表

LinkList List_TailInsert(LinkList &L){    // 正向建立单链表
    int x;    // 设ElemType为整型
        L=(LinkList)malloc(sizeof(LNode));    // 建立投结点
    LNode *s,*r = L;    // r为表尾指针,s为新结点
    scanf("%d",&x);    // 输入新结点的值
    while (x!=9999){    // 输入9999表示结束
        s=(LNode *)malloc(sizeof(LNode));    // 创建新结点的空间
        s->data = x;    // 赋值新结点
        r->next=s;    // 表尾指针指向新结点
        r=s;    // 表尾指针指向表尾
        scanf("%d",&x);    // 继续输入
    }
    r->next = NULL;    // 尾结点指针置空
    return L;
}

举个栗子：

刚开始初始化的情况如下：r,s(头结点) -> NULL

假设第一次要输入10

r(头结点) -> s(10)
头结点 -> r,s(10)

第二次输入15

头结点 -> r,s(10) -> s(15)
头结点 -> s(10) -> r,s(15)

第三次输入20

头结点 -> s(10) -> r,s(15) -> s(20)
头结点 -> s(10) -> s(15) -> r,s(20)

第四次输入9999结束

头结点 -> s(10) -> s(15) -> r,s(20) -> NULL

return L -> end;

头插法初始化带头结点的单链表

LinkList List_HeadInsert(LinkList &L){    // 逆向建立单链表
    LNode *s;
    int x;
    L=(LinkList)malloc(sizeof(LNode));    // 创建头结点
    L->next=NULL;    // 初始化为空链表
    scanf("%d",&x);    // 输入结点的值
    while(x!=9999){
        s=(LNode*)malloc(sizeof(LNode));    // 创建新结点
        s->data=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x);
    }
    return L;
}

这里就简单一些了

s=(LNode*)malloc(sizeof(LNode));    // 创建新结点
s->data=x;
s->next=L->next;
L->next=s;
scanf("%d",&x);

具体叙述一下这里的情况

创建新结点
新结点指向头结点的下一个数据，即第一个结点
头结点指向新结点

其实就是在第一个结点前，让新结点->next 指向第一个结点，那么新结点就在第一个位置了，再让头结点->next指向新结点就行了

双链表

带头结点

构建结构体

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

DNode * = DLinkList

初始化双链表

bool InitDLinkList(DLinklist &L){
    L = (DNode *)malloc(sizeof(DNode));    // 分配一个头结点
    if (L==NULL)
        return false;
    L->prior = NULL;    // 头结点的prior永远指向NULL
     L->next = NULL;    // 头结点之后暂时没有结点
    return true;
}

插入

// 在p结点之后插入s结点
bool InsertNextDNode(DNode *p,DNode *s){
    if (p == NULL || s == NULL)    // 非法参数
        return false;
    s->next=p->next;
    if (p->next != NULL)    // 如果p结点存在后继结点
        p->next->prior=s;
    s->prior=p;
    p->next=s;
    return true
}

先让s的下一个结点去指向p原先的下一个结点，即s 的下一个结点为 p.next

如果p存在后继结点，那么让p的后继结点的前结点为s，如果不存在，说明p是最后一个结点，则无需指向s

最后让s的前结点变为p，p的后继结点变为s

删除

// 删除p结点的后继结点
bool DeleteNextDNode(DNode *p){
    if (p==NULL)
        return false;
     DNode *q = p->next;    // 找到p的后继结点q
     if (q==NULL)
         return false;    // p没有后继
     p->next=q->next;    // p去跳过q这个结点
     if(q->next!=NULL)    // q不是最后一个结点
         q->next->prior=p;    // 那么q的下一个结点的上一个指向为p
     free(q);    // 释放空间
     return true;
}

遍历

查找等其他操作，都建立在遍历的基础上

后向遍历

while (p!=NULL){
    p=p->next
}

前向遍历

while (p!=NULL){
    p=p->prior
}

前向遍历(跳过头结点)

只要prior不为空，说明还没到头结点，如果为空，说明已经是头结点了，因为头结点的prior==NULL

while (p->prior!=NULL){
    p=p->prior
}

循环单链表

结构定义

typedef struct LNode{    // 订阅单链表结点类型
    ElemType data;    // 元素
    struct LNode *next;    // 下一个结点
}LNode, *LinkList;

初始化循环单链表

bool InitList(LinkList &L){
    L = (LNode *)malloc(sizeof(LNode));    // 分配一个头结点
    if (L==NULL)
        return false;    // 内存不足
    L->next = L;    // 头结点next指向头结点
    return true;
}

判断链表是否为空

bool Empty(LinkList L){
    if (L->next == L)
        return true;
    else
        return false;
}

如果只有L自己，说明是空

判断结点p是否为循环单链表的表尾结点

bool isTail(LinkList L,LNode *p){
    if (p->next==L)
        return true;
    else
        return false;
}

如果p的下一个结点是头结点，说明是表尾了

循环双链表

相当于闭环的双链表

表头结点的prior指向表尾结点；

表尾结点的next指向头结点；

插入

// 在p结点之后插入s结点
bool InsertNextDNode(DNode *p,DNode *s){
    s->next=p->next;    // 将s插入到p之后
     p->next->prior=s;    
     s->prior=p;
     p->next=s;
}

举例说明(如图所示)：

最麻烦的只有上面两句

解释一下，s->next=p->next，其实就是s的下一个结点是p的下一个结点，那么，s的下一个结点就拿到了p后面的值

p的下一个结点的上一个选择是s，其实一样的道理，因为p下一个结点只会有值，它是循环的链表

如果p是最后一个值，那么它的prior就是head，而head原先的prior是p，因为p是最后一个结点，也就是说，head替换了prior，将prior改为s，如果p不是最后一个值，那么其实就是将p的下一个结点的上一个结点的prior改为s，此时，s的下一个结点是p->next，p->next->prior是s，最后两行就是让p和s互相加一下线即可

删除

//删除p的后继结点q
p->next=q->next;
q->next->prior=p;
free(q);

p后面的结点直接跳过q，变成q后面的结点，q后面的结点的前置变为p，也就是跳过q，最后释放q

静态链表

静态链表：分配一整片连续的内存空间，各个结点集中安置

0号结点充当“头结点”

下一个结点的数组下标表示游标

游标为-1表示已经到达表尾，游标充当指针

#define MaxSize 10    // 静态链表的最大长度
typedef struct{    // 静态链表结构类型的定义
    ElemType data;    // 存储数据元素
    int next;    // 下一个元素的数组下标
}SLinkList[MaxSize];

等价于

#define MaxSize 10
struct Node{
    ElemType data;    
    int next;
}
typedef struct Node SLinkList[MaxSize]

typedef是别名的意思，如果我们声明SLinkList a;那么这里的a相当于Node a[MaxSize]的数组，有10个元素的结构体数组

查找：从头结点出发挨个往后遍历结点

插入位序为i的结点：

找到一个空的结点，存入数据元素
从头结点出发找到位序为i-1的结点
修改新结点的next为-1
修改i-1号结点的next

删除某个结点：

从头结点出发找到前驱结点
修改前驱结点的游标
被删除结点next设为-2，即特殊数值充当空闲结点

静态链表：用数组方式实现的链表

栈

栈(Stack)是只允许在一端进行插入或删除操作的线性表

栈顶：允许插入和删除的一端

栈底：不允许插入和删除的一端

初始化

构建结构体

#define MaxSize 10    // 定义栈中元素的最大个数
typedef struct{
    ElemType data[MaxSize];    // 静态数组存放栈中元素
    int top;    // 栈顶指针
}SqStack;

初始化栈

void InitStack(SqStack &S){
    S.top=-1;
}

判断栈空

bool StackEmpty(SqStack S){
    return S.top==-1;
}

进栈

bool Push(SqStack &S,ElemType x){
    if (S.top == MaxSize-1)    // 栈满，报错
        return false;
    S.top = S.top + 1;
    S.data[S.top] = x;
    return true;
}

出栈

bool Pop(SqStack &S,ElemType &x){
    if (S.top==-1)
        return false;    // 栈空
    x=S.data[S.top];    // 栈顶元素先出栈
    S.top=S.top-1;    // 指针减1
    return true;
}

数据依然保存在内存中，但是在逻辑上删除了

读栈顶元素

bool GetTop(SqStack S,ElemType &x){
    if (S.top == -1)
        return false;
    x=S.data[S.top];
    return true;
}

链式存储实现

添加结点

bool InsertNextNode(LNode *p,ElemType e){
    if (p==NULL)
        return false;
     LNode *s = (LNode *)malloc(sizeof(LNode));    // 创建结点
     if (s==NULL)
         return false;
     s->data = e;
    s->next=p->next;
    p->next=s;
    return true;
}

队列

队列（Queue)是只允许在一端进行插入，在另一端删除的线性表

特点：先进入队列的元素先出队列（先进先出FIFO）

队头：允许删除的一端

队尾：允许插入的一端

顺序实现

初始化

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];    // 用静态数组存放队列元素
    int front,rear;    // 队头指针和队尾指针
}SqQueue;

// 初始化队列
void InitQueue(Squeue &Q){
    // 初始化时 队头队尾指针指向0
    Q.rear=Q.front=0;
}

void testQueue(){
    // 声明一个队列(顺序存储)
    SqQueue Q;
    InitQueue(Q);
}

// 判断队列是否为空
bool QueueEmpty(SqQueue Q){
    if (Q.rear==Q.front)
        return true;
    else 
        return false;
}

入队

bool EnQueue(SqQueue &Q,ElemType x){
    if ((Q.rear + 1) % MaxSize == Q.front)     // 判断队满
        return false;
    Q.data[Q.rear] = x;    // 新元素插入队尾
    Q.rear=(Q.rear + 1) % MaxSize;    // 队尾指针+1取模
}

通过模运算将存储空间在逻辑上变成了环状

举个栗子：假设有队列3个元素,那么我们模拟一下入队的效果

因为front和rear一开始都是在一个位置，那么通过该方法，先判断是否队满，那么队尾+1取余最大值3，结果是1，与front不同，所以队列未满，将元素插入队尾，并将队尾指针后移，此时rear是1

第二次也是同理，说说第三次，第三次时rear是2,rear + 1 取余3，结果为0，与front相同，说明队满

为什么只存了两个元素就队满呢，因为rear = front是判断队列是否为空的，若让rear = front，此时队列会为空，就不好做后续操作了，目前只能按照取余法，牺牲一个存储单位来判断

第二种方案，新加一个变量size，专门用来记录队列长度，入队size++，出队size--，当sizeMaxSize时队满，size0时队空

第三种方案，新加一个变量tag，用来标记是删除还是插入操作，初始化时tag为0，每次删除操作成功后，都令tag=0，每次插入操作成功后，都令tag=1；队满条件：front rear && tag 1，因为只有插入操作，才可能导致队满，因为上一次是插入操作，而此时front rear，所以队满；队空条件：front rear && tag == 0，如果是删除操作，才可能导致队空，因为上一次是删除操作，所以队空

出队

// 出队（删除一个队头元素，并用x返回）
bool DeQueue(SQueue &Q,ElemType &x){
    if (Q.rear == Q.front)
        return false;    // 队空报错
    x=Q.data[Q.front];    // 获取队头元素
    Q.front = (Q.front + 1) % MaxSize;
}

举个栗子：假设有队列3个元素,那么我们模拟一下出队的效果

先判断是否为空，其实是队尾和队头相同时，我们假设队头为0，队尾为2，先进行一次出队看看，那么先判断队列，不为空，获取元素，front + 1，此时front为1

如果再获取一次，那么队头和队尾就相同了，所以我们进行一次入队操作，因为此时front = 1，rear = 2，那么判断rear + 1 取余 3，结果为0，与front不相同，说明此时队未满，那么2的位置插入一个元素，并且rear + 1是3，对MaxSize取余，循环回到0的位置，那么下一次若队列未满，也可继续进行入队操作

如果想获取队头元素，只需要移除出队操作中的~~Q.front = (Q.front + 1) % MaxSize;~~即可，不让队头元素后移

队列元素个数：(rear + MaxSize - front) % MaxSize

链式存储

初始化

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}

typedef struct{
    LinkNode *front, * rear;
}LinkQueue;

// 初始化队列(带头结点)
void InitQueue(LinkQueue &Q){
    // 初始化时 front、rear都指向头结点
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
    Q.front ->next = NULL;
}

void testLinkQueue(){
    LinkQueue Q;    // 声明一个队列
    InitQueue(Q);    // 初始化队列
}

//判断队列是否为空
bool IsEmpty(LinkQueue Q){
    if(Q.front == Q.rear)
        return true;
    else
        return false;
}

不带头结点

// 初始化队列(不带头结点)
void InitQueue(LinkQueue &Q){
    // 初始化时 front、rear都指向NULL
    Q.front=NULL;
    Q.rear=NULL;
}

//判断队列是否为空(不带头结点)
bool IsEmpty(LinkQueue Q){
    if (Q.front == NULL)
        return true;
    else
        return false;
}

入队

// 新元素入队(带头结点)
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
     s->data=x;
     s->next=NULL;
     Q.rear->next=s;    // 将新结点插入到rear之后
    Q.rear=s;    // 修改表尾指针为最新值
}

// 新元素入队(不带头结点)
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
     s->data=x;
     s->next=NULL;
     if (Q.front == NULL){    // 因为不带头结点的空队列，rear和front都是默认指向NULL的
         Q.front = s;    // 所以第一个元素需要特别处理，让front和rear同时指向第一个元素
         Q.rear = s;
     }
     else{
         Q.rear->next = s;    // 新结点插入到rear后
         Q.rear = s;    // 修改rear为最新结点
     }
}

出队

// 队头元素出队(不带头结点)
bool DeQueue(LinkQueue &Q,ElemType &x){
    if (Q.front == Q.rear)
        return false;    // 空队列
    LinkNode * p = Q.front->next;    // 因为带头结点，所以头结点的下一个结点就是第一个元素
    x=p->data;    // 返回队头元素
    Q.front->next=p->next;    // 修改头结点的next指针
     if (Q.rear==p)
         Q.rear = Q.front;    // 如果是最后一个结点，那么修改rear结点
     // 此时rear == front，队列为空
     free(p);    // 释放空间
     return true;
}

// 队头元素出队(不带头结点)
bool DeQueue(LinkQueue &Q,ElemType &x){
    if (Q.front == NULL)
        return false;    // 空队列
    LinkNode *p = Q.front;    // 指向此次出队的结点
    x=p->data;
    Q.front=p->next;    // 修改front，如果是第一个结点则回到NULL，如果后续有结点则指向后续结点
    if (Q.rear == p){    // 最后一个结点出队，front->rear->NULL
        Q.front = NULL;
        Q.rear = NULL;
    }
    free(p);
    return true;
}

双端队列

双端队列：只允许从两端插入、两端删除的线性表

输入受限的双端队列：只允许从一端插入、两端删除的线性表

输出受限的双端队列：只允许从两端插入、一端删除的线性表

考点：判断输出序列合法性

若数据元素输入序列为1,2,3,4，则哪些输出序列是合法的，哪些是非法的

栈是先进后出

栈中合法的序列，双端队列中也一定合法

括号匹配

括号匹配是匹配两边是否有对应存在的括号，像这种( ( ) )，就是可以匹配成功的，通常使用栈来实现该特性

代码详情

#define MaxSize 10    // 订阅栈中元素的最大个数
typedef struct{
    char data[MaxSize];    // 静态数组存放栈中元素
    int top;    // 栈顶指针
}SqStack;
// 初始化栈
void InitStack(SqStack &S)
// 判断栈是否为空
void StackEmpty(SqStack S)
// 新元素入栈
bool Push(SqStack &S,char x)
// 栈顶元素出栈，用x返回
bool Pop(SqStack &S,char &x)
bool bracketCheck(char str[],int length){
    SqStack S;
    InitStack(S);    // 初始化栈
    for(int i=0;i<length;i++){    // 遍历括号数组
        if (str[i] == '(' || str[i] == '[' || str[i] == '{'){
            Push(S,str[i]);    // 扫描到左括号，入栈
        }
        else{
            if (StackEmpty(S))    // 扫描到右括号且栈空
                return false;
            char topElem;
            Pop(S,topElem);    // 不为空，栈顶元素出栈
            if (str[i] == ')' && topElem != '(')
                return false;
            if (str[i] == ']' && topElem != '[')
                return false;
            if (str[i] == '}' && topElem != '{')
                return false;
        }
    }
    return StackEmpty(S);    // 检索完所有括号，栈空说明匹配成功
}

总结：

用栈实现括号匹配

依次扫描所有字符，遇到左括号入栈，遇到右括号则弹出栈顶元素检查是否匹配。

匹配失败的情况：

左括号单个
右括号单个
左右括号不匹配

栈在表达式中的应用

中缀表达式：运算符在两个操作数中间，例如a+b

后缀表达式：运算符在两个操作数后面，例如ab+

前缀表达式：运算符在两个操作数前面，例如-ab

中缀转后缀的手算方法：

确定中缀表达式中各个运算符的运算顺序
选择下一个运算符，按照[左操作数右操作数运算符]的方式组合成一个新的操作数
如果还有运算符没被处理，就继续2的操作

这里有两个中缀表达式转后缀的情况，我们发现有一个运算式却存在着两个结果，通常来说，因为运算顺序不唯一，因此对应的后缀表达式也不唯一

所以我们都会遵循左优先原则，只要左边的运算符可以运算，就优先算左边的，这就是左优先原则，比如我们看左式和右式，其实括号内和最右边的除法都可以先算，但是括号更靠近左边，所以优先算括号内的

摘自王道考研数据结构与算法的一句话：右边的没有错，只是不合适。就像你一样，你也没有错，只是你不合适

中缀表达式转后缀表达式（机算）

初始化一个栈，用于保存暂时还不能确定运算顺序的运算符

从左到右处理各个元素，直到末尾。可能遇到三种情况：

遇到操作数。直接加入到后缀表达式
遇到界限符。遇到“（”直接入栈；遇到“）”则依次弹出栈内运算符并加入后缀表达式，直到弹出“（”为止。注意“（”不加入后缀表达式
遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到“（”或栈空则停止。之后再把当前运算符入栈。

按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

后缀表达式的手算方法

从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体为一个操作数
注意：两个操作数的左右顺序

中缀转前缀的手算方法：

确定中缀表达式中各个运算符的运算顺序
选择下一个运算符，按照[运算符左操作数右操作数]的方式组合成一个新的操作数
如果还有运算符没被处理，就继续②

右优先原则：只要右边的运算符能先计算，就优先算右边的

后缀表达式

用栈实现后缀表达式的计算：

从左往右扫描下一个元素，直到处理完所有元素
若扫描到操作数则压入栈，并回到①的操作；否则执行③
若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到①

若表达式合法，则最后栈中只会留下一个元素，就是最终结果

前缀表达式

用栈实现前缀表达式的计算：

从右往左扫描下一个元素，直到处理完所有元素
若扫描到操作数则压入栈，并回到①，否则执行③
若扫描到运算符，则弹出两个栈顶元素，执行相应操作，运算结果压回栈顶，回到①

中缀表达式

用栈实习中缀表达式的计算：

初始化两个栈，操作数栈和运算符栈

若扫描到操作数，压入操作数栈

若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出应该运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）

栈在递归中的应用

递归算法计算阶乘

// 计算正整数 n!
int factorial(int n){
    if (n==0 || n==1)
        return 1;
    else
        return n*factorial(n-1);
}
int main(){
    int x = factorial(10);
    return 0;
}

递归调用时，函数调用栈可称为“递归工作栈”

每进入一层递归，就将递归调用所需信息压入栈顶

每退出一层递归，就从栈顶弹出相应信息

举个栗子：比如最开始是main函数，main函数里调用func1，func1里调用func2，很显然它们是依次入栈的

main -> func1 -> func2，也就是说，最先从栈顶被释放的是func2

递归算法求斐波那契数列

int Fib(int n){
    if (n == 0)
        return 0;
    else if(n == 1)
        return 1;
    else
        return Fib(n-1)+Fib(n-2);
}
int main(){
    int x = Fib(4);
    return 0;
}

总结：

函数调用的特点：最后被调用的函数最先执行结束（LIFO）
函数调用时，需要用一个“函数调用栈”存储：
1. 调用返回地址
2. 实参
3. 局部变量
递归调用时，函数调用栈可称为“递归工作栈”，每进入一层递归，就将递归调用所需信息压入栈顶，每退出一层递归，就从栈顶弹出相应信息
缺点：效率低，太多层递归可能会导致栈溢出：可能包含很多重复计算
可以自定义栈将递归算法改为非递归算法

特殊矩阵的压缩存储

一维数组

ElemType a[10]; // ElemType型一维数组

起始地址：LOC

各数组元素大小相同，且物理上连续存放。

数组元素a[i]的存放地址=LOC+i*sizeof(ElemType) (0<=i<=10)

二维数组

ElemType b[2] [4];

行优先存储：将数组数据一行一行的存

M行N列的二维数组b[M] [N]中，若按行优先存储，则b[i] [j]的存储地址=LOC+(i*N+j)*sizeof(ElemType)

这个公式是让初始地址去加上后续的数组字节来找到对应的行优先数组值

列优先存储：将数组数据一列一列的存

M行N列的二维数组b[M] [N]中，若按列优先存储，则b[i] [j]的存储地址=LOC+(j*M+i)*sizeof(ElemType)

对称矩阵

若n阶方阵[n×n的矩阵，行列数相同的矩阵]中任意一个元素aij都有aij=aji，则该矩阵为对称矩阵

策略：只存储主对角线+下三角区

按行优先原则将各元素存入一维数组

如果我们想获取压缩矩阵的某个值，那我们可以编写一个矩阵下标->一维数组下标的方法

简单解释一下这个公式，按照行优先原则，那么下三角区的行位置，第一行0个，第二行1个，第n行n-1个，以此类推

那么我们想计算出对应的位置，就要知道它大概在哪个位置，则1+2+3+4+n-1....(计算等差公式)而列的位置就是第几个了

数组下标就根据这个公式算，因为一维数组下标是从0开始，所以-1，矩阵下标无需-1

上三角算法其实也是类似的，也是列元素依次增加计算，最后加上行的位置

三角矩阵

下三角矩阵：除了主对角线和下三角区，其余的元素都相同

压缩存储策略：按行优先原则将橙色区元素存入一维数组中。并在最后一个位置存储常量c

下三角矩阵的下三角区及主对角线元素其实和对称矩阵没差别，但是上三角区的元素都是常量，并且只在最后一个位置存储这些相同的值，所以只需要找到最后一个位置，也就是一维数组的最后一个值

上三角矩阵：除了主对角线和上三角区，其余的元素都相同

第一行有n个元素，第二行有n-1个元素，如果我们需要找到第i个元素，就要拿到i-1行的空间，那么就该计算1->i-1个行的位置，那么如果我们想找到i-1个行的位置，此时就需要通过n-i+2的方式，因为找的是i-1的位置，所以i不能为1，i为1时这个就不成立了，因为i=1时，计算的就是第0行的空间了，很显然没有第0行

请不要疑惑，因为这里计算的是i-1个元素，也就是说，i=2时，计算的是第一行的空间，因为i=2计算的是i-1个行的空间，即第一行的空间！！！

并且最后需要加入j-i个元素，也就是行前面还需要多少的元素

我认为这里需要重点说明一下公式：n-i+2

我们需要知道每一行有几个元素

第一行：有n个元素

第二行：有n-1个元素

第i行有n-i+1个元素

那么，多出来的1从哪来的呢？

我们要计算的是到某一行的整体个数

则进行公式替换，因为i = i -1

故公式为：n - (i - 1) + 1 = n - i + 1 + 1 = n - i + 2

我们最后从逻辑上来解释

比如说，我们假设k = i - 1

如果说，我们想算第三行的元素，就得拿到前两行一共有多少个元素，再加进去，那么i - 1 = 2，公式的目的是计算任意k(i)行的元素个数，那么这里-1其实是一样的，-1更方便了，因为它直接就算出了前i行所需的个数，然后加入进去，就可以得出结果了

三对角矩阵

三对角矩阵，又称带状矩阵：

当|i-j| > 1时，有aij = 0(1<=i,j<=n)

什么意思呢，也就是说，行号-列号的绝对值大于1时，那么这个元素为0

如图所示

压缩存储策略：

按行优先(或列优先)原则，只存储带状部分

前i-1行共有3(i-1)-1个元素

解释一下这个公式

这个公式计算的是第i行开始前，我们存储了多少个元素

因为我们想计算第i个元素，就得跳过其前面的元素

除了第一行和最后一行是2个元素，其他都是3个元素

假设第1行到i-1行元素都是3个元素，那么前i行就是3i了，而前i-1行就是3(i-1)了

但是！第一行是个特例，所以我们需要从总数里减去1

因此，前i-1行的元素个数就是3*(i-1)-1

当i = 2时，第2行开始前的元素就是3*1 - 1 = 2，没问题，第一行的元素确实是2

当然这里的i = 1就不成立了，因为i = 1是第一行前的元素，这个计算是没有意义的

aij是i行第j - i + 2个元素

这个公式说明aij是它自己所在的这一行里，第几个被存储的非0元素

比如说，我们看第i行的非零元素，它们通常是a[i,i-1],a[i,i],a[i,i+1]

那么带入公式

列号是j = i - 1，代入公式(i-1) - i + 2 = 1，这是第一个
列号是j = i，代入公式i - i + 2 = 2，这是第二个
列号是j = i + 1，代入公式(i + 1) - i + 2 = 3，这是第三个

现在很显然，我们可以很清楚的知道，第aij个元素是第几个非0元素

aij是第2i+j-2个元素

这个公式是前面两个公式相加后的简化，目的是最终的位置在哪，因为第一个公式是计算前i-1行的元素，我们再加上它在列的位置，就知道它在哪了

(3(i - 1) - 1) + (j - i + 2)

= (3i - 3 - 1) + (j - i + 2)

= 3i - 4 + j - i + 2

= 2i +j -2

若已知数组下标k，如何得到i,j?【反向求解】

第k + 1个元素，在第几行？第几列

前i - 1行共3(i-1)-1个元素

前i行共3i-1个元素

[

3i-1计算的是第一行+其他i-1行的个数(除去第一行的总个数)

很显然其他i-1行是3(i-1)，为什么呢？

因为我们去除了第一行，其他的元素个数都是3，除最后一行

第一行是2个，那么相加即为3i - 3 + 2 = 3i - 1

]

显然，3(i-1)-1< k + 1 <= 3i-1

k会大于前i-1行的元素个数，并小于等于前i行的元素个数

把不等式解出来得i为下述公式

i=(k+2)/3 -> 向上取整或 i = (k+1)/3+1 -> 向下取整

由k = 2i+j-3[该公式由上述推导]，得

j = k-2i+3

我们确认一下这里的元素，k是第k个元素，i是行，j是列

稀疏矩阵

稀疏矩阵：非零元素远远少于矩阵元素的个数

压缩存储策略：

顺序存储--三元组<行，列，值>

方法二：十字链表法

一图胜千言

定义两个指针数组，分别指向每一列和每一行

串

串，即字符串（String）是由零个或多个字符组成的有限序列。一般记为

S='a1a2a3......an'(n>=0)

其中S是串名，单引号括起来的字符序列是串的值；

ai可以是字母、数字或其他字符；

串中字符的个数n称为串的长度

n=0时的串称为空串（用空集表示）

例：

S=“HelloWorld”[注：有的地方用双引号，有的地方用单引号]

T=‘Phone’

子串：串中任意个连续的字符组成的字序列。

Eg：'Pho'，'one'是串T的子串

主串：包含子串的串。

Eg：T是'Pho'的主串

字符在主串中的位置：字符在串中的序号

Eg：h在T中的位置是2（第一次出现）

子串在主串中的位置：子串的第一个字符在主串中的位置

Eg：'hone'在T中的位置为2，其实就是子串首个字符出现的位置

注意：位序从1开始，而不是从0

当然，空串和空格串是不一样的

M=''，M是空串

N=' 'N是由三个空格字符组成的空格串，每个空格字符占1B

串是一种特殊的线性表，数据元素之间呈线性关系

串的数据对象限定为字符集（如中文字符、英文字符、数字字符、标点字符等）

串的基本操作，如增删改查等通常以子串为操作对象

基本操作

假设有串T=“”，S=“iPhone 11 Pro Max?”，W=“Pro”

StrAssign(&T,chars)：赋值操作。把串T赋值为chars中的内容

StrCopy(&T,S)：复制操作。把串S复制到串T

StrEmpty(S)：判空操作。若S为空串，则返回TRUE，否则返回FALSE

StrLength(S)：求串长。返回串S的元素个数

ClearString(&S)：清空操作。将S清为空串

DestroyString(&S)：销毁串。将串S销毁（回收存储空间）

Concat(&T,S1,S2)：串联接。用T返回由S1和S2联接而成的新串

SubString(&Sub,S,pos,len)：求子串。用Sub返回串S的第pos个字符起长度为len的子串

Index(S,T)：定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则返回0

StrCompare(S,T):比较操作。若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0

这里的比较操作是针对字符大小来判断的，

Eg：d>a，因为d在a的后面

abstract<abstraction，长串前缀相同时，长串更大

任何数据存到计算机中一定是二进制数。

需要确定一个字符和二进制数的对应规则，这就是编码

“字符集”：

英文字符---ASCII字符集
中英文---Unicode字符集

英文字符大小通常根据ASCII字符集来确定

存储结构

顺序存储

顺序存储其实就是通过顺序表来存储，而ElemType改为了char

#define MAXLEN 255    // 预定义最大串为255
typedef struct{
    char ch[MAXLEN];    // 每个分量存储一个字符,静态数组实现(定长顺序存储)
    int length;    // 串的实际长度
}SString;

typedef struct{
    char *ch;    // 按串长分配存储区，ch指向串的基地址(动态数组实现堆分配存储)
    int length;    // 串的长度
}HString;
HString S;
S.ch = (char *)malloc(MAXLEN * sizeof(char));
S.length = 0;

上述说明的是方案一，写明Length，写明数组

方案二

在ch[0]，即数组首位充当Length，优点：字符的位序和数组下标相同

方案三

没有Length变量，以字符'\0'表示结尾（对应ASCII码的0）

类似这样：w a n g \0

方案四

舍弃ch[0]，由ch[1]开始存储数据，并专门声明Length用来表示字符串有多长

这样就可以截取方案一、二的优点了

链式存储

typedef struct StringNode{
    char ch;    // 每个结点存1个字符
    struct StringNode * next;    // 在32位的系统中，此处占用4个字节
}StringNode, * String;

此时就出现了一个问题

我们存储内容只存一个字节，而辅助存储的next指针却要4个字节，我们称这种情况为

存储密度低：每个字符1B，每个指针4B

如何解决该问题呢？

我们可以让每个结点存储多个字符，以此来提高存储密度

typedef struct StringNode{
    char ch[4];    // 此处存储的信息可以更多
    struct StringNode * next;    // 在32位的系统中，此处占用4个字节
}StringNode, * String;

操作实现

以下操作采用顺序存储方案四

SubString(&Sub,S,pos,len)：求子串。用Sub返回串S的第pos个字符起长度为len的子串

结构

#define MAXLEN 255
typedef struct{
    char ch[MAXLEN];    // 每个分量存储一个字符
    int length;
}SString;

// 求子串
bool SubString(SString &Sub,SString S,int pos,int len){
    // 子串范围越界
    if (pos + len - 1 > S.length)    // 如果第pos个字符+len-1大于总长度时，说明字符越界
        return false;
    for (int i=pos;i<pos+len;i++){
        Sub.ch[i-pos+1] = S.ch[i];    // 这里的第一个位置是不放内容的
    }
    Sub.length = len;
    return true;
}

StrCompare(S,T)：比较操作。若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0

int StrCompare(SString S,SString T){
    for (int i = 1;i <= S.length && i <= T.length;i++){
        // 如果长度小于这两个数组，此时说明还未结束
        if (S.ch[i] != T.ch[i])    // 若字符不同
            return S.ch[i] - T.ch[i];    // ASCII码字符相减
    }
    // 扫描过的所有字符都相同，则长度长的串更大
    return S.length-T.length;
}

Index(S,T)：定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0

int Index(SString S,SString T){
    int i=1,n=StrLength(S),m=StrLength(T);    // 获取两个字符串的长度
    SString sub;    //暂存字符串
    while(i<=n-m+1){    // n-m+1是为了计算可以获取到的子串次数，依次向后，这里+1是把第一次包含进去
        SubString(sub,S,i,m);    // 截取子串
        if(StrCompare(sub,T)!=0) ++i;    // 比对子串
        else return i;    // 返回位置
    }
    return 0;    // 不存在子串
}

朴素模式匹配算法

字符串模式匹配：在主串中找到与模式串相同的子串，并返回其所在位置

主串：123456

模式串：56

模式串：78

子串与模式串不同

子串---主串的一部分，一定存在
模式串---不一定在主串中能找到

朴素模式匹配算法：暴力解决问题

主串长度为n，模式串长度为m

朴素模式匹配算法，将主串中所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的子串，或所有的子串都不匹配为止。

而我们最多能对比n-m+1个子串，这里+1是第一次的对比加入进去

看到这里是不是感觉有些熟悉呢？

其实在操作实现中的Index方法里，我们已经实现了朴素模式匹配算法，但这是通过字符串的基本方法来实现的

接下来我们将通过数组下标实现朴素模式匹配算法

直接上代码解析

int Index(SString S,SString T){
    int i=1,j=1;
    while(i<=S.length && j<=T.length){
        if (S.ch[i] == T.ch[j]){    // 模式串和主串相同
            ++i;++j;    // 继续比较后继字符
        }
        else{
            i=i-j+2;    // 主串来到原字符下一个位置
            // 通常来说是+1，即向后一位，但这里采用的是模式四，第0位被舍弃了，所以+2
            j=1;    // 模式串回到首位
        }
    }
    // 如果j超过了模式串的长度，说明已经找到了，返回位置
    if (j>T.length)
        return i-T.length;
    else 
        return 0;
}

这样的时间复杂度最坏会达到O(nm)

KMP算法

KMP算法相当于朴素模式匹配算法的优化版

简单说明一下旧版的KMP算法

原方法是遍历主串，对应的遍历模式串，如果主串与模式串不符合，就让主串后移，模式串回到原位，这种方法确实稳妥，但是太慢了

KMP算法只需要看模式串，我们会额外声明一个next数组作为辅助使用

拿google为例，如果两个字符匹配，则i，j，i是主串,j是模式串

若j=1时发生不匹配，让i++，而j依然是1

若j=2 时发生不匹配，则应让j回到1

若j=3时发生不匹配，则应让j回到1

若j=4时发生不匹配，则应让j回到1

若j=5时发生不匹配，则应让j回到2，这里是因为google，j=5时，数据为l，很显然前面已经有了g，符合第一个g的标准，就没有必要从原先的g重新开始了，而是直接让j回到o，相当于少匹配一次g

 若j=6 时发生不匹配，则应让j回到1

而j=next[k]，其实是说明了上述的情况

具体代码如下：

int Index_KMP(SString S,SString T,int next[]){
    int i = 1,j = 1;    // 初始化主串、模式串序号
    while(i<=S.length && j<=T.length){
        if(j==0 || S.ch[i]==T.ch[j]){    
            // 当j为next[1]时，说明首字符不匹配，两者后移，让主串后移，并让模式串回到首位
            ++i;
            ++j;
        }else{
            j=next[j];    // 模式串后移
        }
    }
    if(j>T.length)
        return i-T.length;    // 匹配成功
    else
        return 0;    
}

串的前缀：包含第一个字符，且不包含最后一个字符的子串

例如：abcdefg，前缀就有：a、ab、abc、abcd、abcde、abcdef

串的后缀：包含最后一个字符，且不包含第一个字符的子串

例如：abcdefg，后缀就是g、fg、efg、defg、cdefg、bcdefg

我们主要看最长相等的匹配前后缀，通过匹配的前后缀就可以填充next数组了

举个栗子，我们以ababaa来制作next数组

索引j	对应的字符	子串	前缀	后缀	公共部分	最长公共前后缀长度	next[j]
0	a	a	无	无	无	0	0
1	b	ab	a	b	无	0	0
2	a	aba	a,ab	a,ba	a	1	1
3	b	abab	a,ab,aba	b,ab,bab	ab	2	2
4	a	ababa	a,ab,aba,abab	a,ba,aba,baba	a,aba	3	3
5	a	ababaa	a,ab,aba,abab,ababa	a,aa,baa,abaa,babaa	a	1	1

那么next数组就是[0,0,1,2,3,1]

特别的，next[0]是为0的

当然，我们是把next[1]来作为第一个字符使用的，所以通常来说，next[1]=0

我们务必要知道最长相等的前后缀长度

另一种方法：当第j个字符匹配失败，由前1~j-1个字符组成的串记为S，则next[j]=S的最长相等前后缀长度+1

比如拿ababaa来说，如果在索引5的a时匹配失败，那么由ababa组成S

S的最长相等前后缀是：aba aba，那么长度是3，3+1是4

next[5]=4

这两个情况不同，但得到的结果都是对的

在考研处学习的是第二种方法

这里给出相应代码

// 求模式串T的next数组
void get_next(SString T,int next[]){
    int i=1,j=0;    // i是模式串，j是记录公共前缀长度
    next[1]=0;    // 无前后缀必为0
    while(i<T.length){
        if(j==0||T.ch[i]==T.ch[j]){    // 首位或字符相同，只有字符相同，才会走下去
            ++i;++j;    // 模式串前进，并且公共前缀长度增加
            // 若pi=pj，则next[j+1]=next[j]+1
            next[i]=j;    // 对应的模式串赋予公共前缀长度
        }
        else
            // 否则令j=next[j]，循环继续
            // 并且第一个子串next[1]必定是回到第一个位置，会让串向后走
            j=next[j];    //回溯到上一个正确的前后缀位置
    }
}

//KMP算法
int Index_KMP(SString S,SString T){
    int i=1,j=1;
    int next[T.length+1];
    get_next(T,next);    // 求next数组
    while(i<=S.length && j<=T.length){
        if (j==0 || S.ch[i]==T.ch[j]){
            ++i;++j;    // 继续比较后续字符
        }else
            j=next[j];    // 模式串移动
    }
    if (j >　T.length)
        return i-T.length;    // 匹配成功，返回索引
    else 
        return 0;
}

最后在这里说一下自己对于next数组的理解

next数组真的是最重点的内容了，只要掌握了next数组，就掌握了KMP

next数组的第一个位置存放的是0，这是绝对的，因为如果j在第一个字符就匹配失败了，就需要让模式串做重开操作，并让对应主串往后，第二个位置存放的是1，这是绝对的，因为一般来说，第二个位置匹配失败的话，都会回到第一个位置重新匹配公共前后缀，不同就让主串后移，因为第二个匹配失败了，第一个也失败了，第三个乃至后面的，都是根据是否匹配成功来决定，如果匹配成功，说明了一点，此时的前后缀相同，那么长度++，并记录回归位置，如果匹配失败，回到上一次位置，因为上一次位置有成功匹配过的前后缀，对其继续匹配，如果成功，说明前后缀相同，长度++，不同就继续回归，直到回到最前面

求nextval数组

先求next数组，再由next数组求nextval数组

nextval[1] = 0;
for(int j=2;j<=T.length;j++){
    if (T.ch[next[j]]==T.ch[j])
        nextval[j]=nextval[next[j]];
    else
        nextval[j]=next[j];
}

树

基本概念

树：从树根生长，逐级分支

空树：结点数为0的树

非空树的特性

有且仅有一个根节点
前驱：前面的结点，比如C的前驱是A
后继：后面的结点，比如A的后继是C
没有后继的结点称为“叶子结点”（或终端结点）
有后继的结点称为“分支结点”（或非终端结点）

树除了根节点外，任何一个结点有且仅有一个前驱，如果存在多于一个前驱，说明它不是树

树是一个n(n>=0)个结点的有限集合，n=0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足：

有且仅有一个特定的称为根的结点
当n>1时，其余结点可分为m(m>0)个互不相交的有限集合T1,T2......Tn，其中每个集合本身又是一棵树，并且称为根节点的子树

属性：

结点的层次（深度）---从上往下数[默认从1开始]
结点的高度 ---从下往上数
树的高度（深度） ---总共多少层
结点的度 ---有几个孩子（分支）
树的度 ---各结点的度的最大值

有序树---逻辑上看，树中结点的各子树从左至右是有次序的，不能互换

无序树---逻辑上看，树中结点的各子树从左至右是无次序的，可以互换

如图所示，左侧为有序树，右侧为无序树

森林是(m>0)棵互不相交的树的集合,m可为0，空森林

如图所示，左侧为森林，右侧为树

常考性质

结点数=总度数+1

结点的度---结点有几个孩子(分支)

度为m的树、m叉树的区别

树的度---各结点的度的最大值

m叉树---每个结点最多只能有m个孩子的树

度为m的树	m叉树
任意结点的度<=m(最多m个孩子)	任意结点的度<=m(最多m个孩子)
至少有一个结点度=m（有m个孩子）	允许所有的结点的度都<=m
一定是非空树，至少有m+1个结点	可以是空树

度为m的树，至少有应该结点的度=m，并且不能为空，至少有m+1个结点

m叉树可以为m叉空树，度也是任意的，可以为空

度为m的树第i层至多有m^{i-1}个结点(i>=1)

m叉树第i层至多有m^{i-1}个结点(i>=1)

高度为h的m叉树至多有\frac{m^{h}-1}{m-1}个结点

高度为h的m叉树至少有h个结点。

高度为h、度为m的树至少有h+m-1个结点

具有n个结点的m叉树的最小高度为 [log_m(n(m-1)+1)]

二叉树

二叉树是n(n>=0)个结点的有限集合：

或者为空二叉树，即n=0
或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一颗二叉树。

特点：

每个结点至多只有两棵子树
左右子树不能颠倒（二叉树是有序树）

特殊类型

满二叉树

一棵高度为h，且含有2^h-1个结点的二叉树

特点：

只有最后一层有叶子结点
不存在度为1的结点
按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1；结点i的父节点为[i/2]（如果有的话）

完全二叉树

当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树

特点：

只有最后两层可能有叶子结点
最多只有一个度为1的结点
同上③
i<=[n/2]为分支结点，i>[n/2]为叶子结点

二叉排序树

一颗二叉树或者是空二叉树，或者是具有如下性质的二叉树：

左子树上所有结点的关键字均小于根节点的关键字；

右子树上所有结点的关键字均大于根节点的关键字；

左子树和右子树又各是一棵二叉排序树。

二叉排序树可用于元素的排序、搜索

平衡二叉树

平衡二叉树。树上任一结点的左子树和右子树的深度之差不超过1

平衡二叉树能有更高的搜索效率