DataStructure1（线性表和链表）

数据结构

宏定义

在本笔记中用到的宏定义，头文件为define.h

1
2
3
4
5
6
7
8
9
10
#ifndef __DEFINE_H
#define __DEFINE_H
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
#endif

第一章：线性表

  • 线性表的基本操作

    • 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。

    Tips

    1. 对数据的操作（记忆思路）—— 创销、增删改查

    2. C 语言函数的定义 —— <返回值类型> 函数名(<参数1类型> 参数1, <参数2类型> 参数2, ......)

    3. 实际开发中，可根据实际需求定义其他的基本操作

    4. 函数名和参数的形式、命名都可改变（Reference：严蔚敏版《数据结构》）

      • （提示：命名要有可读性）

    5. ==什么时候要传入引用 “&”== —— ==对参数的修改结果需要 “带回来”==

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      #include<stdio.h>

      // 函数参数是引用，x 是 main 中变量 x 的别名
      void test(int &x) {
          x = 1024;  // 直接修改别名，等价于修改 main 中的 x
          cout << "test 内部：x = " << x << endl;
      }

      int main() {
          int x = 1;
          cout << "调用 test 前：x = " << x << endl;
          test(x);  // 直接传变量，不需要取地址（&）
          cout << "调用 test 后：x = " << x << endl;
          return 0;
      }

1.1顺序表的定义

(Sequence List)

特点：逻辑上相邻的数据元素，其物理次序也是相邻的

  • 线性表中第(i + 1)个数据元素的存储位置LOC(ai+1)和第i个元素满足下列关系：
    LOC(ai+1) = LOC(ai) + l
    LOC(ai) = LOC(ai) + (i - 1) * l
    其中，l：代表每个元素所占的存储单元。
  • 1757817244037

顺序表的存储结构：

1
2
3
4
5
6
#define SQLMAXSIZE 100
typedef int SqlElemType;//sq为sequence的缩写：顺序
typedef struct __Sqlist {
	SqlElemType *base;
	int length;
} Sqlist;

1.1.1初始化

1.静态分配
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//顺序表的实现--静态分配

#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; 
}

2.动态分配
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
//顺序表的实现——动态分配
#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; 
}

  • Key: 动态申请和释放内存空间

    • C —— malloc、free 函数

      1
      L.data = (ElemType *)malloc (sizeof(ElemType) * InitSize);

    • C++ —— new、delete 关键字

  • IncreaseSize 函数的核心功能是给顺序表扩容（增加最大容量），过程是：

    • 申请一块更大的==新==内存空间
    • 将原数据==复制==到新空间
    • 释放原内存空间

  • 而 p 的作用就是临时保存原数组的地址，否则在申请新空间后，原地址会被覆盖，导致：

    • 无法将旧数据复制到新空间
    • 原内存空间无法释放（造成内存泄漏）

1.2顺序表的基本操作

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
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
#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;
    }
    // 顺序表初始长度为0
    L.length = 0;
}

// 基本操作：在L的位序i处插入元素e
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--) // 将第i个元素及之后的元素后移
        L.data[j] = L.data[j - 1];
    L.data[i - 1] = e; // 在位置i处放入e
    L.length++; // 长度加1
    return true;
}

int main() {
    // 声明一个顺序表
    SqList L;
    // 初始化顺序表
    InitList(L);
    // 此处省略一些代码，插入几个元素
    // 在顺序表L的位序3处插入元素3
    ListInsert(L, 3, 3);
    return 0;
}

i 范围是 [1, length + 1] 的原因

顺序表的位序（即参数 i）是从 1 开始计数的（而数组下标从 0 开始）。

  • 当 i = 1 时：表示在顺序表的第一个位置（对应数组下标 0）插入元素，这是 “最前面插入” 的情况。
  • 当 i = length + 1 时：表示在顺序表的最后一个元素之后插入（相当于 “尾插”）。

比如当前 length = 6，则 i 最大可以取 7（即 length + 1 = 6 + 1 = 7），对应在数组 data[6] 的位置插入元素（此时数组前 6 个位置 data[0]~data[5] 已有元素）。

