目录
一、单链表的基本介绍
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
1.基本结构
1.以上为单链表的基本结构，每一部分是一个结构体，里面一部分用来存储数据，一部分用来存储下一个结构体的地址。通俗的来说，就是包含数据域和指针域。这里把一个结构体叫做结点。
2.它与顺序表不同，顺序表就好像数组一样，每个数据都是按照顺序排列在一起的。而链表在空间上是不一定有序的。是通过地址连接下一个的。
二、单链表的实现
1.结点定义和头指针的创建
typedef int SLTDataType;//把要存储的数据重新定义一下
typedef struct SListNode
{
SLTDataType data; //数据域
struct SListNode* next;//定义一个指针
}SLTNode;
同时也在测试代码test.c中创建一个头指针，代码如下：
void TestSList1()
{
//头指针
SLTNode* plist = NULL; //plist永远指着第一个
//头插
//...以下是测试代码
}
2.打印接口实现
//打印
void SListPrint(SLTNode* phead) //这里用一级指针，不需要修改头指针
{
//不用assert
//因为它有可能是空的
SLTNode* cur = phead;//赋给一个变量
while (cur!=NULL)
{
printf("%d->", cur->data);
cur = cur->next;
//这里不能cur++，因为链表结点地址不连续
//但是指针域里面存储了下一个结点的地址，直接用
//cur=cur->next.
}
printf("NULL\n");
}
3.开辟新的节点
//开辟结点接口
SLTNode* BuySLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
printf("申请结点失败\n");
//perror("malloc fail");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;//一开始把新的结点置空，但是如果是头插或者中间插的话，在接口外
//还要把这个next指向后边的结点
return newnode;
}
4.头插接口
头插：在链表头插入一个结点
//头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//先开辟结点
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pphead;//把新的结点指向第一个地址，pphead是plist的地址
*pphead = newnode; //再把新的结点赋值给头地址即可
}
5.头删接口
分情况：1.空 2.一个节点 3.一个节点以上
//头删
void SListPopFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//温柔检查
if (*pphead == NULL)
{
return;
}
//暴力检查
//1.为空不能删
//assert(*pphead != NULL);
//2.有一个结点或者以上都可以
//给个临时指针保存我们要free的
SLTNode* del = *pphead;
*pphead = (*pphead)->next;
free(del);
del = NULL;
}
6.尾插接口
//尾插两种
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
//1.空
//2.非空
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//找尾
SLTNode* tail = *pphead; //tail结构体指针
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;//把新结点地址给tail->next即可
}
}
tail这些指针不用free()这些只是临时的指针变量，只是帮助我们找尾的而已，结构走完程序自动free()掉他们了。
7.尾删接口
分情况：1.空 2.一个 3.一个以上
//尾删
void SListPopBack(SLTNode** pphead)
{
//1.空
//2.一个结点
//3.一个以上结点
//1.
assert(pphead);
//温柔检查
//1.空
if (*pphead == NULL)
{
return;
}
//暴力检查
//为空不能删
//assert(*pphead != NULL);
//2.有一个结点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
//3.有一个以上结点
else
{
//尾删
SLTNode* prev = NULL;//把前一个结点置空
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;//把前一个置空
tail = tail->next;
}
prev->next = NULL;
free(tail);
tail = NULL;
//或者
/*SLTNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next=NULL;*/
}
}
8.查找接口实现
//查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;//循环完找不到，返回空指针
}
9.在pos位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
//如果pos是第一个
if (pos == *pphead)
{
SListPopFront(pphead, x);//直接调用头插
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
//暴力检查，pos不在链表中，prev为空，没找到pos，说明pos传错了
assert(prev);
}
SLTNode* newnode = BuySLTNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
10.在pos位置之后插入
//在pos后面删除
void SListEraseAfter(SLTNode* pos)
{
assert(pos);
if (pos->next)
{
//pos->next=pos->next->next;
//不推荐这种写法，这样一些我们原来的pos->next就不见了
SLTNode* next = pos->next;
SLTNode* next_next = next->next;
pos->next = next_next;
free(next);
}
}
11.删除pos位置
//删除pos位置
void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
if (*pphead == pos)
{
SListPopFront(pphead);//直接调用头删
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
//检查pos不是链表中结点，参数传错了
}
prev->next = pos->next;
free(pos);
}
}
12.删除pos后面位置
void SListEraseAfter(SLTNode* pos)
{
assert(pos);
if (pos->next == NULL)
{
return;//pos后一个位置为空
}
else
{
SLTNode* next = pos->next;
pos->next = next->next;
free(next);
}
}
13.销毁
//销毁
void SListDestory(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
}
三、全部代码
1.SList.h
代码如下：
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
//typedef int SLTDataType;
//typedef struct SListNode
//{
// SLTDataType data;
// struct SListNode* next;//定义一个指针
// //SLTNode* next; //错误的写法
// SListNode* next;
//}SLTNode, * PSLTNode;
//
SLTNode*
PSLTNode
struct SListNode* //这三个是等价的(结构体指针)
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;//定义一个指针
}SLTNode;
//开辟结点接口
SLTNode* BuySLTNode(SLTDataType x);
//打印
void SListPrint(SLTNode* phead);
//销毁
void SListDestory(SLTNode** pphead);
//头插
//改变结构体指针，就要传指针的指针
void SListPushFront(SLTNode** pphead, SLTDataType x);
//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);
//尾删
void SListPopBack(SLTNode** pphead);
//头删
void SListPopFront(SLTNode** pphead);
//查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
//或者用二级指针
//在pos之前插入
void SListInsert(SLTNode** pphead,SLTNode* pos,SLTDataType x);
// 在pos后面插入
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos位置
void SListErase(SLTNode** pphead,SLTNode* pos);
// 删除pos后面位置
void SListEraseAfter(SLTNode* pos);
2.SList.c
代码如下：
#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"
//打印
void SListPrint(SLTNode* phead) //这里用一级指针，不需要修改头指针
{
//不用assert
//因为它有可能是空的
SLTNode* cur = phead;//赋给一个变量
while (cur!=NULL)
{
printf("%d->", cur->data);
cur = cur->next;
//这里不能cur++，因为链表结点地址不连续
//但是指针域里面存储了下一个结点的地址，直接用
//cur=cur->next.
}
printf("NULL\n");
}
//开辟结点接口
SLTNode* BuySLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
printf("申请结点失败\n");
//perror("malloc fail");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;//一开始把新的结点置空，但是如果是头插或者中间插的话，在接口外
//还要把这个next指向后边的结点
return newnode;
}
//头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//先开辟结点
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pphead;//把新的结点指向第一个地址，pphead是plist的地址
*pphead = newnode; //再把新的结点赋值给头地址即可
}
//尾插两种
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
//1.空
//2.非空
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//找尾
SLTNode* tail = *pphead; //tail结构体指针
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
//头删
void SListPopFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//温柔检查
if (*pphead == NULL)
{
return;
}
//暴力检查
//1.为空不能删
//assert(*pphead != NULL);
//2.有一个结点或者以上都可以
//给个临时指针保存我们要free的
SLTNode* del = *pphead;
*pphead = (*pphead)->next;
free(del);
del = NULL;
}
//尾删
void SListPopBack(SLTNode** pphead)
{
//1.空
//2.一个结点
//3.一个以上结点
//1.
assert(pphead);
//温柔检查
//1.空
if (*pphead == NULL)
{
return;
}
//暴力检查
//为空不能删
//assert(*pphead != NULL);
//2.有一个结点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
//3.有一个以上结点
else
{
//尾删
SLTNode* prev = NULL;
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;//把前一个置空
tail = tail->next;
}
prev->next = NULL;
free(tail);
tail = NULL;
//或者
/*SLTNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next=NULL;*/
}
}
//销毁
void SListDestory(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
}
//查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;//循环完找不到，返回空指针
}
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
//如果pos是第一个
if (pos == *pphead)
{
SListPopFront(pphead, x);//直接调用头插
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
//暴力检查，pos不在链表中，prev为空，没找到pos，说明pos传错了
assert(prev);
}
SLTNode* newnode = BuySLTNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
//pos后插
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
//注意下边两条顺序
newnode->next = pos->next;
pos->next = newnode;
}
//在pos后面删除
void SListEraseAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
3.Test.c
代码如下：
#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"
void TestSList1()
{
//头指针
SLTNode* plist = NULL; //plist永远指着第一个
//头插
SListPushFront(&plist, 1);
SListPushFront(&plist, 2);
SListPushFront(&plist, 3);
SListPushFront(&plist, 4);
SListPrint(plist);
//删
SListPopFront(&plist);
SListPrint(plist);
SListPopFront(&plist);
SListPrint(plist);
SListPopFront(&plist);
SListPrint(plist);
SListPopFront(&plist);
SListPrint(plist);
}
void TestSList2()
{
SLTNode* plist = NULL; //plist永远指着第一个
//尾插
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPrint(plist);
SListPopBack(&plist);
SListPrint(plist);
SListPopBack(&plist);
SListPrint(plist);
SListPopBack(&plist);
SListPrint(plist);
SListPopBack(&plist);
SListPrint(plist);
SListPopBack(&plist);
SListPrint(plist);
}
TestSList3()
{
SLTNode* plist = NULL;
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPrint(plist);
SLTNode* pos = SListFind(plist, 3);
if (pos)
{
//可以直接修改
pos->data *= 10;
printf("找到了\n");
}
else
{
printf("没有找到\n");
}
SListPrint(plist);
pos = SListFind(plist, 2);
if (pos)
{
SListInsert(&plist, pos, 20);
}
SListPrint(plist);
SListDestory(&plist);
}
int main()
{
//TestSList1();
TestSList3();
return 0;
}