首页 > 其他分享 >数据结构：单链表

数据结构：单链表

时间：2024-09-24 12:21:28浏览次数：3  
标签：pphead 单链 SLTNode NULL pos next 数据结构 节点

单链表

单链表概念与结构

概念：链表是⼀种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
用生活实例比喻就好比我们日常做的高铁火车：
每个列车有n节车厢，每个车厢在组装前都是独立的，当我们需要时，会用一个一个的钩锁将每节车厢链接，每个钩锁就好比指针链接，他将两个不相干的车厢链接。
那链表的车厢（结构）时怎样的？
在这里插入图片描述
本质上就是通过结构体来存放数据与下一个结构体的地址，每个结构体被称为节点。

节点

图中plist存放的时第一个节点的地址（就是列车的车头），我们可以通过地址来找寻下一个节点，通过下一个节点里存放的地址就可以找到第二个节点，这就是节点的作用。

链表的性质

  1. 链式机构在逻辑上是连续的，在物理结构上不⼀定连续
  2. 结点⼀般是从堆上申请的
  3. 从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续
    节点（结构体）的编写：
typedef int SLTDataType//如果要修改数据类型就只用在这里改一下，
//不用在整个程序里面替换数据类型，方面后续修改数据类型的需要
typedef struct SLTNode
{
 SLTDataType data; //结点数据
 struct SListNode* next; //指针保存下⼀个结点的地址
}SLTNode;

单链表的打印

前面我们说了可以通过每个节点存放的地址来找到下一个节点，我们打印链表就可以借助这个特点来打印。

void SLTPrint(SLTNode* phead)
{
assert(phead);
SLTNode* pcur=phead;//保存链表地址，利用这个临时变量来读取内存
while(pcur)
{
	printf("%d->",pcur->data);
	pcur=pcur->next;
}
printf("NULL\n");
}

while循环判定条件的选择：
前面的结构让我们了解到最后一个节点里存放的指针是NULL；
当我们pcur为NULL时，代表我们通过循环访问了每一个节点，每访问一个节点就打印了它的数据，这样我们就打印出了整个链表的数据内容。

实现单链表

创建一个头文件SList.h

#ifndef __SList_H_
#define __SList_H_

#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 SLTPushFront(SLTNode** pphead, SLTDataType x);
//删除
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(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 SListDestroy(SLTNode** pphead);
#endif

接下来在SList.c文件内一个一个实现头文件里面的函数。

创建新的节点

因为要插入数据，就必须创建节点，为了代码的可读性与简洁，我们将创建节点封装为一个函数，写在SList.c文件内部。

SL_BuyNode(SLTDataType x)//x为要写入的数据
{
SLTNode* newnode=(SLTNode*)malloc(sizeof(SLTNode));//采用动态内存管理，方便后续的删除数据等操作
assert(newnode);//防止空间开辟失败
//初始化
newnode->data=x;//保存数据
newnode->next=NULL;//让它指向的下一个节点暂时为空
retuen newnode;//返回新节点的地址
}

在末尾插入数据

思路：
在这里插入图片描述
观察结构图，我们要在尾部插入节点，首先要创建一个新的节点，将新节点的地址赋给原来的末尾节点内的指针；
分析一下执行此操作需要的数据：
原末尾节点的地址
新节点的地址
代码实现：

void SLTPushBack(SLTNode** pphead, SLTDataType x)//这里注意下我们的形参时二级指针
//原因：因为我们尾插时可能会遇到首地址phead为空，也就是一个节点都没有的情况
//所以我们会将节点的地址存放的首地址内部，这样我们就需要改变首地址的内容
//因为形参是实参的临时拷贝，形参的改变不会影响实参，想要形参改变的同时影响到实参，就要使用地址传参，这里接收数据就要使用二级指针
{
assert(pphead);
SLTNode* newnode=SL_BuyNode(x);//创建新节点
if(*pphead==NULL)//链表里面一个节点都没有
{
	*pphead=newnode;
}
else
{
	SLTNode* pcur=*pphead;//这里链表里面以及有节点了，防止改变首地址，我们借用临时变量来操作
	while(pcur->next)//当节点内的next指针指向空，我们就找到了原末尾节点地址
	{
		pcur=pcur->next;
	}
	pcur->next=newnode;
}
}

在头部插入数据

思路：
在这里插入图片描述

  1. 创建一个新节点
  2. 将原首节点的地址存放的新节点内部的指针里
  3. 将首地址plist内存放的地址改为新头节点的地址
    需要的数据：新节点地址，原头节点地址(plist存放的地址)
    代码实现:
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode=SL_BuyNode(x);
	newnode->next=*pphead;
	*pphead=newnode;
}

