线性表——单链表（八千字博客看完你绝对怀疑你学的是假链表）序言：单链表：小结

60 阅读 0 评论 40 点赞

我是靠谱客的博主虚拟早晨，最近开发中收集的这篇文章主要介绍线性表——单链表（八千字博客看完你绝对怀疑你学的是假链表）序言：单链表：小结，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

序言：

单链表：

链表的概念与结构：

概念：

结构：

单链表的定义：

单链表功能实现：

打印函数

空间生成函数

尾插函数（非常重要）

头插函数

头删函数

尾删函数（注意细节）

查找函数

插入函数

删除函数

总体代码

小结

序言：

上一篇博客我们讲到了顺序表（静态、动态），大家可以阅读一下！https://mp.csdn.net/mp_blog/creation/editor/128228026

但是顺序表具有一个弊端realloc函数是空间不够就扩大多少倍，但是如果我们打个比方：原来100个空间占用，我再插入5个空间此时realloc将空间扩大到200，我们将有95个空间浪费！所以我们需要一个新的东西——链表。

单链表：

链表的概念与结构：

前面我们提到了顺序表是不能按照需求来创建需要的空间并且顺序表是有序的，而单链表是按照你的需求来创建空间，所以就有了链表的概念。

概念：

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

结构：

概念中提到了一个非常重要的部分指针链接，那么如何实现指针链接的呢？下面的关于链表的逻辑结构一定理解！非常重要！！！

由此我们可以了解到一个节点包括两部分：第一部分是你添加的数值第二部分是你下一个添加值的地址由该地址便可将其引入到下一个节点，访问下一个节点数值。但是这个时候你会发现第一个节点没有访问，所以我们需要将第一个地址存入到plist里面，就是前面我们所提及到的逻辑结构。但是我们必须要知道逻辑结构是我们自己想出来的，并没用实际的这样的地址，所以我们真实存在的是物理结构。

单链表的定义：

由上面的逻辑结构我们可以知道，每一个节点必须包含两个内容，所以我们需要定义一个结构体，如下：

typedef int SLTDataType;
struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
};
typedef struct SListNode SLTNode;

由于next是下一个节点的地址，下一个节点还是一个结构体，所以我们需要定义成结构体指针。

单链表功能实现：

单链表的功能和顺序表一样，包括打印、头插、尾插、头删、尾删、插入、删除、内存释放等内容。

打印函数

void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULLn");
}

我们可以根据我们之前所提到的为了便于我们理解而想出的逻辑结构来理解，首先将第一个节点的地址存起来，如果第一个节点地址不为空，就打印第一个节点的内容，另cur=cur->next的意思是每一个节点都包含下一个节点地址，如果下一个节点地址不是NULL就继续打印。可以根据下面的图来理解！

空间生成函数

我们前面提到了链表的特点就是按照需求生成空间，所以我们需要使用一个函数malloc扩容函数。

SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

最后我们需要返回newnode就是新生成的地址，为什么呢？我们接下来想下看就明白了！

尾插函数（非常重要）

我们想一下，如何在尾部插入一个节点呢？首先没插入之前我们末尾节点的结构体中next所指向的是NULL指针；所以我们需要把末尾的next改成指向我们新创建的空间，即上面我们所提到的newnode！

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		// 找尾节点的指针
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		// 尾节点，链接新节点
		tail->next = newnode;
	}
}

这个在里面为什么需要使用到双指针，和判断语句呢？首先双指针，我们知道形参是实参的一份临时拷贝改变形参，不会对形参具有影响！

这就是为什么使用双指针的原因。if语句是因为我们刚刚没有创建空间的时候，plist是一个NULL指针，而如果一个空指针->next就是一个野指针，所以我们要避免野指针的形成！

头插函数

如果上面我们理解了尾插函数的话，那么对于头插函数也是非常容易理解！首先将plist的地址改成我们新创建的地址newnode，然后再将新生成的节点结构体的next改成下一个节点的地址。

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);

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

头删函数

头删函数我们可以理解成一个头插函数的逆置过程，首先将第一个节点的结构体next地址（就是下一个节点的地址）给到plist，接着释放我们第一个节点就ok！

void SListPopFront(SLTNode** pphead)
{
	SLTNode* next = (*pphead)->next;
	free(*pphead);

	*pphead = next;
}

尾删函数（注意细节）

首先尾删函数我们按照头删函数的想法，我们需要将倒数第二个节点地next改成NULL；接着将最后一个节点释放！如果你是这样想的话，就是比较狭隘了，如果我们没有节点呢，如果我们就只有一个节点呢？对吧！所以我们上代码！

void SListPopBack(SLTNode** pphead)
{
	// 1、空
	// 2、一个节点
	// 3、一个以上的节点
	if (*pphead == NULL)
	{
		return;
	}
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}

		free(tail);
		prev->next = NULL;
	}
}

其中多个节点的时候单链表我们无法拿出倒数第二个节点的next的内容，所以我们需要使用双指向法拿出我们需要的地址。

查找函数

查找函数我个人觉得没啥可以说的，因为单链表，查找函数只能遍历查找，找到了就是返回该地址没找到就是返回NULL。

SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SListNode* cur = phead;
	//while (cur != NULL)
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;
	}

	return NULL;
}

插入函数

我们先来看一张图片：

根据这个图片我们可以将插入函数理解成头插和尾插的结合，首先需要将生成的新地址储存到第二个节点的next中，接着将新生成的节点的next赋值给第三个节点的地址（即第二个节点结构体的next）。

