数据结构（C语言）代码实现（六）——单链表的实现

目录

参考、格式

头文件LinkList.h

一、将函数的小括号写成中括号

二、读取权限冲突

三、L->Last指针没有移动

四、函数指针的使用

头文件完整代码

测试函数（主函数）test.cpp

测试结果

参考、格式

数据结构课本2.3节（严蔚敏版）

头文件LinkList.h

由于本部分函数过多，这里只介绍自己在实现过程中出现的问题。

一、将函数的小括号写成中括号

E0254 不允许使用类型名-CSDN博客

二、读取权限冲突

C++读取访问权限冲突引发异常问题_引发了异常: 读取访问权限冲突。-CSDN博客

没有记录错误代码，不过编码过程中多次出现过这个问题，原因是指针未初始化（特别是函数内部）

三、L->Last指针没有移动

//算法2.20 插入元素 改编自算法2.9
Status List_Insert_L(LinkList& L, int i, ElemType e) {
	//在带头结点的单链线性表L的第i个元素之前插入元素e，1<=i<=L->len
	//更准确的说法是在第i个结点之后（包括头结点）插入结点。
	Link s = NULL, h = NULL;
	if (!LocatePos(L, i - 1, h))return ERROR;//i值不合法
	if (!MakeNode(s, e))return ERROR;//结点存储分配失败
	InsFirst(h, s);//对于从第i个结点开始的链表，第i-1个结点是它的头结点
	//基于课本中的这句注释，我觉得要实现的线性链表头结点和首元结点不一致
	if (i > L->len)L->tail = s;//若增加的结点位于尾部，应修改尾指针
	L->len++;//InsFirst函数没有让记录元素个数的变量增加
	return OK;
}

四、函数指针的使用

函数指针和指针函数用法和区别-CSDN博客

头文件完整代码

#pragma once
#include <cstdio>
#include <cstdlib>
#include <cstring>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;//Status是函数的类型，其值是函数结果状态代码
typedef int ElemType;

//-----线性链表的存储结构---------
//-----实现单向非循环动态链表-----
//-----头结点与首元结点不一致-----
typedef struct LNode {//结点类型
	ElemType data;
	struct LNode* next;
}LNode,*Link,*Position;

typedef struct LinkNode{      //链表类型
	Link head, tail;  //分别指向线性链表中的头结点和最后一个结点
	int len;          //指示线性链表中数据元素的个数
}LinkNode,*LinkList;

Status MakeNode( Link & p,ElemType e ){
	//分配由p指向的值为e的结点，并返回OK；若分配失败，则返回ERROR
	p = (Link)malloc(sizeof(LNode));
	if (!p)
		return ERROR;
	p->data = e;
	return OK;
}
void FreeNode(Link& p) {//相当于free函数重命名
	//释放p所指结点
	free(p);
    p = NULL;
}

Status InitList(LinkList& L) {
	//构造一个空的线性链表L
	L = (LinkList)malloc(sizeof(LinkNode));
	if (!L)return ERROR;
	L->head = L->tail = (Link)malloc(sizeof(LNode));
	if (!L->head)return ERROR;
	L->head->data = 0;
	L->head->next = NULL;
	L->len = 0;
	return OK;
}

Status DestroyList(LinkList& L) {
	//销毁线性链表L，L不再存在
	Link p;
	while (L->head) {//删除所有结点
		p = L->head;
		L->head = L->head->next;
		free(p);
	}
	free(L);
	L = NULL;
	return OK;
}

Status ClearList(LinkList& L) {
	//将线性链表L重置为空表，并释放原链表的结点空间
	Link p = L->head;
	while (L->head->next) {//保留一个结点，让其作为头结点
		p = L->head->next;
		L->head->next = p->next;
		free(p);
	}
	L->tail = L->head;
	L->len = 0;
	return OK;
}

Status InsFirst(Link h, Link s) {
	//已知h指向线性链表的头结点，将s所指结点插入到首元结点之前
	s->next = h->next;
	h->next = s;
	//这个函数没修改L->len的值，课本算法2.20需要补充L->len++。
	return OK;
}

