数据结构（单链表（2））
单链表的实现
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;
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
为了方便后期测试查看结果，我们先创建一个打印单链表的代码：
void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;
while (pcur)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}与此同时的，还需要创建一个新结点以便后续的增删查补操作：
//申请新节点
SLTNode* SLTBuyNode(SLTDataType x)
{
SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
if (node == NULL)
{
perror("malloc fail!");
exit(1);
}
node->data = x;
node->next = NULL;
return node;
}
后插与前插操作
特别要注意的是，传参时应该传递的是地址而不是单纯的值。
//后插操作
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//pphead --> &plist
// *pphead --> plist
//申请新节点
SLTNode* newnode = SLTBuyNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//找尾结点
SLTNode* pcur = *pphead;
while (pcur->next)
{
pcur = pcur->next;
}
//pcur newnode
pcur->next = newnode;
}
}
//前插操作
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
//newnode *pphead
newnode->next = *pphead;
*pphead = newnode;
}后删与前删操作
//从后删除操作
void SLTPopBack(SLTNode** pphead)
{
//链表为空：不可以删除
assert(pphead && *pphead);
//处理只有一个结点的情况:要删除的就是头结点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
//找 prev ptail
SLTNode* ptail = *pphead;
SLTNode* prev = NULL;
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;
//*pphead --> next
free(*pphead);
*pphead = next;
}查找相应结点
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
assert(phead);
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);
assert(pos);
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* newnode = SLTBuyNode(x);
//找prev :pos的前一个结点
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//prev newnode --> pos
newnode->next = pos;
prev->next = newnode;
}
}
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
//pos newnode --> pos->next
newnode->next = pos->next;
pos->next = newnode;
}指定位置前后删除结点
//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && *pphead);
assert(pos);
//头删
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//prev pos pos->next
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{
assert(pos && pos->next);
//pos pos->next pos->next->next
SLTNode* del = pos->next;
pos->next = pos->next->next;
free(del);
del = NULL;
}销毁链表
此步骤能有效释放空间
//销毁链表
void SListDestroy(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}test.c
测试文件时，我们仅需声明头文件SList.h,并调用一个main函数即可。
结尾
以上便是单链表的实现过程，初学写作可能有部分地方没有解释清楚，欢迎各位专业人士前来批判指正，万分感谢！
原文地址：https://blog.csdn.net/2406_83947720/article/details/140420341
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！