【数据结构】单链表的接口实现（附图解和源码）

单链表的接口实现（附图解和源码）

---

---

前言

本文主要介绍单链表中增删查改等接口实现，结尾附总源码！

---

一、定义结构体

代码如下（示例）：

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

二、接口实现（附图解+源码）

这里一共11个接口，我会我都会一 一为大家讲解（图解+源码）

---

1.开辟新空间

(1)开辟一个链表类型的动态空间，将地址赋给指针newnode；
(2)将值放入newnode的data数据内；
(3)将新成员的next指针置为空指针，因为这个成员将成为链表的最后一个成员
注意：1.将malloc开辟空间存到newnode里面时，参数为结构体所占的字节大小！2.对newnode进行NULL判断！

代码如下（示例）：

SLTNode* BuyListNode(SLTDataType x)//开辟新空间
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//开辟一个链表类型的动态空间 将地址赋给指着newnodeif (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->data = x;//将值放入newnode的data数据内newnode->next = NULL;//将新成员的next指针 置为空指针 因为这个成员将称为链表的最后一个成员
}

---

2.头插数据

注意：头插接口传参的时候一定要传二级指针变量，如果传一级指针就不会实现效果，如下图！

---

代码如下（示例）：

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

---

3.头删数据

头删数据注意：当单链表为空指针NULL时，头删时会对空指针进行解引用，会造成err，所以要进行两步assert断言！

---

图解实现：这里传参也需要传二级指针！

---

代码如下（示例）：

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

---

4.打印整个单链表

注意：这里传参用一级指针即可，因为不需要对结构体进行修改访问！

---

代码如下（示例）：

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

---

5.尾删数据

注意：分为两种情况 1.只有一个链表；2.存在两个及以上链表！

只有一个链表 ：如下（示例）：

if ((*pphead)->next == NULL)//如果第一个链表的next指针存放的是空指针 说明只有一个链表{free(*pphead);//将唯一一个链表的动态内存释放*pphead = NULL;//将指针置为空指针}

---

两个或两个以上链表 ： 如下（示例）：
第一种情况 ： 定义两个指针情况！

//定义2个指针方法SLTNode* tail = *pphead;//寻找当前需要被释放的地址 所创建的变量SLTNode* prev = *pphead;//删除最后一个链表数据后，所保留的最后一个链表的地址。while (tail->next != NULL){prev = tail;tail = tail->next;}//当循环停下来时 prev指针指向的是 tail前面的一个链表  而此时tail->next 指针指向的地址是NULLfree(tail);//释放最后一个链表对应的动态内存tail = NULL;//将最后一个链表指针置为空指针prev->next = NULL;//尾删最重要的是记得要把被删除链表的前一个链表的next指针存放地址置为空指针,避免野指针的情况。

---

两个或两个以上链表 ： 如下（示例）：
第二种情况 ： 定义一个指针情况！

//定义一个指针方法
//来到这说明至少有两个链表SLTNode* tail = *pphead;//将链表地址交给tail指针while (tail->next->next)//当tail指向的地址的地址不是空指针则继续循环{tail = tail->next;//在循环中tail拿到下一个tail的next指针地址}free(tail->next);//tail指向的next地址的动态空间被释放tail->next = NULL;//tail指向的next指针被置为空指针

---

6.查找单链表中的数据

单链表中查找数据和顺序表里面的查找顺序非常相似，这里不做过多介绍，如果找不到返回NULL

代码如下（示例）：

SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}else{cur = cur->next;}}return NULL;
}

---

7.在pos位置之前插入一个节点

第一种情况（pos就是*pphead）代码如下（示例）：

if (*pphead == pos){newnode->next = *pphead;*pphead = newnode;}

---

第二种情况（pos 不是*pphead）代码如下（示例）：

else
{//找到pos前一个链表地址SLTNode* posPrev = *pphead;while (posPrev->next != pos){posPrev = posPrev->next;}posPrev->next = newnode;newnode->next = pos;
}

