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

（数据结构）单链表——C语言

article 2024/10/20 13:30:56

目录

1 概念与结构

1.1 结点

1.2 链表的性质

2 实现单链表

2.1打印SLPrint

2.2申请一个结点SLBuyNode

2.3尾插SLPushBack

2.4头插SLPushfront

2.5尾删SLPopBack

2.6头删SLPopfront

2.7查找结点位置SLFindNode

2.8在pos位置插入SLInsert

2.9在pos节点之后插入SLInsertAfter

2.10删除pos位置的结点SLErase

2.11删除pos位置之后后的结点SLEraseAfter

2.12销毁链表SLDestory

3.整体代码

1 概念与结构

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

1.1 结点

与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“结点/结点” 结点的组成主要有两个部分：当前结点要保存的数据和保存下⼀个结点的地址（指针变量）。 图中指针变量head保存的是第⼀个结点的地址，我们称head此时“指向”第⼀个结点，如果我们希望 head“指向”第⼆个结点时，只需要修改head保存的内容为0x0012。 链表中每个结点都是独⽴申请的（即需要插⼊数据时才去申请⼀块结点的空间），我们需要通过指针 变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。

1.2 链表的性质

1、链式机构在逻辑上是连续的，在物理结构上不⼀定连续

2、结点⼀般是从堆上申请的

3、从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续

结点对应的结构体代码：

struct SListNode
{
    int data; //结点数据
    struct SListNode* next; //指针变量⽤保存下⼀个结点的地址
};

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

2 实现单链表

这里也是先建三个文件，SList.h,SList.c,test.c,分别为头文件，实现函数的文件，测试文件

SList.h

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

typedef int SLDataType;

typedef struct SLNode
{
	SLDataType data;
	struct SLNode* next;
}SLNode;

void SLPrint(SLNode* phead);
SLNode* SLBuyNode(SLDataType x);

void SLPushBack(SLNode** pphead, SLDataType x);
void SLPushfront(SLNode** pphead, SLDataType x);
void SLPopBack(SLNode** pphead);
void SLPopfront(SLNode** pphead);

SLNode* SLFindNode(SLNode* phead, SLDataType x);
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x);
void SLInsertAfter( SLNode* pos,SLDataType x);
void SLErase(SLNode** pphead, SLNode* pos);
void SLEraseAfter(SLNode* pos);
void SLDestory(SLNode** pphead);

包括了结构体SLNode表示结点，这里有一个结构体自引用，用来找到下一个结点位置，以及实现的各种函数这里typedef的SLDataType，便于后续修改数据类型，这里以int类型为例。

2.1打印SLPrint

