数据结构篇2—《单链表(不带头单向不循环链表)》

news/2024/10/19 3:31:19/

在这里插入图片描述

文章目录

  • 🚩前言
    • 1、单链表的内涵
      • (1) 逻辑结构
      • (2) 物理结构
    • 2、链表的分类
    • 3、单链表的具体实现
      • (1) 框架结构
      • (2) SingleLinkList.h头文件的实现
      • (3)SingleLinkList.c源文件的实现
        • ①SLTPushBack()尾插函数
        • ②SLTPushFront()头插函数
        • ③SLTPopBack()尾删函数
        • ④SLTPopFront()头删函数
        • ⑤SLTInsert()和SLTInsertAfter()指定位置之前和之后插入数据函数
        • ⑥SLTErase()和SLTDestroy()删除和销毁函数
    • 4、完整代码
    • 5、效果展示

🚩前言

在数据结构中主要的就是对数据的增删查改操作，在前面讲的顺序表就是其中一种结构，顺序表前身的数组（静态和动态）。而该结构是叫单链表，从逻辑结构上看是连续的，而在物理结构上是不连续存储的。下面就来对单链表的具体实现：

1、单链表的内涵

(1) 逻辑结构

什么叫作逻辑结构上是连续的，而物理结构上是不连续的。首先，在一个连续的空间当中就是连续存储，反之就不是，但是从我们思维结构来看可以当做是连续的，下面是单链表的逻辑结构：
在这里插入图片描述

(2) 物理结构

物理结构上就得从计算机内存中来看，就是在一个内存块中，每个节点所开辟的空间位置不是紧挨着的，存在一定距离，如下简图：
在这里插入图片描述

2、链表的分类

链表的种类比起顺序表就多了，顺序表就是静态和动态。而链表主要从带不带头、单向还是双向、循不循环三个点来分类，如下：
在这里插入图片描述

比如 ：不带头单向不循环->单链表
不带头双向循环链表
带头单向循环链表等等。最常见的就是单链表和带头双向循环链表。

3、单链表的具体实现

(1) 框架结构

在这里插入图片描述

(2) SingleLinkList.h头文件的实现

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//创建单链表结构体
typedef int DataType;
typedef struct SingLinkListNode
{DataType data;struct SingLinkListNode *next;
}SLTNode;//打印函数
void PrintLinkList(SLTNode *phead);//尾插
void SLTPushBack(SLTNode **pphead,DataType data);//头插
void SLTPushFront(SLTNode **pphead,DataType data);//尾删
void SLTPopBack(SLTNode **pphead);//头删
void SLTPopFront(SLTNode **pphead);//查找
SLTNode* SLTFind(SLTNode *phead,DataType data);//指定位置之前插入数据
void SLTInsert(SLTNode **pphead,SLTNode *pos,DataType data);//指定位置之后插入数据
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, DataType data);//删除节点函数
void SLTErase(SLTNode** pphead,SLTNode* pos);//销毁链表函数
void SLTDestroy(SLTNode** pphead);

(3)SingleLinkList.c源文件的实现

