AHA'S BOOK

线性表中的「单链表」的实现，包括单链表的顺序存储（数组实现）和单链表的链式存储。上篇文章 介绍了单链表的顺序存储（数组实现），这篇文章主要介绍单链表的链式存储（结构体指针实现）。

链表的链式存储（结构体指针实现）

链表的 API 主要包括：

  • 创建并初始化链表
  • 查找链表中的元素
  • 向链表中插入元素
  • 删除链表中的元素
  • 获取链表的长度

链表结构定义

1
2
3
4
5
// 定义链表结构
typedef struct Node {
    int data;
    struct Node* next;
} Linked_t;

这段代码定义了一个名为 Linked_t 的结构体，用来表示一个结构体实现的链表。

该结构体包含两个成员变量：

  1. int data：一个整形变量，用来存储链表中的元素。
  2. struct Node* next：一个链表结构体指针，用于指向链表中当前结点的下一个结点的指针（地址）。

链表中的不同元素，通过节点之间的指针首尾连接起来。

创建并初始化链表

使用动态申请内存空间的方式创建并初始化一个链表。

1
2
3
4
5
6
7
Linked_t *createNode(int data) {
    Linked_t *linked = (Linked_t *)malloc(sizeof(Linked_t));
    linked->data = data;
    linked->next = NULL;
    // printf("Linked_t size is %d bytes.\n", sizeof(linked));
    return linked;
}

查找链表中的元素

在链表中查找目标元素第一次出现时的结点，不存在则返回空。

1
2
3
4
5
6
7
8
9
10
Linked_t *findNode(Linked_t *linked, int target) {
    Linked_t *curNode = linked;
    while (curNode != NULL) {
        if (curNode->data == target) {
            return curNode;
        }
        curNode = curNode->next;
    }
    return NULL;  // 没有找到元素
}

向链表末尾插入元素

在链表末尾插入新结点，插入成功时返回链表头结点，失败时返回空地址。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Linked_t *insertTailNode(Linked_t *linked, int data) {
    if (linked == NULL) {
        printf("linked is NULL\n");
        return NULL;
    }

    Linked_t *curNode = linked;
    while (curNode->next != NULL) {
        curNode = curNode->next;
    }
    Linked_t *newNode = createNode(data);
    curNode->next = newNode;
    newNode->next = NULL;

    return linked;
}

向链表指定结点前插入元素

在链表的指定结点前插入新结点，如果指定的结点为空，则在末尾插入结点，最后返回插入新结点后链表的头结点。

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
Linked_t *insertNode(Linked_t *linked, Linked_t *node, int data) {
    if (linked == NULL) {
        printf("linked is NULL\n");
        return NULL;
    } else if (node == linked) {  // 在链表头结点前插入新结点
        Linked_t *newNode = createNode(data);
        newNode->next = linked;
        return newNode;
    } else if (node == NULL) {
        return insertTailNode(linked, data);
    }

    Linked_t *preNode = linked;
    Linked_t *curNode = preNode->next;
    while (curNode != NULL) {
        if (curNode == node) {  // 在链表结点中间插入新结点
            Linked_t *newNode = createNode(data);
            preNode->next = newNode;
            newNode->next = curNode;
            return linked;
        }
        preNode = curNode;
        curNode = curNode->next;
    }
    printf("The specified node does not exist in the linked list.\n");
    return linked;
}

删除链表中的元素

删除链表中指定索引位置的元素，并返回新的链表。

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
Linked_t *deleteNode(Linked_t *linked, int index) {
    if (linked == NULL || index < 0) {
        return linked;
    }

    if (index == 0) {
        Linked_t *newHead = linked->next;
        linked->next = NULL;
        free(linked);
        return newHead;
    } else {
        int cnt = 0;
        Linked_t *preNode = linked, *curNode = preNode->next;
        while (curNode != NULL) {
            cnt++;
            if (cnt == index) {
                Linked_t *curNext = curNode->next;
                curNode->next = NULL;
                free(curNode);
                preNode->next = curNext;
                return linked;
            } else {
                preNnode = curNode;
                curNode = curNode->next;
            }
        }
    }
    printf("The specified index is illegal.\n");
    return linked;
}

获取链表的长度

获取链表中有效数据元素的长度（结点的数量）。

1
2
3
4
5
6
7
8
int getLinkedLength(Linked_t *linked) {
    int count = 0;
    while (linked != NULL) {
        count++;
        linked = linked->next;
    }
    return count;
}

释放链表空间

1
2
3
4
5
6
7
8
9
void freeLinked(Linked_t *linked) {
    Linked_t *curNode = linked;
    Linked_t *tmpNode = NULL;
    while (curNode != NULL) {
        tmpNode = curNode->next;
        free(curNode);
        curNode = tmpNode;
    }
}

