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

数据结构与算法学习笔记之线性表五---循环链表的表示和实现(C++)

目录

前言

1.双向链表的定义

2.双向链表的表示和实现

1.定义

2.初始化

3.销毁

4.清空

5.表长

6.获取数据元素

7.前驱节点

8.后继节点

9.插入

10.删除

11.遍历

12.完整代码


前言

        记录下双向链表的表示和实现。

1.循环链表的定义

        循环链表(circular linked list)是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。由此,从表中任一结点出发均可找到表中其他结点,如图 2.12所示为单链的循环链表。类似地,还可以有多重链的循环链表。。

2.循环链表的表示和实现

1.定义

typedef int Status;
typedef int ElemType;
// 定义循环链表
typedef struct CircularNode {ElemType data; // 数据域struct CircularNode * next; // 直接后继
}CircularNode,*CircularLinkedList;

2.初始化

        初始化双向链表,next指针指向自己。

// 初始化循环链表
Status initCircularLinkedList(CircularLinkedList &circularLinkedList){circularLinkedList = new CircularNode;if (!circularLinkedList) {//内存分配失败return 0;}circularLinkedList->next = circularLinkedList; // 将头节点的指针指向自身,形成循环return 1;
}

3.销毁

// 循环链表销毁
void destroyCircularLinkedList(CircularLinkedList &circularLinkedList) {if (!circularLinkedList) {return; // 链表为空,无需销毁}CircularLinkedList current = circularLinkedList->next; // 从第一个节点开始while (current != circularLinkedList) { // 遍历至头节点CircularLinkedList temp = current; // 暂存当前节点current = current->next; // 移动到下一个节点delete temp; // 释放当前节点内存}delete circularLinkedList; // 释放头节点内存circularLinkedList = nullptr; // 头指针置为空
}

4.清空

// 循环链表清空
void clearCircularLinkedList(CircularLinkedList &circularLinkedList) {if (!circularLinkedList) {return; // 链表为空,无需清空}CircularLinkedList current = circularLinkedList->next; // 从第一个节点开始while (current != circularLinkedList) { // 遍历至头节点CircularLinkedList temp = current; // 暂存当前节点current = current->next; // 移动到下一个节点delete temp; // 释放当前节点内存}circularLinkedList->next = circularLinkedList; // 头节点的 next 指针指向自身,链表置为空链表
}

5.表长

// 循环链表表长
int getCircularLinkedListLength(CircularLinkedList &circularLinkedList) {int length = 0;CircularNode *p = circularLinkedList->next; // 从第一个节点开始计数while (p != circularLinkedList) { // 当指针指向头节点时结束循环++length;p = p->next;}return length;
}

6.获取数据元素

// 获取循环链表中的元素
Status getCircularLinkedListElement(CircularLinkedList &circularLinkedList, int position, int *element) {if (position < 1 || position > getCircularLinkedListLength(circularLinkedList)) { // 非法位置return 0;}CircularNode *p = circularLinkedList->next; // 从第一个节点开始遍历int index = 1;while (index < position) { // 定位到指定位置p = p->next;index++;}*element = p->data; // 将节点的数据域值赋给 elementreturn 1;
}

7.前驱节点

// 获取循环链表中的第一个与element相同的元素的直接前驱
Status priorCircularLinkedListElement(CircularLinkedList &circularLinkedList, int element, int *priorElement) {if (isCircularLinkedListEmpty(circularLinkedList)) { // 空链表return 0;}CircularNode *p = circularLinkedList->next;CircularNode *pre = circularLinkedList; // 前驱节点do {if (p->data == element) { // 找到要查找的节点*priorElement = pre->data;return 1;}pre = p;p = p->next;} while (p != circularLinkedList->next); // 循环直到回到起始节点return 0; // 未找到相同元素
}

8.后继节点

        先判断循环链表是否是空链表,然后遍历删除节点。

// 获取循环链表中的第一个与element相同的元素的后继节点
Status nextCircularLinkedListElement(CircularLinkedList &circularLinkedList, int element, int *nextElement) {if (isCircularLinkedListEmpty(circularLinkedList)) { // 空链表return 0;}CircularNode *p = circularLinkedList->next;do {if (p->data == element) { // 找到要查找的节点*nextElement = p->next->data;return 1;}p = p->next;} while (p != circularLinkedList->next); // 循环直到回到起始节点return 0; // 未找到相同元素
}

9.插入

         首先判断插入位置是否合法,然后分别处理头结点和非头结点的情况。

// 循环链表插入
Status insertCircularLinkedList(CircularLinkedList &circularLinkedList, int i, int element) {if (i < 1) { // 插入位置非法return 0;}CircularNode *newNode = new CircularNode; // 新节点if (!newNode) { // 内存分配失败return 0;}newNode->data = element;if (i == 1) { // 插入到表头if (circularLinkedList == nullptr) { // 空链表newNode->next = newNode; // 自己指向自己circularLinkedList = newNode;} else {CircularNode *last = circularLinkedList;while (last->next != circularLinkedList) { // 找到最后一个节点last = last->next;}newNode->next = circularLinkedList; // 新节点指向表头last->next = newNode; // 最后一个节点指向新节点circularLinkedList = newNode; // 更新表头指针}} else { // 插入到非表头位置CircularNode *p = circularLinkedList;int j = 1;while (p->next != circularLinkedList && j < i - 1) { // 找到插入位置的前一个节点p = p->next;++j;}if (j < i - 1) { // 插入位置超出链表长度delete newNode;return 0;}newNode->next = p->next; // 新节点指向原来位置节点p->next = newNode; // 前一个节点指向新节点}return 1;
}

10.删除

        首先判断删除位置是否合法,然后分别处理头结点和非头结点的情况。

// 循环链表删除
Status deleteCircularLinkedList(CircularLinkedList &circularLinkedList, int position, ElemType *deletedElement) {if (position < 1 || circularLinkedList == nullptr) { // 删除位置非法或链表为空return 0;}if (position == 1) { // 删除表头节点CircularNode *temp = circularLinkedList;*deletedElement = temp->data; // 存储被删除节点的数据if (circularLinkedList->next == circularLinkedList) { // 链表只有一个节点delete temp;circularLinkedList = nullptr;} else {CircularNode *last = circularLinkedList;while (last->next != circularLinkedList) { // 找到最后一个节点last = last->next;}last->next = circularLinkedList->next; // 最后一个节点指向第二个节点circularLinkedList = circularLinkedList->next; // 更新表头指针delete temp; // 释放被删除节点的内存}} else { // 删除非表头节点CircularNode *p = circularLinkedList;int j = 1;while (p->next != circularLinkedList && j < position - 1) { // 找到要删除节点的前一个节点p = p->next;++j;}if (j < position - 1 || p->next == circularLinkedList) { // 删除位置超出范围return 0;}CircularNode *temp = p->next; // 要删除的节点*deletedElement = temp->data; // 存储被删除节点的数据p->next = temp->next; // 前一个节点指向后一个节点delete temp; // 释放被删除节点的内存}return 1;
}

11.遍历

        遍历循环链表

// 遍历循环链表
void traverseCircularLinkedList(CircularLinkedList &circularLinkedList) {if (circularLinkedList == nullptr) { // 空链表return;}CircularNode *p = circularLinkedList;do {cout << p->data << "\t"; // 输出当前节点的数据p = p->next; // 移动到下一个节点} while (p != circularLinkedList); // 循环直到回到起始节点cout << endl;
}

12.测试代码

void  testCircularLinkedList(void) {CircularLinkedList circularLinkedList;cout<<"\n**********\t循环链表初始化\t**********"<<endl;if (initCircularLinkedList(circularLinkedList)) {cout<<"顺序表初始化成功"<<endl;}cout<<"\n**********\t循环链表判空和长度计算\t**********"<<endl;if (isCircularLinkedListEmpty(circularLinkedList)) {cout<<"循环链表为空,长度为"<<getCircularLinkedListLength(circularLinkedList)<<endl;}cout<<"\n**********\t循环链表插入测试\t**********"<<endl;for (int i = 1; i <=11 ; i++) {if (insertCircularLinkedList(circularLinkedList,i, i)) {cout<<"数据元素"<<i<<"插入成功"<<endl;}else{cout<<"数据元素"<<i<<"插入失败"<<endl;}}traverseCircularLinkedList(circularLinkedList);cout<<"\n**********\t循环链表根据下标获取数据元素测试\t**********"<<endl;for (int i = 0; i <= 12 ; i++) {int element;if (getCircularLinkedListElement(circularLinkedList,i, &element)) {cout<<"第"<<i<<"个数据元素为"<<element<<endl;}else{cout<<"第"<<i<<"个数据元素不存在"<<endl;}}cout<<"插入之后的循环链表"<<endl;traverseCircularLinkedList(circularLinkedList);cout<<"\n**********\t循环链表删除测试\t**********"<<endl;ElemType element;if (deleteCircularLinkedList(circularLinkedList, 11, &element)){cout<<"数据元素"<<element<<"删除成功"<<endl;}cout<<"删除之后的循环链表"<<endl;traverseCircularLinkedList(circularLinkedList);cout<<"\n**********\t循环链表后继节点测试\t**********"<<endl;int nextArr[3] = {1,8,11};for (int i = 0; i < 3; i++) {ElemType nextElement;if (nextCircularLinkedListElement(circularLinkedList, nextArr[i], &nextElement)) {cout<<"数据元素"<<nextArr[i]<<"后继节点为:"<<nextElement<<endl;}else{cout<<"数据元素"<<nextArr[i]<<"后继节点不存在"<<endl;}}cout<<"\n**********\t循环链表前驱节点测试\t**********"<<endl;int priorArr[3] = {8,11,1};for (int i = 0; i < 3; i++) {ElemType priorElement;if (priorCircularLinkedListElement(circularLinkedList, priorArr[i], &priorElement)) {cout<<"数据元素"<<priorArr[i]<<"前驱节点为"<<priorElement<<endl;}else{cout<<"数据元素"<<priorArr[i]<<"前驱节点不存在"<<endl;}}cout<<"\n**********\t循环链表销毁\t**********"<<endl;destroyCircularLinkedList(circularLinkedList);cout<<"循环链表销毁"<<endl;}
http://www.lryc.cn/news/348311.html

相关文章:

  • 微信小程序生命周期揭秘:从启动到消亡的全过程剖析【附代码】
  • Linux 下载 miniconda
  • 第十五篇:全面防护:构建不容侵犯的数据库安全策略与实战指南
  • 电脑快速搜索文件及文件夹软件——Everything
  • 02-登录页面、动态路由、权限等模块开发
  • 万物生长大会 | 创邻科技再登杭州准独角兽榜单
  • (六)Linux的Shell编程(上)
  • CANopen总线_CANOpen开源协议栈
  • Rust 语言不支持 goto 语句
  • uniapp日期区间选择器
  • k8s job
  • Python---NumPy万字总结【此篇文章内容难度较大,线性代数模块】(3)
  • 【面试经典题】环形链表
  • 【联合索引】最左匹配原则是什么?
  • LeetCode 700.二叉搜索树中的搜索
  • 程序设计实践-课程设计任务布置(麦当劳) (price 200)(不包含文档)
  • leetcode 918.环形子数组的最大和
  • Spring中用到的设计模式有哪些
  • CSS 样式清单整理:文字超出部分显示省略号和设置placeholder的字体样式
  • Docker容器:Docker-Consul 的容器服务更新与发现
  • 容器化Jenkins远程发布java应用(方式二:自定义镜像仓库远程拉取构建)
  • 解密某游戏的数据加密
  • 【报错合集】完美解决“虚拟机使用的是此版本 VMware Workstation 不支持的硬件版本”
  • YOLOv8小白中的小白安装环境教程!没一个字废话,看一遍不踩坑!
  • C#正则表达式,提取信息使用
  • 【数据结构】详解队列
  • 大模型微调方法汇总
  • 探究NVMe SSD HMB应用场景与影响-<续>
  • YTU 3166 共享单车 DFS 记忆化搜索
  • RAG应用中的路由模式