首页 考研专业课 数据结构

# 2.1、线性表的定义和基本操作

如有侵权请联系删除。

# 2.1.1、线性表的定义：

​ 线性表是具有相同数据类型的 n (n>=0) 个数据元素的有限序列，其中 n 为表长，当 n = 0 时线性表是一个空表。若用 L 命名线性表，则其一般表示为：

L=(a1,a2,a3,...,ai,xi+1,...,an)L=(a_1,a_2,a_3,...,a_i,x_{i+1},...,a_n)

式中， a1a_1 是唯一的 “第一个元素”，又称表头元素；ana_n 是唯一的 “最后一个元素”，又称表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后驱。

​ 由此，线性表的特点是：

  • 表中元素的个数有限。
  • 表中元素具有逻辑上的顺序性，表中数据有其先后次序。
  • 表中元素都是数据元素，每个元素都是单个数据。
  • 表中元素的数据类型都相同，这意味着每个元素都占有相同大小的存储空间。
  • 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

# 2.1.2、线性表的操作：

​ 线性表的主要操作如下：

InitList (&L) ：初始化表。构造一个空的线性表。

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

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

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

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

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

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

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

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

# 2.2、线性表的顺序表示：

# 2.2.1、顺序表的定义：

​ 线性表的顺序储存又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第 1 个元素存储在线性表的起始位置，第 i 个元素的存储位置后面紧跟着存储位置的是第 i + 1 个元素，称 i 为元素 aia_i 在线性表中的位序。因此，顺序表的特点是表中元素的逻辑顺序与物理顺序相同。

​ 假设线性表 L 存储的起始地址为 LOC (A)，sizeof (ElemType) 是每个数据元素所占用内存空间的大小，则表 L 所对应的顺序存储如下图所示。

在这里插入图片描述

​ 通常用高级语言中的数组来描述线性表的顺序存储结构。

​ 假定线性表的元素类型为 ElemType ，则线性表的顺序存储类型描述为：

1
2
3
4
5
#define MaxSize 50					//定义线性表的最大长度
typedef struct {
    ElemType data[MaxSize];			//顺序表的元素
    int length;						//顺序表的当前长度
} SqList;							//顺序表的类型定义

​ 一维数组可以是静态分配的，也可以是动态分配的。在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据就会产生溢出，进而导致程序崩溃。

​ 而在动态分配时，存储数组的空间实在程序执行过程中通过动态存储分配语句分配到，一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空间的目的，而不需要为线性表依次性地划分所有空间。

1
2
3
4
5
#define InitSize 100				//表长度的初始定义
typedef struct {
	ElemType *data;					//指示动态分配数组的指针
    int MaxSize,length;				//数组的最大容量和当前个数
} SeqList;							//动态分配数组顺序表定义

​ C 语言初始动态分配语句为：

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

​ 顺序表最主要的特点是随机访问，即通过首地址和元素序号可在时间 O (1) 内找到指定的元素。

​ 顺序表的存储密度高，每个结点只存储数据元素。

​ 顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

# 2.2.2、顺序表上基本操作的实现：

# （1）、插入操作：

​ 在顺序表 L 的第 i (1<= i <= L.Length+1) 个位置插入新元素 e 。若 i 的输入不合法，则返回 false ，表示插入失败；否则，将第 i 个元素及其后的所有元素依次往后移动一个位置，腾出一个空位置插入新元素 e ，顺序表长度增加 1，插入成功，返回 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
#include "stdio.h"
#define MaxSize 50

typedef struct {
    int data[MaxSize];
    int length;
} SqList;

int ListInsert(SqList *L,int i , int e);

int main(){
    SqList L;
    L.length = 0;
    for (int i = 0; i < 9; i++){
        L.data[i] = i + 1;
        L.length += 1;
    }

    ListInsert(&L,4,10);

    for (int i = 0; i < L.length; i++){
        printf("%d,",L.data[i]);
    }
    printf("\n%d",L.length);

    return 0;
}

//实现插入算法的主体函数
int ListInsert(SqList *L,int i , int e){
    if (i < 1 || i > L->length + 1)
        return 0;
    if (L->length >= MaxSize)
        return 0;
    for (int j = L->length;j >= i;j--)
        L->data[j] = L->data[j-1];
    L->data[i - 1] = e;
    L->length ++;
    return 1;
}

