文章目录

• 一、链表概念结构及定义
• 二、链表分类
• 三、单链表实现逻辑
• • （1）创建结构体
  • （2）具体函数实现及解析
  • • （*）动态申请一个节点
    • （*）单链表打印
    • （*）单链表尾插
    • （*）单链表的头插
    • （*）单链表的尾删
    • （*）单链表头删
    • （*）单链表查找
    • （*）单链表在pos位置之前插入x
    • （*）单链表在pos位置之后插入x
    • （*）删除pos位置之后的值
    • （*）单链表删除pos位置的值
    • （*）单链表的销毁
  • （3）函数对比和摒弃
• 四、单链表实现代码
• • （1）Slist.c
  • （2）Slist.h
  • （3）test.c
• 五、单链表测试结果

一、链表概念结构及定义

单链表是一种链式存取的，物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。链表的数据是以结点来表示，每个结点的构成是元素+指针。
元素：是存储数据的存储单元
指针：是连接每个结点的地址数据

• 从上图结构可以看到，链式结构再逻辑上是连续的，再物理上不一定连续
• 现实中的结点一般都是从堆上申请出来的
• 从堆上申请的空间，是按照一定策略来分配，两次申请的空间可能连续，也可能不连续。
  C语言结构定义：

typedef int DataType//便于改类型
typedef struct Node
{DataType data；//结点的数据域struct Node* next；//结点的指针域
}LTNode；

二、链表分类

链表的结构非常多样，以下情况组合起来就有8种链表结构：
（1）单向或者双向：

（2）带头或者不带头：

（3）循环或者非循环：
（4）无头单向非循环和带头双向循环链表：

我们实际中最常用的是这两种结构：
1、无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单。
而今天实现是无头单向非循环链表

三、单链表实现逻辑

（1）创建结构体

typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SLTNode;

先使用typedef int SLTDateType是为了方便更改数据类型，因为链表是以结点表示的，所以在结构体里创建2个变量来表示结点SLTDateType data;
struct SListNode* next;，分别表示结点的数据域和指针域
数据域是存放数据的
指针域是存放的是下一个结点的地址

（2）具体函数实现及解析

（*）动态申请一个节点

SLTNode* BuySListNode(SLTDateType x)//动态申请节点
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");}newnode->data = x;newnode->next = NULL;return newnode;
}

动态申请结点，那函数返回的应该是一个指针类型，用malloc开辟一个SLTNode大小的空间，并用newnode指向这个空间，再判断是否为空，如为空就perror，显示错误信息。反之则把要存的数据x存到newnode指向的空间里面，把指针置为空。

（*）单链表打印

