在“数据结构（1）”中，我在博客中实现了顺序表的定义功能和基本功能函数。那么这篇博客我想以相同的思路来实现单链表。
单链表也是一种数据存储结构，与顺序表性比，单链表存储数据所用的空间不是连续的，在内存中是一块块零散的空间，通过指针相连。
因此，在单链表的结构体中，有两个成员：
typedef int DataType;
struct SListNode
{
DataType data;//用于存储数据
struct SListNode* next;//用于指向下一块空间
};
示意图：
当然，这是是最为简单的一种链表形式——单向无头单链表
链表一共有三个变量因素：
1. 是否带哨兵位头指针（哨兵位的数据成员data不存放实际数据内容）
2. 单向/双向
3. 循环/非循环
但是实际中，用的最多的是 单向无头非循环链表 和 双向带头循环链表。
双向带头循环链表结构最为复杂，但用起来最为方便。结构图为：
今天我们先来实现单向无头非循环链表。在下一篇博客中，再来实现双向带头循环链表。
老规矩，这次还是分为三个文件来写：
- Slist.h
- Slust.c
- Test.c
一、Slist.h
实现单链表结点的结构体：
#pragma once
typedef int DataType;
struct SListNode
{
DataType data;
struct SListNode* next;
};
我们要实现的功能函数：
//1.开辟一个新结点
//这是内部函数使用的，不属于对外开放的接口函数
struct SListNode* BuynewNode(DataType x);
//2.打印
void SListPrint(struct SListNode* plist);
//3.尾插
void SListPushBack(struct SListNode** pplist,DataType x);
//4.头插
void SListPushFront(struct SListNode** pplist, DataType x);
//5.尾删
void SListPopBack(struct SListNode** pplist);
//6.头删
void SListPopFront(struct SListNode** pplist);
//7.查找
struct SListNode* SListFind(struct SListNode* plist, DataType x);
//8.指定位置的后面插入
void SListInsertAfter(struct SListNode** pplist, DataType x);
//9.指定位置前面插入
void SListInsertBefore(struct SListNode** pplist, struct SListNode* pos, DataType x);
//10.删去指定位置的后一个结点
void SListEreaseAfter(struct SListNode* pos);
二、Slist.c
1.开辟一个新结点
struct SListNode* BuynewNode(DataType x)
{
struct SListNode* node = (struct SListNode*)malloc(sizeof(struct SListNode));
node->data = x;
node->next = NULL;
return node;
}
2.打印
void SListPrint(struct SListNode* plist)
{
struct SListNode* cur = plist;
while (cur != NULL)
{
printf("%d->",cur->data);
cur = cur->next;
}
printf("NULL");
printf("\n");
}
3.尾插
void SListPushBack(struct SListNode** pplist, DataType x)
{
//第一步：创建一个新结点,malloc开辟
struct SListNode* newNode = BuynewNode(x);
//第二步：先判断给的链表是非为NULL
//若为空，则直接将新结点赋给plist;若为非空，则先遍历找出尾再串接
if (*pplist == NULL)
{
*pplist = newNode;
}
else
{
struct SListNode* tail = *pplist;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newNode;
}
}
4.头插
示意图：
void SListPushFront(struct SListNode** pplist, DataType x)
{
//头插比尾插要方便很多，因为省去了找尾的过程
struct SListNode* newNode = BuynewNode(x);
newNode->next = *pplist;
//这一步很关键*pplist一直都是头，所以头插后，最后一步要把新结点赋给*pplist
*pplist = newNode;
}
5.尾删
示意图：
//尾删时，先要把原链表的最后一个数据空间释放掉，再让最后一个的前一个的next指针指向NULL
void SListPopBack(struct SListNode* plist)
{
struct SListNode* prev = NULL;
struct SListNode* tail = plist;
while (tail->next != NULL)
{
prev = tail;
tail = tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
但是会发现上面的这种尾删的写法对于 链表为空 和 链表中只有一个结点 这两种情况都不成立。
- 当链表为空时，plist为空指针，程序中将plist赋给tail然后使用tail->next会导致程序崩溃；
- 当链表中只有一个节点时，第一次while循环的判断条件就不满足，直接跳过while循环，因此prev的值没有改变，始终为NULL,那最后prev->next就会导致程序崩溃。
因此我们要将这两种情况单独列出来讨论：
void SListPopBack(struct SListNode** pplist)
{
if (*pplist == NULL)
{
return;
}
else if ((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
struct SListNode* prev = NULL;
struct SListNode* tail = pplist;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
}
6.头删
void SListPopFront(struct SListNode** pplist)
{
//链表为空的情况分开讨论
if (*pplist == NULL)
{
return;
}
//这里对链表中有一个结点和多个结点的情况都适用
else
{
//在删除*pplist前，必须先保存一份*pplist->next
struct SListNode* next = (*pplist)->next;
free(*pplist);
*pplist = next;
}
}
7.查找
struct SListNode* SListFind(struct SListNode* plist, DataType x)
{
struct SListNode* cur = plist;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
8.指定位置的后面插入
示意图：
注意：step1和step2不能调换。若先让*ppos的next指向新开辟结点，那最后一步的pos->next就找不到原链表中的下一个结点了
void SListInsertAfter(struct SListNode** ppos, DataType x)
{
assert(*ppos);
struct SListNode* newNode = BuynewNode(x);
newNode->next = (*ppos)->next;//相当于先保存原链表的next
(*ppos)->next = newNode;
}
9.指定位置前面插入
指定位置前插比后插少麻烦一些，因为有一个遍历找*ppos的过程。
void SListInsertBefore(struct SListNode** pplist, struct SListNode* pos, DataType x)
{
assert(pos);
struct SListNode* newNode = BuynewNode(x);
//只有一个结点时，等价于头插
if (pos == *pplist)
{
newNode->next = *pplist;
*pplist = newNode;
}
else
{
struct SListNode* prev = NULL;
struct SListNode* cur = *pplist;
while (cur != pos)
{
prev = cur;
cur = cur->next;
}
prev->next = newNode;
newNode->next = cur;
}
}
10.指定位置后面删除
思路图：
但是如果pos的下一个结点，即tmpNode为空，那程序中的tmpNode->next又会导致程序崩溃。因此要将这种情况单独讨论。
void SListEreaseAfter(struct SListNode* pos)
{
assert(pos);
if (pos->next == NULL)
{
return;
}
else
{
struct SListNode* tmpNode = pos->next;
pos->next = tmpNode->next;
free(tmpNode);
}
}
3.Test.c
在这个文件中，我们可以根据自己需要编写代码来调用这个单链表：
void TestSList1()
{
struct SListNode* plist = NULL;
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPrint(plist);
SListPushFront(&plist, 0);
SListPushFront(&plist, -1);
SListPushFront(&plist, -2);
SListPushFront(&plist, -3);
SListPrint(plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListPrint(plist);
SListPopFront(&plist);
SListPopFront(&plist);
SListPopFront(&plist);
SListPrint(plist);
}
void TestSList2()
{
struct SListNode* plist = NULL;
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPrint(plist);
printf("现在，我想寻找值为3的结点:\n");
struct SListNode* tmp=SListFind(plist, 3);
if (tmp == NULL)
{
printf("找不到\n");
}
else
{
printf("找到了,现修改其值:");
tmp->data = 30;
SListPrint(plist);
}
printf("在位置后面插入值：");
SListEreaseAfter(tmp);
SListPrint(plist);
printf("在位置前面插入值：");
SListInsertBefore(&plist, tmp, 100);
SListPrint(plist);
}
int main()
{
TestSList1();
TestSList2();
return 0;
}