Status DelFirst(Link h, Link& q) {
	//已知h指向线性链表的头结点，删除链表中的首元结点并以q返回
	q = h->next;
	h->next = q->next;
	q->next = NULL;
	return OK;
}

Status Append(LinkList& L, Link s) {
	//将指针s所指(彼此以指针相链)的一串结点链接在线性链表L的最后一个结点(用L->tail寻找)
	//之后，并改变链表L的尾指针指向新的尾结点
	while (s) {
		L->tail->next = s;
		L->tail = s;
		L->len++;
		s = s->next;
	}
	return OK;
}

Status Remove(LinkList& L, Link& q) {
	//删除线性链表L中的尾节点并以q返回，改变链表L的尾指针指向新的尾结点
	if (!L->tail)return ERROR;
	Link p = L->head;
	while (p->next != L->tail)
		p = p->next;//寻找尾结点的上一个结点
	q = L->tail;
	L->tail = p;//改变尾结点
	L->tail->next = NULL;
	L->len--;
	return OK;
}

Status InsBefore(LinkList& L, Link& p, Link s) {
	//已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之前
	//并修改指针p指向新插入的结点
	Link q = L->head;
	while (q->next != p)
		q = q->next;//寻找结点q的上一个结点
	q->next = s;
	s->next = p;//插入s
	p = s;//修改指针p
	L->len++;
	return OK;
}

Status InsAfter(LinkList& L, Link& p, Link s) {
	//已知p指向线性链表L中的一个结点，将s所指的结点插入在p所指结点之后
	//并修改指针p指向新插入的结点
	s->next = p->next;
	p->next = s;
	p = s;
	L->len++;
	return OK;
}

Status SetCurElem(Link& p, ElemType e) {
	//已知p指向线性链表L中的一个结点，用e更新p所指结点中数据元素的值
	p->data = e;
	return OK;
}

ElemType GetCurElem(Link p) {
	//已知p指向线性链表L中的一个结点，返回p所指结点中数据元素的值
	return p->data;
}

Status ListEmpty(LinkList L) {
	//若线性链表L为空表，则返回TRUE，否则返回FALSE
	if (!L->len)
		return TRUE;
	else
		return FALSE;
}

int ListLength(LinkList L) {
	//返回线性链表L中元素个数
	return L->len;
}

Position GetHead(LinkList L) {
	//返回线性链表L中头结点的位置
	return L->head;
}

Position GetLast(LinkList L) {
	//返回线性链表L中尾结点的位置
	return L->tail;
}

Position PriorPos(LinkList L, Link p) {
	//已知p指向线性链表L中的一个结点，返回p所指结点中的直接前驱的位置
	//若无前驱，则返回NULL
	Link q = L->head;
	if (p == L->head)return NULL;
	while (q->next != p)
		q = q->next;
	return q;
}

Position NextPos(LinkList L, Link p) {
	//已知p指向线性链表L中的一个结点，返回p所指结点中的直接后继的位置
	//若无后继，则返回NULL
	return p->next;
}

Status LocatePos(LinkList L, int i, Link& p) {
	//返回p指示线性链表L中第i个结点的位置并返回OK，i值不合法时返回ERROR
	//头结点当作第0结点，首元结点第1个，尾结点第（L->len）个
	if (i<0 || i>L->len)return ERROR;
	int j = 0;Link q = L->head;
	while (j < i) {
		q = q->next;
		++j;//j++也一样
	}
	p = q;
	return OK;
}

//compare与visit都是函数指针，请看相关博客
Position LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType)) {
	//返回线性链表L中第1个与e满足函数compare()判定关系的元素的位置，
	//若不存在这样的元素，则返回NULL
	int i = 1;Link p = L->head->next;
	while (i <= L->len && !(*compare)(p->data, e)) {
		p = p->next;
		i++;
	}
	return p;
}