①SLTPushBack()尾插函数
SLTNode* BuyNode(DataType x)
{SLTNode *NewNode = (SLTNode*)malloc(sizeof(SLTNode));if (NewNode == NULL){perror("BuyNode:: malloc fail!");exit(1);}else{NewNode->data = x;NewNode->next = NULL;}return NewNode;
}void SLTPushBack(SLTNode **pphead, DataType data)
{assert(pphead);SLTNode *NewNode=BuyNode(data);if ((*pphead) == NULL){*pphead = NewNode;}else{//找尾SLTNode *ptail = *pphead;while (ptail->next!=NULL){ptail = ptail->next;}ptail->next = NewNode;}
}

图解：尾插数据得申请新节点BuyNode();
在这里插入图片描述

②SLTPushFront()头插函数
void SLTPushFront(SLTNode **pphead, DataType data)
{assert(pphead);SLTNode *NewNode = BuyNode(data);if (*pphead == NULL){*pphead = NewNode;}else{NewNode->next = *pphead;*pphead = NewNode;}
}

图解：
在这里插入图片描述

③SLTPopBack()尾删函数
void SLTPopBack(SLTNode **pphead)
{assert(pphead&&(*pphead)->data);SLTNode* prev = NULL;SLTNode* ptail = *pphead;//当只有一个节点的时候if ((*pphead)->next==NULL){free(*pphead);*pphead = NULL;}else{//找尾节点while ((ptail->next)!=NULL){prev = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;prev->next = NULL;}
}

图解：
在这里插入图片描述

④SLTPopFront()头删函数
void SLTPopFront(SLTNode **pphead)
{assert(pphead && *pphead);SLTNode *pcur = (*pphead)->next;free(*pphead);*pphead = pcur;
}

图解：头删很简单。
在这里插入图片描述

⑤SLTInsert()和SLTInsertAfter()指定位置之前和之后插入数据函数
void SLTInsert(SLTNode** pphead, SLTNode* pos, DataType data)
{assert(pphead && pos);SLTNode* NewNode = BuyNode(data);SLTNode* prev = *pphead;//当插入的数据节点是头节点时就调用头插if (pos == *pphead){SLTPushFront(pphead,data);}else{while (prev->next != pos){prev = prev->next;}prev->next = NewNode;NewNode->next = pos;}
}void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, DataType data)
{assert(pphead && pos);//SLTNode* pcur = *pphead;SLTNode* NewNode = BuyNode(data);//pcur = pos->next;//pos->next = NewNode;//NewNode->next = pcur;NewNode->next = pos->next;pos->next = NewNode;
}

图解：
在这里插入图片描述

⑥SLTErase()和SLTDestroy()删除和销毁函数
//删除
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && pos);SLTNode* prev = *pphead;if (pos == *pphead){//头删SLTPopFront(pphead);}else{while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}
//销毁
void SLTDestroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

在销毁的时候得注意，因为节点是一个一个创建的，所以也得一个一个的销毁。

4、完整代码

1、头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//创建单链表结构体
typedef int DataType;
typedef struct SingLinkListNode
{DataType data;struct SingLinkListNode *next;
}SLTNode;//打印函数
void PrintLinkList(SLTNode *phead);//尾插
void SLTPushBack(SLTNode **pphead,DataType data);//头插
void SLTPushFront(SLTNode **pphead,DataType data);//尾删
void SLTPopBack(SLTNode **pphead);//头删
void SLTPopFront(SLTNode **pphead);//查找
SLTNode* SLTFind(SLTNode *phead,DataType data);//指定位置之前插入数据
void SLTInsert(SLTNode **pphead,SLTNode *pos,DataType data);//指定位置之后插入数据
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, DataType data);//删除节点函数
void SLTErase(SLTNode** pphead,SLTNode* pos);//销毁链表函数
void SLTDestroy(SLTNode** pphead);

