数据结构之单链表

  • 开发
  • 30

数据结构之单链表

1. 链表的概念及结构

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

如图所示:
在这里插入图片描述
与顺序表不同的是，链表⾥的每个节点都是申请下来的空间，我们称之为“结点/节点”，节点的组成主要两个部分：当前节点要保存的数据和保存下⼀个节点的地址（指针变量）。

图中指针变量 plist保存的是第⼀个节点的地址，我们称plist此时“指向”第⼀个节点，如果我们希望plist“指向”第⼆个节点时，只需要修改plist保存的内容为 0x0012FFA0。

为什么还需要指针变量来保存下一个节点的位置？

链表中每个节点都是独立申请的（即需要插入数据时才去申请一块节点的空间），我们需要通过指针变量来保存下一个节点位置才能从当前节点找到下⼀个节点。

每个节点对应的结构体代码：

typedef int SLTDataType;

//链表是由节点组成的
typedef struct SListNode
{
   
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

当我们想要保存一个整型数据时，实际是向操作系统申请了一块内存，这个内存不仅要保存整型数据，也需要保存下一个节点的地址（当下⼀个节点为空时保存的地址为空）。
当我们想要从第⼀个节点⾛到最后⼀个节点时，只需要在前⼀个节点拿上下⼀个节点的地址就可以了。

然后我们用这个类型定义几个节点

#include "SList.h"
int main()
{
   
	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
	node1->data = 1;
	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	node2->data = 2;
	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	node3->data = 3;
	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
	node4->data = 4;
	
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;
	SLTNode* plist = node1;
	SLTPrint(plist);
	return 0;
}

我们写一个打印链表的函数
思路:

依次遍历链表中的每个节点直到遇到NULL指针停止。

//打印单链表
void SLTPrint(SLTNode* phead)
{
   
	SLTNode* pcur = phead;
	while (pcur)
	{
   
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

画图分析：
在这里插入图片描述

运行结果如图:
在这里插入图片描述

补充说明：

  1. 链式机构在逻辑上是连续的，在物理结构上不⼀定连续
  2. 节点⼀般是从堆上申请的
  3. 从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续

2. 单链表的各个函数

实现
申请一个节点

//申请一个节点
SLTNode* SLTBuyNode(SLTDataType x)
{
   
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
   
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

这里一定不要把最后一句代码return newnode;遗忘掉。

尾插节点

//尾插节点
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
   
	assert(pphead);
	SLTNode* newnodes = SLTBuyNode(x);
	//链表为空,新节点作为phead
	if (*pphead == NULL)
	{
   
		*pphead = newnodes;
	}
	//链表不为空,找尾节点
	else
	{
   
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
   
			ptail = ptail->next;
		}
		//patil就是尾节点
		ptail->next = newnodes;
	}
}

头插节点

//头插节点
void SLTPushFornt(SLTNode** pphead, SLTDataType x)
{
   
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

尾删节点

//尾删节点
void SLTPopBack(SLTNode** pphead)
{
   
	assert(pphead);
	//链表为空
	assert(*pphead);
	//链表只有一个节点
	if ((*pphead)->next == NULL)
	{
   
		*pphead = NULL;
	}
	//链表有多个节点
	else
	{
   
		SLTNode* ptail = *pphead;
		SLTNode* prev = NULL;
		while (ptail->next)
		{
   
			prev = ptail;
			ptail = ptail->next;
		}
		free(ptail);
		ptail = NULL;
		prev->next = NULL;
	}
}

头删节点

//头删节点
void SLTPopFornt(SLTNode** pphead)
{
   
	assert(pphead);
	//链表不为空
	assert(*pphead);
	//让第二个节点成为新头
	//把旧空间释放
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

查找节点

//查找节点
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{
   
	SLTNode* pcur = *pphead;
	while (pcur)
	{
   
		if (pcur->data == x)
		{
   
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

在指定位置之前插入数据

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
   
	assert(pphead);
	assert(pos);
	assert(*pphead);
	SLTNode* newnode = SLTBuyNode(x);

	if (pos == *pphead)
	{
   
		SLTPushFornt(pphead, x);
		return;
	}

	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
   
		prev = prev->next;
	}
	newnode->next = pos;
	prev->next = newnode;
}

在指定位置之后插入数据

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
   
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	/*SLTNode* next = pos->next;
	newnode->next = next;*/
	newnode->next = pos->next;
	pos->next = newnode;
}

删除pos节点

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
   
	assert(pphead);
	assert(*pphead);
	assert(pos);

	if (*pphead == pos)
	{
   
		SLTPopFornt(pphead);
		return;
	}

	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
   
		prev = prev->next;
	}
	SLTNode* next = pos->next;
	free(pos);
	pos = NULL;
	prev->next = next;
}

删除pos之后节点

//删除pos之后节点
void SLTEraseAfter(SLTNode* pos)
{
   
	assert(pos);
	assert(pos->next);
	SLTNode* next = pos->next->next;
	free(pos->next);
	pos->next = next;
}

销毁链表

//销毁链表
void SLTDestory(SLTNode** pphead)
{
   
	assert(pphead);
	assert(*pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
   
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

3. 链表全部代码实现

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;

//打印节点
void SLTPrint(SLTNode* phead);

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

//头插节点
void SLTPushFornt(SLTNode** pphead, SLTDataType x);

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

//头删节点
void SLTPopFornt(SLTNode** pphead);

//查找节点
SLTNode* SLTFind(SLTNode* phead,SLTDataType x);

//在指定位置插入数据

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x);

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

//在指定位置删除节点

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);

//删除pos之后节点
void SLTEraseAfter(SLTNode* pos);

//销毁链表
void SLTDestory(SLTNode** pphead);

SList.c

#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"

//打印单链表
void SLTPrint(SLTNode* phead)
{
   
	SLTNode* pcur = phead;
	while (pcur)
	{
   
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

SLTNode* SLTBuyNode(SLTDataType x)
{
   
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
   
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

//尾插节点
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
   
	assert(pphead);
	SLTNode* newnodes = SLTBuyNode(x);
	//链表为空,新节点作为phead
	if (*pphead == NULL)
	{
   
		*pphead = newnodes;
	}
	//链表为空,找尾节点
	else
	{
   
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
   
			ptail = ptail->next;
		}
		//patil就是尾节点
		ptail->next = newnodes;
	}
}

//头插节点
void SLTPushFornt(SLTNode** pphead, SLTDataType x)
{
   
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

//尾删节点
void SLTPopBack(SLTNode** pphead)
{
   
	assert(pphead);
	//链表为空
	assert(*pphead);
	//链表只有一个节点
	if ((*pphead)->next == NULL)
	{
   
		*pphead = NULL;
	}
	//链表有多个节点
	else
	{
   
		SLTNode* ptail = *pphead;
	/*	SLTNode* prev = NULL;
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		free(ptail);
		ptail = NULL;
		prev->next = NULL;*/

		while (ptail->next->next)
		{
   
			ptail = ptail->next;
		}
		free(ptail->next);
		ptail->next = NULL;
	}
}

//头删节点
void SLTPopFornt(SLTNode** pphead)
{
   
	assert(pphead);
	//链表不为空
	assert(*pphead);
	//让第二个节点成为新头
	//把旧空间释放
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

//查找节点
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{
   
	SLTNode* pcur = *pphead;
	while (pcur)
	{
   
		if (pcur->data == x)
		{
   
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
   
	assert(pphead);
	assert(pos);
	assert(*pphead);
	SLTNode* newnode = SLTBuyNode(x);

	if (pos == *pphead)
	{
   
		SLTPushFornt(pphead, x);
		return;
	}

	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
   
		prev = prev->next;
	}
	newnode->next = pos;
	prev->next = newnode;
}

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
   
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	/*SLTNode* next = pos->next;
	newnode->next = next;*/
	newnode->next = pos->next;
	pos->next = newnode;
}

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
   
	assert(pphead);
	assert(*pphead);
	assert(pos);

	if (*pphead == pos)
	{
   
		SLTPopFornt(pphead);
		return;
	}

	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
   
		prev = prev->next;
	}
	SLTNode* next = pos->next;
	free(pos);
	pos = NULL;
	prev->next = next;
}

//删除pos之后节点
void SLTEraseAfter(SLTNode* pos)
{
   
	assert(pos);
	assert(pos->next);
	SLTNode* next = pos->next->next;
	free(pos->next);
	pos->next = next;
}

//销毁链表
void SLTDestory(SLTNode** pphead)
{
   
	assert(pphead);
	assert(*pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
   
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"

int main()
{
   
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);


	SLTNode* FindRet = SLTFind(&plist, 3);
	if (FindRet == NULL)
	{
   
		printf("找不到\n");
	}
	else
	{
   
		printf("找到了\n");
	}
	SLTDestory(&plist);
	return 0;
}

运行结果如图:
在这里插入图片描述

阅读全部

相关推荐

最近更新

  4. TCP协议是安全的吗?

    2024-02-01 20:52:02       18 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2024-02-01 20:52:02       19 阅读

  13. 【Python教程】压缩PDF文件大小

    2024-02-01 20:52:02       18 阅读

  18. 通过文章id递归查询所有评论（xml）

    2024-02-01 20:52:02       20 阅读

热门阅读

  2. 台达dvp16es2plc-qt串口通信协议

    2024-02-01 20:52:02       28 阅读
  4. C++入门

    C++入门

    2024-02-01 20:52:02      25 阅读

  8. 项目解决方案：市小区高清视频监控平台联网整合设计方案(下)

    2024-02-01 20:52:02       30 阅读

  10. 2024美赛数学建模D题思路+模型+代码+论文（持续更新）

    2024-02-01 20:52:02       37 阅读

  12. 使用android辅助服务监听Activity打开

    2024-02-01 20:52:02       25 阅读

  15. 被审查？ChatGPT陷入数据风波！

    2024-02-01 20:52:02       31 阅读

  17. （蓝桥杯每日一题）游戏最优解及求二进制中有多少1

    2024-02-01 20:52:02       29 阅读

  19. M1芯片MAC 安装MySQL、Nacos遇到的问题

    2024-02-01 20:52:02       32 阅读

  23. 【SpringBoot】如何在 Utils 工具类中注入 Bean

    2024-02-01 20:52:02       29 阅读

  30. 每日打卡 力扣2808 使循环数组所有元素相等的最少秒数

    2024-02-01 20:52:02       37 阅读