数据结构 | koko2pp

一、基本概念引入

存储结构/物理结构

数据元素与数据元素间有两种结构：逻辑结构，存储结构/物理结构

逻辑结构分类：

线性结构（线性表、栈、队列、串，有且仅有一个前趋和后继）；非线性结构（树、图，有多个前趋和后继）
四类基本逻辑结构：集合结构；线性结构(1v1)；树形结构( 1v多)；图状结构(多v多)

存储结构分类：

顺序存储结构(用存储先后位置表示逻辑先后关系)；链式存储结构(任意存储位置，但有指针表示前后逻辑关系)；索引存储结构；散列存储结构；

时间/空间复杂度

对比不同算法：时间空间复杂度，即时间和空间增长的趋势

时间渐进复杂度

(BigO: 当一个问题量级增加的时候，时间增长的趋势)：T(n) = O(f(n))，其中f(n)代表代码执行次数，O表示正比例关系
Eg: O(n)

for(int i = 1; i<=n; i++){
    x++;
}
//若n = 3:
//1. int i = 1;
//2. i<=n;
//3. x++;
//4. i++; (i=2)
//5. i<=n;
//6. x++;
//7. i++; (i=3)
//8. i<=n;
//9. x++;
//10.i++;
//11.i<=n → 退出
//执行次数为：i=1 执行一次； x++ i++ 会执行 n次，i<=n执行n+1次，因此f(n) = 3n+2
//O(f(n)) = O(3n+2) =O(n),n接近于无限大的比例，常数和倍数意义不大，因此简略为O(n)

Eg: O(n²)

for(int i = 1; i <= n; i++){
    for(int j = 1; j <=n; j++){
        x++;
    }
}
//同理，O(f(n)) = O(n^2)

常用时间复杂度量级

Eg: O(1): 交换x和y的值，是一个常量

int x = 1;
int y = 1;
int temp = x;
x = y;
y = temp;

Eg: O(logN): 2^k = n,k是循环次数即算法复杂度，k = logN

int i = 1;
while(i<n){
    i = i*2;
}

Eg: O(nlogN)

for(int i = 0; i<=n; i++){
    int x = 1;
    while(x<n){
        x = x*2;
    }
}

其它时间复杂度指标：

空间复杂度（内存增长的趋势）
- 常用空间复杂度：O(1), O(n), O(n²)
- Eg: O(1)
  1
  2
  3
  4
  int x = 1;
  int y = 0;
  x++;
  y++;
  Eg: O(n)，1D Array, 算法复杂度取决于newArray的长度，长度越大，需要分配的内存空间就越多
  1
  2
  3
  4
  int[] newArray = new int[n];
  for(int i = 0; i < n; i++){
  newArray[i] = i;
  }
  Eg: O(n²)，计算Matrix，或者2D Array
计算：

找变量和不变量，i++或者i–就是写本身，对于乘除写原表达式

例1中：变得是变量：{x=x-10;y–}与x++，不变得是限制条件：while(y>0){}与if(x>100)中得0和100，先看外层：左式(变)=右式(不变)，最后相乘：y = O(o)，x = O(100) y*x = O(1)，复杂度为O(1)

例2中：i = O(n), j = O(m) → 最后相乘复杂度为O(n*m)

例3中：i = O(n), j=O(n), s=O(1) → 最后相乘复杂度为O(n*n)

例4中：3ⁱ= O(n) → j = O(log n) → 最后复杂度为O(log n)

二、线性表（顺序表、链表）

2.1 线性表的定义、特点、基本操作

线性表的定义：

一个线性表是n个具有相同特性的数据元素的有限序列。

线性表的逻辑结构：线性结构

在非空的线性表，有且仅有一个开始结点 a₁，它没有直接前趋，且仅有一个直接后继a₂
有且仅有一个终端结点 a_n，它没有直接后继，且仅有一个直接后继a_n-1
其余的内部结点( 2 ≤ i ≤ n-1)都有且仅有一个直接前趋a_i-1和一个一个直接后继a_i-1

线性表的特点：

元素个数有限（区别于数学中的集合，如自然数集合/实数集合等是无限且无序）
元素逻辑上有顺序性，即元素间有先后次序
元素都是数据元素，每个元素都是单个元素且数据类型相同，即每个元素占有相同大小的存储空间
元素具有抽象性，只讨论元素间的逻辑关系，不管元素的具体内容

线性表的分类：顺序存储、链式存储

线性表指的是逻辑结构，元素之间1v1的线性关系；链式存储和顺序存储指的是存储结构；

线性表的基本操作：

2.2 线性表的顺序存储—顺序表

顺序表的定义：

逻辑顺序与物理顺序相同

逻辑上相邻的数据元素存储在物理上相邻的存储单元的存储结构，即逻辑顺序与物理顺序相同。

顺序表中元素存储位置的计算：

