数据结构2：顺序表与链表

数据结构2

线性表

定义

由n(n>=0)个数据特性相同的元素构成的有限序列，称为线性表。

n == 0时，称为空表。

对于头一个元素，我们称为“头节点”，对于最后一个数据元素“尾节点”。

除了头节点之外，每个元素的前一个元素，叫做“前驱”。

除了尾节点，每个元素的后一个元素叫做“后驱”。

顺序表

用一组连续的内存单元依次存储线性表的各个元素，也就是说，逻辑上相邻的元素，实际的物理存储空间也是连续的。

接下来，我们会构建一个顺序表并且逐步实现“增删改查”。

我们构建一个顺序表：

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

struct list
{
    int *date;
    int length = 0;

};
void add(struct list *l, int date)
{
    l->date[l->length] = date;   //使用下标来像使用数组一样使用指针是被允许的
    l->length++;
}


int main(int argc, char const *argv[]) {
    struct list l;
    add(&l, 20210101);
    add(&l, 20210102);
    return 0;
}

该代码实现了一个简易的顺序表，且配置了尾部增加的功能，但是我们往往只需要在中间插入某个元素，可以这么做：

1
2
3
4
5
6
7
8
9
void insertElement(struct list *l, int index, int date)
{
    for (int i = l->length - 1; i >= index; i--) 
    {
        l->date[i + 1] = l->date[i];  //这会把待插入元素之后的元素全部往后挪动一个单位。
    }
    l->date[index] = date;     //把输入元素插入到表中
    l->length++;               //长度更新
}

如果是在末尾插入，无疑其时间复杂度是最低的，在头节点插入是最大的。

类似地，我们能够写一个函数实现删。

1
2
3
4
5
6
7
8
void deleteElement(struct list *l, int index)
{
    for (int i = index; i < l->length - 1; i++)
    {
        l->date[i] = l->date[i + 1];
    }
    l->length--;
}

在删的基础上修改，就得到了改。

1
2
3
4
void changeElement(struct list *l, int index, int date)
{
    l->date[index] = date;
}

从date[0]开始查找，到length结束，就是查。

1
2
3
4
5
6
7
8
9
10
11
12
void seekElement(struct list *l, int date)
{
    for (int i = 0; i < l->length; i++)
    {
        if (l->date[i] == date)
        {
            printf("Element found at index %d\n", i);
            return;
        }
    }
    printf("Element not found\n");
}

顺序表有很多不方便使用的地方，说白了，他就是一个套壳的数组。所以，我们使用了一种链式结构-链表。

链表

线性表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的)。
为了表示每个数据元素a与其直接后继数据元素a[i+1]之间的逻辑关系，对数据元素a[i]来说，除了其本身的信息之外，还需要存储一个指示其直接后继的信息（直接后继的存储位置)。这两部分信息组成数据元素a的存储映像，称为节点(node)。
结点包括两个域：其中存储数据元素信息的称为数据域；存储直接后继存储位置有域称为指针域。指针域中存储的信息称作指针或链。

061b5ffce79596f4445207f850c0db6e

初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# include <stdio.h>
typedef struct  Node{  //定义节点
    int data;
    struct Node *next;
}Node;


Node *init(){
    Node *head = (Node*)malloc(sizeof(Node));
    head->data = 0;    //数据域为0
    head->next = NULL;  //指针域为空指针
    return head;
}


int main() {
    Node *list = init();
    return 0;
}

链表的延长

原理：前一个节点的指针指向新插入的节点，使新节点的指针指向前一个节点原来指向的节点。

image-20250403214812079

头插法

头插法指的是每次都在头节点后面一个位置插入新的数据节点。

1
2
3
4
5
6
void insert(Node *head, int data){
    Node *new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data; //引入传入参数
    new_node->next = head->next;  //新节点的指针域指向原链表的头节点的指针域
    head->next = new_node;  //原链表的头节点的指针域指向新节点
}

这会使得每个插入的结构体都处于头节点的背后，从而免去了数组和顺序表的元素移动这一步骤，执行效率快很多。

