数据结构之线性表（单链表的实现）

目录

一、单链表的原理

二、单链表的实现

1.单链表的定义

2.单链表的初始化

3.清空单链表

4.单链表是否为空

5.单链表的长度

6.获取指定位置 i 的元素

7.获取指定元素 e 的位置  

8.向链表中插入指定位置的元素

9.向链表中删除指定位置的元素

10.遍历链表中的元素

三、打印测试功能

1.测试

2.结果输出

3.总代码

一、单链表的原理

        本章节紧跟上一篇文章《顺序表的实现》来继续讲述线性表的一种：单链表。

        前面我们讲的线性表的顺序存储结构。它是有缺点的，最大的缺点就是插入和删除时需要移动大量元素，这显然就需要耗费时间。能不能想办法解决呢?

         要解决这个问题，我们就得考虑一下导致这个问题的原因。为什么当插入和删除时，就要移动大量元素，仔细分析后，发现原因就在于相邻两元素的存储位置也具有邻居关系。它们编号是1，2，3，…，n，它们在内存中的位置也是挨着的，中间没有空隙，当然就无法快速介入，而删除后，当中就会留出空隙，自然需要弥补。问题就出在这里。

        我们可以在第一个元素时，就知道第二个元素的位置(内存地址)，而找到它;在第二个元素时，再找到第三个元素的位置(内存地址)。这样所有的元素我们就都可以通过遍历而找到，而这就是单链表的特点，如下图所示。

         而链表的结构则如下图所示，第一个节点的指针由头节点所指，第二个节点的指针由第一个节点所指，以此类推。

二、单链表的实现

1.单链表的定义

        定义一些功能常量和单链表的结构。

        这里需要注意的是，我给链表起别名的是一个指针，后面我们在实现链表功能的时候，我们传递函数参数的时候要传递的是一个双指针（LinkList* L）。 这是因为链表的结构使然，因为链表存储的是其他链表的指针，它是一个地址，后面我们在进行链表的增加和删除的时候，会经常涉及到指针的变化。

        如果函数的参数是本身一级指针，那么在函数内部对指针的修改将不会反映到函数外部，因为函数接收到的是指针的一个副本。使用指针的指针作为参数，则可以确保在函数内部对指针的修改能够反映到原始的指针上。

typedef  struct  Node*  LinkList;

#include <iostream>#define MAX_SIZE 20
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int ElemType;typedef struct Node
{ElemType data;struct Node* next;
}Node;typedef struct Node* LinkList;
2.单链表的初始化

        链表的初始化主要是为头节点分配内存空间，使它的data 和 next 都指向为 NULL，方便我们后续的操作。

Status InitList(LinkList* L)
{*L = (LinkList)malloc(sizeof(Node));if (*L == NULL) return ERROR;(*L)->data = 0;(*L)->next = NULL;return OK;
}
3.清空单链表

        对链表进行清空操作，因为是用 malloc 进行分配的空间，对堆中的空间进行释放操作。

Status ClearList(LinkList* L)
{LinkList p, q;p = (*L)->next;while (p != NULL) {	q = p->next;free(p);p = q;}(*L)->next = NULL;return OK;
}
4.单链表是否为空

        判断头节点指向的元素是否为空。即 next 是否为 NULL。

Status isListEmpty(LinkList L)
{if (L->next  == NULL) return TRUE;return FALSE;
}
5.单链表的长度

        求链表的长度，定义一个变量，然后用while循环遍历链表。

int ListLength(LinkList L)
{int num{ 0 };LinkList temp = L->next;while (temp != NULL){temp = temp->next;num++;}return num;
}
6.获取指定位置 i 的元素

        定义一个变量，进行while操作，判断是否与指定位置 i 相同，获取其节点值。

Status GetElem(LinkList L, int i, ElemType* e)
{int num{ 1 };LinkList temp = L->next;while (temp != NULL && num < i){temp = temp->next;num++;}	if (temp == NULL || num > i) return ERROR;*e = temp->data;
}
7.获取指定元素 e 的位置  

        和上述功能类似，返回值为 int 位置。

