单链表的实现
一.链表的概念及结构
二.链表的分类
链表的种类多种多样，彼此组合共有八种方式。
虽然链表结构多样，但最常使用的链表一般为以下两种，单链表和带头双向循环链表：
1.无头单向非循环链表：结构简单，⼀般不会单独⽤来存数据。实际种更多是作为其他数据结构的
子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。
2.带头双向循环链表：结构最复杂，⼀般⽤在单独存储数据。实际中使⽤的链表数据结构，都是带
头双向循环链表。但是这个结构虽然结构复杂，但是使⽤代码实现以后会发现结构会带来很多优
势，实现反而简单了，在下一篇博客我们将进行双向链表的实现。
三.单链表的实现
即不带头单向不循环链表的实现，主要相关接口如下。
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
void creatlist();
SLTNode* SLTBuyNode(SLTDataType x);
void printlist(SLTNode*);
//插入
void SLTPushBack(SLTNode**, SLTDataType);
void SLTPushFront(SLTNode**, SLTDataType);
//删除
void SLTPopBack(SLTNode**);
void SLTPopFront(SLTNode**);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//指定位置插入数据
void SLTInsert(SLTNode**, SLTDataType, SLTNode*);
void SLTInsertAfter( SLTDataType, SLTNode*);
//删除指定节点
void SLTErase(SLTNode**, SLTNode*);
void SLTEraseAfter(SLTNode*);
//销毁链表
void SListDestroy(SLTNode**);
test.c测试代码如下
注意：建议每完成一个接口就进行测试，避免全部完成后的一堆报错难以改正。
#include "sllist.h"
//实际操作中不会这么去创建链表
void creatlist()
{
SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
node1->data = 1;
SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
node2->data = 2;
SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
node3->data = 3;
SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
node4->data = 4;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = NULL;
SLTNode* plist = node1;
printlist(plist);
}
void test1()
{
SLTNode* plist = NULL;
//SLTPushBack(&plist, 1);
//SLTPushBack(&plist, 2);
//SLTPushBack(&plist, 3);
//SLTPushBack(&plist, 4);
SLTPushBack(NULL, 4);
SLTPushFront(&plist, 1);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 4);
SLTPushFront(&plist, 3);
//SLTPopBack(&plist);
//SLTPopBack(&plist);
//SLTPopFront(&plist);
//SLTPopFront(&plist);
//SLTNode* m=SLTFind(plist, 3);
//if (m!= NULL)
//{
//printf("找到了\n");
//}
SLTInsert(&plist, 3, m);
//SLTInsertAfter( 6, m);
//SLTErase(&plist, m);
//SLTEraseAfter(m);
SListDestroy(&plist);
printlist(plist);
}
int main()
{
//creatlist();
test1();
return 0;
}
1.单链表的创建和销毁及打印
核心步骤主要如下：
1）首先定义链表的节点结构体，里面需要存储数据和下一个节点的指针。
2）另外编写一个创建节点的函数用以每次动态开辟空间，避免代码冗余。
单链表的打印
void printlist(SLTNode* phead)
{
assert(phead);
SLTNode* p1 = phead;
while (p1)
{
printf("%d ", p1->data);
p1 = p1->next;
}
}
分析：
1.我们传入链表的头节点phead，并在该函数中再创建一个变量，使其等于phead，其目的是为了避免头节点被改变。
2.由于链表通过next指针逐次连接，因此通过对p1重新赋值为下一个节点的方式，对链表进行遍历。
3.打印只是遍历链表的值，而不需要改变链表的值，因此我们只需要穿一级指针即可。
单链表的销毁
void SListDestroy(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* p1 = pcur;
pcur = pcur->next;
free(p1);
p1 = NULL;
}
*pphead = NULL;
}
分析：
1. 需注意与打印明显不同的是，我们要改变链表的值使其空间释放并置为空。因此需要传二级指针。
2.由于每一个节点都是动态开辟都需要释放，而他们的访问只能通过上一个节点的next指针进行访问，因此我们尤其需要注意避免直接将头节点释放，而是采取与打印相似的原理，逐个遍历释放，最后将头节点置为空。
2.单链表的插入
头插：
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 SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
分析：
1. 与顺序表不同，此时不再需要进行检查空间的操作。而是直接创建节点进行插入。该函数的参数即为要插入节点的数值。
2. 头插将新节点插在原先链表的头部之前，要记得及时更新的链表的头节点。（后续也可采取创建一个哨兵位直接在其后插入的方式，后续博客会进行讲解）
尾插：
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;
}
}
分析：
1.首先创建新节点。
2.分析链表是否为空，如果为空，直接进行赋值操作。
3.如果不为空，则先遍历链表得到尾节点，将尾节点的next指针指向新节点，并更新尾节点。
在指定位置之前插入：
void SLTInsert(SLTNode** pphead, SLTDataType x, SLTNode* pos)
{
assert(pphead && pos);
if (pos == *pphead)
{
SLTPushFront(pphead,x);
}//检查pos是否为头节点
else
{
SLTNode* newnode = SLTBuyNode(x);
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
newnode->next = pos;
prev->next = newnode;
}
}
分析：
1.检查要插入的位置pos是否为头节点，若是则可以直接采用头插。
2.创建新节点，进行遍历操作寻找pos的位置。
3.记录pos的前驱节点位置，更新其与pos之间的连接。
在指定位置之后插入：
void SLTInsertAfter( SLTDataType x, SLTNode* pos)
{
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
原理与上相同。
3.单链表的删除
头删：
void SLTPopFront(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
注意记录要删除节点之后的位置，否则会导致后续节点无法访问。
尾删：
void SLTPopBack(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* ptail = *pphead;
SLTNode* prev = NULL;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
if (prev)//处理只有一个节点的情况
{
prev->next = NULL;
prev=NULL;
}
else
*pphead = NULL;
free(ptail);
ptail = NULL;
}
分析：
1. 当链表只有一个节点时，直接删除即可。
2. 当链表大于一个节点时，首先遍历链表得到尾节点，并记录其前驱节点的位置，之后删除尾节点
并更新尾部位置。
在指定位置删除：
void SLTErase(SLTNode** pphead, SLTNode* pos )
{
assert(pos && pphead&&*pphead);
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
分析：
1.若节点与头节点一样，直接头删。
2.若节点不为头节点，与上同理，遍历并删除。
4.单链表的查找
查找指定位置节点：
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
assert(phead);
SLTNode* pcur = phead;
while (pcur)
{
if (pcur->data==x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
与上同理，直接遍历查找即可。
以上就是单链表结构和实现的讲解，欢迎各位大佬前来斧正支持。
原文地址：https://blog.csdn.net/2303_81060385/article/details/142603597
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！