// 在pos的前面插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SLTNode* newnode = BuySListNode(x);
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		prev->next = newnode;
		newnode->next = pos;
	}
}

但是我们需要注意的是如果只有节点，那么就是prev是pos的下一个节点，这样的话就是prev永远不会等于pos这样就会导致程序崩掉！所以我们就可以把它单独拿出来考虑成头插！

删除函数

我们还是先来看一张图：

如果想要删除pos这个位置，就需要将第二个节点与第四个节点链接，那么就是需要将第二个节点的next改成第三个节点的next，再将第三个节点free掉！

// 删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	if (pos == *pphead)
	{
		SListPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		prev->next = pos->next;
		free(pos);
	}
}

但是我们还是没有考虑一直情况，如果我们删除的的第一个元素呢？我们知道我们想要删除一个数值必须要找到它前一个数值，但是第一个节点没有前一个数值，所以我们想要删除第一个数值的时候需要使用头删！

总体代码

我将代码分为三部分，函数的测试，函数的声明，函数的定义

函数声明

#pragma once
#include <stdio.h>
#include <stdlib.h>

typedef int SLTDataType;
struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
};
typedef struct SListNode SLTNode;

// 不会改变链表的头指针，传一级指针
void SListPrint(SLTNode* phead);

// 可能会改变链表的头指针，传二级指针
void SListPushBack(SLTNode** pphead, SLTDataType x);
void SListPushFront(SLTNode** pphead, SLTDataType x);
void SListPopFront(SLTNode** pphead);
void SListPopBack(SLTNode** pphead);

SLTNode* SListFind(SLTNode* phead, SLTDataType x);
// 在pos的前面插入x
void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x);
// 删除pos位置的值
void SListErase(SLTNode** phead, SLTNode* pos);

// 有些地方也有这样的
 在pos的前面插入x
//void SListInsert(SLTNode** phead, int i, SLTDataType x);
 删除pos位置的值
//void SListErase(SLTNode** phead, int i);

函数定义

#include "SList.h"

void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULLn");
}

SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		// 找尾节点的指针
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		// 尾节点，链接新节点
		tail->next = newnode;
	}
}

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);

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

void SListPopFront(SLTNode** pphead)
{
	SLTNode* next = (*pphead)->next;
	free(*pphead);

	*pphead = next;
}

void SListPopBack(SLTNode** pphead)
{
	// 1、空
	// 2、一个节点
	// 3、一个以上的节点
	if (*pphead == NULL)
	{
		return;
	}
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}

		free(tail);
		prev->next = NULL;
	}
}

SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SListNode* cur = phead;
	//while (cur != NULL)
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;
	}

	return NULL;
}

// 在pos的前面插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SLTNode* newnode = BuySListNode(x);
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		prev->next = newnode;
		newnode->next = pos;
	}
}

// 删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	if (pos == *pphead)
	{
		SListPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		prev->next = pos->next;
		free(pos);
	}
}

函数的测试

#include "SList.h"

void TestSList1()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushFront(&plist, 0);
	SListPrint(plist);

	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPrint(plist);

	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPrint(plist);
}

void TestSList2()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);

	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPrint(plist);
}

void TestSList3()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);

	// 想在3的前面插入一个30
	SLTNode* pos = SListFind(plist, 1);
	if (pos)
	{
		SListInsert(&plist, pos, 10);
	}
	SListPrint(plist);

	pos = SListFind(plist, 3);
	if (pos)
	{
		SListInsert(&plist, pos, 30);
	}
	SListPrint(plist);
}

void TestSList4()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);

	SLTNode* pos = SListFind(plist, 1);
	if (pos)
	{
		SListErase(&plist, pos);
	}
	SListPrint(plist);

	pos = SListFind(plist, 4);
	if (pos)
	{
		SListErase(&plist, pos);
	}
	SListPrint(plist);

	pos = SListFind(plist, 3);
	if (pos)
	{
		SListErase(&plist, pos);
	}
	SListPrint(plist);

	pos = SListFind(plist, 2);
	if (pos)
	{
		SListErase(&plist, pos);
	}
	SListPrint(plist);
}


int main()
{
	TestSList4();

	return 0;
}

小结

写了快八千字的博客，属实不容易，希望大家可以给个点赞、关注来支持一下，你们的支持是我坚持的动力，万分感谢！

最后

以上就是虚拟早晨为你收集整理的线性表——单链表（八千字博客看完你绝对怀疑你学的是假链表）序言：单链表：小结的全部内容，希望文章能够帮你解决线性表——单链表（八千字博客看完你绝对怀疑你学的是假链表）序言：单链表：小结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：链表
浏览次数：60 次浏览
发布日期：2023-12-02 09:55:08
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_23_o_10_f5_13_jky.html

线性表——单链表（八千字博客看完你绝对怀疑你学的是假链表）序言：单链表：小结

概述

序言：

单链表：

链表的概念与结构：

概念：

结构：

单链表的定义：

单链表功能实现：

打印函数

空间生成函数

尾插函数（非常重要）

头插函数

头删函数

尾删函数（注意细节）

查找函数

插入函数

删除函数

总体代码

小结

最后

评论列表共有 0 条评论

发表评论取消回复

线性表——单链表（八千字博客看完你绝对怀疑你学的是假链表）序言：单链表：小结

概述

序言：

单链表：

链表的概念与结构：

概念：

结构：

单链表的定义：

单链表功能实现：

打印函数

空间生成函数

尾插函数（非常重要）

头插函数

头删函数

尾删函数（注意细节）

查找函数

插入函数

删除函数

总体代码

小结

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

发表评论取消回复