数据结构————单链表

引言

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

全部代码：

#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;}
}

结语： 

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

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

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

相关文章

探探我对测试开发的看法？

探探我对测试开发的看法？

测试开发岗位主要负责确保软件的可用性和稳定性。 ● 可用性不仅包括功能的正常使用&#xff0c;还涵盖了软件在不同环境下的兼容性&#xff0c;如各种网络环境、不同 CPU 核心环境以及多样化的移动端设备等。 ● 稳定性方面我的理解是&#xff0c;测试人员不仅要从用户角度评判…
阅读更多...
OpenAI gym: How to get complete list of ATARI environments

OpenAI gym: How to get complete list of ATARI environments

题意&#xff1a;OpenAI Gym&#xff1a;如何获取完整的 ATARI 环境列表 问题背景&#xff1a; I have installed OpenAI gym and the ATARI environments. I know that I can find all the ATARI games in the documentation but is there a way to do this in Python, witho…
阅读更多...
UE5 半透明阴影 快速解决方案

UE5 半透明阴影 快速解决方案

Step 1&#xff1a; 打开该选项 Step 2&#xff1a; 将半透明材质给到模型后&#xff0c;设置光照的Shadow Resolution Scale&#xff0c;越大&#xff0c;阴影的效果越好 Step 3&#xff1a; 用这种方式去做&#xff0c;阴影会因为半透明的程度&#xff0c;降低阴影的浓度 要…
阅读更多...
使用Azure+C#+visual studio开发图像目标检测系统

使用Azure+C#+visual studio开发图像目标检测系统

在这篇文章里面&#xff0c;我们讲解使用AzureC#visual studio在Azure上做图像的目标检测系统。 笔者是头一次接触C#。之前以Python Java和Scala为主。感觉C#.Net是一种挺好用的开发系统。C#和Java非常像。会一个学另一个很快。 首先&#xff0c;目标检测是个什么东西&#x…
阅读更多...
【高校主办，EI稳定检索】2024年人机交互与虚拟现实国际会议（HCIVR 2024）

【高校主办，EI稳定检索】2024年人机交互与虚拟现实国际会议（HCIVR 2024）

会议简介 2024年人机交互与虚拟现实国际会议&#xff08;HCIVR 2024&#xff09;定于2024年11月15-17日在中国杭州召开&#xff0c;会议由浙江工业大学主办。人机交互&#xff0c;虚拟现实技术的发展趋势主要体现在系统将越来越实际化&#xff0c;也越来越贴近人类的感知和需求…
阅读更多...
python-新冠病毒

python-新冠病毒

题目描述 假设我们掌握了特定时间段内特定城市的新冠病毒感染病例的信息。在排名 i 的当天有 i 个案例&#xff0c;即&#xff1a; 第一天有一例感染第二天有两例感染第三天有三例感染以此类推...... 请计算 n 天内的感染总数和每天平均感染数。 输入 整数 n 表示天数&…
阅读更多...
将星 x17 安装ubuntu 20.04 双系统

将星 x17 安装ubuntu 20.04 双系统

准备工作&#xff0c;包含关闭快速启动&#xff0c;关闭Secret Boot 1.进入控制面板选择小图标&#xff0c;找到电源选项 2.点击更改当前不可用的设置&#xff0c;关闭快速启动 3.开机启动时快速按F2&#xff0c;进入BIOS 4.选择Setup Utiltity&#xff0c;选择Security&#…
阅读更多...
LeetCode 热题 100 回顾5

LeetCode 热题 100 回顾5

干货分享&#xff0c;感谢您的阅读&#xff01;原文见&#xff1a;LeetCode 热题 100 回顾_力code热题100-CSDN博客 一、哈希部分 1.两数之和 &#xff08;简单&#xff09; 题目描述 给定一个整数数组 nums 和一个整数目标值 target&#xff0c;请你在该数组中找出 和为目标…
阅读更多...
ArcGIS之建模处理栅格数据以表格显示分区统计（以夜间灯光数据为例）

ArcGIS之建模处理栅格数据以表格显示分区统计（以夜间灯光数据为例）

当需要计算一个shp数据中多个面中的栅格数据值是&#xff0c;可以通过模型构建器进行批量处理&#xff0c;也就是统计多个面中的栅格数据值。但在处理过程中可能会遇见不同的错误&#xff0c;本文会介绍ERROR000883的解决办法。 数据准备&#xff1a;一个shp数据&#xff08;例…
阅读更多...
Idea 创建 Maven项目的时候卡死

Idea 创建 Maven项目的时候卡死

文章目录 一、Archetype 和 Catalog1.1 Archetype&#xff08;原型&#xff09;1.2 Catalog&#xff08;目录&#xff09; 二、可能遇到的问题2.1 问题描述2.2 原因分析2.3 解决方案 参考资料 一、Archetype 和 Catalog 1.1 Archetype&#xff08;原型&#xff09; Archetype…
阅读更多...
私域电商 IP 化发展的探索与优势

