概述
经典的单向链表 , 需要考虑各种场景 , 实现较为复杂 , 在代码中有很多自己的注解不删除了 见谅
我由三个文件实现 , 分别是
- 头文件和声明 List.h
- 实现功能的源码List.c
- 测试链表功能的测试文件 Test.c
List.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);
SLTNode* SLFind(SLTNode* phead, SLTDataType x);
void SLPushFront(SLTNode** pphead, SLTDataType x);
void SLPushBack(SLTNode** pphead, SLTDataType x);
void SLpopFront(SLTNode** pphead);
void SLpopBack(SLTNode** pphead);
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
void SLInsertAfter(SLTNode* phead, SLTDataType x);
void SLErase(SLTNode** pphead, SLTNode* pos);
void SLEraseAfter(SLTNode* pos);
void SLdestroy(SLTNode** pphead);
List.c
#include "SList.h"
void SLTPrint(SLTNode *phead)
{
// cur 当前的缩写 cur存储的是当前的节点地址
SLTNode *cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next; // 自身的 next元素 就是下一个的地址
}
printf("NULL\n");
}
SLTNode *BuyLTNode(SLTDataType x)
{
SLTNode *newnode = (SLTNode *)malloc(sizeof(SLTNode)); // 局部开辟空间会消失 所以需要malloc
if (newnode == NULL)
{
perror("mallic fail");
return NULL;
}
newnode->data = x; // 初始化
newnode->next = NULL;
return newnode;
}
void SLPushFront(SLTNode **pphead, SLTDataType x)
{
SLTNode *newnode = BuyLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void SLPushBack(SLTNode **pphead, SLTDataType x)
{
SLTNode *newnode = BuyLTNode(x); // 第一次的时候 plist为空的情况下
if (*pphead == NULL)
{
*pphead = newnode; // 改变结构体自身的指针 需要2级指针
}
else
{
SLTNode *tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode; // 改变结构体的内容
}
}
void SLpopFront(SLTNode **pphead)
{
assert(*pphead);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode *second = (*pphead)->next; // 释放前需要记录当前位置
free(*pphead);
*pphead = second;
}
}
void SLpopBack(SLTNode **pphead) // 3种情况 NULL 一个节点 多个几点
{
assert(*pphead); // NULL
if ((*pphead)->next == NULL) // 单节点
{
free(*pphead);
*pphead = NULL;
}
else // 多节点
{
SLTNode *tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
SLTNode *SLFind(SLTNode *phead, SLTDataType x) // 查找也有修改的功能, 因为fine返回了节点的指针
{
SLTNode *cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
// 在pos之前插入
void SLInsert(SLTNode **pphead, SLTNode *pos, SLTDataType x)
{
assert(pphead);
assert(pos);
SLTNode *cur = *pphead;
if (*pphead == pos)
{
SLPushFront(pphead, x);
}
else
{
SLTNode *newnode = BuyLTNode(x);
while (cur->next != pos)
{
cur = cur->next;
}
newnode->next = pos;
cur->next = newnode;
}
}
// 在pos之后插入
void SLInsertAfter(SLTNode *pos, SLTDataType x)
{
assert(pos);
SLTNode *newnode = BuyLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
// 删除pos位置的值
void SLErase(SLTNode **pphead, SLTNode *pos)
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
SLpopFront(pphead);
}
else
{
SLTNode *cur = *pphead;
while (cur->next != pos)
{
cur = cur->next;
}
cur->next = pos->next;
free(pos);
pos = NULL;
}
}
// 删除pos位置后面的值
void SLEraseAfter(SLTNode *pos)
{
assert(pos);
assert(pos->next);
SLTNode *next = pos->next;
pos->next = next->next;
free(next);
}
void SLdestroy(SLTNode **pphead)
{
assert(pphead);
SLTNode *cur = *pphead;
while (cur)
{
SLTNode *next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
Test.c
#include "SList.h"
void TestList1()
{
SLTNode *plist = NULL;
SLPushFront(&plist, 1);
SLPushFront(&plist, 2);
SLPushFront(&plist, 3);
SLPushFront(&plist, 4);
SLTNode *pos = SLFind(plist, 3);
if (pos)
pos->data = 30;
SLTPrint(plist);
}
void TestList2()
{
SLTNode *plist = NULL;
SLPushBack(&plist, 1);
SLPushBack(&plist, 2);
SLPushBack(&plist, 3);
SLPushBack(&plist, 4);
SLTNode *pos = SLFind(plist, 3);
SLEraseAfter(pos);
SLTPrint(plist);
SLdestroy(&plist);
}
int main()
{
TestList2();
return 0;
}
