C语言链表的含义与链表数据操作代码详解！

一，链表的含义

1，火车引例

        在讲解开始前，我们先来看一张图片：

        如图我们可以看到一列火车，它由车头和车厢组成，同时由链条连接，从整个火车我们可以看出，前一节的车厢尾总有着一个链条，让它紧密与后一个车厢相连。这样，如果我们找到了前一个车厢，那么我们就可以同时通过这条链子找到下一节车厢。而在数据结构中，这样有着“火车”一样的结构，通过某种方式将数据（车厢）节节相连的线性表，就叫做链表。

2，链表的概念与图解

        链表与顺序表不同，虽然他们都属于线性表的一种，但是链表的特点却不同于顺序表。链表是一种逻辑结构连续，但物理结构不连续的数据储存结构。它由一个个节点组成，而每个节点由它所储存的数据和下一个结点的地址组成。由下图所示：

        图中所表示的就是一个简单的链表，它们都储存着各自的数据，并且储存着下一个节点的地址，而最后一个节点的地址被我们置空。由此可见，链表虽然在物理结构上看似散乱分布，但是它们却被一条名为“地址”的链子连接起来，让我们可以通过上一个节点而找到下一个节点。

        所以有了上面的详细解释之后，那么我们如果想定义一个链表，就易如反掌了。

typedef int SLDataType;//重命名数据类型，方便以后更改储存的数据类型
typedef struct SListNode
{
	SLDataType data;//链表所储存的数据
	struct SListNode* next;//下一个结点的地址
}SLD;//将链表改名为SLD

二，链表操作函数准备

        老样子，就像我们之前讲的顺序表操作函数的实现一样，我们都需要生成三个文件。

        然后我们需要在SList.h文件中完成我们可能用到的头文件的包含

#include<stdio.h>
#include<assert.h>//assert断言用于判断链表是否为空
#include<stdlib.h>//会用到malloc函数创建空间

三，链表操作函数的实现

1，链表打印函数

        所谓链表的打印，就是通过链表的地址为路径，依次将链表所储存的数据打印出来。这个链表打印实现函数我们将于SList.c中进行实现。

//链表的打印
void SLDPrint(SLD* phead)
{
	while (phead)//phead!=NULL;
	{
		printf("%d->", phead->data);//打印数据
		phead = phead->next;//下一个节点
	}
	printf("NULL\n");
}

        我们将该函数命名为SLDPrint（）。它通过while循环进行链表数据的打印，每进行一次打印，phead就为被重新赋值为该节点所储存的地址（也就是下一个结点的地址），当phead到达最后一个节点并完成打印时，phead就会被赋值为NULL，从而跳出while循环，打印结束。

        所以我们将该函数在SList.h中声明，并于test.c中测试。

        测试函数代码如下：

#include"SList.h"
void test()
{
	SLD* node1 = (SLD*)malloc(sizeof(SLD));//使用malloc函数申请一个结构体的空间
	node1->data = 1;//为结构体中的数据赋值
	SLD* node2 = (SLD*)malloc(sizeof(SLD));
	node2->data = 2;
	SLD* node3 = (SLD*)malloc(sizeof(SLD));
	node3->data = 3;
	SLD* node4 = (SLD*)malloc(sizeof(SLD));
	node4->data = 4;
	node1->next = node2;//将链表一个一个的使用地址连起来
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;//最后一个节点所储存的地址赋值为NULL
	SLD* plist = node1;//给plist赋值为node1的地址
	SLDPrint(plist);//开始打印！
}

        于是我们代码走起来，结果如下：

        链表打印函数实现成功！

2，链表尾插函数

        码如其名，该函数的作用就是在链表的最后插入一个新的节点（这个函数是我们刚接触链表数据改变的第一个函数，可能较难理解，可一旦理解这个函数，后面的函数对你来说就不在话下了）。话不多说，我们先上图解释：

        难点1：由图可知，要进行链表的尾插操作，我们就需要首先创造出来一个新的节点，来储存新数据x的值，同时因为是尾插，所以我们同时还应该将新的尾节点所储存的地址初始化为NULL。所以我们应该于SList.c函数中写一个创建新节点的函数SLDCreatNode（）函数 。