私域电商 IP 化发展的探索与优势

摘要&#xff1a;本文聚焦于私域电商与社交电商的区别&#xff0c;重点探讨私域电商的 IP 属性。深入分析其在获取流量、转化用户以及挖掘用户价值方面的独特优势。同时引入链动 2 1 模式、AI 智能名片、S2B2C 商城小程序源码等元素&#xff0c;详细阐述这些元素在私域电商 IP…
阅读更多...
C++——哈希

C++——哈希

目录 1.undered系列容器 1.1 undered_map 1.1.1 undered_map特点介绍 1.1.2 undered_map接口介绍 1.2 undered_set 2.底层结构 2.1 哈希概念 2.2 哈希冲突 2.3 哈希函数 2.3.1 哈希函数设计原则&#xff1a; 2.3.2 常见哈希函数 1.直接定值法 2.除留余数法 3.平方…
阅读更多...
数学建模笔记——层次分析法

数学建模笔记——层次分析法

数学建模笔记——层次分析法 数学建模笔记——层次分析法1. 层次分析法的基本原理和步骤2. 层次分析法的建模过程2.1 问题的提出2.2 模型原理2.3 为该问题建立层次结构模型2.4 构造判断矩阵1. 判断矩阵的含义2. 为该问题构造判断矩阵 2.5 一致性检验1. 一致性检验方法2. 对上述…
阅读更多...
相机内存卡格式化了照片怎么恢复？格式化恢复详解

相机内存卡格式化了照片怎么恢复？格式化恢复详解

摄影爱好者们都知道&#xff0c;相机内存卡是记录我们美好瞬间的重要媒介。然而&#xff0c;在使用过程中&#xff0c;有时我们会因操作不当或设备故障&#xff0c;不小心格式化了内存卡&#xff0c;从而导致珍贵的照片丢失。面对这种情况&#xff0c;我们该如何恢复这些被格式…
阅读更多...
电脑pe是什么意思_电脑pe系统作用详细分析

电脑pe是什么意思_电脑pe系统作用详细分析

有些小白很好奇&#xff0c;电脑pe是什么意思?所谓的电脑pe系统其实就是当我们的电脑出现问题而不能进入正常系统时候的一种“紧急备用”系统。如果需要重装操作系统的话&#xff0c;以往采用光盘使用的比较多&#xff0c;随着技术的进步&#xff0c;用u盘制作一个pe启动盘去安…
阅读更多...
【自然语言处理】实验一：基于NLP工具的中文分词

【自然语言处理】实验一：基于NLP工具的中文分词

目录 前言 1. 导入jieba分词器 2. 用精确模式进行中文分词 3. 用全模式进行中文分词 4. 用搜索引擎进行中文分词 5. 利用 lcut返回结果列表(list) 总结 &#x1f308;嗨&#xff01;我是Filotimo__&#x1f308;。很高兴与大家相识&#xff0c;希望我的博客能对你有所帮助。 &a…
阅读更多...
避免在C#循环中使用await

避免在C#循环中使用await

在C#中&#xff0c;异步编程因其能够提升应用程序性能和响应能力而变得越来越流行。async和await关键字使得编写异步代码变得更加容易&#xff0c;但如果使用不当&#xff0c;它们也可能引入一些陷阱。一个常见的错误是在循环中使用await&#xff0c;这可能导致性能瓶颈和意外行…
阅读更多...
直播相关01-录制麦克风声音，QT上 .pro 将 linux，mac和windows上配置为三种可以共享, 在.pro文件中 message 的作用

直播相关01-录制麦克风声音，QT上 .pro 将 linux，mac和windows上配置为三种可以共享, 在.pro文件中 message 的作用

一 QT 上的 .pro 文件 将 linux&#xff0c;mac和windows上配置设置为可以共享 1. 先来看文件夹布局 2. 再来看 QT 中的 .pro文件 .pro 文件的写法 QT core guigreaterThan(QT_MAJOR_VERSION, 4): QT widgetsCONFIG c11# The following define makes your compiler …
阅读更多...
Spring框架的核心模块有哪些

Spring框架的核心模块有哪些

Spring框架的核心模块构成了其基础架构&#xff0c;并为开发者提供了丰富的功能。以下是一些主要的Spring核心模块&#xff1a; Spring Core&#xff1a; 这是Spring框架中最基础的模块&#xff0c;提供了依赖注入&#xff08;DI&#xff09;功能&#xff0c;这是Spring的基石。…
阅读更多...
职场答案薄

职场答案薄

公司做大的过程就是创始人把职责一层层分摊下去的过程&#xff0c;公司里的各级领导在招聘时的原始诉求都是一样的&#xff0c;就是招到可以帮自己分担一部分工作的人&#xff0c;然后自己好集中精力去做更重要的工作 如何去做运营 1.流程制度&#xff08;三个目的&#xff1a;…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023