单链表（增删查改）

一、什么是单链表？

单链表是一种链式存取的数据结构，，链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。以“结点的序列”表示的线性表称作线性链表（单链表），单链表是链式存取的结构。简单来说单链表就是一个一个的节点链接起来的链式结构，每个节点里面存储着一个数据和与它链接的下一个节点的（指针）地址。（注意，每一个节点都是同一种结构体类型）

二、单链表的增删查改

2.1 结构体变量的声明

typedef int SLTDataType;
typedef struct SLTNode
{SLTDataType data;struct SLTNode* next;}SLTNode;

2.2 申请新结点

SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));if (newNode == NULL){perror("malloc fail");return NULL;}else{newNode->data = x;newNode->next = NULL;return newNode;}
}

2.2 链表的头插

void SListPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newNode = BuySListNode(x);newNode->next = *pphead;*pphead = newNode;
}

2.3 链表的尾插

void SListPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newNode = BuySListNode(x);if (*pphead == NULL){*pphead = newNode;}else{SLTNode* tail = *pphead;while (tail->next){tail = tail->next;}tail->next = newNode;}}

2.4 链表的头删

void SListPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* del = *pphead;*pphead = (*pphead)->next;free(del);del = NULL;}

2.5 链表的尾删

void SListPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tailPrev = NULL;SLTNode* tail = *pphead;while (tail->next){tailPrev = tail;tail = tail->next;}tailPrev->next = NULL;free(tail);tail = NULL;}}

2.6 链表的查找

SLTNode* SListFind(SLTNode* pphead, SLTDataType x)
{SLTNode* cur = pphead;while (cur){if (cur->data == x){return cur;}else{cur = cur->next;}}printf("找不到%d\n",x);return NULL;}

2.7 链表的任意位置后面插入

void SListInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newNode = BuySListNode(x);SLTNode* posNext = pos->next;pos->next = newNode;newNode->next = posNext;}

2.8 链表的任意位置后面删除

void SListEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* posNext = pos->next;pos->next = posNext->next;free(posNext);posNext = NULL;}

2.9 链表的销毁

//建议传二级指针，因为销毁的话需要把这个指向链表的指针置空
//传一级指针无法把指向链表的指针置空
void SListDestroy(SLTNode** pphead)
{SLTNode* cur = *pphead;while (cur){SLTNode* del = cur;cur = cur->next;free(del);del = NULL;}*pphead = NULL;
}

2.10 链表的打印

void SListPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");}

三、代码汇总

3.1 SLish.h

#pragma once//SList.h#include <stdio.h>
#include <assert.h>
#include <stdlib.h>typedef int SLTDataType;
typedef struct SLTNode
{SLTDataType data;struct SLTNode* next;}SLTNode;// 动态申请一个节点
extern SLTNode* BuySListNode(SLTDataType x);
// 单链表打印
extern void SListPrint(SLTNode* phead);
// 单链表尾插
extern void SListPushBack(SLTNode** pphead, SLTDataType x);
// 单链表的头插
extern void SListPushFront(SLTNode** pphead, SLTDataType x);
// 单链表的尾删
extern void SListPopBack(SLTNode** pphead);
// 单链表头删
extern void SListPopFront(SLTNode** pphead);
// 单链表查找
extern SLTNode* SListFind(SLTNode* pphead, SLTDataType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
extern void SListInsertAfter(SLTNode* pos, SLTDataType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
extern void SListEraseAfter(SLTNode* pos);
// 单链表的销毁
extern void SListDestroy(SLTNode** pphead);

3.2 SLish.c

#define _CRT_SECURE_NO_WARNINGS 1
//Slist.c#include "SList.h"SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));if (newNode == NULL){perror("malloc fail");return NULL;}else{newNode->data = x;newNode->next = NULL;return newNode;}
}void SListPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");}void SListPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newNode = BuySListNode(x);if (*pphead == NULL){*pphead = newNode;}else{SLTNode* tail = *pphead;while (tail->next){tail = tail->next;}tail->next = newNode;}}void SListPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newNode = BuySListNode(x);newNode->next = *pphead;*pphead = newNode;
}void SListPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tailPrev = NULL;SLTNode* tail = *pphead;while (tail->next){tailPrev = tail;tail = tail->next;}tailPrev->next = NULL;free(tail);tail = NULL;}}void SListPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* del = *pphead;*pphead = (*pphead)->next;free(del);del = NULL;}SLTNode* SListFind(SLTNode* pphead, SLTDataType x)
{SLTNode* cur = pphead;while (cur){if (cur->data == x){return cur;}else{cur = cur->next;}}printf("找不到%d\n",x);return NULL;}void SListInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newNode = BuySListNode(x);SLTNode* posNext = pos->next;pos->next = newNode;newNode->next = posNext;}void SListEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* posNext = pos->next;pos->next = posNext->next;free(posNext);posNext = NULL;}void SListDestroy(SLTNode** pphead)
{SLTNode* cur = *pphead;while (cur){SLTNode* del = cur;cur = cur->next;free(del);del = NULL;}*pphead = NULL;
}

