第 2 章 线性表 （设立尾指针的单循环链表（链式存储结构）实现）

1. 背景说明

循环链表(circular linked list)，是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，

整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点 。

2. 示例代码

1) status.h

/* DataStructure 预定义常量和类型头文件 */#ifndef STATUS_H
#define STATUS_H#define CHECK_NULL(pointer) if (!(pointer)) { \printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_NULL_PTR); \return NULL; \
}#define CHECK_RET(ret) if (ret != RET_OK) { \printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ret); \return ret; \
}#define CHECK_VALUE(value, ERR_CODE) if (value) { \printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_CODE); \return ERR_CODE; \
}#define CHECK_FALSE(value, ERR_CODE) if (!(value)) { \printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_CODE); \return FALSE; \
} /* 函数结果状态码 */
#define TRUE 					1			/* 返回值为真 */
#define FALSE 					0			/* 返回值为假 */
#define RET_OK 					0			/* 返回值正确 */
#define INFEASIABLE    		   	2			/* 返回值未知 */
#define ERR_MEMORY     		   	3			/* 访问内存错 */
#define ERR_NULL_PTR   			4			/* 空指针错误 */
#define ERR_MEMORY_ALLOCATE		5			/* 内存分配错 */
#define ERR_NULL_STACK			6			/* 栈元素为空 */
#define ERR_PARA				7			/* 函数参数错 */
#define ERR_OPEN_FILE			8			/* 打开文件错 */
#define ERR_NULL_QUEUE			9			/* 队列为空错 */
#define ERR_FULL_QUEUE			10			/* 队列为满错 */
#define ERR_NOT_FOUND			11			/* 表项不存在 */
typedef int Status;							/* Status 是函数的类型,其值是函数结果状态代码，如 RET_OK 等 */
typedef int Bollean;						/* Boolean 是布尔类型,其值是 TRUE 或 FALSE */#endif // !STATUS_H

2) cycleSingleList.h

/* 设立尾指针的单循环链表实现头文件 */#ifndef CYCLESINGLELINKLIST_H
#define CYCLESINGLELINKLIST_H#include "status.h"typedef int ElemType;typedef struct LNode {ElemType data;struct LNode *next;
} *LinkList;/* 操作结果：构造一个空的线性表 L */
Status InitList(LinkList *L);/* 操作结果：销毁线性表 L */
Status DestroyList(LinkList *L);/* 初始条件：线性表 L 已存在操作结果：将 L 重置为空表 */
Status ClearList(LinkList *L);/* 初始条件：线性表 L 已存在操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE */
Bollean ListEmpty(LinkList L);/* 初始条件：L 已存在操作结果：返回 L 中数据元素个数 */
int ListLength(LinkList L);/* 当第 i 个元素存在时,其值赋给 e 并返回 RET_OK, 否则返回 ERROR */
Status GetElem(LinkList L, int i, ElemType *e);/* 初始条件：线性表 L 已存在，compare() 是数据元素判定函数操作结果：返回 L 中第 1 个与 e 满足关系 compare() 的数据元素的位序若这样的数据元素不存在，则返回值为 0 */
int LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType));/* 初始条件：线性表 L 已存在操作结果：若 curr_e 是 L 的数据元素，且不是第一个，则用 pre_e 返回它的前驱否则操作失败，pre_e 无定义 */
Status PriorElem(LinkList L, ElemType curr_e, ElemType *pre_e);/* 初始条件：线性表 L 已存在操作结果：若 curr_e 是 L 的数据元素, 且不是最后一个,则用 next_e 返回它的后继否则操作失败，next_e 无定义 */
Status NextElem(LinkList L, ElemType curr_e, ElemType *next_e);/* 在 L 的第 i 个位置之前插入元素 e */
Status ListInsert(int i, ElemType e, LinkList *L);/* 删除 L 的第 i 个元素,并由 e 返回其值 */
Status ListDelete(int i, LinkList *L, ElemType *e);/* 初始条件: L 已存在操作结果: 依次对 L 的每个数据元素调用函数 vi()。一旦 vi() 失败,则操作失败 */
Status ListTraverse(LinkList L, void(*vi)(ElemType));#endif // !CYCLESINGLELINKLIST_H

3) cycleSingleLink.c

