title: 数据结构与算法（二）线性表之顺序表、单链表date: 2021-06-22 22:20:56.145

updated: 2021-06-25 20:42:03.453
url: /?p=255
categories: 数据结构与算法
tags: 数据结构与算法

线性表

什么是线性表

线性表，数据结构中最简单的一种存储结构，基本上用于存储逻辑关系为”一对一”的数据。

线性表，基于数据在实际物理空间中的存储状态，又可细分为顺序表（顺序存储结构）和链表（链式存储结构）。

线性表，全名为线性存储结构。就好似把数据拿“一根线”串起来，所以是线性的。

注意，线性存储的每一个元素必须都是同一种类型，比如整型、字符串、自定义类型等。

前驱和后继

数据结构中，一组数据中的每个个体被称为数据元素（简称元素）。

另外，对于具有“一对一”逻辑关系的数据，我们一直在用“某一元素的左侧（前边）或右侧（后边）”这样不专业的词，其实线性表中有更准确的术语：

  1. 某一元素的左侧相邻元素称为直接前驱，位于此元素左侧的所有元素都统称为前驱元素；
  2. 某一元素的右侧相邻元素称为直接后继，位于此元素右侧的所有元素都统称为后继元素；

顺序表（顺序存储结构）

顺序表，即顺序存储结构，是线性表的一种。

顺序表的内存空间是连续的，并且顺序表存储数据时，需要提前申请一整块足够空间的物理内存空间，然后将数据依次存储起来，存储时做到数据元素之间不留一丝缝隙。

顺序表的初始化

使用顺序表存储数据之前，除了要申请足够大小的物理空间之外，为了方便后期使用表中的数据，顺序表还需要实时记录以下 2 项数据：

  1. 顺序表申请的存储容量；
  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
35
36
37
38
39
40
41
42
43
44
45
#include<stdio.h>
#include<stdlib.h>

typedef struct Table{
    int * head;//声明了一个名为head的长度不确定的数组，也叫“动态数组”
    int length;//记录当前顺序表的长度
    int size;//记录顺序表分配的存储容量
} table;


table initTable(int);
void displayTable(table);


int main(){
    table t = initTable(5);
    for (size_t i = 0; i < 5; i++)
    {
        t.head[i] = i;
        t.length++;
    }
    printf("输出顺序表元素\n");
    displayTable(t);
    return 1;
}

table initTable(int size){
    table t;
    t.head = (int*)malloc(size*sizeof(int));
    if(!t.head){  //注意这里是！
        printf("初始化失败");
        exit(0);
    }
    t.length = 0;
    t.size = size;
    return t;
}

//输出顺序表中元素的函数
void displayTable(table t){
    for (int i=0;i<t.length;i++) {
        printf("%d ",t.head[i]);
    }
    printf("\n");
}

运行结果：

1
2
输出顺序表元素
0 1 2 3 4

顺序表插入元素

向顺序表插入元素，有3种情况：

  1. 插入顺序表的表头。
  2. 在表的中间插入。
  3. 尾部插入。

虽然数据元素插入顺序表中的位置有所不同，但是都使用的是同一种方式去解决，即：通过遍历，找到数据元素要插入的位置，然后做如下两步工作：

  1. 将要插入位置元素以及后续的元素整体向后移动一个位置；
  2. 将元素放到腾出来的位置上；

以上代码增加table addTable(table t, int elem, int index);函数：

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
#include <stdio.h>
#include <stdlib.h>

typedef struct Table
{
    int *head;  //声明了一个名为head的长度不确定的数组，也叫“动态数组”
    int length; //记录当前顺序表的长度
    int size;   //记录顺序表分配的存储容量
} table;

table initTable(int);
void displayTable(table);
table addTable(table t, int elem, int index);

int main()
{
    table t = initTable(5);
    for (size_t i = 0; i < 5; i++)
    {
        t.head[i] = i;
        t.length++;
    }
    printf("输出顺序表元素\n");
    displayTable(t);


    printf("addTable(t,100,0);\n");
    table t1 = addTable(t,100,0);
    printf("输出顺序表元素\n");
    displayTable(t1);

    printf("addTable(t1,101,2);\n");
    table t2 = addTable(t1,101,2);
    printf("输出顺序表元素\n");
    displayTable(t2);

    printf("addTable(t2,102,t2.length);\n");
    table t3 = addTable(t2,102,t2.length);
    printf("输出顺序表元素\n");
    displayTable(t3);
    return 1;
}

