数据结构——单链表

2023-12-19 21:46:38

一、链表

链表是线性表的一种。上篇文章提到过,线性表(linear list)是一种具有n个相同特性的数据元素的有限序列,是一种被广泛运用的数据结构,常见的线性表有:顺序表、链表、栈、队列、数组、字符串等。

1.1 链表的概念及结构?

链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接的顺序来实现的,我们可以想象成一列火车,火车头就是头节点,每一节车厢都是一个节点,“车厢”与“车厢”之间用指针来建立联系。

?首先我们需要明确几点:

  • 链式结构在逻辑上是连续的,但是在物理上(内存中)不一定连续。
  • 节点一般都是从堆上申请出来的

1.2 链表的分类

本章中虽然只讲解单链表相关的知识,但是实际上链表的结构非常多样,以下情况分别组合起来就有8种链表结构

(1)单向/双向和带头/不带头

(2)循环/非循环

所以细分下来,8种结构分别是:

  • 无头单向循环
  • 无头单向非循环
  • 带头单向循环
  • 带头单向非循环
  • 带头双向循环
  • 带头双向非循环
  • 无头双向循环
  • 无头双向非循环

虽然链表有这么多种结构,但是我们实际上最常用的还是这两种结构:

无头单向非循环链表:结构简单,一般不会单独用来存数据,而是更多作为其他数据结构的子结构,如哈希桶、图的邻接表等,或者作为笔试面试题出现。

带头双向循环链表:结构最复杂,一般用来单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外,这个结构虽然复杂,但是会带来很多优势,反而化繁为简了。

二、单链表的增删查改接口实现

接下来,我们手把手逐步的来实现单链表的增删查改接口,此处的单链表指无头单向非循环链表。

此次演示使用的是vs2019,我们先创建一个新工程,并新建一个头文件"SList.h"和两个源文件"SList.c"和"test.c",具体作用为:

  • SList.h:单链表的定义,头文件的引用和接口函数的声明
  • SList.c:接口函数的实现
  • test.c:测试各个函数

首先我们展示"SList.h"的完整代码,不要忘记在两个源文件中引用"SList.h"

#pragma once//防止头文件被二次引用

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

typedef int SLTDataType;//如果要修改存储的数据类型可直接在此修改

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

//无头单向非循环链表增删查改接口实现

SLTNode* CreateNewNode(SLTDataType x);//创建新节点

void SLTPushFront(SLTNode** pphead, SLTDataType x);//头部插入节点

void SLTPushBack(SLTNode** pphead, SLTDataType x);//尾部插入节点

void SLTPopFront(SLTNode** pphead);//头部删除节点

void SLTPopBack(SLTNode** pphead);//尾部删除节点

void SLTPrint(SLTNode* plist);//打印单链表

SLTNode* SLTFind(SLTNode* plist, SLTDataType x);//在单链表中查找数据

//在指定位置插入节点
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在pos位置之前插入节点
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//在pos位置之后插入节点

//在指定位置删除节点
void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos位置的节点
void SLTEraseAfter(SLTNode* pos);//删除pos位置的后一个节点

接下来我们按照"SList.h"中的顺序逐步实现各个接口函数,每一步都详细讲解,必须让你学会

(1)创建新节点

SLTNode* CreateNewNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); //创建新节点
	if (newnode == NULL) //防止空间开辟失败
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x; //初始化新节点数据
	newnode->next = NULL; //初始化新节点中存放的指针变量
	return newnode; //返回新节点地址
}

(2)头部插入节点

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead); //断言,防止传入空指针
    //这里不需要对*pphead进行断言,因为*pphead为NULL时说明链表为空,可以插入节点
	SLTNode* newnode = CreateNewNode(x); //创建新节点
	newnode->next = *pphead; //新节点中存放原来头节点的地址
	*pphead = newnode; //再把新节点地址存放到头节点指针中
}

插入和删除操作都需要对指向节点的指针中存放的地址进行修改,而传一级指针属于传值调用,形参的修改不会影响到实参,所以需要传入二级指针

配一张图方便各位理解

测试一下

?

SLTPrint可以跳转到<(6)打印单链表>部分查看

(3)尾部插入节点

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead); //断言,防止传入空指针
	SLTNode* newnode = CreateNewNode(x); //创建新节点
	if (*pphead == NULL) //如果*pphead为空则说明链表为空
	{
		*pphead = newnode; //新节点地址即为头节点地址
	}
	else //如果链表不为空
	{
		SLTNode* tail = *pphead; //创建一个tail指针用来从头找到尾
		while (tail->next) //当tail指向的节点中的指针不为空,则没有找到尾节点
		{
			tail = tail->next; //找到下一个节点
		}
		tail->next = newnode; //尾节点中存放的指针指向新节点
	}
}