​ 注意：区别顺序表的为序和数组下标。

​ 最好情况：在表尾插入（i = n + 1），元素后移语句将不执行，时间复杂度为 O (1)。

​ 最坏情况：在表头插入（i = 1），元素后移语句将执行 n 次，时间复杂度为 O (n)。

​ 平均情况：假设 pip_i（pi=1/(n−1)p_i=1/(n-1)）是在第 i 个位置上插入一个结点的概率，则在长度为 n 的线性表中插入一个结点时，所需移动的结点平均次数为：

∑i=1n+1pi(n−i+1)=∑i=1n+11n+1(n−i+1)=1n+1∑i=1n+1(n−i+1)=1n+1n(n+1)2=n2\sum_{i=1}^{n+1}p_i(n-i+1)=\sum_{i=1}^{n+1}\frac{1}{n+1}(n-i+1)=\frac{1}{n+1}\sum_{i=1}^{n+1}(n-i+1)=\frac{1}{n+1}\frac{n(n+1)}{2}=\frac{n}{2}

​ 因此，顺序表插入算法的平均时间复杂度为 O (n)

# （2）、删除操作：

​ 删除顺序表 L 中第 i （1 <= i <= L.length）个位置的元素，用引用变量 e 返回。若 i 的输入不合法，则返回 false ；否则，将被删元素赋给引用变量 e ，并将 i + 1 个元素及其后的所有元素依次往前移动一个位置，返回 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"
#define MaxSize 50

typedef struct {
    int data[MaxSize];
    int length;
} SqList;

int ListInsert(SqList *L,int i , int e);
int ListDelete(SqList *L,int i , int *e);

int main(){
    SqList L;
    int e;
    L.length = 0;
    for (int i = 0; i < 9; i++){
        L.data[i] = i + 1;
        L.length += 1;
    }

    ListInsert(&L,4,10);
    ListDelete(&L,4,&e);
    
    for (int i = 0; i < L.length; i++){
        printf("%d,",L.data[i]);
    }
    printf("\n%d",e);

    return 0;
}

int ListInsert(SqList *L,int i , int e){
    if (i < 1 || i > L->length + 1)
        return 0;
    if (L->length >= MaxSize)
        return 0;
    for (int j = L->length;j >= i;j--)
        L->data[j] = L->data[j-1];
    L->data[i - 1] = e;
    L->length ++;
    return 1;
}

//实现删除算法的主体函数
int ListDelete(SqList *L,int i , int *e){
    if (i < 1 || i > L->length)
        return 0;
    *e = L->data[i-1];
    for (int j = i;j<L->length;j++)
        L->data[j-1] = L->data[j];
    L->length--;
    return 1;
}

​ 最好情况：删除表尾元素（即 i = n），无须移动元素，时间复杂度为 O (1)。

​ 最坏情况：删除表头元素（即 i = 1），需移动除表头元素以外的所有元素，时间复杂度为 O (n)。

​ 平均情况：假设 pip_i（pi=1/np_i=1/n）是删除第 i 个位置上结点的概率，则在长度为 n 的线性表中删除一个结点时，所需移动结点的平均次数为：

∑i=1n+1pi(n−i)=∑i=1n+11n+1(n−i)=1n∑i=1n+1(n−i)=1nn(n−1)2=n−12\sum_{i=1}^{n+1}p_i(n-i)=\sum_{i=1}^{n+1}\frac{1}{n+1}(n-i)=\frac{1}{n}\sum_{i=1}^{n+1}(n-i)=\frac{1}{n}\frac{n(n-1)}{2}=\frac{n-1}{2}

​ 因此，顺序表删除算法的平均时间复杂度为 O (n)。

​ 可见，顺序表中插入和删除操作的时间主要耗费在移动元素上，而移动元素的个数取决于插入和删除元素的位置。如下图所示：

在这里插入图片描述

# （3）、按值查找（顺序查找）

​ 在顺序表 L 中查找第一个元素值等于 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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include "stdio.h"
#define MaxSize 50

typedef struct {
    int data[MaxSize];
    int length;
} SqList;

int ListInsert(SqList *L,int i , int e);
int ListDelete(SqList *L,int i , int *e);
int LocateElem(SqList *L,int e);