Loc(a_i) = Loc(a₁)+(i-1)*sizeof(ElemType)

顺序表的特点：随机存取

主要特点是随机存取，通过首地址和元素序号可在时间O(1)内找到任一元素
存储密度高，每个结点只存储数据元素
顺序表逻辑上相邻元素物理上也相邻，因此插入和删除操作需要移动大量元素

顺序表的存储结构描述：静态分配/动态分配

一维数组可以静态分配，也可以动态分配。

静态分配：由于数组大小和空间已提前固定，一旦空间占满，再加入新数据则造成溢出、程序崩溃；

动态分配：动态存储分配语句进行存储数据的空间分配，一旦空间占满，就另外开辟更大的存储空间去替换原存储空间以扩充存储数组空间，不需要为线性表提前一次性地划分所有空间

静态分配：假设线性表的元素类型为ElemType

#define MaxSize 50        //定义线性表的最大长度
typedef struct{
    ElemType data[MaxSize];   //顺序表的元素 使用数组表示
    int length;         //顺序表的当前长度
}SqList;            //顺序表的类型定义，使用该名称

动态分配（依旧是顺序存储结构，物理结构没有变化）

#define InitSize 100      //表长度的初始定义
typedef struct{
    ElemType *data;       //指示动态分配数组的指针(数组第一个元素所在位置的地址)
    int MaxSize,length;     //数组的最大容量和当前个数
}SqList;            //动态分配数组顺序表的类型定义

//C初始动态分配语句： (空间类型/指针类型)malloc(需要分配的空间大小)
L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);
//原型:分配长度为num-byte字节的内存块; 分配成功，则返回指向被分配的指针；分配失败，返回空指针NULL
//malloc函数通常与free函数成对使用，分配空间使用结束后使用free函数释放
extern void*malloc(unsigned int num-bytes);
//Eg:
int *A;
A = (int*)malloc(sizeof(int)*20); // A可以被当作做A[20]进行使用

问题：InitSize=10 即A[10]，放入15个元素，则动态分配的另外空间是A[5]/A[10]/A[15]？

答案：A[15]，要求逻辑上相邻的元素物理上也相邻，没有办法保证中间断开的两个元素的物理位置是相邻的，因此需要分配一个更大长度的连续物理存储空间放入所有元素

顺序表的基本操作：

插入O(n) /删除O(n)/ 查找( 按位查找O(1) 按值查找O(n) )

插入：在顺序表 L 的第 i ( 1 <= i <= L.length+1 )个位置插入新元素 e

若 i 的输入不合法，则返回 false，表示插入失败；

若 i 合法，则将第 i 个元素及其后面的所有元素一次向后移动一个位置，腾出一个空位插入新元素e，顺序表长度增加 1 ，插入成功，返回true;

或者插入失败 #define false 0; 插入成功 #define true 1; 那么bool ListInsert() 改为 int ListInsert()

//插入操作需要Input: 哪个顺序表(指针类型)，第几个元素进行插入，插入元素的值
bool ListInsert(SqList *L, int i, ElemType 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--){ //从最后一个元素开始，将第i个元素及之后的元素进行后移
        L.data[j] = L.data[j-1];  //把j-1位置的元素赋值给j位置
    } 
    L.data[i-1] = e;        //在位置i处放入e，i是位序，位序和下标差1
    L.length++;           //线性表程度加1
    return true;
}

删除：删除顺序表L中第 i (1 <= i <= L.length)个位置的元素，用引用变量e返回。

输入不合法返回false；

输入合法，将被删除元素赋值给引用变量e (指针)，并将第i+1个元素及其后的所有元素依次向前移动一格位置，返回true;

先把删除结点内容赋值给变量e，数组的删除是覆盖操作，原来的值(如图63)还会存在，但是length–，我们认为变化后的length长度为我们的表长，后面的63已经不在表内

bool ListDelete(SqList *L, int i, Elemtype *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个位置后的元素前移，提供的i是位置，j是下标
        L.data[j-1] = L.data[j];
    }
    L.length--;
    return true;          //线性表长度减1
}

查找：

按位查找（input位置 output值，直接找O(1)）、按值查找（input值 output位置，需要从头遍历）

按值查找：在顺序表L中查找第一个元素值等于 e 的元素，并返回其位序

int LocateElem(Sqlist L,ElemType e){
    int i;
    for(i=0;i<L.length;i++){  //从头开始找 i = 0 开始，一直到L.length-1
        if(L.data[i] == e){   
            return i+1;     //下标为i的元素值等于e，返回其位序 i+1
        }
    }
    return 0;         //退出循环，说明查找失败
}

顺序表总结：

20230120223240 20230120223258

2.3 线性表的链式存储—链表(单链表)

