提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

c++的链表-C++链表

C++链表
2023-06-13 09:16:12 时间

  C++链表

  链表是由一系列连接在一起的结点构成，其中的每个结点都是一个数据结构。

  链表的结点通常是动态分配、使用和删除的，允许链表在程序运行时增大或缩小，如果需要将新信息添加到链表中，则程序只需要分配另一个结点并将其插入到系列中。如果需要从链表中删除特定的信息块，则程序将删除包含该信息的结点。

  为什么要用到链表

  数组作为存放同类数据的集合，给我们程序中带来了很多方便，增加了灵活性。但数组同样存在弊病。如数组的大小在定义时要事先规定大小，不能在程序中进行调整。所以我们只能够根据可能的最大需求来定义数组，常常会造成一定的存储空间浪费。

  我们希望构造动态的数组，随时可以调整数组的大小，以满足不同问题的需要。链表就是我们需要的动态数组。它是在程序的执行过程中根据需要有数据存储就向系统要求申请存储空间，决不构成对存储区的浪费。

  链表是一种复杂的数据结构，其数据之间相互关系使得链表分成三种：单链表、循环链表、双向链表。

  链表的结构

  链表中的每个结点都包含一个或多个保存数据的成员，例如：存储在结点中的数据可以是库存记录；或者它可以由客户的姓名、地址和电话号码等组成的客户信息记录。

  除了数据之外，每个结点还包含一根后继指针指向链表中的下一个结点。

  单个结点的组成

  非空链表的第一个结点称为链表的头。要访问链表中的结点，需要有一个指向链表头的指针。从链表头开始，可以按照存储在每个结点中的后继指针访问链表中的其余结点。最后一个结点中的后继指针被设置为 以指示链表的结束。

  指向链表头的指针用于定位链表的头部，所以也可以认为它代表了链表头。同样的指针也可以用来定位整个链表，从头开始，后面跟着后续指针，所以也可以很自然地把它看作是代表了整个链表。

  由 3 个结点组成的链表，其中显示了指向头部的指针，链表的 3 个结点以及表示链表末尾的 指针。

  链表结构图解

  一、单向链表

  单链表有一个头结点head，指向链表在内存的首地址。链表中的每一个结点的数据类型为结构体类型。结点有两个成员：整形成员（实际中需要保存的数据）和指向下一个结构体类型结点的指针即下一个结点的地址（至此，我们就拥有一个存放整形数据的动态数组（链表））。链表按此结构对各结点的访问需从链表的头找起，后续结点的地址由当前结点给出。无论表中访问那一个结点，都需要从链表的头开始。顺序向后查找。链表的尾结点由于无后续结点c++的链表，其指针域为空，写作NULL。

  链表中的各节点在内存的存储地址不是连续的，其各节点的地址是在需要时向系统申请分配的，系统根据内存的当前情况，既可以连续分配地址，也可以跳跃式分配地址。

  单向链表程序实现

  （1）链表节点的数据结构定义

`struct ListNode
{double value;
ListNode *next;};`   就是要存储在链表中的结点的类型，结构成员 value 是结点的数据部分，而另一个结构成员 next 则被声明为  的指针，它是指向下一个结点的后继指针。   结构有一个有趣的属性，它包含一个指向相同类型数据结构的指针，因此可以说是一个包含对自身引用的类型。像这样的类型称为自引用数据类型或自引用数据结构。  在已经声明了一个数据类型来表示结点之后，即可定义一个初始为空的链表，定义一个用作链表表头的指针并将其初始化为，   *head=;  可以创建一个链表，其中包含一个结点，存储值为20.6，  `head=new ListNode;  //分配新结点
head->value=20.6;  //存储值
head->next=nullptr;  //表示链表的结尾`  如何创建一个新结点，在其中存储18.8的值，并将其作为链表中的第二个结点，可以使得第二个指针来指向新分配的结点（其中将存储18.8的值）  `ListNode *secondPtr=new ListNode;
secondPtr->value=18.8;
secondPtr->next=nullptr; //第二个结点是链表的结尾
head->next=secondPtr;   //第一个结点指向第二个`  将其后继指针 ->next 设置为 ，可以使第二个结点成为链表的结尾，通过 head->next = ; 语句将链表头的后继指针改为指向第二个结点。  创建链表，并给链表进行赋值：#include 
#include 
#include
using namespace std;
struct ListNode{
    double value;
    ListNode *next;
};
int main(int argc, char** argv) {
    ListNode *head=NULL;
    head=new ListNode;
    head->value=20.6;
    head->next=NULL;
    
    ListNode *secondPtr=new ListNode;
    secondPtr->value=18.8;
    secondPtr->next=NULL;
    head->next=secondPtr;
    
    cout
[1]: https://xuan.ddwoo.top/index.php/archives/92/
[2]: https://xuan.ddwoo.top/index.php/archives/92/

相关文章