table initTable(int size)
{
    table t;
    t.head = (int *)malloc(size * sizeof(int));
    if (!t.head)
    {
        printf("初始化失败");
        exit(0);
    }
    t.length = 0;
    t.size = size;
    return t;
}

//输出顺序表中元素的函数
void displayTable(table t)
{
    for (int i = 0; i < t.length; i++)
    {
        printf("%d ", t.head[i]);
    }
    printf("【%d,%d】",t.length,t.size);
    printf("\n");
}

// 插入函数，t 顺序表 ；elem 元素 ； index 索引 以 0 开头。
table addTable(table t, int elem, int index)
{
    //判断插入本身是否存在问题（如果插入元素位置比整张表的长度+1还大（如果相等，是尾随的情况），或者插入的位置本身不存在，程序作为提示并自动退出）
    if (index > t.length + 1 || index < 0)
    {
        printf("插入位置有问题\n");
        return t;
    }

    //做插入操作时，首先需要看顺序表是否有多余的存储空间提供给插入的元素，如果没有，需要申请
    if(t.length == t.size){
        t.head = (int *)realloc(t.head,(t.size+1)*sizeof(int));
        if (!t.head)
        {
            printf("存储内存分配失败\n");
            return t;
        }
        t.size+=1;
    }

    //插入操作，需要将从插入位置开始的后续元素，逐个后移
    for (int i = t.length-1; i >= index; i--)
    {
        t.head[i+1] = t.head[i];
    }

    //后移完成，插入元素
    t.head[index] = elem;
    t.length++;
    return t;
    
}

运行结果：

1
2
3
4
5
6
7
8
9
10
11
输出顺序表元素
0 1 2 3 4 【5,5】
addTable(t,100,0);
输出顺序表元素
100 0 1 2 3 4 【6,6】
addTable(t1,101,2);
输出顺序表元素
100 0 101 1 2 3 4 【7,7】
addTable(t2,102,t2.length);
输出顺序表元素
100 0 101 1 2 3 4 102 【8,8】

顺序表删除元素

删除元素很简单，找到目标元素，把它后面的后继元素前移即可。后面的元素数据会覆盖目标元素数据，起到删除的作用。

在初始化代码的基础上增加table deleteTable(table t, int index);:

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
#include <stdio.h>
#include <stdlib.h>

typedef struct Table
{
    int *head;  //声明了一个名为head的长度不确定的数组，也叫“动态数组”
    int length; //记录当前顺序表的长度
    int size;   //记录顺序表分配的存储容量
} table;

table initTable(int);
void displayTable(table);
table deleteTable(table, int);

int main()
{
    table t = initTable(5);
    for (size_t i = 0; i < 5; i++)
    {
        t.head[i] = i;
        t.length++;
    }
    printf("输出顺序表元素\n");
    displayTable(t);

    printf("执行：table t1 = deleteTable(t,t.length);\n");
    table t1 = deleteTable(t,t.length);
    printf("输出顺序表元素\n");
    displayTable(t1);
    
    printf("执行：table t2 = deleteTable(t1,2);\n");
    table t2 = deleteTable(t1,2);
    printf("输出顺序表元素\n");
    displayTable(t2);

    printf("执行：table t3 = deleteTable(t2,0);\n");
    table t3 = deleteTable(t2,0);
    printf("输出顺序表元素\n");
    displayTable(t3);

    return 1;
}

table initTable(int size)
{
    table t;
    t.head = (int *)malloc(size * sizeof(int));
    if (!t.head)
    {
        printf("初始化失败");
        exit(0);
    }
    t.length = 0;
    t.size = size;
    return t;
}

//输出顺序表中元素的函数
void displayTable(table t)
{
    for (int i = 0; i < t.length; i++)
    {
        printf("%d ", t.head[i]);
    }
    printf("【%d,%d】", t.length, t.size);
    printf("\n");
}

