数据结构与算法(C语言版)P3.1---链表(无头单向非循环链表)

2023-09-16 11:42:59

1、链表的概念及结构

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

在这里插入图片描述

注意：

​ 1、从上图可看出：链式结构在逻辑上是连续的，但是在物理上不一定连续。

​ 2、现实中的结点一般都是从堆上申请出来的。

​ 3、从堆上申请空间，是按照一定策略来分配的，再次申请的空间可能连续，不可能不连续。

链表中的结点也是动态内存分配空间，按需分配。

假设在32位系统上，结点中值域为int类型，则一个结点的大小位8字节，则可能有如下链表：

在这里插入图片描述

链表结构中的结点由两部分组成：

  • 数据域：存储元素数值数据。
  • 指针域：存储直接后继节点的存储位置。

2、链表的分类

实际中链表的结构非常多，以下情况组合起来就有8中链表结构：

在这里插入图片描述

结点只有一个指针域的链表，称为单链表或线性表。

结点有两个指针域的链表，称为双链表。

首尾相接的链表称为循环链表。

头指针、头结点和首元结点：

在这里插入图片描述

头指针：是指向链表中第一个结点的指针。

首元结点：是指链表中存储第一个数据元素a1的结点。

头结点（哨兵位）：是在链表的首元结点之前附设的一个结点，此节点不存储数据，只记录首元结点的地址。

讨论一：在链表中设置头结点有什么好处？

1、便于首元节点的处理：

​ 首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其它位置一致，无须进行 特殊处理。

2、便于空表和非空表的统一处理：

​ 无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

讨论二：头结点的数据域内装的是什么呢？

​ 头结点的数据域可以为空，也可以存放线性表长度等附加信息，但此结点不能计入链表长度值。

1、单向或者双向

在这里插入图片描述

2、带头或者不带头

在这里插入图片描述

3、循环和非循环

在这里插入图片描述

虽然有那么多的链表结构，但是我们实际中最常用的还是两种结构：

​ 1、无头单向非循环链表

​ 在这里插入图片描述

​ 2、带头双向循环链表

​

1、无头单向非循环链表：结构简单，一般不会单独用来__存放数据__，实际中更多是作为__其它数据结构的子结构__，如：哈希桶，图的邻接表等等。另外这种结构在笔试中出现很多。

2、带头双向循环链表：结构复杂，一般用在单独存储数据。实际中使用的链表结构，都是带头双向链表，另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

在这里插入图片描述
所以下面我们就实现以上两个最常用的链表。

3、无头单向非循环链表的实现

链表主要有以下几个接口功能：

  • 打印（SListPrint）
  • 销毁链表（SListDestory）
  • 扩容（BuyListNode）
  • 头插（SListPushFront）
  • 头删（SListPopFront）
  • 尾插（SListPushBack）
  • 尾删（SListPopBack）
  • 查找元素（SListFind）
  • 在pos位置之前插入（SListInsert）
  • 在pos位置之后去插入（SListErase）
  • 删除pos当前位置的数据（SeqListErase）
  • 删除pos位置之后的一个结点（SListEraseAfter)

和顺序表不同的是，无头单向非循环链表是不用初始化的。所以没有初始化接口。我们只需要在main函数中申请一个结点地址即可。如下：

int main()
{
	SLTNode* plist = NULL;
	return 0;
}

3.1、定义结构体

#pragma once;

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

typedef int SLDataType;

typedef struct SListNode
{
	SLDataType data;
	struct SListNode* Next;
}SLTNode;

data变量用于存储数据，叫做数据域。
Next指针变量用于存储下一个结点的地址，叫做指针域。

3.2、扩容

链表的好处之一就是存储一个数据就申请一块空间，所以在链表中进行任意擦汗如操作时，都需要先申请内存空间。

SLTNode* BuyListNode(SLDataType x)
{
	//创建新节点（就是需要尾插的那个结点）
	//注意这个newnode指针，它就是新节点的地址，后面将尾结点和新节点关联的时候，就需要用到此地址。
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));

	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->Next = NULL;
	return newnode;
}

3.3、头插

void SListPushFront(SLTNode** pphead, SLDataType x)
{
	SLTNode* newnode = BuyListNode(x);
	newnode->Next = *pphead;
	*pphead = newnode;
}

3.4、打印

这里打印只需要传一级指针即可。只需打印输出，无需其它操作，所以传一级指针即可。

void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d ", cur->data);
		cur = cur->Next;
	}
	printf("\n");
}

3.5、销毁