//遍历链表
Status ListTraverse(LinkList L, void (*visit)(Link)) {
	//依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。
	Link p = L->head;
	for (int i = 1;i <= L->len;i++) {
		p = p->next;
		visit(p);
	}
	printf("\n");
	return OK;
}
//上面的为线性链表的基本算法

//算法2.20 插入元素 改编自算法2.9
Status List_Insert_L(LinkList& L, int i, ElemType e) {
	//在带头结点的单链线性表L的第i个元素之前插入元素e，1<=i<=L->len
	//更准确的说法是在第i个结点之后（包括头结点）插入结点。
	Link s = NULL, h = NULL;
	if (!LocatePos(L, i - 1, h))return ERROR;//i值不合法
	if (!MakeNode(s, e))return ERROR;//结点存储分配失败
	InsFirst(h, s);//对于从第i个结点开始的链表，第i-1个结点是它的头结点
	//基于课本中的这句注释，我觉得要实现的线性链表头结点和首元结点不一致
	if (i > L->len)L->tail = s;//若增加的结点位于尾部，应修改尾指针
	L->len++;//InsFirst函数没有让记录元素个数的变量增加
	return OK;
}

//删除元素
Status List_Delete_L(LinkList& L, int i, ElemType& e) {
	Link s = NULL, h = NULL;
	if (!LocatePos(L, i - 1, h))return ERROR;//i值不合法
	if (i == L->len)L->tail = h;//若删除的结点位于尾部，应修改尾指针
	DelFirst(h, s);//对于从第i个结点开始的链表，第i-1个结点是它的头结点
	e = s->data;
	FreeNode(s);
	L->len--;
	return OK;
}

//算法2.21 合并线性表 改编自算法2.12
Status MergeList_L(LinkList& La, LinkList& Lb, LinkList& Lc, int (*compare)(ElemType, ElemType)) {
	//已知单链线性表La和Lb的元素按值非递减排列。
	//归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。
	if (!InitList(Lc))return ERROR;//存储空间分配失败
	Link ha = GetHead(La);Link hb = GetHead(Lb);//ha和hb分别指向La和Lb的头结点
	Link pa = NextPos(La, ha);Link pb = NextPos(Lb, hb);//pa和pb分别指向La和Lb中当前结点
	while (pa && pb) {//La和Lb均非空
		int a = GetCurElem(pa);int b = GetCurElem(pb);//a和b为两表中当前比较元素
		Link q = NULL;
		if ((*compare)(a, b) <= 0) {//a<=b
			DelFirst(ha, q);Append(Lc, q);pa = NextPos(La, ha);
		}
		else{//a>b
			DelFirst(hb, q);Append(Lc, q);pb = NextPos(Lb, hb);
		}
	}
	if (pa)Append(Lc, pa);//链接La中剩余结点
	else Append(Lc, pb);//链接Lb中剩余结点
	FreeNode(ha);FreeNode(hb);//释放La和Lb的头结点
	return OK;
}

测试函数（主函数）test.cpp

InBefore、InAfter、PriorPos这三个函数没有测试。

#include "LinkList.h"
Status comp(ElemType c1, ElemType c2) /* 数据元素判定函数(平方关系) */
{
    if (c1 == c2 * c2)
        return TRUE;
    else
        return FALSE;
}

int compare(ElemType a, ElemType b) /*数据元素判定函数(大小关系)*/
{
    return a - b;
}

void visit(Link p) /* ListTraverse()调用的函数(类型要一致) */
{
    printf("%d ", p->data);
}

void dbl(Link p) /* ListTraverse()调用的另一函数(元素值加倍) */
{
    p->data *= 2;
}

