C语言实现不带头单链表的增、删、查、改
目录
什么是链表
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
- 单向、双向
- 带头、不带头
- 循环、非循环
这里介绍一种OJ题常考的，不带头节点的单向非循环链表。
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多
不带头单链表的增、删、查、改
一、增
增加的方式有两种，在链表的头部增加，和尾部增加，分别为头插和尾插。
1.头插
在链表的最前端插入数据，头插之前先要malloc一个节点。
创建节点
//创建新节点
SLTNode* BuySLTNode(SLTDataType x)
{
SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
node->data = x;
node->next = NULL;
return node;
}
头插
头插很简单，直接用新创建的节点指向原链表的头即可。
注意：这里形参要传二级指针，因为要该变有原指针的位置。可能不太容易理解，举个例子；交换两个数
当进行值传递时，数据内容并不会交换
而进行地址传递，数据的值才会传递
所以想要改变指针的值，需要传递指针的地址才行。形参也需要二级指针接收才行。
//头插
void SListPushFront(SLTNode** pplist, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pplist;
*pplist = newnode;
}
2.尾插
//尾插
void SListPushBack(SLTNode** pplist, SLTDataType x)
{
//创建一个新节点
SLTNode* newnode = BuySLTNode(x);
//1.判断链表是否为空
if (*pplist== NULL)
{
//链表为空，直接将新节点插入
*pplist = newnode;
}
//2.链表非空
else
{
//遍历，找链表的尾
SLTNode* tail = *pplist;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
二、删
删除的方式有两种，在链表的头部删除，和尾部删除，分别为头删和尾删。
1.头删
//头删
void SListPopFront(SLTNode** pplist)
{
//1.链表为空，不需要删除，直接返回
if (*pplist == NULL)
{
return;
}
//2.链表有多个节点，先找到头节点
SLTNode* next = (*pplist)->next;
free(*pplist);
*pplist = next;
}
2.尾删
//尾删
void SListPopBack(SLTNode** pplist)
{
//1.空节点
if (*pplist == NULL)
{
return;
}
//2.只有一个节点
SLTNode* tail = *pplist;
if((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
//多节点
else
{
SLTNode* prev = NULL;
SLTNode* tail = *pplist;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
}
三、查
//单链表查找
SLTNode* SListFind(SLTNode* plist, SLTDataType x)
{
SLTNode* cur = plist;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
四、改
1.任意位置插入
这里任意位置插入，是插入你所选位置的下一个元素。
//单链表在pos位置之后插入x
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
2.任意位置删除
这里任意位置删除，是删除你所选位置的下一个元素
//任意位置删除
void SListEraseAfter(SLTNode* pos)
{
assert(pos);
if (pos->next == NULL)
{
return;
}
else
{
SLTNode* next = pos->next;
pos->next = next->next;
free(next);
}
}
完整代码实现
头文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
//打印链表
void SListPrint(SLTNode* plist);
//尾插
void SListPushBack(SLTNode** pplist, SLTDataType x);
//头插
void SListPushFront(SLTNode** pplist, SLTDataType x);
//尾删
void SListPopBack(SLTNode** pplist);
//头删
void SListPopFront(SLTNode** pplist);
//单链表查找
SLTNode* SListFind(SLTNode* plist, SLTDataType x);
//单链表在pos位置之后插入x
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//单链表在pos位置之前插入
void SListInsertBefore(SLTNode** pplist, SLTNode* pos, SLTDataType x);
//任意位置之后删除
void SListEraseAfter(SLTNode* pos);
//任意位置删除
void SListEraseCur(SLTNode** pplist, SLTNode* pos);
.c文件，存放函数定义
#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"
//打印链表
void SListPrint(SLTNode* plist)
{
SLTNode* cur = plist;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL");
printf("\n");
}
SLTNode* BuySLTNode(SLTDataType x)
{
SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
node->data = x;
node->next = NULL;
return node;
}
//尾插
void SListPushBack(SLTNode** pplist, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
//1.空
if (*pplist== NULL)
{
*pplist = newnode;
}
//2.非空
else
{
//找尾
SLTNode* tail = *pplist;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
//头插
void SListPushFront(SLTNode** pplist, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pplist;
*pplist = newnode;
}
//尾删
void SListPopBack(SLTNode** pplist)
{
//1.空节点
if (*pplist == NULL)
{
return;
}
//2.一个节点
SLTNode* tail = *pplist;
if((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
SLTNode* prev = NULL;
SLTNode* tail = *pplist;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
}
//头删
void SListPopFront(SLTNode** pplist)
{
//1.空
if (*pplist == NULL)
{
return;
}
//2.多节点
SLTNode* next = (*pplist)->next;
free(*pplist);
*pplist = next;
}
//单链表查找
SLTNode* SListFind(SLTNode* plist, SLTDataType x)
{
SLTNode* cur = plist;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
//单链表在pos位置之后插入x
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
//单链表在pos位置之前插入
void SListInsertBefore(SLTNode** pplist,SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode= BuySLTNode(x);
if (pos == *pplist)
{
newnode->next = pos;
*pplist = newnode;
}
else
{
SLTNode* prev = NULL;
SLTNode* cur = *pplist;
while (cur != pos)
{
prev = cur;
cur = cur->next;
}
prev->next = newnode;
newnode->next = pos;
}
}
//任意位置删除
void SListEraseAfter(SLTNode* pos)
{
assert(pos);
if (pos->next == NULL)
{
return;
}
else
{
SLTNode* next = pos->next;
pos->next = next->next;
free(next);
}
}
//任意位置删除
void SListEraseCur(SLTNode** pplist, SLTNode* pos)
{
assert(pos);
if (pos == NULL)
{
return;
}
else
{
SLTNode* prev = NULL;
SLTNode* cur = *pplist;
while (cur != pos)
{
prev = cur;
cur = cur->next;
}
prev->next = pos->next;
free(pos);
}
}
.c文件，测试文件，主函数文件
#include "SList.h"
void TestSList1()
{
SLTNode* plist = NULL;
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPrint(plist);
}
int main()
{
TestSList1();
return 0;
}