销毁链表的错误做法，不能直接操作：free(*pphead);
如果这样，只释放了头结点的地址，后面的结点的地址，都会找不到且无法释放。所以会造成内存泄漏。

正确的操作：一个结点一个结点的释放，并且在释放一个结点之前先把此结点的地址先保存来下来，以防找不到。

void SListDestroy(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->Next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

3.6、头删

头删的核心思想：先保存第二个结点的地址，然后释放头结点，最后再将头指针和第二个结点的地址链接起来。

void SListPopFront(SLTNode** pphead)
{
	assert(*pphead != NULL);
	
	//保存第二个结点
	SLTNode* next = (*pphead)->Next;
	//释放第一个结点
	free(*pphead);
	//重新链接结点
	*pphead = next;
}

3.7、尾插

尾插的核心思想：找到最后一个结点，然后和扩容的newnode新节点进行链接。

需要注意的是：由于我们实现的是无头链表，所以在进行结点的插入以及删除时，需要考虑，空链表，只有一个结点的特殊情况。

void SListPushBack(SLTNode** pphead, SLDataType x)
{
	SLTNode* newnode = BuyListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
	//首先需要找到链表中的尾结点,尾结点有个特征：它的Next为NULL。
		SLTNode* tail = *pphead;
		while (tail->Next)
		{
			tail = tail->Next;
		}
		//关联尾节点和新节点
		tail->Next = newnode;
	}
}

3.8、尾删

尾删的核心思想：同时找到最后一个结点和倒数第二个结点。然后释放最后一个结点，并且将倒数第二个结点的Next指为NULL。

这里也需要考虑3种情况：没有结点，只有一个结点，有多个结点。

void SListPopBack(SLTNode** pphead)
{
	//先处理没有结点的情况，直接断言即可。
	assert(*pphead != NULL);

	//其次处理只有一个结点的情况
	if ((*pphead)->Next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//最后考虑的就是有多个结点的情况
	else
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;

		while (tail->Next)
		{
			prev = tail;
			tail = tail->Next;
		}
		free(tail);
		tail = NULL;
		prev->Next = NULL;
	}
}

3.9、查询指定元素，并返回结点地址pos

SLTNode* SListFind(SLTNode* phead, SLDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (x == cur->data)
		{
			return cur;
		}
		else
		{
			cur = cur->Next;
		}
	}
	return NULL;
}

3.10、在pos位置之前插入

核心思想：找到pos结点前面的结点，然后依次链接起来即可。

特殊情况：需要考虑只有一个结点和多个结点的情况

void SListInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{
	SLTNode* newnode = BuyListNode(x);
	//这个用于只有一个结点的情况
	if (*pphead == pos)
	{
		*pphead = newnode;
		newnode->Next = pos;
	}
	//这个用于多个结点前插入数据
	else
	{
		SLTNode* posPrev = *pphead;
		//找到pos的前一个位置
		while (posPrev->Next != pos)
		{
			posPrev = posPrev->Next;
		}
		//链接
		posPrev->Next = newnode;
		newnode->Next = pos;
	}
}

在pos之前插入的时间复杂度分析。这里分三种情况：

  • 直接是头插，那时间复杂度是O(1)
  • 需要插入的数据在中间
  • 需要插入的数据在最后一个结点前，所以是O(N)。

所以取悲观预期，综合来说时间复杂度是O(N)。

3.11、在pos位置之后插入

在pos位置之后插入比在pos位置之前插入简单。就直接依次链接即可。

void SListInsertAfter(SLTNode** pphead, SLTNode* pos,SLDataType x)
{
	SLTNode* newnode = BuyListNode(x);

	SLTNode* posNext = pos->Next;
	pos->Next = newnode;
	newnode->Next = posNext;
}

在pos之后插入的时间复杂度分析：
在pos位置之后插入，由于确定好了插入的位置，可以直接插入。所以时间复杂度为O(1)。

相比在pos位置之前插入，结点，更推荐使用pos位置之后插入结点。

3.12、删除pos当前位置结点

核心思想：找到pos前一个结点，将pos前一个结点和pos后一个结点链接，然后释放pos。

考虑情况：

  • 只有一个结点
  • 有多个结点
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	//删除头结点
	if (*pphead == pos)
	{
		*pphead = pos->Next;
		free(pos);
	}
	//删除非头结点的其它结点。
	else
	{
		SLTNode* posPrev = *pphead;
		while (posPrev->Next != pos)
		{
			posPrev = posPrev->Next;
		}
		posPrev->Next = pos->Next;
		free(pos);
	}
}