2、源文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"SingleLinkList.h"void PrintLinkList(SLTNode *phead)
{// assert(phead&&phead->next);SLTNode *pcur = phead;while (pcur != NULL){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL");
}SLTNode* BuyNode(DataType x)
{SLTNode *NewNode = (SLTNode*)malloc(sizeof(SLTNode));if (NewNode == NULL){perror("BuyNode:: malloc fail!");exit(1);}else{NewNode->data = x;NewNode->next = NULL;}return NewNode;
}void SLTPushBack(SLTNode **pphead, DataType data)
{assert(pphead);SLTNode *NewNode=BuyNode(data);if ((*pphead) == NULL){*pphead = NewNode;}else{//找尾SLTNode *ptail = *pphead;while (ptail->next!=NULL){ptail = ptail->next;}ptail->next = NewNode;}
}void SLTPushFront(SLTNode **pphead, DataType data)
{assert(pphead);SLTNode *NewNode = BuyNode(data);if (*pphead == NULL){*pphead = NewNode;}else{NewNode->next = *pphead;*pphead = NewNode;}
}void SLTPopBack(SLTNode **pphead)
{assert(pphead&&(*pphead)->data);SLTNode* prev = NULL;SLTNode* ptail = *pphead;//当只有一个节点的时候if ((*pphead)->next==NULL){free(*pphead);*pphead = NULL;}else{//找尾节点while ((ptail->next)!=NULL){prev = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;prev->next = NULL;}
}void SLTPopFront(SLTNode **pphead)
{assert(pphead && *pphead);SLTNode *pcur = (*pphead)->next;free(*pphead);*pphead = pcur;
}SLTNode* SLTFind(SLTNode *phead, DataType data)
{assert(phead);SLTNode *pcur = phead;while (pcur){if (pcur->data == data){return pcur;}pcur = pcur->next;}return NULL;
}void SLTInsert(SLTNode** pphead, SLTNode* pos, DataType data)
{assert(pphead && pos);SLTNode* NewNode = BuyNode(data);SLTNode* prev = *pphead;//当插入的数据节点是头节点时就调用头插if (pos == *pphead){SLTPushFront(pphead,data);}else{while (prev->next != pos){prev = prev->next;}prev->next = NewNode;NewNode->next = pos;}
}void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, DataType data)
{assert(pphead && pos);//SLTNode* pcur = *pphead;SLTNode* NewNode = BuyNode(data);//pcur = pos->next;//pos->next = NewNode;//NewNode->next = pcur;NewNode->next = pos->next;pos->next = NewNode;
}void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && pos);SLTNode* prev = *pphead;if (pos == *pphead){//头删SLTPopFront(pphead);}else{while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}void SLTDestroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

3、测试代码文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"SingleLinkList.h"void test()
{SLTNode* sl=NULL;//尾插函数测试SLTPushBack(&sl, 1);SLTPushBack(&sl, 2);SLTPushBack(&sl, 3);SLTPushBack(&sl, 4);//打印PrintLinkList(sl);printf("\n");//头插函数测试SLTPushFront(&sl, 10);SLTPushFront(&sl, 20);SLTPushFront(&sl, 30);//打印PrintLinkList(sl);printf("\n");//尾删函数测试SLTPopBack(&sl);SLTPopBack(&sl);//打印PrintLinkList(sl);printf("\n");//头删函数测试SLTPopFront(&sl);SLTPopFront(&sl);//打印PrintLinkList(sl);//查找函数测试int number = 0;printf("\n请输入要查找的数：");scanf("%d",&number);if (SLTFind(sl, number) == NULL){printf("没找到！\n");}else{printf("找到了！%p\n", SLTFind(sl, number));}//在一节点之前插入数据函数测试int number1 = 0;int number2 = 0;printf("请输入要在那个节点之前插入数据：");scanf("%d",&number1);printf("请输入要插入的数据：");scanf("%d",&number2);SLTInsert(&sl,SLTFind(sl,number1),number2);//打印PrintLinkList(sl);printf("\n");//在一节点之后插入数据函数测试int number3 = 0;int number4 = 0;printf("请输入要在那个节点之后插入数据：");scanf("%d", &number3);printf("请输入要插入的数据：");scanf("%d", &number4);SLTInsertAfter(&sl, SLTFind(sl, number3), number4);//打印PrintLinkList(sl);printf("\n");//删除节点函数测试int number5 = 0;printf("请输入要删除的节点的数据：");scanf("%d",&number5);SLTErase(&sl,SLTFind(sl,number5));PrintLinkList(sl);printf("\n");//销毁函数测试SLTDestroy(&sl);
}int main()
{test();return 0;
}

5、效果展示

在这里插入图片描述
在这里插入图片描述


http://www.ppmy.cn/news/1448256.html

相关文章

【论文阅读】互连网络的负载平衡路由算法 (GAL, Globally Adaptive Load-balancing 全局自适应负载平衡)

【论文阅读】互连网络的负载平衡路由算法 (GAL, Globally Adaptive Load-balancing 全局自适应负载平衡)

Globally Adaptive Load-balancing 全局自适应负载平衡 GAL: Globally Adaptive Load-balanced routing 全局自适应负载平衡路由 1. GAL on a ring2. GAL on higher dimensional torus3. 实验性能4. 算法稳定性 Stability总结 References Globally Adaptive Load-balancing 全…
阅读更多...
Mac M2 本地下载 Xinference

Mac M2 本地下载 Xinference

想要在Mac M2 上部署一个本地的模型。看到了Xinference 这个工具 一、Xorbits Inference 是什么 Xorbits Inference&#xff08;Xinference&#xff09;是一个性能强大且功能全面的分布式推理框架。可用于大语言模型&#xff08;LLM&#xff09;&#xff0c;语音识别模型&…
阅读更多...
C语言嵌入Lua解释器的方法

C语言嵌入Lua解释器的方法

Lua语言是一个轻量的脚本语言&#xff0c;可以用很少的资源运行其解释器 C语言是一个很常用的语言&#xff0c;广泛用于嵌入式等底层场景 这两个语言结合&#xff0c;可以应用于嵌入式等多个场景。比如&#xff0c;一些硬件公司会允许开发者使用Lua语言操作其硬件 Lua的安装…
阅读更多...
使用FPGA实现串-并型乘法器

使用FPGA实现串-并型乘法器

介绍 其实我们知道&#xff0c;用FPGA实现乘法器并不是一件很简单的事&#xff0c;而且在FPGA中也有乘法器的IP核可以直接调用&#xff0c;我这里完全就是为了熟悉一些FPGA的语法然后写了这样一个电路。 串-并型乘法器模块 从字面上看&#xff0c;串-并乘法器就是其中一个乘数…
阅读更多...
Java实现以图识图功能模块（简单案例）

Java实现以图识图功能模块（简单案例）

由于完整的以图识图系统代码较长且复杂&#xff0c;这里仅提供使用OpenCV进行特征提取和比较的简化版示例代码。 1. 引入OpenCV Java库 首先&#xff0c;你需要在项目中引入OpenCV的Java库。这通常涉及将OpenCV的jar包添加到项目的类路径中。 2. 提取图像特征 使用OpenCV的…
阅读更多...
【全网首发】2024五一数学建模ABC题保奖思路（后续会更新）

【全网首发】2024五一数学建模ABC题保奖思路（后续会更新）

一定要点击文末的卡片哦&#xff01; 1&#xff09;常见模型分类 机理分析类&#xff1a;来源于实际问题&#xff0c;需要了解一定的物理机理&#xff0c;转化为优化问题。 运筹优化类&#xff1a;旨在找到使某个目标函数取得最大或最小值的最优解,对于机理要求要求不高&…
阅读更多...
selinux 基础知识

selinux 基础知识

目录 概念 作用 SELinux与传统的权限区别 SELinux工作原理 名词解释 主体&#xff08;Subject&#xff09; 目标&#xff08;Object&#xff09; 策略&#xff08;Policy&#xff09; 安全上下文&#xff08;Security Context&#xff09; 文件安全上下文查看 先启用…
阅读更多...
ngrinder压测过程中遇到的坑

ngrinder压测过程中遇到的坑

问题1、执行压测脚本时&#xff0c;代理服务提示错误&#xff0c;如下 代理服务的错误日志&#xff1a; SLF4J: See http://www.slf4j.org/codes.html#multiple_bindings for an explanation. 2024-04-30 22:08:37,225 ERROR worker-bootstrap: Error running worker process o…
阅读更多...
最新文章

Copyright @ 2022~2023