这个应该很好理解,找到尾节点然后将尾节点与新节点连接就实现了尾插

测试一下

(4)头部删除节点

void SLTPopFront(SLTNode** pphead)
{
	assert(pphead); //断言,防止传入空指针
	assert(*pphead); //断言,防止链表为空还进行删除
	SLTNode* tmp = *pphead; //保存头节点地址
	*pphead = (*pphead)->next; //更新头节点
	free(tmp); //释放原头节点空间
}

测试一下

?

(5)尾部删除节点

void SLTPopBack(SLTNode** pphead)
{
	assert(pphead); //断言,防止传入空指针
	assert(*pphead); //断言,防止链表为空还进行删除
	if ((*pphead)->next == NULL) //此时链表中只有一个节点
	{
		free(*pphead); //释放节点空间
		*pphead = NULL; //置空
	}
	else //链表中有多个节点时
	{
		SLTNode* tail = *pphead; //创建一个tail指针用来从头找到尾
		while (tail->next->next) //当tail->next->next为NULL时说明tail的下一个节点是尾节点
		{
			tail = tail->next; //找到下一个节点
		}
		free(tail->next); //释放尾节点空间
		tail->next = NULL; //置空
	}
}

测试一下

?

(6)打印单链表

void SLTPrint(SLTNode* plist)
{
	SLTNode* tmp = plist; 
	while (tmp)
	{
		printf("%d->", tmp->data); //打印节点数据
		tmp = tmp->next; //找到下一个节点
	}
	printf("NULL"); //尾节点指向空
}

?(7)在单链表中查找数据

SLTNode* SLTFind(SLTNode* plist, SLTDataType x)
{
	SLTNode* tmp = plist;
	while (tmp)
	{
		if (tmp->data == x) //找到目标数据
		{
			return tmp; //返回节点地址
		}
		tmp = tmp->next; //找到下一个节点
	}
	return NULL; //没找到就返回NULL
}

因为返回了目标数据所在的节点地址,可以将这个函数与后面的几个函数进行搭配

(8)在pos位置之前插入节点

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead); //断言,防止传入空指针
	assert(pos); //断言,防止传入空指针
	if (*pphead == pos) //如果pos位置为头节点
	{
		SLTPushFront(pphead, x); //进行头插操作
	}
	else //pos位置不为头节点
	{
		SLTNode* tmp = *pphead; //将头节点地址传入tmp
		while (tmp->next != pos) //tmp的下一个节点不为pos位置时
		{
			tmp = tmp->next; //继续寻找下一个节点
		}
		SLTNode* newnode = CreateNewNode(x); //创建新节点
		newnode->next = pos; //将pos位置的节点地址传给新节点中的指针
		tmp->next = newnode; //将新节点地址传给tmp节点的指针
	}
}

测试一下

?

(9)在pos位置之后插入节点

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos); //断言,防止传入空指针
	SLTNode* newnode = CreateNewNode(x); //创建新节点
	newnode->next = pos->next; //先把pos的后一个节点地址传给新节点的指针
	pos->next = newnode; //再更新pos的指针,指向新节点
}

这里的后两行代码顺序一定不能调换,pos->next先指向newnode的话,newnode->next中存放的就变成自己的地址了,链表此时就变成循环的了。

测试一下

(10)删除pos位置的节点

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead); //断言,防止传入空指针
	assert(*pphead); //断言,防止链表为空还进行删除
	assert(pos); //断言,防止传入空指针
	if (*pphead == pos) //如果pos位置为头节点
	{
		SLTPopFront(pphead); //直接进行头删即可
	}
	else //pos位置不为头节点
	{
		SLTNode* tmp = *pphead; //把将头节点地址传给tmp
		while (tmp->next != pos) //tmp的下一个节点不为pos位置时
		{
			tmp = tmp->next; //继续寻找下一个节点
		}
		tmp->next = pos->next; //将tmp节点与pos的下一个节点连接
		free(pos); //释放pos节点空间
        pos = NULL;//置空
	}
}

测试一下

?

?(11)删除pos位置的下一个节点

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos); //断言,防止传入空指针
	assert(pos->next); //断言,防止pos指向尾节点
	SLTNode* next = pos->next; //保存pos位置的下一个节点地址
	pos->next = next->next; //将pos节点与下下个节点链接
	free(next); //释放pos位置的下一个节点空间
}

测试一下

完.?

文章来源:https://blog.csdn.net/Eristic0618/article/details/135089186
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。