链表的遍历

1
2
3
4
5
6
7
8
void list_print(Node *head){
    Node *p = head->next;   
    while(p!= NULL){  //只要不是空指针，就一直循环
        printf("%d ", p->data);
        p = p->next;   //指针指向下一个节点
    }
    printf("\n");
}

尾插法

尾插法总是在链表的尾部插入新节点。

1
2
3
4
5
6
7
8
9
10
void insert_tail(Node *head, int data){
    Node *new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = NULL;
    Node *p = head;
    while(p->next!= NULL){  //该循环用于找到最后一个节点
        p = p->next;
    }
    p->next = new_node;
}

指定位置插入节点

我们在特殊情况需要在某两个节点中插入一个新节点。

1
2
3
4
5
6
7
8
9
10
11
void insert(Node *head, int pos, int data){
    Node *new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = NULL;  //初始化为空指针，防止出错
    Node *p = head;
    for(int i = 0; i < pos-1; i++){  //循环找到插入位置的前一个节点
        p = p->next;
    }
    new_node->next = p->next;  //新节点的指针域指向原节点的指针域
    p->next = new_node;  //原节点的指针域指向新节点
}

删除节点

原理是让被删除节点的前一个节点直接指向被删除节点的后一个节点，链就是自动排除被删除元素。

image-20250403215033701

1
2
3
4
5
6
7
8
9
void delete(Node *head, int pos){
    Node *p = head;
    for(int i = 0; i < pos-1; i++){  //循环找到删除位置的前一个节点
        p = p->next;
    }
    Node *del_node = p->next;  //找到要删除的节点
    p->next = del_node->next;  //原节点的指针域指向要删除节点的下一个节点
    free(del_node);  //释放要删除的节点
}

释放所有节点

释放，指的是free，指的是将节点占用的堆内存解放出来。

1
2
3
4
5
6
7
8
9
void free_list(Node *head){
    Node *p = head->next;
    while(p!= NULL){  //如果不是尾节点，就一直free下去。
        Node *temp = p;
        p = p->next;
        free(temp);
    }
    free(head);  //释放头节点
}

源代码

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


Node *init(){
    Node *head = (Node*)malloc(sizeof(Node));
    head->data = 0;    //数据域为0
    head->next = NULL;  //指针域为空指针
    return head;
}

void insert(Node *head, int data){
    Node *new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data; //引入传入参数
    new_node->next = head->next;  //新节点的指针域指向原链表的头节点的指针域
    head->next = new_node;  //原链表的头节点的指针域指向新节点
}
void list_print(Node *head){
    Node *p = head->next;   
    while(p!= NULL){  //只要不是空指针，就一直循环
        printf("%d ", p->data);
        p = p->next;   //指针指向下一个节点
    }
    printf("\n");
}
void insert(Node *head, int pos, int data){
    Node *new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = NULL;  //新节点的指针域为空指针
    Node *p = head;
    for(int i = 0; i < pos-1; i++){  //循环找到插入位置的前一个节点
        p = p->next;
    }
    new_node->next = p->next;  //新节点的指针域指向原节点的指针域
    p->next = new_node;  //原节点的指针域指向新节点
}

void free_list(Node *head){
    Node *p = head->next;
    while(p!= NULL){  //循环释放所有节点
        Node *temp = p;
        p = p->next;
        free(temp);
    }
    free(head);  //释放头节点
}
void delete(Node *head, int pos){
    Node *p = head;
    for(int i = 0; i < pos-1; i++){  //循环找到删除位置的前一个节点
        p = p->next;
    }
    Node *del_node = p->next;  //找到要删除的节点
    p->next = del_node->next;  //原节点的指针域指向要删除节点的下一个节点
    free(del_node);  //释放要删除的节点
}
void insert_tail(Node *head, int data){
    Node *new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = NULL;
    Node *p = head;
    while(p->next!= NULL){  //该循环用于找到最后一个节点
        p = p->next;
    }
    p->next = new_node;
}
int main() {
    Node *list = init();
    insert(list, 2);
    list_print(list);
    return 0;
}