【C语言 数据结构】单链表的学习使用_首元节点

本文借鉴点击跳转

链表的介绍

链表是什么

链表又称单链表、链式存储结构，用于存储逻辑关系为“一对一”的数据。

和顺序表不同，使用链表存储数据，不强制要求数据在内存中集中存储，各个元素可以分散存储在内存中。例如，使用链表存储 {1,2,3}，各个元素在内存中的存储状态可能是：

可以看到，数据不仅没有集中存放，在内存中的存储次序也是混乱的。那么，链表是如何存储数据间逻辑关系的呢？

链表存储数据间逻辑关系的实现方案是：为每一个元素配置一个指针，每个元素的指针都指向自己的直接后继元素，如下图所示：

显然，我们只需要记住元素 1 的存储位置，通过它的指针就可以找到元素 2，通过元素 2 的指针就可以找到元素 3，以此类推，各个元素的先后次序一目了然。

像图 2 这样，数据元素随机存储在内存中，通过指针维系数据之间“一对一”的逻辑关系，这样的存储结构就是链表。

---

结点

很多教材中，也将“结点”写成“节点”，它们是一个意思。

在链表中，每个数据元素都配有一个指针，这意味着，链表上的每个“元素”都长下图这个样子：

数据域用来存储元素的值，指针域用来存放指针。数据结构中，通常将图 3 这样的整体称为结点。

也就是说，链表中实际存放的是一个一个的结点，数据元素存放在各个结点的数据域中。举个简单的例子，图 2 中 {1,2,3} 的存储状态用链表表示，如下图所示：

---

在 C 语言中，可以用结构体表示链表中的结点，例如：

typedef char ElemType;

typedef struct node {
    ElemType data;
    struct Node *link;
} Node;
1
2
3
4
5
6

我们习惯将结点中的指针命名为 next，因此指针域又常称为“Next 域”。

---

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

图 4 所示的链表并不完整，一个完整的链表应该由以下几部分构成：

1. 头指针：一个和结点类型相同的指针，它的特点是：永远指向链表中的第一个结点。上文提到过，我们需要记录链表中第一个元素的存储位置，就是用头指针实现。
2. 结点：链表中的节点又细分为头结点、首元结点和其它结点：
   • 头结点：某些场景中，为了方便解决问题，会故意在链表的开头放置一个空结点，这样的结点就称为头结点。也就是说，头结点是位于链表开头、数据域为空（不利用）的结点。
   • 首元结点：指的是链表开头第一个存有数据的结点。
   • 其他节点：链表中其他的节点。

也就是说，一个完整的链表是由头指针和诸多个结点构成的。每个链表都必须有头指针，但头结点不是必须的。

例如，创建一个包含头结点的链表存储 {1,2,3}，如下图所示：

再次强调，头指针永远指向链表中的第一个结点。换句话说，如果链表中包含头结点，那么头指针指向的是头结点，反之头指针指向首元结点。

---

链表的基本操作

插入

同顺序表一样，向链表中增添元素，根据添加位置不同，可分为以下 3 种情况：

• 插入到链表的头部，作为首元节点；
• 插入到链表中间的某个位置；
• 插入到链表的最末端，作为链表中最后一个结点；

对于有头结点的链表，3 种插入元素的实现思想是相同的，具体步骤是：

1. 将新结点的 next 指针指向插入位置后的结点；
2. 将插入位置前结点的 next 指针指向插入结点；

例如，在链表 {1,2,3,4} 的基础上分别实现在头部、中间、尾部插入新元素 5，其实现过程如图1 所示：

代码实现

// TODO 添加节点,在最后的位置插入
void appendTail(Node *list, ElemType data) {
//    Node* head=list;
    Node *node = (Node *) malloc(sizeof(Node));
    node->data = data;
    node->link = NULL;
    while (list->link) {
        list = list->link;
    }
    list->link = node;
}
1
2
3
4
5
6
7
8
9
10
11

---

删除

从链表中删除指定数据元素时，实则就是将存有该数据元素的节点从链表中摘除。

对于有头结点的链表来说，无论删除头部（首元结点）、中部、尾部的结点，实现方式都一样，执行以下三步操作：

1. 找到目标元素所在结点的直接前驱结点；
2. 将目标结点从链表中摘下来;
3. 手动释放结点占用的内存空间；

从链表上摘除目标节点，只需找到该节点的直接前驱节点 temp，执行如下操作：

temp->next=temp->next->next;
1

例如，从存有 {1,2,3,4} 的链表中删除存储元素 3 的结点，则此代码的执行效果如图 3 所示：

---

代码实现

