数据结构：单链表的实现(C语言)

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

在这里插入图片描述

个人主页 水月梦镜花
个人专栏 《C语言》 《数据结构》

文章目录

前言

本博客将要实现的无头单向不循环链表。

一、单链表实现思路和图解

1.节点的定义(SListNode)

我们将节点定义为如下结构
在这里插入图片描述
其成员变量有datanext。

将int重命名为STLDataType方便我们以后修改数据域的内容。

//无头单向不循环链表
typedef int SLTDataType;

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

2.申请一个节点(BuySListNode)

动态申明一个空间来放置数据。如下
在这里插入图片描述
将data的内容置成形参xnext置NULL。

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

	retur

3.单链表打印(SListPrint)

循环遍历链表直到尾节点。创建一个结构体指针变量cur循环cur = cur->next并打印cur->data的内容直到cur == NULL。
在这里插入图片描述

//单链表打印
void SListPrint(SListNode* plist)
{
	SListNode* cur = plist;

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

4.单链表尾插(SListPushBack)

  • 如果链表不为NULL(链表中有元素)要先遍历链表找到尾节点在让尾节点指向新节点完成尾插。
  • 如果链表为NULL(链表中没有元素)此时应该直接让新节点等于头结点完成尾插。(本链表是无哨兵位的)
  • 如果传入的头结点无效直接判错。

在这里插入图片描述

在这里插入图片描述
当链表为NULL我们就要修改头结点本身的内容所以我们需要头结点的指针而本文中头结点本身就是结构体指针所以尾插函数参数我们需要二级指针。

//单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x)
{
	assert(pplist);

	SListNode* newnode =  BuySListNode(x);
	if (*pplist != NULL)
	{
		SListNode* cur = *pplist;
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
	else
	{
		*pplist = newnode;
	}
}

5.单链表的头插(SListPushFront)

对于头插而言链表是否有元素并不重要我们只需要让新节点的指向头结点并将头结点等于新节点。

在这里插入图片描述
因为头插链表一定会改变头结点的内容所以我们头插函数的形参也是二级指针。

//单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x)
{
	assert(pplist);

	SListNode* newnode = BuySListNode(x);
	
	newnode->next = *pplist;
	*pplist = newnode;
}

6.单链表的尾删(SListPopBack)

  • 如果链表元素有两个及两以上我们需要两个指针变量prevnext来找尾节点循环prev = curcur = cur->next使next指向尾节点prev指向尾节点的前一个free尾节点prev指向的节点指向NULL。
  • 如果链表元素只有一个直接free头结点使头结点置NULL。
  • 如果链表没有元素直接判错。

在这里插入图片描述

在这里插入图片描述
当链表元素只有一个时此时尾删链表要修改头结点的内容尾删函数的形参需要二级指针。

//单链表的尾删
void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	//链表为NULL
	assert(*pplist);

	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* cur = *pplist;
		SListNode* prev = NULL;

		while (cur->next != NULL)
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = NULL;
		free(cur);
	}
}

7.单链表头删(SListPopFront)

我们需要一个结构体指针变量next来保存头结点的下一个节点然后free头结点使头结点 = 指针变量next。

  • 如果链表没有元素直接判错。

在这里插入图片描述

//单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	assert(*pplist);

	SListNode* next = (*pplist)->next;
	free(*pplist);
	*pplist = next;
}

8.单链表的查找(SListFind)

我们需要一个结构体指针变量cur来遍历链表比较cur->data == x如果相等放回此时cur的内容(该节点的地址)。如果遍历完链表并没有相等元素放回NULL。

//单链表的查找
SListNode* SListFind(SListNode* plist, SLTDataType x)
{
	SListNode* cur = plist;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}

	return NULL;
}

9.单链表在pos位置之后插入x(SListInsertAfter)

我们让newnode指向pos下一个的节点pos指向newnode。

  • 如果我们先让pos指向newnodenewnode在指向pos的下一个节点就会造成newnode指向自己导致链表成环。
  • 该函数不会影响头结点的内容所以函数的形参不用二级指针。

在这里插入图片描述


//单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);

	SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

10.单链表删除在pos位置之后的值(SListEraseAfter)

我们需要一个结构体指针变量next记录pos下一个节点的地址然后是pos指向next的下一个节点接着free(next)。

  • 如果链表只有一个元素我们不能调用该函数否则会导致NULL指针的解引用。
  • 该函数不会改变头结点的内容所以形参我们不用二级指针。