int LocateElem(LinkList L, ElemType* e)
{int num{ 0 };LinkList temp = L->next;while (temp != NULL){num++;if (temp->data = *e){return num;}temp = temp->next;}return 0;
}
8.向链表中插入指定位置的元素

          此功能为链表的难点所在，需要根据图像理解实现，如下图所示。 

      

Status LinkInsert(LinkList* L, int i, ElemType e)
{int j;LinkList p, s;p = *L;j = 1;while (p != NULL && j < i){p = p->next;++j;}	if (!p || j > i) return ERROR;s = (LinkList)malloc(sizeof(Node));if (s == NULL) return ERROR;s->data = e;s->next = p->next;p->next = s;return OK;}
9.向链表中删除指定位置的元素

        和上功能类似，如图所示。

Status LinkDelete(LinkList* L, int i, ElemType* e)
{int j;LinkList p, s;j = 1;p = (*L);while (p != NULL && j < i){p = p->next;++j;}if (!p || j > i) return ERROR;s = p->next;p->next = s->next;*e = s->data;free(s);return OK;
}
10.遍历链表中的元素

        功能比较简单，通过不断遍历打印其节点的data值。

Status visit(ElemType e)
{printf("%d->", e);return OK;
}
Status ListTraverse(LinkList L)
{LinkList p = L->next;while (p != NULL){visit(p->data);p = p->next;} printf("\n");return OK;
}

三、打印测试功能

1.测试

        测试主要为测试以上的功能是否可以实现。

int TestSingleList()
{LinkList L;ElemType e;Status ret;int j, k;// 初始化ret = InitList(&L);printf("初始化长度：%d\n", ListLength(L));for(j = 1; j <= 5; j++){ret = LinkInsert(&L, 1, j);}printf("插入5个元素后：");ListTraverse(L);ret = isListEmpty(L);printf("是否为空，%d\n", ret);ret = ClearList(&L);printf("清空后的长度：%d\n", ListLength(L));printf("是否为空，%d\n", ret);for (j = 1; j <= 10; j++){ret = LinkInsert(&L, j, j);}printf("插入10个元素后：");ListTraverse(L);LinkInsert(&L, 3, 100);printf("在第2个节点后面增加元素100：");ListTraverse(L);LinkDelete(&L, 2, &e);printf("删除第二个节点,节点元素为%d :", e);ListTraverse(L);ClearList(&L);return 0;
}
2.结果输出

           结果输出如图所示：

3.总代码

        总代码如下：