由于顺序表的插入、删除操作需要移动大量元素，因此引入链式存储结构的线性表。链表不需要使用地址连续的存储单元，通过指针建立起数据元素之间的逻辑关系，因此插入和删除不需要移动元素，只需要修改指针，也因此失去了顺序表随机存取的优点。

链表(单链表)/双链表/循环链表的定义：

线性表的链式存储又称为单链表，即通过一组任意存储单元来存数据元素。每个链表结点由数据域（存放元素数值数据）和指针域（存储直接后继节点的指针）构成

单链表的描述：

typedef struct LNode{  //定义单链表结点类型
    ElemType data;    //数据域
    struct LNode *next;  //指针域（指向下一个结点的指针）
}LNode,*LinkList; //LNode普通类型，*LinkList为指针类型，Linklist A;和LNode *B; 类型等价

结点只有一个指针域的链表为单链表

双链表：结点有两个指针域的链表
循环链表：首尾相接的单链表

链表的头指针、头结点、首元结点的定义：

使用头指针来标识一个单链表（Eg：单链表L，头指针为NULL的时候表示为一个空表），在单链表第一个结点之前附加一个结点，称为头结点，头结点的数据域可以不放任何信息，也可以用于记录表长，头结点的指针域指向线性表的首元结点（第一个元素结点）。头结点可以有可无

链表的基本操作：

