数据结构——单链表（附图文讲解 | 超详细）

文章目录

• • 一、前言
  • 二、单链表
  • • 2.1 定义
    • • 特点
    • 2.2 单链表的实现
    • • 2.2.1 准备工作
      • 2.2.1 单链表的功能接口
      • • 1.创建一个单链表
        • 2.销毁单链表
        • 3.单链表的打印
        • 4.节点的创建
        • 5.单链表的增加功能接口
        • 6.单链表的删除功能接口
        • 7.单链表的查找实现接口
  • 三、总代码
  • • SList.h
    • SList.c
    • test.c

一、前言

这篇博客将从全面讲解数据结构中的单链表

二、单链表

2.1 定义

概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表由一系列节点组成，每个节点包含两部分：数据域和指针域。数据域用于存储实际的数据，而指针域则存储指向链表中下一个节点的地址。在单链表中，除了最后一个节点外，每个节点的指针域都指向下一个节点，最后一个节点的指针域通常设置为NULL，以标识链表的结束。单链表的特点是其存储不需要连续的内存空间，节点可以分散在内存中的任意位置，通过指针连接形成线性结构。

特点

2.2 单链表的实现

2.2.1 准备工作

先创建三个文件

解释这三个文件的作用
1. 头文件SList.h是来声明接口函数，定义单链表，将几个公共用到的库函数集合起来
2. 源文件SList.c是用来具体实现接口
3. 源文件test.c用于接口的测试工作 ，即具体的使用场景

2.2.1 单链表的功能接口

1.创建一个单链表

//单链表
typedef int SLTDataType; //自定义数据元素类型
typedef struct SListNode
{
SLTDataType data; //数据域 存储的数据
struct SListNode* next; //指针域 指向下一个结点
}SLTNode;

2.销毁单链表

//销毁链表
void SListDestroy(SLTNode** pphead)
{
SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}

3.单链表的打印

//链表的打印
void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;
while (pcur)
{
printf("%d -> ", pcur->data);
pcur = pcur->next;
//对pcur解引用拿到next指针变量中的地址（下一个节点的地址）
//赋值给pucr，此时pcur保存的地址为下一个节点的地址，即pcur“指向了下一个节点”
}
printf("NULL\\n");
}

4.节点的创建

单链表的每次增加都涉及到节点的创建

//节点的创建
SLTNode* SLTbuyNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;

return newnode;
}

5.单链表的增加功能接口

5.1 尾插接口

若链表为空则直接创建一个节点作为链表，若不为空则将最后一个节点的指针域改成新建的节点的指针

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTbuyNode(x);
//链表为空
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//找尾
SLTNode* ptail = *pphead;
while (ptail->next)
{
ptail = ptail->next;
}
ptail->next = newnode;
}
}

5.2 头插接口

将第一个节点的地址赋值给新建的节点的指针域，再将链表头指向新建节点的地址

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTbuyNode(x);
newnode->next = *pphead;
*pphead = newnode;
}

5.3 指定位置之前插入接口

若指定位置是第一个位置，则用头插的方法，若不是第一个位置，则将prev的指针域改成新建的节点的地址，再将新建的节点的指针域改成pos的地址

//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead && pos);
//当pos指向第一个结点，是头插
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* newnode = SLTbuyNode(x);
//找pos的前一个结点
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = newnode;
newnode->next = pos;
}
}

5.4 指定位置之后插入接口

先将pos中指针域中的地址（指定位置之后一位的地址）给新建的节点的指针域，再将新建的节点的地址赋值给pos中的指针域

//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = SLTbuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}

6.单链表的删除功能接口

6.1 尾删接口

若只有一个节点，则将这个节点销毁，若不止一个，则将倒数第二个节点的指针域中的地址赋为NULL，再将最后一个节点销毁

//尾删
void SLTPopBack(SLTNode** pphead)
{
assert(pphead && *pphead);
//只有一个结点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* prev = NULL;
SLTNode* ptail = *pphead;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
prev->next = NULL;
free(ptail);
ptail = NULL;
}
}

6.2 头删接口

先将链表头指向第二个节点，再将第一个节点销毁