删除pos位置当前的时间复杂度：O(N)。

3.13、删除pos位置之后的结点

很简单，直接链接。

void SListEraseAfter(SLTNode* pos)
{
	assert(pos->Next);
	SLTNode* next = pos->Next;
	pos->Next = next->Next;
	free(next);
}

在pos位置之后的时间复杂度：O(1)。

4、全代码展示

这里使用三个文件：

  • seqlist.h：用于结构体、各种函数接口的声明
  • seqlist.c：用于各种函数接口的定义。
  • test.c：用于创建链表，实现链表。

4.1、seqlist.h

#pragma once;

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

typedef int SLDataType;

typedef struct SListNode
{
	SLDataType data;
	struct SListNode* Next;
}SLTNode;

//扩容
SLTNode* BuyListNode(SLDataType x);

//头插
void SListPushFront(SLTNode** pphead, SLDataType x);

//打印
void SListPrint(SLTNode* phead);

//销毁
void SListDestroy(SLTNode** pphead);

//头删
void SListPopFront(SLTNode** pphead);

//尾插
void SListPushBack(SLTNode** pphead, SLDataType x);

//尾删
void SListPopBack(SLTNode** pphead);

//查询指定元素，返回结点地址
SLTNode* SListFind(SLTNode* phead,SLDataType x);

//在pos位置之前插入结点
void SListInsert(SLTNode** phead, SLTNode* pos, SLDataType x);

//在pos位置之后插入结点
void SListInsertAfter(SLTNode** pphead, SLTNode* pos,SLDataType x);

//删除当前pos位置结点
void SListErase(SLTNode** pphead, SLTNode* pos);

//删除pos位置之后的结点
void SListEraseAfter(SLTNode* pos);

4.2、seqlist.c

#include "list.h"

//扩容
SLTNode* BuyListNode(SLDataType x)
{
	//创建新节点（就是需要尾插的那个结点）
	//注意这个newnode指针，它就是新节点的地址，后面将尾结点和新节点关联的时候，就需要用到此地址。
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));

	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->Next = NULL;
	return newnode;
}

//头插
void SListPushFront(SLTNode** pphead, SLDataType x)
{
	SLTNode* newnode = BuyListNode(x);
	newnode->Next = *pphead;
	*pphead = newnode;
}

//打印
void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d ", cur->data);
		cur = cur->Next;
	}
	printf("\n");
}

//销毁
void SListDestroy(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->Next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

//头删
void SListPopFront(SLTNode** pphead)
{
	assert(*pphead != NULL);
	
	//保存第二个结点
	SLTNode* next = (*pphead)->Next;
	//释放第一个结点
	free(*pphead);
	//重新链接结点
	*pphead = next;
}

//尾插
void SListPushBack(SLTNode** pphead, SLDataType x)
{
	SLTNode* newnode = BuyListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->Next)
		{
			tail = tail->Next;
		}
		tail->Next = newnode;
	}
}

//尾删
void SListPopBack(SLTNode** pphead)
{
	if ((*pphead)->Next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;

		while (tail->Next)
		{
			prev = tail;
			tail = tail->Next;
		}
		free(tail);
		tail = NULL;
		prev->Next = NULL;
	}
}

//查询指定元素，返回结点地址
SLTNode* SListFind(SLTNode* phead, SLDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (x == cur->data)
		{
			return cur;
		}
		else
		{
			cur = cur->Next;
		}
	}
	return NULL;
}

//在pos位置之前插入结点
void SListInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{
	SLTNode* newnode = BuyListNode(x);
	
	if (*pphead == pos)
	{
		*pphead = newnode;
		newnode->Next = pos;
	}
	else
	{
		SLTNode* posPrev = *pphead;
		while (posPrev->Next != pos)
		{
			posPrev = posPrev->Next;
		}
		posPrev->Next = newnode;
		newnode->Next = pos;
	}
}

//在pos位置之后插入结点
void SListInsertAfter(SLTNode** pphead, SLTNode* pos,SLDataType x)
{
	SLTNode* newnode = BuyListNode(x);

	SLTNode* posNext = pos->Next;
	pos->Next = newnode;
	newnode->Next = posNext;
}

//删除当前pos位置结点
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	if (*pphead == pos)
	{
		*pphead = pos->Next;
		free(pos);
	}
	else
	{
		SLTNode* posPrev = *pphead;
		while (posPrev->Next != pos)
		{
			posPrev = posPrev->Next;
		}
		posPrev->Next = pos->Next;
		free(pos);
	}
}