创建链表O(n)(头插法/尾插法、删除、查找O(n)(按序/按值)

创建链表

头插法：从一个空表开始生成新结点，并将读取到的数据存放到新结点的数据域中，然后**将新结点插入到当前链表的表头，即头结点之后**。

（需要**先操作后端，再操作前端**，如图，在表头插入a_i新结点，首先将a_i的指针域指向原来的首元结点a_l，再将头结点的指针域指向a_i；错误做法：先前端再后端，先将头结点的指针指向a_i，则此时丢失了指向a_l的指针域，即无法找到a_l结点）

头插法输出后得到的是一个倒序的序列

LinkList List_HeadInsert(LinkList &L){ //输入：头指针，输出LinkList类型的链表
    //逆向建立单链表：
    LNode *s; int x;            // 新结点s以及新结点存放的数据x
    L = (LinkList)malloc(sizeof(LNode));  //创建头结点，指针类型
    L->next = NULL;             //头结点赋空，初始化为空链表
    scanf("%d",&x);             //输入结点的值
    while(x!=9999){             //输入9999表示循环/插入结束
        s=(LNode*)malloc(sizeof(LNode));  //创建新结点s
        s->data = x;            //把x赋值给s结点的数据域
        s->next = L->next;          //先操作后端
        L->next = s;            //再操作前端，将新结点插入链表，L头指针
        scanf("%d",&x);
    }
    return L;
}

每个结点插入时间为O(1)，设单链表的表长为n，则总时间复杂度为O(n)

思考：若没有设立头结点，则修改为：

//输入：头指针L，输出LinkList类型
LinkList List_HeadInsert(LinkList &L){    //逆向建立单链表：
    LNode *s; int x;            // 新结点s以及新结点存放的数据x
    L = (LinkList)malloc(sizeof(LNode));  //创建头结点，指针类型
    scanf("%d",&x);             //输入结点的值
    while(x!=9999){             //输入9999表示循环/插入结束
        s=(LNode*)malloc(sizeof(LNode));  //创建新结点s
        s->data = x;            //把x赋值给s结点的数据域
        if(L==NULL){
            L = s;              //先操作后端
            s->next = NULL;         //再操作前端
        }else{
            s->next = L;          //先操作后端
            L = s;              //再操作前端
        }
        scanf("%d",&x);
    }
    return L;
}

个人理解：如果不设置头结点，L头指针就直接指向第一个结点（L=s）；设置了头结点则头指针存放在头结点的指针域中，当作一个结点使用 (L->next = s)

尾插法：尾插法生成的链表中，结点的次序和输入数据的顺序一致。该方法将新结点插入当前链表的表尾，因此需要一个尾指针 r ，使其始终指向当前链表的尾结点

依然先操作后端再操作前端：先将a_j的指针域NULL赋给a_i的后端，再将a_i的结点地址赋给a_j的指针域

① ②③

//输入：头指针L，输出LinkList类型
LinkList List TailInsert(LinkList &L){
    int x;                  //设元素类型为整形
    L = (LinkList)malloc(sizeof(LNode));  //创建头结点
    LNode *s, *r=L;           //① r为表尾指针(上面右图 和L一样指向头节点）
    scanf("%d", &x);          //输入结点的值
    while(x!=9999){
        s=(LNode *)malloc(sizeof(LNode));   //新结点
        s->data = x;            //新结点数据域
        r->next = s;    //② 最后结点的指针域指向s，连接尾结点和s结点
        r = s;        //③ r指向新的表尾结点s
         scanf("%d",&x);
    }
    r->next = NULL; //尾结点指针置空
    return L;
}

因为附设了一个指向表尾结点的指针，因此时间复杂度和头插法相同为O(n)

查找：复杂度为O(n)

按序查找：从第一个结点出发，顺着指针next域逐个向下搜索，知道找到第i个结点为止，否则返回最后一个结点指针域NULL。遍历操作，复杂度为O(n)

//输入：链表 序号；输出：结点
LNode *GetElem(LinkList L, int i){
    int j = 1; //计数，初始为1
    LNode *p = L->next; //移动的指针,L指向头结点，p此时指向的是第一个数据结点即首元结点
    if(i==0) return L;    //若i等于0，返回头结点
    if(i<1) return NULL;  //若i不合法，返回NULL
    //这里p等价于p→next!=null，while循环进行判断，如果p不等于空且j<i（即没到尾节点并且还没有查到i节点）判断为真，继续执行循环;若p指向NULL即P已经是尾结点，跳出循环
    while(p && j<i){    //从第一个结点开始找，找到第i个结点
        p = p->next;    //
        j++;
    }
    return p;         //返回第i个结点的指针，若i大于表长，则返回NULL
}

按值查找：从表的第一个结点开始，从前往后依次比较各结点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的指针；若整个单链表中没有该结点，则返回NULL。遍历操作，复杂度为O(n)

LNode *LocateElem(LinkList L, ElemType e){
    LNode *p = L->next;
    while(p!=NULL && p->data!=e){ //从第一个结点开始查找data域为e的结点
        p = p -> next;
    }
    return p; //找到后返回该指针，不然返回NULL(p此时是尾结点，返回尾结点的指针域)
}

插入 O(n)
- 将值为 x 的新结点插入到单链表的第 i 个位置上。先检查插入位置的合法性，**找到带插入位置的前驱节点**，即第 i-1 个结点，再在其后插入新结点。算法：首先调用按序查找函数找到第 i-1 个结点GetElem(L, i-1)，返回的是第 i-1 个结点为 *p ，让新结点 *s 的指针域指向 *p 的后继节点，再令结点 *p 的指针域指向新插入的结点 *s
删除结点操作
- 删除结点操作是将单链表的第 i 个结点删除。先检查删除位置的合法性，后查找表中第 i-1 个结点，即被删结点的前驱节点，再将其删除
求表长：计数器，算法复杂度为O(n)

双链表及双链表的基本操作

插入O(1) 删除O(1)

已知单链表中访问某结点的前驱结点（插入、删除操作），只能够从头遍历。为克服该缺点，引入双链表：双链表结点中有两个指针 prior 和 next，分别指向其前驱结点和后继结点

双链表中结点类型的描述：

typedef struct DNode{       //定义双链表结点类型
    ElemType data;          //数据域
    struct DNode *prior, *next;   //前驱和后继指针
}DNode, *DLinklist;

双链表的插入操作

为了不断链，同样是先后端再前端：
双链表的删除操作

循环单链表

循环链表中，**最后一个结点的指针不是NULL，而改为指向头结点**，整个链表形成一个环。

循环单链表中，表尾结点r的next域指向L，因此表中没有指针域为NULL的结点，因此*循环单链表的判空条件不是头结点是否为空，而是判断它是否等于头指针

循环双链表

链表的总结

2.4 链表与顺序表的对比

三、栈和队列

3.1 栈(后进先出)和队列(先进先出)的定义、特点

栈和队列是限定插入操作和删除操作只能在表的“端点”进行的线性表

栈的定义和特点：

栈（stack）是一个特殊的线性表，是**限定仅在一端(表尾)，进行插入和删除操作的线性表**；又称为后进先出（Last In First Out）的线性表，简称LIFO结构。元素间的逻辑结构为1 v 1。根据存储结构不同分为顺序栈和链栈。

举例：
补充：

栈的应用举例

① 表达式求值；② 递归工作栈；③ 括号匹配；④ 迷宫求解；⑤ 进制转换；⑥ 行编辑程序；⑦悔棋操作

表达式求值：在计算机中任何一个表达式都可以由操作数 operand（常数），运算符 operator （算数运算符、关系运算符和逻辑运算符）和界限符 delimiter（左右括号和标识表达式结束的结束符）组成。
递归：
- 定义和举例：
- 算法设计：
进制转换：
括号匹配：

队列的定义和特点：

队列（queue）是一种先进先出（First In First Out, FIFO）的线性表。**在表尾插入，在表头删除**。与线性表相同，逻辑结构为1 v 1，根据存储结构不同分为顺序队与链队。
队头Front，允许删除的一端，又称为队首；队尾Rear，允许插入的一端。
举例：

3.2 栈的表示和操作实现

栈的基本操作：

栈的顺序存储：顺序栈

顺序栈的定义

同一般线性表的顺序存储结构完全相同，利用一组地址连续的存储单元一次存放自栈底到栈顶的数据元素，栈底一般在低地址端。

顺序栈的表示

使用base指针，指示栈底元素在顺序栈中的位置
使用top指针，指示栈顶元素在顺序栈中的位置（一般指的是**栈顶元素上一个元素的存储单元**）
用stacksize表示栈可用的最大容量

#define MAXSIZE 100
typedef struct{
    SElemType *base; //栈底指针
    SElemType *top;  //栈顶指针
    int stacksize;   //最大容量
}SqStack;

判断顺序栈的栈空和栈满：

栈空标志：base == top

栈满标志：top-base==stacksize

栈中**元素个数：top - base**
- 栈满时候的处理方法：1.报错，返回操作系统；2.分配更大的空间。
- 进行出栈和入栈操作可能会遇到上溢/下溢（因为数组大小提前已使用stacksize固定）
  - 上溢（overflow）：栈已经满，依然入栈
  - 下溢（underflow）：栈已经空，还要出栈
  - 上溢是一种错误，使问题的处理无法执行；而下溢被认为是一种结束条件，即问题处理结束

顺序栈的基本操作

顺序栈的初始化：分配空间，初始化S.base; S.top; S.stacksize

Status InitStack(SqStack &S){//构造一个空栈
    S.base = new SElemType[MaXSIZE]; //S.base指针指向内存中构造数组的首元素
    if(!S.base) exit (OVERFLOW); //内存空间满，存储分配失败
    S.top = S.base; // 空栈标志，让栈顶指针top等于栈底指针base
    S.stacksize = MAXSIZE; //初始化S.stacksize的值
    return 1;
}

判断栈是否为空

Status StackEmpty(SqStack S){
    if(S.top == S.base){
        return 1; // 栈空
    }else{
        return 0; // 栈不空
    }
}

求顺序栈长度( 顺序栈中元素的个数 )

1
2
3

int StackLength(SqStack S){
    return S.top-S.base;
}

清空顺序栈：若栈存在 S.top = S.base 让栈空就可以

Status ClearStack(SqStack &S){
    if(S.base) S.top=S.base;//若栈存在 S.top = S.base 让栈空就可以
    return 1;
}

销毁顺序栈

Status DestroyStack(SqStack &S){
    if(S.base){
        delete S.base; //如果栈存在，删除栈底指针
        //delete操作释放了指针原本所指部分内存，此时base指针值并非NULL，而是随机值成为了野指针
        S.stacksize = 0;
        S.base = S.top = NULL; //指针置空
        return 1;
    }
    return 0;
}

顺序栈的入栈

首先是否判断是否栈满，栈满则报错上溢
将元素e压入栈顶
栈顶指针top加1

Status Push(SqStack &S,SElemType e){
    if(S.top-S.base==S.stacksize) return ERROR; //栈满
    *S.top = e;
    S.top++;
    //或者集成为 *S.top++ = e;
    return 1;
}

顺序栈的出栈

判断是否栈空，若栈空则报错下溢
获取栈顶元素 e 用于返回
栈顶指针 S.top 减 1

Status Pop(SqStack &S, SElemType &e){
    if(S.top == S.base) return ERROR; // 栈空 则报错
    S.top--; //先将top指针下移一位
    e = *S.top; //再提值
    // 等价于e = *--S.top
    return 1
}

栈的链式存储：链栈

链栈的定义

采用链式存储的栈称为链栈，采用单链表实现，只能在链表的头部进行操作。**next域中存放的是前驱元素的地址**

特点：

链表的头指针就是栈顶；
不需要头结点；
基本不存在栈满的情况
空栈相当于头指针指向空
插入操作和删除操作仅在栈顶处执行

链栈的表示

typedef struct StackNode{
    SElemType data;			// 数据域
    struct StackNode *next; // 指针域
}StackNode,*LinkStack;

链栈的基本操作

链栈的初始化

Status InitStack(LinkStack &S){
    // 构造一个空栈，栈顶指针置空
    S = NULL;
    return 1;
}

判断链栈是否为空

Status StackEmpty(LinkStack S){
    if(S==NULL) 
        return 1; //栈空
    else
        return 0; //栈不空
}

链栈的入栈

1.创建新结点

2.将新结点插入栈顶

3.更新栈顶指针

Status Push(LinkStack &S,SElemType e){
    p = new StackNode; //生成新结点p
    p->data = e; //设置新结点的数据域
    p->next = S; //将新结点插入栈顶
    S = p; // 修改栈顶指针
    return 1;
}

链栈的出栈

1.首先判断是否栈空，栈空报错

2.保存删除结点的数据域

3.删除结点

4.更新栈顶指针

Status Pop(LinkStack &S,SElemType e){
    if(S==NULL) return ERROR;
    e = S->data; // 将data值保存在元素e中
    LinkStack p = S; //生成新结点p指向S
    S = S->next; // 移动S指向栈顶
    delete p; //释放p所指向的内存
    return 1; 
}

取栈顶元素

1
2
3

SElemType GetTop(LInkStack S){
    if(S!=NULL) return S->data;
}

3.3 队列的表示和操作实现

队列的基本操作

顺序队列：

顺序队列的定义

队列的顺序存储结构是指分配一块连续的存储单元来存放队列中的元素，并附设两个指针：队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置。

顺序队列的表示

#define MAXQSIZE 100 // 指定队列的最大长度
typedef struct{ //定义顺序队列的结构体
    QElemType *base; //初始化的动态分配存储空间，指向队列
    int front; //头指针，队头 用于删除
    int rea; //尾指针，队尾 用于插入
}

初始状态（队空条件）：Q.front == Q.rear = 0

进队操作：队若不满，先送值到队尾元素，再将队尾元素指针加1

出队操作：队不空时，先取队头元素值，再将队头元素加1

会发生假（上）溢出操作，超过MaxSize的大小，因此使用循环顺序队列

循环顺序队列的定义

将顺序队列想象为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。可以用除法取余%运算来实现。当队首指针Q.front = MaxSize-1后，再进一个位置就自动到0的操作。

初始时：Q.front = Q.rear = 0

删除操作，队头指针进1：( Q.front = Q.front + 1) % MaxSize

插入操作，队尾指针进1：( Q.rear = Q.rear + 1) % MaxSize

队列长度：(Q.rear + MaxSize - Q.front) % MaxSize

循环顺序队列的表示

#define MAXQSIZE 100 //设置最大队列长度
typedef struct{
    QElemType *base;//动态分配存储空间
    int front; //头指针，若队列不空，指向队列头元素
    int rear; //尾指针，若队列不空，指向队列为元素的下一个位置
}SqQueue;

循环顺序队列的基本操作

队列初始化：分配空间，初始化Q.base; Q.front, Q.rear

Status InitQueue(SqQueue &Q){
    Q.base = new QElemType[MAXQSIZE]; //分配固定数组空间
    if(!Q.base) exit(OVERFLOW); // 内存已满，分配空间失败，报错
    Q.front = Q.rear = 0;//头指针和尾指针置为0，创建空队列
    return 1;
}

求队列长度（元素个数）

1
2
3

int QueueLength(SqQueue Q){
    return ((Q.rear + MaxSize - Q.front) % MaxSize);
}

循环顺序队列入队：若队没满则队尾插入

Status EnQueue(SqQueue &Q, QElemType e){
    if((Q.rear+1)%MAXQSIZE == Q.font) return ERROR; // 队满报错
    Q.base[rear] = e; //将新元素放在尾指针位置
    Q.rear = (Q.rear+1)%MAXQSIZE; //更新尾指针位置，队尾指针+1
    return 1;
}

循环顺序队列出队：若队不为空，队头删除

Status DeQueue(SqQueue &Q, QElemType &e){
    if(Q.rear==Q.front) return ERROR; //队空报错
    e = Q.base[front]; //用元素e保存要删除的队头元素
    Q.front = (Q.front+1)%MAXQSIZE; //更新头指针位置，队头指针+1
    return 1;
}

取队头元素：若队不为空，返回队头元素的值

QElemType GetHead(SqQueue Q){
    if(Q.front != Q.rear)  //队列不为空
        return Q.base[front]; //返回队列头指针元素
    else
        return ERROR;
}

判断是否队空

Status isEmpty(SqQueue Q)){
    if(Q.front == Q.rear)  
        return 1;  //队列为空
    else
        return 0;  //队列不为空
}