//创建一个新结点
SLD* SLDCreatNode(SLDataType x)
{
	SLD* newnode = (SLD*)malloc(sizeof(SLD));//malloc函数创建一个新节点
	if (newnode==NULL)//判断是否内存申请成功
	{
		perror("malloc fail!");
		exit(1);//非正常退出
	}
	newnode->data = x;//为节点data赋值
	newnode->next = NULL;//将节点的next值置空
	return newnode;//返回节点地址
}

        该函数的返回值就是新创建节点结构体的地址。函数中我们使用malloc函数申请一个节点结构体的空间，然后将该节点所储存的数据初始化为x，后将该节点所储存的地址置空。

        难点2：既然我们想要对链表进行尾插，那么我们总得找到当前链表最后一个节点吧。所以我们将设计一个SLDptail（）函数，来找到链表的最后一个节点：

//寻找尾节点
SLD* SLDptail(SLD* phead)/传给该函数首节点的地址
{
	assert(phead);//防止空链表
	SLD* ptail = phead;
	while (ptail->next != NULL)//利用最后一个节点所储存的地址为NULL的特点
	{
		ptail = ptail->next;//ptail依次往后走
	}
	return ptail;//返回最后一个节点的地址
}

        这样，通过while循环，我们就找到了链表尾节点的地址。 

        难点3：这也是本函数比较烧脑的地方。让我们仔细想一想，如果我们如下定义函数形参，会发生什么问题？

void SLDPushBack(SLD* pphead,SLDataType x)

        如果我们这样设计函数，那么该函数在使用时进行一份临时拷贝，编译器则会在另一个完全不同的空间中进行链表的尾插，而你原来的链表不会有任何变化。所以我们需要使用二级指针，进行节点地址的地址的传址调用，从而完成对原来链表内容的改变。所以我们如下定义：

void SLDPushBack(SLD** pphead, SLDataType x)

        所以各个符号所表示的含义如下：

        在这些难点攻克之后，其实想要写出链表尾插函数就十分简单了，代码如下：

//链表的尾插
void SLDPushBack(SLD** pphead, SLDataType x)
{
	assert(pphead);
	SLD* newnode = SLDCreatNode(x);//创建一个新节点
	//讨论情况：空链表与非空链表
	if (*pphead == NULL)//空链表
	{
		*pphead = newnode;
	}
	else//非空链表
	{
		//找到尾节点
		SLD* ptail = SLDptail(*pphead);
		ptail->next = newnode;
	}
}

        我们首先创造一个新节点newnode。如果链表为空，那么我们就直接将newnode的地址设为链表首节点的地址，节点插入成功；如果链表不为空，我们就先使用SLDptail()函数找到尾节点，再将尾节点所储存的地址赋值为newnode的地址，这样就尾插成功了！

        我们将此函数声明后，于test.c中测试，代码如下：

#include"SList.h"
void test()
{
	SLD* plist = NULL;
	SLDPushBack(&plist, 1);//进行尾插
	SLDPushBack(&plist, 2);
	SLDPushBack(&plist, 3);
	SLDPushBack(&plist, 4);
	SLDPrint(plist);//对链表进行打印
}

        代码走起来，结果如图：

        链表尾插函数实现成功！

3，链表头插函数

        头插头插，就是在链表的第一个节点之前再插入一个新节点，让新节点成为链表的首节点。而我想说的是，这个函数十分简单！！！

        如图所示，我们只需要将这个新创建的节点所储存的地址赋值为原来链表首节点的地址就可以了，完全不需要像顺序表一样进行什么数据的移位操作。所以于SList.c中，该函数代码如下：

//链表的头插
void SLDPushFront(SLD** pphead, SLDataType x)
{
	assert(pphead);
	SLD* newnode = SLDCreatNode(x);//创建一个新节点
	newnode->next = *pphead;//将新节点所储存的地址赋值为原来链表首节点的地址
	*pphead = newnode;//将newnode视为新的第一个节点
}

        根据之后我们的分析可得，这个函数对于空链表也同样适用。那让我们声明该函数之后在test.c中测试一下吧！