3.3 test.c

#define _CRT_SECURE_NO_WARNINGS 1
//test.c#include "SList.h"void test_SListPushBack(void)
{SLTNode* plist = NULL;SListPushBack(&plist, 1);SListPushBack(&plist, 2);SListPushBack(&plist, 3);SListPushBack(&plist, 4);SListPushBack(&plist, 5);SListPrint(plist);SLTNode* ret = SListFind(plist, 1);if (ret != NULL){printf("找到了，地址为：%p\n", ret);SListInsertAfter(ret, 6);SListPrint(plist);}ret = SListFind(plist, 1);if (ret != NULL){printf("找到了，地址为：%p\n", ret);SListInsertAfter(ret, 7);SListPrint(plist);}ret = SListFind(plist, 1);if (ret != NULL){printf("找到了，地址为：%p\n", ret);SListInsertAfter(ret, 8);SListPrint(plist);}ret = SListFind(plist, 1);if (ret != NULL){printf("找到了，地址为：%p\n", ret);SListInsertAfter(ret, 9);SListPrint(plist);}ret = SListFind(plist, 1);if (ret != NULL){printf("找到了，地址为：%p\n", ret);SListInsertAfter(ret, 10);SListPrint(plist);}/*SLTNode* ret = SListFind(plist, 1);if (ret != NULL){printf("找到了，地址为：%p\n", ret);SListEraseAfter(ret);SListPrint(plist);}ret = SListFind(plist, 1);if (ret != NULL){printf("找到了，地址为：%p\n", ret);SListEraseAfter(ret);SListPrint(plist);}ret = SListFind(plist, 1);if (ret != NULL){printf("找到了，地址为：%p\n", ret);SListEraseAfter(ret);SListPrint(plist);}ret = SListFind(plist, 1);if (ret != NULL){printf("找到了，地址为：%p\n", ret);SListEraseAfter(ret);SListPrint(plist);}*//*ret = SListFind(plist, 1);if (ret != NULL){printf("找到了，地址为：%p\n", ret);SListEraseAfter(ret);SListPrint(plist);}*///SListInsertAfter(ret, 8);/*SListPrint(plist);SListPopFront(&plist);SListPrint(plist);SListPopFront(&plist);SListPrint(plist); SListPopFront(&plist);SListPrint(plist); SListPopFront(&plist);SListPrint(plist); SListPopFront(&plist);SListPrint(plist);*/}void test_SListPushFront(void)
{SLTNode* plist = NULL;SListPushFront(&plist, 1);SListPushFront(&plist, 2);SListPushFront(&plist, 3);SListPushFront(&plist, 4);SListPushFront(&plist, 5);SListPrint(plist);SListPopFront(&plist);SListPrint(plist);SListPopFront(&plist);SListPrint(plist);SListPopFront(&plist);SListPrint(plist);SListPopFront(&plist);SListPrint(plist);SListPopFront(&plist);SListPrint(plist);/*SListPopFront(&plist);SListPrint(plist);*///SListDestroy(plist);//SListPrint(plist);/*SListPopBack(&plist);SListPrint(plist);SListPopBack(&plist);SListPrint(plist);SListPopBack(&plist);SListPrint(plist);SListPopBack(&plist);SListPrint(plist);SListPopBack(&plist);SListPrint(plist);*/}int main()
{//test_SListPushBack();test_SListPushFront();return 0;
}

以上就是有关单链表增删查改的全部内容了，你学会了吗？如果对你有帮助，点亮一下小心心，点点关注呗，后期会持续更新计算机相关知识哦！！！