删除尾部数据

思路：
在这里插入图片描述

  1. 找到倒数第二个节点
  2. 利用free函数释放最后一个节点的空间（最后一个节点的空间在倒数第二个节点内部存放）
  3. 让倒数第二节点内的指针指向NULL；
    需要的数据：倒数第二个节点地址
    代码实现：
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	if((*pphead)->next==NULL)
	{
		free(*pphead);
		*pphead=NULL;
	}
	else
	{
		SLTNode* prv=*NULL;
		SLTNode* pcur=*pphead;
		while(pcur->next==NULL)
		{
			prv=pcur;
			pcur=pcur->next;
		}
		free(pcur);
		prv->next=NULL;
	}
}

删除第一个节点

思路：
在这里插入图片描述

  1. 将第二个节点的地址存放到plist
  2. 释放第一个节点空间
    需要的数据：第二个节点的地址
    代码实现：
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* div = (*pphead)->next;//暂存第二个节点的地址
	free(*pphead);
	*pphead = div;
}

在链表中寻找目标数据

思路：

  1. 通过循环遍历每个节点
  2. 每个节点的数据与目标数据对比
  3. 找到了就返回该节点地址，没找到就返回NULL
    代码实现：
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;;
}

在指定位置之前插入数据

思路：

  1. 创建新的节点
  2. 找到指定位置之前的节点地址
  3. 将新节点的地址存放的指定位置之前的节点中
  4. 将指定位置的节点地址存放到新节点里
    数据需求：指定位置，新的节点，指定位置前的节点地址
    指定位置由函数SLTFind提供。
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && *pphead);
	assert(pos);
	SLTNode* newnode=SL_BuyNode(x);
	if (pos == NULL)//当指定位置为NULL，说明该链表没有节点或者没有我们我要的数据，就将新节点作为头节点
	{
		SLTPushFront(pphead,x);
	}
	else
	{
		SLTNode* prv = *pphead;
		while (prv->next!=pos)
		{
			prv =prv->next;
		}
		newnode->next = pos;
		prv->next = newnode;
	}
}

在指定位置之后插⼊数据

思路：

  1. 创建新节点
  2. 找到指定位置
  3. 将指定位置后节点地址放到newnode里面
  4. 将newnode的地址放到指定位置节点里
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode=SL_BuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

删除pos结点

思路：

  1. 找到该位置下一个节点地址并赋值给该位置前一个节点
  2. 释放该位置空间
    代码：
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead&&*pphead);//当pphead为NULL，说明没有节点，防止free释放NULL
	assert(pos);
	if(pos==*pphead)//只有一个节点
	{
		SLTPopFront(pphead);
	}
	else//两个及两个以上
	{
		SLTNode* prv = *pphead;
		while (prv->next != pos)
		{
			prv = prv->next;
		}
		prv->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

删除pos之后的结点

思路：

  1. 找到pos的下下一个节点地址赋值给pos
  2. 释放pos下一个节点
    代码：
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	SLTNode* div = pos->next;
	pos->next = div->next;//div->next等价于pos->next->next
	free(div);
	div = NULL;
}

销毁链表

思路：

  1. 将plist(*pphead)重新赋值为NULL
  2. 利用free释放后续节点
void SListDestroy(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* div = pcur->next;
		free(pcur);
		pcur = div;
	}
	*pphead = NULL;
}

