当前位置： 首页 > news >正文

数据结构————单链表

news 来源：原创 2024/9/20 10:35:26

引言

  在计算机科学的领域里，数据结构的探索与应用是程序设计的灵魂。单链表，作为一种基础而灵活的数据结构，不仅在理论上有着丰富的内涵，其在实际编程中的应用亦是广泛而深远。本文旨在深入浅出地介绍单链表的实现过程，从理论基础到代码实践，为读者呈现单链表构建的全过程。

全部代码：

#include<stdlib.h>
#include<stdio.h>typedef int ElemType;typedef struct LNode
{ElemType data;//数据域struct LNode* next;//指针域
}LinkNode;/*【1】整体建立单链表  给定数组a[n] */
//<1>头插法建立单链表
void CreateListF(LinkNode *&L,ElemType a[],int n)
{LinkNode * s;  //新节点L = (LinkNode*)malloc(sizeof(LinkNode));//创建头节点L->next = NULL;//头节点初始化for (int i = 0; i < n; i++){s = (LinkNode*)malloc(sizeof(LinkNode));//新节点创建s->data = a[i];// 初始化s->next = L->next;L->next = s;}
}
//<2>尾插法建立单链表
void CreateListR(LinkNode*& L, ElemType a[], int n)
{LinkNode* r, * s;//尾指针和新的节点指针L = (LinkNode*)malloc(sizeof(LinkNode));r = L;   //r始终指向尾节点，初始指向Lfor (int i = 0; i < n; i++){s = (LinkNode*)malloc(sizeof(LinkNode));//新节点创建和初始化s->data = a[i];r->next = s;//将节点s插入到r后面r = s;}r->next = NULL;  //尾节点的next域置为NULL
}
/*【2】基本运算 ----初始化*/
void  InitList(LinkNode*&L)
{L = (LinkNode*)malloc(sizeof(LinkNode));L->next = NULL;
}
/*【3】基本运算 ----销毁*/
void DestoryList(LinkNode*& L)
{LinkNode* pre = L;LinkNode* p = L->next;//pre指向p的前驱节点while (p != NULL)  //遍历单链表L{free(pre);//释放前驱节点pre = p;  //移动p = pre->next; }free(pre);  //循环结束，p为NULLL,pre指向尾节点，释放它
}
/*【4】基本运算 ----求表的长度*/
int ListLength(LinkNode *L)
{int n = 0;LinkNode* p = L;while (p->next != NULL){n++;p = p->next;}return n;
}
/*【5】基本运算 ----输出线性表*/
void printLinkNode(LinkNode* L)
{LinkNode* p = L->next;//指向头节点的下一个节点，头节点不存放数据while (p!= NULL){printf("%d->", p->data);p = p->next;}printf("end\n");
}
/*【6】基本运算 ----查找 */
//<1>按元素查找节点的序号  给定单链表 L 查找值为e的节点的序号i，存在返回该序号，否则返回0
int  LocateElem(LinkNode* L, ElemType e)
{LinkNode* p = L->next;int n = 1;  //逻辑序号，首节点位置为1while (p->next != NULL && p->data != e)//查找该节点{n++;p = p->next;}if (p == NULL)//不存在元素为e的节点{return 0;}else   //存在，返回逻辑序号n{return n;}
}
//<2>按序号求线性表中的元素，给定单链表L,查找第i个节点的元素值，提取到e，存在返回true 否则返回false
bool GetElem(LinkNode* L, int i, ElemType& e)
{LinkNode* p = L;//p指向头结点i，j置为0，即头节点序号为0int j = 0;if (i < 0)return false;while (j < i && p != NULL){j++;p = p->next;}if (p == NULL)//不存在第 i 个数据节点，返回false{return false;}else//存在，取值 并返回true{e = p->data;return true;}
}
/*【7】基本运算 ----插入   在第i个位置前面插入节点， p指向第i-1个节点，将s节点插入p后面 */  
bool ListInsert(LinkNode*& L, int i, ElemType e)
{int j = 0;if (i <= 0)return false;LinkNode* s, * p=L;while (j < i-1 && p != NULL)//寻找i-1的节点，然后由p指向它{j++;p = p->next;}if (p == NULL)//未找到·返回false{return  false;}else{s = (LinkNode*)malloc(sizeof(LinkNode));s->data = e;s->next = p->next;//将新节点插入到p之后（i-1的节点）p->next = s;return true;}
}
/*【8】基本运算  ---- 删除  ，给定L，删除第i个节点，并将删除节点的值带回p指向第i-1个节点,q为第i个节点，*/
bool ListDelete(LinkNode*& L, int i, ElemType& e)
{int j = 0;LinkNode* q, * p = L;if (i <= 0)return false;while (j < i - 1 && p != NULL){j++;p = p->next;}if (p == NULL)//没有找到第i-1个节点 返回false{return false;}else//找到第i-1和节点 ，进行删除操作{q = p->next;//q指向第i个节点if (q == NULL)return false;  //这个容易忽略，我们也因该判断第i个元素是否为空e = q->data;p->next = q->next;free(q);return true;}
}
int main()
{int a[5];int b[5] = { 1,2,3,4,5 };for (int i = 0; i < 5; i++){scanf_s("%d", &a[i]);}//用数组创建单链表LinkNode * L1;LinkNode * L2;CreateListF(L1, a,5); //头插法CreateListR(L2, b,5);//尾插法printLinkNode(L1);//输出单链表printLinkNode(L2);//输出单链表//按值查找，返回序号printf("L2 's number 5 is in the %d position\n", LocateElem(L2, 5));printf("L2 's number 3 is in the %d position\n", LocateElem(L2, 3));//按序号查找元素值int e1, e2;if(GetElem(L1,5,e1)){printf("The value at the 5 position of the L1 is %d\n", e1);}if (GetElem(L1, 1, e2)){printf("The value at the 1 position of the L1 is %d\n", e2);}//插入元素,插入到第i 个位置ListInsert(L1,5,6);printLinkNode(L1);//输出单链表ListInsert(L2, 1, 2);printLinkNode(L2);//输出单链表//删除元素int e = 0;if (ListDelete(L1,5,e)){printf("删除成功，删除的值为%d\n",e);}else{printf("删除失败，节点不存在");}printLinkNode(L1);//输出单链表DestoryList(L1);DestoryList(L2);return 0;
}

