单向无头不循环链表的实现
如上图即为链表的逻辑结构（人为想象出来的）
以下是更为具体的解释
#include<stdio.h>
#include<stdlib.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
int main()
{
struct SListNode* node1 = (struct SListNode*)malloc(sizeof(struct SListNode));
struct SListNode* node2 = (struct SListNode*)malloc(sizeof(struct SListNode));
struct SListNode* node3 = (struct SListNode*)malloc(sizeof(struct SListNode));
struct SListNode* node4 = (struct SListNode*)malloc(sizeof(struct SListNode));
printf("%p\n", node1);
printf("%p\n", node2);
printf("%p\n", node3);
printf("%p\n", node4);
}
程序运行结果如下
我们先用上面程序创造四个节点
一个节点就是一个结构体
链表的节点（有一个数据域和一个指针域）
指针指向下一个节点，就是他自己的类型
同时我们会发现链表是单独开空间的，地址是随机的
我们用图画来表示上述过程
这就是链表存储的物理结构
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
- 单向、双向
- 带头、不带头
- 循环、非循环
- 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结
构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2.带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向
循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而
简单了，后面我们代码实现了就知道了
在这里我们实现的是无头单向不循环的链表
接下来进入正题
假装已经有了一个链表，这里我们首先实现一下打印这个接口
void SListPrint(SLTNode* plist)
{
SLTNode* cur = plist;
while (cur != NULL)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
plist是第一个节点的地址，将plist给给cur，然后将cur->next赋给cur 意思就是让cur指向下一个节点，如下是图画解释
尾插的实现
尾插顾名思义就是在链表的最后一个节点处再插入一个节点
我们需要考虑以下两种情况：
1.0 链表是空的
2.0 链表不是空的
但是无论是哪种我们都需要创造出一个新的节点为了使用方便，我们编写一个函数来是实现
SLTNode* BuySLTNode(SLTDataType x) //创建一个节点
{
SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
node->data = x;
node->next = NULL;
return node;
}
以下就是典型的错误，没考虑链表为空，发生空指针问题，程序崩溃
链表是空的，没有尾，如果链表不是空，链接到后面，如果链表是空，创建一个节点
改进之后的代码
void SListPushBack(SLTNode* plist, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
//分链表是空和非空两种情况
if (plist == NULL)
{
plist = newnode;
}
else
{
//先遍历找尾
SLTNode* tail = plist;
while (tail != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
但是在我们改进之后发现程序仍然崩溃
下图是在尾插函数中，通过调试我们发现，在尾插函数（SListPushBack）中，newnode（创造的新节点）赋给了plist
但是当我们出了函数作用域后，通过调试我们发现pilst仍然为空，并没有将newnode 赋给plist
这是为什么呢？
这个地方存在着一个传值的问题
解释如下图
看到这里想必大家仍然有点有点懵逼
接下来以另一种方式解释：
假设我们要改变一个数子，采用以下代码，最终我们发现这样是改变不了的，输出结果仍然是2
#include<stdio.h>
void change(int num)
{
int a = 5;
num = a;
}
int main()
{
int num=2;
printf("%d \n",num );
change(num);
printf("%d \n",num );
}
这就类似于上述尾插，只不过在尾插当中主函数里创建的就是指针，尾插函数中传的形参也是指针，这样还是相当于传值，所以形参的改变并不会影响实参的改变。
接下来用更容易理解的方法解释：
（通过经典的交换来解释）
如果要实现交换两个数要实参需要传它们的地址，而形参就需要两个指针接收
int a, int b;
swap(&a, &b);
void swap(inta,intb);
同样，如果我们将交换数字变为交换两个指针，实参就要传指针的地址，也就是说交换函数中形参需要二级指针接受实参
int *a,int *b;
swap(&a,&b);
void swap(**a,**b)；
代码最终改进为：
ps: 对二级指针解引用就是 plist
void SListPushBack(SLTNode** pplist, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
//分链表是空和非空两种情况
if (*pplist == NULL)
{
*pplist = newnode;
}
else
{
//先遍历找尾
SLTNode* tail = *pplist;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
总结：改变第一个节点的值传二级指针 不改变第一个节点的值传一级指针
头插的实现：
第一步：需要将新节点的next指向下一个节点
第二步：plist指向newnode(同样需要二级指针)
void SListPushFront(SLTNode** pplist, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pplist;
*pplist = newnode;
}
尾删的实现：
void SListPopBack(SLTNode* plist)
{
SLTNode* tail = plist;
while (tail->next != NULL)
{
tail = tail->next;
}
free(tail);
tail = NULL;
}
很多人都会这样写，但这样是错的。错误之处在于没考虑1.链表是空链表， 2.没将tail前一个节点指向NULL
改进后的代码及思路如下图所示，设置一个prev
但是这只是理想情况
实际中还存在以下两种情况
根据分析尾删同样需要二级指针，以下是最终代码
void SListPopBack(SLTNode** pplist)
{
//1.0 没有节点
//2.0 1个节点
//3.0 多个节点
if (*pplist==NULL)
{
return; //啥也不敢， 同时也可以用断言，把这种情况断死
}
else if ((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
SLTNode* prev = NULL;
SLTNode* tail = *pplist;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
}
头删的实现，类比尾删的思路，同样存在三种情况：
1.0 无节点
2.0只有一个节点
3.0有多个节点
void SListPopFront(SLTNode** pplist)
{
if (*pplist == NULL)
{
return;
}
else if ((*pplist)->next==NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
SLTNode* prev = *pplist;
*pplist = (*pplist)->next;
free(prev);
prev = NULL;
}
}
到此一个单向不带头不循环的链表已经实现。
完整代码展示：
SList.h部分
#pragma once
#include<stdio.h>
#include<stdlib.h>
//链表单独开空间，地址是随机的
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
//一个节点就是一个结构体
//链表的节点（有一个数据域和一个指针域）
//指针指向下一个节点，就是他自己的类型
//单向+不带头+循环
//不改变传一级指针，要改变传二级指针
void SListPushBack(SLTNode** pplist,SLTDataType x); //plist存的就是第一个有效数据的节点
void SListPushFront(SLTNode* pplist, SLTDataType x);
void SListPopBack(SLTNode** pplist);
void SListPopFront(SLTNode** pplist);
void SListPrint(SLTNode* plist);
SList.c 部分
#include "SList.h"
void SListPrint(SLTNode* plist)
{
SLTNode* cur = plist;
while (cur != NULL)
{
printf("%d-> ", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
SLTNode* BuySLTNode(SLTDataType x) //创建一个节点
{
SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
node->data = x;
node->next = NULL;
return node;
}
void SListPushBack(SLTNode** pplist, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
//分链表是空和非空两种情况
if (*pplist == NULL)
{
*pplist = newnode;
}
else
{
//先遍历找尾
SLTNode* tail = *pplist;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void SListPushFront(SLTNode** pplist, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pplist;
*pplist = newnode;
}
void SListPopBack(SLTNode** pplist)
{
//1.0 没有节点
//2.0 1个节点
//3.0 多个节点
if (*pplist==NULL)
{
return; //啥也不敢， 同时也可以用断言，把这种情况断死
}
else if ((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
SLTNode* prev = NULL;
SLTNode* tail = *pplist;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
}
void SListPopFront(SLTNode** pplist)
{
if (*pplist == NULL)
{
return;
}
else if ((*pplist)->next==NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
SLTNode* prev = *pplist;
*pplist = (*pplist)->next;
free(prev);
prev = NULL;
}
}
test.c部分
#include"SList.h"
void TestSList1()
{
SLTNode* plist = NULL;
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPrint(plist);
SListPushFront(&plist, 0);
SListPrint(plist);
SListPopFront(&plist);
SListPrint(plist);
SListPopFront(&plist);
SListPrint(plist);
}
int main()
{
TestSList1();
}
代码演示：