// 删除顺序表的元素； t 顺序表 ； index 索引；
table deleteTable(table t, int index)
{
    if (index > t.length || index < 0)
    {
        printf("index有误。");
        return t;
    }
    for (size_t i = index + 1; i < t.length; i++)
    {
        t.head[i - 1] = t.head[i];
    }

    t.length--;

    return t;
}
1
2
3
4
5
6
7
8
9
10
11
输出顺序表元素
0 1 2 3 4 【5,5】
执行：table t1 = deleteTable(t,t.length);
输出顺序表元素
0 1 2 3 【4,5】
执行：table t2 = deleteTable(t1,2);
输出顺序表元素
0 1 3 【3,5】
执行：table t3 = deleteTable(t2,0);
输出顺序表元素
1 3 【2,5】

顺序表查找元素

顺序表中查找目标元素，可以使用多种查找算法实现，比如说二分查找算法、插值查找算法等。

这里，我们选择顺序查找算法，具体实现代码为：

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
#include <stdio.h>
#include <stdlib.h>

typedef struct Table
{
    int *head;  //声明了一个名为head的长度不确定的数组，也叫“动态数组”
    int length; //记录当前顺序表的长度
    int size;   //记录顺序表分配的存储容量
} table;

table initTable(int);
void displayTable(table);
int selectTable(table t, int elem);

int main()
{
    table t = initTable(5);
    for (size_t i = 0; i < 5; i++)
    {
        t.head[i] = i;
        t.length++;
    }
    printf("输出顺序表元素\n");
    displayTable(t);

    printf("找到元素0索引：%d\n",selectTable(t,0));
    printf("找到元素1索引：%d\n",selectTable(t,1));
    printf("找到元素2索引：%d\n",selectTable(t,2));
    printf("找到元素3索引：%d\n",selectTable(t,3));
    printf("找到元素4索引：%d\n",selectTable(t,4));

    return 1;
}

table initTable(int size)
{
    table t;
    t.head = (int *)malloc(size * sizeof(int));
    if (!t.head)
    {
        printf("初始化失败");
        exit(0);
    }
    t.length = 0;
    t.size = size;
    return t;
}

//输出顺序表中元素的函数
void displayTable(table t)
{
    for (int i = 0; i < t.length; i++)
    {
        printf("%d ", t.head[i]);
    }
    printf("【%d,%d】", t.length, t.size);
    printf("\n");
}

//查找函数，其中，elem 表示要查找的数据元素的值
int selectTable(table t, int elem)
{
    for (size_t i = 0; i < t.length; i++)
    {
        if (t.head[i] == elem)
        {
            return i;
        }
    }
    // 返回 -1 表示未找到。
    return -1;
}
1
2
3
4
5
6
7
输出顺序表元素
0 1 2 3 4 【5,5】
找到元素0索引：0
找到元素1索引：1
找到元素2索引：2
找到元素3索引：3
找到元素4索引：4

顺序表更改元素

顺序表更改元素的实现过程是：

  • 找到目标元素的索引index；
  • 直接修改该元素的值；
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
#include <stdio.h>
#include <stdlib.h>

typedef struct Table
{
    int *head;  //声明了一个名为head的长度不确定的数组，也叫“动态数组”
    int length; //记录当前顺序表的长度
    int size;   //记录顺序表分配的存储容量
} table;

table initTable(int);
void displayTable(table);
int selectTable(table t, int elem);
table updateTable(table t , int elem , int newElem);

int main()
{
    table t = initTable(5);
    for (size_t i = 0; i < 5; i++)
    {
        t.head[i] = i;
        t.length++;
    }
    printf("输出顺序表元素\n");
    displayTable(t);

    table t1 = updateTable(t,3,100);
    displayTable(t1); 

    return 1;
}

table initTable(int size)
{
    table t;
    t.head = (int *)malloc(size * sizeof(int));
    if (!t.head)
    {
        printf("初始化失败");
        exit(0);
    }
    t.length = 0;
    t.size = size;
    return t;
}

//输出顺序表中元素的函数
void displayTable(table t)
{
    for (int i = 0; i < t.length; i++)
    {
        printf("%d ", t.head[i]);
    }
    printf("【%d,%d】", t.length, t.size);
    printf("\n");
}

//查找函数，其中，elem 表示要查找的数据元素的值
int selectTable(table t, int elem)
{
    for (size_t i = 0; i < t.length; i++)
    {
        if (t.head[i] == elem)
        {
            return i;
        }
    }
    // 返回 -1 表示未找到。
    return -1;
}