/* 设立尾指针的单循环链表实现源文件 */#include "cycleSingleLinkList.h"
#include <stdio.h>
#include <stdlib.h>/* 辅助函数，创建一个新的节点 */
static LinkList MakeNewLNode(ElemType e)
{LinkList newLNode = (LinkList)malloc(sizeof(struct LNode));CHECK_NULL(newLNode)newLNode->data = e;newLNode->next = NULL;return newLNode;
}/* 操作结果：构造一个空的线性表 L */
Status InitList(LinkList *L)
{*L = (LinkList)malloc(sizeof(struct LNode));CHECK_VALUE(!(*L), ERR_MEMORY_ALLOCATE)(*L)->next = *L;return RET_OK;
}/* 操作结果：销毁线性表 L, *L 指的是尾指针 */
Status DestroyList(LinkList *L)
{LinkList p = (*L)->next;while (p != *L) {LinkList q = p->next;free(p);p = q;}free(*L);*L = NULL;return RET_OK;
}/* 初始条件：线性表 L 已存在操作结果：将 L 重置为空表 */
Status ClearList(LinkList *L)
{*L = (*L)->next;LinkList p = (*L)->next;while (p != *L) {LinkList q = p->next;free(p);p = q;}(*L)->next = *L;return RET_OK;
}/* 初始条件：线性表 L 已存在操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE */
Bollean ListEmpty(LinkList L)
{return (L->next == L) ? TRUE : FALSE;
}/* 初始条件：L 已存在操作结果：返回 L 中数据元素个数 */
int ListLength(LinkList L)
{int length = 0;LinkList p = L->next;while (p != L) {++length;p = p->next;}return length;
}/* 当第 i 个元素存在时,其值赋给 e 并返回 RET_OK, 否则返回 ERROR */
Status GetElem(LinkList L, int i, ElemType *e)
{LinkList p = L->next->next;CHECK_VALUE((i < 1 || i > ListLength(L)), ERR_PARA)int pos = 0;while (pos < i - 1) {p = p->next;++pos;}*e = p->data;return RET_OK;
}/* 初始条件：线性表 L 已存在，compare() 是数据元素判定函数操作结果：返回 L 中第 1 个与 e 满足关系 compare() 的数据元素的位序若这样的数据元素不存在，则返回值为 0 */
int LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType))
{LinkList p = L->next->next;int pos = 0;while (p != L->next) {++pos;if (compare(p->data, e)) {return pos;}p = p->next;}return 0;
}/* 初始条件：线性表 L 已存在操作结果：若 curr_e 是 L 的数据元素，且不是第一个，则用 pre_e 返回它的前驱否则操作失败，pre_e 无定义 */
Status PriorElem(LinkList L, ElemType curr_e, ElemType *pre_e)
{LinkList p = L->next->next;LinkList q = p->next;while (q != L->next) {if (q->data == curr_e) {*pre_e = p->data;return TRUE;}p = q;q = q->next;}return FALSE;
}/* 初始条件：线性表 L 已存在操作结果：若 curr_e 是 L 的数据元素, 且不是最后一个,则用 next_e 返回它的后继否则操作失败，next_e 无定义 */
Status NextElem(LinkList L, ElemType curr_e, ElemType *next_e)
{LinkList p = L->next->next;while (p != L) {if (p->data == curr_e) {*next_e = p->next->data;return TRUE;}p = p->next;}return FALSE;
}/* 在 L 的第 i 个位置之前插入元素 e */
Status ListInsert(int i, ElemType e, LinkList *L)
{CHECK_VALUE((i < 1 || i > ListLength(*L) + 1), ERR_PARA)LinkList p = (*L)->next;int pos = 0;while (pos < i - 1) {++pos;p = p->next;}LinkList newLNode = MakeNewLNode(e);CHECK_VALUE(!newLNode, ERR_MEMORY_ALLOCATE)newLNode->next = p->next;p->next = newLNode;if (p == *L) {*L = newLNode;}return RET_OK;
}/* 删除 L 的第 i 个元素,并由 e 返回其值 */
Status ListDelete(int i, LinkList *L, ElemType *e)
{LinkList p = (*L)->next;CHECK_VALUE((i < 1 || i > ListLength(*L)), ERR_PARA)int pos = 0;while (pos < i - 1) {++pos;p = p->next;}LinkList q = p->next;p->next = q->next;*e = q->data;if (q == *L) {*L = p;}free(q);return RET_OK;
}/* 初始条件: L 已存在操作结果: 依次对 L 的每个数据元素调用函数 vi()。一旦 vi() 失败,则操作失败 */
Status ListTraverse(LinkList L, void(*vi)(ElemType))
{LinkList p = L->next->next;while (p != L->next) {vi(p->data);p = p->next;}return RET_OK;
}

