当前位置：首页 > article >正文

数据结构之链表——单向链表

article 2024/10/21 8:06:14

单向链表

链表跟数据表有着本质的关系

回顾一下顺序表：顺序表分为动态顺序表和静态顺序表
静态顺序表：静态顺序表详解
动态顺序表：动态顺序表详解
顺序表的本质还是数组，通过数组来存储数据，如果我们需要插入一个数据，在顺序表中我们就需要将需要插入的位置之后的元素统统向后挪动一位，而且顺序表在创建时需要指定一个固定的大小，如果需要扩展，通常需要创建一个新的更大的数组并将旧数组中的数据复制过去，这是一个开销较大的操作。
我们的链表就可以完美的解决这些问题：
链表中的节点可以按需分配，因此可以避免像数组那样为未使用的空间分配内存。

链表：在链表中插入和删除元素的时间复杂度通常为O(1)（找到插入或删除位置后），因为只需要修改前后节点的指针即可。
顺序表：在数组中插入或删除元素的时间复杂度通常为O(n)，因为需要移动插入或删除位置之后的所有元素。

我们先通过画图来理解一下链表：
在这里插入图片描述
链表由数据域和指针域构成，数据域里存放的时我们的数据，指针域里存放的就是我们的指针（下一个节点的地址）大概来说就是这样的 phead 代表首节点

首先我们还是从头文件开始写
包含所需要的头文件，定义数据类型，定义结构体

#pragma once
#include<stdlib.h>
#include<stdio.h>
typedef int SLDataType;//重命名 int 类型为 SLDataType
typedef struct SLTDataNode {//重点是定义结构体：
	SLDataType data;//这个是数据域
	struct SLTDataNode* next;//这个是指针域，用来记录下一个节点的地址
}SLTNode;//重新命名 SLDataNode 结构体为SLTNode

第一个函数：尾插（这个函数有问题，具体原因请往下看）

void Pushback(SLTNode* plist,SLDataType x)
{
	//开始我们的尾插函数
	/*我们来想，链表是链式存储，通过指针来寻找下一个节点的地址，那么我们
	应该通过遍历的方式来寻找链表的尾节点（最后一个节点）
	而且我们在前面初始化的时候设置的首节点的地址为NULL 所以我们这个时候需要
	动态开辟一个空间，记为newnode,因为一个节点就是一个结构体，所以我们需要定义
	为结构体类型的指针，malloc 函数我们之前也介绍过返回的是一个空指针，这里我们
	将其转换成结构体指针*/
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	//开辟节点之后我们判断一下是不是开辟成功了
	if (newnode == NULL)
	{
		printf("error\n");
		exit(-1);
	}
	//如果开辟成功，那么我们将新开辟出来的节点的下一个节点设置为NULL
	//将新开辟出来的节点里的数据域赋值为  x  
	newnode->next = NULL;
	newnode->data = x;
	//判断我们的首节点是不是空，如果是空的话，那么就将开辟出的新节点赋值给plist当作首节点
	if (plist == NULL)
	{
		plist = newnode;
	}
	else//如果首节点不为空，那么我们定义一个tail的结构体指针类型的变量，用来找这个链表的尾节点（即最后一个节点）
	{
		SLTNode* tail = plist;
		while (tail->next != NULL)//循环，开始寻找最后一个节点，我们下面通过画图来帮大家理解
		{
			tail = tail->next;
		}
		tail->next = newnode;//将尾节点指向新开辟的节点，将整个链表连接起来
	}
}

我们现在通过画图来帮大家理解寻找尾节点的含义：

初始化是这样的：

我们从首节点出发，向后遍历
在这里插入图片描述
一直遍历到最后一个节点，此时 tail 的下一个就是空了，所以

while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;

这个循环条件为 tail 的下一个节点不为空（这里的tail = tail->next就相当于再往前遍历），如果为空，那么就找到了这个链表的为节点。找到尾节点之后我们将新开辟的节点赋值给尾节点，此时newnode相当于尾节点，tail相当于倒数第二个节点
图如下：
在这里插入图片描述
我们来调试一下，发现plist的地址改变了，而且数据域里面也有值了，next也指向空了，目前好像没什么问题，我们接着往下走

欸，这一步怎么回事，我不是已经赋值了吗，为什么没有改变呢？我们再往下走
在这里插入图片描述
奇怪啊，为啥呢，都成空了，好奇怪啊，我们来仔细的想一想，我们实参传入的是什么？

实参：
我们传入的是一个指针类型的变量啊，对吧，他是一个变量啊，传进去并不会该改变phead的值，所以！！！我们需要传个地址过去！！
既然都传地址了，那我们的形参是不是也需要变一下呀——YES!
我们这里采用二级指针：
在这里插入图片描述
改变了形参，我们的函数也就需要改上一改了
改之后：

void Pushback(SLTNode** plist,SLDataType x)
{
	//开始我们的尾插函数
	/*我们来想，链表是链式存储，通过指针来寻找下一个节点的地址，那么我们
	应该通过遍历的方式来寻找链表的尾节点（最后一个节点）
	而且我们在前面初始化的时候设置的首节点的地址为NULL 所以我们这个时候需要
	动态开辟一个空间，记为newnode,因为一个节点就是一个结构体，所以我们需要定义
	为结构体类型的指针，malloc 函数我们之前也介绍过返回的是一个空指针，这里我们
	将其转换成结构体指针*/
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	//开辟节点之后我们判断一下是不是开辟成功了
	if (newnode == NULL)
	{
		printf("error\n");
		exit(-1);
	}
	//如果开辟成功，那么我们将新开辟出来的节点的下一个节点设置为NULL
	//将新开辟出来的节点里的数据域赋值为  x  
	newnode->next = NULL;
	newnode->data = x;
	//判断我们的首节点是不是空，如果是空的话，那么就将开辟出的新节点赋值给plist当作首节点
	if (*plist == NULL)
	{
		*plist = newnode;
	}
	else//如果首节点不为空，那么我们定义一个tail的结构体指针类型的变量，用来找这个链表的尾节点（即最后一个节点）
	{
		SLTNode* tail = *plist;
		while (tail->next != NULL)//循环，开始寻找最后一个节点，我们下面通过画图来帮大家理解
		{
			tail = tail->next;
		}
		tail->next = newnode;//将尾节点指向新开辟的节点，将整个链表连接起来
	}
}

在我们改变之后的函数中，我们的形参变为了二级指针，那么我们在函数中使用的时候就应该对其解引用。在我们测试函数中 phead 已经是一个结构体指针类型的变量了，本身就是一个地址，我们再对其取地址，相当于得到了指针的地址，我们在尾插函数中对其解引用，就相当于找到了 phead 这个结构体指针
这样就对啦！！！
在这里插入图片描述
我们下来实现一个打印函数，来测试一下我们尾插有没有成功

void SLTNodePrint(SLTNode* plist)//我们不需要改变链表，所以我们这里不需要二级指针
{
	SLTNode* tail = plist;//将首节点赋值给新的变量tail
	while (tail!= NULL)//我们这里为什么不写tail->next！=NULL呢？
	//因为我们这里并不是要定位链表的尾节点在哪，我们现在是使用，不是改变，详细请看图
	{
		printf("%d->", tail->data);
		tail = tail->next;
	}
		printf("NULL\n");
}