// t 顺序表 ； elem 旧元素 ； newElem 新元素；
table updateTable(table t , int elem , int newElem){
    int index = selectTable(t,elem);
    t.head[index] = newElem;
    return t;
}
1
2
3
输出顺序表元素
0 1 2 3 4 【5,5】
0 1 2 100 4 【5,5】

单链表（链式存储结构）

与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的，即内存空间是不连续的。

数据元素随机存储，并通过指针表示数据之间逻辑关系的存储结构就是链式存储结构。

链表的节点

链表中每个数据的存储都由以下两部分组成：

  1. 数据元素本身，其所在的区域称为数据域；
  2. 指向直接后继元素的指针，所在的区域称为指针域；

链表实际存储的是一个一个的节点，真正的数据元素包含在这些节点中，如下图所示：

节点的结构体表示：

1
2
3
4
typedef struct Link{
    char cdata; //数据域
    struct Link * next; // 指向下一个节点的指针变量
} link;

头节点、头指针和首元节点

一个完整的链表需要由以下几部分构成：

  1. 头指针：一个普通的指针，它的特点是永远指向链表第一个节点的位置。很明显，头指针用于指明链表的位置，便于后期找到链表并使用表中的数据；

  2. 节点：链表中的节点又细分为头节点、首元节点和其他节点：

    • 头节点：其实就是一个不存任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的，它的作用只是为了方便解决某些实际问题；
    • 首元节点：由于头节点（也就是空节点）的缘故，链表中称第一个存有数据的节点为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓，没有实际意义；
    • 其他节点：链表中其他的节点；

因此，一个存储 {1,2,3} 的完整链表结构如图所示：

链表中有头节点时，头指针指向头节点；反之，若链表中没有头节点，则头指针指向首元节点。

链表初始化

创建一个链表需要做如下工作：

  1. 声明一个头指针（如果有必要，可以声明一个头节点）；
  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
#include <stdio.h>
#include <stdlib.h>

typedef struct Link
{
    int data;          //数据域
    struct Link *next; // 指向下一个节点的指针变量
} link;

link *initLink();

int main()
{
    link *l = initLink();
    printf("初始化%d,%p", l->data, l->next);
    return 1;
}