一、单链表的定义及其特点

定义

  单链表（Singly Linked List）是一种基本的数据结构，它由一系列节点组成，每个节点包含两部分：数据域和指针域。数据域用于存储实际的数据，而指针域则存储指向链表中下一个节点的地址。在单链表中，除了最后一个节点外，每个节点的指针域都指向下一个节点，最后一个节点的指针域通常设置为NULL，以标识链表的结束。单链表的特点是其存储不需要连续的内存空间，节点可以分散在内存中的任意位置，通过指针连接形成线性结构。 

特点

  1. 动态存储：单链表的长度可以动态变化，可以根据需要动态地添加或删除节点。

  2. 非连续存储：节点在内存中的位置不需要连续，只需通过指针连接即可。

  3. 易于插入和删除：在单链表中插入或删除节点只需修改相应节点的指针，时间复杂度为O(1)，但前提是能够快速访问到要操作的节点或其前驱节点。

  4. 不支持随机访问：访问单链表中的特定节点需要从头节点开始逐个遍历，时间复杂度为O(n)。

  5. 额外空间存储指针：每个节点除了存储数据外，还需要额外的空间来存储指向下一个节点的指针。

  6. 头指针：单链表通常有一个头指针，用于访问链表的第一个节点。头指针可能指向头节点（头节点包含数据）或直接指向第一个实际数据节点（头节点不存储数据）。 

单链表的实现

  准备工作：

自定义数据元素类型：

typedef int ElemType;

结构体：

typedef struct LNode
{ElemType data;//数据域struct LNode* next;//指针域
}LinkNode;

1.单链表的创建

单链表的创建通常涉及两种主要的插入方法：头插法和尾插法。

1.1头插法介绍

定义

  头插法指的是在单链表的头部插入节点。新节点的指针将指向当前的头节点，然后更新头指针以指向新节点。

特点
  • 实现简单，插入操作时间复杂度为O(1)。
  • 但链表元素的顺序与插入顺序相反，如果需要保持原有顺序，需要在插入后进行反转

大致实现步骤：

  1. 创建新节点。
  2. 将新节点的next指针设置为头指针所指向的节点。
  3. 更新头指针，使其指向新节点。
代码：整体建立单链表，给定数组
void CreateListF(LinkNode *&L,ElemType a[],int n)
{LinkNode * s;  //新节点L = (LinkNode*)malloc(sizeof(LinkNode));//创建头节点L->next = NULL;//头节点初始化for (int i = 0; i < n; i++){s = (LinkNode*)malloc(sizeof(LinkNode));//新节点创建s->data = a[i];// 初始化s->next = L->next;L->next = s;}
}

1.2尾插法介绍

定义

  尾插法指的是在单链表的尾部插入节点。此方法下，新节点成为链表的最后一个节点。

特点
  • 插入操作的时间复杂度为O(n)，因为可能需要遍历整个链表。
  • 保持了数据的插入顺序，链表元素的顺序与插入顺序一致。

