【链表】无头单向非循环链表

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

单链表

顺序表的问题及思考

我们之前了解了线性表中的顺序表下面针对顺序表有一些问题思考

问题

  1. 中间/头部的插入删除时间复杂度为O(N)
  2. 增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。
  3. 增容一般是呈2倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。

思考如何解决以上问题呢下面给出了链表的结构来看看。

链表

链表的概念及结构

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

它不按照线性的顺序存储数据而是由若干个同一结构类型的“结点”依次串联而成的即每一个结点里保存着下一个结点的地址。
在这里插入图片描述
注意

  • 从上图看出链式结构在逻辑上是连续的但是在物理上不一定连续。
  • 现实中的节点一班都是从堆上申请出来的。
  • 从堆上申请的空间是按照一定的策略来分配的两次申请的空间可能连续也可能不连续。

链表的分类

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

  1. 单向或者双向
  2. 带头或者不带头
  3. 循环或者非循环

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

  • 无头单项非循环链表

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

  • 带头双向循环链表

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

今天我们来讲常用的无头单向非循环链表

无头单向非循环链表

初始化链表

我们知道链表是由多个结点组成所以要想创建一个链表首先要创建一个结点。一个结点存储的内容可以分为两部分数据域指针域。

  • 数据域用于存储数据。
  • 指针域用于存储下一个结点的地址使链表“连起来”。

这里我们以存储整型(int)的数据为例创建结点。

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data; 数据域用于存储该结点的数据
	struct SListNode* next;//指针域用于存放下一个结点的地址
}SLTNode;

功能接口

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include<stdbool.h>
// 要改变传过来的指向第一个节点的指针就传二级
// 不改变传过来的指向第一个节点的指针就传一级

//读写修改的函数传二级指针

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

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

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

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

//只读的函数接口传一级指针
SLTNode* BuySListNode(SLTDataType x);//创建新节点

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

int SListSize(SLTNode* phead);//查看数据元素个数

bool SListEmpty(SLTNode* phead);//判空  

SLTNode* SListFind(SLTNode* phead, SLTDataType x);//查找元素

// 在pos位置之前去插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//效率不高得找插入前面的结点
//在pos位置后面去插入x
void SListInsertAfter(SLTNode* pos, SLTDataType x);


// 删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos);//删除pos位置
void SListEraseAfter(SLTNode* pos);//删除pos后面位置


void SListDestory(SLTNode** pphead);//销毁结点

打印单链表

打印链表时我们需要从头指针指向的位置开始依次向后打印直到指针指向NULL时结束打印。

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

增加结点

每当我们需要增加一个结点之前我们必定要先申请一个新结点然后再插入到相应位置

SLTNode* BuySListNode(SLTDataType x)//创建新节点
{
	SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
	if (node == NULL)
	{
		printf("malloc fall!\n");
		exit(-1);
	}
	node->data = x;
	node->next = NULL;
	return node;//返回新结点地址
}

插入操作增

单链表的尾插

尾插的时候我们需要先判断链表是否为空若为空则直接让头指针指向新结点即可若不为空我们首先需要利用循环找到链表的最后一个结点然后让最后一个结点的指针域指向新结点。

void SListPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
	assert(pphead);

	if (*pphead == NULL)//判断是否为空表
	{
		SLTNode* newnode = BuySListNode(x);
		*pphead = newnode;
	}
	
	else
	{
		//找尾
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		SLTNode* newnode = BuySListNode(x);
		tail->next = newnode;
	}
}

注增加节点BuySListNode()的函数本身就已经将新节点指针域置空所以尾插时不需要再将新结点的指针域置空。

单链表的头插

头插时我们只需要先让新结点的指针域指向即原来的第一个结点的位置然后把新结点的地址给头指针变量即可。

void SListPushFront(SLTNode** pphead, SLTDataType x)//头插
{
		SLTNode* newnode = BuySListNode(x);
		newnode->next = *pphead;
		*pphead = newnode;
}

注上面两步操作的顺序不能颠倒若先让头指针指向新结点即先让新节点作为头指针那么就无法找到原来第一个结点的位置了即原来第一个结点的位置没有保存。

在给定位置之后插入

在给定位置后插入结点也只需要两步先让新结点的指针域指向该位置pos的下一个结点然后再让该位置pos的结点指向新结点即可。

//在pos位置后面去插入x
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySListNode(x);
	//下面两行代码的顺序不能换防止该位置pos的下一个结点地址因为没保存而找不到
	newnode->next = pos->next;
	pos->next = newnode;
}
在给定位置之前插入