链队列：

链队列的定义

队列的链式表示称为链队列，实际上是一个同时带有队头指针和队尾指针的单链表，头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点（注意：与顺序存储不同）

链队列的表示

typedef struct QNode{ //定义结构：链式队列的结点
    QlemType data;			//数据域
    struct QNode *next;	//指针域
}QNode,*QuenePtr;

typedef struct{			//定义结构：链式队列
    QuenePtr front,rear; //队头和队尾指针
}LinkQueue;

空队列：Q.front == NULL 切 Q.rear == NULL

链队列的基本操作

链队列的初始化：初始化链表和 front和rear指针

Status InitQueue(LinkQueue &Q){
    //让front和rear指针指向分配的新空间 ，并让首尾指针都指向头结点
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)); 
    if(!Q.front) exit(OVERFLOW); //内存满，分配失败
    Q.front -> next = NULL; //将头结点next域置空
    return 1;
}

判端链队列空

Status isEmpty(LinkQueue Q){
    if(Q.rear == Q.front)
        return 1;
    else
        return 0;
}

销毁链队列：若队列存在，从队头结点开始，依次释放所有结点

Status DestroyQueue(LinkQueue &Q){
    while(Q.front){ //判断队列是否存在
        //p指向下一结点，删除原结点，更新front指针
        p=(QNode*)malloc(sizeof(QNode));
        p = Q.front->next; free(Q.front); Q.front = p;
        //或者使用已有的指针，实现思路一样:
        //rear = Q.front->next; free(Q.front); Q.front = rear;
        return 1;
    }
    return 0;
}