链表的数组实现完整代码

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

#define MAX_SIZE (100)

// 定义链表结构
typedef struct Node {
    int data;
    struct Node* next;
} Linked_t;

Linked_t *createNode(int data) {
    Linked_t *linked = (Linked_t *)malloc(sizeof(Linked_t));
    linked->data = data;
    linked->next = NULL;
    // printf("Linked_t size is %d bytes.\n", sizeof(linked));
    return linked;
}

Linked_t *findNode(Linked_t *linked, int target) {
    Linked_t *curNode = linked;
    while (curNode != NULL) {
        if (curNode->data == target) {
            return curNode;
        }
        curNode = curNode->next;
    }
    return NULL;  // 没有找到元素
}

Linked_t *insertTailNode(Linked_t *linked, int data) {
    if (linked == NULL) {
        printf("linked is NULL\n");
        return NULL;
    }

    Linked_t *curNode = linked;
    while (curNode->next != NULL) {
        curNode = curNode->next;
    }
    Linked_t *newNode = createNode(data);
    curNode->next = newNode;
    newNode->next = NULL;

    return linked;
}

Linked_t *insertNode(Linked_t *linked, Linked_t *node, int data) {
    if (linked == NULL) {
        printf("linked is NULL\n");
        return NULL;
    } else if (node == linked) {  // 在链表头结点前插入新结点
        Linked_t *newNode = createNode(data);
        newNode->next = linked;
        return newNode;
    } else if (node == NULL) {
        return insertTailNode(linked, data);
    }

    Linked_t *preNode = linked;
    Linked_t *curNode = preNode->next;
    while (curNode != NULL) {
        if (curNode == node) {  // 在链表结点中间插入新结点
            Linked_t *newNode = createNode(data);
            preNode->next = newNode;
            newNode->next = curNode;
            return linked;
        }
        preNode = curNode;
        curNode = curNode->next;
    }
    printf("The specified node does not exist in the linked list.\n");
    return linked;
}

Linked_t *deleteNode(Linked_t *linked, int index) {
    if (linked == NULL || index < 0) {
        return linked;
    }

    if (index == 0) {
        Linked_t *newHead = linked->next;
        linked->next = NULL;
        free(linked);
        return newHead;
    } else {
        int cnt = 0;
        Linked_t *preNode = linked, *curNode = preNode->next;
        while (curNode != NULL) {
            cnt++;
            if (cnt == index) {
                Linked_t *curNext = curNode->next;
                curNode->next = NULL;
                free(curNode);
                preNode->next = curNext;
                return linked;
            } else {
                preNnode = curNode;
                curNode = curNode->next;
            }
        }
    }
    printf("The specified index is illegal.\n");
    return linked;
}

int getLinkedLength(Linked_t *linked) {
    int count = 0;
    while (linked != NULL) {
        count++;
        linked = linked->next;
    }
    return count;
}

void freeLinked(Linked_t *linked) {
    Linked_t *curNode = linked;
    Linked_t *tmpNode = NULL;
    while (curNode != NULL) {
        tmpNode = curNode->next;
        free(curNode);
        curNode = tmpNode;
    }
}

void printLinked(Linked_t *linked) {
    printf("Linked List: ");
    while (linked) {
        printf("%d ", linked->data);
        linked = linked->next;
    }
    printf("\n");
}

int main() {
    Linked_t *linked = createNode(10);
    printLinked(linked);

    linked = insertTailNode(linked, 20);
    printLinked(linked);

    linked = insertTailNode(linked, 30);
    printLinked(linked);

    linked = insertNode(linked, linked, 5);
    printLinked(linked);

    linked = insertNode(linked, linked->next, 15);
    printLinked(linked);

    linked = insertNode(linked, NULL, 40);
    printLinked(linked);

    linked = deleteNode(linked, 0);
    printLinked(linked);

    linked = deleteNode(linked, 2);
    printLinked(linked);

    int length = getLinkedLength(linked);
    printf("Linked List Length: %d\n", length);

    freeLinked(linked);
    
    return 0;
}

程序的输出结果为：

1
2
3
4
5
6
7
8
9
Linked List: 10
Linked List: 10 20
Linked List: 10 20 30
Linked List: 5 10 20 30
Linked List: 5 15 10 20 30
Linked List: 5 15 10 20 30 40
Linked List: 15 10 20 30 40
Linked List: 15 10 30 40
Linked List Length: 4
aha
2023-10-08
数据结构 链表
Expand all Back to top Go to bottom Search in blogs
银河白
豆沙绿
杏仁黄
青草绿
秋叶褐