在这里插入图片描述


//单链表删除在pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
	assert(pos && pos->next);

	SListNode* next = pos->next;
	pos->next = next->next;
	free(next);
}

11.单链表的销毁(SListDestroy)

我们需要两个结构体指针prevcur。先让prev = cur cur再指向下一个节点free(prev)重复上述操作直到cur指向NULL。

在这里插入图片描述
需要我们在函数调用完后自己对头结点置NULL。

//单链表的销毁
void SListDestroy(SListNode* plist)
{
	assert(plist);

	SListNode* cur = plist;
	while (cur != NULL)
	{
		SListNode* prev = cur;
		cur = cur->next;
		free(prev);
	}
}

二、代码实现

//slist.h  文件


#pragma once
#define _CRT_SECURE_NO_WARNINGS 1

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

//无头单向不循环链表
typedef int SLTDataType;

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


//申请一个节点
SListNode* BuySListNode(SLTDataType x);

//单链表打印
void SListPrint(SListNode* plist);

//单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x);

//单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x);

//单链表的尾删
void SListPopBack(SListNode** pplist);

//单链表头删
void SListPopFront(SListNode** pplist);

//单链表的查找
SListNode* SListFind(SListNode* plist, SLTDataType x);

//单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x);

//单链表删除在pos位置之后的值
void SListEraseAfter(SListNode* pos);

//单链表的销毁
void SListDestroy(SListNode* plist);

//slist.c    文件


#include "slist.h"

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

	return newnode;
}


//单链表打印
void SListPrint(SListNode* plist)
{
	SListNode* cur = plist;

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


//单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x)
{
	assert(pplist);

	SListNode* newnode =  BuySListNode(x);
	if (*pplist != NULL)
	{
		SListNode* cur = *pplist;
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
	else
	{
		*pplist = newnode;
	}
}


//单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x)
{
	assert(pplist);

	SListNode* newnode = BuySListNode(x);
	
	newnode->next = *pplist;
	*pplist = newnode;
}

//单链表的尾删
void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	//链表为NULL
	assert(*pplist);

	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* cur = *pplist;
		SListNode* prev = NULL;

		while (cur->next != NULL)
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = NULL;
		free(cur);
	}
}


//单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	assert(*pplist);

	SListNode* next = (*pplist)->next;
	free(*pplist);
	*pplist = next;
}


//单链表的查找
SListNode* SListFind(SListNode* plist, SLTDataType x)
{
	SListNode* cur = plist;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}

	return NULL;
}

//单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);

	SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}


//单链表删除在pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
	assert(pos && pos->next);

	SListNode* next = pos->next;
	pos->next = next->next;
	free(next);
}


//单链表的销毁
void SListDestroy(SListNode* plist)
{
	assert(plist);

	SListNode* cur = plist;
	while (cur != NULL)
	{
		SListNode* prev = cur;
		cur = cur->next;
		free(prev);
	}
}

总结

以上就是我对于无头单向不循环链表的实现

在这里插入图片描述

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

上一篇：【在英伟达nvidia的jetson-orin-nx上使用调试can基础收发-硬件连接-开机自启动can-初步调试】

下一篇：计算机视觉的延伸整理

“数据结构：单链表的实现(C语言)” 的相关文章

二叉搜索树详解--实现插入和删除1年前 (2023-02-02)
菜鸡的bug-vue组件中传递的数据能显示，但是控制台报not defind的错误1年前 (2023-02-02)
【提升团队运营效率】交易履约之订单中心实践1年前 (2023-02-02)
WPF从零到1教程详解,适合新手上路1年前 (2023-02-02)
【云原生 | 从零开始学istio】二、Istio核心特性与架构_istio 架构变化1年前 (2023-02-02)
关于 Dev-C++ 中缺少 iconv.h 的问题1年前 (2023-02-02)
SQL Father - 模拟数据生成器（后端）1年前 (2023-02-02)
CTF比赛必备常用工具1年前 (2023-02-02)
java中实现创建目录、创建文件的操作_java 创建目录1年前 (2023-02-02)
《鹅鸭杀》爆火，一文带你了解如何实现顶流社交游戏1年前 (2023-02-02)

阿里云国际版