目录
- 前言
- 单链表
- 1.1 单链表的定义
- 1.2单链表代码实现
- 1.2.1 头文件
- 1.2.2 函数实现文件
- 1.2.3 测试文件
- 1.2.4 野指针问题
- 总结
前言
本文介绍单链表，主要是创销、增删改查代码实现。
注：文章中函数命名采取STL库。
单链表
1.1 单链表的定义
单链表是链线性表的一种，线性表是一种逻辑结构，根据不同的物理（存储）结构即顺序存储和链式存储，分为顺序表和链表。
链表顾名思义，像链条一样，将存储数据的结点一个一个串起来；每一个节点不仅存储数据，也存储指向下一个节点的指针。
不同于顺序表，其优点是，不需要一次开辟大量空间进行存储，根据需要随时动态申请内存。
缺点是，需要存储额外的指针。
而单链表，是每个节点只有一个指针。
单链表在内存中的分布可以抽象为下图：
链表插入时是否需要对传入的地址进行断言？
- 如果传入的是单链表头指针，是不需要断言的，因为即使是空链表，也可以插入呀~
- 但如果是顺序表的话，是需要对传入的指针进行断言的，因为如下图，传入的结构体指针是有数据的，数组指针、size、capacity，如果传入的指针为NULL，说明该顺序表不存在！
顺序表的代码实现
//顺序表的定义
#include <assert.h>
typedef int SLDataType;
#define INIT_CAPACITY 4
typedef struct SeqList
{SLDataType* a;int size;int capacity;
}SL;//顺序表的插入
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);int end = ps->size - 1;while (end >= pos)ps->a[end + 1] = ps->a[end--];ps->a[pos] = x;ps->size++;
}
1.2单链表代码实现
单链表的创销、增删改查函数代码实现如下
1.2.1 头文件
SList.h
//将所有可能用到的库文件中的头文件在.h文件中声明
#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SLTNode
{SLTDataType data;struct SLTNode* next;
}SLTNode;//定义一个单链表//单链表的打印、插入、删除函数声明
void SLTPrint(SLTNode* phead);//打印
SLTNode* BuySLTNode(SLTDataType x);//动态申请一个节点，用于插入
void SLTPushFront(SLTNode** pphead, SLTDataType x);//头插
void SLTPushBack(SLTNode** pphead, SLTDataType x);//尾插
void SLTPopFront(SLTNode** pphead);//头删
void SLTPopBack1(SLTNode** pphead);//尾删方式1
void SLTPopBack2(SLTNode** pphead);//尾删方式2
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
void SLTErase(SLTNode** pphead, SLTNode* pos);
void SLTEraseAfter(SLTNode* pos);
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
void SLTDestroy1(SLTNode* phead);//销毁链表
void SLTDestroy2(SLTNode** phead);//传二级指针销毁链表
1.2.2 函数实现文件
SList.c
//单链表的打印、插入、删除函数实现
#include "SList.h"
void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}//封装的思想，头插、尾插都要申请节点，将其封装为函数，一方面调用方便；另一方面，方便维护，如果出了问题，在函数内部修复即可，如果没有封装，则每次使用这个功能的地方都要修复。
SLTNode* BuySLTNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc failed");return NULL;}newnode->data = x;newnode->next = NULL;return newnode;
}//插入没有必要对顺序表是否为空进行讨论，因为与非空操作一致
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySLTNode(x);newnode->next = *pphead;*pphead = newnode;
}void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySLTNode(x);if (*pphead == NULL)*pphead = newnode;else{//找尾节点SLTNode* tail = *pphead;//命名的可读性while (tail->next != NULL)tail = tail->next;tail->next = newnode;}
}//删除需要对链表为空的情况单独讨论，没有节点怎么删呀
//删除也要对只有一个节点情况进行讨论，因为第一个节点的内存被释放，与删除非第一个结点相比，要修改头指针，否则头指针成为野指针
//尾删方式1
void SLTPopBack1(SLTNode** pphead)
{assert(pphead);assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tail = *pphead;SLTNode* prev = NULL;while (tail->next != NULL){prev = tail;//记录尾节点的前一个节点的位置tail = tail->next;}free(tail);tail = NULL;//VS2022语法较为严格if (prev == NULL)return;prev->next = NULL;}
}//尾删方式2
void SLTPopBack2(SLTNode** pphead)
{assert(pphead);assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tail = *pphead;//VS2022语法较为严格if (tail == NULL || tail->next==NULL)return;//找到尾节点的前一个节点while (tail->next->next != NULL)tail = tail->next;free(tail->next);//释放尾节点所在内存tail->next = NULL;//将指向尾节点的指针置为空}
}void SLTPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* first = *pphead;*pphead = first->next;free(first);first = NULL;
}SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (*pphead == pos)SLTPushFront(pphead,x);else{SLTNode* prev = *pphead;while (prev->next!=pos)prev = prev->next;SLTNode* newnode = BuySLTNode(x);newnode->next = pos;prev->next = newnode;}
}void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (*pphead == pos)SLTPopFront(pphead);else{SLTNode* prev = *pphead;while (prev->next != pos)prev = prev->next;prev->next = pos->next;free(pos);}
}void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySLTNode(x);newnode->next = pos->next;pos->next = newnode;
}void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}void SLTDestroy1(SLTNode* phead)
{SLTNode* cur = phead;while (cur){SLTNode* tmp = cur->next;free(cur);cur = tmp;}
}void SLTDestroy2(SLTNode** pphead)
{assert(pphead);SLTNode* cur = *pphead;while (cur){SLTNode* tmp = cur->next;free(cur);cur = tmp;}*pphead = NULL;
}
1.2.3 测试文件
Test.c
#include "SList.h"
//单链表的打印、插入、删除函数测试
void TestList1()
{SLTNode* plist = NULL;for (int i = 0; i < 10; i++)SLTPushFront(&plist, i);SLTPrint(plist);SLTPopBack1(&plist);SLTPrint(plist);SLTPopBack2(&plist);SLTPrint(plist);
}//对头删函数进行测试
void TestList2()
{SLTNode* plist = NULL;for (int i = 0; i < 10; i++)SLTPushBack(&plist, i);SLTPopFront(&plist);SLTPrint(plist);
}
void TestList3()
{SLTNode* plist = NULL;for (int i = 0; i < 10; i++)SLTPushBack(&plist, i);for (int i = 0; i < 10; i++){SLTPopFront(&plist);SLTPrint(plist);}//SLTPopFront(&plist);
}//对尾删函数进行测试
void TestList4()
{SLTNode* plist = NULL;for (int i = 0; i < 10; i++)SLTPushBack(&plist, i);for (int i = 0; i < 10; i++){SLTPopBack1(&plist);SLTPrint(plist);}//SLTPopBack1(&plist);
}//对寻找、插入、删除、后插函数进行测试
void TestList5()
{SLTNode* plist = NULL;for (int i = 0; i < 10; i++)SLTPushBack(&plist, i+1);SLTPrint(plist);SLTNode* ret = SLTFind(plist, 3);ret->data *= 5;SLTPrint(plist);//SLTInsert(&plist, ret, 30);SLTErase(&plist, ret);SLTPrint(plist);
}
void TestList6()
{SLTNode* plist = NULL;for (int i = 0; i < 10; i++)SLTPushBack(&plist, i+1);SLTPrint(plist);SLTNode* ret = SLTFind(plist, 1);ret->data *= 5;SLTPrint(plist);//SLTInsert(&plist, ret, 30);//SLTErase(&plist, ret);//SLTInsertAfter(ret, 30);SLTEraseAfter(ret);ret = NULL;SLTPrint(plist);
}//对链表销毁函数进行测试
void TestList7()
{SLTNode* plist = NULL;for (int i = 0; i < 10; i++)SLTPushBack(&plist, i + 1);SLTPrint(plist);/*SLTDestroy1(plist);plist = NULL;*/ //传头指针进行销毁，要将头指针置为NULLSLTDestroy2(&plist);
}
int main()
{TestList7();return 0;
}
1.2.4 野指针问题
对于销毁链表操作，有一个经典错误，就是野指针，其实其他场景下也会出现，代码示例如下。首先我们要清楚free(cur)到底做了什么，就是将cur指向的原本动态开辟的内存空间的使用权还给操作系统，cur的值可能变，也可能不变，但是即使不变，也不能通过cur再去使用其指向的那块空间了。通过调试我们可以看到，虽然free前后plist的值没有改变（下图红色框），但是free后，plist指向区域的data是随机值（下图橙色框），并且后续节点不能被访问（下图蓝色框），在free(plist)后打开plist的next域显示如下图黄色框。
举个例子，这就像住酒店，指针就像房卡，显示房间号，可以找到房间，也就是内存区域，free就像退房，退房后还有可能通过房卡找到房间吗？当然可以，可是没有使用权。用一个临时变量存储cur，并free(cur)，之后通过临时变量访问该地址，就像将房卡给别人，退房后还是不能使用该房间。
//错误范例1
void SLTDestroy2(SLTNode** pphead)
{assert(pphead);SLTNode* cur = *pphead;while (cur){free(cur);//此时cur已经是野指针了，下面不能在调用了cur = cur->next;}*pphead = NULL;
}
//错误范例2
void SLTDestroy2(SLTNode** pphead)
{assert(pphead);SLTNode* cur = *pphead;while (cur){SLTNode* tmp = cur->next;free(tmp);//此时tmp已经是野指针了，下面不能在调用了cur = tmp->next;}*pphead = NULL;
}
总结
写代码时几个注意的点：
- 指针不一定要断言，只有一定不为空的指针才需要断言，具体情况具体分析；
- 要有封装的思想，多次使用的功能封装为函数；
- 在实际应用中，头插、尾插不一定要调用函数；
- 代码有不同的实现逻辑和方式，注意区分差别；
- 野指针问题经常出现，注意规避；
- 出现问题进行调试，观察出错步骤，进行修改。
上面的代码即思想在做链表相关的题时很有用，希望大家可以动手写一写~