4) algorithm.h

/* 算法定义头文件 */
#ifndef ALGORITHM_H
#define ALGORITHM_H#include "cycleSingleLinkList.h"/* 算法，合并两个已知尾指针的循环链表 */
Status MergeList(const LinkList Lb, LinkList *La);#endif // !ALGORITHM_H

5) algorithm.c

/* 算法实现源文件 */#include "algorithm.h"
#include <stdio.h>
#include <stdlib.h>/* 算法，合并两个已知尾指针的循环链表 */
Status MergeList(const LinkList Lb, LinkList *La)
{CHECK_VALUE(ListEmpty(Lb), ERR_NULL_PTR)CHECK_VALUE(ListEmpty(*La), ERR_NULL_PTR)LinkList p = (*La)->next;(*La)->next = Lb->next->next;free(Lb->next);Lb->next = p;*La = Lb;return RET_OK;
}

6) main.c

/* 入口程序源文件 */#include "cycleSingleLinkList.h"
#include "algorithm.h"
#include <stdio.h>void Visit(ElemType e);
Status Compare(ElemType e1, ElemType e2);int main(void)
{LinkList L;Status ret = InitList(&L);CHECK_RET(ret)printf("LinkList L is %s\n", (ListEmpty(L) == TRUE) ? "empty" : "not empty");ListInsert(1, 3, &L);ListInsert(2, 5, &L);ElemType e;GetElem(L, 1, &e);printf("The length of L is %d, the value of 1th element is %d\n", ListLength(L), e);printf("The elements in L is: ");ListTraverse(L, Visit);putchar('\n');PriorElem(L, 5, &e);printf("The previous element of 5 is %d\n", e);NextElem(L, 3, &e);printf("The next element of 3 is %d\n", e);printf("LinkList L is %s\n", (ListEmpty(L) == TRUE) ? "empty" : "not empty");ret = LocateElem(L, 5, Compare);if (ret) {printf("The %dth element of L is %d\n", ret, 5);} else {printf("The element 5 is not exist in L.\n");}printf("Delete the 2th element of L\n");ret = ListDelete(2, &L, &e);if (ret == RET_OK) {printf("The element deleted is %d, Now the elements in L is: ", e);ListTraverse(L, Visit);putchar('\n');} else {printf("Delete element failed!\n");}printf("Clear L %s\n", (ClearList(&L) == RET_OK) ? "success" : "not success");printf("Now L is %s\n", (ListEmpty(L) == TRUE) ? "empty" : "not empty");printf("Destroy L %s\n", (DestroyList(&L) == TRUE) ? "success" : "not success");/* Algorithm Test */LinkList La, Lb;InitList(&La);InitList(&Lb);for (int i = 0; i < 5; ++i) {ListInsert(i + 1, i + 1, &La);ListInsert(i + 1, (i + 1) * 2, &Lb);}printf("After initialize La, La is: ");ListTraverse(La, Visit);putchar('\n');printf("After initialize Lb, Lb is: ");ListTraverse(Lb, Visit);putchar('\n');MergeList(Lb, &La);printf("After merge La and Lb, La is: ");ListTraverse(La, Visit);putchar('\n');DestroyList(&La);return 0;
}void Visit(ElemType e)
{printf("%d ", e);
}Status Compare(ElemType e1, ElemType e2)
{return (e1 == e2) ? TRUE : FALSE;
}

3. 输出示例

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

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

相关文章

Visual Studio 新建类从默认internal改为public

Visual Studio 新建类从默认internal改为public

前言 之前一直用的Resharp辅助编写C#代码&#xff0c;Resharp用起来的确方便不少&#xff0c;但是太消耗开发机内存了。重装电脑后&#xff0c;还是决定使用Visual Studio内置的功能。 默认情况下&#xff0c;Visual Studio 中生成一个类或接口是internal类型的&#xff0c;而…
阅读更多...
大学大创项目：手机室内AR导航APP项目思路

大学大创项目：手机室内AR导航APP项目思路

文章目录 一、最初的项目思路二、建图和定位分离的项目思路1、建图2、定位 个人见解&#xff0c;如有错误&#xff0c;请多包涵 一、最初的项目思路 在大创项目的开始&#xff0c;将手机确定为应用设备&#xff0c;传感器确定为相机。 由于知识储备的原因&#xff0c;在头一次…
阅读更多...
Shell常用的几个正则表达式:[:alnum:], [:alpha:], [:upper:], [:lower:], [:digit:] 认知

