C语言--数据结构：单链表

1、认知

什么是链表，顾名思义就像一个个环环相扣的圈。那我们怎么使用编程语言实现这个链表呢？以及它的作用是什么呢？

单链表是一种线性数据结构，由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。节点按顺序排列，通过指针链接在一起，形成链表。

单链表的主要作用包括：

1. 存储数据： 单链表可以用来存储各种类型的数据，例如整数、浮点数、字符串等等。

2. 动态分配内存： 单链表的节点可以动态分配内存，这意味着它可以根据需要灵活地增加或减少节点，不像数组一样需要在初始化时确定大小。

3. 插入和删除操作高效： 在单链表中，插入和删除元素的操作非常高效，只需要修改节点的指针即可，无需移动其他元素。

4. 实现其他数据结构： 单链表可以用作其他数据结构的基础，例如栈、队列等，通过在单链表上实现特定的操作即可实现这些数据结构。

5. 处理大数据集： 当需要处理大量数据，并且事先无法确定数据量大小时，单链表可以提供一种灵活的解决方案，因为它的大小可以根据需要进行动态调整。

2、原理

上图是链表的一个简图：

• data是自己定义的数据类型
• next是指向下一个节点的指针

易知，我们只需要知道第一个节点的地址就可以顺藤摸瓜找到余下节点的地址，所以我们要先创建一个节点。

以下为节点的定义：

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType date;
	struct SListNode* next;
	//
}SLTNode;

单链表由节点组成，每个节点包含两部分：数据和指针。数据存储实际数据，指针指向下一个节点。

单链表的基本操作：

• 创建链表： 动态分配内存创建节点，并将节点链接起来形成链表。

• 插入节点： 在链表的特定位置或末尾插入新节点。

• 删除节点： 删除链表中的特定节点。

• 遍历链表： 通过指针依次访问链表中的每个节点。

• 查找节点： 在链表中查找特定值的节点。

一、创建链表、插入节点

在主函数中我们创建一个指针节点，然后往链表中插入数据。

int main()
{
	SLTNode* head = NULL;
	SLTPushBack(&head, 1);
	SLTPushBack(&head, 2);
	SLTPushBack(&head, 3);
	return 0;
}

Push为插入函数插入分头插和尾插，我先讲尾插。

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* pcul =SLTBuy(x);
	SLTNode* preal = *pphead;
	if (*pphead==NULL)
	{
		*pphead= pcul;
		return;
 
	}
	while (preal->next)
	{
		preal = preal->next;
	}
	preal->next= pcul;
}

 每当我们插入数据时先调用一个Buy函数创建好节点：

SLTNode* SLTBuy(SLTDataType x)
{
	SLTNode* pret = (SLTNode*)malloc(sizeof(SLTNode));
	pret->date = x;
	pret->next = NULL;
	return pret;
}

在尾插时我们分为两种情况，当链表为空时，我们直接将创建好的节点赋值给头节点，链表不为空时，我们就要创建一个指针顺着链表走，走到头节点。while中的preal->next意思是当这个节点的next为NULL时就走出循环，这样我们就得到了指向末尾的一个指针， 然后将创建好的节点赋值给末尾就可以了

头插依旧分为两种情况  链表为空  链表不为空，链表为空也是直接赋值给头节点，不为空就先将创建好的新节点的next指向头节点，然后重新让旧头节点的指针指向新的头节点就可以。

有点绕，理解就好了，以下是头插代码：

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* nownode = SLTBuy(x);
	if (*pphead == NULL)
	{
		*pphead = nownode;
		return;
	}
	nownode->next = *pphead;
	*pphead = nownode;
 
}

二、尾删和头删

先讲尾删，就是先遍历一遍链表然后找到最后一个节点，并将其free就可以，但也分只有一个节点的情况：

void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLTNode* pre = *pphead;
	SLTNode* ptail = pre->next;
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	while (ptail->next)
	{
		pre = pre->next;
		ptail = pre->next;
	}
	pre->next = NULL;
	free(ptail);
	ptail = NULL;
}

头删依旧分两种情况  只有一个节点  和   多个节点；我们只需要删除前一个节点并将头节点向后移动一个节点就可以，但是记得向后移动头节点前先保留要删除节点的指针。