链队列的入队：尾结点插入。建立一个新结点，将新结点插入到链表的尾部，并该让 Q.rear 指向这个新插入的结点（若原队列是一个空对，则令 Q.front 也指向该结点）

Status EnQueue(LinkQueue &Q, QlemType e){
    p = (QNode*)malloc(sizeof(QNode)); //创建新结点：找一块内存，让指针p指向它
    if(!p) exit(OVERFLOW); //内存满分配失败
    p->data = e; p->next = null; //准备好新结点
    Q.rear->next = p; //插入新结点
    Q.rear = p; //更新尾指针
    return 1;
}

链队列的出队：首先判断队列是否为空，若不空则取出队头元素，将其从链表中摘除，并让 Q.front 指向下一个结点（若该结点为最后一个结点，则置 Q.front 和 Q.rear 都为 NULL）

Status DeQueue(LinkQueue &Q, QlemType &e){
    if(Q.rear == Q.front) return ERROR;
    p = (QNode*)malloc(sizeof(QNode)); 
    p = Q.front->next; //指针p指向要删除的结点
    e = p->data;//保存要删除结点的数据域
    if(Q.rear == p) Q.rear = Q.front; //尾结点指向的就是首元结点，就先把Q.rear一走
    Q.front->next = p->next; // 链表中删除头结点
    delete p;//内存中释放删除结点内存
    return 1;
}