Shell常用的几个正则表达式:[:alnum:], [:alpha:], [:upper:], [:lower:], [:digit:] 认知

一&#xff1a;通配符命令简介&#xff1a; 匹配符合相关条件的符号&#xff0c;匹配文件名查找。 通配符类型&#xff1a; *&#xff1a;匹配任意长度的任意字符 &#xff1f;&#xff1a;匹配任意单个字符 []&#xff1a;匹配指定范围内的任意单个字符 [^]&#xff1a;匹配指…
阅读更多...
解决deepspeed框架的bug：不保存调度器状态，模型训练重启时学习率从头开始

解决deepspeed框架的bug：不保存调度器状态，模型训练重启时学习率从头开始

deepspeed存在一个bug&#xff0c;即在训练时不保存调度器状态&#xff0c;因此如果训练中断后再重新开始训练&#xff0c;调度器还是会从头开始而不是接着上一个checkpoint的调度器状态来训练。这个bug在deepspeed的github中也有其他人提出&#xff1a;https://github.com/mic…
阅读更多...
ResNet 09

ResNet 09

一、发展 1989年&#xff0c;Yann LeCun提出了一种用反向传导进行更新的卷积神经网络&#xff0c;称为LeNet。 1998年&#xff0c;Yann LeCun提出了一种用反向传导进行更新的卷积神经网络&#xff0c;称为LeNet-5 AlexNet是2012年ISLVRC 2012&#xff08;ImageNet Large Sca…
阅读更多...
MySQL——备份和还原

MySQL——备份和还原

备份 热备 即MySQL服务在运行的时候进行的备份 mysqldump命令 mysqldump --databases db1 db2 db3 > dump.sql mysqldump -uroot -pSanchuang1234# --all-databases >all_db.sql mysqldump -uroot -pSanchuang123# --databases TENNIS >/backup/tennis.sql mysq…
阅读更多...
Always On 数据库无法自动同步的问题

Always On 数据库无法自动同步的问题

问题&#xff1a; 在给客户的SQL Server 2019 配置好Always On 之后&#xff0c;不久就出现高可用组里的一个库无法正常同步。 第一次出现&#xff0c;以为是偶发性问题&#xff0c;直接右键点击恢复数据同步&#xff0c;没一会就同步好了&#xff1b;过了一个月问题又出现了…
阅读更多...
高云USB下载器仿真器用户手册（包括在线逻辑分析仪的使用方法）

高云USB下载器仿真器用户手册（包括在线逻辑分析仪的使用方法）

高云 USB 仿真器用户手册 一.简介 仿真器用于高云 GOWIN 公司所生产的 FPGA&#xff0c;可用于程序下载和调试。主要特点如下&#xff1a; 1.支持宽电压1.2V - 3.6V&#xff1b; 2.速度最高可达30Mb/s&#xff0c;极速完成下载和波形调试功能&#xff1b; 3.完美支持在线逻…
阅读更多...
【个人博客系统网站】项目的发布 · 通过公网IP访问我们的网站 · 思考总结

【个人博客系统网站】项目的发布 · 通过公网IP访问我们的网站 · 思考总结

【JavaEE】进阶 个人博客系统&#xff08;6&#xff09; 文章目录 【JavaEE】进阶 个人博客系统&#xff08;6&#xff09;1. 项目发布1.1 后端代码修改1.1.1 数据库密码1.1.2 端口号修改1.1.3 文件保存地址修改1.1.4 静态资源映射修改 1.2 云服务器1.2.1 建库建表1.2.2 必要…
阅读更多...
自动化驱动程序管理

自动化驱动程序管理

在部署操作系统时&#xff0c;每次都从下载和分发所需的驱动程序中实现真正的独立性可能是一场艰苦的战斗。特别是具有硬件多样化的环境&#xff0c;并且需要支持新的硬件类型时。借助 OS Deployer&#xff0c;可以对所有端点使用一个映像&#xff0c;无论品牌和型号如何&#…
阅读更多...
使用maven idea环境

使用maven idea环境

