【无标题】

链表示意图

• 首节点：第一个有效节点
• 头节点：首节点前面的那个节点；不存放有效数据；目的是为了方便对首节点的操作，保持链表操作的一致性；
• 尾节点：最后一个节点
• 尾指针：指向最后一个节点的变量
• 头指针：指向头节点的变量，知道了头指针就确定了一个链表；

重点

1. 链表的插入和删除操作，关键处我在后文做了详解；
2. free§: 删除 p 所指向的变量所占内存（堆内存），而不是删除 p 本身所占内存（栈内存）。所以除了 free§，还要加一句 p = NULL，否则 p 会变成野指针。

关注我的 微信公众号：破壳Ai，分享最佳学习路径、教程和资源。成长路上，有我陪你。

源码

/*
 * 功能: 单链表
 * 作者: Guyue
 * 微信公众号: https://img.arctee.cn/one/pokeai-wechat.png
 * 网站：https://pokeai.cn
 * Github: https://github.com/Pokoai/DaHua-Data-Structure/tree/main/%E6%9C%80%E6%96%B0%E4%BC%98%E5%8C%96%E7%89%88%E4%BB%A3%E7%A0%81
 * Date: 2022-08-20
 */


#include 
#include 
#include 

typedef int ElemType;

// 节点定义
typedef struct node {
    ElemType data;
    struct node * pNext; 
}NODE, *PNODE;  // NODE等价于struct node, *PNODE等价于struct node *


// 函数声明
PNODE createList();
bool traverseList(PNODE pHead);
bool isEmpty(PNODE pHead);
int lengthList(PNODE pHead);
bool insertList(PNODE pHead, int pos, ElemType elem);
bool deleteList(PNODE pHead, int pos, ElemType * elem);
void sortList(PNODE pHead);


int main(void)
{
    PNODE pHead = createList();  // 创建一个链表，并返回头节点的地址给头指针pHead
    traverseList(pHead);  // 打印链表

    int len = lengthList(pHead);
    printf("链表长度：%d\n", len);

    printf("---插入元素---\n");
    insertList(pHead, 0, 555);
    traverseList(pHead);

    len = lengthList(pHead);
    printf("链表长度：%d\n", len);

    printf("---删除元素---\n");
    ElemType e;
    deleteList(pHead, 0, &e);
    traverseList(pHead);

    printf("---排序---\n");
    sortList(pHead);
    traverseList(pHead);

}

// 创建链表
PNODE createList()
{
    int len;
    int val;  

    // 首先创建一个头指针
    PNODE pHead = (PNODE)malloc(sizeof(NODE));  
    if ( NULL == pHead ) {
        printf("头节点内存分配失败，程序终止！");
        exit(-1);
    }
    // printf("%p\n", pHead);
    // 定义尾节点
    PNODE pTail = pHead;
    pTail->pNext = NULL;

    printf("请输入要创建链表的节点数：len = ");
    scanf("%d", &len);
    for ( int i = 0; i < len; i++ ) {
        printf("请输入第%d个节点的值：", i+1);
        scanf("%d", &val);
        // 为新节点分配内存
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        if ( NULL == pNew ) {
            printf("节点内存分配失败，程序终止！");
            exit(-1);
        }
        // 新节点初始化
        pNew->data = val;
        pNew->pNext = NULL;
        // 将新节点挂到尾节点后面
        pTail->pNext = pNew;
        // 更新尾节点
        pTail = pNew;
    }
    // printf("%p\n", pTail);
    return pHead;
}

// 遍历链表
bool traverseList(PNODE pHead)
{
    if ( isEmpty(pHead) ) {
        printf("链表为空!");
        return false;
    }

    // q指向第一个有效节点
    PNODE q = pHead->pNext;
    
    printf("遍历链表：");
    while ( q != NULL ) {
        printf("%d ", q->data);
        q = q->pNext;
    }
    printf("\n");

    return true;
}

// 是否为空
bool isEmpty(PNODE pHead)
{
    return ( NULL == pHead->pNext );
}

// 链表长度
int lengthList(PNODE pHead)
{
    int len = 0;
    PNODE p = pHead->pNext;

    while ( p != NULL ) {
        len++;
        p = p->pNext;
    }
    return len;
}