//TODO 删除指定位置的节点
void delLink(Node *list, int loc) {
    if(loc<1){//判断和删除位置是否有误
        printf("删除位置错误！！！");
    }else{
        for (int i = 0; i < loc - 1; ++i) {
            list = list->link;//找到删除位置的前一个节点
        }
        Node *node = list->link;
        node = node->link;//删除位置的后一个节点
        free(list->link);//释放删除的节点
        list->link = node;//指向新的地址
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

完整代码如下所示

//
// Created by HR on 2022/9/27.
//
#include "stdio.h"
#include "windows.h"
#include "stdlib.h"

typedef char ElemType;

typedef struct node {
    ElemType data;
    struct Node *link;
} Node;

// TODO 初始化链表
Node *creatHead() {
    Node *head;
    head = (Node *) malloc(sizeof(Node));
    head->link = NULL;
    return head;
}

// TODO 添加节点,在最后的位置插入
void appendTail(Node *list, ElemType data) {
//    Node* head=list;
    Node *node = (Node *) malloc(sizeof(Node));
    node->data = data;
    node->link = NULL;
    while (list->link) {
        list = list->link;
    }
    list->link = node;
}

// TODO 打印输出
void printList(Node *list)//遍历操作
{
    list = list->link;//指向头节点
    while (list)//遍历打印
    {
        printf("%c", list->data);
        list = list->link;
    }
    printf("\n");
}

// TODO 删除指定值的节点
void deleteTail(Node *list, ElemType data)//删除
{
    Node *pre = list;
    Node *current = list->link;
    while (current) {
        if (current->data == data) {
            pre->link = current->link;
            free(current);
            break;//退出循环
        }
        pre = current;
        current = current->link;
    }
}

// TODO 在指定位置插入指定的值
void insertLink(Node *list, int loc, ElemType data) {
    if(loc<1){//判断插入位置是否有误
        printf("插入位置错误！！！");
    }else{
        Node *node = (Node *) malloc(sizeof(Node));// 需要插入的节点
        node->data = data;//修改数据域
        for (int i = 0; i < loc - 1; ++i) {
            list = list->link;//找到插入位置前一个节点
        }
        node->link = list->link;//为新建节点的指针域赋值
        list->link = node;//修改插入节点前一位的指针域地址
    }
}

//TODO 删除指定位置的节点
void delLink(Node *list, int loc) {
    if(loc<1){//判断和删除位置是否有误
        printf("删除位置错误！！！");
    }else{
        for (int i = 0; i < loc - 1; ++i) {
            list = list->link;//找到删除位置的前一个节点
        }
        Node *node = list->link;
        node = node->link;//删除位置的后一个节点
        free(list->link);//释放删除的节点
        list->link = node;//指向新的地址
    }
}

// TODO 有序链表合并
void MergeList(Node *a, Node *b, Node *c) {
    Node *aNext = a->link;
    Node *bNext = b->link;
    while (aNext && bNext) {
        Node *tmp = (Node *) malloc(sizeof(Node));
        if (aNext->data > bNext->data) {
            tmp->data = bNext->data;
            tmp->link = c->link;
            c->link = tmp;
            bNext = bNext->link;
        } else {
            tmp->data = aNext->data;
            tmp->link = c->link;
            c->link = tmp;
            aNext = aNext->link;
        }
    }
    while (aNext) {
        Node *tmp = (Node *) malloc(sizeof(Node));
        tmp->data = aNext->data;
        tmp->link = c->link;
        c->link = tmp;
        aNext = aNext->link;
    }
    while (bNext) {
        Node *tmp = (Node *) malloc(sizeof(Node));
        tmp->data = bNext->data;
        tmp->link = c->link;
        c->link = tmp;
        bNext = bNext->link;
    }
}

int main() {
    Node *head = creatHead();
    char arr[] = "asdfghjkl";
    for (int i = 0; i < strlen("asdfghjkl"); i++) {
        appendTail(head, arr[i]);
    }
    printList(head);
    deleteTail(head, 'b');
    printf("链表数据展示:");
    printList(head);
    insertLink(head, 4, 'z');
    printf("在第四个位置插入z:");
    printList(head);
    delLink(head, 4);
    printf("删除第四个位置的元素:");
    printList(head);

    // 合并
    Node *a = creatHead();
    char arr1[] = "3789";
    for (int i = 0; i < strlen("3789"); i++) {
        appendTail(a, arr1[i]);
    }
    Node *b = creatHead();
    char arr2[] = "257";
    for (int i = 0; i < strlen("257"); i++) {
        appendTail(b, arr2[i]);
    }
    printf("链表a的数据:");
    printList(a);
    printf("链表b的数据:");
    printList(b);
    Node *c = creatHead();
    MergeList(a, b, c);
    printf("合并后的链表数据:");
    printList(c);

    return 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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165

运行结果展示

链表数据展示:asdfghjkl
在第四个位置插入z:asdzfghjkl
删除第四个位置的元素:asdfghjkl
链表a的数据:3789
链表b的数据:257
合并后的链表数据:9877532