void SLPrint(SLNode* phead)
{
	SLNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

这里定义一个指向头结点的指针，当pcur不为NULL时，就打印pcur->data,pcur等于指向pcur的下一个节点，相当于循环里面的++,这是单链表遍历的方式,直到pcur为NULL停止。

2.2申请一个结点SLBuyNode

SLNode* SLBuyNode(SLDataType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

这里申请一个结点，所以返回类型是这个结构体指针，利用malloc函数申请，注意判断是否申请成功，再将值赋给newnode->data,newnode的下一个节点为NULL。

2.3尾插SLPushBack

void SLPushBack(SLNode** pphead, SLDataType x)
{
	assert(pphead);
	SLNode* newnode = SLBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else 
	{
		SLNode* ptail = *pphead;
		while (ptail->next)
		{
		ptail = ptail->next;
		}
	ptail->next = newnode;
	}
}

尾插即从链表尾部插入，注意这里传参需要传二级指针，因为这里可能会引起头结点的改变，要使实参的改变，就要传它的指针，本身它就是一级指针，所以这里传二级，首先断言pphead不能指为空，申请一个结点，如果链表为空，则直接将申请的结点直接赋给头结点，如果链表不为空，因为链表只能从上一个结点找到下一个，所以尾插之前，就要找到尾结点，就需要遍历整个链表，再将尾结点的下一个结点，指向newnode，即可。

2.4头插SLPushfront

void SLPushfront(SLNode** pphead, SLDataType x)
{
	assert(pphead);
	SLNode* newnode = SLBuyNode(x);

	newnode->next = *pphead;
	*pphead = newnode;
}

从头部插入，还是断言，然后申请一个节点，头插较为简单，直接将申请节点的next指向头结点，再将newnode赋给头结点。

2.5尾删SLPopBack

void SLPopBack(SLNode** pphead)
{
	assert(pphead && *pphead);
	SLNode* prev = *pphead;
	SLNode* ptail = *pphead;
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		prev->next = NULL;
		free(ptail);
		ptail = NULL;
	}
	
}

从尾部删除元素，和尾插一样，如果链表只有一个结点直接free，置空就可以，如果链表不止一个结点，需要遍历，定义尾结点的前一个结点为prev，向后遍历两个依次向后移动直到ptail->next为空就停止，找到尾结点的前一个结点，再将prev的next置为空，然后free掉ptail就可以了。

2.6头删SLPopfront

void SLPopfront(SLNode** pphead)
{
	assert(pphead && *pphead);

	SLNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

从头部删除，先定义头结点的next结点，free掉头结点，再将next结点赋给next，成为新的头结点。

2.7查找结点位置SLFindNode

SLNode* SLFindNode(SLNode* phead, SLDataType x)
{
	assert(phead);
	SLNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;

查找，不会影响头结点的改变，所以这里可以传一级指针，这里就和尾插一样遍历，加一个判断pcur->data是否相等x，返回其结点就行，如果未找到就返回NULL。

2.8在pos位置插入SLInsert

void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{
	assert(pphead && *pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLPushfront(pphead, x);
	}
	else
	{
	SLNode* prev = *pphead;
	SLNode* newnode = SLBuyNode(x);
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	newnode->next=pos;
	prev->next = newnode;
	}
}

在pos位置插入一个结点，先申请一个节点，如果在头结点位置插入，直接调用头插函数，如果不是头结点的位置，然后像尾差一样向后遍历找到pos的前一个节点，再将newnode的下一个结点指向pos，pos的前一个结点的next指向newnode即完成插入。

2.9在pos节点之后插入SLInsertAfter

void SLInsertAfter(SLNode* pos, SLDataType x)
{
	assert(pos);
	SLNode* newnode = SLBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

在pos之后，插入不需要遍历，直接在pos后插入，申请完节点后，直接将newnode->next结点指向pos的next，再将pos的next指向newnode。

2.10删除pos位置的结点SLErase

void SLErase(SLNode** pphead, SLNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	SLNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	prev->next = pos->next;
	free(pos);
	pos = NULL;
}

这里删除结点，要断言，链表不为空，pos位置存在，和尾删一样遍历找到pos位置之前的prev，直接将prev的next指向pos的next，释放掉pos的空间，即删除结点。

2.11删除pos位置之后后的结点SLEraseAfter

void SLEraseAfter(SLNode* pos)
{
	assert(pos&&pos->next!=NULL);
	SLNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

删除pos位置的节点，将pos的next定义为del，再将pos->next指向del->next,再释放掉del，置为NULL。

2.12销毁链表SLDestory

void SLDestory(SLNode** pphead)
{
	SLNode* pcur=*pphead;
	while (pcur)
	{
		SLNode*next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

循环链表，依次删除，直到pcur为空，最后再将头结点释放掉，置为空。

3.整体代码

SList.h

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

typedef int SLDataType;

typedef struct SLNode
{
	SLDataType data;
	struct SLNode* next;
}SLNode;

void SLPrint(SLNode* phead);
SLNode* SLBuyNode(SLDataType x);

void SLPushBack(SLNode** pphead, SLDataType x);
void SLPushfront(SLNode** pphead, SLDataType x);
void SLPopBack(SLNode** pphead);
void SLPopfront(SLNode** pphead);

SLNode* SLFindNode(SLNode* phead, SLDataType x);
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x);
void SLInsertAfter( SLNode* pos,SLDataType x);
void SLErase(SLNode** pphead, SLNode* pos);
void SLEraseAfter(SLNode* pos);
void SLDestory(SLNode** pphead);

SList.c

#include"SList.h"

void SLPrint(SLNode* phead)
{
	SLNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

SLNode* SLBuyNode(SLDataType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

void SLPushBack(SLNode** pphead, SLDataType x)
{
	assert(pphead);
	SLNode* newnode = SLBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else 
	{
		SLNode* ptail = *pphead;
		while (ptail->next)
		{
		ptail = ptail->next;
		}
	ptail->next = newnode;
	}
}

void SLPushfront(SLNode** pphead, SLDataType x)
{
	assert(pphead);
	SLNode* newnode = SLBuyNode(x);

	newnode->next = *pphead;
	*pphead = newnode;
}

void SLPopBack(SLNode** pphead)
{
	assert(pphead && *pphead);
	SLNode* prev = *pphead;
	SLNode* ptail = *pphead;
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		prev->next = NULL;
		free(ptail);
		ptail = NULL;
	}
	
}

void SLPopfront(SLNode** pphead)
{
	assert(pphead && *pphead);

	SLNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

SLNode* SLFindNode(SLNode* phead, SLDataType x)
{
	assert(phead);
	SLNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{
	assert(pphead && *pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLPushfront(pphead, x);
	}
	else
	{
	SLNode* prev = *pphead;
	SLNode* newnode = SLBuyNode(x);
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	newnode->next=pos;
	prev->next = newnode;
	}
}

void SLInsertAfter(SLNode* pos, SLDataType x)
{
	assert(pos);
	SLNode* newnode = SLBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

void SLErase(SLNode** pphead, SLNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	SLNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	prev->next = pos->next;
	free(pos);
	pos = NULL;
}

void SLEraseAfter(SLNode* pos)
{
	assert(pos&&pos->next!=NULL);
	SLNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

void SLDestory(SLNode** pphead)
{
	SLNode* pcur=*pphead;
	while (pcur)
	{
		SLNode*next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}


http://www.kler.cn/news/357342.html

相关文章：

  • 吴恩达深度学习笔记：卷积神经网络（Foundations of Convolutional Neural Networks）3.5-3.6
  • 十五、行为型（迭代器模式）
  • 探索GenAI/大模型评估与对比：AutoArena开源框架及产品介绍
  • Azure OpenAI 服务上线具有音频和语音功能的 GPT-4o-Realtime-Preview，免费申请试用
  • 文本生成视频技术：艺术与科学的交汇点
  • Perl打印9x9乘法口诀
  • 【练习题】设计循环队列
  • OJ-两个字符串间的最短路径问题
  • 在数据库中，`SELECT`, `FROM`, `JOIN`, `ON`, 和 `WHERE`各自的作用
  • csp普及组算法集训--Dfs
  • 一级注册消防工程师《消防安全技术实务》模拟试题及详解
  • 详解mac系统通过brew安装mongodb与使用
  • SpringCloud学习：Spring Cloud Alibaba Nacos（服务注册中心、配置管理中心）
  • PyTorch 实现自然语言分类
  • [PHP]Undefined index错误只针对数组
  • 如何有效保障专线健康：运维团队的专线监控策略
  • yjs机器学习数据操作01——数据的获取、可视化
  • 基于Flink MySQL CDC技术实现交易告警
  • 三、数据聚合和函数
  • 个人主页模版（源代码开源）