浅谈【数据结构】链表之单链表

2024-08-25 21:44
文章标签 链表 数据结构 单链 浅谈

本文主要是介绍浅谈【数据结构】链表之单链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

1、什么是数据？

2、什么是结构

3、什么是数据结构？

4、线性结构(线性表）

4.1线性表的物理结构的实现

5、链表

5.1无头结点的单链表

5.2新内容、老面孔

5.3数组和链表的优缺点

5.4链表的概念

5.5链表的创建步骤

5.5.1创建过程

5.5.2尾插法

5.5.3头插法

5.5.4中间插入法

谢谢帅气美丽且优秀的你看完我的文章还要点赞、收藏加关注

没错，说的就是你，不用再怀疑！！！

希望我的文章内容能对你有帮助，一起努力吧！！！

在IT界有一个公式：程序=数据结构+算法

1、什么是数据？

数据（data）是客观事物的一个符号表示，在计算机科学中式指所有能够输入到计算机中并能够被计算 机程序处理的符号统称。

数据元素（data element）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一 个数据元素可以由若干个数据项（data item）组成。数据项是数据不可分割的最小单位。

数据对象（data object）是性质相同的数据元素的集合，是一个数据的子集。

2、什么是结构

结构：数据元素之间的关系的不同性质称之为：结构（structure）

根据数据元素之间的关系的性质不同， 通常有四类基本结构：

  • 集合：结构中的数据元素之间，除了“同属于一个集合的关系”之外，就没有其它关系了。
  • 线性结构：（顺序）
  • 树状结构：（层次）
  • 网状结构：（图状）

3、什么是数据结构？

数据结构的形式定义：数据结构是一个二元组

Data_Sturcture = (D,S)

其中：D是数据元素的有限集，S是D上的关系的有限集（数据元素之间的关系的集合）

结构定义中的“关系”描述的是数据元素之间的逻辑关系（指向关系），因此又称之为：“逻辑结构”

“逻辑结构”并不一定是数据元素在计算机中的存储（称为：映像）表示，数据元素存储结构称为：数据 的物理结构，又称：“存储结构”。

4、线性结构(线性表）

例子：

26个英文字母（A、B、C、D...Z）

 班上同学的学号

日期

...

线性表的数据元素可以是各种各样、但是同一个线性表中的元素必须要具有相同的特性，即同属于同一 个数据对象，相邻的元素之间存储序偶关系。

若将线性表记为：（a1、a2、a3....an）那么则会存在以下性质：

  • 存在唯一的一个被称为："第一个"的数据元素
  • 存在唯一的一个被称为：“最后一个”的数据元素
  • 除了第一个元素之外，集合中的每一个数据元素均只有一个前驱结点
  • 除了最后一个元素之外，集合中的每一个数据元素均只有一个后继结点
    • 前驱结点：前面有结点
    • 后继结点：后面有结点

4.1线性表的物理结构的实现

在计算机中是怎么存储线性表的

  • 顺序结构
    • 线性表的顺序表示的是用一组地址连续的存储单元依次存储线性表中数据元素
      • 数组
      • 动态开辟内存空间
  • 链式结构
    • 链式结构存储用的存储单元的地址不一定连续的

5、链表

链表：链式存储的线性表

5.1无头结点的单链表

无头结点的单链表：没有头结点的单向的链式存储的线性表。

问题：我们在定义数组的时候，需要规定数组的长度，定义好了就不能修改了。

int a[10]; // 定义了一个元素为int类型的数组，数组大小为10个int类型

// 修改数组的大小

a = malloc(sizeof(int) * 100); // 不行的，因为a是常量指针，不能改变a指向。

链表就是有一个或者是多个结构体通过指针去进行指向关系构成的。

5.2新内容、老面孔

先来看一下下面这种结构体类型（带指针的结构体）

struct data

{

        int d_data; // 数据

        struct data *p_data; // 指针 存储数据元素的地址。在单链表结构里面，存储下一个数据元素的 内存地址

};

即想要按需分配，又可以进行灵活的删除和增加元素的时候：链表就可以解决这样的问题。

5.3数组和链表的优缺点

数组：

  • 优点：
    • 数组将元素按顺序存放在内存中，而且元素的内存占用都是相同的，因为它的地址连续、所有 可以通过下标快速的对数组元素进行访问。
    • 内存不会有太多的碎片化
  • 缺点：
    • 有可能造成内存资源的浪费
    • 数组元素的插入和删除比较复杂
    • 有可能内存资源不够用，容易造成段错误（内存越界）

链表：

  • 优点：
    • 插入和删除很方便
    • 可以按需分配，不会造成空间的浪费
  • 缺点：
    • 空间不是连续，访问相对数组而言效率要低很多碎片化比数组要高

获取结构体空间方式：

  • 动态内存开辟：堆空间的内存
    • 特性：空间的生存期是随进程持续性，需要手动释放
    • 保存空间地址
  • 通过定义变量：栈空间的内存
    • 特性：作用域结束，空间就会被系统释放
    • 用变量名

5.4链表的概念

链表就是由一个或者是多个包含指针成员变量的结构体，通过其指针变量来指向其他同类型结构体内存 地址来形成一种逻辑上的链式的数据结构。我们把每一个结构体实例（变量/空间）称为该链表的：结点 （node)

  • 首结点
    • 是链表中唯一一个没有前驱结点、只有后继结点的结点。是唯一一个指向其他的结点的结点
    • 首结点同时也是整个链表的首地址。
  • 尾结点
    • 是链表中唯一一个没有后继结点，只有前驱结点的结点。是唯一一个被其他结点指向的结点。

注意：尾结点的指针成员是指向 空 的

  • 可以保证尾结点的指针成员不会成为野指针
  • 可以通过判断指针是否指向空来判断是不是查询到了最后一个元素

***无头结点单链表基础示例***

/*无头结点的单链表
*/#include <iostream>/*结点类型
*/
struct node
{// 用来存储数据的空间（成员）称为：数据域int data;       // 用来保存其他结点的地址（关系）称为：指针域struct node *next;
};/*@brief:创建一个新链表@return:返回新链表的首结点的地址
*/
struct node *createNewList()
{// 新链表的首结点指针struct node *newList = nullptr;// 循环通过数据不断的去增加新结点到链表中while(1){int data = -1;// 通过键盘获取数据std::cin >> data;// 判断退出条件if(data == -1)break;// 申请了一个新结点的空间struct node *newNode = new struct node;newNode->data = data; // 将通过键盘获取到的数据存入结构体的数据域中newNode->next = nullptr; // 因为它是一个新结点，暂时是没有后继结点// 增加到链表里面:向后增加（尾插法）// 做第一次判断：链表中有没有结点if(newList == nullptr){// 如果newList是nullptr说明该链表里面为空，当前的新节点就是首届点newList = newNode;continue; // 继续增加新结点}// 搞一个临时指针，来指向首结点struct node *node_ptr = newList;// 找尾结点while(node_ptr->next)node_ptr = node_ptr->next;// 到这个位置 node_ptr 此时指向的结点是尾结点// 就可以把newNode作为尾结点的后继结点添加到链表里面去了node_ptr->next = newNode;}return newList;
}// 打印链表（遍历方法）
void printList(struct node *list)
{// 判断是不是空链表if(list == nullptr){std::cout << "链表为空" << std::endl;return;}std::cout << "List( ";// 如果不为空打印链表元素while(list) // 只要list不为空就一直循环{// list本来就可以表示首结点std::cout << list->data << " ";// 让list移动到下一个结点list = list->next;}std::cout << ")" << std::endl;
}int main()
{// 不在栈空间里面申请结点空间// 创建一个链表struct node *newList = createNewList();// 打印链表元素printList(newList); // 传入的值是newList存储的地址，并非newList自己的地址return 0;
}

5.5链表的创建步骤

  • 每获取一个数据，就一个创建一个结构体空间来存储数据
  • 把数据存放到结构体体空间中
  • 把这个新的结构体加入到链表中

5.5.1创建过程

  • 从无到有的过程：
    • 第一个结点诞生，此时首结点和尾结点都是第一个结点本身
  • 从少到多的过程
    • 在链表中增加结点，可以在链表尾部增加（尾插法）、也可以在链表的中间增加（中间插入 法）、也可以在链表头部增加（头插法）
  • 图示：

5.5.2尾插法

新节点增加在链表原尾结点的后面，即链表原尾结点要指向新结点（成为原尾结点的后继结点），然后 新结点就代替原尾结点成为新的尾结点

  • 特点：先加入的链表的结点在前面，而后加入结点在后面

5.5.3头插法

新结点在原首结点的前面，即新结点指向首结点（成为原首结点的前驱结点），然后新结点代替原首结 点称为新的首结点

  • 特点：先加入链表的结点在后面，后加入链表的结点在前面

5.5.4中间插入法

通过和每个结点数据进行比对，从而找到新结点存放的位置。通过中间插入法创建的链表是有序的。

  • 特点：链表的结点数据是有序的。

***单链表基础操作示例***

/*无头结点的单链表
*/#include <iostream>/*结点类型
*/
struct node
{// 用来存储数据的空间（成员）称为：数据域int data;       // 用来保存其他结点的地址（关系）称为：指针域struct node *next;
};/*@brief：头部插入@param: list 需要增加新数据的链表指针@param: data 是需要存入链表的数据@return : 链表首地址
*/
struct node* addNodeHead(struct node *list,int data)
{// list 表示就是一个链表（链表首地址/首结点的地址）头插法其实就是在它的首结点前面插入struct node *newNode = new struct node;newNode->data = data; // 数据存入结点数据域newNode->next = list; // 因为新结点作为新的首结点存入链表，那么原有的首结点就变成了新节点后继结点return newNode; // 返回newNode因为newNode变成了新的首结点了。更新链表的首地址
}/*@brief: 尾部插入@param: list 需要增加新数据的链表指针@param: data 是需要存入链表的数据@return : 链表首地址
*/
struct node* addNodeTail(struct node *list,int data)
{struct node *newNode = new struct node;newNode->data = data; // 将通过键盘获取到的数据存入结构体的数据域中newNode->next = nullptr; // 因为它是一个新结点，暂时是没有后继结点// 搞一个临时指针，来指向首结点struct node *node_ptr = list;// 找尾结点while(node_ptr->next)node_ptr = node_ptr->next;// 到这个位置 node_ptr 此时指向的结点是尾结点// 就可以把newNode作为尾结点的后继结点添加到链表里面去了node_ptr->next = newNode;return list;
}/*@brief : 中间插入法@param : list 需要增加数据的链表首地址@param : data 需要增加到链表的数据@return : 链表首地址
*/
struct node *addNodeMid(struct node *list,int data)
{struct node *newNode = new struct node;newNode->data = data; // 将通过键盘获取到的数据存入结构体的数据域中newNode->next = nullptr; // 因为它是一个新结点，暂时是没有后继结点// 循环比较数据 大到小  小到大// struct node *node_previce = nullptr;// struct node *node_current = list;// 第一种方法两个指针// while(node_current)// {//     if(node_current->data > data)//         break; // 找到插入位置了//     // 把两个指针往后移//     node_previce = node_current;//     node_current = node_current->next;// }// // 进行插入// if(node_previce == nullptr) // 说明需要作为首结点插入（头插入)// {//     // 头插代码// }// else// {//     // 直接插入到node_previce的后面//     newNode->next = node_previce->next; // 要成为node_previce下一个结点的前驱结点//     node_previce->next = newNode; // 然后让newNode成为node_previce的后继结点// }// 第二种方法提前判断struct node *node_ptr = list;// 如果第一个结点就比data大说明要插入到最前面（头插法）if(node_ptr->data > data){// 头插法list = addNodeHead(list,data);return list;} while(node_ptr&&node_ptr->next){std::cout << node_ptr->data << std::endl;if(node_ptr->data < data && node_ptr->next->data >= data) // 大于前一个小于后一个{// 将新结点的next指向当前结点的后继结点node_ptr->nextnewNode->next = node_ptr->next;// 让newNode成为node_ptr的后继结点node_ptr->next = newNode;return list; // 退出增加}// 把指针往后移node_ptr = node_ptr->next;}// 严谨判断一下node_ptr->next是不是为空if(node_ptr->next == nullptr) // 尾插法{node_ptr->next = newNode;}return list;
}/*@brief:创建一个新链表@return:返回新链表的首结点的地址
*/
struct node *createNewList()
{// 新链表的首结点指针struct node *newList = nullptr;// 循环通过数据不断的去增加新结点到链表中while(1){int data = -1;// 通过键盘获取数据std::cin >> data;// 判断退出条件if(data == -1)break;// 做第一次判断：链表中有没有结点if(newList == nullptr){struct node *newNode = new struct node;newNode->data = data; // 将通过键盘获取到的数据存入结构体的数据域中newNode->next = nullptr; // 因为它是一个新结点，暂时是没有后继结点// 如果newList是nullptr说明该链表里面为空，当前的新节点就是首届点newList = newNode;continue;}// 通过中间插入法增加结点newList = addNodeMid(newList,data);// 通过尾插法增加结点// newList = addNodeTail(newList,data);}return newList;
}// 打印链表（遍历方法）
void printList(struct node *list)
{// 判断是不是空链表if(list == nullptr){std::cout << "链表为空" << std::endl;return;}std::cout << "List( ";// 如果不为空打印链表元素while(list) // 只要list不为空就一直循环{// list本来就可以表示首结点std::cout << list->data << " ";// 让list移动到下一个结点list = list->next;}std::cout << ")" << std::endl;
}int main()
{// 不在栈空间里面申请结点空间// 创建一个链表struct node *newList = createNewList();// 打印链表元素printList(newList); // 传入的值是newList存储的地址，并非newList自己的地址// 删除元素int data = 0;std::cin >> data ;delNodeData(newList,data);// 打印链表元素printList(newList); // 传入的值是newList存储的地址，并非newList自己的地址return 0;
}

这篇关于浅谈【数据结构】链表之单链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1106739。

相关文章

浅谈配置MMCV环境,解决报错,版本不匹配问题

浅谈配置MMCV环境,解决报错,版本不匹配问题

《浅谈配置MMCV环境,解决报错,版本不匹配问题》：本文主要介绍浅谈配置MMCV环境,解决报错,版本不匹配问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录配置MMCV环境,解决报错,版本不匹配错误示例正确示例总结配置MMCV环境,解决报错,版本不匹配在col
阅读更多...
C#数据结构之字符串(string)详解

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》：本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘
阅读更多...
浅谈mysql的sql_mode可能会限制你的查询

浅谈mysql的sql_mode可能会限制你的查询

《浅谈mysql的sql_mode可能会限制你的查询》本文主要介绍了浅谈mysql的sql_mode可能会限制你的查询,这个问题主要说明的是,我们写的sql查询语句违背了聚合函数groupby的规则... 目录场景：问题描述原因分析：解决方案：第一种：修改后，只有当前生效，若是mysql服务重启，就会失效；
阅读更多...
使用C++实现链表元素的反转

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定
阅读更多...
Go语言中三种容器类型的数据结构详解

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据：本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组（Array）2. 切片（Slice）3. 映射（Map）对比总结注意事项基本概念在 Go 语言中，有三种主要
阅读更多...
使用C++实现单链表的操作与实践

使用C++实现单链表的操作与实践

《使用C++实现单链表的操作与实践》在程序设计中,链表是一种常见的数据结构,特别是在动态数据管理、频繁插入和删除元素的场景中,链表相比于数组,具有更高的灵活性和高效性,尤其是在需要频繁修改数据结构的应... 目录一、单链表的基本概念二、单链表类的设计1. 节点的定义2. 链表的类定义三、单链表的操作实现四、
阅读更多...
Spring核心思想之浅谈IoC容器与依赖倒置(DI)

Spring核心思想之浅谈IoC容器与依赖倒置(DI)

《Spring核心思想之浅谈IoC容器与依赖倒置(DI)》文章介绍了Spring的IoC和DI机制,以及MyBatis的动态代理,通过注解和反射,Spring能够自动管理对象的创建和依赖注入,而MyB... 目录一、控制反转 IoC二、依赖倒置 DI1. 详细概念2. Spring 中 DI 的实现原理三、
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
浅谈主机加固，六种有效的主机加固方法

浅谈主机加固，六种有效的主机加固方法

在数字化时代，数据的价值不言而喻，但随之而来的安全威胁也日益严峻。从勒索病毒到内部泄露，企业的数据安全面临着前所未有的挑战。为了应对这些挑战，一种全新的主机加固解决方案应运而生。 MCK主机加固解决方案，采用先进的安全容器中间件技术，构建起一套内核级的纵深立体防护体系。这一体系突破了传统安全防护的局限，即使在管理员权限被恶意利用的情况下，也能确保服务器的安全稳定运行。 普适主机加固措施：
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2