要想在给定位置的前面插入一个新结点我们首先还是要找到该位置之前的一个结点然后让新结点的指针域指向位置为pos的结点让前一个结点的指针域指向新结点即可。需要注意的是当给定位置为头指针指向的位置时相当于头插。

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)// 在pos位置之前去插入x
{
	assert(pphead);
	assert(pos);

	// 1、头插
	if (*pphead == pos)
	{
		SListPushFront(pphead, x);
	}
	// 2、后面插入
	else
	{
		SLTNode* prev = *pphead;//接收头指针
		while (prev->next != pos)
		{
			prev = prev->next;
		}
	    // 找到pos位置的前一个节点,prev存的就是它的地址
		SLTNode* newnode = BuySListNode(x);
		newnode->next = pos;//让新结点的指针域指向位置为pos的结点
		prev->next = newnode;//让pos位置的前一个结点指向新结点
	}
}

**

注意单链表不适合在pos的位置之前插入元素因为需要找前一个位置

**

删除操作删

单链表的头删

头删较为简单若为空表则不必做处理若不为空表则直接让头指针指向第二个结点然后释放第一个结点的内存空间即可。

void SListPopFront(SLTNode** pphead)//头删
{
	
	//链表为空,断言检测
	assert(*pphead != NULL);

	SLTNode* newnode = (*pphead)->next;
	free(*pphead);
	(*pphead) = newnode;
}
单链表的尾删

我们需要考虑三种不同的情况

1、当链表为空时不做处理。
2、当链表中只有一个结点时直接释放该结点然后将头指针置空。
3、当链表中有多个结点时我们需要先找到最后一个结点的前一个结点然后将最后一个结点释放将前一个结点的指针域置空使其成为新的尾结点。

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

	//链表为空断言
	assert(*pphead != NULL);
	//1.一个结点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//2.多个结点
	else
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail=NULL;
		prev->next = NULL;
	}	
}
删除给定位置的结点

要删除给定位置的结点我们首先要判断该结点是否为第一个结点若是则操作与头删相同若不是我们就需要先找到待删除结点的前一个结点然后让其指向待删除结点的后一个结点最后才能释放待删除的结点。

void SListErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	//1.如果待删除的结点为第一个结点,则调用头删即可
	if (pos== *pphead)
	{
		SListPopFront(pphead);
	}
    //2.删除非头节点
	else
	{
		//找pos的前一个结点
		SLTNode* prev =* pphead;
		while (prev->next!=pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
删除给定位置之后的结点

要删除给定位置之后的值我们首先判断传入地址是否为最后一个结点的地址若是则不做处理因为最后一个结点后面没有结点可删除。若不是最后一个结点我们首先让地址为pos的结点指向待删除结点的后一个结点然后将待删除结点释放即可。

void SListEraseAfter(SLTNode* pos)
{
	assert(pos);//确保传入地址不为空
	if (pos->next != NULL)
	{
		SLTNode* nwenode = pos->next->next;

		free(pos->next);
		pos->next = NULL;
		pos->next = nwenode;	
	}
	else
	{
		printf("后面没有元素可删!\n");
	}
}

查找数据查

查找数据相对于前面的来说就非常简单了我们只需要遍历一遍链表在遍历的过程中若找到了目标结点则返回结点的地址若遍历结束也没有找到目标结点则直接返回空指针。

SLTNode* SListFind(SLTNode* phead, SLTDataType x)//查找元素
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
		
	}
	return NULL;//没有找到数据为x的结点
}

修改数据改

//修改数据
void SListModify(SLTNode* pos, SLTDataType x)
{
	pos->data = x;//将结点的数据改为目标数据
}

查看链表元素个数

int SListSize(SLTNode* phead)//查看数据元素个数
{
	int size = 0;
	SLTNode* cur = phead;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

判空

//bool 只有真和假
bool SListEmpty(SLTNode* phead)//判空
{
	//法一
	//return phead == NULL;//空为真非空为假用01表示
	//法二
	return phead == NULL ? true : false;//空为真非空为假用01表示
}

销毁所有节点

void SListDestory(SLTNode** pphead)//销毁结点
{
	assert(pphead);

	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);

		cur = next;
	}
	*pphead = NULL;
}

测试案例

test1手动创建链表并输出