int main(){
    SqList L;
    int e,index;
    L.length = 0;
    for (int i = 0; i < 9; i++){
        L.data[i] = i + 1;
        L.length += 1;
    }

    ListInsert(&L,4,10);
    ListDelete(&L,4,&e);

    for (int i = 0; i < L.length; i++){
        printf("%d,",L.data[i]);
    }
    printf("\n%d",e);
    index = LocateElem(&L,4);
    printf("\n%d",index);

    return 0;
}

int ListInsert(SqList *L,int i , int e){
    if (i < 1 || i > L->length + 1)
        return 0;
    if (L->length >= MaxSize)
        return 0;
    for (int j = L->length;j >= i;j--)
        L->data[j] = L->data[j-1];
    L->data[i - 1] = e;
    L->length ++;
    return 1;
}

int ListDelete(SqList *L,int i , int *e){
    if (i < 1 || i > L->length)
        return 0;
    *e = L->data[i-1];
    for (int j = i;j<L->length;j++)
        L->data[j-1] = L->data[j];
    L->length--;
    return 1;
}

//实现按值查找算法的主体函数
int LocateElem(SqList *L,int e){
    int i;
    for (i = 0;i < L->length;i++)
        if (L->data[i] == e)
            return i + 1;
    return 0;
}

​ 最好情况：查找到元素在表头，仅需比较一次，时间复杂度为 O (1)。

​ 最坏情况：查找到元素在表尾（或不存在），需要比较 n 次，时间复杂度为 O (n)。

​ 平均情况：假设 pip_i（pi=1/np_i=1/n）是查找到元素在第 i (1 <= i <L.length) 个位置上的概率，则长度为 n 的线性表中查找值为 e 的元素所需比较多平均次数为 ：

∑i=1npi×i=∑n=1n1n×i=1nn(n+1)2=n+12\sum_{i=1}^{n}p_i\times i=\sum_{n=1}^{n}\frac{1}{n}\times i=\frac{1}{n}\frac{n(n+1)}{2}=\frac{n+1}{2}

​ 因此，顺序表按值查找算法的平均时间复杂度为 O (n)。

# 2.3、线性表的链式表示：

​ 链式存储线性表时，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理位置上也相邻，它通过 “链” 建立起元素之间的逻辑关系，因此插入和删除操作不需要移动元素，而只需修改指针，但也会失去顺序表可随机存取的优点。

# 2.3.1、单链表的定义：

​ 线性表的链式存储又称单链表，它是指通过一组任意的存储单位来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息外，还需存放一个指向其后继的指针。单链表结点一般存放两个域，一个时 data 数据域，用于存放数据；另一个 next 为指针域，用于存放后继结点的地址。

​ 单链表中结点类型的描述如下：

