1.单链表概念
单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(s数据元素的映象) +指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
2.链表分类
链表的结构多种多样有三个大分类：
1.单向、双向
2.带头、不带头
3.循环、不循环
而三组之间又可以互相组合，使得链表的结构多达8种，本篇的单链表主要是指单向不带头不循环链表，这也是本篇的重点。
2.1单向链表
单向链表：指链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始，只能通过前一个结点找到后一结点，而不能从后一结点找到前一结点。
2.2双向链表
双向链表：指链表的每个数据中结点都有两个指针，分别指向直接后继和直接前驱，它能从双向链表中的任意一个结点开始，并且可以方便地访问它的前驱结点和后继结点。
2.3不带头链表
不带头链表：指链表以一个结点结构的指针开头，我们存储的数据直接从该指针指向的位置存储，该链表实现相较于带头结点稍微复杂，是各oj题与面试题的常客。
2.4带头链表
带头链表：指链表的以一个不存任何数据的结点开始，我们称之为头结点，而我们存储的数据则从头节点的下一结点开始存储，这样就能有效地避免因链表为空带来的各种问题。
2.5不循环链表
不循环链表：指链表的最后一个结点指向空，使得当链表走到空时我们就可以知道链表已经走到了尽头。
2.6循环链表
循环链表：指链表的最后一个结点指向链表的头结点，从而在逻辑形态中就像一个完整的闭环。
3.单链表实现
3.1单链表结构
typedef int SListDataType
typedef struct SListNode
{
SListDataType data;
struct SListNode* next;
}SListNode;SListNode:链表头结点代称。
SListDataType:指链表中每个结点存储的数据类型，只需要改动typedef int SListDataType 中的int就能该变节点内存放的数据类型。
data：存放类型结构体变量名
next：指向下一结点的指针。
3.2链表功能实现
文件：SList.c
3.2.1创建新结点
SListNode* BuySListNode(SListDataType x) //创建新结点
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); //开辟新结点的空间
if (newnode == NULL) //判断是否开辟成功
{
printf("开辟内存失败\n");
exit(-1);
}
newnode->data = x; //将新节点中需要存放的值放入结点的data中
newnode->next = NULL; //将新节点指向空
return newnode; //返回新结点指针
}3.2.2链表打印
void SListPrint(SListNode* plist) //链表打印
{
SListNode* cur = plist; //可以不用创建cur，单这样会使可读性更强
while (cur != NULL) //链表不为空才打印，依次遍历打印
{ //直到cur为NULL
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}3.2.3链表尾插
void SListPushBack(SListNode** pplist, SListDataType x) //尾插
{
SListNode* newnode = BuySListNode(x);
if (*pplist == NULL) //当链表为空
{
*pplist = BuySListNode(x); //直接创建新节点，plist指向新结点
}
else
{
SListNode* backnode = *pplist;
while (backnode->next != NULL)
{
backnode = backnode->next; //链表不为空找尾结点
}
backnode->next = newnode; //在尾结点插入新结点
}
}3.2.4链表头插
void SListPushFront(SListNode** pplist, SListDataType x) //头插
{
SListNode* newnode = BuySListNode(x); //创建新结点
newnode->next = *pplist; //新节点指向头指针
*pplist = newnode; //头指针指向新节点
}3.2.5链表按位插入
void SListInsert(SListNode** pplist, int pos, SListDataType x) //按位插入
{
SListNode* cur = *pplist;
SListNode* pre = NULL;
SListNode* newnode;
int i = 0;
//特殊情况1：在首位置插入(链表为空)
//特殊情况2：在首位置插入(链表不为空)
if (pos == 0)
{
newnode = BuySListNode(x);
*pplist = newnode;
newnode->next = cur;
//printf("在首位置插入\n"); //调试用
return;
}
while (cur != NULL)
{
//特殊情况3：在除首位置及末位置插入
if (pos == i)
{
newnode = BuySListNode(x);
pre->next = newnode;
newnode->next = cur;
//printf("在除首位置及末位置插入\n"); //调试用
return;
}
pre = cur;
cur = cur->next;
i++;
}
//特殊情况4：在末位置插入
if (pos == i)
{
newnode = BuySListNode(x);
pre->next = newnode;
newnode->next = cur;
//printf("在末位置插入\n"); //调试用
}
//特殊情况5：超出可插入范围
else
{
printf("超出可插入范围\n"); //错误提示
return;
}
}3.2.6链表尾删
void SListPopBack(SListNode** pplist) //尾删
{
SListNode* pre = NULL;
SListNode* backnode = *pplist;
//特殊情况1：当链表为空
if (backnode == NULL)
{
//printf("链表为空\n"); //调试用
return;
}
//特殊情况2：当链表只有一个元素
else if (backnode->next == NULL)
{
//printf("链表只有一个结点\n"); //调试用
free(*pplist);
*pplist = NULL;
}
//正常情况
else
{
while (backnode->next != NULL) //找尾
{
pre = backnode;
backnode = backnode->next;
}
free(backnode); //释放结点
backnode = NULL;
pre->next = NULL; //上一结点的next指向NULL
}
}3.2.7链表头删
void SListPopFront(SListNode** pplist) //头删
{
SListNode* frontnode = *pplist;
*pplist = frontnode->next;
free(frontnode);
frontnode = NULL;
}
3.2.8链表按位删除
void SListErase(SListNode** pplist, int pos) //位删
{
SListNode* cur = *pplist;
SListNode* pre = NULL;
int i = 0;
//特殊情况1:当链表为空
if (cur == NULL)
{
printf("链表为空\n");
return;
}
//特殊情况2：在首位置删除
else if (pos == 0)
{
*pplist = cur->next;
free(cur);
cur = NULL;
printf("首位置删除\n");
return;
}
//特殊情况3；中间与末位置删除
while (cur != NULL)
{
if (pos == i)
{
pre->next = cur->next;
free(cur);
cur = NULL;
printf("当链表不为空删除\n");
return;
}
pre = cur;
cur = cur->next;
i++;
}
//特殊情况4：超出可删除范围
printf("超出可删除位置\n");
return;
}3.2.9链表按值查找
int SListFind(SListNode* plist, SListDataType x) //按值查找
{
int pos = 0;
while (plist != NULL)
{
if (plist->data == x)
return pos; //找到查找值返回位置
else
{
pos++;
plist = plist->next; //没找到值往链表下一位走
}
}
return - 1; //没找到该值返回-1
}
3.3链表头文件
文件："SList.h"
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SListDataType;
typedef struct SListNode
{
SListDataType data;
struct SListNode* next;
}SListNode;
void SListPrint(SListNode* plist); //打印
void SListPushBack(SListNode** pplist, SListDataType x); //尾插
void SListPushFront(SListNode** pplist, SListDataType x); //头插
void SListInsert(SListNode** pplist, int pos, SListDataType x); //按位插入
void SListPopBack(SListNode** pplist); //尾删
void SListPopFront(SListNode** pplist); //头删
void SListErase(SListNode** plist, int pos); //位删
int SListFind(SListNode* plist, SListDataType x); //按值查找
3.4链表功能测试
文件："test.c"
#include "SList.h"
void SListTest1()
{
SListNode* plist = NULL;
SListPopBack(&plist); //尾删第一种情况测试
SListPushBack(&plist, 0);
SListPrint(plist);
SListPopBack(&plist); //尾删第二种情况测试
SListPushFront(&plist, 2);
SListPushFront(&plist, 1);
SListPrint(plist);
SListPopBack(&plist); //尾删第三种情况测试
SListPrint(plist);
SListPushFront(&plist, 0);
SListPushFront(&plist, -1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPrint(plist);
SListPopFront(&plist);
SListPrint(plist); //头删测试
return;
}
void SListTest2() //按值查找测试
{
SListNode* plist = NULL;
int pos;
SListPushBack(&plist, 0);
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPrint(plist);
pos = SListFind(plist, 1);
printf("%d ", pos);
pos = SListFind(plist, 9);
printf("%d ", pos);
}
void SListTest3()
{
SListNode* plist = NULL;
SListInsert(&plist, 0, 5); //在首位置插入且链表为空测试
SListPushFront(&plist, 4);
SListPrint(plist);
SListInsert(&plist, 0, 3); //在首位置插入且链表不为空测试
SListPrint(plist);
SListPushFront(&plist, 2);
SListPushFront(&plist, 1);
SListPushFront(&plist, 0);
SListInsert(&plist, 3, 9); //在除首位置和末位置插入测试
SListPrint(plist);
SListInsert(&plist, 7, 9); //在末位置插入测试
SListPrint(plist);
SListInsert(&plist, -1, 9); //在超出链表的位置插入
SListInsert(&plist, 10, 9);
SListPrint(plist);
}
void SListTest4() //按位删除测试
{
SListNode* plist = NULL;
SListErase(&plist, 3); //链表为空测试
SListInsert(&plist, 0, 4);
SListPrint(plist);
SListErase(&plist, 0); //首位置删除测试
SListPrint(plist);
SListInsert(&plist, 0, 0);
SListInsert(&plist, 0, 1);
SListInsert(&plist, 0, 2);
SListInsert(&plist, 0, 3);
SListPrint(plist);
SListErase(&plist, 2); //中间位置删除测试
SListPrint(plist);
SListErase(&plist, 2); //末位置删除测试
SListPrint(plist);
SListErase(&plist, 3); //超出可删除范围测试
SListPrint(plist);
}
int main()
{
SListTest1();
SListTest2();
SListTest3();
SListTest4();
return 0;
}✨写在最后
⏱笔记时间：2021_10_3
🌐代码：Gitee:朱雯睿 (zhu-wenrui) - Gitee.com
Github:Zero0Tw0 · GitHub