1758074014196

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

1
2
3
4
5
6
7
8
9
10
11
12
13
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
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
#include <stdio.h>
// 假设 SqList 等相关定义如下（根据常见顺序表结构补充）
#define MaxSize 10
typedef struct {
    int data[MaxSize];
    int length;
} SqList;

// 初始化顺序表函数（假设存在）
void InitList(SqList &L) {
    L.length = 0;
    for (int i = 0; i < MaxSize; i++) {
        L.data[i] = 0;
    }
}

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

int main() {
    SqList L; // 声明一个顺序表
    InitList(L); // 初始化顺序表
    //...此处省略一些代码，插入几个元素（比如可以手动插入或通过其他函数插入）
    // 这里假设已经插入了元素，使得顺序表中有至少3个元素
    int e = -1; // 用变量e把删除的元素“带回来”
    if (ListDelete(L, 3, e))
        printf("已删除第3个元素,删除元素值为=%d\n", e);
    else
        printf("位序i不合法，删除失败\n");
    return 0;
}

1758075875915

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

  • 静态分配

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

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

  • 时间复杂度：O (1)

    由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第 i 个元素 ——“随机存取” 特性

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define InitSize 10  // 顺序表的初始长度
typedef struct {
    ElemType *data;  // 指示动态分配数组的指针
    int MaxSize;     // 顺序表的最大容量
    int length;      // 顺序表的当前长度
} SeqList;  // 顺序表的类型定义（动态分配方式）

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

1758676722083

1.1.6销毁，清空，检查为空

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
// 删除顺序表中指定位置的元素
// 参数：L-顺序表指针，position-要删除元素的位置（1-based），e-用于存储被删除元素的指针
// 返回值：成功返回OK，失败返回ERROR（位置无效时）
Status SqlDelete(Sqlist *L, int position, SqlElemType *e) {
    // 检查位置合法性（1 ≤ position ≤ 当前长度）
    if (position < 1 || position > L->length) {
        return ERROR;
    }
    
    // 记录被删除的元素
    *e = L->base[position - 1];
    
    // 将删除位置后的元素依次前移
    for (int i = position; i < L->length; i++) {
        L->base[i - 1] = L->base[i];
    }
    
    // 长度减1
    L->length--;
    return OK;
}

// 销毁顺序表（释放动态分配的内存）
// 参数：L-顺序表指针
// 返回值：成功返回OK，已释放过返回ERROR
Status SqlDestroy(Sqlist *L) {
    // 检查内存是否已释放
    if (!L->base) {
        return ERROR;
    }
    
    // 释放基地址指向的内存
    free(L->base);
    // 避免野指针（可选，视具体实现而定）
    L->base = NULL;
    L->length = 0;
    return OK;
}

// 清空顺序表（仅重置长度，不释放内存）
// 参数：L-顺序表指针
void SqlClear(Sqlist *L) {
    L->length = 0;  // 逻辑上清空，元素物理空间仍保留
}

// 判断顺序表是否为空
// 参数：L-顺序表指针
// 返回值：空返回TRUE，非空返回FALSE
Status SqlIsEmpty(Sqlist *L) {
    return (L->length == 0) ? TRUE : FALSE;
}
  • L->length
    当 L 是指针变量（指向结构体 / 类的指针）时，使用 -> 运算符访问其成员。
    例如：Sqlist *L;（L 是指向 Sqlist 结构体的指针），此时需用 L->length 访问 length 成员。
  • L.length
    当 L 是结构体 / 类的实例变量（非指针）时，使用 . 运算符访问其成员。
    例如：Sqlist L;（L 是 Sqlist 结构体的实例），此时需用 L.length 访问 length 成员。

1.3 线性表的链式表示

1.3.1单链表