大致实现步骤：

  1. 创建新节点。
  2. 如果链表为空，新节点同时作为头节点和尾节点。
  3. 如果链表非空，遍历链表找到尾节点，将尾节点的next指针指向新节点。
代码：整体建立单链表，给定数组
//<2>尾插法建立单链表
void CreateListR(LinkNode*& L, ElemType a[], int n)
{LinkNode* r, * s;//尾指针和新的节点指针L = (LinkNode*)malloc(sizeof(LinkNode));r = L;   //r始终指向尾节点，初始指向Lfor (int i = 0; i < n; i++){s = (LinkNode*)malloc(sizeof(LinkNode));//新节点创建和初始化s->data = a[i];r->next = s;//将节点s插入到r后面r = s;}r->next = NULL;  //尾节点的next域置为NULL
}

总结：

 头插法和尾插法各有优劣，选择哪种方法取决于具体的应用场景。如果需要快速插入节点且不关心元素的顺序，头插法是更好的选择。反之，如果要保持元素的插入顺序，尾插法则更为合适。在实际应用中，根据需求灵活选择插入方法，可以更高效地创建和管理单链表。

2.单链表的初始化

  创建一个头结点，并将其头结点的next域置空

void  InitList(LinkNode*&L)
{L = (LinkNode*)malloc(sizeof(LinkNode));L->next = NULL;
}

3.单链表的求表长

 用p指向头结点，用n来累计数据节点的个数，n初始值为0；

int ListLength(LinkNode *L)
{int n = 0;LinkNode* p = L;while (p->next != NULL){n++;p = p->next;}return n;
}

4.单链表的销毁

实现步骤：

1.  pre 和 p指向相邻的节点，初始pre 指向头结点，p指向首个数据节点。

2.p不为空时循环，释放pre节点，然后pre 和p 俩个节点后移。

3. 循环结束后pre指向尾节点，将其释放

代码：
/*【3】基本运算 ----销毁*/
void DestoryList(LinkNode*& L)
{LinkNode* pre = L;LinkNode* p = L->next;//pre指向p的前驱节点while (p != NULL)  //遍历单链表L{free(pre);//释放前驱节点pre = p;  //移动p = pre->next; }free(pre);  //循环结束，p为NULLL,pre指向尾节点，释放它
}

5.单链表的插入

 给定单链表L ,在第i个位置插入节点s，值为e。

实现步骤：

1.在单链表L中找到第i-1个结点，由p指向他

2.若存在该结点，将值为e的s结点插入p节点的后面。

代码：

/*【7】基本运算 ----插入   在第i个位置前面插入节点， p指向第i-1个节点，将s节点插入p后面 */  
bool ListInsert(LinkNode*& L, int i, ElemType e)
{int j = 0;if (i <= 0)return false;LinkNode* s, * p=L;while (j < i-1 && p != NULL)//寻找i-1的节点，然后由p指向它{j++;p = p->next;}if (p == NULL)//未找到·返回false{return  false;}else{s = (LinkNode*)malloc(sizeof(LinkNode));s->data = e;s->next = p->next;//将新节点插入到p之后（i-1的节点）p->next = s;return true;}
}

6.单链表的查找

 6.1按序查找

实现步骤：

1. p指向头结点，用j来累计遍历过的数据结点的个数（初始值为0)，当j<i且不为空时循环：j增1,p指向下一个结点。

2. 循环结束后有两种情况，若为空，表示单链表L中没有第i个数据结点（参数i错误），返回false；否则找到第i个数据结点力，提取它的值并返回true。

代码：

/<2>按序号求线性表中的元素，给定单链表L,查找第i个节点的元素值，提取到e，存在返回true 否则返回false
bool GetElem(LinkNode* L, int i, ElemType& e)
{LinkNode* p = L;//p指向头结点i，j置为0，即头节点序号为0int j = 0;if (i < 0)return false;while (j < i && p != NULL){j++;p = p->next;}if (p == NULL)//不存在第 i 个数据节点，返回false{return false;}else//存在，取值 并返回true{e = p->data;return true;}
}

6.2按值查找

 在单链表L中从头开始找到第一个值域为e的结点，找到返回逻辑序号，否则返回0

实现步骤： 

代码：

//<1>按元素查找节点的序号  给定单链表 L 查找值为e的节点的序号i，存在返回该序号，否则返回0
int  LocateElem(LinkNode* L, ElemType e)
{LinkNode* p = L->next;int n = 1;  //逻辑序号，首节点位置为1while (p->next != NULL && p->data != e)//查找该节点{n++;p = p->next;}if (p == NULL)//不存在元素为e的节点{return 0;}else   //存在，返回逻辑序号n{return n;}
}

7.单链表的删除元素

  给定单链表L，删除第i个节点，并将删除节点的值带回，p指向第i-1个节点,q为第i个节点，*/