单链表测试

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
void test()
{
	SLTNode* plist = NULL;
	//尾插1，2，3，4
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	//结果：1->2->3->4->NULL
	SLTPrint(plist);
	//头插
	SLTPushFront(&plist,0);
	//结果：0->1->2->3->4->NULL
	SLTPrint(plist);
	//尾删
	SLTPopBack(&plist);
	//结果：0->1->2->3->NULL
	SLTPrint(plist);
	//头删
	SLTPopFront(&plist);
	//结果：1->2->3->NULL
	SLTPrint(plist);
	//查找数据
	SLTNode* div=SLTFind(plist, 3);
	if (div)
	{
		printf("YES\n");
	}
	else
	{
		printf("NO!\n");
	}
	//在指定位置前插入
	SLTInsert(&plist,div,11);
	//结果：1->2->->11->3->NULL
	SLTPrint(plist);
	//在指定位置后插入
	SLTInsertAfter(div,12);
	//结果：1->2->->11->3->12->NULL
	SLTPrint(plist);
	//删除指定位置
	SLTErase(&plist, div);
	//结果：1->2->->11->12->NULL
	SLTPrint(plist);

	SListDestroy(&plist);
	SLTPrint(plist);

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

在这里插入图片描述
源码地址如下
https://gitee.com/xiao-li-learning-c-language/c-language-exercisehomework/commit/4556d2aa9e0f2506be4ae0f2e52b430650f7b2ec

-------------------------------------------------分隔符
单链表的基本结构与性质就介绍完了，出了我列举的几个函数外还有其他功能的函数，有兴趣的可以自行尝试，原理与上述函数差不多。
有错请在评论区指正，谢谢。

标签：pphead,单链,SLTNode,NULL,pos,next,数据结构,节点
From： https://blog.csdn.net/qq_71391318/article/details/142435728

相关文章

  • 基础数据结构之链表
    链表1)概述定义在计算机科学中，链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续Incomputerscience,alinkedlistisalinearcollectionofdataelementswhoseorderisnotgivenbytheirphysicalplacementinmemory.Instead,eachelem......
  • C语言结构体、指针和常见数据结构
    在学习C语言时，结构体、指针和常见的数据结构如链表、栈、队列、二叉树等，是绕不开的重点。本篇博客用通俗易懂的方式，介绍这些概念，结合简单的代码示例，带你逐步掌握这些基础知识。1.结构体和指针我们先来看一眼结构体和指针,不懂这些的话,下面的代码肯定看不懂,没学过......
  • 数据结构-线性表的单链式存储结构图解及C语言实现
    概念链式存储：结点在存储器中的位置是任意的，即逻辑相邻的数据元素在物理上不一定相邻链式存储结构也称非顺序映像或链式映像图解链式存储结构中结点一般有两个部分组成，即数据域(data)和指针域，数据域是用于存放数据的，指针域是用来指向下一结点的地址的，其中头节点指向该链表......
  • 【数据结构和算法实践-排序-归并排序】
    数据结构和算法实践-排序-归并排序题目MyThought代码示例JAVA-8题目排序MyThought然后再进行递归，递归要注意两个方面：一、自我调用二、终止条件：即函数边界注意点：树、递归*代码示例JAVA-8publicclassMergeSort{publicstaticvoidmergeSor......
  • 数据结构线性表两种方式分享
    第一种方式为老师说的数组+结构体（课本上），我用的是c++，其实与c没什么不同（区别：cin是scanf，cout是print，new是malloc（）函数），我用的全局变量，所以不用传参。代码1：点击查看代码#include<iostream>#include<cstring>usingnamespacestd;constintN=1e4+5;structss{ charname[......
  • 算法与数据结构学习路线图
    基础阶段编程语言基础：选择一门编程语言作为学习算法与数据结构的工具，如Python、Java、C++等，掌握其基本语法、数据类型、控制结构、函数等。这是后续学习的基础。学习时间：建议花费1-2个月左右打牢基础。学习网站及资源：菜鸟教程：网址为https://www.runoob.com/，提供各种编程......
  • 数据结构 ——— 常见的时间复杂度计算例题（最终篇）
    目录前言例题1：例题2（例题1的延申）：例题3：前言在前两章分析了不少常见的时间复杂度计算例题，有固定执行N次的，也有要分情况看待的数据结构———常见的时间复杂度计算例题（上篇）-CSDN博客数据结构———常见的时间复杂度计算例题（中篇）-CSDN博客接下来要分析的是递归算法的......
  • 数据结构与算法——Java实现 12.习题——合并有序链表
    目录21.合并两个有序链表方法1递归思路方法2迭代思路 完整代码结点类方法 人各有所感，角度不同又怎能感同身受                                                ——24.9.2321.合并两个有序链表将两个......
  • 数据结构 - 概述及其术语
    经过上一章节《数据结构与算法之间有何关系？》的阐述，相信大家对数据结构多少有了点了解，今天我们将进入数据结构的正式学习中。在计算机科学中，数据结构是一种数据管理、组织和存储的格式。它是相互之间存在一种或多种特定关系的数据元素的集合。在计算机中一个静态数据是没有灵魂......
  • 树上数据结构问题
    天天爱跑步假设现在又一棵树如果一个人要从\(3\)跑到\(5\),那么如果在\(2\)点的观察员要满足\(w[2]=dep[2]-dep[3]\),如果在点\(4\)的观察员要满足\(w[4]=dep[fa[lca]]-dep[3]+dep[lca]-dep[4]\),简单来说就是如果处于\(i\)点的观察员可以观察到,那么要......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99