2025年c++单向链表（c++单向链表的创建）

编程日记 • 2025-04-25 19:40 • 阅读 71

提示：以下是本篇文章正文内容

当需要建立一个学生信息表,学生的人数无法确定而且人数经常变化,此时若用顺序表来实现将会很麻烦

在这里插入图片描述

单链表:线性表的链接存储结构, 用一组任意(不联系, 零散分布) 的存储单元存放线性表的元素.

存储特点:
1.逻辑次序和物理次序不一定相同

2.元素之间的逻辑关系用指针表示

如(a1, a2 ,a3, a4)存储在内存中
在这里插入图片描述

结点结构

单链表是由若干结点构成的, 结点包含数据域和指针域在这里插入图片描述

data: 存储数据元素
next: 存储指向后继结点的地址

申请一个结点

在这里插入图片描述
结点建立之后,
引用数据元素: (*p).data <==> p->data
引用指针元素: p->next

链表(a1, a2, a3, a4)
在这里插入图片描述

头指针:指向第一个结点的地址

尾标志:终端节点的指针域为空

首元结点:链表第一个数据结点

头节点: 在单链表的第一个元素结点之前附设一个类型相同的结点, 以便空表和非空表的处理统一
在这里插入图片描述
注:头节点的数据域一般为空, 指针域指向第一个节点

接口操作: void displayNode(Link head);

操作接口:int length(Link head);
在这里插入图片描述
伪代码:
1.工作指针p初始化, 累加器count初始化

2.重复执行下述操作, 直到p为空;

3.返回累加器count的值

操作接口:bool queryNode(Link head, int x);

思路: 依次遍历链表的数据域与要查找的数据进行比较

操作接口:bool insertNode(Link head, int index, int item);

思路:
在这里插入图片描述
插入到第i个结点, 先找到第i-1 个节点, 然后, 让插入结点的指针域指向i-1个结点的指向的指针域, 再修改第i-1结点的指针域, 使其指向插入结点. 注意, 修改指针指向的顺序不要颠倒, 不然会导致找不到第i个结点. 对于边界情况也同样适合.

伪代码
1.工作指针p初始化
2.查找第i-1个结点, 并使该指针p指向该结点
3.若查找不成功,则返回false
否则:

3.1生成一个元素值为x的新结点node
3.2将新结点插入到p所指向的结点
3.3返回true

操作接口:Link newList(const int a[],int n);
头插法:将待插入的结点插在头节点的后面,插入顺序最终相反
在这里插入图片描述

这与链表插入一样的, 若以数组传入参数, 则生成的链表的数据则与数组的数据刚好相反

操作接口:Link new_List(const int a[],int n);
尾插法:将待插入结点插在终端结点的后面
在这里插入图片描述

操作接口:bool deleteNode(Link head,DateType x);

思路:
引入两个指针p,q, p指向要删除的结点, q指向要删除结点的前一个结点
在这里插入图片描述
找到要删除的结点, 用free()函数释放该节点, 并修改删除结点两边指针关系情况,
要保证p,q指针一前一后: 在插在过程中, 若发现结点p指向的数据域不等于x, 则p,q指针同时向前移动即可

若在查找过程一直没有找到要删除的结点(链表遍历完毕),则退出循环,返回错误

操作接口:void clearLink(Link head)
将单链表中所有结点存储空间释放, 要保证链表末处理的部分不断开
在这里插入图片描述

将单链表的首尾相接，将终端结点的指针域由空指针改为指向头节点，构成单循环链表，简称循环链表。
在这里插入图片描述

循环链表没有明显的尾端，如何避免死循环？

单链表---->循环链表

在单链表的每个结点中再设置一个指向其前驱节点的指针域
在这里插入图片描述
data: 数据域，存储数据元素
prior: 指针域，存储该结点的前驱结点地址
next：指针域，存储该结点的后继结点地址

在这里插入图片描述

提示：这里对文章进行总结：