void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	SLTNode* nownode = *pphead;
	*pphead = (*pphead)->next;
	free(nownode);
	nownode = NULL;
}

剩余的查找和在指定位置删除节点，在理解了前面链表的定义最后看代码就可以理解，我就直接放出我的代码，希望可以帮你更好的理解链表。

头文件：SList.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType date;
	struct SListNode* next;
	//
}SLTNode;
 
SLTNode* SLTBuy(SLTDataType x);
 
 
void SLTPrint(SLTNode* phead);
 
//头部插入删除/尾部插入删除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
 
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);

源文件SList.c

#include"SList.h"
void SLTPrint(SLTNode* phead) {
	SLTNode* pcul = phead;
	while (pcul)
	{
		printf("%d->", pcul->date);
		pcul = pcul->next;
	}
	printf("NULL\n");
}
 
 
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* pcul =SLTBuy(x);
	SLTNode* preal = *pphead;
	if (*pphead==NULL)
	{
		*pphead= pcul;
		return;
 
	}
	while (preal->next)
	{
		preal = preal->next;
	}
	preal->next= pcul;
}
 
 
SLTNode* SLTBuy(SLTDataType x)
{
	SLTNode* pret = (SLTNode*)malloc(sizeof(SLTNode));
	pret->date = x;
	pret->next = NULL;
	return pret;
}
 
 
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* nownode = SLTBuy(x);
	if (*pphead == NULL)
	{
		*pphead = nownode;
		return;
	}
	nownode->next = *pphead;
	*pphead = nownode;
 
}
 
 
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLTNode* pre = *pphead;
	SLTNode* ptail = pre->next;
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	while (ptail->next)
	{
		pre = pre->next;
		ptail = pre->next;
	}
	pre->next = NULL;
	free(ptail);
	ptail = NULL;
}
 
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	SLTNode* nownode = *pphead;
	*pphead = (*pphead)->next;
	free(nownode);
	nownode = NULL;
}
 
 
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);
	while (phead)
	{
		if ((phead->date == x))
		{
			return phead;
		}
		phead = phead->next;
	}
	return NULL;
}
 
 
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
 
	SLTNode* nownode = SLTBuy(x);
	SLTNode* pcul = *pphead;
	if (pos == *pphead)
	{
		nownode->next = *pphead;
		*pphead = nownode;
		return;
	}
	while (pcul->next != pos)
	{
		pcul = pcul->next;
	}
	nownode->next = pcul->next;
	pcul->next = nownode;
}
 
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
 
	SLTNode* nownode = *pphead;
	SLTNode* nownode2 = NULL;
	if (pos == *pphead)
	{
		*pphead = (*pphead)->next;
		free(nownode);
		nownode = NULL;
		return;
	}
	while (nownode->next != pos)
	{
		nownode = nownode->next;
	}
	nownode2 = nownode->next;
	nownode->next = nownode->next->next;
	free(nownode2);
	nownode2 = NULL;
}
 
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* nownode = SLTBuy(x);
	nownode->next = pos->next;
	pos->next = nownode;
}
 
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
 
	SLTNode* nownode = pos->next;
	pos->next = pos->next->next;
	free(nownode);
	nownode = NULL;
}
 
void SListDesTroy(SLTNode** pphead)
{
	assert(pphead);
 
	SLTNode* pre = *pphead;
	while (*pphead != NULL)
	{
		pre = *pphead;
		*pphead = (*pphead)->next;
		free(pre);
		pre = NULL;
	}
}

test主函数文件：大家可以自行用函数测试

#include"SList.h"
int main()
{
	SLTNode* head =NULL;
	SLTPushBack(&head, 1);
	SLTPushBack(&head, 2);
	SLTPushBack(&head, 3);
	SLTPushBack(&head, 4);
	SLTPrint(head);
	SLTNode* new = SLTFind(head, 2);
	SLTInsertAfter(new, 100);
	SLTPrint(head);
	SLTEraseAfter(new);
	SLTPrint(head);
	SListDesTroy(&head);
	return 0;
}

通过本文的介绍，读者应该对C语言中的单链表有了深入的了解。单链表是一种灵活而强大的数据结构，能够在各种应用场景中发挥重要作用。掌握单链表的概念和操作，将有助于读者更好地理解和应用数据结构与算法。