#include <iostream>#define MAX_SIZE 20
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int ElemType;typedef struct Node
{ElemType data;struct Node* next;
}Node;typedef struct Node* LinkList;Status visit(ElemType e)
{printf("%d->", e);return OK;
}Status InitList(LinkList* L)
{*L = (LinkList)malloc(sizeof(Node));if (*L == NULL) return ERROR;(*L)->data = 0;(*L)->next = NULL;return OK;
}Status ClearList(LinkList* L)
{LinkList p, q;p = (*L)->next;while (p != NULL) {	q = p->next;free(p);p = q;}(*L)->next = NULL;return OK;
}Status isListEmpty(LinkList L)
{if (L->next  == NULL) return TRUE;return FALSE;
}int ListLength(LinkList L)
{int num{ 0 };LinkList temp = L->next;while (temp != NULL){temp = temp->next;num++;}return num;
}Status GetElem(LinkList L, int i, ElemType* e)
{int num{ 1 };LinkList temp = L->next;while (temp != NULL && num < i){temp = temp->next;num++;}	if (temp == NULL || num > i) return ERROR;*e = temp->data;
}int LocateElem(LinkList L, ElemType* e)
{int num{ 0 };LinkList temp = L->next;while (temp != NULL){num++;if (temp->data = *e){return num;}temp = temp->next;}return 0;
}Status LinkInsert(LinkList* L, int i, ElemType e)
{int j;LinkList p, s;p = *L;j = 1;while (p != NULL && j < i){p = p->next;++j;}	if (!p || j > i) return ERROR;s = (LinkList)malloc(sizeof(Node));if (s == NULL) return ERROR;s->data = e;s->next = p->next;p->next = s;return OK;}Status LinkDelete(LinkList* L, int i, ElemType* e)
{int j;LinkList p, s;j = 1;p = (*L);while (p != NULL && j < i){p = p->next;++j;}if (!p || j > i) return ERROR;s = p->next;p->next = s->next;*e = s->data;free(s);return OK;
}Status ListTraverse(LinkList L)
{LinkList p = L->next;while (p != NULL){visit(p->data);p = p->next;} printf("\n");return OK;
}Status CreateListHead(LinkList* L,int n)
{LinkList p;srand((unsigned)time(0));*L = (LinkList)malloc(sizeof(Node));if (*L == NULL) return ERROR;(*L)->next = NULL;for (int i = 0; i < n; i++){p = (LinkList)malloc(sizeof(Node));if (p == NULL) return ERROR;p->data = rand() % 100 + 1;p->next = (*L)->next;(*L)->next = p;}return OK;
}Status CreateListTail(LinkList* L,int n)
{LinkList p, r;srand((unsigned)time(0));*L = (LinkList)malloc(sizeof(Node));if (*L == NULL) return ERROR;(*L)->next = NULL;r = (*L);for (int i = 0; i < n; i++){p = (LinkList)malloc(sizeof(Node));if (p == NULL) return ERROR;p->data = rand() % 100 + 1;r->next = p;r = p;}return OK;
}int TestSingleList()
{LinkList L;ElemType e;Status ret;int j, k;// 初始化ret = InitList(&L);printf("初始化长度：%d\n", ListLength(L));for(j = 1; j <= 5; j++){ret = LinkInsert(&L, 1, j);}printf("插入5个元素后：");ListTraverse(L);ret = isListEmpty(L);printf("是否为空，%d\n", ret);ret = ClearList(&L);printf("清空后的长度：%d\n", ListLength(L));printf("是否为空，%d\n", ret);for (j = 1; j <= 10; j++){ret = LinkInsert(&L, j, j);}printf("插入10个元素后：");ListTraverse(L);LinkInsert(&L, 3, 100);printf("在第2个节点后面增加元素100：");ListTraverse(L);LinkDelete(&L, 2, &e);printf("删除第二个节点,节点元素为%d :", e);ListTraverse(L);ClearList(&L);return 0;
}int main()
{return TestSingleList();
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/396192.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

告别手动操作！KeyMouseGo实现自动化工作流

告别手动操作！KeyMouseGo实现自动化工作流

前言 在这个快节奏的时代&#xff0c;我们每天都在与电脑打交道&#xff0c;重复着那些繁琐而单调的操作&#xff1b;你是否曾想过&#xff0c;能让电脑自己完成这些任务&#xff0c;而你则悠闲地喝着咖啡&#xff0c;享受着生活&#xff1f;今天&#xff0c;就让我们一起揭开一…
阅读更多...
【sdk】- 对接阿里云抠图

【sdk】- 对接阿里云抠图

文档地址&#xff1a;https://help.aliyun.com/zh/viapi/use-cases/general-image-segmentation?spma2c4g.11186623.0.0.3814173cenldIs java对接阿里云的通用分割&#xff0c;将代码原封不动复制进来&#xff0c;执行结果失败&#xff0c;咨询阿里云的人员之后&#xff0c;由…
阅读更多...
优盘数据救援：应对文件与目录损坏的全方位指南

优盘数据救援：应对文件与目录损坏的全方位指南

一、问题剖析&#xff1a;优盘文件或目录损坏的困境 在数字化时代&#xff0c;优盘&#xff08;USB闪存驱动器&#xff09;作为便携、高效的数据存储工具&#xff0c;广泛应用于数据传输、备份与分享。然而&#xff0c;面对频繁的使用与不当操作&#xff0c;优盘中的文件或目录…
阅读更多...
FPGA常见型号

FPGA常见型号

FPGA&#xff08;现场可编程门阵列&#xff09;开发板种类繁多&#xff0c;涵盖了从入门级教育用途到高性能工业应用的广泛领域。以下是一些常见的 FPGA 开发板型号及其特点&#xff1a; 1. Xilinx&#xff08;赛灵思&#xff09;系列 Xilinx 是 FPGA 领域的领导者之一&#…
阅读更多...
Ubuntu22.04安装Docker教程

Ubuntu22.04安装Docker教程

简介 ​ Docker 是一个开源的平台&#xff0c;旨在简化应用开发、交付和运行的过程。通过使用容器技术&#xff0c;Docker 能够让开发人员将应用及其依赖环境一同打包&#xff0c;从而实现快速部署、一致的开发环境和优秀的可移植性。 系统版本 ​ 本文以Ubuntu 22.04.4 LTS…
阅读更多...
【探索Linux】P.46（高级IO —— 五种IO模型简介 | IO重要概念）

【探索Linux】P.46（高级IO —— 五种IO模型简介 | IO重要概念）

阅读导航 引言一、五种IO模型1. 阻塞IO&#xff08;1&#xff09;定义&#xff08;2&#xff09;特点 2. 非阻塞IO&#xff08;1&#xff09;定义&#xff08;2&#xff09;特点 3. IO多路复用&#xff08;1&#xff09;定义&#xff08;2&#xff09;特点 4. 信号驱动IO&#…
阅读更多...
深入探索：【人工智能】、【机器学习】与【深度学习】的全景视觉之旅

深入探索：【人工智能】、【机器学习】与【深度学习】的全景视觉之旅

目录 第一部分&#xff1a;人工智能、机器学习与深度学习概述 1.1 人工智能的概念与发展 代码示例&#xff1a;简单的AI决策系统 1.2 机器学习的定义与分类 代码示例&#xff1a;简单的线性回归模型 1.3 深度学习的基础与应用 代码示例&#xff1a;构建简单的神经网络 …
阅读更多...
【TwinCAT】TwinCAT3 PLC HMI在WIN10系统中的全屏显示及用户管理

【TwinCAT】TwinCAT3 PLC HMI在WIN10系统中的全屏显示及用户管理

在工业自动化领域，TwinCAT3 PLC HMI 是一款强大的可视化工具，它支持多种操作系统，并且能够满足不同控制器的需求。在本文中，我们将详细介绍如何在WIN10系统中进行全屏显示设置以及如何进行用户管理配置。 一、TwinCAT3 PLC HMI 全屏显示方法 1. 创建Visualization和配置Vi…
阅读更多...
Git开发流程

Git开发流程

Git开发流程规范如下&#xff1a; 详情参考&#xff1a;https://www.processon.com/view/link/5d0cf86ce4b0376de9c19e16
阅读更多...
【自动驾驶】ROS中自定义格式的服务通信，含命令行动态传参（c++）

【自动驾驶】ROS中自定义格式的服务通信，含命令行动态传参（c++）

目录 通信流程创建服务器端及客户端新建服务通讯文件修改service的xml及cmakelistCMakeLists.txt编辑 msg 相关配置编译消息相关头文件在cmakelist中包含头文件的路径在service包下编写service.cpp在client包下编写client.cpp测试运行查询服务的相关指令列出目前的所有服务&…
阅读更多...
【Vue3】组件通信之mitt

【Vue3】组件通信之mitt

【Vue3】组件通信之mitt 背景简介开发环境开发步骤及源码总结 背景 随着年龄的增长&#xff0c;很多曾经烂熟于心的技术原理已被岁月摩擦得愈发模糊起来&#xff0c;技术出身的人总是很难放下一些执念&#xff0c;遂将这些知识整理成文&#xff0c;以纪念曾经努力学习奋斗的日…
阅读更多...
什么是智能加密？超好用神器智能加密软件推荐

什么是智能加密？超好用神器智能加密软件推荐

信息安全已成为我们日常生活中不可忽视的一环。 随着网络攻击手段的不断升级和隐私泄露事件的频发&#xff0c;如何有效保护个人及企业的敏感数据成为了亟待解决的问题。 智能加密&#xff0c;作为信息安全领域的一项重要技术&#xff0c;正逐渐走进大众视野&#xff0c;以其高…
阅读更多...
【数据结构七夕专属版】单链表及单链表的实现【附源码和源码讲解】

【数据结构七夕专属版】单链表及单链表的实现【附源码和源码讲解】

本篇是博主在学习数据结构时的心得&#xff0c;希望能够帮助到大家&#xff0c;也许有些许遗漏&#xff0c;但博主已经尽了最大努力打破信息差&#xff0c;如果有遗漏还请见谅&#xff0c;嘻嘻&#xff0c;前路漫漫&#xff0c;我们一起前进&#xff01;&#xff01;&#xff0…
阅读更多...
超声波眼镜清洗机哪家强？盘点四款精品超声波清洗机机型

超声波眼镜清洗机哪家强？盘点四款精品超声波清洗机机型

超声波清洗机因其卓越的清洁能力&#xff0c;成为了家庭和专业环境中清洁小物件的理想选择。无论是日常佩戴的眼镜、珍贵的珠宝首饰&#xff0c;还是精密的电子设备和实验工具&#xff0c;超声波清洗机都能提供深层、温和且高效的清洁。然而&#xff0c;面对市场上众多品牌和价…
阅读更多...
原神4.8版本升级计划数据表

原神4.8版本升级计划数据表

原神4.8版本角色数据升级计划表 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>原神4.8版本升级计划…
阅读更多...
使用Anaconda安装多个版本的Python并与Pycharm进行对接

使用Anaconda安装多个版本的Python并与Pycharm进行对接

1、参考链接 Anaconda安装使用教程解决多Python版本问题_anaconda安装多个python版本-CSDN博客 基于上面的一篇博客的提示&#xff0c;我做了尝试。并在Pycharm的对接上做了拓展。 2、首先安装Anaconda 这个比较简单&#xff0c;直接安装即可&#xff1a; 3、设置conda.exe的…
阅读更多...
【iOS】SideTable

【iOS】SideTable

目录 SideTablesStripedMapSideTable1. spinlock_t slock2. RefcountMap3. weak_table_t 总结 objc4源码地址&#xff1a; SideTable& table SideTables()[this]; // 获取对象的SideTable size_t& refcntStorage table.refcnts[this];SideTables 查源码SideTables…
阅读更多...
K8s第三节：k8s1.23.1升级为k8s1.30.0

K8s第三节：k8s1.23.1升级为k8s1.30.0

上回书说到我们使用了kubeadm安装了k8s1.23.1,但是在k8s1.24之前还是使用docker作为容器运行时&#xff0c;所以这一节我打算将我安装的k8s集群升级为1.30.0版本&#xff1b; 1、修改containerd 配置 因为我们安装的docker自带containerd&#xff0c;所以我们不需要重新安装con…
阅读更多...
docker拉取MySQL后数据库连接失败解决方案

docker拉取MySQL后数据库连接失败解决方案

如果数据库连接失败&#xff0c;检查以下几个地方&#xff1a; 1&#xff1a;防火墙&#xff0c;查看防火墙是否打开&#xff1a; systemctl status firewalld 关闭状态&#xff1a; 开启状态&#xff1a; 如果是开启状态&#xff0c;则很有可能是防火墙拦截掉了3306端口的访问…
阅读更多...
挖矿木马攻破了服务器

挖矿木马攻破了服务器

最近被国外的挖矿木马攻破了服务器 根据非法登录&#xff0c;用 #last指令查看登录ip 首先删掉登录主机 #kill -9 pts/0 第二步 #top 看看什么占用cpu高 第三步杀死狂刷CPU的服务 过一分钟后&#xff0c;服务又开始狂刷cpu。 第四步根据pid查到服务地址 #systemctl status…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023