void SListPrint(SLTNode* plist)//打印链表
{SLTNode* cur = plist;while (cur){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}

因为当前的指针是变化的，所以先把头指针存到定义的cur里面，在来一个while循环，终止条件是cue为空，里面是先用printf函数打印值，再更新cur。

（*）单链表尾插

void SListPushBack(SLTNode** pplist, SLTDateType x)// 单链表尾插
{assert(pplist);SLTNode* newnode=BuySListNode(x);if (*pplist == NULL){*pplist = newnode;}else{SLTNode* tail = *pplist;while (tail->next){tail = tail->next;}tail->next = newnode;}
}

这里所用的是二级指针pplist，因为它在程序里面需要改变，这样传参传指针的地址的才能改变，而接收就要用二级指针。

尾插先用assert断言一下指针，用来检测异常情况，来提供警告信息并退出程序，再申请结点并用newnode指向，尾插有两种情况当头指针的为空，就把刚申请的结点赋给头指针，否则进行尾插尾插，先把头指针赋给定义的为指针，再用while循环来找尾部，直到为空停止，最用tail->next来链接刚申请的结点

（*）单链表的头插

void SListPushFront(SLTNode** pplist, SLTDateType x)//单链表的头插
{assert(pplist);SLTNode* newnode = BuySListNode(x);newnode->next = *pplist;*pplist=newnode;
}

头插直接就是插，不用找尾，先申请结点，再next链接头结点，即连到前面，在更新头指针，以方便下一次连接。

（*）单链表的尾删

void SListPopBack(SLTNode** pplist)//单链表的尾删
{assert(pplist);assert(*pplist);if (*pplist == NULL){free(*pplist);*pplist = NULL;}SLTNode* tail = *pplist;while (tail->next->next){tail = tail->next;}free(tail->next);tail->next = NULL;}

尾删先找尾，如果头指针为空直接释放，并置指针为空，以防止成为野指针，再把头指针赋给定义的为指针，用while循环找尾部，用tail的下下个结点来判断，如果为空就是放下个结点，并置下个结点为空。

（*）单链表头删

void SListPopFront(SLTNode** pplist)//单链表头删
{assert(pplist);assert(*pplist != NULL);SLTNode* next = (*pplist)->next;free(*pplist);*pplist = next;
}

先把头指针下个结点地址存放到定义的next指针里面，再释放头指针，最后更新头指针。

（*）单链表查找

SLTNode* SListFind(SLTNode* plist, SLTDateType x)// 单链表查找
{SLTNode* cur = plist;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

查找也是一个当前指针发生变化的过程，先把头指针存到定义的cur指针里面，再用while来查找，用if语句来判断，如果找到直接返回cur指针，没有则更新当前指针，遍历下一个。最后都没有返回空。

（*）单链表在pos位置之前插入x

void SListInsertFront(SLTNode** plist, SLTNode* pos, SLTDateType x)// 单链表在pos位置之前插入x
{assert(plist);assert(pos);if (*plist == pos){SListPushFront(plist, x);}else{SLTNode* pre = *plist;while (pre->next != pos){pre = pre->next;}SLTNode* newnode = BuySListNode(x);pre->next=newnode;newnode->next = pos;}
}

在pos位置之前插入，分两种情况，第一头指针正好是pos，直接调用头插，否则进行二种情况，多个结点：先把头指针存放到定义的前驱指针pre，再用while循环来找pos，不等于pos更新pre继续找，找到之后先申请一个要插入的结点，再用前驱指针pre来链接刚申请的结点，然后申请的结点再链接pos。

（*）单链表在pos位置之后插入x

void SListInsertAfter(SLTNode * pos, SLTDateType x)//单链表在pos位置之后插入x
{assert(pos);SLTNode* newnode = BuySListNode(x);SLTNode* next = pos->next;pos->next = newnode;newnode->next = next;}

这个函数要结合查找函数来用。在这里面先申请结点，再把pos下个结点地址存放到next里面，再用pos来连接刚申请的结点，之后再用刚申请的结点来链接next也即是pos下一个的结点。

（*）删除pos位置之后的值

void SListEraseAfter(SLTNode* pos)//删除pos位置之后的值
{assert(pos);if (pos == NULL){return;}SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;}

先判断pos是否为空，如是则return终止函数执行，反之先把pos之后的结点地址存到del指针里面，然后直接让pos链接del的下一个结点，再释放掉中间的del。

（*）单链表删除pos位置的值

void SListErase(SLTNode** plist, SLTNode* pos)// 单链表删除pos位置的值
{assert(plist);assert(pos);if (*plist == pos){free(*plist);*plist = NULL;}else{SLTNode* pre = *plist;while (pre->next!= pos){pre = pre->next;}pre->next = pos->next;free(pos);pos= NULL;}
}

删除pos位置的值，如果头指针刚好是直接释放头指针并置为空，否则，把头指针赋给前驱指针，再用while循环找pos，找到则pre直接链接pos下一个结点，并释放掉中间的pos，并置为空。

（*）单链表的销毁

void SListDestroy(SLTNode** plist)// 单链表的销毁
{assert(plist);SLTNode* tail = *plist;while (*plist){while (tail){tail = tail->next;}free(tail);tail = NULL;}
}

释放链表，先从尾部进行逐个删除，把头指针赋给定义的尾指针，再用两个while循环来控制，第一层是控制头指针，第二层是控制为尾指针，找到则释放并置为空，然后直到头指针为空则停止。

（3）函数对比和摒弃

我们需要摒弃 单链表在pos位置之前插入x函数和单链表删除pos位置的值函数。
原因和对比：

• 摒弃pos之前插入：因为是单向链表，需要从头遍历查找pos，如果在pos之前插入，找到pos还需要找pos之前的地址，对传参数不友好，所以一般再pos之后插入
• 摒弃删除pos位置：因为是单向链表，需要从头遍历查找pos，如果删除pos位置，找到pos还需要找pos之前的地址，对传参数不友好，而且这样就少传参数了，所以一般不删除pos，一般删除pos后面的值。

四、单链表实现代码

（1）Slist.c

#include"Slist.h"
SLTNode* BuySListNode(SLTDateType x)//动态申请节点
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");}newnode->data = x;newnode->next = NULL;return newnode;
}
void SListPrint(SLTNode* plist)//打印链表
{SLTNode* cur = plist;while (cur){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}
void SListPushBack(SLTNode** pplist, SLTDateType x)// 单链表尾插
{assert(pplist);SLTNode* newnode=BuySListNode(x);if (*pplist == NULL){*pplist = newnode;}else{SLTNode* tail = *pplist;while (tail->next){tail = tail->next;}tail->next = newnode;}
}
void SListPushFront(SLTNode** pplist, SLTDateType x)//单链表的头插
{assert(pplist);SLTNode* newnode = BuySListNode(x);newnode->next = *pplist;*pplist=newnode;
}
void SListPopBack(SLTNode** pplist)//单链表的尾删
{assert(pplist);assert(*pplist);if (*pplist == NULL){free(*pplist);*pplist = NULL;}SLTNode* tail = *pplist;while (tail->next->next){tail = tail->next;}free(tail->next);tail->next = NULL;}
void SListPopFront(SLTNode** pplist)//单链表头删
{assert(pplist);assert(*pplist != NULL);SLTNode* next = (*pplist)->next;free(*pplist);*pplist = next;
}
SLTNode* SListFind(SLTNode* plist, SLTDateType x)// 单链表查找
{SLTNode* cur = plist;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}
void SListInsertFront(SLTNode** plist, SLTNode* pos, SLTDateType x)// 单链表在pos位置之前插入x
{assert(plist);assert(pos);if (*plist == pos){SListPushFront(plist, x);}else{SLTNode* pre = *plist;while (pre->next != pos){pre = pre->next;}SLTNode* newnode = BuySListNode(x);pre->next=newnode;newnode->next = pos;}
}
void SListInsertAfter(SLTNode * pos, SLTDateType x)//单链表在pos位置之后插入x
{assert(pos);SLTNode* newnode = BuySListNode(x);SLTNode* next = pos->next;pos->next = newnode;newnode->next = next;}
void SListEraseAfter(SLTNode* pos)//删除pos位置之后的值
{assert(pos);if (pos == NULL){return;}SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;}
void SListErase(SLTNode** plist, SLTNode* pos)// 单链表删除pos位置的值
{assert(plist);assert(pos);if (*plist == pos){free(*plist);*plist = NULL;}else{SLTNode* pre = *plist;while (pre->next!= pos){pre = pre->next;}pre->next = pos->next;free(pos);pos= NULL;}
}
void SListDestroy(SLTNode** plist)// 单链表的销毁
{assert(plist);SLTNode* tail = *plist;while (*plist){while (tail){tail = tail->next;}free(tail);tail = NULL;}
}

（2）Slist.h

#pragma once
#include
#include
#include
typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SLTNode;
SLTNode* BuySListNode(SLTDateType x);// 动态申请一个节点//SLTNode* CreateSList(int n);//创建链表void SListPrint(SLTNode* plist); 单链表打印void SListPushBack(SLTNode** pplist, SLTDateType x);// 单链表尾插void SListPushFront(SLTNode** pplist, SLTDateType x);///单链表的头插void SListPopBack(SLTNode** pplist); //单链表的尾删void SListPopFront(SLTNode** pplist);//单链表头删SLTNode* SListFind(SLTNode* plist, SLTDateType x);// 单链表查找void SListInsertFront(SLTNode** plist, SLTNode* pos,SLTDateType x);// 单链表在pos位置之前插入xvoid SListInsertAfter(SLTNode * pos,SLTDateType x); //单链表在pos位置之后插入xvoid SListEraseAfter(SLTNode* pos);//删除pos位置之后的值void SListErase(SLTNode** plist, SLTNode* pos);// 单链表删除pos位置的值void SListDestroy(SLTNode* plist);// 单链表的销毁

（3）test.c

#include"Slist.h"
void test1()
{SLTNode* plist = NULL;SListPushBack(&plist, 1);//尾插测试SListPushBack(&plist, 2);SListPushBack(&plist, 3);SListPushBack(&plist, 4);SListPrint(plist);}
void test2()
{SLTNode* plist = NULL;SListPushFront(&plist, 1);//头插+尾删+头删测试SListPushFront(&plist, 2);SListPushFront(&plist, 3);SListPushFront(&plist, 4);SListPopBack(&plist);SListPopFront(&plist);SListPrint(plist);}
void test3()
{SLTNode* plist = NULL;SListPushBack(&plist, 1);SListPushBack(&plist, 2);SListPushBack(&plist, 3);SListPushBack(&plist, 4);SListPrint(plist);SLTNode* ret = SListFind(plist, 3);if (ret){printf("%d\n",ret->data);}SLTNode* pos = SListFind(plist, 4);if (pos){SListInsertFront(&plist, pos, 5);}SListPrint(plist);pos = SListFind(plist, 5);if (pos){SListErase(&plist, pos);}SListPrint(plist);
}
int main()
{test1();//尾插测试test2();//头插+尾删+头删测试test3();//尾插+查找+在pos位置之前插入x+单链表删除pos位置的值}

五、单链表测试结果