1. 单链表的定义

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

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

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

  • next：是一个指针，指向struct LNode类型的数据，用于存放下一个节点的地址，通过这个指针将各个节点连接起来，形成链表

  • LNode：是struct LNode的别名，使用时可以直接用LNode代替struct LNode来定义节点变量

  • *LinkList：是struct LNode *的别名，表示指向链表节点的指针，通常用于表示整个链表（指向链表的头节点）

单链表的两种实现方式：

  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
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

//初始化一个空的单链表
bool InitList(LinkList &L){  //注意用引用 &  
    //不然后续操作是对L的复制品进行操作
    L = NULL; //空表，暂时还没有任何结点；
    return true;
}

void test(){
    LinkList L;  //声明一个指向单链表的指针: 头指针
    //初始化一个空表
    InitList(L);
    //...
}

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

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

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

带头结点和不带头结点的比较：

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

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

1759038586215

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
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;
}
  • p 是指向 LNode 类型结构体的指针，而 LNode 结构体中包含 next 成员（struct LNode *next;），所以可以通过 p->next 来访问该结点的 next 元素，进而操作链表的下一个结点
  • s->next = p->next; //将新结点 s 的指针域赋值为 p->next，使 s 的下一个结点指向 p 原本的下一个结点
  • p->next = s; //更新指针 p 的指针域，使其指向新结点 s，完成 “p → s → 原 p 的下一个结点” 的链接

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

3. 按位序插入（不带头结点）

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

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
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;

}
4. 指定结点的后插操作：

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

  • 就是上面代码（整合成一个函数了）
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
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)
}
5. 指定结点的前插操作

  • 法一：可以在参数里面加入头指针，循环查找p的前驱q，再对q后插，时间复杂度→O(n)

  • 法二：太妙了，虽然找不到p结点的前驱结点，但可以实现：

    1759042377590

    1759042398984

思想：设待插入结点是s，将s插入到p的前面。我们仍然可以将s插入到p的后面。然后将p->data与s->data交换，这样既能满足了逻辑关系，又能是的时间复杂度为==O(1)==.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//前插操作：在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)
6. 按位序删除节点（带头结点）

1759043556687

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

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

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

时间复杂度分析：

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

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

7. 指定结点的删除

  • 删除结点p，需要修改其前驱结点的 next 指针

    • 方法1：传入头指针，循环寻找p的前驱结点

    • 方法2：偷天换日（类似于结点前插的实现）

      1759043833755

      1759043862972

      1759043879571

1
2
3
4
5
6
7
8
9
10
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结点从链中“断开”
    freem(q);
    return true;
} //时间复杂度 = O(1)
  • But
  • 如果p是最后一个结点：q指针是指向p指针的next，也就是指向了NULL，执行到p->data=p->next->data，就会出错，因为q结点没有指向具体的结点，不能取得data域，就会出现空指针的错，只能用法一：
  • 只能从表头开始依次寻找p的前驱，时间复杂度O(n)

  • 单链表的局限性：无法逆向检索，有时候不太方便

  • 如果各个结点有前面的指针：双链表

    1759044287865

8. 按位查找

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

1
2
3
4
5
6
7
8
9
10
11
12
13
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指针指向的值
}

平均时间复杂度O（n）

9. 按值查找

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

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

平均时间复杂度O（n）

10. 求单链表的长度

Length(LinkList L)：计算单链表中数据结点（不含头结点）的个数，需要从第一个结点看是顺序依次访问表中的每个结点。

1
2
3
4
5
6
7
8
9
int Length(LinkList L){
    int len=0;       //统计表长
    LNode *p = L;
    while(p->next != NULL){
        p = p->next;
        len++;
    }
    return len;
}

平均时间复杂度O（n）

11. 尾插法建立单链表（时间复杂度O（n））

  • 类似按位序插入，每次把元素插入表尾

  • 但是每次插入都要从头遍历，平均时间复杂度O（n^2^）

  • 实际上没必要每次从表头开始遍历，可以设置一个表尾指针，指向表尾最后一个数据结点，类似后插操作

    1759063290329

    1759063312117

    1759063323881

    思路：每次将新节点插入到当前链表的表尾，所以必须增加一个尾指针r,使其始终指向当前链表的尾结点。好处：生成的链表中结点的次序和输入数据的顺序会一致。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
}

