一.定义：
链表由多个节点组成，尽管物理空间上每个节点位置可能不同，但逻辑顺序上每个节点两两之间相互联系，像小火车的每节车厢一样，我们可以对链表进行增删查改等操作。
因此，链表由两部分组成，一部分是我们要存储的数据，另一部分是结构体指针，指向下一个节点地址，从而将每个节点两两连接在一起。
struct SListNode
{
int Data;
struct SListNode* next;
};
二.代码实现
1.打印
void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;//创建临时变量，避免影响phead变量
while (pcur)//pcur!=NULL
{
printf("%d->", pcur->data);
pcur = pcur->next;//因为物理上可能不连续，因此不能用循环变量i来遍历每个节点。
}
printf("NULL\n");
}
2.尾插
SLTNode* SLTBuyNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc");
return 1;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SLTPushBack(SLTNode** pphead, SLTDataTypex)
//*plist==**phead,plist=*phead,&plist=phead
{ //*pphead是指向第一个节点的指针
assert(pphead);//二级指针，不能为空；一级指针可以为空，表示空节点
//创建新节点：
SLTNode* newnode=SLTBuyNode(x);
//两种情况：
if (*pphead == NULL)//特殊情况：当链表没有节点时，phead指针指向NULL
{
*pphead = newnode;//将phead与新节点连接
}
else
{
//找到原链表尾节点：
SLTNode* ptail = *pphead;
while (ptail->next)//注意不是ptail
{
ptail = ptail->next;//遍历每个节点
}
//连接起来；
ptail->next = newnode;
}
}
3.头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
//*pphead是否为空，该代码都可以满足，因此不用if分开讨论
newnode->next = *pphead;//连接
*pphead = newnode;//改变*pphead
}
4.尾删
void SLTPopBack(SLTNode** pphead)
{
assert(pphead && *pphead);//pphead不能为空否则不能解引用+*phead不能为空，因为节点不能为空
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead == NULL;
}
else
{
SLTNode* ptail = *pphead;//指向尾节点
SLTNode* prev = *pphead;//指向尾节点前一个节点
while (ptail->next)
{
prev = ptail;//滞后一个节点
ptail = ptail->next;
}
free(ptail);
ptail = NULL;
prev->next = NULL;
}
}
5.头删
void SLTPopFront(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* next = (*pphead)->next;//创建临时结构体指针变量，指向第二个节点
free(*pphead);
(*pphead) = next;
}
6.查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* pcur = phead;
while (pcur)//遍历每个元素
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
7.在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead && *pphead);//！！！！！
assert(pos);
//创建新节点
SLTNode* newnode = SLTBuyNode(x);
//当pos在第一个节点：头插
if (*pphead == pos)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)//找到pos前一个节点
{
prev = prev->next;
}
//连接
newnode->next = pos;
prev->next = newnode;
}
}
8.在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
//创建新节点
SLTNode* newnode = SLTBuyNode(x);
//连接
newnode->next = pos->next;
pos->next = newnode;
}
9.删除指定位置节点
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->next = pos->next;
free(pos);
pos = NULL;
}
}
10.删除指定位置之后的节点
void SLTErazeAfter(SLTNode* pos)
{
assert(pos && pos->next);
SLTNode* del = pos->next;//一定要创建del临时变量
pos->next = del->next;
free(del);
del = NULL;//别忘了
}
11.销毁
void SListDestroy(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* pcur = *pphead;
while (pcur)
{//双指针法
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}
三.整体代码实现：
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 SLTErazeAfter(SLTNode* pos);
//销毁
void SListDestroy(SLTNode** pphead);
SList.c
#include"SList.h"
//打印：
void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;//创建临时变量，避免影响phead变量
while (pcur)//pcur!=NULL
{
printf("%d->", pcur->data);
pcur = pcur->next;//因为物理上可能不连续，因此不能用循环变量i来遍历每个节点。
}
printf("NULL\n");
}
//尾插：
SLTNode* SLTBuyNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)//*plist==**phead,plist=*phead,&plist=phead
{//*pphead是指向第一个节点的指针
assert(pphead);//二级指针，不能为空；一级指针可以为空，表示空节点
//创建新节点：
SLTNode* newnode=SLTBuyNode(x);
//两种情况：
if (*pphead == NULL)//特殊情况：当链表没有节点时，phead指针指向NULL
{
*pphead = newnode;//将phead与新节点连接
}
else
{
//找到原链表尾节点：
SLTNode* ptail = *pphead;
while (ptail->next)//注意不是ptail
{
ptail = ptail->next;//遍历每个节点
}
//连接起来；
ptail->next = newnode;
}
}
//头插：
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
//*pphead是否为空，该代码都可以满足，因此不用if分开讨论
newnode->next = *pphead;//连接
*pphead = newnode;//改变*pphead
}
//尾删
void SLTPopBack(SLTNode** pphead)
{
assert(pphead && *pphead);//pphead不能为空否则不能解引用+*phead不能为空，因为节点不能为空
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* ptail = *pphead;//指向尾节点
SLTNode* prev = *pphead;//指向尾节点前一个节点
while (ptail->next)
{
prev = ptail;//滞后一个节点
ptail = ptail->next;
}
free(ptail);
ptail = NULL;
prev->next = NULL;
}
}
//头删
void SLTPopFront(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* next = (*pphead)->next;//创建临时结构体指针变量，指向第二个节点
free(*pphead);
(*pphead) = next;
}
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
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 && *pphead);//！！！！！
assert(pos);
//创建新节点
SLTNode* newnode = SLTBuyNode(x);
//当pos在第一个节点：头插
if (*pphead == pos)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)//找到pos前一个节点
{
prev = prev->next;
}
//连接
newnode->next = pos;
prev->next = newnode;
}
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
//创建新节点
SLTNode* newnode = SLTBuyNode(x);
//连接
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->next = pos->next;
free(pos);
pos = NULL;
}
}
//删除pos之后的节点
void SLTErazeAfter(SLTNode* pos)
{
assert(pos && pos->next);
SLTNode* del = pos->next;//一定要创建del临时变量
pos->next = del->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
#include"SList.h"
void SLTtest1()
{
//创建几个节点：malloc
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;
//将4个节点连接起来
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = NULL;
//链表打印
SLTNode* plist = node1;
SLTPrint(plist);
}
void SLTest2()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);//传址调用！！！
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
SLTNode* find = SLTFind(plist, 2);
SLTInsert(&plist, find, 11);
SLTPrint(plist);
SLTNode* find2 = SLTFind(plist, 3);
SLTErase(&plist, find2);
SLTPrint(plist);
SLTNode* find3 = SLTFind(plist, 11);
SLTErazeAfter(find3);
SLTPrint(plist);
SListDestroy(&plist);
SLTPrint(plist);
}
int main()
{
//SLTtest1();
SLTest2();
return 0;
}
————————————————
版权声明：本文为CSDN博主「fffzd」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/yyyzc_/article/details/157060081
|
本帖子中包含更多资源
您需要 登录 才可以下载或查看，没有账号？注册
×
|