if语句：

求链队列的队头元素：表不为空，返回队头元素的值

Status GetHead(LinkQueue Q, QlemType &e){
    if(Q.rear == Q.front) return ERROR;
    e = Q.front->next->data;
    return 1;
}

四、串、数组、广义表

线性表和栈和队列(操作受限的线性表)的线性结构可以表示为：(a₁, a₂, a₃, …, a_n)

串：是内容受限的线性表，每个数据元素只能是字符；

数组：是线性结构的推广，线性表的每个元素又是线性表；

广义表：是线性结构的推广，广义表的数据元素是原子或者广义表；

4.1 串的类型定义、存储结构

4.1.1 串的定义

串(string)是由**零个或多个字符组成的有限序列**，一般记作 S = “a₁ a₂ … a_n“, （n>=0，串长度），S为串名。a_i (1≤i≤n)可以是字符(字母、数字、或者其它字符)

几个术语：

子串：一个传中任意连续字符组成的子序列(含空串)称为该串的子串。例如，”abcde”的字串有：””, “a”,”ab”,”abc”,”abcd”,”abcde”等。真子串是指不包含自身的所有子串。

主串：包含子串的串相应地称为主串，空串是任意串的子串，任意串是其自身的子串。

字符位置：字符在序列中的位置为该字符在串中的位置

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

空串：长度为零的串，不包含任何字符””

空格串：由一个或者多个空格组成的串，与空串不同，空格串” “的长度≥1

串相等：当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，这两个串是相等的。所有空串相等

模式匹配：确定子串从主串的某个位置开始后，在主串中首次出现的位置的运算。在串匹配中，一般将主串称为目标串，子串称为模式串。

例：假设串A、B、C、D分别为：

A = ‘data’, B = ‘structure’, C = ‘datastructure’, D = ‘data structure’

长度分别为4、9、13、14，A和B都是C和D的子串，A在C和D的位置都是1，B在C和D的位置分别是5和6。

4.1.2 串的抽象数据类型定义

串的实现方法有：定长顺序串、堆串和块链串。串中元素逻辑关系和线性表相同，串可以采用与线性表相同的存储结构，串→ 顺序存储结构→顺序串；串 → 链式存储结构→链串

4.1.3 顺序串的表示

顺序串的表示：

#define MAXLEN 50 //字符串的最大长度
typedef struct{
    char ch[MAXLEN+1]; //存储串的一维字符型数组，+1是因为一般0号不用
    int length; //串的当前长度
}SString;

4.1.4 块串

一般链串的存储密度较低，将多个字符放在一个结点中，即块串

串的链式存储结构——块链结构表示：

#define CHUNKSIZE 80 //块,即每个结点的元素多少由用户定义
typedef struct Chunk{
    char ch[CHUNKSIZE]; //数据域：存储一个块的一维字符数组
    struct Chunk *next; //指针域：指向下一个块
}Chunk;

typedef struct{
    Chunk *head,*tail; //串的头指针和尾指针
    int curlen; //串的当前长度
}LString //字符串的块链结构

