文章目录
任意位置（pos）前插入????????SListInsert
任意位置（pos）值删除????????SListErase
一、单链表结构
图示
代码实现
//结构
typedef int SLTDataType;
struct SListNode
{
SLTDataType data;
struct SListNode* next;
};
typedef struct SListNode SLTNode;二、函数接口
动态申请一个节点????????BuySListNode
//插入时--动态申请一个节点
SLTNode* BuySListNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); //创建一个新的节点newnode
newnode->data = x; //将要插入的数据放入该节点
newnode->next = NULL; //初始化该节点的next为NULL，因为只是申请，还没有具体使用
return newnode; //将新开辟出的节点返回
}单链表打印????????SListPrint
//单链表打印
void SListPrint(SLTNode* phead)
{
SLTNode* cur = phead; //phead是头指针，在main函数种创建，指向该链表第一个节点
while (cur != NULL) //cur指针用于链表遍历
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}尾插????????SListPushBack
//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
//二级指针，理解为传址调用即可
//若不用二级指针而用一级指针，无法做到在该函数体内改变main函数中我们创建的单链表
{
SLTNode* newnode = BuySListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
// 找尾节点的指针
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
// 尾节点，链接新节点
tail->next = newnode;
}
}头插????????SListPushFront
//头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}尾删????????SListPopBack
void SListPopBack(SLTNode** pphead)
{
if (*pphead == NULL) // 1、空
{
return;
}
else if ((*pphead)->next == NULL) // 2、链表中只有一个节点时
{
free(*pphead);
*pphead = NULL;
}
else // 3、有一个以上的节点
{
SLTNode* prev = NULL;
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}头删????????SListPopFront
//头删
void SListPopFront(SLTNode** pphead)
{
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}查找????????SListFind
//查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
SListNode* cur = phead;
//while (cur != NULL)
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}任意位置（pos）前插入????????SListInsert
// 在pos的前面插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
if (pos == *pphead)
{
SListPushFront(pphead, x);
}
else
{
SLTNode* newnode = BuySListNode(x);
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = newnode;
newnode->next = pos;
}
}任意位置（pos）值删除????????SListErase
// 删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{
if (pos == *pphead)
{
SListPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}三、整体实现
头文件? Slist.h
//头文件 Slist.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
//结构
typedef int SLTDataType;
struct SListNode
{
SLTDataType data;
struct SListNode* next;
};
typedef struct SListNode SLTNode;
//插入之前开辟一个新的节点
SLTNode* BuySListNode(SLTDataType x);
// 不会改变链表的头指针，传一级指针
void SListPrint(SLTNode* phead);
// 可能会改变链表的头指针，传二级指针
void SListPushBack(SLTNode** pphead, SLTDataType x);
void SListPushFront(SLTNode** pphead, SLTDataType x);
void SListPopFront(SLTNode** pphead);
void SListPopBack(SLTNode** pphead);
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
// 在pos的前面插入x
void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x);
// 删除pos位置的值
void SListErase(SLTNode** phead, SLTNode* pos);
// 有些地方也有这样的
在pos的前面插入x
//void SListInsert(SLTNode** phead, int i, SLTDataType x);
删除pos位置的值
//void SListErase(SLTNode** phead, int i);
源文件? Slist.c
// Slist.c
#include "SList.h"
//单链表打印
void SListPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
//插入时--动态申请一个节点
SLTNode* BuySListNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); //创建一个新的节点newnode
newnode->data = x; //将要插入的数据放入该节点
newnode->next = NULL; //初始化该节点的next为NULL，因为只是申请，还没有具体使用
return newnode; //将新开辟出的节点返回
}
//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
// 找尾节点的指针
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
// 尾节点，链接新节点
tail->next = newnode;
}
}
//头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
//头删
void SListPopFront(SLTNode** pphead)
{
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
//尾删
void SListPopBack(SLTNode** pphead)
{
if (*pphead == NULL) // 1、空
{
return;
}
else if ((*pphead)->next == NULL) // 2、链表中只有一个节点时
{
free(*pphead);
*pphead = NULL;
}
else // 3、有一个以上的节点
{
SLTNode* prev = NULL;
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}
//查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
SListNode* cur = phead;
//while (cur != NULL)
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
// 在pos的前面插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
if (pos == *pphead)
{
SListPushFront(pphead, x);
}
else
{
SLTNode* newnode = BuySListNode(x);
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = newnode;
newnode->next = pos;
}
}
// 删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{
if (pos == *pphead)
{
SListPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}四、使用
源文件? test.c
// test.c
#include "SList.h"
void TestSList1()
{
SLTNode* plist = NULL;
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPushFront(&plist, 0);
SListPrint(plist);
SListPopFront(&plist);
SListPopFront(&plist);
SListPopFront(&plist);
SListPrint(plist);
SListPopFront(&plist);
SListPopFront(&plist);
SListPrint(plist);
}
void TestSList2()
{
SLTNode* plist = NULL;
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPrint(plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListPrint(plist);
}
void TestSList3()
{
SLTNode* plist = NULL;
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPrint(plist);
// 想在3的前面插入一个30
SLTNode* pos = SListFind(plist, 1);
if (pos)
{
SListInsert(&plist, pos, 10);
}
SListPrint(plist);
pos = SListFind(plist, 3);
if (pos)
{
SListInsert(&plist, pos, 30);
}
SListPrint(plist);
}
void TestSList4()
{
SLTNode* plist = NULL;
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPrint(plist);
SLTNode* pos = SListFind(plist, 1);
if (pos)
{
SListErase(&plist, pos);
}
SListPrint(plist);
pos = SListFind(plist, 4);
if (pos)
{
SListErase(&plist, pos);
}
SListPrint(plist);
pos = SListFind(plist, 3);
if (pos)
{
SListErase(&plist, pos);
}
SListPrint(plist);
pos = SListFind(plist, 2);
if (pos)
{
SListErase(&plist, pos);
}
SListPrint(plist);
}
int main()
{
TestSList4();
return 0;
}