目录 idea三种方式执行maven命令 工程导入 生命周期lifecycle 插件和目标 常用命令 创建模块工程后 idea三种方式执行maven命令 想在哪个工程模块上执行就点开哪一个 如果觉得双击完clean再双击install麻烦&#xff0c;可以 如果有需要还可以给命令后面加参数 ​​​ 第三种…
阅读更多...
C# 共享项目的应用

C# 共享项目的应用

概述 共享项目也可以称为共享资产项目，它允许在多个目标项目之间共享的代码。 它支持编译器指令，可以有条件地包含特定于平台的代码，以便编译为引用共享项目的项目的子集。 还有 IDE 支持，可帮助管理编译器指令并直观显示代码在每个应用程序中的外观。 什么是共享项目？ …
阅读更多...
XL-LightHouse 与 Flink 和 ClickHouse 流式大数据统计系统

XL-LightHouse 与 Flink 和 ClickHouse 流式大数据统计系统

一个Flink任务只能并行处理一个或少数几个数据流&#xff0c;而XL-LightHouse一个任务可以并行处理数万个、几十万个数据流&#xff1b; 一个Flink任务只能实现一个或少数几个数据指标&#xff0c;而XL-LightHouse单个任务就能支撑大批量、数以万计的数据指标。 1、XL-LightHo…
阅读更多...
Excel文件生成与下载（SpringBoot项目）（easypoi）

Excel文件生成与下载（SpringBoot项目）（easypoi）

说明 通过接口&#xff0c;导出表格。 使用SpringBoot框架和easypoi表格解析框架&#xff0c;生成Excel表格&#xff0c;并通过接口下载。 表格示例 依赖 版本 <easypoi.version>4.4.0</easypoi.version>依赖 <!-- easypoi --> <dependency><…
阅读更多...
springboot整合mybatisPlus全技巧（2-常用开发技巧：通用字段插入）

springboot整合mybatisPlus全技巧（2-常用开发技巧：通用字段插入）

本系列专题基于 springboot 整合 mybatisPlus 的各种文章早已烂大街的背景下&#xff0c;根据 整合过程&#xff0c;MP开发中的常见技巧&#xff0c;MP开发中遇到的各种坑 三个方面&#xff0c;来对这一专题做一个全面且实用的总结&#xff0c;基本上只要你吃透这篇文章&#x…
阅读更多...
Linux mac Windows三系统 局域网文件共享方法

Linux mac Windows三系统 局域网文件共享方法

主要工具&#xff1a; Samba是一个开源的软件套件&#xff0c;允许Linux系统与Windows系统之间共享文件和打印机。 一、首先是Linux共享的设置 ①安装 sudo apt-get install samba ②创建共享文件夹 sudo mkdir /home/share ③配置用户 sudo smbpasswd -a kequan ④修改…
阅读更多...
Java智慧工地信息化管理平台源码，依托计算机信息、网络通讯、物联网、系统集成及云计算技术建立

Java智慧工地信息化管理平台源码，依托计算机信息、网络通讯、物联网、系统集成及云计算技术建立

Java智慧工地源码 智慧工地APP源码 系统定义&#xff1a; 智慧工地信息化管理平台是依托计算机信息、网络通讯、物联网、系统集成及云计算技术&#xff0c;通过数据采集、信息动态交互、智能分析&#xff0c;建立起来的一套集成的项目建设综合管理系统。实现项目管理信息化、网…
阅读更多...
图像噪声--添加噪声

图像噪声--添加噪声

椒盐噪声 椒盐噪声就是给图片添加黑白噪点&#xff0c;椒指的是黑色的噪点(0,0,0),盐指的是白色的噪点(255,255,255)&#xff0c;通过num来控制噪声多少&#xff0c;值越大添加的噪声越多&#xff0c;图像损坏的更加严重。 void add_salt_pepper_noise(Mat& src,Mat& …
阅读更多...
淘宝双11数据分析与预测课程案例中（林子雨）错误点总结

淘宝双11数据分析与预测课程案例中（林子雨）错误点总结

问题一&#xff1a;可视化代码中男女买家各个年龄段对比散点图中数值不显示以及坐标不正确问题如下图 解决方法&#xff1a; 1修改坐标 2修改数值 修改后散点图 问题二&#xff1a;各省份的总成交量对比中地图显示不出来 有时间再写
阅读更多...
JavaScript中的原型链（prototype chain）

JavaScript中的原型链（prototype chain）

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ JavaScript中的原型链⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅&#xff01;这个专栏是为那些对Web开发感兴趣、刚刚踏…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023