---

8.在pos位置之后插入一个节点

---

代码如下（示例）：

void SListInserAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuyListNode(x);newnode->next = pos->next;pos->next = newnode;
}

---

9.删除pos节点

注意：这里分为两种情况：1.pos==*pphead；2.pos 不等于 * pphead

第一种情况 pos==*pphead，这里相等于头删 ：

if (*pphead == pos){//头删*pphead = pos->next;free(pos);}

---

第二种情况 pos 不等于 *pphead ：

else
{//找前一个SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;
}

---

10.删除pos的下一个节点

注意：如果链表为空，则不能删除，否则会对空指针进行访问！所以也需要进行两步assert断言！

代码如下（示例）：

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

---

11.销毁单链表

很多人都是用free直接销毁，这样会导致内存泄漏问题(因为单链表不是连续存放的），如下图所示！

---

代码如下（示例）：

void SListDestroy(SLTNode** pphead)
{assert(pphead);while (*pphead){SLTNode* tmp = (*pphead)->next;free(*pphead);*pphead = tmp;}*pphead = NULL;
}

---

三、源代码展示

1.test.c（测试+主函数）

代码如下（示例）：

#include "Slist.h"
void TestSList1()
{SLTNode* plist = NULL;SListPushBack(&plist, 1);//尾插SListPushBack(&plist, 2);//尾插SListPushBack(&plist, 3);//尾插SListPushBack(&plist, 4);//尾插SListPushFront(&plist, 5);//头插SListPopFront(&plist);//头删SListPopBack(&plist);//尾删SListPopBack(&plist);//尾删SListPopBack(&plist);//尾删SListPopBack(&plist);//尾删SListPopFront(&plist);//头删SListPrint(plist);//打印
}void TestSList2()
{SLTNode* plist = NULL;SListPushBack(&plist, 1);//尾插SListPushBack(&plist, 2);//尾插SListPushBack(&plist, 1);//尾插SListPushBack(&plist, 3);//尾插SListPushBack(&plist, 4);//尾插SListPushBack(&plist, 1);//尾插SListPushFront(&plist, 5);//头插SListPopFront(&plist);//头删SListPrint(plist);//打印
}
void TestSList3()
{SLTNode* plist = NULL;SListPushBack(&plist, 1);//尾插SListPushBack(&plist, 2);//尾插SListPushBack(&plist, 1);//尾插SListPushBack(&plist, 3);//尾插SListPushBack(&plist, 4);//尾插SListPushBack(&plist, 1);//尾插SListPushFront(&plist, 5);//头插SLTNode* pos = SListFind(plist, 1);int i = 1;while (pos){printf("第%d个pos节点:%p->%d\n", i++, pos, pos->data);pos = SListFind(pos->next, 1);}pos = SListFind(plist, 4);if (pos){pos->data = 30;}SListPrint(plist);
}void TestSList4()
{SLTNode* plist = NULL;SListPushBack(&plist, 2);//尾插SListPushBack(&plist, 3);//尾插SListPushBack(&plist, 4);//尾插SListPushBack(&plist, 5);//尾插SListPushBack(&plist, 6);//尾插SListPushFront(&plist, 1);//头插//SLTNode* pos = SListFind(plist, 6);//SListInserAfter(pos, 1);//SListInsert(&plist, pos, 7);//SListErase(&plist, pos);SListDestroy(&plist);SListPrint(plist);
}
int main()
{//TestSList1();//TestSList2();//TestSList3();TestSList4();return 0;
}

---

2.Slist.h（接口函数的声明）

代码如下（示例）：

#pragma onc
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;void SListPrint(SLTNode* phead);//打印
void SListPushBack(SLTNode** pphead, SLTDataType x);//尾插
void SListPushFront(SLTNode** pphead, SLTDataType x);//头插
void SListPopBack(SLTNode** pphead);//尾删
void SListPopFront(SLTNode** pphead);//头删
SLTNode* SListFind(SLTNode* phead, SLTDataType x);//找数据
//在pos位置前插入一个节点
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos位置之后去插入一个节点
void SListInserAfter(SLTNode* pos, SLTDataType x);
void SListErase(SLTNode** pphead, SLTNode* pos);//删除pos节点
void SListEraseAfter(SLTNode* pos);//删除pos的下一个节点
void SListDestroy(SLTNode** pphead);

---

3.Slist.c（接口函数的实现）

代码如下（示例）：

#include "Slist.h"
SLTNode* BuyListNode(SLTDataType x)//开辟新空间
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//开辟一个链表类型的动态空间 将地址赋给指着newnodeif (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->data = x;//将值放入newnode的data数据内newnode->next = NULL;//将新成员的next指针 置为空指针 因为这个成员将称为链表的最后一个成员
}
void SListPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}
void SListPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuyListNode(x);if (*pphead == NULL){*pphead = newnode;//如果*pphead是空指针 将 newnode的地址给与 *pphead 称为链表的第一个成员}else{//如果链表已经不是空的了 *pphead那么肯定也不是NULL空指针则进入这里SLTNode* tail = *pphead;//用一个tail指针 接收链表地址while (tail->next != NULL)//while寻找链表的最后成员{tail = tail->next;//循环直至找到最后一个链表的成员}tail->next = newnode;//最后一个成员取得新链表成员地址}
}
void SListPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuyListNode(x);newnode->next = *pphead;*pphead = newnode;
}
void SListPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead != NULL);//仿C++处理错误的方式//来到这说明至少有一个链表  或 两个以上链表if ((*pphead)->next == NULL)//如果第一个链表的next指针存放的是空指针 说明只有一个链表{free(*pphead);//将唯一一个链表的动态内存释放*pphead = NULL;//将指针置为空指针}else{//定义2个指针方法SLTNode* tail = *pphead;//寻找当前需要被释放的地址 所创建的变量SLTNode* prev = *pphead;//删除最后一个链表数据后，所保留的最后一个链表的地址。while (tail->next != NULL){prev = tail;tail = tail->next;}//当循环停下来时 prev指针指向的是 tail前面的一个链表  而此时tail->next 指针指向的地址是NULLfree(tail);//释放最后一个链表对应的动态内存tail = NULL;//将最后一个链表指针置为空指针prev->next = NULL;//尾删最重要的是记得要把被删除链表的前一个链表的next指针存放地址置为空指针,避免野指针的情况。//定义一个指针方法//来到这说明至少有两个链表//SLTNode* tail = *pphead;//将链表地址交给tail指针//while (tail->next->next)//当tail指向的地址的地址不是空指针则继续循环//{//	tail = tail->next;//在循环中tail拿到下一个tail的next指针地址//}//free(tail->next);//tail指向的next地址的动态空间被释放//tail->next = NULL;//tail指向的next指针被置为空指针}
}
void SListPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead != NULL);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}else{cur = cur->next;}}return NULL;
}
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuyListNode(x);if (*pphead == pos){newnode->next = *pphead;*pphead = newnode;}else{//找到pos前一个链表地址SLTNode* posPrev = *pphead;while (posPrev->next != pos){posPrev = posPrev->next;}posPrev->next = newnode;newnode->next = pos;}
}
//自己写的
void SListInserAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuyListNode(x);newnode->next = pos->next;pos->next = newnode;
}
void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);if (*pphead == pos){//头删*pphead = pos->next;free(pos);}else{//找前一个SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}
void SListEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);SLTNode* next = pos->next;pos->next = next->next;free(next);next = NULL;
}
void SListDestroy(SLTNode** pphead)
{assert(pphead);while (*pphead){SLTNode* tmp = (*pphead)->next;free(*pphead);*pphead = tmp;}*pphead = NULL;
}

---

总结

以上就是今天要讲的内容，本文介绍了单链表11种接口的模拟实现的图解+源代码
如果我的博客对你有所帮助记得三连支持一下，感谢大家的支持！