1
2
3
4
typedef struct LNode {
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

​ 利用单链表可以解决顺序表需要大量连续存储单元的缺点，但单链表附加指针域，也存在浪费存储空间的缺点。由于单链表的元素离散地分布在存储空间中，所以单链表是非随机存取的存储结构，即不能直接找到表中某个特定的结点。查找某个特定的接待你时，需要从头开始遍历，依次查找。

​ 通常用头指针来表示一个单链表，如单链表 L ，头指针为 NULL 时表示一个空表。此外，为了操作上的方便，在单链表第一个结点之前附加一个结点，成为头结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点，如下图：

在这里插入图片描述

​ 头结点和头指针的区分：不管带不带头结点，头指针都始终指向链表的第一个结点，而头结点时带头节点的链表中的第一个结点，结点内通常不存储信息。

​ 引入头结点后，可以带来两个优点。

  1. 由于第一个数据结点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操作和在表的其他位置上的操作一致，无需进行特殊处理。
  2. 无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就得到了统一。

# 2.3.2、单链表上基本操作和实现：

# 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
37
38
39
40
41
#include "stdio.h"
#include "stdlib.h"
typedef struct Node {
    int data;
    struct Node *next;
}LNode,*LinkList;

LinkList List_HeadInsert(LinkList L);

int main(){
    LinkList L,p;

    L = List_HeadInsert(L);

    p = L->next;
    while(p){
        printf("%d,",p->data);
        p = p->next;
    }

    return 0;
}

//实现头插法建立链表的函数，输出结果是输入的逆序，输入1 2 3，输出结果是3，2，1
LinkList List_HeadInsert(LinkList L){
    LNode *s;
    int x;

    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;

    scanf("%d",&x);
    while (x!=9999) {
        s = (LinkList)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d",&x);
    }
    return L;
}

​ 采用头插法建立单链表时，读入数据的顺序与生成的链表的元素的顺序时相反的。每个结点插入的时间为 O (1)，设单链表长为 n ，则总时间复杂度为 O (n)。

# 2、采用尾插法建立单链表：

​ 头插法建立单链表的算法虽然简单，但生成的链表中节点的次序和输入数据的顺序不一致。若希望两者次序一致，则可采用尾插法。该方法将新结点插入到当前链表的表尾，为此必须增加一个尾指针 r ，使其始终指向当前链表的尾结点，如下图：

在这里插入图片描述

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
#include "stdio.h"
#include "stdlib.h"
typedef struct Node {
    int data;
    struct Node *next;
}LNode,*LinkList;

LinkList List_HeadInsert(LinkList L);
LinkList List_TailInsert(LinkList L);

int main(){
    LinkList L,p;

    //头插法建立链表的函数调用
//    L = List_HeadInsert(L);
    //尾插法建立链表的函数调用
    L = List_TailInsert(L);

    p = L->next;
    while(p){
        printf("%d,",p->data);
        p = p->next;
    }

    return 0;
}

LinkList List_HeadInsert(LinkList L){
    LNode *s;
    int x;

    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;

    scanf("%d",&x);
    while (x!=9999) {
        s = (LinkList)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d",&x);
    }
    return L;
}

//实现尾插法建立链表的函数
LinkList List_TailInsert(LinkList L){
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LinkList s,r = L;
    scanf("%d",&x);
    while (x != 9999){
        s = (LinkList) malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d",&x);
    }
    r->next = NULL;
    return L;
}

# 3、按序号查找结点：

​ 在单链表中从第一个结点出发，顺时针 next 域逐个往下搜索，直到找到第 i 个结点为止，否则返回最后一个结点指针域 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
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
69
70
71
72
73
74
75
76
#include "stdio.h"
#include "stdlib.h"
typedef struct Node {
    int data;
    struct Node *next;
}LNode,*LinkList;

LinkList List_HeadInsert(LinkList L);
LinkList List_TailInsert(LinkList L);
LinkList GetElem(LinkList L,int i);

int main(){
    LinkList L,p;

    //头插法建立链表的函数调用
//    L = List_HeadInsert(L);
    //尾插法建立链表的函数调用
    L = List_TailInsert(L);

    p = L->next;
    while(p){
        printf("%d,",p->data);
        p = p->next;
    }
    LinkList target =  GetElem(L,4);
    printf("\n%d",target->data);

    return 0;
}

LinkList List_HeadInsert(LinkList L){
    LNode *s;
    int x;

    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;

    scanf("%d",&x);
    while (x!=9999) {
        s = (LinkList)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d",&x);
    }
    return L;
}

LinkList List_TailInsert(LinkList L){
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LinkList s,r = L;
    scanf("%d",&x);
    while (x != 9999){
        s = (LinkList) malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d",&x);
    }
    r->next = NULL;
    return L;
}

//实现按序号查找结点算法的函数
LinkList GetElem(LinkList L,int i){
    if (i < 1)
        return NULL;
    int j = 1;
    LinkList p = L->next;
    while(p != NULL && j < i){
        p = p->next;
        j ++;
    }
    return p;
}

​ 按序号查找操作的时间复杂度为 O (n)。

# 4、按值查找表结点：

​ 从单链表的第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值 e ，则返回该结点的指针；若整个单链表中没有这样的结点，则返回 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
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include "stdio.h"
#include "stdlib.h"
typedef struct Node {
    int data;
    struct Node *next;
}LNode,*LinkList;

LinkList List_HeadInsert(LinkList L);
LinkList List_TailInsert(LinkList L);
LinkList GetElem(LinkList L,int i);
LinkList LocateElem(LinkList L,int e);

int main(){
    LinkList L,p;

    //头插法建立链表的函数调用
//    L = List_HeadInsert(L);
    //尾插法建立链表的函数调用
    L = List_TailInsert(L);

    p = L->next;
    while(p){
        printf("%d,",p->data);
        p = p->next;
    }
    LinkList target =  GetElem(L,4);
    printf("\n%d",target->data);

    target = LocateElem(L,5);
    printf("\n%d",target->data);

    return 0;
}

LinkList List_HeadInsert(LinkList L){
    LNode *s;
    int x;

    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;

    scanf("%d",&x);
    while (x!=9999) {
        s = (LinkList)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d",&x);
    }
    return L;
}

LinkList List_TailInsert(LinkList L){
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LinkList s,r = L;
    scanf("%d",&x);
    while (x != 9999){
        s = (LinkList) malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d",&x);
    }
    r->next = NULL;
    return L;
}

LinkList GetElem(LinkList L,int i){
    if (i < 1)
        return NULL;
    int j = 1;
    LinkList p = L->next;
    while(p != NULL && j < i){
        p = p->next;
        j ++;
    }
    return p;
}

//实现按值查找结点的函数如下
LinkList LocateElem(LinkList L,int e){
    LinkList p = L->next;
    while (p!=NULL && p->data != e)
        p = p->next;
    return p;
}

# 5、插入结点操作

# 通过查找到指定结点的前驱结点进行后插操作

​ 插入结点操作将值为 x 的新结点插入到单链表的第 i 个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第 i - 1 个结点，，再在其后插入新结点。

​ 算法先调用按序号查找算法 GetElem (L,i-1)，查找第 i - 1 个结点。假设返回的第 i - 1 个结点为 *p，然后令新结点 *s 的指针域指向 *p 的后继结点，再领结点 *p 的指针域指向新插入的结点 *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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include "stdio.h"
#include "stdlib.h"
typedef struct Node {
    int data;
    struct Node *next;
}LNode,*LinkList;

LinkList List_HeadInsert(LinkList L);
LinkList List_TailInsert(LinkList L);
LinkList GetElem(LinkList L,int i);
LinkList LocateElem(LinkList L,int e);
LinkList PreInsert(LinkList L,int i,int e);

int main(){
    LinkList L,p;

    //头插法建立链表的函数调用
//    L = List_HeadInsert(L);
    //尾插法建立链表的函数调用
    L = List_TailInsert(L);
    L = PreInsert(L,5,99);
    p = L->next;
    while(p){
        printf("%d,",p->data);
        p = p->next;
    }
    LinkList target =  GetElem(L,4);
    printf("\n%d",target->data);

    target = LocateElem(L,5);
    printf("\n%d",target->data);

    return 0;
}

LinkList List_HeadInsert(LinkList L){
    LNode *s;
    int x;

    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;

    scanf("%d",&x);
    while (x!=9999) {
        s = (LinkList)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d",&x);
    }
    return L;
}

LinkList List_TailInsert(LinkList L){
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LinkList s,r = L;
    scanf("%d",&x);
    while (x != 9999){
        s = (LinkList) malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d",&x);
    }
    r->next = NULL;
    return L;
}

LinkList GetElem(LinkList L,int i){
    if (i < 1)
        return NULL;
    int j = 1;
    LinkList p = L->next;
    while(p != NULL && j < i){
        p = p->next;
        j ++;
    }
    return p;
}

LinkList LocateElem(LinkList L,int e){
    LinkList p = L->next;
    while (p!=NULL && p->data != e)
        p = p->next;
    return p;
}

//实现通过第 i 个数据的前驱结点进行插入的函数算法
LinkList PreInsert(LinkList L,int i,int e){                       //实现在第i个结点之后进行插入
    LinkList p,s;
    s = (LinkList) malloc(sizeof(LNode));
    p = GetElem(L,i-1);                                         //获取第i个结点的前驱结点
    s->data = e;
    s->next = p->next;
    p->next = s;

    return L;
}

# 扩展：对指定结点进行前插操作

​ 假设，我们想将结点 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
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include "stdio.h"
#include "stdlib.h"
typedef struct Node {
    int data;
    struct Node *next;
}LNode,*LinkList;

LinkList List_HeadInsert(LinkList L);
LinkList List_TailInsert(LinkList L);
LinkList GetElem(LinkList L,int i);
LinkList LocateElem(LinkList L,int e);
LinkList PreInsert(LinkList L,int i,int e);
LinkList backInsert(LinkList L,int i,int e);

int main(){
    LinkList L,p;

    //头插法建立链表的函数调用
//    L = List_HeadInsert(L);
    //尾插法建立链表的函数调用
    L = List_TailInsert(L);
    L = backInsert(L,5,99);
    p = L->next;
    while(p){
        printf("%d,",p->data);
        p = p->next;
    }
    LinkList target =  GetElem(L,4);
    printf("\n%d",target->data);

    target = LocateElem(L,5);
    printf("\n%d",target->data);

    return 0;
}

LinkList List_HeadInsert(LinkList L){
    LNode *s;
    int x;

    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;

    scanf("%d",&x);
    while (x!=9999) {
        s = (LinkList)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d",&x);
    }
    return L;
}

LinkList List_TailInsert(LinkList L){
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LinkList s,r = L;
    scanf("%d",&x);
    while (x != 9999){
        s = (LinkList) malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d",&x);
    }
    r->next = NULL;
    return L;
}

LinkList GetElem(LinkList L,int i){
    if (i < 1)
        return NULL;
    int j = 1;
    LinkList p = L->next;
    while(p != NULL && j < i){
        p = p->next;
        j ++;
    }
    return p;
}

LinkList LocateElem(LinkList L,int e){
    LinkList p = L->next;
    while (p!=NULL && p->data != e)
        p = p->next;
    return p;
}

LinkList PreInsert(LinkList L,int i,int e){                       //实现在第i个结点之后进行插入
    LinkList p,s;
    s = (LinkList) malloc(sizeof(LNode));
    p = GetElem(L,i-1);                                         //获取第i个结点的前驱结点
    s->data = e;
    s->next = p->next;
    p->next = s;

    return L;
}

//实现后插结点的函数主题如下
LinkList backInsert(LinkList L,int i,int e){
    LinkList p,s;
    int temp;
    s = (LinkList) malloc(sizeof(LNode));
    p = GetElem(L,i);                                         //获取第i个结点的前驱结点
    s->data = e;
    s->next = p->next;
    p->next = s;
    temp = p->data;
    p->data = s->data;
    s->data = temp;

    return L;
}

# 6、删除结点操作：

​ 删除结点操作是将单链表的第 i 个结点删除。先检查删除位置的合法性，后查找表中第 i - 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
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include "stdio.h"
#include "stdlib.h"
typedef struct Node {
    int data;
    struct Node *next;
}LNode,*LinkList;

LinkList List_HeadInsert(LinkList L);
LinkList List_TailInsert(LinkList L);
LinkList GetElem(LinkList L,int i);
LinkList LocateElem(LinkList L,int e);
LinkList PreInsert(LinkList L,int i,int e);
LinkList backInsert(LinkList L,int i,int e);
LinkList DeleteNode(LinkList L,int i);

int main(){
    LinkList L,p;

    L = List_TailInsert(L);
    p = L->next;

    L = DeleteNode(L,4);

    while(p){
        printf("%d,",p->data);
        p = p->next;
    }

    return 0;
}

LinkList List_HeadInsert(LinkList L){
    LNode *s;
    int x;

    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;

    scanf("%d",&x);
    while (x!=9999) {
        s = (LinkList)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d",&x);
    }
    return L;
}

LinkList List_TailInsert(LinkList L){
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LinkList s,r = L;
    scanf("%d",&x);
    while (x != 9999){
        s = (LinkList) malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d",&x);
    }
    r->next = NULL;
    return L;
}

LinkList GetElem(LinkList L,int i){
    if (i < 1)
        return NULL;
    int j = 1;
    LinkList p = L->next;
    while(p != NULL && j < i){
        p = p->next;
        j ++;
    }
    return p;
}

LinkList LocateElem(LinkList L,int e){
    LinkList p = L->next;
    while (p!=NULL && p->data != e)
        p = p->next;
    return p;
}

LinkList PreInsert(LinkList L,int i,int e){                       //实现在第i个结点之后进行插入
    LinkList p,s;
    s = (LinkList) malloc(sizeof(LNode));
    p = GetElem(L,i-1);                                         //获取第i个结点的前驱结点
    s->data = e;
    s->next = p->next;
    p->next = s;

    return L;
}

LinkList backInsert(LinkList L,int i,int e){
    LinkList p,s;
    int temp;
    s = (LinkList) malloc(sizeof(LNode));
    p = GetElem(L,i);                                         //获取第i个结点的前驱结点
    s->data = e;
    s->next = p->next;
    p->next = s;
    temp = p->data;
    p->data = s->data;
    s->data = temp;

    return L;
}

//实现删除结点操作的函数的主体如下
LinkList DeleteNode(LinkList L,int i){
    LinkList p,q;
    int e;
    p = GetElem(L,i-1);
    q = p->next;
    p->next = q->next;
    printf("被删除结点的元素的数据为：%d\n",q->data);
    free(q);

    return L;
}

​ 和插入算法一样，该算法的主要时间也是耗费在查找操作上，时间复杂度为 O (n)。

# 7、求表长操作：

​ 求表长操作要求计算单链表数据结点，也就是不含头结点的结点的总个数，需要从第一个结点开始遍历，直到访问完所有的结点，因为比较简单，具体实现就不进行赘述了，不过需要注意：有的链表存在头结点，有的不存在，在计算的时候要做好相关的区分操作。

# 8、销毁整个表（我自己写的）

​ 不多解释，直接上源码：

1
2
3
4
5
6
7
8
9
10
void AllFree(LinkList L){
    LinkList p = L->next,r;
    while(p){
        r = p;
        p = p->next;
        free(r);
    }
    free(p);
    free(L);
}

# 2.3.3、双链表：

​ 单链表结点中只有一个指向其后继的指针，使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点（插入、删除操作时），只能从头开始遍历，访问后继结点的时间复杂度为 O (1)，访问前驱结点的时间复杂度为 O (n)。

​ 为了克服单链表的上述缺点，引入了双链表，双链表结点中有两个指针 prior 和 next ，分别指向其前驱和后继结点，如下图：

在这里插入图片描述

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

1
2
3
4
typedef struct DNode{
    ElemType data;
    struct DNode *prior,*next;
} Dnode,*DLinkList;

​ 双链表在单链表的结点中增加了一个指向前驱的 prior 指针，因此双链表中的按值查找和按位查找的操作与单链表相同。但双链表在插入和删除操作的实现上，与单链表有着较大的不同。这是因为 “链” 变化时也需要对 prior 指针做出修改，其关键是保证在修改的过程中不断链。此外，双链表可以很方便地找到其前驱结点，因此，插入、删除操作的时间复杂度仅为 O (1)。

# 1、双链表的插入操作：

​ 在双链表中 p 所指的结点之后插入结点 *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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include "stdio.h"
#include "stdlib.h"

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

DLinkList create(DLinkList DL);
DLinkList GetElem(DLinkList DL,int i);
DLinkList Insert(DLinkList DL,int i,int e);
void AllFree(DLinkList L);

int main(){
    DLinkList DL,p;

    DL = create(DL);

    p = DL->next;
    while(p){
        printf("%d,",p->data);
        p = p->next;
    }
    puts("");
    DL = Insert(DL,3,10);

    p = DL->next;
    while(p){
        printf("%d,",p->data);
        p = p->next;
    }

    AllFree(DL);

    return 0;
}

DLinkList create(DLinkList DL){
    int x;
    DL = (DLinkList)malloc(sizeof(DNode));
    DLinkList s,r = DL;
    scanf("%d",&x);
    while (x != 9999){
        s = (DLinkList) malloc(sizeof(DNode));
        s->data = x;
        r->next = s;
        r->next->prior = r;
        r = s;
        scanf("%d",&x);
    }
    r->next = NULL;
    return DL;
}

DLinkList GetElem(DLinkList DL,int i){
    if (i < 1)
        return NULL;
    int j = 1;
    DLinkList p = DL->next;
    while(p != NULL && j < i){
        p = p->next;
        j ++;
    }
    return p;
}

//实现插入操作的函数主体如下
DLinkList Insert(DLinkList DL,int i,int e){
    DLinkList s,p;
    s = (DLinkList) malloc(sizeof(DNode));
    p = GetElem(DL,i-1);
    s->data = e;
    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;

    return DL;
}

void AllFree(DLinkList DL){
    DLinkList p = DL->next,r;
    while(p){
        r = p;
        p = p->next;
        free(r);
    }
    free(p);
    free(DL);
}

# 2、双链表的删除操作：

​ 删除双链表的结点 *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
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include "stdio.h"
#include "stdlib.h"

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

DLinkList create(DLinkList DL);
DLinkList GetElem(DLinkList DL,int i);
DLinkList Insert(DLinkList DL,int i,int e);
DLinkList Delete(DLinkList DL,int i);
void AllFree(DLinkList L);

int main(){
    DLinkList DL,p;
    DL = create(DL);

    p = DL->next;
    while(p){
        printf("%d,",p->data);
        p = p->next;
    }
    puts("");
    DL = Insert(DL,3,10);

    p = DL->next;
    while(p){
        printf("%d,",p->data);
        p = p->next;
    }
    puts("");
    DL = Delete(DL,3);

    p = DL->next;
    while(p){
        printf("%d,",p->data);
        p = p->next;
    }

    AllFree(DL);

    return 0;
}

DLinkList create(DLinkList DL){
    int x;
    DL = (DLinkList)malloc(sizeof(DNode));
    DLinkList s,r = DL;
    scanf("%d",&x);
    while (x != 9999){
        s = (DLinkList) malloc(sizeof(DNode));
        s->data = x;
        r->next = s;
        r->next->prior = r;
        r = s;
        scanf("%d",&x);
    }
    r->next = NULL;
    return DL;
}

DLinkList GetElem(DLinkList DL,int i){
    if (i < 1)
        return NULL;
    int j = 1;
    DLinkList p = DL->next;
    while(p != NULL && j < i){
        p = p->next;
        j ++;
    }
    return p;
}

DLinkList Insert(DLinkList DL,int i,int e){
    DLinkList s,p;
    s = (DLinkList) malloc(sizeof(DNode));
    p = GetElem(DL,i-1);
    s->data = e;
    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;

    return DL;
}

//实现删除结点的函数的主体
DLinkList Delete(DLinkList DL,int i){
    DLinkList p,q;
    q = GetElem(DL,i);
    p = q->prior;

    p->next = q->next;
    q->next->prior = p;
    free(q);

    return DL;
}

void AllFree(DLinkList DL){
    DLinkList p = DL->next,r;
    while(p){
        r = p;
        p = p->next;
        free(r);
    }
    free(p);
    free(DL);
}

# 2.3.4、循环链表：

# 1、循环单链表：

​ 循环单链表和单链表的区别在于，表中最后一个结点的指针不是 NULL ，而改为指向头结点，从而整个链表形成一个环，如下图：

在这里插入图片描述

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

​ 循环单链表的插入、删除算法与单链表的几乎一样，所不同的是若操作在表尾进行，则执行的操作不同，以让单链表继续保持循环的特性。当然，正因为循环单链表是一个环，因此在任何一个位址上的插入和删除操作都是等价的，无需判断是否是表尾。

​ 在单链表中只能从表头结点开始往后顺序遍历整个链表，而循环单链表可以从表中的任意一个结点开始遍历整个链表。有时对循环链表不设头指针仅设尾指针，以使得操作效率更高。其原因是，若设的是头指针，对在表尾插入元素需要 O (n) 的时间复杂度，而若设的是尾指针 r ，r->next 即为头指针，对在表头或表尾插入元素都只需要 O (1) 的时间复杂度。

# 2、循环双链表：

​ 由循环单链表的定义不难退出寻你换双链表。不同的是在循环双链表中，头结点的 prior 指针还要指向表尾结点，如下图：

在这里插入图片描述

​ 在循环双链表 L 中，某节点 *p 为尾结点时，p->next == L ；当循环双链表为空表时，其头结点的 prior 域和 next 域都等于 L 。

# 2.3.5、静态链表：

​ 静态链表借助数组来描述线性表的链式存储结构，结点也有数据域 data 和 指针域 next ，与之前的链表中的指针不同的是，这里的指针是结点的相对地址（数组下标），又称游标。和顺序表一样，静态链表也要预先分配一段连续的内存空间。

​ 静态链表和单链表的对应关系如下。

在这里插入图片描述

​ 静态链表结构类型的描述如下：

1
2
3
4
5
#define MaxSize 50
typedef struct {
    ElemType data;
    int next;
}SLinkList[MaxSize];

​ 静态链表以 next == 1 作为其结束的标志。静态链表的插入、删除操作与动态链表的相同，只需要修改指针，而不需要移动元素，静态链表没有单链表使用起来方便，但在一些不支持指针的高级语言中，这是一种非常巧妙的设计方法。

更新于

请我喝[茶]~(￣▽￣)~*

g01den 微信支付

微信支付

g01den 支付宝

支付宝

g01den 贝宝

贝宝