链表的介绍与单链表的实现

ops/2024/11/25 10:24:56/

1.链表的介绍

链表分为单链表与双链表。链表和顺序表一样，均属于顺序表，因此链表的逻辑结构是线性的。链表在内存中的存储方式是不一定连续的（因此链表的物理结构不一定是线性的），也不一定是按照顺序存储。
在这里插入图片描述

2、节点的介绍

a.链表是由一个一个的节点连接组成的。每一个节点存储一个数据和指向下一个节点的指针。

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

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

d.结点的空间⼀般是从堆上申请的。从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续。

3.创建单链表

//创建单链表(结点)的结构
typedef struct SListNode
{DataType data;//结点中存储一个DataType类型的数据struct SListNode* next;//再存储一个指向下一个结点的指针
}SLNode;void CreateSList()//创建一个单链表(Create:创建)
{//创建了4个结点，并将4个结点的地址分别给了node1、node2、node3、node4SLNode* node1 = (SLNode*)malloc(sizeof(SLNode));node1->data = 1;SLNode* node2 = (SLNode*)malloc(sizeof(SLNode));node2->data = 2;SLNode* node3 = (SLNode*)malloc(sizeof(SLNode));node3->data = 3;SLNode* node4 = (SLNode*)malloc(sizeof(SLNode));node4->data = 4;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;}

用这种方式创建单链表，需要手动创建一个又一个的结点，效率太低了。下面给出效率高的方式。

4.单链表的实现

4.1实现的具体框架

需要创建SList.c、SList.h、SListTest.c三个文件。

1.SList.h文件相当于目录的功能，告诉我们这个文件中提供了哪些函数（即存放函数的声明）
2.SList.c文件是用来具体实现SList.h文件中的每个函数的功能
3.等SList.c、SList.h这两个文件写好之后，在SListTest.c文件中测试单链表的增删查改各项功能。
a.SList.h文件
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int DataType;
//定义单链表(结点)的结构
typedef struct SListNode
{DataType data;//存储一个DataType类型的数据struct SListNode* next;//存储下一个结点的地址
}SLNode;//打印单链表的数据
void SLPrint(SLNode* plist);//传首结点的地址//插入结点前要申请新结点的空间,并返回新结点的地址
SLNode* SLbuyNode(DataType x);//向单链表头部插入结点
void SLpushFront(SLNode** pplist, DataType x);//两个p表示二级指针
//若单链表为空表，则头结点的地址为NULL，插入新结点后，头结点的地址将会发生变化
//因此要传指向头结点的指针的地址(采用传址调用)//向单链表尾部插入结点
void SLpushBack(SLNode** pplist, DataType x);//两个p表示二级指针
//若单链表为空表，则头结点的地址为NULL，插入新结点后，头结点的地址将会发生变化
//因此要传指向头结点的指针的地址(采用传址调用)//删除头结点
void SLpopFront(SLNode** pplist);//两个p表示二级指针
//若单链表中只有一个结点，删除头结点后，头结点的地址就变成了NULL
//因此要传指向头结点的指针的地址//删除尾结点
void SLpopBack(SLNode** pplist);//两个p表示二级指针
//若单链表中只有一个结点，则删除尾结点后，头结点的地址就变成了NULL
//因此要传指向头结点的指针的地址//查找单链表中的数据
SLNode* SLFind(SLNode* phead, DataType x);//查找数据x的过程中，不会改变头结点的地址
//因此传头结点的地址就行(传值调用)//在指定结点(pos指向的结点)之前插入结点
//会影响pos指向的结点的前一个结点
void SLInsert(SLNode** pphead, SLNode* pos, DataType x);
//若在头结点之前插入结点，则头结点的地址将会发生变化
//因此要传指向头结点的指针的地址//在指定结点(pos指向的结点)之后插入结点
//会影响pos指向的结点
void SLInsertAfter(SLNode* pos, DataType x);
//通过pos就能找到pos指向的下一个结点，因此不需要头结点的地址//删除指定的结点(pos指向的结点)
//会影响pos指向的结点与pos指向的结点的前一个结点
void SLErase(SLNode** pphead, SLNode* pos);
//若删除的是头结点，则头结点的地址会方式变化，因此要传指向头结点的指针的地址(传址调用)//删除指定的结点(pos指向的结点)的后一个结点
//会影响pos指向的结点与pos指向的结点的后一个结点
void SLEraseAfter(SLNode* pos);
//通过pos就能找到pos指向的结点的下一个结点，因此不需要传头结点的地址//单链表的销毁
void SListDestroy(SLNode** pphead);
//头结点的地址会方式变化，因此要传指向头结点的指针的地址(传址调用)
b.SList.c文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
//打印单链表的数据
void SLPrint(SLNode* plist)//传首结点的地址
{while (plist){printf("%d->", plist->data);plist = plist->next;}printf("NULL\n");
}//插入结点前要申请新结点的空间,并返回新结点的地址
SLNode* SLbuyNode(DataType x)
{SLNode* node = (SLNode*)malloc(sizeof(SLNode));//检查新结点的空间是否申请成功assert(node);node->data = x;node->next = NULL;return node;
}//向单链表头部插入结点
void SLpushFront(SLNode** pplist, DataType x)//两个p表示二级指针
{//*pplist表示指向头结点的指针assert(pplist);//插入结点前要申请新结点的空间SLNode* NewNode = SLbuyNode(x);//判断单链表是否为空表(若指向头结点的指针为空指针，单链表就是空表)if (*pplist == NULL){//若单链表是空表，则新申请的结点就是头结点*pplist = NewNode;}else{//若单链表不是空表，则将新结点的next指针指向头结点，再将指向头结点的指针的值进行修改NewNode->next = *pplist;*pplist = NewNode;}
}//向单链表尾部插入结点
void SLpushBack(SLNode** pplist, DataType x)//两个p表示二级指针
{assert(pplist);//插入结点前要申请新结点的空间SLNode* NewNode = SLbuyNode(x);//判断单链表是否为空(若指向头结点的指针为空指针，则单链表为空表)if (*pplist == NULL){//若单链表为空表，新申请的结点就是尾结点(同时也是头结点)*pplist = NewNode;}else{//若单链表为空表，则先要找尾结点(尾结点的特征:它的next指针为空指针)，然后将尾结点的next指针指向新结点SLNode* start = *pplist;//找尾结点时，不能修改指向头结点的指针，否则就会找不到头结点了while (start->next){start = start->next;//找到尾结点之前，start指向下一个结点}start->next = NewNode;}
}//删除头结点
void SLpopFront(SLNode** pplist)//两个p表示二级指针
{//若单链表为空表，则不能删除结点(*pplist!=NULL)assert(*pplist && pplist);if ((*pplist)->next == NULL){//若单链表中只有一个结点free(*pplist);*pplist = NULL;}else{//若单链表中不止一个结点//将指向头结点的指针指向下一个结点，再释放头结点的空间SLNode* start = *pplist;*pplist = (*pplist)->next;free(start);//头结点的空间被释放后，start就变成了野指针start = NULL;}}//删除尾结点
void SLpopBack(SLNode** pplist)//两个p表示二级指针
{//若单链表为空表(*pplist!=NULL)，则不能删除结点assert(*pplist && pplist);if ((*pplist)->next == NULL){//若单链表中只有一个结点free(*pplist);*pplist = NULL;}else{//若单链表中不止一个结点//给尾结点的前一个结点的next指针赋值NULL，再释放尾结点的空间SLNode* end = *pplist;//end用于找尾结点。找尾结点的前一个结点时，不能修改指向头结点的指针，否则就找不到头结点了SLNode* prev = *pplist;//找尾结点的前一个结点while (end->next){prev = end;end = end->next;//end指向下一个结点}free(end);end = NULL;prev->next = NULL;}}//查找单链表中的数据
SLNode* SLFind(SLNode* phead, DataType x)
{//空链表无法查找数据assert(phead);SLNode* pcur = phead;//查找数据x的过程中，不希望指向头结点的指针的值发生变化，否则就找不到头结点了while (pcur)//从头结点往后遍历{if (pcur->data == x){return pcur;}pcur = pcur->next;}//如果单链表中没有x，就返回NULLreturn NULL;
}//在指定结点(pos指向的结点)之前插入新结点
void SLInsert(SLNode** pphead, SLNode* pos, DataType x)
{//若pphead==NULL，就找不到头结点了//若单链表为空表(*pphead=NULL),则单链表中不存在指定的结点//每个结点都有地址，若pos==NULL，则表示pos指向的结点不存在assert(pphead && *pphead && pos);/*插入思路:在指定结点(pos指向的结点)前插入新结点，则会影响pos指向的结点的前一个结点由于头结点没有前一个结点，因此要判断pos指向的结点是不是头结点*/if (pos == *pphead)//若pos指向的结点是头结点{SLpushFront(pphead, x);//这个函数内部会申请新结点的空间}else//若pos指向的结点不是头结点{//插入结点前要申请新结点的空间SLNode* NewNode = SLbuyNode(x);SLNode* pcur = *pphead;//pcur用于找pos指向的结点的前一个结点//p是point(指向)的缩写   cur是current(当前位置)的缩写while (pcur->next != pos){pcur = pcur->next;}pcur->next = NewNode;NewNode->next = pos;}
}//在指定结点(pos指向的结点)之后插入新结点
void SLInsertAfter(SLNode* pos, DataType x)
{//每个结点都有地址，若pos==NULL，则表示pos指向的结点不存在assert(pos);/*插入思路:在指定结点(pos指向的结点)之后插入新结点,会影响pos指向的结点*///插入结点前要申请新结点的空间SLNode* NewNode = SLbuyNode(x);/*pos->next = NewNode;NewNode->next = pos->next;这种写法是错误的*/NewNode->next = pos->next;pos->next = NewNode;
}//删除指定的结点(pos指向的结点)
void SLErase(SLNode** pphead, SLNode* pos)
{//若pphead==NULL,则找不到头结点//若*pphead==NULL，则单链表为空表，无法删除结点//每个结点都有地址，若pos==NULL，则表示pos指向的结点不存在assert(pphead && *pphead && pos);/*删除思路:删除指定的结点(pos指向的结点),会影响pos指向的结点与pos指向的结点的前一个结点由于头结点没有前一个结点，因此要判断pos指向的结点是不是头结点*/if (pos == *pphead)//若pos指向的结点是头结点{SLNode* pcur = *pphead;*pphead = (*pphead)->next;free(pcur);pcur = NULL;}else//若pos指向的结点不是头结点{//先找pos指向的结点的前一个结点//找pos指向的结点的前一个结点时，不能改变指向头结点的指针的值，否则就找不到头结点了SLNode* pcur = *pphead;//pcur用于找pos指向的结点的前一个结点while (pcur->next != pos){pcur = pcur->next;}pcur->next = pos->next;free(pos);pos = NULL;}}//删除指定的结点(pos指向的结点)的后一个结点
//会影响pos指向的结点与pos指向的结点的后一个结点
void SLEraseAfter(SLNode* pos)
{//若pos==NULL,则表示pos指向的结点不存在//若(pos->next)==NULL，则表示pos指向的结点的下一个结点不存在assert(pos && pos->next);SLNode* temp = pos->next;pos->next = pos->next->next;free(temp);temp = NULL;
}//单链表的销毁
void SListDestroy(SLNode** pphead)
{//若pphead==NULL,则找不到头结点//若*pphead==NULL,则单链表是空表，不需要销毁assert(pphead && *pphead);SLNode* pcur = *pphead;while (pcur){//逐个释放pucr指向的结点的空间SLNode* next = pcur->next;free(pcur);pcur = next;}*pphead =NULL;
}
c.SListTest.c文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void test()
{//创建一个空的单链表(指向头结点的指针为空指针)SLNode* phead = NULL;/*测试插入头结点SLpushFront(&phead, 3);SLpushFront(&phead, 2);SLpushFront(&phead, 1);SLPrint(phead);SLpopFront(&phead);SLPrint(phead);SLpopFront(&phead);SLPrint(phead);SLpopFront(&phead);SLPrint(phead);*//*测试插入尾结点SLpushBack(&phead, 3);SLpushBack(&phead, 2);SLpushBack(&phead, 1);SLPrint(phead);SLpopBack(&phead);SLPrint(phead);SLpopBack(&phead);SLPrint(phead);SLpopBack(&phead);SLPrint(phead);*//*测试单链表的销毁SLpushFront(&phead, 3);SLpushFront(&phead, 2);SLpushFront(&phead, 1);SLPrint(phead);//1->2->3->NULLSListDestroy(&phead);SLPrint(phead);*/
}
int main()
{test();return 0;
}

http://www.ppmy.cn/ops/136537.html

相关文章

ESP32移植Openharmony外设篇(6)光敏电阻ADC读取

ESP32移植Openharmony外设篇(6)光敏电阻ADC读取

光照传感器 模块简介 产品描述 光敏电阻&#xff08;photoresistor orlight-dependent resistor&#xff0c;后者缩写为LDR&#xff09;是一种基于内光电效应的半导体元件&#xff0c;它的阻值依赖于入射光强的变化 。入射光强增加&#xff0c;光敏电阻的阻值减小&#xff0…
阅读更多...
FIFO和LRU算法实现操作系统中主存管理

FIFO和LRU算法实现操作系统中主存管理

FIFO&#xff0c;用数组实现 1和2都是使用nextReplace实现新页面位置的更新 1、不精确时间&#xff1a;用ctime输出运行时间都是0.00秒 #include <iostream> #include <iomanip> #include<ctime>//用于计算时间 using namespace std;// 页访问顺序 int pa…
阅读更多...
linux下i2c开发与框架源码分析

linux下i2c开发与框架源码分析

目录 1 概述 2 I2c子系统框架 3 I2C的使用流程 3.1 在驱动里使用 3.2 在应用层使用 3.3 I2ctool的使用 4 为硬件i2c注册一个适配器 5 i2c子系统源码流程分析 5.1 i2c device与driver绑定过程 5.1.1 Driver的注册与处理 5.1.2 Client device的生成 5.2 I2c的发送与接…
阅读更多...
【C++】类（三）：类的其它特性

【C++】类（三）：类的其它特性

7.3 类的其它特性 本节将继续介绍之前章节当中 Sales_data 没有体现出来的类的特性&#xff0c;包括&#xff1a;类型成员、类的成员的类内初始值、可变数据成员、内联成员函数、从成员函数返回*this、如何定义并使用类类型及友元类等。 7.3.1 类成员再探 这部分定义了一对相…
阅读更多...
机器学习入门-Scikit-learn

机器学习入门-Scikit-learn

目录 一.Sklearn基本介绍 二.以鸢尾花数据集为例&#xff0c;理解基础运用 1.导入包 2.加载数据集 3.数据预处理 4.数据集拆分 5.模型训练 6.模型评估 7.模型保存和加载 三.碎碎念 一.Sklearn基本介绍 scikit-learn是一个开源的Python机器学习库&#xff0c;提供了大…
阅读更多...
无Linux管理员权限，照样可以安装CUDA

无Linux管理员权限，照样可以安装CUDA

以下演示内容使用CUDA版本为 CUDA11.7 1、官网 官网：CUDA官网下载地址 这里会列出所有的CUDA版本，选择需要的版本即可。 2、查看系统信息 这里分享三个命令，可以查看Linux系统的配置信息，方便下一步下载合适的CUDA版本。 可以根据这些命令输出的系统配置信息选择相应的…
阅读更多...
阿里云IIS虚拟主机部署ssl证书

阿里云IIS虚拟主机部署ssl证书

宝塔配置SSL证书用起来是很方便的&#xff0c;只需要在站点里就可以配置好&#xff0c;但是云虚拟主机在管理的时候是没有这个权限的&#xff0c;只提供了简单的域名管理等信息。 此处记录下阿里云&#xff08;原万网&#xff09;的IIS虚拟主机如何配置部署SSL证书。 进入虚拟…
阅读更多...
IntelliJ IDEA常用快捷键

IntelliJ IDEA常用快捷键

文章目录 环境快捷键外观编辑移动光标提示查找Live Templates列操作调试运行 环境 Ubuntu 24.04.1IntelliJ IDEA 2024.1.6 快捷键 外观 Alt 1&#xff1a;打开/关闭“项目”窗口&#xff08;即左边的导航窗口&#xff09; Alt 4&#xff1a;打开/关闭“运行”窗口 Alt …
阅读更多...
最新文章

Copyright @ 2022~2023