4.2 串的模式匹配

确定主串中所含子串在某位置后第一次出现的位置。主串S称为目标串，子串T为模式串

4.2.4 BF模式匹配算法

Brute-Froce暴力解法：从S的每一个字母开始一次与T的字符进行匹配。假定使用顺序串

BF算法实现：

Index(S,T,pos)：将主串的第pos个字符和模式串的第一个字符比较，若相等，继续逐个比较后续字符；若不等，从主串的下一个字符起，重新与模式串的第一个字符比较。直到S和T相等，返回匹配的第一个字符序号，否则匹配失败返回0；

int Index_BF(SString S, SString T, int pos){
    int i=pos,j=1;
    while( i<=S.length && j<=T.length ){//循环条件：若i指针在主串内且j在子串内
        if(S.ch[i]==T.ch[i]){ //主串和子串对应pos的字符相等，则依次匹配下一个
            ++i;++j;
        }else{ //主串和子串对应pos的字符不相等，则i回溯到原来的下一个位置，j变为1
            i=i-j+2;
            j=1;
        }
        if(j>=T.length){
            return i-T.length; //j已出子串，证明匹配成功，返回第一个字符位置
        }else{
            return 0;//匹配失败，返回0
        }
    }
}

BF算法的时间复杂度：O(n*m)

4.2.5 KMP模式匹配算法

特点：采用next指针数组消除指针回溯，用next数组告诉i和j应该回溯到哪里，而不是从头开始，省去重复部分。如图P0不等于t1且P0不等于t2，因此指针i不用回到pos2重新比较

GIF 2023-1-30 0-31-57

KMP:

主串不同子串动

KMP算法的时间复杂度：O(n+m)

next数组求法：

① 写出模式串；

②模式串的第一位写0，第二位写1；

③从第3位到第n位：比较前n-1位，得出最长公共前后缀匹配长度K，则填K+1；K为0 则填1

KMP算法表示：

int Index_KMP(SString S, SString T, int pos){
    i=pos,j=1;
    while( i<=S.length && j<=T.length ){//循环条件：若i指针在主串内且j在子串内
        if(S.ch[i]==T.ch[i]){ //主串和子串对应pos的字符相等，则依次匹配下一个
            ++i;++j;
        }else{ //主串和子串对应pos的字符不相等，则i不变，j后退
            j=next[j];
        }
        if(j>=T.length){
            return i-T.length; //j已出子串，证明匹配成功，返回第一个字符位置
        }else{
            return 0;//匹配失败，返回0
        }
    }
}

void get_next(SString T, int &next[]){
    int i=1,j=0;
    next[1]=0;
    while(i<T.length){
        if(j==0 || T.ch[i]==T.ch[j]){
            ++i;++j;
            next[i]=j;
        }else{
            j=next[j];
        }
    }
}

4.3 多维数组(地址运算)

多为数组和广义表可以看为是线性表的扩展，即它们的数据元素构成线性表，而数据元素本身又是一个线性结构。

数组定义：按照一定格式排列的，具有相同类型的数据元素的集合；
数组特点：结构固定——定义后，维数和维界不变；
数组基本操作：除了结构的初始化和销毁，只有取元素和修改元素。因此，一般使用顺序存储结构
一维数组：线性表中的数据元素为非结构的简单元素为一维数组。Eg：int num[5] = {0, 1, 2, 3, 4}; 线性结构。
二维数组：一维数组中的元素又是一维数组结构，则为二维数组。二维数组的逻辑结构可以堪为线性结构（以行优先行/或以列优先），也可以看为非线性结构（如图，a₁₁有两个前趋和两个后继，不是1v1的线性结构）。声明格式：数组类型变量名称[行数] [列数];
- 例题：
三维数组：页，行，列。二维数组中的元素又是一个一维数组，称为三维数组。
n维数组：
求地址的例题：

4.4 矩阵的压缩存储

用二维数组表示矩阵，但高阶矩阵中存在许多值相同或者值为零的元素，并且这些元素的分布存在一定规律，称这类矩阵为特殊矩阵。如果使用传统的二维数组对特殊矩阵进行存储会造成很大的空间浪费，为节省存储空间，对这类矩阵进行压缩存储。Eg: 对称矩阵，对角矩阵，三角矩阵，稀疏矩阵

对称矩阵：元素沿着主对角线对称
三角矩阵
对角矩阵
稀疏矩阵
- 三元组顺序表存储稀疏矩阵。三元组顺序表又称为有序的双下标法。优点：非零元素在表中按照行序有序存储，便于进行以行顺序处理的矩阵运算。缺点：不能随机存储，插入修改不便（元素变成0，需要踢出该三元组顺序表；或者0元素修改为非零元素，三元组顺序表需要插入该元素）
- 链式矩阵的链式存储结构，十字链表
  
  例题：