link *initLink()
{
    link *p = NULL; //头指针
    link *node = (link *)malloc(sizeof(link)); //首元节点

    //初始化首元节点
    node->data = 0; 
    node->next = NULL; 

    p = node; //使得头指针指向首元节点
    
    return 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
#include <stdio.h>
#include <stdlib.h>

typedef struct Link
{
    int data;          //数据域
    struct Link *next; // 指向下一个节点的指针变量
} link;

link *initLink();

int main()
{
    link *l = initLink();
    printf("初始化%d,%p", l->data, l->next);
    return 1;
}

link *initLink()
{
    link * node = (link *)malloc(sizeof(link)); //头结点
    link * p = node;
    return 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
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>
#include <stdlib.h>

typedef struct Link
{
    int data;          //数据域
    struct Link *next; // 指向下一个节点的指针变量
} link;

link *initLink();
void initData(link *);
void displayLink(link *);

int main()
{
    link *myLink = initLink();
    initData(myLink);
    displayLink(myLink);
    return 1;
}

link *initLink()
{
    printf("创建链表\n");
    link *p = NULL;                            //头指针
    link *node = (link *)malloc(sizeof(link)); //首元节点

    //初始化首元节点
    node->data = 0;
    node->next = NULL;

    p = node; //使得头指针指向首元节点

    return p; //返回头指针
}

void initData(link *l)
{
    printf("初始化数据\n");
    link *temp = l;
    for (size_t i = 0; i < 50; i+=2)
    {
        // 创建新节点
        link *node = (link *)malloc(sizeof(link));
        node->data = i;
        node->next = NULL;
        // 使得头指针指向下一个节点。
        temp->next = node;

        temp = temp->next;
    }
}

void displayLink(link *l)
{
    printf("输出链表\n");
    link *temp = l;
    while (temp->next)
    {
        temp = temp->next;
        printf("%d ", temp->data);
    }
    printf("\n");
}

链表插入元素

插入元素分为3种情况：

  1. 插入到链表的头部（头节点之后），作为首元节点；
  2. 插入到链表中间的某个位置；
  3. 插入到链表的最末端，作为链表中最后一个数据元素；

虽然新元素的插入位置不固定，但是链表插入元素的思想是固定的，只需做以下两步操作，即可将新元素插入到指定的位置：

  1. 将新结点的 next 指针指向插入位置后的结点；
  2. 将插入位置前结点的 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
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
#include <stdio.h>
#include <stdlib.h>

typedef struct Link
{
    int data;          //数据域
    struct Link *next; // 指向下一个节点的指针变量
} link;

link *initLink();
void initData(link *);
void displayLink(link *);
void insertLink(link *l, int elem, int index);

int main()
{
    link *myLink = initLink();
    initData(myLink);
    displayLink(myLink);
    insertLink(myLink,1000,4);
    insertLink(myLink,1000,10);
    displayLink(myLink);
    return 1;
}

link *initLink()
{
    printf("创建链表\n");
    link *p = NULL;                            //头指针
    link *node = (link *)malloc(sizeof(link)); //首元节点

    //初始化首元节点
    node->data = 0;
    node->next = NULL;

    p = node; //使得头指针指向首元节点

    return p; //返回头指针
}

void initData(link *l)
{
    printf("初始化数据\n");
    link *temp = l;
    for (size_t i = 0; i < 50; i += 2)
    {
        // 创建新节点
        link *node = (link *)malloc(sizeof(link));
        node->data = i;
        node->next = NULL;
        // 使得头指针指向下一个节点。
        temp->next = node;

        temp = temp->next;
    }
}

void displayLink(link *l)
{
    printf("输出链表\n");
    link *temp = l;
    while (temp->next)
    {
        temp = temp->next;
        printf("%d ", temp->data);
    }
    printf("\n");
}

void insertLink(link *l, int elem, int index)
{
    link *temp = l;
    for (size_t i = 0; i < index; i++)
    {
        temp = temp->next;
        if (temp == NULL)
        {
            printf("插入位置无效！");
        }
    }

    // 创建新的节点
    link *newNode = (link *)malloc(sizeof(link));
    newNode->data = elem;
    newNode->next = temp->next;
    //
    temp->next = newNode;
}
1
2
3
4
5
6
创建链表
初始化数据
输出链表
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 
输出链表
0 2 4 6 1000 8 10 12 14 16 1000 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48

链表删除元素

从链表中删除数据元素需要进行以下 2 步操作:

  1. 将结点从链表中摘下来;
  2. 手动释放掉结点，回收被结点占用的存储空间;

其中，从链表上摘除某节点的实现非常简单，只需找到该节点的直接前驱节点 temp，执行一行程序：

1
temp->next=temp->next->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
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 Link
{
    int data;          //数据域
    struct Link *next; // 指向下一个节点的指针变量
} link;

link *initLink();
void initData(link *);
void displayLink(link *);
void insertLink(link *l, int elem, int index);
void delElem(link *l, int index);


int main()
{
    link *myLink = initLink();
    initData(myLink);
    displayLink(myLink);
    insertLink(myLink, 1000, 4);
    insertLink(myLink, 1000, 10);
    displayLink(myLink);
    delElem(myLink, 5);
    displayLink(myLink);
    return 1;
}

link *initLink()
{
    printf("创建链表\n");
    link *p = NULL;                            //头指针
    link *node = (link *)malloc(sizeof(link)); //首元节点

    //初始化首元节点
    node->data = 0;
    node->next = NULL;

    p = node; //使得头指针指向首元节点

    return p; //返回头指针
}

void initData(link *l)
{
    printf("初始化数据\n");
    link *temp = l;
    for (size_t i = 0; i < 50; i += 2)
    {
        // 创建新节点
        link *node = (link *)malloc(sizeof(link));
        node->data = i;
        node->next = NULL;
        // 使得头指针指向下一个节点。
        temp->next = node;

        temp = temp->next;
    }
}

void displayLink(link *l)
{
    printf("输出链表\n");
    link *temp = l;
    while (temp->next)
    {
        temp = temp->next;
        printf("%d ", temp->data);
    }
    printf("\n");
}

void insertLink(link *l, int elem, int index)
{
    link *temp = l;
    for (size_t i = 0; i < index; i++)
    {
        temp = temp->next;
        if (temp == NULL)
        {
            printf("插入位置无效！");
        }
    }

    // 创建新的节点
    link *newNode = (link *)malloc(sizeof(link));
    newNode->data = elem;
    newNode->next = temp->next;
    //
    temp->next = newNode;
}

void delElem(link *l, int index)
{
    printf("执行 delElem(link *l, int index):void 函数，参数为 %d,%d\n", l, index);
    link *temp = l;
    for (size_t i = 0; i < index; i++)
    {
        temp = temp->next;
        if (temp == NULL)
        {
            printf("无节点");
        }
    }

    link *indexNode = temp->next;  //单独设置一个指针指向被删除结点，以防丢失
    temp->next = temp->next->next; //删除某个结点的方法就是更改前一个结点的指针域
    free(indexNode);               //手动释放该结点，防止内存泄漏
}
1
2
3
4
5
6
7
8
9
创建链表
初始化数据
输出链表
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 
输出链表
0 2 4 6 1000 8 10 12 14 16 1000 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 
执行 delElem(link *l, int index):void 函数，参数为 11281456,5
输出链表
0 2 4 6 1000 10 12 14 16 1000 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48

链表查找元素

在链表中查找指定数据元素，最常用的方法是：从表头依次遍历表中节点，用被查找元素与各节点数据域中存储的数据元素进行比对，直至比对成功或遍历至链表最末端的 NULL（比对失败的标志）。

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

int selectIndex(link *l, int elem)
{
    link *temp = l;
    int index = 0;
    while (temp != NULL)
    {
        temp = temp->next;
        if (temp->data == elem)
        {
            return index;
        }
        index++;
    }

    return -1;
}
1
index: 4

链表更新元素

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

void updateElem(link *l, int newElem, int index)
{
    printf("执行 updateElem(link *l, int newElem, int index):void,参数为 %p,%d,%d", l, newElem, index);
    link *temp = l;
    for (size_t i = 0; i <= index; i++)
    {
        temp = temp->next;
    }

    temp->data = newElem;
}
1
2
index: 4执行 updateElem(link *l, int newElem, int index):void,参数为 0000000000192430,999,4输出链表
0 2 4 6 999 10 12 14 16 1000 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48

以上完整代码

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <stdio.h>
#include <stdlib.h>

typedef struct Link
{
    int data;          //数据域
    struct Link *next; // 指向下一个节点的指针变量
} link;

link *initLink();
void initData(link *);
void displayLink(link *);
void insertLink(link *l, int elem, int index);
void delElem(link *l, int index);
int selectIndex(link *l, int elem);
void updateElem(link *l, int newElem, int index);

int main()
{
    link *myLink = initLink();
    initData(myLink);
    displayLink(myLink);
    insertLink(myLink, 1000, 4);
    insertLink(myLink, 1000, 10);
    displayLink(myLink);
    delElem(myLink, 5);
    displayLink(myLink);

    printf("index: %d", selectIndex(myLink, 1000));

    updateElem(myLink, 999, 4);
    displayLink(myLink);
    return 1;
}

link *initLink()
{
    printf("创建链表\n");
    link *p = NULL;                            //头指针
    link *node = (link *)malloc(sizeof(link)); //首元节点

    //初始化首元节点
    node->data = 0;
    node->next = NULL;

    p = node; //使得头指针指向首元节点

    return p; //返回头指针
}

void initData(link *l)
{
    printf("初始化数据\n");
    link *temp = l;
    for (size_t i = 0; i < 50; i += 2)
    {
        // 创建新节点
        link *node = (link *)malloc(sizeof(link));
        node->data = i;
        node->next = NULL;
        // 使得头指针指向下一个节点。
        temp->next = node;

        temp = temp->next;
    }
}

void displayLink(link *l)
{
    printf("输出链表\n");
    link *temp = l;
    while (temp->next)
    {
        temp = temp->next;
        printf("%d ", temp->data);
    }
    printf("\n");
}

void insertLink(link *l, int elem, int index)
{
    link *temp = l;
    for (size_t i = 0; i < index; i++)
    {
        temp = temp->next;
        if (temp == NULL)
        {
            printf("插入位置无效！");
        }
    }

    // 创建新的节点
    link *newNode = (link *)malloc(sizeof(link));
    newNode->data = elem;
    newNode->next = temp->next;
    //
    temp->next = newNode;
}

void delElem(link *l, int index)
{
    printf("执行 delElem(link *l, int index):void 函数，参数为 %d,%d\n", l, index);
    link *temp = l;
    for (size_t i = 0; i < index; i++)
    {
        temp = temp->next;
        if (temp == NULL)
        {
            printf("无节点");
        }
    }

    link *indexNode = temp->next;  //单独设置一个指针指向被删除结点，以防丢失
    temp->next = temp->next->next; //删除某个结点的方法就是更改前一个结点的指针域
    free(indexNode);               //手动释放该结点，防止内存泄漏
}

int selectIndex(link *l, int elem)
{
    link *temp = l;
    int index = 0;
    while (temp != NULL)
    {
        temp = temp->next;
        if (temp->data == elem)
        {
            return index;
        }
        index++;
    }

    return -1;
}

void updateElem(link *l, int newElem, int index)
{
    printf("执行 updateElem(link *l, int newElem, int index):void,参数为 %p,%d,%d", l, newElem, index);
    link *temp = l;
    for (size_t i = 0; i <= index; i++)
    {
        temp = temp->next;
    }

    temp->data = newElem;
}
1
2
3
4
5
6
7
8
9
10
11
创建链表
初始化数据
输出链表
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 
输出链表
0 2 4 6 1000 8 10 12 14 16 1000 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 
执行 delElem(link *l, int index):void 函数，参数为 1647664,5
输出链表
0 2 4 6 1000 10 12 14 16 1000 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 
index: 4执行 updateElem(link *l, int newElem, int index):void,参数为 0000000000192430,999,4输出链表
0 2 4 6 999 10 12 14 16 1000 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48

顺序表和链表的优缺点

顺序表和链表同属于线性表，但数据的存储结构有本质的不同：

  1. 顺序表存储数据，需预先申请一整块足够大的存储空间，然后将数据按照次序逐一存储，数据之间紧密贴合，不留一丝空隙，内存空间是连续的。
  2. 链表的存储方式与顺序表截然相反，什么时候存储数据，什么时候才申请存储空间，数据之间的逻辑关系依靠每个数据元素携带的指针维持。

基于不同的存储结构，顺序表和链表有以下几种不同。

开辟空间的方式不同

我们在前面的内容知道，顺序表需要使用 malloc()函数一次性申请足够的内存空间，但是一旦开辟就无法改变内存大小。（使用动态数组的情况除外）

而链表的情况不同，因为是链表存储，所以每次增加一个节点只需要申请一次节点（结构体）的内存空间，需要的时候申请，不需要的时候 free 。

空间利用率

从空间利用率的角度上看，顺序表的空间利用率显然要比链表高。

这是因为，链表在存储数据时，每次只申请一个节点的空间，且空间的位置是随机的。

这种申请存储空间的方式会产生很多空间碎片，一定程序上造成了空间浪费。不仅如此，由于链表中每个数据元素都必须携带至少一个指针，因此，链表对所申请空间的利用率也没有顺序表高。

空间碎片，指的是某些容量很小（1KB 甚至更小）以致无法得到有效利用的物理空间。

时间复杂度

解决不同类型的问题，顺序表和链表对应的时间复杂度也不同。

根据顺序表和链表在存储结构上的差异，问题类型主要分为以下 2 类：

  1. 问题中主要涉及访问元素的操作，元素的插入、删除和移动操作极少；
  2. 问题中主要涉及元素的插入、删除和移动，访问元素的需求很少；

第 1 类问题适合使用顺序表。这是因为，顺序表中存储的元素可以使用数组下标直接访问，无需遍历整个表，因此使用顺序表访问元素的时间复杂度为 O(1)；而在链表中访问数据元素，需要从表头依次遍历，直到找到指定节点，花费的时间复杂度为 O(n);

第 2 类问题则适合使用链表。链表中数据元素之间的逻辑关系靠的是节点之间的指针，当需要在链表中某处插入或删除节点时，只需改变相应节点的指针指向即可，无需大量移动元素，因此链表中插入、删除或移动数据所耗费的时间复杂度为 O(1)；而顺序表中，插入、删除和移动数据可能会牵涉到大量元素的整体移动，因此时间复杂度至少为 O(n);

综上所述，不同类型的场景，选择合适的存储结构会使解决问题效率成倍数地提高。

参考

  1. C编程网

其它

  1. 单链表的反转
  2. 如何判断两个单链表相交？