void TestSList1()//手动创建链表
{
	SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));
	n1->data = 1;

	SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));
	n2->data = 2;

	SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));
	n3->data = 3;

	SLTNode* n4 = (SLTNode*)malloc(sizeof(SLTNode));
	n4->data = 4;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;

	SLTNode* plist = n1;
	SListPrint(plist);
}
int main()
{
	TestSList1();
	return 0;
}

在这里插入图片描述

test2插入删除测试

void TestSList2()
	{
	SLTNode* plist = NULL;
	SListPushFront(&plist, -1);//头插
	SListPrint(plist);

	SListPushBack(&plist, 1);//尾插
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);  

	SListPrint(plist);

	SListPushFront(&plist, 0);//头插
	SListPrint(plist);

	SListPopBack(&plist);//尾删
	SListPopBack(&plist);//尾删
	SListPopBack(&plist);//尾删
	SListPopBack(&plist);//尾删
	SListPrint(plist);

	SListPopFront(&plist);//头删
	SListPrint(plist);

	printf("SListSize:%d\n", SListSize(plist));//查看当前链表元素个数
	printf("SListEmpty:%d\n", SListEmpty(plist));//判空操作

	}
int main()
{
	TestSList2();
	return 0;
}

在这里插入图片描述

test3查找元素并修改元素

TestSList3()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);//尾插
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushBack(&plist, 5);
	SListPrint(plist);
	int n = 0;
	printf("请输入需要查找的元素");
	scanf("%d", &n);
	SLTNode* pos = SListFind(plist,n);//查找元素
	if (pos)
	{
		printf("找到了!\n");
		//用SListFind找到元素返回的是结点指针,就可以修改此元素
		int m = 0;
		printf("请修改元素为:");
		scanf("%d", &m);

		SListModify(pos, 20);

		SListPrint(plist);
	}
	else
	{
		printf("没找到!\n");
	}
}
int main()
{
	TestSList3();
	return 0;
}

在这里插入图片描述

test4指定位置插入元素

TestSList4()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);//尾插
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushBack(&plist, 5);
	SListPrint(plist);
	int n = 0;
	printf("请输入需要查找的元素");
	scanf("%d", &n);
	SLTNode* pos = SListFind(plist, n);//查找元素
	if (pos)
	{
		printf("找到了!\n");
		int m = 0;
		printf("请输入插入元素:");
		scanf("%d", &m);
		SListInsert(&plist,pos, m);// 在pos位置之前去插入元素
		SListInsertAfter(pos, -1);//在pos位置后面去插入元素
		SListPrint(plist);
	}
}
int main()
{
	TestSList4();
	return 0;
}

在这里插入图片描述

test5删除指定位置元素

TestSList5()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);//尾插
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushBack(&plist, 5);
	SListPrint(plist);
	int n = 0;
	printf("请输入需要查找的元素");
	scanf("%d", &n);
	SLTNode* pos = SListFind(plist, n);//查找元素
	if (pos)
	{
		printf("找到了,并且会依次删除pos位置之后的元素以及pos位置的元素~\n");
		SListEraseAfter(pos);
		SListPrint(plist);

		SListErase(&plist, pos);
		SListPrint(plist);
	}
	else
	{
		printf("没有此元素\n");
	}
	SListDestory(&plist);//销毁结点
	SListPrint(plist);
}
int main()
{
	TestSList5();
	return 0;
}

在这里插入图片描述

the end

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
返回列表

上一篇：尚硅谷ES6李强笔记

下一篇：6.R语言【频数、频率统计函数】一维、二维、三维

“【链表】无头单向非循环链表” 的相关文章

中科蓝讯读取CSV文件中地址来指定地址段烧录1年前 (2023-02-02)
基于Android 的校园疫情防控管理系统设计与实现1年前 (2023-02-02)
主题 2 Shell工具和脚本1年前 (2023-02-02)
[20221227]a mutating table error without a trigger!.txt1年前 (2023-02-02)
微信小程序｜基于小程序+C#制作一个聊天系统_c#微信小程序开发1年前 (2023-02-02)
vue3实现一个抽奖小项目1年前 (2023-02-02)
【RocketMQ】消息拉模式分析1年前 (2023-02-02)
腾讯会议使用OBS虚拟摄像头_obs虚拟摄像头1年前 (2023-02-02)
Git的安装，理论基础与基本使用1年前 (2023-02-02)
C++Day12 虚拟继承内存布局测试1年前 (2023-02-02)

阿里云国际版