#include"SList.h"
void test()
{
	SLD* plist = NULL;
	SLDPushBack(&plist, 1);//进行尾插
	SLDPushBack(&plist, 2);
	SLDPushBack(&plist, 3);
	SLDPushBack(&plist, 4);
	SLDPushFront(&plist, 5);//进行头插
	SLDPrint(plist);//对链表进行打印
}

        代码我们走起来，结果如下：

        链表头插函数实现成功！

4，链表尾删函数

        链表的尾删函数，无非就主要分为两种操作：1，将链表最后的一个节点空间释放掉，并且将最后一个节点所保存的地址置为空；2，将原本倒数第二个节点所保存的地址置为空。我们画图解释更清楚。

        同时我们也应该创建一个pre结构体指针，用于保存倒数第二个节点的地址。但我们也不能忘了讨论当链表只有一个节点的情况。若链表只有一个节点，那么则满足表达式(（*pphead）->next==NULL)，所以我们直接将第一个节点释放掉并且将第一个节点的地址置空。那么完整的代码如下：

//链表的尾删
void SLDDeleteBack(SLD** pphead)
{
	assert(pphead);
	assert(*pphead);
	//只有一个节点时
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else//有多个节点时
	{
		//先找到尾部节点并且保存尾节点之前的一个节点的地址
		SLD* ptail = *pphead;
		SLD* pre = *pphead;
		while (ptail->next)
		{
			pre = ptail;
			ptail = ptail->next;
		}
		pre->next = NULL;//尾节点前的一个节点的next置空
		free(ptail);//释放尾节点空间
		ptail = NULL;//防止野指针的出现
	}
}

        先声明后测试：

#include"SList.h"
void test()
{
	SLD* plist = NULL;
	SLDPushBack(&plist, 1);//进行尾插
	SLDPushBack(&plist, 2);
	SLDPushBack(&plist, 3);
	SLDPushBack(&plist, 4);
	SLDPushFront(&plist, 5);//进行头插
	SLDDeleteBack(&plist);//进行尾删
	SLDPrint(plist);//对链表进行打印
}

        结果如下图所示：

        链表尾删函数实现成功！ 

5，链表头删函数

        链表的头删函数与链表的头插函数的难度十分相似，都非常简单！我们所需要做的就是要释放掉第一个节点的空间并且将第二个节点的地址赋值为第一个节点的地址。但是我们需要先注意，不可以先释放头节点，因为这样可能导致我们找不到第二个节点。我们画图看一下吧：

所以代码如下：

//链表的头删
void SLDDeleteFront(SLD** pphead)
{
	//链表不为空
	assert(pphead && *pphead);
	SLD* next = (*pphead)->next;//将头节点所储存的地址命名为next
	free(*pphead);//释放掉头节点的空间
	*pphead = next;//将第二个节点变为头节点
}

        该代码中，我们首先将next赋值为第一个节点所储存的地址（也就是第二个结点的地址），这样，在保证第二个节点的地址可以被找到的情况下，我们释放掉第一个节点的空间。然后我们再将表示第一个节点的地址的*pphead赋值为next，标志着第二个节点正式成为第一个节点。

        所以我们先声明后测试，测试代码如下：

#include"SList.h"
void test()
{
	SLD* plist = NULL;
	SLDPushBack(&plist, 1);//进行尾插
	SLDPushBack(&plist, 2);
	SLDPushBack(&plist, 3);
	SLDPushBack(&plist, 4);
	SLDDeleteFront(&plist);//对链表进行头删
	SLDPrint(plist);//对链表进行打印
}

        代码走起来，结果如下图所示：

        链表头删函数实现成功！

6，链表查找函数

        链表的查找函数，作用就是找出链表中是否储存着某个数据，如果该数据存在，那么则返回储存这该数据的节点的地址；如果不存在，那么则返回NULL。该函数十分简单，我们直接上代码！