//删除pos位置之后的结点
void SListEraseAfter(SLTNode* pos)
{
	assert(pos->Next);
	SLTNode* next = pos->Next;
	pos->Next = next->Next;
	free(next);
}

4.3、test.c

#include "list.h"

void TestList1()
{
	SLTNode* plist = NULL;

	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPushFront(&plist, 5);
	SListPushFront(&plist, 6);

	SLTNode* pos = SListFind(plist, 3);
	SListEraseAfter(pos);

	SListPrint(plist);

	SListDestroy(&plist);
}

int main()
{
	TestList1();
	return 0;
}
更多推荐

Git学习

什么是Git？Git是一个分布式版本控制系统，用于追踪文件和项目的变化。它可以帮助开发者或团队有效地协同工作，并提供版本管理、分支管理、代码合并等功能。Git的设计目标是速度快、简单易用。Git的基本概念仓库（Repository）：Git仓库是存储代码和历史记录的地方。它可以位于本地计算机或远程服务器上。每个仓库都有

java自定义异常

首先跟前端商量好，用errMessage作为异常信息传输的关键字。1.创建一个公共异常类如果要获取"非法参数"的错误消息，可以使用CommonError.PARAMS_ERROR.getErrMessage()方法来获取。这种方式使得代码更具可读性和维护性。publicenumCommonError{//Java的枚举

Java中stream是什么？有什么作用？如何使用？

Java中stream是什么？有什么作用？如何使用？在Java中，Stream（流）是一种用于操作集合（Collection）、数组等数据源的API。它提供了一种功能强大且表达力高的编程模型，可以用更简洁、更具可读性的方式处理数据。Stream的主要作用是进行数据的转换、筛选、聚合等操作，可以极大地简化对数据的处理。使

基于Android系统英语学习助手APP设计开发

一、设计思路1.1设计目标1.2设计思路1.3设计内容1.3.1界面设计1.3.2功能模块设计1.3.3功能流程图1.3.4数据库设计（如果没有数据库这部分删除）1.4工具设备要求1.5技术方案二、设计过程与说明2.1技术路线2.2实现方案2.3实现原理2.3.1欢迎页面功能2.3.2首页功能2.3.3搜索2.3.4单

【小沐学CAD】虚拟仿真开发工具：GL Studio

文章目录1、简介2、软件功能3、应用行业3.1航空3.2汽车3.3防御3.4工业3.5电力与能源3.6医疗3.7空间3.8科技结语1、简介https://disti.com/gl-studio/https://ww2.mathworks.cn/products/connections/product_detail/gl

C语言——贪吃蛇小游戏

目录一、ncurse1.1为什么需要用ncurse：1.2ncurse的输入输出：1.2.1如何使用ncurse：1.2.2编译ncurse的程序：1.2.3测试输入一个按键ncurse的响应速度：1.3ncurse上下左右键获取：1.3.1如何查看宏定义的.h文件：1.3.2ncurse上下左右键获取：二、地图规划2

github一些有趣的使用场景和基本使用方法

文章目录github的使用入门安装Git创建GitHub帐户在本地设置Git克隆仓库进行修改和提交推送更改拉取更新删除Github上废弃的仓库注意github更多有趣的使用场景协作和社交编程文档和知识库学习和教育自动化工作流程数据科学和可视化用来写blogGitHubPagesJekyllHexo第三方集成开发者简历插

eNSP网络学习

一、eNSP1.什么是eNSPeNSP(EnterpriseNetworkSimulationPlatform)是一款由华为提供的免费的、可扩展的、图形化操作的网络仿真工具平台，主要对企业网络路由器、交换机进行软件仿真，完美呈现真实设备实景，支持大型网络模拟，让广大用户有机会在没有真实设备的情况下能够模拟演练，学习网络

ELK部署

一，elk提供了一个分布式多用户能力的全文搜索分析引擎，能对各种类型的数据进行近实时的索引和查询，支持高可用和水平扩展性。作用：1.将日志进行集中化管理2.将日志格式化_(ogstash)并输出到Elasticsearch3.对格式化后的数据进行索引和存储(Elasticsearch)4.前端数据的展示(Kibana)

使用自定义XML配置文件在.NET桌面程序中保存设置

本文将详细介绍如何在.NET桌面程序中使用自定义的XML配置文件来保存和读取设置。除了XML之外，我们还将探讨其他常见的配置文件格式，如JSON、INI和YAML，以及它们的优缺点和相关的NuGet类库。最后，我们将重点介绍我们为何选择XML作为配置文件格式，并展示一个实用的示例。1.背景在.NET桌面程序中，通常使用

Quartz.NET,强大的开源作业调度框架

Quartz.NET是一个强大的开源作业调度框架，专为C#和.NET开发而设计。它允许开发人员在应用程序中调度、执行和管理各种类型的作业，例如定时任务、后台作业、周期性作业等。Quartz.NET具有高度可配置性和灵活性，可以满足各种复杂的调度需求。**作用：**Quartz.NET的作用在于简化作业调度的实现并提供可

热文推荐
  1. k8s pod概念、分类及策略

    目录一.pod相关概念２.Kubrenetes集群中Pod两种使用方式３.pause容器的Pod中的所有容器共享的资源４.kubernetes中的pause容器主要为每个容器提供功能：６.Pod分为两类：二.Pod容器的分类1.基础容器（infrastructurecontainer）（1）作用（2）配置2.初始化容器

  2. 【网络安全】黑客自学笔记

    1️⃣前言🚀作为一个合格的网络安全工程师，应该做到攻守兼备，毕竟知己知彼，才能百战百胜。计算机各领域的知识水平决定你渗透水平的上限🚀【1】比如：你编程水平高，那你在代码审计的时候就会比别人强，写出的漏洞利用工具就会比别人的好用；【2】比如：你数据库知识水平高，那你在进行SQL注入攻击的时候，你就可以写出更多更好的S

  3. 大数据时代元数据的重要性

    元数据，是描述了数据本身（如数据库、数据元素、数据模型），数据表示的概念（如业务流程、应用系统、软件代码、技术基础设施，数据与概念之间的联系。元数据可以帮助组织理解其自身的数据、系统和流程，同时帮助用户评估数据质量，对数据库与其他应用程序的管理来说是不可或缺的。它有助于处理、维护、集成、保护和治理其他数据。在大数据的海

  4. spark 精华总结

    面试题：Hadoop的基于进程的计算和Spark基于线程方式优缺点？答案：Hadoop中的MR中每个map/reducetask都是一个java进程方式运行，好处在于进程之间是互相独立的，每个task独享进程资源，没有互相干扰，监控方便，但是问题在于task之间不方便共享数据，执行效率比较低。比如多个maptask读取

  5. Elasticsearch(四)深分页Scroll

    一、前言1.1、scroll与from+size区别ES对于from+size的个数是有限制的，二者之和不能超过1w。当所请求的数据总量大于1w时，可用scroll来代替from+size。from+size在ES查询数据的方式步骤如下：1、先将用户指定的关键字进行分词；2、将词汇去分词库中进行检索，得到多个文档的id

  6. 数据结构简述，时间、空间复杂度，学习网站推荐

    目录IT学习路线相关坚韧大厚书相关有趣/耐看书或视频数据结构与算法学习网站推荐刷题时间、空间复杂度数据结构简述基本概念数据结构与算法简述和CS综述整理。本文非基础的教程，本文会列出大量学习和参考网站。老惯例，一个文章是一个集大成（本文借助了语音输入（PC版讯飞输入法）由此加速码字，但仍保持简洁的文风）。数据结构+算法=

  7. 【ES实战】ES中关于segment的小结

    文章目录ES中关于segment的小结ES中segment相关的原理在Lucene中的产生segment的过程。（Lucenecommit过程）ES为了实现近实时可查询做了哪些缩短数据可被搜索的等待时长增加数据的可靠性优化segment的数量段合并自动合并强制合并相关配置translog合并策略相关合并调度相关相关AP

  8. 王道408计组汇编语言部分学习总结

    x86汇编语言指令基础x86处理器中程序计数器PC通常被称为IP高级语言—>汇编语言—>机器语言x86架构CPU，有哪些寄存器EAX通用寄存器EBXECXEDXESI变址寄存器变址寄存器可用于线性表、字符串的处理EDIEBP堆栈基指针堆栈寄存器用于实现函数调用ESP堆栈顶指针moveax,ebx#寄存器—>寄存器mov

  9. WebGPU学习（10）---如何利用 WebGPU 实现高性能

    虽然是WebGPU，但是速度很慢！？我们将解释如何充分利用WebGPU性能。这次我们以绘制大量物体为例，根据“使用纹理”中的代码进行一些更改并绘制900个立方体。要均匀分布立方体，可以按如下方式更新worldMatrix：for(leti=0;i<30*30;i++){draw({context,pipeline,ve