[数据结构与算法]【单链表接口实现-C语言】

前言

本文总结学习单链表的各个接口实现。

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

一、链表头文件SListNode.h

本节主要包含：结构体类型创建，函数声明，头文件包含

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <assert.h>

typedef int SLTDateType;

typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;

}SListNode;

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);

// 单链表打印
void SListPrint(SListNode* plist);

// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);

// 单链表尾插（需要传二级指针->在于是否需要改变slist）
void SListPushBack(SListNode** pplist, SLTDateType x);

// 单链表尾删（需要传二级指针->在于是否需要改变slist）
void SListPopBack(SListNode** pplist);

// 单链表头插（需要传二级指针->在于是否需要改变slist）
void SListPushFront(SListNode** pplist, SLTDateType x);

// 单链表头删（需要传二级指针->在于是否需要改变slist）
void SListPopFront(SListNode** pplist);

// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);

// 单链表在pos位置插入x
void SListInsert(SListNode** pplist, SListNode* pos, SLTDateType x);

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);

// 单链表删除pos位置的值
void SListErase(SListNode** pplist, SListNode* pos);

// 单链表销毁
void SListDestroy(SListNode** pplist);

二、链表各接口具体实现SListNode.c

本节主要包含：链表各个接口的实现方法

2.1 动态申请一个节点

SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));

	if (NULL == newnode) {
		printf("%s\n", strerror(errno));
		exit(-1);
	}
	else {
		newnode->data = x;
		newnode->next = NULL;
	}
	return newnode;
}

2.2 单链表打印

void SListPrint(SListNode* plist)
{
	if (NULL == plist) {
		printf("头指针为NULL\n");
		return;
	}
	else {
		SListNode* cur = plist;
		while (cur != NULL) {
			printf("%d->", cur->data);
			cur = cur->next;
		}
	}
	printf("NULL\n");
}

2.3 单链表查找

SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	// 写法1：
	/*SListNode* cur = plist;
	if (NULL == plist) {
		return NULL
	}
	else {
		while ((cur->data) != x) {
			cur = cur->next;
		}
	}
	if (x == (cur->data)) {  // 注意需考虑找不到的情况
		return cur;
	}
	else {
		return NULL;
	}*/

	// 写法2：（思路相同）
	if (NULL == plist) {
		// 如果传入的头指针为空，返回NULL
		return NULL;
	}
	SListNode* cur = plist;
	while (NULL != cur) {
		if (x == (cur->data)) {
			return cur;
		}
		else {
			cur = cur->next;
		}
	}
	// 如果循环结束仍然没找到返回NULL  // 注意需考虑找不到的情况
	return NULL;
}

2.4 单链表尾插（需要传二级指针->在于是否需要改变slist）

void SListPushBack(SListNode** pplist, SLTDateType x)
{
	// pplist一定不能为空
	assert(pplist);

	SListNode* newnode = BuySListNode(x);
	if (NULL == *pplist) {
		// 如果传入的头指针为空，则将创建的新节点的地址作为头指针赋值给它
		*pplist = newnode;
	}
	else {
		// 找当前的尾节点
		SListNode* cur = *pplist;
		while ((cur->next) != NULL) {
			cur = cur->next;
		}
		// 此时cur在最后一个结点
		cur->next = newnode;
	}	
}

2.5 单链表尾删（需要传二级指针->在于是否需要改变slist）

void SListPopBack(SListNode** pplist)
{
	// 特殊情况：1-空；2-一个结点；3-多个结点
	// pplist一定不能为空
	assert(pplist);

	// 也可以暴力检查为空的情况
	//assert(NULL != *pplist);
	// 温和检查
	if (NULL == *pplist) {
		// 无结点时，没得删
		printf("头指针为NULL\n");
		return;
	}
	else if (NULL == ((*pplist)->next)) {
		// 单个结点必须要单独处理！！！画图分析可得多个结点的方法对1个节点不适用
		free(*pplist);
		(*pplist) = NULL;
	}
	else {
		// 方法一：（易错）
		//SListNode* cur = *pplist;
		//while ((cur->next->next) != NULL) {
		//	cur = cur->next;
		//}
		 此时cur在倒数第二个结点
		//free(cur->next);
		//cur->next = NULL;

		// 方法二：（不易错）
		SListNode* cur = *pplist;
		SListNode* prev = NULL;
		while ((cur->next) != NULL) {
			prev = cur;
			cur = cur->next;
		}
		// 此时prev在倒数第二个结点，cur在尾结点
		prev->next = NULL;
		free(cur);
		cur = NULL;
	}
}

2.6 单链表头插（需要传二级指针->在于是否需要改变slist）

void SListPushFront(SListNode** pplist, SLTDateType x)
{
	// pplist一定不能为空
	assert(pplist);

	SListNode* newnode = BuySListNode(x);
	if (NULL == *pplist) {
		*pplist = newnode;
	}
	else {
		// 将原先头结点的地址保存起来，这样newnode->next = next和*pplist = newnode的顺序可以颠倒
		SListNode* next = *pplist;

		newnode->next = next;
		*pplist = newnode;
	}
}

2.7 单链表头删（需要传二级指针->在于是否需要改变slist）

void SListPopFront(SListNode** pplist)
{
	// pplist一定不能为空
	assert(pplist);

	if (NULL == *pplist) {
		// 头指针为空，没得删
		printf("头指针为NULL\n");
		return;
	}
	else {
		// 一个或多个结点
		// 先将原先第二个结点的地址保存起来
		SListNode* next = (*pplist)->next;
		// 先free掉头结点的空间，然后将上述保存的地址赋值给头指针
		free(*pplist);
		// 此时头指针会乱指向
		*pplist = next;
	}
}