//链表的查找
SLD* SLDFind(SLD* phead, SLDataType x)
{
	SLD* pcur = phead;//将第一个节点的地址赋值给pcur
	while (pcur->next)
	{
		if (pcur->data == x)
		{
			return pcur;//找到了
		}
		pcur = pcur->next;
	}
	//遍历了一遍链表都没找到X，则返回NULL
	return NULL;
}

        经过我们的测试，这个函数同样也对空链表适用。该函数创建了一个变量pcur赋值为首节点的地址（为了防止phead被改变），然后使用while循环遍历链表，如果找到了则返回该节点地址（pcur），若没找到则返回NULL。

        老样子，我们先声明再测试：

#include"SList.h"
void test()
{
	SLD* plist = NULL;
	SLDPushBack(&plist, 1);//进行尾插
	SLDPushBack(&plist, 2);
	SLDPushBack(&plist, 3);
	SLDPushBack(&plist, 4);
	SLD* find = SLDFind(plist, 3);//寻找链表中数据为3的节点
	if (find != NULL)
	{
		printf("找到了");
	}
	else
	{
		printf("没有找到");
	}
}

        代码一走！结果如下图所示：

        链表查找函数实现成功！

7，链表指定位置之前插入数据函数

        该函数的作用是在我们所指定的节点位置（SLD* pos）之前插入一个新节点。它需要我们正确地运用节点创建函数，让我们画图解释：

        如图所示，我们需要除了pphead以外的两个新的变量pre（用来表示指定位置之前的节点地址），pos（用于表示指定位置的节点）。然后我们再创造一个新节点，将pre->next赋值为新节点的地址，后将新节点所储存的地址赋值为pos，这样，一个新节点就成功插入了。当然，我们不能忘记讨论只有一个节点的情况，这也非常简单，只有一个节点的话，不就是头插了吗，我们直接调用头插函数就行了呗！所以该函数的代码如下：

//链表的指定位置之前插入数据
void SLDInsert(SLD** pphead, SLD* pos, SLDataType x)
{
	assert(pphead && *pphead);
	assert(pos);//指定位置不可以为空
	SLD* newnode = SLDCreatNode(x);//创建一个新节点
	if (pos == *pphead)
	{
		SLDPushFront(pphead, x);//调用头插函数
	}
	else
	{
		SLD* pre = *pphead;
		while (pre->next != pos)
		{
			pre = pre->next;
		}
		//新节点的首尾相连
		pre->next = newnode;
		newnode->next = pos;
	}
}

        我们先声明再测试，测试代码如下：

#include"SList.h"
void test()
{
	SLD* plist = NULL;
	SLDPushBack(&plist, 1);//进行尾插
	SLDPushBack(&plist, 2);
	SLDPushBack(&plist, 3);
	SLDPushBack(&plist, 4);
	SLD* find = SLDFind(plist, 3);
	SLDInsert(&plist, find, 100);//插入一个数据值为100的新节点
	SLDPrint(plist);//对链表进行打印
}

        那咱们代码走起来，结果如图所示：

        链表指定位置之前插入数据函数实现成功！ 

8，链表指定位置之后插入数据函数

        对于这个函数，所用到的参数就比前一个函数更少，这是因为在前一个函数，如果我们想要找到pos之前的节点的地址，我们需要使用while函数从头遍历一遍链表。而这个函数不用，因为我们可以直接通过pos找到pos之后节点的地址。就像下图所示：

        所以我们只需要创造一个新节点newnode，然后将newnode所储存的地址赋值为pos->next,最后再将pos->next赋值为newnode就可以了，是不是非常简单！所以我们的代码如下：

//链表的指定位置之后插入数据
void SLDInsertAfter(SLD* pos, SLDataType x)
{
	assert(pos);//pos不可以为空指针
	SLD* newnode = SLDCreatNode(x);
	//首尾相连
	newnode->next = pos->next;
	pos->next = newnode;
}

        所以我们先声明再测试：

#include"SList.h"
void test()
{
	SLD* plist = NULL;
	SLDPushBack(&plist, 1);//进行尾插
	SLDPushBack(&plist, 2);
	SLDPushBack(&plist, 3);
	SLDPushBack(&plist, 4);
	SLD* find = SLDFind(plist, 3);
	SLDInsertAfter( find, 100);//插入一个数据值为100的新节点
	SLDPrint(plist);//对链表进行打印
}

        咱们代码走起来，结果如下图所示：

        链表指定位置之后插入数据函数实现成功！

