笔触狂放9

这个屌丝很懒，什么也没留下！

热门标签

2024年《王道》数据结构笔记整理2024_2024版王道数据结构pdf(1)，零基础也能看得懂

作者：笔触狂放9 | 2024-07-30 19:41:07

踩

王道数据结构pdf

网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。

需要这份系统化的资料的朋友，可以戳这里获取

一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！

数据结构

- 第一章：绪论

需要PDF版请加qq2281872155

第一章：绪论

1.1数据结构的基本概念

1.数据：数据是信息的载体，是描述客观事物属性的数、字符以及所有能输入到计算机中并被程序识别和处理的符号的集合。

2.数据元素：数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。例如，学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成。

3.数据对象:数据对象是具有相同性值的数据元素的集合，是数据的一个子集。

4.数据类型:数据类型是一个值的集合和定义再此集合上的一组操作的总称。

1）原子类型。其值不可再分的数据类型。如bool 和int 类型。
2）结构类型。其值可以再分解为若干成分（分量）的数据类型。
3）抽象数据类型。抽象数据组织及与之相关的操作。

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

1.2数据结构的三要素

1.数据的逻辑结构：
逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。
逻辑结构包括：

集合结构：结构中的数据元素之间除“同属一个集合”外，别无其它关系。
线性结构：结构中的数据元素之间只存在一对一的关系，除了第一个元素，所有元素都有唯一前驱；除了最后一个元素，所有元素都有唯一后继。
树形结构：结构中数据元素之间存在一对多的关系。
图状结构：数据元素之间是多对多的关系。

2.数据的存储结构（物理结构）：
存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。
存储结构包括：

顺序存储：把逻辑上相邻的元素存储在物理位置也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
链式存储：逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。
索引存储：在存储元素信息的同时，还建立附加的索引表，索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）
散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储。

3.数据的运算：施加在数据上的运算包括运算的定义何实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。

1.3算法的基本概念

程序=数据结构+算法
算法（algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。
算法的特性：
1.有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
2.确定性：算法中每条指令必须有确定的含义，对于相同的输入只能得到相同的输出。
3.可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
4.输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
5.输出：一个算法有一个多个输出，这些输出是与输入有着某种特定关系的量。
好的算法达到的目标：

正确性：算法应能够正确的求接问题。
可读性：算法应具有良好的可读性，以帮助人们理解。
健壮性：输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名奇妙地输出结果。
效率与低存储量需求：效率是指算法执行的时间，存储量需求是指算法执行过程中所需要的最大存储空间，这两者都与问题的规模有关。

1.4算法的时间复杂度

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作T（n)=O(n)，它表示随问题规模n的增大而增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。

1.5算法的空间复杂度

算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它是问题规模n的函数。记为S(n)=O(g(n))。

第二章：线性表

2.1线性表的定义