2.8 单链表在pos位置之后插入x

// 为什么不是之前呢？-> 不知道前一个结点的地址，无法调用它对应的next，无法与pos位置结点连接
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);

	SListNode* newnode = BuySListNode(x);

	// 写法1：如果不保存pos->next，则必须按下面顺序来赋值
	/*newnode->next = pos->next;
	pos->next = newnode;*/

	// 写法2：（更推荐）先将pos->next（待插位置）保存，pos->next = newnode和newnode->next = next执行先后都可以
	SListNode* next = pos->next;
	pos->next = newnode;
	newnode->next = next;
}

2.9 单链表在pos位置插入x

// 形参需要传入头指针地址
void SListInsert(SListNode** pplist, SListNode* pos, SLTDateType x)
{
	assert(pplist);
	assert(pos);

	if (NULL == *pplist) {
		printf("头指针为NULL\n");
		return;
	}
	else if (*pplist == pos) {
		// pos在链表开头（与pos在链表中间或结尾实现方法不同）

		/*SListNode* newnode = BuySListNode(x);
		newnode->next = *pplist;
		*pplist = newnode;*/

		// 复用头插代码
		SListPushFront(pplist, x);
	}
	else {
		// pos在链表中间或结尾
		SListNode* newnode = BuySListNode(x);
		SListNode* cur = *pplist;
		while (pos != (cur->next)) {
			cur = cur->next;
		}
		// 此时cur为pos位置前一个结点地址
		cur->next = newnode;
		newnode->next = pos;
	}
}

2.10 单链表删除pos位置之后的值

// 为什么不删除pos位置 -> 不知道前一个结点的地址，无法调用它对应的next使得它和pos之后的结点连接
void SListEraseAfter(SListNode* pos)
{
	assert(pos);

	// 保存pos位置之后结点的地址（待删位置）
	SListNode* next = pos->next;
	if (next) {
		// 如果next不为NULL，才处理，小心别忽略！！！！！
		pos->next = next->next;

		free(next);
		next = NULL;
	}
	else {
		printf("pos位置之后为NULL，无法删除\n");
		return;
	}
}

2.12 单链表删除pos位置的值

// 形参需要传入头指针地址
void SListErase(SListNode** pplist, SListNode* pos)
{
	assert(pplist);
	assert(pos);

	if (NULL == *pplist) {
		printf("NULL\n");
		return;
	}
	else if(*pplist == pos){
		// pos在链表开头
		// 复用头删
		SListPopFront(pplist);
	}
	else {
		// pos在链表中间和结尾
		SListNode* cur = *pplist;
		while (pos != (cur->next)) {
			cur = cur->next;
		}
		// 此时cur为pos前一个结点的地址
		cur->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

2.11 单链表销毁

void SListDestroy(SListNode** pplist)
{
	assert(pplist);

	SListNode* cur = *pplist;
	while (NULL != cur) { // 相当while(cur)
		// 先将cur->next保存起来，将cur空间释放后，赋值给cur
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}

	*pplist = NULL;
}

三、链表接口测试test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "SListNode.h"

int main()
{
	SListNode* slist = NULL;// 空链表
	// 链表无需初始化，因为起始仅有1个头指针，为空，无结点

	// 动态申请一个节点
	SListNode* n1 = BuySListNode(1);
	SListNode* n2 = BuySListNode(2);
	SListNode* n3 = BuySListNode(3);
	SListNode* n4 = BuySListNode(4);
	SListNode* n5 = BuySListNode(5);
	slist = n1;
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = NULL;

	// 单链表打印
	SListPrint(slist);

	// 单链表尾插（需要传二级指针->在于是否需要改变slist）
	SListPushBack(&slist, 100);
	SListPrint(slist);

	// 单链表尾删（需要传二级指针->在于是否需要改变slist）
	SListPopBack(&slist);
	SListPrint(slist);

	// 单链表头插（需要传二级指针->在于是否需要改变slist）
	SListPushFront(&slist, 123);
	SListPrint(slist);

	// 单链表头删（需要传二级指针->在于是否需要改变slist）
	SListPopFront(&slist);
	SListPrint(slist);

	// 单链表在pos位置之后插入x
	SListInsertAfter(n4, 88);
	SListPrint(slist);

	// 单链表在pos位置插入x
	SListInsert(&slist, n4, 99);
	SListPrint(slist);

	// 单链表删除pos位置之后的值
	SListEraseAfter(n4);
	SListPrint(slist);

	// 单链表删除pos位置的值
	SListErase(&slist, n4);
	SListPrint(slist);

	// 单链表查找
	SListNode* ret = SListFind(slist, 2);
	if (ret) {
		// 一般结合修改或插入或删除或打印使用
		// 。。。
		ret->data = 77;
		printf("%d\n", ret->data);
	}

	// 单链表销毁
	SListDestroy(&slist);

	return 0;
}

总结

这里对文章进行总结：
以上就是今天总结的内容，本文包括了C语言实现单链表各个接口，分享给大家。
真💙欢迎各位给予我更好的建议，欢迎访问！！！小编创作不易，觉得有用可以一键三连哦，感谢大家。peace
希望大家一起坚持学习，共同进步。梦想一旦被付诸行动，就会变得神圣。

欢迎各位大佬批评建议，分享更好的方法！！！🙊🙊🙊