// 插入元素
// pos >= 1
// 该操作涉及到两个节点：pos前驱、pos本身
// 所以先遍历到 pos前驱，然后利用 pos前驱表示出 pos本身
bool insertList(PNODE pHead, int pos, ElemType elem)
{
    // 异常处理
    // if ( pos > 1 + lengthList(pHead) ) {
    //     printf("插入位置超过有效范围!\n");
    //     return false;
    // }
    
    // lengthList(pHead)要遍历链表，后面代码 while ( i++ < pos-1 ) { p = p->pNext; }也遍历链表，相当于遍历了两次，故效率低下
    // 优化：将两者结合起来，while( (i++ < pos-1) && p != NULL ) { p = p->pNext; }

    PNODE p = pHead;
    int i = 0;

    while ( (i++ < pos-1) && p != NULL ) {  // 见后文详细注解
        p = p->pNext;
    }

    if ( (i > pos-1) || NULL == p ) {  // NULL==p: pos>n+1; i>pos-1: pos<1
        printf("插入位置超过有效范围!\n");
        return false;
    }

    // 为新节点分配内存空间
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if ( NULL == pNew ) {
        printf("内存分配失败！");
        exit(-1);
    }
    pNew->data = elem;

    // 定位到pos位置的前驱节点，p指向该前驱节点
    // PNODE p = pHead;  
    // int i = 0;
    // while ( i++ < pos-1 ) {
    //     p = p->pNext;
    // }

    PNODE q = p->pNext;  // q指向pos位置的节点
    pNew->pNext = q;   // 先将新节点后端与pos节点连起来
    p->pNext = pNew;  // 再将新节点前端与pos前驱节点连起来

    return true;
}

// 删除元素
// 该操作涉及到三个节点：pos前驱、pos本身、pos后驱
// 所以先遍历到 pos前驱，然后利用pos前驱依次表示出 pos本身和pos后驱
bool deleteList(PNODE pHead, int pos, ElemType * elem)
{
    // 异常处理
    if ( isEmpty(pHead) ) {
        printf("链表为空！");
        return false;
    }
    // if ( pos > lengthList(pHead) ) {
    //     printf("pos超出有效范围！");
    //     return false;
    // } 

    // 定位到pos位置的前驱节点，p指向该前驱节点
    // PNODE p = pHead;
    // int i = 0;
    // while ( i++ < pos-1 ) {
    //     p = p->pNext;
    // }

    PNODE p = pHead;
    int i = 0;

    while ( (i++ < pos-1) && p != NULL ) {
        p = p->pNext;
    }

    if ( (i > pos-1) || NULL == p ) {
        printf("删除位置超过有效范围!\n");
        return false;
    }

    // 删除pos位置节点
    PNODE q = p->pNext;  // q指向pos位置的节点
    *elem = q->data;

    p->pNext = q->pNext;  // 将pos位置的前驱节点与后驱节点（q->pNext）连接起来
    // printf("p->pNext:%p\n", p->pNext);
    // printf("q:%p\n", q);
    free(q);  // 释放q所指的那个变量所占的内存，但是q变量仍然存在
    q = NULL;  // 将q指向空，否则q就变成了野指针，存在危险

    return true;
}

// 排序
void sortList(PNODE pHead)
{
    ElemType t; 

    for ( PNODE p = pHead; p != NULL; p = p->pNext ) {
        for ( PNODE q = p->pNext; q != NULL; q = q->pNext ) {
            if ( p->data > q->data ) {
                t = p->data;
                p->data = q->data;
                q->data = t;
            }
        }
    }
}

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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251

注解

有疑问，请关注我的 微信公众号：破壳Ai

PNODE p = pHead;
int i = 0;

while ( (i++ < pos-1) && p != NULL ) {
    p = p->pNext;
}

if ( (i > pos-1) || NULL == p ) {  // NULL==p: pos>n+1; i>pos-1: pos<1
    printf("插入位置超过有效范围!\n");
    return false;
}
1
2
3
4
5
6
7
8
9
10
11

1. (i++ < pos-1)：遍历到 pos 的前驱节点。

2. p != NULL：如果 pos 超过（链表长度+1），那么 while 循环会从该条件退出循环。

3. while 语句退出循环有四种可能：

   • 成功找到 pos 的前驱节点：(i++ < pos-1) 不满足，跳出循环；
   • pos >（链表长度+1）：p != NULL 不满足，跳出循环；
   • pos < 1：一进入 while ，(i++ < pos-1) 就不满足，直接跳出；
   • pos == 1：一进入 while ，(i++ < pos-1) 就不满足，直接跳出；

4. 针对第3点的四种跳出循环情况，需要分别处理：

   • 成功找到 pos 的前驱节点 + pos == 1：这两种情况都是正常的，进入后面插入程序；
   • pos >（链表长度+1） + pos < 1：这两种情况均异常，进入后面 if 程序块进行异常处理；
     为了区别 pos == 1 和 pos < 1两种情况，if 条件采用：(i > pos-1)来剔除掉 pos == 1的正常情况。