int main()
{
    LinkList L, L1, L2;
    Status i;
    ElemType e0;
    int j;
    Link p, q;
    i = InitList(L);
    printf("初始化L后：L->len=%u\n", L->len);
    for (j = 1;j <= 5;j++) {
        i = List_Insert_L(L, 1, j);//有没有i=不影响结果，只有List_Insert(L,1,j);也行。
    }
    printf("在表头插入元素1到5，表L中元素为");
    i = ListTraverse(L, visit);
    i = ClearList(L);
    i = ListEmpty(L);
    if (i)
        printf("表L为空\n");
    for (j = 10;j > 5;j--) {
        i = List_Insert_L(L, 1, j);
    }
    printf("表L中元素为");
    i = ListTraverse(L, visit);
    printf("表L中元素个数为%d", ListLength(L));
    i = ListTraverse(L, dbl);
    printf("表L中元素为");
    i = ListTraverse(L, visit);
    i = List_Delete_L(L, 3, e0);
    printf("被删除的元素为%d\n", e0);
    printf("表L中元素为");
    i = ListTraverse(L, visit);
    for (j = 10;j > 5;j--) {
        i = List_Insert_L(L, 1, j);
    }
    printf("表L中元素为");
    i = ListTraverse(L, visit);
    printf("表L中元素个数为%d\n", ListLength(L));
    i = Remove(L, q);
    printf("被删除的元素为%d\n", q->data);
    i = SetCurElem(L->tail, 30);
    printf("表L中元素为");
    i = ListTraverse(L, visit);
    for (j = 3;j <= 4;j++) {
        p = LocateElem(L, j, comp);
        if (p)
            printf("表L中第1个为%d的平方的元素是%d\n", j, p->data);
        else
            printf("表L中没有%d的平方的元素\n", j);
    }
    i = InitList(L1);
    for (j = 13;j >= 3;j -= 2) {
        i = List_Insert_L(L1, 1, j);
    }
    printf("表L1中元素为");
    i = ListTraverse(L1, visit);
    i = MergeList_L(L, L1, L2, compare);
    printf("表L2中元素为");
    i = ListTraverse(L2, visit);//此时L与L1头结点均被删除
    i = DestroyList(L2);
	return 0;
}

测试结果

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【PLC一体机】PLC一体机中如何实现触摸屏和PC电脑的通讯

【PLC一体机】PLC一体机中如何实现触摸屏和PC电脑的通讯

博主今天准备把之前买的PLC一体机拿出来玩一下&#xff0c;翻看以前的博文&#xff0c;发现没有记录分享PLC一体机中如何实现触摸屏程序下载的内容。 如之前博文介绍的那样&#xff0c;PLC一体机由PLC和触摸屏两部分集成的设备&#xff0c;因此设备内部已经做好了PLC和触摸屏之…
阅读更多...
树莓派5一键安装C++版本OpenCV

树莓派5一键安装C++版本OpenCV

安装环境 本人当前的安装环境&#xff1a; 树莓派5Raspberry Pi os (64-bit) Debian12 Bookworm 镜像下载地址 我这里是将镜像安装好后直接安装opencv&#xff0c;如果不是刚安装好的镜像需要注意是否有openCV的python之类的安装过&#xff0c;不然可能出现编译错误 一、扩展内…
阅读更多...
HubSpot营销自动化如何优化营销流程？

HubSpot营销自动化如何优化营销流程？

HubSpot营销自动化在优化营销流程、减少手动工作以及提高效率方面发挥着关键作用。以下是一些具体的方法和策略&#xff1a; 1. 自动化电子邮件营销&#xff1a; 利用HubSpot的电子邮件自动化功能&#xff0c;设置触发条件&#xff0c;使邮件发送根据用户行为或阶段自动进行。…
阅读更多...
Java 数据结构 二叉树（一）二叉查询树

Java 数据结构 二叉树（一）二叉查询树

目录 树的种类 二叉树 二叉查找树 满二叉树 ​编辑 完全二叉树 二叉树的数据存储 链式存储 数组存储 寻址方式&#xff1a; 二叉树的遍历&#xff08;了解即可&#xff09; ​编辑 二叉查询树缺点 前言-与正文无关 生活远不止眼前的苦劳与奔波&#xff0c;它还充满…
阅读更多...
Web项目利用OSS进行图像存储服务