实现步骤：

1.在单链表L中找到第i一1个结点，由p指向它。

2.若存在这样结点，且也存在后继结点（由q指向它），则删除通过结点pq所指的结点，返回true；否则回false,表示参数i错误。

代码：

/*【8】基本运算  ---- 删除  ，给定L，删除第i个节点，并将删除节点的值带回p指向第i-1个节点,q为第i个节点，*/
bool ListDelete(LinkNode*& L, int i, ElemType& e)
{int j = 0;LinkNode* q, * p = L;if (i <= 0)return false;while (j < i - 1 && p != NULL){j++;p = p->next;}if (p == NULL)//没有找到第i-1个节点 返回false{return false;}else//找到第i-1和节点 ，进行删除操作{q = p->next;//q指向第i个节点if (q == NULL)return false;  //这个容易忽略，我们也因该判断第i个元素是否为空e = q->data;p->next = q->next;free(q);return true;}
}

结语： 

  单链表的实现，不仅是一次理论与实践的完美结合，更是一个程序员逻辑思维与动手能力的双重考验。通过对单链表的深入理解与实现，我们不仅掌握了数据结构的精髓，更在编程的道路上迈出了坚实的一步。未来，无论是面对复杂的数据处理，还是高效算法的设计，单链表都将成为我们手中得心应手的工具，助力我们在编程的世界里自由翱翔。

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • Unity3D ARPG（动作角色扮演游戏）设计与实现详解
  • Python 基础之模块与文件操作（Basic Modules and File Operations in Python）
  • HTML、CSS实现树状图
  • ROM RAM
  • 四数相加 II--力扣454
  • 【经纬度坐标系、墨卡托投影坐标系和屏幕坐标系转换详解】
  • Numpy中常用的数学方法
  • 输入子系统
  • 大型语言模型中推理链的演绎验证
  • 漫谈设计模式 [2]：工厂方法模式
  • 第145天：内网安全-Linux权限维持Rootkit后门Strace监控Alias别名Cron定时任务
  • 在这12种场景下会使Spring事务失效--注意防范
  • RestTemplate服务调用
  • Qt C++ Udp相关知识学习（一）
  • React 通用后台管理项目
  • 分享的文章《人生如棋》
  • Android Studio：GIT提交项目到远程仓库
  • CoolViewPager:即刻刷新,自定义边缘效果颜色,双向自动循环,内置垂直切换效果,想要的都在这里...
  • FastReport在线报表设计器工作原理
  • GDB 调试 Mysql 实战（三）优先队列排序算法中的行记录长度统计是怎么来的（上）...
  • mac修复ab及siege安装
  • Meteor的表单提交:Form
  • SpiderData 2019年2月13日 DApp数据排行榜
  • 程序员该如何有效的找工作?
  • 翻译：Hystrix - How To Use
  • 基于阿里云移动推送的移动应用推送模式最佳实践
  • 计算机在识别图像时“看到”了什么？
  • 快速构建spring-cloud+sleuth+rabbit+ zipkin+es+kibana+grafana日志跟踪平台
  • 如何进阶一名有竞争力的程序员?
  • 如何胜任知名企业的商业数据分析师？
  • 提升用户体验的利器——使用Vue-Occupy实现占位效果
  • 在GitHub多个账号上使用不同的SSH的配置方法
  • 正则学习笔记
  • No resource identifier found for attribute,RxJava之zip操作符
  • 哈罗单车融资几十亿元，蚂蚁金服与春华资本加持 ...
  • ​flutter 代码混淆
  • ######## golang各章节终篇索引 ########
  • #if和#ifdef区别
  • #Linux（make工具和makefile文件以及makefile语法）
  • #LLM入门|Prompt#1.8_聊天机器人_Chatbot
  • #免费 苹果M系芯片Macbook电脑MacOS使用Bash脚本写入(读写)NTFS硬盘教程
  • #我与Java虚拟机的故事#连载03：面试过的百度，滴滴，快手都问了这些问题
  • （16）Reactor的测试——响应式Spring的道法术器
  • （2）关于RabbitMq 的 Topic Exchange 主题交换机
  • （3）(3.2) MAVLink2数据包签名(安全)
  • (31)对象的克隆
  • （4.10~4.16）
  • （6）STL算法之转换
  • （分享）一个图片添加水印的小demo的页面，可自定义样式
  • （附源码）ssm基于微信小程序的疫苗管理系统 毕业设计 092354
  • （蓝桥杯每日一题）平方末尾及补充（常用的字符串函数功能）
  • （四）stm32之通信协议
  • (转)socket Aio demo
  • (转)Sql Server 保留几位小数的两种做法
  • .net core Swagger 过滤部分Api