平均时间复杂度O（n）

1759063465306

1759063514398

1759063543740

12. 头插法建立单链表（平均时间复杂度O(n)）

  • 对头结点的后插操作

    思路：每次都将生成的结点插入到链表的表头。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
   
}
  • 1759064035519
  • 发现插入的是跟输入的是反的
  • 应用：

链表的逆置：（利用头插法）

  • 核心代码逻辑不变，取数据元素的时候，不适用scanf，而是通过一个指针去扫描，依次取得数据元素，

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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.3.2双链表

  • 单链表只包含指向后继节点的指针，找前驱结点复杂

  • 而双链表是在单链表基础上再增加一个指针域

    1759971587076

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

1
2
3
4
typedef struct DNode{            //定义双链表结点类型
    ElemType data;               //数据域
    struct DNode *prior, *next;  //前驱和后继指针
}DNode, *DLinklist;
  • DNode中的D：double
  • prior是指向结点的前驱结点
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
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;
}
2.双链表的插入操作
  • 后插操作
    InsertNextDNode(p, s): 在p结点后插入s结点

1759973073725

1
2
3
4
5
6
7
8
9
10
11
12
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;
}

如果没有后继节点，就不需要修改后继节点的前向指针

  • 按位序插入操作：
    思路：从头结点开始，找到某个位序的前驱结点，对该前驱结点执行后插操作；

  • 前插操作：
    思路：找到给定结点的前驱结点，再对该前驱结点执行后插操作；

==均转化为后插操作==

3.双链表的删除操作

删除p节点的后继节点 q

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//删除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

    }
}
4.双链表的遍历操作

前向遍历 

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

后向遍历 

1
2
3
4
while(p!=NULL){
    //对结点p做相应处理，eg打印
    p = p->next;
}
  • 注意：双链表不可随机存取，按位查找和按值查找操作都只能用遍历的方式实现，时间复杂度为O(n)

1.3.3循环链表

1.循环单链表

最后一个结点的指针不是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
26
27
28
29
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;
}

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

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

2.循环双链表

表头结点的prior指向表尾结点，表尾结点的next指向头结点

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
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
bool InsertNextDNode(DNode *p, DNode *s){ 
    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;
}

双链表的删除

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

双向循环链表:

和单链的循环表类似，双向链表也可以有循环表，让头结点的前驱指针指向链表的最后一个结点，让最后一个结点的后继指针指向头结点。

在这里插入图片描述

结构定义：

1
2
3
4
5
typedef struct DuLNode{
	Elemtype data;
	struct DulNode *prior,*next;
	
} DuLNode,*DuLinkList;

1.3.4静态链表

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

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

void testSLinkList(){
    SLinkList a;
}

也等同于：

1
2
3
4
5
6
7
8
#define MaxSize 10        //静态链表的最大长度

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

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

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

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

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

1.3.5顺序表和链表的比较

1.逻辑结构

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

2.存储结构

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

3. 基本操作 - 创建

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

4. 基本操作 - 销毁

  • 顺序表：修改 Length = 0
    • 静态数组——系统自动回收空间
1
2
3
4
5
typedef struct{
    ElemType *data;
    int MaxSize;
    int length;
}SeqList;
  • 动态分配：动态数组——需要手动free()
1
2
3
4
5
6
//创
L.data = (ELemType *)malloc(sizeof(ElemType) *InitSize)
//销
free(L.data);

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

5.基本操作-增/删

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

6.基本操作-查

  • 顺序表
    • 按位查找：O(1)（直接可以找到地址）
    • 按值查找：O(n)，若表内元素有序，可在O(log2n)时间内找到（折半查找）
  • 链表
    • 按位查找：O(n)
    • 按值查找：O(n)

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

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

1.3.7链表的逆置算法

思路：先将链表一个一个的断开，再将断开的链表插入到原来的队列中

在这里插入图片描述