Web项目利用OSS进行图像存储服务

一、OSS介绍 在Web项目中&#xff0c;一些常见的功能&#xff0c;比如展示图片&#xff0c;修改头像等&#xff0c;都需要进行图片的上传操作&#xff0c;但是如果是存储在Web服务器中&#xff0c;在读取图片的时候会占用比较多的资源&#xff0c;影响服务器的性能。 常…
阅读更多...
EasyCVR智能视频监控平台云台降低延迟小tips

EasyCVR智能视频监控平台云台降低延迟小tips

TSINGSEE青犀视频监控汇聚平台EasyCVR可拓展性强、视频能力灵活、部署轻快&#xff0c;可支持的主流标准协议有国标GB28181、RTSP/Onvif、RTMP等&#xff0c;以及支持厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等。平台既具备传统安防视频监控的能力&…
阅读更多...
零基础爬什么值得买的榜单——爬虫练习题目一（答三）

零基础爬什么值得买的榜单——爬虫练习题目一（答三）

一步一步似爪牙&#xff0c;先给爷爬一个! 引言分析数据上一节代码运行 工具&#xff1a;JSON 在线解析使用实操 获取其中一个数据添加代码知识点 结尾 引言 我也太能拖了 这个假期前确实有点懒惰 加上这个周末连班 不能去打篮球 腿没有得到充分的运动 像是千万只蚂蚁在爬一样…
阅读更多...
AI Infra论文阅读之将流水线并行气泡几乎降到零（附基于Meagtron-LM的ZB-H1开源代码实现解读）

AI Infra论文阅读之将流水线并行气泡几乎降到零（附基于Meagtron-LM的ZB-H1开源代码实现解读）

0x0. 前言 这篇论文对应的链接为&#xff1a;https://openreview.net/pdf?idtuzTN0eIO5 &#xff0c;最近被ICLR 2024接收&#xff0c;但不少AI Infra的同行已经发现了这个工作的价值&#xff0c;并且已经开源在 https://github.com/sail-sg/zero-bubble-pipeline-parallelis…
阅读更多...
编写程序实现二叉树的创建，三种遍历自己销毁

编写程序实现二叉树的创建，三种遍历自己销毁

#include <myhead.h>// 定义二叉树节点结构体 struct tree {char value; //二叉树的值struct tree* left; //左子树struct tree* right; //右子树 };// 创建节点 struct tree* create_node(int value) {//申请空间struct tree* new (struct tree*)malloc(sizeof(st…
阅读更多...
[Python] opencv - 什么是直方图？如何绘制图像的直方图？

[Python] opencv - 什么是直方图？如何绘制图像的直方图？

什么是直方图&#xff1f; 直方图是一种统计图&#xff0c;用于展示数据的分布情况。它将数据按照一定的区间或者组进行划分&#xff0c;然后计算在每个区间或组内的数据频数或频率&#xff08;即数据出现的次数或占比&#xff09;&#xff0c;然后用矩形或者柱形图的形式将这…
阅读更多...
学成在线:媒体资源管理系统(MAM)

学成在线:媒体资源管理系统(MAM)

媒体资源管理系统(MAM) 媒体资源管理系统(Media Asset Management)是建立在多媒体、网络、数据库和数字存储等先进技术基础上的一个对各种媒体及内容进行数字化存储、管理以及应用的总体解决方案,可以满足媒体资源拥有者收集、保存、查找、编辑、发布各种信息的要求,为媒体资源…
阅读更多...
Cannot resolve plugin org.apache.maven.plugins:maven-compiler-plugin:3.8.1

Cannot resolve plugin org.apache.maven.plugins:maven-compiler-plugin:3.8.1

目录 【问题描述】maven环境报错 Cannot resolve plugin org.apache.maven.plugins:maven-compiler-plugin:3.8.1 【解决办法】 检查maven路径是否一致 路径一致的话&#xff0c;更改配置文件settings.xml的镜像源。 添加代码到 <mirrors> <!-- 阿里镜像 --> &l…
阅读更多...
Security ❀ TCP异常报文详解

