目录
一、什么是链表
二、单链表的实现
1、动态申请一个结点
2、单链表打印
3、单链表尾插
4、单链表的尾删
5、单链表的头插
6、单链表头删
7、单链表查找
8、单链表在pos位置之后插入x
9、单链表删除pos位置之后的值
10、单链表在pos位置之前插入x
11、单链表删除pos位置的值
12、销毁链表
三、源代码
1、SList.h
2、SList.c
3、test.c
一、什么是链表
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
单链表的声明如下：
-
//声明单链表
-
typedef
struct SListNode
-
{
-
SLTDataType data;
-
struct SListNode* next;
-
}SLTNode;
链表的逻辑结构：
链表的物理结构：
注意：
1、从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续。
2、现实中的结点一般都是从堆上申请出来的。
3、从堆上申请空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。
假设在32位系统上，结点中值域为int类型，则一个节点的大小为8个字节，则也可能有下述链表：
每个链表都是由一节节的链结组成的，我们称之为节点。其中，每一个节点都是由两部分组成的，存储数据的部分叫做数据域，存储地址的部分叫做指针域。指向第一个节点的指针称之为头指针。
二、单链表的实现
1、动态申请一个结点
在链表中插入一个数据，首先需要先动态申请一个结点，并将该结点的数值域与指针域进行赋值，指针域都设置为NULL。
-
//动态申请一个节点
-
SLTNode* BuySLTNode(SLTDataType x)
-
{
-
SLTNode* newnode = (SLTNode*)malloc(
sizeof(SLTNode));
-
if (newnode == NULL)
-
{
-
perror(
"malloc fail");
-
exit(
-1);
-
}
-
newnode->data = x;
-
newnode->next = NULL;
-
return newnode;
-
}
2、单链表打印
在这里我的思路是用while循环将链表遍历一遍，从首个结点开始移动，直到NULL结束。
-
//打印链表
-
void SLTPprint(SLTNode* phead)
-
{
-
SLTNode* cur = phead;
-
while (cur != NULL)
-
{
-
printf(
"%d->", cur->data);
-
cur = cur->next;
-
}
-
printf(
"NULL\n");
-
}
3、单链表尾插
尾插就需要我们先动态开辟一个新的节点 。然后让前面的指针指向新的节点。但是要分两种情况如下图所示：
因为链表为NULL时，plist指针指向的是空，此时不能进行解引用操作，所以如果为NULL时，直接进行赋值就行。当链表不为空时，直接在后面进行尾插。
注意：
在这里使用的是二级指针，因为需要改变结构体里面的数值，而头指针是一个结构体类型的指针，而指针也是一种变量。假设我们用的是一级指针，当链表为空，我们进行尾插的时候，我们会将头指针内的数据改为新节点的地址。我们可以找到，一级指针的传递方式不会引起实参的变化。因此，当此函数结束后，我们的头指针依旧是空。因此，我们这里需要传入的是二级指针，从而实现地址传递。
-
//尾插
-
void SLTPushBack(SLTNode** pphead, SLTDataType x)
-
{
-
SLTNode* newnode = BuySLTNode(x);
-
if (*pphead == NULL)
-
{
-
*pphead = newnode;
-
}
-
else
-
{
-
SLTNode* tail = *pphead;
-
//找尾
-
while (tail->next)
-
{
-
tail = tail->next;
-
}
-
tail->next = newnode;
-
}
-
}
4、单链表的尾删
在这里首先要要声明一下，保证链表不为空，然后再分两种情况：(1)如果链表长度大于1时，只需要将倒是第二个节点的指针域设置为空指针，并且将最后一个节点释放掉。(2)如果链表长度为1时，只需将头指针置空，第一个节点释放掉就行。
-
//单链表尾删
-
void SLTPopBack(SLTNode** pphead)
-
{
-
//暴力的检查
-
assert(*pphead);
-
if ((*pphead)->next == NULL)
-
{
-
free(*pphead);
-
*pphead = NULL;
-
}
-
else
-
{
-
SLTNode* tail = *pphead;
-
while (tail->next->next)
-
{
-
tail = tail->next;
-
}
-
free(tail->next);
-
tail->next = NULL;
-
}
-
}
5、单链表的头插
头插也是先要开辟一个新的节点，然后直接让新节点的next链接到头节点上，最后重新更新一下头节点。
-
//头插
-
void SLTPushFront(SLTNode** pphead, SLTDataType x)
-
{
-
SLTNode* newnode = BuySLTNode(x);
-
newnode->next = *pphead;
-
*pphead = newnode;
-
}
6、单链表头删
头删首先还是要声明一下，保证链表不为空，然后保存头指针指向指针域中所对的地址空间，最后释放头节点即可。
-
//头删
-
void SLTPopFront(SLTNode** pphead)
-
{
-
assert(*pphead);
-
SLTNode* next = (*pphead)->next;
-
free(*pphead);
-
*pphead = next;
-
}
7、单链表查找
直接用while循环将链表遍历一遍。注意返回值返回的是空指针或者所查元素的地址。
-
//查找
-
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
-
{
-
SLTNode* cur = phead;
-
while (cur)
-
{
-
if (cur->data == x)
-
{
-
return cur;
-
}
-
else
-
cur = cur->next;
-
}
-
return NULL;
-
}
8、单链表在pos位置之后插入x
在pos位置之后插入x时，pos位置所对的节点的指针域中就记录了后面的节点位置。因此可以直接插入x所对应的节点。
-
//在pos之后插入x
-
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
-
{
-
assert(pos);
-
SLTNode* newnode = BuySLTNode(x);
-
newnode->next = pos->next;
-
pos->next = newnode;
-
}
9、单链表删除pos位置之后的值
在删除pos位置之后的节点时，如果pos->next为空时，说明pos位置就是最后一个节点，它的后面已经没有节点了，所以直接返回即可，如果pos->next不为空时，要保存住这个位置，然后重新链接pos->next = pos->next->next(就相当于下面代码中pos->next = nextNode->next)，最后释放pos->next。
-
//删除pos之后的值
-
void SLTEraseAfter(SLTNode* pos)
-
{
-
assert(pos);
-
if (pos->next == NULL)
-
{
-
return;
-
}
-
else
-
{
-
SLTNode* nextNode = pos->next;
-
pos->next = nextNode->next;
-
free(nextNode);
-
}
-
}
10、单链表在pos位置之前插入x
在pos位置前面插入新的节点，分两种情况：(1)如果pos的位置就是头节点时，就相当于头插。(2)如果pos位置不是头节点时，要找到pos位置原链表的前方的节点。然后让该节点指向所插入的节点，然后让所插入的节点指向pos所对的节点。
-
//在pos之前插入x
-
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
-
{
-
assert(pos);
-
if (*pphead == pos)
-
{
-
SLTPushFront(pphead, x);
-
}
-
else
-
{
-
SLTNode* prev = *pphead;
-
while (prev->next != pos)
-
{
-
prev = prev->next;
-
}
-
SLTNode* newnode = BuySLTNode(x);
-
prev->next = newnode;
-
newnode->next = pos;
-
}
-
}
11、单链表删除pos位置的值
删除pos位置的节点，分两种情况：(1)如果pos的位置就是头节点时，就相当于头删。(2)如果pos的位置不是头节点时，先保存pos位置后面的节点，然后让该节点链接pos位置之前的节点，最后再释放掉pos位置的节点。
-
//删除pos位置的数据
-
void SLTErase(SLTNode** pphead, SLTNode* pos)
-
{
-
assert(pos);
-
if (pos == *pphead)
-
{
-
SLTPopFront(pphead);
-
}
-
else
-
{
-
SLTNode* prev = *pphead;
-
while (prev->next != pos)
-
{
-
prev = prev->next;
-
}
-
prev->next = pos->next;
-
free(pos);
-
}
-
}
12、销毁链表
销毁链表的时候，我们不能简单只释放头指针。这样是没有将空间完全释放掉的，这只是释放了头节点。所以可以设置一个指针cur，让它用while循环将链表从头到尾都释放一遍，最后将头指针设置为空。一定要将头指针设置为空指针！否则会出现野指针的问题！
-
//销毁
-
void SLTDestroy(SLTNode** pphead)
-
{
-
SLTNode* cur = *pphead;
-
while (cur)
-
{
-
SLTNode* next = cur->next;
-
free(cur);
-
cur = next;
-
}
-
*pphead = NULL;
-
}
三、源代码
1、SList.h
-
#pragma once
-
#include <stdio.h>
-
#include <stdlib.h>
-
#include <assert.h>
-
-
-
typedef
int SLTDataType;
-
-
//声明单链表
-
typedef
struct SListNode
-
{
-
SLTDataType data;
-
struct SListNode* next;
-
}SLTNode;
-
-
//动态申请一个节点
-
SLTNode* BuySLTNode(SLTDataType x);
-
//创建循环节点
-
SLTNode* CreateSList(
int n);
-
//打印链表
-
void SLTPprint(SLTNode* phead);
-
//查找
-
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
-
-
//尾插尾删
-
void SLTPushBack(SLTNode** pphead, SLTDataType x);
-
void SLTPopBack(SLTNode** pphead);
-
//头插头删
-
void SLTPushFront(SLTNode** pphead, SLTDataType x);
-
void SLTPopFront(SLTNode** pphead);
-
-
-
//在pos之后插入x
-
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
-
//删除pos之后的值
-
void SLTEraseAfter(SLTNode* pos);
-
-
//在pos之前插入x
-
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
-
-
//删除pos位置的数据
-
void SLTErase(SLTNode** pphead, SLTNode* pos);
-
-
//销毁
-
void SLTDestroy(SLTNode** pphead);
2、SList.c
-
#include "SList.h"
-
-
//动态申请一个节点
-
SLTNode* BuySLTNode(SLTDataType x)
-
{
-
SLTNode* newnode = (SLTNode*)malloc(
sizeof(SLTNode));
-
if (newnode == NULL)
-
{
-
perror(
"malloc fail");
-
exit(
-1);
-
}
-
newnode->data = x;
-
newnode->next = NULL;
-
return newnode;
-
}
-
-
//创建循环节点
-
SLTNode* CreateSList(
int n)
-
{
-
SLTNode* phead = NULL, * ptail = NULL;
-
for (
int i =
0; i < n; i++)
-
{
-
SLTNode* newnode = BuySLTNode(i);
-
if (phead == NULL)
-
{
-
ptail = phead = newnode;
-
}
-
else
-
{
-
ptail->next = newnode;
-
ptail = newnode;
-
}
-
}
-
return phead;
-
}
-
-
//打印链表
-
void SLTPprint(SLTNode* phead)
-
{
-
SLTNode* cur = phead;
-
while (cur != NULL)
-
{
-
//printf("[%d | %p]->", cur->data, cur->next);
-
printf(
"%d->", cur->data);
-
cur = cur->next;
-
}
-
printf(
"NULL\n");
-
}
-
//尾插
-
void SLTPushBack(SLTNode** pphead, SLTDataType x)
-
{
-
SLTNode* newnode = BuySLTNode(x);
-
if (*pphead == NULL)
-
{
-
*pphead = newnode;
-
}
-
else
-
{
-
SLTNode* tail = *pphead;
-
//找尾
-
while (tail->next)
-
{
-
tail = tail->next;
-
}
-
tail->next = newnode;
-
}
-
}
-
void SLTPopBack(SLTNode** pphead)
-
{
-
//暴力的检查
-
assert(*pphead);
-
if ((*pphead)->next == NULL)
-
{
-
free(*pphead);
-
*pphead = NULL;
-
}
-
else
-
{
-
SLTNode* tail = *pphead;
-
while (tail->next->next)
-
{
-
tail = tail->next;
-
}
-
free(tail->next);
-
tail->next = NULL;
-
}
-
}
-
//头插
-
void SLTPushFront(SLTNode** pphead, SLTDataType x)
-
{
-
SLTNode* newnode = BuySLTNode(x);
-
newnode->next = *pphead;
-
*pphead = newnode;
-
}
-
//头删
-
void SLTPopFront(SLTNode** pphead)
-
{
-
assert(*pphead);
-
SLTNode* next = (*pphead)->next;
-
free(*pphead);
-
*pphead = next;
-
}
-
-
//查找
-
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
-
{
-
SLTNode* cur = phead;
-
while (cur)
-
{
-
if (cur->data == x)
-
{
-
return cur;
-
}
-
else
-
cur = cur->next;
-
}
-
return NULL;
-
}
-
-
//在pos之后插入x
-
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
-
{
-
assert(pos);
-
SLTNode* newnode = BuySLTNode(x);
-
newnode->next = pos->next;
-
pos->next = newnode;
-
}
-
-
//在pos之前插入x
-
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
-
{
-
assert(pos);
-
if (*pphead == pos)
-
{
-
SLTPushFront(pphead, x);
-
}
-
else
-
{
-
SLTNode* prev = *pphead;
-
while (prev->next != pos)
-
{
-
prev = prev->next;
-
}
-
SLTNode* newnode = BuySLTNode(x);
-
prev->next = newnode;
-
newnode->next = pos;
-
}
-
}
-
-
//删除pos之后的值
-
void SLTEraseAfter(SLTNode* pos)
-
{
-
assert(pos);
-
if (pos->next == NULL)
-
{
-
return;
-
}
-
else
-
{
-
SLTNode* nextNode = pos->next;
-
pos->next = nextNode->next;
-
free(nextNode);
-
}
-
}
-
-
//删除pos位置的数据
-
void SLTErase(SLTNode** pphead, SLTNode* pos)
-
{
-
assert(pos);
-
if (pos == *pphead)
-
{
-
SLTPopFront(pphead);
-
}
-
else
-
{
-
SLTNode* prev = *pphead;
-
while (prev->next != pos)
-
{
-
prev = prev->next;
-
}
-
prev->next = pos->next;
-
free(pos);
-
}
-
}
-
-
//销毁
-
void SLTDestroy(SLTNode** pphead)
-
{
-
SLTNode* cur = *pphead;
-
while (cur)
-
{
-
SLTNode* next = cur->next;
-
free(cur);
-
cur = next;
-
}
-
*pphead = NULL;
-
}
3、test.c
-
TestSList1()
-
{
-
SLTNode* plist = NULL;
-
SLTPushBack(&plist,
1);
-
SLTPushBack(&plist,
2);
-
SLTPushBack(&plist,
3);
-
SLTPushBack(&plist,
4);
-
SLTPushBack(&plist,
5);
-
SLTPprint(plist);
-
-
SLTPopBack(&plist);
-
SLTPprint(plist);
-
-
SLTPushFront(&plist,
100);
-
SLTPushFront(&plist,
200);
-
SLTPprint(plist);
-
-
SLTPopFront(&plist);
-
SLTPprint(plist);
-
-
SLTNode* p = SLTFind(plist,
2);
-
SLTInsertAfter(p,
30);
-
SLTPprint(plist);
-
-
p = SLTFind(plist,
1);
-
SLTEraseAfter(p);
-
SLTPprint(plist);
-
SLTDestroy(&plist);
-
-
}
-
int main()
-
{
-
TestSList1();
-
return
0;
-
}
本文要是有不足的地方，欢迎大家在下面评论，我会在第一时间更正。
老铁们，记着点赞加关注哦!!!
转载：https://blog.csdn.net/m0_63198468/article/details/128462123
查看评论