线性表是具有相同数据类型的n(n>0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。

2.2顺序表的定义

2.2.1静态分配:

//顺序表的实现--静态分配

#include<stdio.h>
#define MaxSize 10 //定义表的最大长度 
typedef struct{
	int data[MaxSize];//用静态的"数组"存放数据元素
	int length; //顺序表的当前长度  
}SqList;        //顺序表的类型定义（静态分配方式） 
void InitList(SqList &L){
	 for(int i=0;i<MaxSize;i++){
	 	L.data[i]=0;  //将所有数据元素设置为默认初始值
		  
	 }
	 L.length=0;
}
int main(){
	SqList L;//声明一个顺序表
	InitList(L);//初始化一个顺序表
	for(int i=0;i<MaxSize;i++){
		printf("data[%d]=%d\n",i,L.data[i]);
	}
	return 0; 
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2.2.2动态分配

//顺序表的实现——动态分配
#include<stdio.h>
#include<stdlib.h>//malloc、free函数的头文件 
#define InitSize 10 //默认的最大长度
typedef struct{
	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){
	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);  //释放原来的内存空间 
	
} 
int main(void){
	SeqList L; //声明一个顺序表
	InitList(L);//初始化顺序表
	IncreaseSize(L,5);
	return 0; 
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

顺序表的特点：

随机访问，可以在O(1)时间内找到第i个元素。
存储密度高，每个节点只存储数据元素
拓展容量不方便
插入、删除操作不方便，需要移动大量元素

2.2顺序表的基本操作

1.插入操作：平均时间复杂度O(n)

bool ListInsert(SqList &L, int i, int e){ 
    //判断i的范围是否有效
    if(i<1||i>L.length+1) 
        return false;
    if(L.length>MaxSize) //当前存储空间已满，不能插入  
        return false;

    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
    return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.删除操作：平均时间复杂度O(n)

bool LisDelete(SqList &L, int i, int &e){ // e用引用型参数 
    //判断i的范围是否有效
    if(i<1||i>L.length) 
        return false;

    e = L.data[i-1]    //将被删除的元素赋值给e

    for(int j=L.length; j>=i; j--){    //将第i个后的元素前移
        L.data[j-1]=L.data[j];
    }
    L.length--;      //长度减1
    return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.按位查找(获取L表中第i个位置的值)：平均时间复杂度O(1)

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

ElemType GetElem(SqList L, int i){
    // ...判断i的值是否合法
    return L.data[i-1];      //注意是i-1
}


1
2
3
4
5
6
7
8
9
10
11
12

4.按值查找：平均时间复杂度O（n）

#define InitSize 10 //定义最大长度 
typedef struct{
    ElemTyp *data;  //用静态的“数组”存放数据元素 
    int Length;              //顺序表的当前长度
}SqList;   

//在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SqList L, ElemType e){
    for(int i=0; i<L.lengthl i++)
        if(L.data[i] == e)  
            return i+1;     //数组下标为i的元素值等于e，返回其位序i+1
    return 0;               //推出循环，说明查找失败
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.3线性表的链式表示

2.3.1 单链表的定义

定义： 线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。

typedef struct LNode{//定义单链表结点类型
    ElemType data; //数据域
    struct LNode *next;//指针域
}LNode, *LinkList;

1
2
3
4
5

可以利用typedef关键字——数据类型重命名：type<数据类型><别名>

单链表的两种实现方式：

不带头结点的单链表

```bash
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){
    if (L == NULL)
        return true;
    else
        return false;
}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

头结点：代表链表上头指针指向的第一个结点，不带有任何数据。

带头结点的单链表

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);
    //...
}

//判断单链表是否为空（带头结点）
bool Empty(LinkList L){
    if (L->next == NULL)
        return true;
    else
        return false;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

带头结点和不带头结点的比较：
不带头结点：写代码麻烦！对第一个数据节点和后续数据节点的处理需要用不同的代码逻辑，对空表和非空表的处理也需要用不同的代码逻辑; 头指针指向的结点用于存放实际数据;
带头结点：头指针指向的头结点不存放实际数据,头结点指向的下一个结点才存放实际数据;

2.3.2单链表上基本操作的实现

1.按位序插入（带头结点）：
==ListInsert(&L, i, e): ==在表L中的第i个位置上插入指定元素e = 找到第i-1个结点(前驱结点)，将新结点插入其后；其中头结点可以看作第0个结点，故i=1时也适用。

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

//在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, ElemType e){  
    //判断i的合法性, i是位序号(从1开始)
    if(i<1)
        return False;
    
    LNode *p;       //指针p指向当前扫描到的结点 
    int j=0;        //当前p指向的是第几个结点
    p = L;          //L指向头结点，头结点是第0个结点（不存数据）

    //循环找到第i-1个结点
    while(p!=NULL && j<i-1){     //如果i>lengh, p最后会等于NULL
        p = p->next;             //p指向下一个结点
        j++;
    }

    if (p==NULL)                 //i值不合法
        return false;
    
    //在第i-1个结点后插入新结点
    LNode *s = (LNode *)malloc(sizeof(LNode)); //申请一个结点
    s->data = e;
    s->next = p->next;
    p->next = s;                 //将结点s连到p后,后两步千万不能颠倒qwq

    return true;
}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

平均时间复杂度：O(n)

2.按位序插入（不带头结点）
==ListInsert(&L, i, e): ==在表L中的第i个位置上插入指定元素e = 找到第i-1个结点(前驱结点)，将新结点插入其后; 因为不带头结点，所以不存在“第0个”结点，因此！i=1 时，需要特殊处理——插入(删除)第1个元素时，需要更改头指针L;

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

bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
        return false;
    
    //插入到第1个位置时的操作有所不同！
    if(i==1){
        LNode *s = (LNode *)malloc(size of(LNode));
        s->data =e;
        s->next =L;
        L=s;          //头指针指向新结点
        return true;
    }

    //i>1的情况与带头结点一样！唯一区别是j的初始值为1
    LNode *p;       //指针p指向当前扫描到的结点 
    int j=1;        //当前p指向的是第几个结点
    p = L;          //L指向头结点，头结点是第0个结点（不存数据）

    //循环找到第i-1个结点
    while(p!=NULL && j<i-1){     //如果i>lengh, p最后会等于NULL
        p = p->next;             //p指向下一个结点
        j++;
    }

    if (p==NULL)                 //i值不合法
        return false;
    
    //在第i-1个结点后插入新结点
    LNode *s = (LNode *)malloc(sizeof(LNode)); //申请一个结点
    s->data = e;
    s->next = p->next;
    p->next = s;          
    return true;

}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

3.指定结点的后插操作：

InsertNextNode(LNode *p, ElemType e): 给定一个结点p，在其之后插入元素e; 根据单链表的链接指针只能往后查找，故给定一个结点p，那么p之后的结点我们都可知，但是p结点之前的结点无法得知;

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

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保存数据元素e 
    s->next = p->next;
    p->next = s;          //将结点s连到p之后

    return true;
}                         //平均时间复杂度 = O(1)


//有了后插操作，那么在第i个位置上插入指定元素e的代码可以改成：
bool ListInsert(LinkList &L, int i, ElemType e){  
    if(i<1)
        return False;
    
    LNode *p;       //指针p指向当前扫描到的结点 
    int j=0;        //当前p指向的是第几个结点
    p = L;          //L指向头结点，头结点是第0个结点（不存数据）

    //循环找到第i-1个结点
    while(p!=NULL && j<i-1){     //如果i>lengh, p最后4鸟会等于NULL
        p = p->next;             //p指向下一个结点
        j++;
    }

    return InsertNextNode(p, e)
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

4.指定结点的前插操作
思想：设待插入结点是s，将s插入到p的前面。我们仍然可以将s插入到*p的后面。然后将p->data与s->data交换，这样既能满足了逻辑关系，又能是的时间复杂度为O(1).（真是妙的不达鸟）

//前插操作：在p结点之前插入元素e
bool InsertPriorNode(LNode *p, ElenType 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连到p之后
    s->data = p->data; //将p中元素复制到s
    p->data = e;       //p中元素覆盖为e

    return true；
}  //时间复杂度为O(1)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

王道书代码：

bool InsertPriorNode(LNode *p, LNode *s){
    if(p==NULL || S==NULL)
        return false;
    
    s->next = p->next;
    p->next = s;  ///s连接到p
    ELemType temp = p->data;  //交换数据域部分
    p->data = s->data;
    s->data = temp;

    return true;
}
 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

5.按位序删除节点（带头结点）
ListDelete(&L, i, &e): 删除操作，删除表L中第i个位置的元素，并用e返回删除元素的值;头结点视为“第0个”结点；

思路：找到第i-1个结点，将其指针指向第i+1个结点，并释放第i个结点；

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

bool ListDelete(LinkList &L, int i, ElenType &e){
    if(i<1) return false;

    LNode *p;       //指针p指向当前扫描到的结点 
    int j=0;        //当前p指向的是第几个结点
    p = L;          //L指向头结点，头结点是第0个结点（不存数据）

    //循环找到第i-1个结点
    while(p!=NULL && j<i-1){     //如果i>lengh, p最后会等于NULL
        p = p->next;             //p指向下一个结点
        j++;
    }

    if(p==NULL) 
        return false;
    if(p->next == NULL) //第i-1个结点之后已无其他结点
        return false;

    LNode *q = p->next;         //令q指向被删除的结点
    e = q->data;                //用e返回被删除元素的值
    p->next = q->next;          //将*q结点从链中“断开”
    free(q)                     //释放结点的存储空间

    return true;
}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

时间复杂度分析：
最坏，平均时间复杂度：O(n)

最好时间复杂度：删除第一个结点 O(1)

6.指定结点的删除

bool DeleteNode(LNode *p){
    if(p==NULL)
        return false;
    
    LNode *q = p->next;      //令q指向*p的后继结点
    p->data = p->next->data; //让p和后继结点交换数据域
    p->next = q->next;       //将*q结点从链中“断开”
    free(q);
    return true;
} //时间复杂度 = O(1)


1
2
3
4
5
6
7
8
9
10
11
12

2.3.3单链表的查找

按位查找
==GetElem(L, i): ==按位查找操作，获取表L中第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;               //返回p指针指向的值
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

平均时间复杂度O（n）

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

LNode * LocateElem(LinkList L, ElemType e){
    LNode *P = L->next;    //p指向第一个结点
    //从第一个结点开始查找数据域为e的结点
    while(p!=NULL && p->data != e){
        p = p->next;
    }
    return p;           //找到后返回该结点指针，否则返回NULL
}


1
2
3
4
5
6
7
8
9
10

2.3.4求单链表的长度

== Length(LinkList L)==：计算单链表中数据结点（不含头结点）的个数，需要从第一个结点看是顺序依次访问表中的每个结点。算法的时间复杂度为O（n）。

int Length(LinkList L){
    int len=0;       //统计表长
    LNode *p = L;
    while(p->next != NULL){
        p = p->next;
        len++;
    }
    return len;
}


1
2
3
4
5
6
7
8
9
10
11

2.3.5单链表的创建操作

1.头插法建立单链表（平均时间复杂度O(n)）
思路：每次都将生成的结点插入到链表的表头。

LinkList List_HeadInsert(LinkList &L){       //逆向建立单链表
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));     //建立头结点
    L->next = NULL;                          //初始为空链表,这步不能少！

    scanf("%d", &x);                         //输入要插入的结点的值
    while(x!=9999){                          //输入9999表结束
        s = (LNode *)malloc(sizeof(LNode));  //创建新结点
        s->data = x;
        s->next = L->next;
        L->next = s;                         //将新结点插入表中，L为头指针
        scanf("%d", &x);   
    }
    return L;
   
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.尾插法建立单链表（时间复杂度O（n））
思路：每次将新节点插入到当前链表的表尾，所以必须增加一个尾指针r,使其始终指向当前链表的尾结点。好处：生成的链表中结点的次序和输入数据的顺序会一致。

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

链表的逆置：
算法思想：逆置链表初始为空，原表中结点从原链表中依次“删除”，再逐个插入逆置链表的表头（即“头插”到逆置链表中），使它成为逆置链表的“新”的第一个结点，如此循环，直至原链表为空；

LNode *Inverse(LNode *L)
{
	LNode *p, *q;
	p = L->next;     //p指针指向第一个结点
	L->next = NULL;  //头结点指向NULL

	while (p != NULL){
		q = p;
		p = p->next;
		q->next = L->next;  
		L->next = q;
	}
	return L;



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.3.6双链表

双链表中节点类型的描述：`

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


1
2
3
4
5
6

双链表的初始化（带头结点）

typedef struct DNode{            //定义双链表结点类型
    ElemType data;               //数据域
    struct DNode \*prior, \*next;  //前驱和后继指针
}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;
}

void testDLinkList(){
    //初始化双链表
    DLinklist L;         // 定义指向头结点的指针L
    InitDLinkList(L);    //申请一片空间用于存放头结点，指针L指向这个头结点
    //...
}

//判断双链表是否为空
bool Empty(DLinklist L){
    if(L->next == NULL)    //判断头结点的next指针是否为空
        return true;
    else
        return false;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

双链表的插入操作
后插操作
InsertNextDNode(p, s): 在p结点后插入s结点

bool InsertNextDNode(DNode \*p, DNode \*s){ //将结点 \*s 插入到结点 \*p之后
    if(p==NULL || s==NULL) //非法参数
        return false;
    
    s->next = p->next;
    if (p->next != NULL)   //p不是最后一个结点=p有后继结点 
        p->next->prior = s;
    s->prior = p;
    p->next = s;
    
    return true;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14

按位序插入操作：
思路：从头结点开始，找到某个位序的前驱结点，对该前驱结点执行后插操作；
前插操作：
思路：找到给定结点的前驱结点，再对该前驱结点执行后插操作；
双链表的删除操作
删除p节点的后继节点

//删除p结点的后继结点
bool DeletNextDNode(DNode \*p){
    if(p==NULL) return false;
    DNode \*q =p->next;            //找到p的后继结点q
    if(q==NULL) return false;     //p没有后继结点;
    p->next = q->next;
    if(q->next != NULL)           //q结点不是最后一个结点
        q->next->prior=p;
    free(q);

    return true;
}

//销毁一个双链表
bool DestoryList(DLinklist &L){
    //循环释放各个数据结点
    while(L->next != NULL){
        DeletNextDNode(L);  //删除头结点的后继结点
    free(L); //释放头结点
    L=NULL;  //头指针指向NULL

    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

双链表的遍历操作
前向遍历

while(p!=NULL){
    //对结点p做相应处理，eg打印
    p = p->prior;
}


1
2
3
4
5
6

后向遍历

while(p!=NULL){
    //对结点p做相应处理，eg打印
    p = p->next;
}


1
2
3
4
5
6

注意：双链表不可随机存取，按位查找和按值查找操作都只能用遍历的方式实现，时间复杂度为O(n)
在这里插入图片描述

2.3.7循环链表

1.循环单链表
最后一个结点的指针不是NULL,而是指向头结点

typedef struct LNode{            
    ElemType data;               
    struct LNode \*next;  
}DNode, \*Linklist;

/初始化一个循环单链表
bool InitList(LinkList &L){
    L = (LNode \*)malloc(sizeof(LNode)); //分配一个头结点
    if(L==NULL)             //内存不足，分配失败
        return false;
    L->next = L;            //头结点next指针指向头结点
    return true;
}

//判断循环单链表是否为空（终止条件为p或p->next是否等于头指针）
bool Empty(LinkList L){
    if(L->next == L)
        return true;    //为空
    else
        return false;
}

//判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L, LNode \*p){
    if(p->next == L)
        return true;
    else
        return false;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

单链表和循环单链表的比较：
**单链表：**从一个结点出发只能找到该结点后续的各个结点；对链表的操作大多都在头部或者尾部；设立头指针，从头结点找到尾部的时间复杂度=O(n)，即对表尾进行操作需要O(n)的时间复杂度;
**循环单链表：**从一个结点出发，可以找到其他任何一个结点；设立尾指针，从尾部找到头部的时间复杂度为O(1)，即对表头和表尾进行操作都只需要O(1)的时间复杂度;

==优点：==从表中任一节点出发均可找到表中其他结点。

2.循环双链表
表头结点的prior指向表尾结点，表尾结点的next指向头结点

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

//初始化空的循环双链表
bool InitDLinkList(DLinklist &L){
    L = (DNode \*) malloc(sizeof(DNode));    //分配一个头结点
    if(L==NULL)            //内存不足，分配失败
        return false;  
    L->prior = L;          //头结点的prior指向头结点
    L->next = L;           //头结点的next指向头结点
}

void testDLinkList(){
    //初始化循环单链表
    DLinklist L;
    InitDLinkList(L);
    //...
}

//判断循环双链表是否为空
bool Empty(DLinklist L){
    if(L->next == L)
        return true;
    else
        return false;
}

//判断结点p是否为循环双链表的表尾结点
bool isTail(DLinklist L, DNode \*p){
    if(p->next == L)
        return true;
    else
        return false;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

双链表的插入（循环双链表）：

bool InsertNextDNode(DNode \*p, DNode \*s){ 
    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;


1
2
3
4
5
6
7

双链表的删除

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


1
2
3
4
5
6

双向循环链表:
和单链的循环表类似，双向链表也可以有循环表，让头结点的前驱指针指向链表的最后一个结点，让最后一个结点的后继指针指向头结点。
在这里插入图片描述
结构定义：

typedef struct DuLNode{
	Elemtype data;
	struct DulNode \*prior,\*next;
	
} DuLNode,\*DuLinkList;

1
2
3
4
5
6

2.3.8静态链表

1. 定义：

单链表：各个结点散落在内存中的各个角落，每个结点有指向下一个节点的指针(下一个结点在内存中的地址);
静态链表：用数组的方式来描述线性表的链式存储结构: 分配一整片连续的内存空间，各个结点集中安置，包括了——数据元素and下一个结点的数组下标(游标)
- 其中数组下标为0的结点充当"头结点"
- 游标为-1表示已经到达表尾
- 若每个数据元素为4B，每个游标为4B，则每个结点共8B；假设起始地址为addr，则数据下标为2的存放地址为：addr+8*2
- 注意： 数组下标——物理顺序，位序——逻辑顺序；
- 优点：增、删操作不需要大量移动元素；
- 缺点：不能随机存取，只能从头结点开始依次往后查找，容量固定不变！

2.静态链表用代码表示：

#define MaxSize 10 //静态链表的最大长度

struct Node{              //静态链表结构类型的定义
    ElemType data;        //存储数据元素
    int next;             //下一个元素的数组下标(游标)
};

//用数组定义多个连续存放的结点
void testSLinkList(){
    struct Node a[MaxSize];  //数组a作为静态链表, 每一个数组元素的类型都是struct Node
    //...
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14

也可以这样：

#define MaxSize 10 //静态链表的最大长度

typedef struct{           //静态链表结构类型的定义
    ELemType data;        //存储数据元素
    int next;             //下一个元素的数组下标
}SLinkList[MaxSize];

void testSLinkList(){
    SLinkList a;
}


1
2
3
4
5
6
7
8
9
10
11
12

也等同于：

#define MaxSize 10 //静态链表的最大长度

struct Node{              //静态链表结构类型的定义
    ElemType data;        //存储数据元素
    int next;             //下一个元素的数组下标(游标)
};

typedef struct Node SLinkList[MaxSize]; //重命名struct Node，用SLinkList定义“一个长度为MaxSize的Node型数组;



1
2
3
4
5
6
7
8
9
10
11

注意：SLinkList a 强调a是静态链表；struct Node a 强调a是一个Node型数组；

3.静态链表基本操作的实现

初始化静态链表：把a[0]的next设为-1
查找某个位序（不是数组下标，位序是各个结点在逻辑上的顺序）的结点：从头结点出发挨个往后遍历结点，时间复杂度O=(n)
在位序为i上插入结点：① 找到一个空的结点，存入数据元素；② 从头结点出发找到位序为i-1的结点；③修改新结点的next；④ 修改i-1号结点的next；
删除某个结点：① 从头结点出发找到前驱结点；② 修改前驱节点的游标；③ 被删除节点next设为-2；

2.3.9 顺序表和链表的比较

1.逻辑结构

顺序表和链表都属于线性表，都是线性结构

2.存储结构

顺序表：顺序存储
- 优点：支持随机存取，存储密度高
- 缺点：大片连续空间分配不方便，改变容量不方便
链表：链式存储
- 优点：离散的小空间分配方便，改变容量方便
- 缺点：不可随机存取，存储密度低

3. 基本操作 - 创建

顺序表：需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量；若分配空间过大，则浪费内存资源；
静态分配：静态数组，容量不可改变
动态分配：动态数组，容量可以改变，但是需要移动大量元素，时间代价高（malloc(),free()）
链表：只需要分配一个头结点或者只声明一个头指针

4. 基本操作 - 销毁

顺序表：修改 Length = 0
- 静态数组——系统自动回收空间

typedef struct{
    ElemType \*data;
    int MaxSize;
    int length;
}SeqList; 

1
2
3
4
5
6

动态分配：动态数组——需要手动free()

//创
L.data = (ELemType \*)malloc(sizeof(ElemType) \*InitSize)
//销
free(L.data);

//！malloc() 和 free() 必须成对出现


1
2
3
4
5
6
7
8

5.基本操作-增/删

顺序表：插入/删除元素要将后续元素后移/前移；时间复杂度=O(n)，时间开销主要来自于移动元素；
链表：插入/删除元素只需要修改指针；时间复杂度=O(n)，时间开销主要来自查找目标元素

6.基本操作-查

顺序表
- 按位查找：O(1)
按值查找：O(n)，若表内元素有序，可在O(log2n)时间内找到
链表
- 按位查找：O(n)
- 按值查找：O(n)

2.3.10顺序、链式、静态、动态四种存储方式的比较

顺序存储的固有特点：
逻辑顺序与物理顺序一直，本质上是用数组存储线性表的各个元素（即随机存取）；存储密度大，存储空间利用率高。
链式存储的固有特点：
元素之间的关系采用这些元素所在的节点的“指针”信息表示（插、删不需要移动节点）。
静态存储的固有特点：
在程序运行的过程中不要考虑追加内存的分配问题。
动态存储的固有特点：
可动态分配内存；有效的利用内存资源，使程序具有可扩展性。

2.3.11链表的逆置算法

思路：先将链表一个一个的断开，再将断开的链表插入到原来的队列中
在这里插入图片描述

第三章：栈和队列

3.1栈（stack）

3.1.1栈的基本概念

标题

1.栈的定义

栈是特殊的线性表：只允许在一端进行插入或删- 除操作，其逻辑结构与普通线性表相同；
栈顶（Top）：允许进行插入和删除的一端（最上面的为栈顶元素）；
栈底（Bottom）：固定的，不允许进行插入和删除的一端（最下面的为栈底元素）；
空栈：不含任何元素的空表；
特点：后进先出（后进栈的元素先出栈）；
缺点：栈的大小不可变，解决方法——共享栈；

2.栈的基本操作

“创建&销毁”

InitStack(&S) 初始化栈：构造一个空栈S，分配内存空间；
DestroyStack(&S) 销毁栈：销毁并释放栈S所占用的内存空间；

“增&删”

Push(&S, x) 进栈：若栈S未满，则将x加入使其成为新栈顶；
Pop(&S, &x) 出栈：若栈S非空，则弹出（删除）栈顶元素，并用x返回；
“查&其他”
GetTop(S, &x) 读取栈顶元素：若栈S非空，则用x-返回栈顶元素；（栈的使用场景大多只访问栈顶元素）；
StackEmpty(S) 判空：断一个栈S是否为空，若S为空，则返回true,否则返回false；

3.1.2 栈的顺序存储

1.顺序栈的定义

#define MaxSize 10 //定义栈中元素的最大个数

typedef struct{
    ElemType data[MaxSize];       //静态数组存放栈中元素
    int top;                      //栈顶元素
}SqStack;

void testStack(){
    SqStack S;       //声明一个顺序栈(分配空间)
                     //连续的存储空间大小为 MaxSize\*sizeof(ElemType)
}


1
2
3
4
5
6
7
8
9
10
11
12
13

2.顺序栈的基本操作

#define MaxSize 10 //定义栈中元素的最大个数

typedef struct{
    ElemType data[MaxSize];       //静态数组存放栈中元素
    int top;                      //栈顶元素
}SqStack;

//初始化栈
void InitStack(SqStack &S){
    S.top = -1;                   //初始化栈顶指针
}

//判栈空
bool StackEmpty(SqStack S){
    if(S.top == -1)      //栈空
        return true;
    else                 //栈不空
        return false;
}

//新元素进栈
bool Push(SqStack &S, ElemType x){
    if(S.top == MaxSize - 1)        //栈满
        return false;
    
    S.top = S.top + 1;    //指针先加1
    S.data[S.top] = x;    //新元素入栈

    /\*
 S.data[++S.top] = x;
 \*/
    return true;
}

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

    /\*
 x = S.data[S.top--];
 \*/

    //只是逻辑上的删除，数据依然残留在内存里

}

//读栈顶元素
bool GetTop(SqStack S, ElemType &x){
    if(S.top == -1)
        return false;
    
    x = S.data[S.top];      //x记录栈顶元素
    return true; 
}


void testStack(){
    SqStack S;       //声明一个顺序栈(分配空间)
    InitStack(S);
    //...
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

**注意：**也可以初始化时定义 S.top = 0 ：top指针指向下一个可以插入元素的位置(栈顶元素的后一个位置)；

进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素。S.data[S.top++] = x;
出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1。`x = S.data[–S.top];
栈空条件：S.top==-1
栈满条件：S.top==MaxSize-1
栈长：S.top+1

3.共享栈
**定义：**利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。

存取数据的时间复杂度均为O（1）

#define MaxSize 10 //定义栈中元素的最大个数

typedef struct{
    ElemType data[MaxSize];       //静态数组存放栈中元素
    int top0;                     //0号栈栈顶指针
    int top1;                     //1号栈栈顶指针
}ShStack;

//初始化栈
void InitSqStack(ShStack &S){
    S.top0 = -1;        //初始化栈顶指针
    S.top1 = MaxSize;   
}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

栈满条件：top1-top0=1

3.1.3栈的链式存储

1.定义：采用链式存储的栈称为链栈。
2.优点：链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。
3.特点：

进栈和出栈都只能在栈顶一端进行(链头作为栈顶)
链表的头部作为栈顶，意味着：

在实现数据"入栈"操作时，需要将数据从链表的头部插入；
在实现数据"出栈"操作时，需要删除链表头部的首元节点；
因此，链栈实际上就是一个只能采用头插法插入或删除数据的链表;
栈的链式存储结构可描述为：

typedef struct Linknode{
    ElemType data;              //数据域
    struct Linknode \*next;      //指针域
}\*LiStack;                      //栈类型的定义


1
2
3
4
5
6

栈的基本操作：

初始化
进栈
出栈
获取栈顶元素
判空、判满
带头结点的链栈基本操作：

#include<stdio.h>

struct Linknode{
    int data;             //数据域
    Linknode \*next;       //指针域
}Linknode,\*LiStack;   

typedef Linknode \*Node;   //结点结构体指针变量
typedef Node List;        //结点结构体头指针变量

//1. 初始化
void InitStack(LiStack &L){   //L为头指针
    L = new Linknode; 
    L->next = NULL;
}

//2.判栈空
bool isEmpty(LiStack &L){
    if(L->next == NULL){
        return true;
    }
    else
        return false;
}

//3. 进栈(：链栈基本上不会出现栈满的情况)
void pushStack(LiStack &L, int x){
    Linknode s;          //创建存储新元素的结点
    s = new Linknode;
    s->data = x;

    //头插法
    s->next = L->next;
    L->next = s;
}

//4.出栈
bool popStack(LiStack &L, int &x){
    Linknode s;
    if(L->next == NULL) //栈空不能出栈
        return false;
    
    s = L->next;
    x = s->data;
    L->next = L->next->next;
    delete(s);

    return true;
}




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

不带头结点的链栈基本操作：

#include<stdio.h>

struct Linknode{
    int data;             //数据域
    Linknode \*next;       //指针域
}Linknode,\*LiStack;   

typedef Linknode \*Node;   //结点结构体指针变量
typedef Node List;        //结点结构体头指针变量

//1.初始化 
void initStack(LiStack &L){
    L=NULL;
}

//2.判栈空
bool isEmpty(LiStack &L){
    if(L == NULL)
        return true;
    else
        teturn false;
}

//3.进栈
void pushStack(LiStack &L, int x){
    Linknode s;          //创建存储新元素的结点
    s = new Linknode;

    s->next = L;
    L = s;
}

//4.出栈
bool popStack(LiStack &L, int &x){
    Linknode s; 
    if(L = NULL)     //栈空不出栈
        return false;

    s = L;
    x = s->data;
    L = L->next;
    delete(s);
    
    return true;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

3.2队列（Queue）

3.2.1队列的基本概念

1.定义：队列（Queue）简称队，是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。
2.特点

队列是操作受限的线性表，只允许在一端进行插入 (入队)，另一端进行删除 (出队)
操作特性：先进先出 FIFO
队头：允许删除的一端
队尾：允许插入的一端
空队列：不含任何元素的空表
3.队列的基本操作
“创建&销毁”
InitQueue(&Q): 初始化队列，构造一个空列表Q
DestroyQueue(&Q): 销毁队列，并释放队列Q所占用的内存空间
“增&删”
EnQueue(&Q, x): 入队，若队列Q未满，将x加入，使之成为新的队尾
DeQueue(&Q, &x): 出队，若队列Q非空，删除队头元素，并用x返回
“查&其他”
GetHead(Q,&x): 读队头元素，若队列Q非空，则将队头元素赋值给x
QueueEmpty(Q): 判队列空，若队列Q为空，则返回

3.2.2队列的顺序存储结构

队头指针：指向队头元素
队尾指针：指向队尾元素的下一个位置

队列存储的基本操作

//队列的顺序存储类型
# define MaxSize 10; //定义队列中元素的最大个数
typedef struct{
    ElemType data[MaxSize];   //用静态数组存放队列元素
                              //连续的存储空间，大小为——MaxSize\*sizeof(ElemType)
    int front, rear;          //队头指针和队尾指针
}SqQueue;

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

void test{
    SqQueue Q;                //声明一个队列
    InitQueue(Q);
    //...
}

// 判空
bool QueueEmpty(SqQueue 0){
    if(Q.rear == Q.front)    //判空条件后
        return true;
    else 
        return false;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

循环队列
定义：将循环队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。
基本操作：

a%b == a除以b的余数

初始：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


1
2
3
4
5
6
7
8
9
10
11

区分队空还是队满的情况：
方案一: 牺牲一个单元来区分队空和队满
队尾指针的再下一个位置就是队头，即 (Q.rear+1)%MaxSize == Q.front

循环队列——入队：只能从队尾插入（判满使用方案一）

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

    return true;
}



1
2
3
4
5
6
7
8
9
10
11

循环队列——出队：只能让队头元素出队

//出队，删除一个队头元素，用x返回
bool DeQueue(SqQueue &Q, ElemType &x){
    if(Q.rear == Q.front)              //队空报错
        return false;  

    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize; //队头指针后移动

    return true;
}


1
2
3
4
5
6
7
8
9
10
11
12

循环队列——获得队头元素

bool GetHead(SqQueue &Q, ElemType &x){
    if(Q.rear == Q.front)              //队空报错
        return false;  

    x = Q.data[Q.front];
    return true;
}


1
2
3
4
5
6
7
8
9

方案二: 不牺牲存储空间，设置size
定义一个变量 size用于记录队列此时记录了几个数据元素，初始化 size = 0，进队成功 size++，出队成功size--，根据size的值判断队满与队空

队满条件：size == MaxSize

队空条件：size == 0

# define MaxSize 10; 
typedef struct{
    ElemType data[MaxSize];   
    int front, rear;        
    int size;               //队列当前长度
}SqQueue;

//初始化队列
void InitQueue(SqQueue &Q){
    Q.rear = Q.front = 0;
    size = 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14

方案三: 不牺牲存储空间，设置tag
定义一个变量 tag，tag = 0 --最近进行的是删除操作；tag = 1 --最近进行的是插入操作；

每次删除操作成功时，都令tag = 0；只有删除操作，才可能导致队空；
每次插入操作成功时，都令tag = 1；只有插入操作，才可能导致队满；
队满条件：Q.front == Q.rear && tag == 1

队空条件：Q.front == Q.rear && tag == 0

# define MaxSize 10; 
typedef struct{
    ElemType data[MaxSize];   
    int front, rear;        
    int tag;               //最近进行的是删除or插入
}SqQueue;



1
2
3
4
5
6
7
8
9

3.2.3队列的链式存储结构

1.定义：队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。
链队列：用链表表示的队列，是限制仅在表头删除和表尾插入的单链表。
队列的链式存储类型可描述为:

typedef struct LinkNode{      //链式队列结点
    ElemType data;
    struct LinkNode \*next;
}

typedef struct{               //链式队列
    LinkNode \*front, \*rear;   //队列的队头和队尾指针
}LinkQueue;


1
2
3
4
5
6
7
8
9
10

2.链式队列的基本操作——带头结点

初始化 & 判空

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

//判断队列是否为空
bool IsEmpty(LinkQueue Q){
    if(Q.front == Q.rear)     //也可用 Q.front -> next == NULL
        return true;
    else
        return false;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

入队操作

//新元素入队 (表尾进行)
void EnQueue(LinkQueue &Q, ElemType x){
    LinkNode \*s = (LinkNode \*)malloc(sizeof(LinkNode)); //申请一个新结点
    s->data = x;
    s->next = NULL;     //s作为最后一个结点，指针域指向NULL
    Q.rear->next = s;   //新结点插入到当前的rear之后
    Q.rear = s;         //表尾指针指向新的表尾
}


1
2
3
4
5
6
7
8
9
10

出队操作

//队头元素出队
bool DeQueue(LinkQueue &Q, ElemType &x){
    if(Q.front == Q.rear)
        return false;                    //空队
    
    LinkNode \*p = Q.front->next;         //p指针指向即将删除的结点 (头结点所指向的结点)
    x = p->data;
    Q.front->next = p->next;             //修改头结点的next指针
    if(Q.rear == p)                      //此次是最后一个结点出队
        Q.rear = Q.front;                //修改rear指针
    free(p);                             //释放结点空间

    return true;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

队列满的条件
顺序存储：预分配存储空间

链式存储：一般不会队满，除非内存不足

计算链队长度 (遍历链队)
设置一个int length 记录链式队列长度
初始化 & 判空
入队操作

//新元素入队 (表尾进行)
void EnQueue(LinkQueue &Q, ElemType x){
    LinkNode \*s = (LinkNode \*)malloc(sizeof(LinkNode)); //申请一个新结点
    s->data = x;
    s->next = NULL;

    //第一个元素入队时需要特别处理
    if(Q.front = NULL){            //在空队列中插入第一个元素
        Q.front = s;               //修改队头队尾指针
        Q.rear = s;
    }else{
        Q.rear->next = s;           //新结点插入到rear结点之后
        Q.rear = s;                 //修改rear指针指向新的表尾结点
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.2.4双端队列

1.定义：双端队列是指允许两端都可以进行入队和出队操作的队列

双端队列允许从两端插入、两端删除的线性表；
如果只使用其中一端的插入、删除操作，则等同于栈；
输入受限的双端队列：允许一端插入，两端删除的线性表；
输出受限的双端队列：允许两端插入，一端删除的线性表；

在这里插入图片描述

3.2.5循环队列

利用一组地址连续的存储单元依次存放队列中的数据元素。因为队头和队尾的位置是变化的。所以：设头、尾指针。

求循环队列的长度：
在这里插入图片描述

3.3栈的应用

3.3.1栈在括号匹配中的应用

用栈实现括号匹配

((())) 最后出现的左括号最先被匹配 (栈的特性—LIFO);
遇到左括号就入栈;
遇到右括号，就“消耗”一个左括号 (出栈);
匹配失败情况：
扫描到右括号且栈空，则该右括号单身;
扫描完所有括号后，栈非空，则该左括号单身;
左右括号不匹配;

代码：

#define MaxSize 10 

typedef struct{
    char data[MaxSize];
    int top;
} SqStack;

//初始化栈
InitStack(SqStack &S)

//判断栈是否为空
bool 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;       
        }
    }

    StackEmpty(S);                //栈空说明匹配成功
}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

3.3.2栈在表达式求值中的应用

1. 中缀表达式 (需要界限符)
运算符在两个操作数中间:

① a + b
② a + b - c
③ a + b - c\*d
④ ((15 ÷ (7-(1+1)))×3)-(2+(1+1))
⑤ A + B × (C - D) - E ÷ F

1
2
3
4
5
6

2. 后缀表达式 (逆波兰表达式)
运算符在两个操作数后面:

① a b +
② ab+ c - / a bc- +
③ ab+ cd\* -
④ 15 7 1 1 + - ÷ 3 × 2 1 1 + + -
⑤ A B C D - × + E F ÷ - (机算结果)
  A B C D - × E F ÷ - + (不选择)


1
2
3
4
5
6
7
8

中缀表达式转后缀表达式-手算
步骤1：确定中缀表达式中各个运算符的运算顺序

步骤2：选择下一个运算符，按照[左操作数右操作数运算符]的方式组合成一个新的操作数

步骤3：如果还有运算符没被处理，继续步骤2

“左优先”原则: 只要左边的运算符能先计算，就优先算左边的 (保证运算顺序唯一)；

中缀：A + B - C \* D / E + F
       ①   ④   ②   ③   ⑤     
后缀：A B + C D \* E / - F +

1
2
3
4

重点：中缀表达式转后缀表达式-机算
初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。从左到右处理各个元素，直到末尾。可能遇到三种情况:

遇到操作数: 直接加入后缀表达式。
遇到界限符: 遇到 ‘(’ 直接入栈; 遇到 ‘)’ 则依次弹出栈内运算符并加入后缀表达式，直到弹出 ‘(’ 为止。注意: '(' 不加入后缀表达式。
遇到运算符: 依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到 ‘(’ 或栈空则停止。之后再把当前运算符入栈。
按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

后缀表达式的计算—手算:
从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应的运算，合体为一个操作数；

注意： 两个操作数的左右顺序

1
2

重点：后缀表达式的计算—机算
用栈实现后缀表达式的计算（栈用来存放当前暂时不能确定运算次序的操作数）

步骤1: 从左往后扫描下一个元素，直到处理完所有元素;

步骤2: 若扫描到操作数，则压入栈，并回到步骤1;否则执行步骤3;

步骤3: 若扫描到运算符，则弹出两个栈顶元素，执行相应的运算，运算结果压回栈顶，回到步骤1;

注意: 先出栈的是“右操作数”

3.前缀表达式 (波兰表达式)
运算符在两个操作数前面:

① + a b
② - +ab  c
③ - +ab \*cd

1
2
3
4

中缀表达式转前缀表达式—手算
步骤1：确定中缀表达式中各个运算符的运算顺序

步骤2：选择下一个运算符，按照[运算符左操作数右操作数]的方式组合成一个新的操作数

步骤3：如果还有运算符没被处理，就继续执行步骤2

“右优先”原则: 只要右边的运算符能先计算，就优先算右边的;

中缀：A + B \* (C - D) - E / F
       ⑤   ③    ②    ④   ①
前缀：+ A - \* B - C D / E F

1
2
3
4

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

步骤1: 从右往左扫描下一个元素，直到处理完所有元素；

步骤2: 若扫描到操作数则压入栈，并回到步骤1，否则执行步骤3

步骤3: 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到步骤1；

注意: 先出栈的是“左操作数”

4.中缀表达式的计算(用栈实现)
两个算法的结合：中缀转后缀 + 后缀表达式的求值

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

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

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

3.3.3栈在递归中的应用

函数调用的特点：最后被调用的函数最先执行结束(LIFO)

函数调用时，需要用一个栈存储：

调用返回地址
实参
局部变量

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

每进入一层递归，就将递归调用所需信息压入栈顶；
每退出一层递归，就从栈顶弹出相应信息；

**缺点：**太多层递归可能回导致栈溢出；

适合用“递归”算法解决：可以把原始问题转换为属性相同，但规模较小的问题；

3.4特殊矩阵的压缩存储

矩阵定义：一个由m*n个元素排成的m行(横向)n列(纵向)的表。
矩阵的常规存储：将矩阵描述为一个二维数组。

3.4.1数组的存储结构

1.一维数组

Elemtype a[10];


1
2
3

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

起始地址：LOC

数组下标：默认从0开始！

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

2.二维数组

Elemtype b[2][4]; //2行4列的二维数组


1
2
3

行优先/列优先存储优点：实现随机存储

起始地址：LOC

M行N列的二维数组 b[M][N] 中，b[i][j]的存储地址：

行优先存储: LOC + (i×N + j) × sizeof(ElemType)
列优先存储：LOC + (j×M + i) × sizeof(ElemType)

3.4.2普通矩阵的存储

二维数组存储：

描述矩阵元素时，行、列号通常从1开始；
描述数组时，通常下标从 0 开始；

3.4.3特殊矩阵的存储

特殊矩阵——压缩存储空间（只存有用的数据）

矩阵的压缩存储：为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。

对称矩阵(方阵)

在一个n阶方阵A中，若元素满足下述性值：在这里插入图片描述
则称A为对称矩阵。

三角矩阵(方阵)
以主对角线划分，三角矩阵有上（下）三角两种。上（下）三角矩阵的下（上）三角（不含主对角线）中的元素均为常数。在大多数情况下，三角矩阵常数为零。

在这里插入图片描述

三对角矩阵(方阵)

对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一维数组中，且也能找到每个非零元素和向量下标的对应关系。
稀疏矩阵
设在mn的矩阵中有t个非零元素，令c=t/(mn),当c<=0.05时称为稀疏矩阵。
压缩存储原则：存各非零元的值、行列位置和矩阵的行列数。

顺序存储——三元组

在这里插入图片描述

链式存储——十字链表法
优点：它能够灵活得插入因运算而产生的新的非零元素，删除因运算而产生的新的零元素，实现矩阵的运算。
十字链表中结点的结构示意图：

right:用于链接同一行中的下一个非零元素；
down:用于链接同一列中的下一个非零元素。

第四章：串

4.1串的定义和实现

4.1.1串的定义

串: 零个或多个字符组成的有限序列，如 S = 'iPhone 11 Pro Max?'；
串名：S是串名；
串的长度：串中字符的个数n；
空串：n=0时的串；
子串：串中任意多个连续的字符组成的子序列称为该串的子串；
主串：包含子串的串；
字符在主串中的位置：某个字符在串中的序号（从1开始）；
子串在主串中的位置：子串的第一个字符在主串中的位置；
空串 V.S 空格串：
M = ‘’ 是空串；
N = ’ ’ 是空格串；
串 V.S 线性表：
串是特殊的线性表，数据元素之间呈线性关系（逻辑结构相似）；
串的数据对象限定为字符集：中文字符、英文字符、数字字符、标点字符…
串的基本操作，如增删改除通常以子串为操作对象

4.1.2串的基本操作

假设有串 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联接而成的新串———可能会导致存储空间的扩展；
例：

Concat(&T, S, W)

T = ‘iPhone 11 Pro Max?Pro’

1
2
3
4

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

SubString(&T, S, 4, 6)

T = ‘one 11’

1
2
3
4

Index(S, T): 定位操作，若主串S中存在与串T值相同的子串，则返回它再主串S中第一次出现的位置，否则函数值为0；
StrCompare(S, T): 串的比较操作，参照英文词典排序方式；若S > T,返回值>0; S = T,返回值=0 (需要两个串完全相同) ; S < T,返回值<0;

4.1.3串的存储结构

1定长顺序存储表示

#define MAXLEN 255 //预定义最大串长为255

typedef struct{
    char ch[MAXLEN];   //静态数组实现（定长顺序存储）
                       //每个分量存储一个字符
                       //每个char字符占1B
    int length;        //串的实际长度
}SString;

1
2
3
4
5
6
7
8
9

串长的两种表示法：
方案一：用一个额外的变量length来存放串的长度（保留ch[0]）；
方案二：用ch[0]充当length；
优点：字符的位序和数组下标相同；
方案三：没有length变量，以字符’\0’表示结尾（对应ASCII码的0）；
缺点：需要从头到尾遍历；
**方案四——最终使用方案：**ch[0]废弃不用，声明int型变量length来存放串的长度（方案一与方案二的结合）
基本操作实现（基于方案四）

#define MAXLEN 255

typedef struct{
    char ch[MAXLEN];   
    int length;       
}SString;

// 1. 求子串
bool SubString(SString &Sub, SString S, int pos, int len){
    //子串范围越界
    if (pos+len-1 > S.length)
        return false;
    
    for (int i=pos; i<pos+len; i++)
        Sub.cn[i-pos+1] = S.ch[i];
    
    Sub.length = len;

    return true;
}

// 2. 比较两个串的大小
int StrCompare(SString S, SString T){
    for (int i; i<S.length && i<T.length; i++){
        if(S.ch[i] != T.ch[i])
            return S.ch[i] - T.ch[i];
    }
    //扫描过的所有字符都相同，则长度长的串更大
    return S.length - T.length;
}

// 3. 定位操作
int Index(SString S, SString T){
    int i=1;
    n = StrLength(S);
    m = StrLength(T);
    SString sub;        //用于暂存子串

    while(i<=n-m+1){
        SubString(Sub,S,i,m);
        if(StrCompare(Sub,T)!=0)
            ++i;
        else 
            return i;    // 返回子串在主串中的位置
    }
    return 0;            //S中不存在与T相等的子串
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

2.堆分配存储表示
**堆存储结构的特点：**仍以一组空间足够大的、地址连续的存储单元依次存放字符序列，但它们的存储空间实在程序执行过程种动态分配的。
通常，C语言提供的串类型就是以这种存储方式实现的。由动态分配函数malloc()分配一块实际串长所需要的存储空间（“堆”），如果分配成功，则返回此空间的起始地址，作为串的基址。由free()释放串不再需要的空间，

**堆存储结构的优点：**堆存储结构既有顺序存储结构的特点，处理（随机取子串）方便，操作中对串长又没有任何限制，更显灵活，因此在串处理的应用程序中常被采用。

//动态数组实现
typedef struct{
    char \*ch;           //按串长分配存储区，ch指向串的基地址
    int length;         //串的长度
}HString;

HString S；
S.ch = (char \*) malloc(MAXLINE \* sizeof(char)); //基地址指针指向连续空间的起始位置
                                                //malloc()需要手动free()
S.length;



![img](https://img-blog.csdnimg.cn/img_convert/cc93367e2b1e3c8460a0c4cbe1af8237.png)
![img](https://img-blog.csdnimg.cn/img_convert/9bb34e2cdd3138ce01c37fad8a304c10.png)
![img](https://img-blog.csdnimg.cn/img_convert/29548b33e83a7694c5304f85462c8002.png)

**既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，涵盖了95%以上软件测试知识点，真正体系化！**

**由于文件比较多，这里只是将部分目录截图出来，全套包含大厂面经、学习笔记、源码讲义、实战项目、大纲路线、讲解视频，并且后续会持续更新**

**[需要这份系统化的资料的朋友，可以戳这里获取](https://bbs.csdn.net/forums/4f45ff00ff254613a03fab5e56a57acb)**



* `Index(S, T)`: 定位操作，若主串S中存在与串T值相同的子串，则返回它再主串S中第一次出现的位置，否则函数值为0；
* `StrCompare(S, T):` 串的比较操作，参照英文词典排序方式；若S > T,返回值>0; S = T,返回值=0 (需要两个串完全相同) ; S < T,返回值<0;


##### 4.1.3串的存储结构


1定长顺序存储表示



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#define MAXLEN 255 //预定义最大串长为255

typedef struct{
char ch[MAXLEN]; //静态数组实现（定长顺序存储）
//每个分量存储一个字符
//每个char字符占1B
int length; //串的实际长度
}SString;


* 串长的两种表示法：
* 方案一：用一个额外的变量length来存放串的长度（保留ch[0]）；
* 方案二：用ch[0]充当length；  
 优点：字符的位序和数组下标相同；
* 方案三：没有length变量，以字符’\0’表示结尾（对应ASCII码的0）；  
 缺点：需要从头到尾遍历；
* \*\*方案四——最终使用方案：\*\*ch[0]废弃不用，声明int型变量length来存放串的长度（方案一与方案二的结合）
* 基本操作实现（基于方案四）



1
2
3
4
5
6
7
8
9
10
11
12

#define MAXLEN 255

typedef struct{
char ch[MAXLEN];
int length;
}SString;

// 1. 求子串
bool SubString(SString &Sub, SString S, int pos, int len){
//子串范围越界
if (pos+len-1 > S.length)
return false;

for (int i=pos; i<pos+len; i++)
    Sub.cn[i-pos+1] = S.ch[i];

Sub.length = len;

return true;
1
2
3
4
5
6

}

// 2. 比较两个串的大小
int StrCompare(SString S, SString T){
for (int i; i<S.length && i<T.length; i++){
if(S.ch[i] != T.ch[i])
return S.ch[i] - T.ch[i];
}
//扫描过的所有字符都相同，则长度长的串更大
return S.length - T.length;
}

// 3. 定位操作
int Index(SString S, SString T){
int i=1;
n = StrLength(S);
m = StrLength(T);
SString sub; //用于暂存子串

while(i<=n-m+1){
    SubString(Sub,S,i,m);
    if(StrCompare(Sub,T)!=0)
        ++i;
    else 
        return i;    // 返回子串在主串中的位置
}
return 0;            //S中不存在与T相等的子串
1
2
3
4
5
6
7
8

}


2.堆分配存储表示  
 \*\*堆存储结构的特点：\*\*仍以一组空间足够大的、地址连续的存储单元依次存放字符序列，但它们的存储空间实在程序执行过程种动态分配的 。  
 通常，C语言提供的串类型就是以这种存储方式实现的。由动态分配函数malloc()分配一块实际串长所需要的存储空间（“堆”），如果分配成功，则返回此空间的起始地址，作为串的基址。由free()释放串不再需要的空间，


\*\*堆存储结构的优点：\*\*堆存储结构既有顺序存储结构的特点，处理（随机取子串）方便，操作中对串长又没有任何限制，更显灵活，因此在串处理的应用程序中常被采用。



1
2
3
4
5
6
7
8
9
10

//动态数组实现
typedef struct{
char *ch; //按串长分配存储区，ch指向串的基地址
int length; //串的长度
}HString;

HString S；
S.ch = (char *) malloc(MAXLINE * sizeof(char)); //基地址指针指向连续空间的起始位置
//malloc()需要手动free()
S.length;

[外链图片转存中…(img-U0zLQ1HF-1715112062722)]
[外链图片转存中…(img-Q0fIH0Vf-1715112062722)]
[外链图片转存中…(img-bjkBqZh4-1715112062722)]

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，涵盖了95%以上软件测试知识点，真正体系化！

由于文件比较多，这里只是将部分目录截图出来，全套包含大厂面经、学习笔记、源码讲义、实战项目、大纲路线、讲解视频，并且后续会持续更新

需要这份系统化的资料的朋友，可以戳这里获取

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/905136

2024年《王道》数据结构笔记整理2024_2024版王道数据结构pdf(1)，零基础也能看得懂

数据结构

第一章：绪论

1.1数据结构的基本概念

1.2数据结构的三要素

1.3算法的基本概念

1.4算法的时间复杂度

1.5算法的空间复杂度

第二章：线性表

2.1线性表的定义

2.2顺序表的定义

2.2.1静态分配:

2.2.2动态分配

2.2顺序表的基本操作

1.插入操作 ：平均时间复杂度O(n)

2.删除操作：平均时间复杂度O(n)

3.按位查找(获取L表中第i个位置的值)：平均时间复杂度O(1)

4.按值查找：平均时间复杂度O（n）

2.3线性表的链式表示

2.3.1 单链表的定义

2.3.2单链表上基本操作的实现

2.3.3单链表的查找

2.3.4求单链表的长度

2.3.5单链表的创建操作

2.3.6双链表

2.3.7循环链表

2.3.8静态链表

2.3.9 顺序表和链表的比较

2.3.10顺序、链式、静态、动态四种存储方式的比较

2.3.11链表的逆置算法

第三章：栈和队列

3.1栈（stack）

3.1.1栈的基本概念

标题

3.1.2 栈的顺序存储

3.1.3栈的链式存储

3.2队列（Queue）

3.2.1队列的基本概念

3.2.2队列的顺序存储结构

3.2.3队列的链式存储结构

3.2.4双端队列

3.2.5循环队列

3.3栈的应用

3.3.1栈在括号匹配中的应用

3.3.2栈在表达式求值中的应用

3.3.3栈在递归中的应用

3.4特殊矩阵的压缩存储

3.4.1数组的存储结构

3.4.2普通矩阵的存储

3.4.3特殊矩阵的存储

第四章：串

4.1串的定义和实现

4.1.1串的定义

4.1.2串的基本操作

4.1.3串的存储结构

1.插入操作：平均时间复杂度O(n)