Security ❀ TCP异常报文详解

文章目录 1. TCP Out-Of-Order2. TCP Previous Segment Lost3. TCP Retransmission4. TCP Dup Ack XXX#X5. TCP Windows Update6. TCP Previous segment not captured7. 异常案例分析 TCP协议中seq和ack seq的联系&#xff1a; id4的http请求报文由客户端发向服务器&#xff0…
阅读更多...
Transformer实战-系列教程1：Transformer算法解读1

Transformer实战-系列教程1：Transformer算法解读1

&#x1f6a9;&#x1f6a9;&#x1f6a9;Transformer实战-系列教程总目录 有任何问题欢迎在下面留言 Transformer实战-系列教程1&#xff1a;Transformer算法解读1 Transformer实战-系列教程2&#xff1a;Transformer算法解读2 现在最火的AI内容&#xff0c;chatGPT、视觉大模…
阅读更多...
初识webpack（一）概念、入口配置、输出配置、loader等

初识webpack（一）概念、入口配置、输出配置、loader等

目录 (一)概念 webpack的依赖图 (二)webpack的基本使用 (三)webpack的配置文件 1.入口(entry)配置 2.输出(output)配置 (三)loader 1.css文件处理 (1)安装css-loader和style-loader (2)在webpack.config.js中配置loader 2.less文件处理 3.postcss的使用 (1)安装…
阅读更多...
mysql索引有哪些，如何分类

mysql索引有哪些，如何分类

前言 按数据结构分类可分为&#xff1a;Btree索引、Hash索引、Full-text索引。 按物理存储分类可分为&#xff1a;聚簇索引、二级索引&#xff08;辅助索引&#xff09;。 按字段特性分类可分为&#xff1a;主键索引、普通索引、前缀索引。 按字段个数分类可分为&#xff1…
阅读更多...
C++拷贝构造函数、赋值运算符重载

C++拷贝构造函数、赋值运算符重载

1.拷贝构造函数 拷贝构造函数的写法如图所示 调用方式如下 接下来我来说说它的特征 1.1特征 拷贝构造函数&#xff1a;只有单个形参&#xff0c;该形参是对本类类型对象的引用(一般常用const修饰)&#xff0c;在用已存在的类类型对象创建新对象时由编译器自动调用。 拷贝构造函…
阅读更多...
推荐系统(Recommender Systems)

推荐系统(Recommender Systems)

一、问题形式化 在接下来的内容中&#xff0c;我将开始讲解推荐系统的一些理论知识。我们从一个例子开始定义推荐系统&#xff0c;假使我们是一个电影供应商&#xff0c;我们有 5 部电影和 4 个用户&#xff0c;我们要求用户为电影打分 前三部电影是爱情片&#xff0c;后两部是…
阅读更多...
GPT用来润色论文\生成完整长篇论文\进行AI绘图，真的太香了！

GPT用来润色论文\生成完整长篇论文\进行AI绘图，真的太香了！

详情点击公众号&#xff1a;技术科研吧 链接&#xff1a;GPT用来润色论文\生成完整长篇论文\进行AI绘图&#xff0c;真的太香了&#xff01; 一&#xff1a;AI领域最新技术 1.OpenAI新模型-GPT-5 2.谷歌新模型-Gemini Ultra 3.Meta新模型-LLama3 4.科大讯飞-星火认知 5.百…
阅读更多...
歌声悠扬如往昔

歌声悠扬如往昔

有一首歌 - 朱晓琳&#xff08;网易云单曲&#xff09; 作词 : 陈彼得作曲 : 陈彼得有一首歌我想起你那时候微风轻轻有一首歌我想起你你的感觉温馨有多少的欢笑就有多少的忧伤 愿时光在这里停住(好景不常在)歌声悠扬如往昔哦哦哦咿咿咿有一首歌我和你词意朦胧旋律依稀唱一首歌…
阅读更多...
最新文章

Copyright @ 2022~2023