//头删
void SLTPopFront(SLTNode** pphead)
{
assert(pphead && *pphead);

SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}

6.3 删除指定位置接口

先将prev位置的节点中的指针域改成pos位置的节点中的指针域中的地址（pos下一个位置的节点地址），再将pos位置的节点销毁

//删除指定位置结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && pos);
//pos就是头结点
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}

6.4 删除指定位置之后接口

先将pos的指针域中的地址（指定位置之后的节点地址）保存起来，再将指定位置节点中的指针域中的地址（指定位置后两位节点的地址）赋给pos位置节点的指针域，最后将指定位置的节点销毁

//删除指定位置之后的结点
void SLTEraseAfter(SLTNode* pos)
{
assert(pos && pos->next);
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}

7.单链表的查找实现接口

一个一个进行比对

//单链表的查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* pcur = phead;
while (pcur)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}

三、总代码

SList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//定义链表的结构—结点的结构
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;//存储的数据
struct SListNode* next; //指向下一个结点
}SLTNode;

//typedef struct SListNode SLTNode;

//链表的打印
void SLTPrint(SLTNode* phead);

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos);

//销毁链表
void SListDestroy(SLTNode** pphead);

SList.c

#include"SList.h"
//链表的打印
void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;
while (pcur)
{
printf("%d -> ", pcur->data);
pcur = pcur->next;
}
printf("NULL\\n");
}

SLTNode* SLTbuyNode(SLTDataType x)
{
//根据x创建节点
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;

return newnode;
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTbuyNode(x);
//链表为空
if (*pphead == NULL)
{
*pphead = newnode;
}
else {
//找尾
SLTNode* ptail = *pphead;
while (ptail->next)
{
ptail = ptail->next;
}
ptail->next = newnode;
}
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTbuyNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
//尾删
void SLTPopBack(SLTNode** pphead)
{
assert(pphead && *pphead);
//只有一个结点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else {
SLTNode* prev = NULL;
SLTNode* ptail = *pphead;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
prev->next = NULL;
free(ptail);
ptail = NULL;
}
}
//头删
void SLTPopFront(SLTNode** pphead)
{
assert(pphead && *pphead);

SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* pcur = phead;
while (pcur)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead && pos);
//当pos指向第一个结点，是头插
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else {
SLTNode* newnode = SLTbuyNode(x);
//找pos的前一个结点
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = newnode;
newnode->next = pos;
}
}
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = SLTbuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}

//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && pos);
//pos就是头结点
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else {
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{
assert(pos && pos->next);
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}

//销毁链表
void SListDestroy(SLTNode** pphead)
{
SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}

test.c

#include"SList.h"

void test01()
{
SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));

node1->data = 1;
node2->data = 2;
node3->data = 3;
node4->data = 4;

node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = NULL;

SLTNode* plist = node1;
SLTPrint(plist);
}

void test02()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
//SLTPushFront(&plist, 1);
//SLTPushFront(&plist, 2);
//SLTPushFront(&plist, 3);
//SLTPushFront(&plist, 4);
//SLTPrint(plist);
//SLTPushFront(NULL, 4);
//SLTPopBack(&plist);
//SLTPrint(plist);
//SLTPopBack(&plist);
//SLTPrint(plist);
//SLTPopBack(&plist);
//SLTPrint(plist);
//SLTPopBack(&plist);
//SLTPrint(plist);
//
//SLTPopBack(&plist);
//SLTPopFront(&plist);
//SLTPrint(plist);
//SLTPopFront(&plist);
//SLTPrint(plist);
//SLTPopFront(&plist);
//SLTPrint(plist);
//SLTPopFront(&plist);
//SLTPrint(plist);
//
//SLTPopFront(&plist);

SLTNode* find = SLTFind(plist, 4);

//SLTInsert(&plist, find, 100);//1 2 3 100 4
//SLTInsertAfter(find, 100);//1 100 2 3 4
//SLTErase(&plist, find);
//SLTEraseAfter(find);//1 3 4
//SLTPrint(plist);

SListDestroy(&plist);
}

int main()
{
test01();
test02();

return 0;
}