9，链表删除指定位置节点函数

        该函数的作用是删除指定位置的节点，并且将其前后的节点重新连接起来，但是在实现过程中，我们需要注意删除的节点是否为头节点等特殊情况。如下图所示：

        我们先看代码，再进行细讲吧！

//链表的指定位置删除节点
void SLDDelete(SLD** pphead, SLD* pos)
{
	assert(pphead && *pphead);
	assert(pos);//pos不可以为空指针
	if (pos == *pphead)//pos为头节点
	{
		SLDDeleteFront(pphead);//直接调用头删函数
	}
	else
	{
		SLD* pre = *pphead;
		while (pre->next != pos)//遍历链表,当pre为pos前一个结点时则退出循环
		{
			pre = pre->next;
		}
		pre->next = pos->next;//连接pre与pos之后的节点
		free(pos);
		pos = NULL;//防止野指针的出现
	}
}

         在该函数中，我们还是先用assert断言保证链表和pos的非空，然后我们再进行pos是否为头节点的分类讨论。

        当pos为头节点时，那此时这个函数就相当于头删，那我们直接调用我们先前实现的头删函数就行了。

        当pos不为头节点时，那么我们就需要定义一个pre结构体指针，用于保存pos前一个节点的地址，然后我们使用while循环遍历链表，并且在pre->next!=pos条件为假时停下，那么此时pre正好表示pos之前一个节点的地址。最后我们再将pre->next赋值为pos->next以完成新节点的首尾相连，释放pos并且防止pos成为野指针。这样，链表删除指定位置节点函数就完成了！

        让我们先声明后测试：

#include"SList.h"
void test()
{
	SLD* plist = NULL;
	SLDPushBack(&plist, 1);//进行尾插
	SLDPushBack(&plist, 2);
	SLDPushBack(&plist, 3);
	SLDPushBack(&plist, 4);
	SLD* find = SLDFind(plist, 3);
	SLDDelete(&plist, find);//删除数据值为3的节点
	SLDPrint(plist);//对链表进行打印
}

        我们代码走起来，那么所得到的结果如下：

        链表删除指定位置节点函数实现成功！

10，链表删除指定位置之后节点函数

        这是我们所接触链表操作函数的最后一个函数了！它可以删除掉链表指定位置之后的节点，让我们直接看图说话！

        如图所示，pos之后的那个节点才是我们想要删除的，所以我们将那个节点命名为del，所以我们需要做的就是先将pos与pos->next->next连接起来，然后释放掉del就行了，十分简单！

        那么代码如下图所示：

void SLDDeleteAfter(SLD** pphead, SLD* pos)
{
	assert(*pphead && pphead);
	assert(pos && pos->next);//pos和pos的下一个节点都不可以为空
	SLD* del = pos->next;//del为要被删除的节点
	pos->next = del->next;//首尾相连
	free(del);
	del = NULL;//防止野指针
}

        所以我们先声明后测试，测试代码如下：

#include"SList.h"
void test()
{
	SLD* plist = NULL;
	SLDPushBack(&plist, 1);//进行尾插
	SLDPushBack(&plist, 2);
	SLDPushBack(&plist, 3);
	SLDPushBack(&plist, 4);
	SLD* find = SLDFind(plist, 3);
	SLDDeleteAfter(&plist, find);//删除数据值为3的节点之后的节点
	SLDPrint(plist);//对链表进行打印
}

        结果如下图所示：

        链表删除指定位置之后节点函数实现成功！

四，结语

        现在我已经从一个C语言小白变成了一个略懂一点数据结构的C语言小白了，感觉在学习编程的路上逐渐走上坡路了，也慢慢有了对编程的兴趣了，这篇九千三百多字的文章也算是一个很不错的里程碑了。

        本人才疏学浅，希望我的这篇文章能给你们带来帮助，也非常希望可以得到给位的支持，加油吧，好好学习，未来可期！！

文章来源地址https://www.toymoban.com/news/detail-856448.html

到了这里，关于C语言链表的含义与链表数据操作代码详解！的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！