数据结构（C语言版）代码实现（三）——单链表部分代码实现

目录

格式

头文件

宏定义

线性表的单链表存储结构

按位查找

插入元素

删除元素

头插法建立单链表

合并非递减单链表

其他基本操作

完整版

测试代码（主函数）

测试结果

格式

参考 2.3节 线性表的链式表示和实现

头文件

宏定义

#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,*LinkList;

按位查找

//算法2.8 函数GetElem在单链表中的实现。
Status GetElem_L(LinkList L, int i, ElemType& e) {
	//L为带头结点的单链表的头指针。
	//当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
	LinkList p = L->next;int j = 1;//初始化，p指向第一个结点，j为计数器
	while (p && j < i) {//顺指针向后查找，直到p指向第i个元素或p为空
		p = p->next;
		++j;
	}
	if (!p || j > i)
		return ERROR;//第i个元素不存在
	e = p->data;//取第i个元素
	return OK;
}

插入元素

//算法2.9 函数ListInsert在单链表中的实现
Status ListInsert_L(LinkList& L, int i, ElemType e) {
	//在带头结点的单链线性表L中第i个位置之前插入元素e
	LinkList p = L;int j = 0;
	while (p && j < i - 1) {
		p = p->next;
		++j;//寻找第i-1个结点
	}
	if (!p || j > i - 1)
		return ERROR;//i小于1或者大于表长+1
	LinkList s = (LinkList)malloc(sizeof(LNode));//生成新结点
	s->data = e;s->next = p->next;//插入L中
	p->next = s;
}

删除元素

//算法2.10 函数ListDelete在单链表中的实现
Status ListDelete_L(LinkList& L, int i, ElemType& e) {
	//在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
	LinkList p = L;int j = 0;
	while (p && j < i - 1) {
		p = p->next;
		++j;//寻找第i个结点,p->next所在的位置
	}
	if (!(p->next) || j > i - 1)
		return ERROR;//删除位置不合理
	LinkList q = p->next;p->next = q->next;//删除并释放结点
	e = q->data;free(q);
	return OK;
}

头插法建立单链表

//算法2.11 头插法建立单链表
void CreateList_L(LinkList& L, int n) {
	//逆位序输入n个元素的值，建立带表头结点的单链线性表L。
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;//先建立一个带头结点的单链表
	LinkList p;
	for (int i = n;i > 0;i--) {
		p = (LinkList)malloc(sizeof(LNode));
		scanf_s("%d", &p->data);//输入元素值
		p->next = L->next;//插入到表头
		L->next = p;
		//插入到表尾
		// LinkList T=L;
		// for循环，用下面三行替换插入表头两行
		//p->next=NULL;
		//T->next=p;
		//T=p;
	}
}

合并非递减单链表

//算法2.12 合并非递减单链表
void MergeList_L(LinkList& La, LinkList& Lb, LinkList& Lc) {
	//已知顺序线性表La和Lb的元素按值非递减排列
	//归并La和Lb得到的新的顺序线性表Lc,Lc的元素也按值非递减排列
	LinkList pa = La->next;LinkList pb = Lb->next;
	LinkList pc = Lc = La;//用La的头结点作为Lc的头结点
	while (pa && pb) {
		if (pa->data <= pb->data) {
			pc->next = pa;
			pc = pa;
			pa = pa->next;
		}
		else {
			pc->next = pb;
			pc = pb;
			pb = pb->next;
		}
	}
	pc->next = pa ? pa : pb;//插入剩余段
	free(Lb);//释放Lb的头结点
}

free函数不能放在while循环内，否则会出现以下情况。

警告信息：使用未初始化的内存"Lb"。

看不懂，但这个问题解决了。

其他基本操作

void PrintList_L(LinkList L) {//打印链表
	LinkList p = L->next;
	while (p) {//while(p=p->next)这样写行吗？
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

Status DestroyList_L(LinkList& L) {//销毁链表
	LinkList p;
	while (L) {
		p = L;
		L = L->next;
		free(p);//free函数的释放是只释放一个结点，还是释放后面相关的所有结点？--已解决，只释放一个结点。
	}
	return OK;
}

完整版

#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,*LinkList;

//算法2.11 头插法建立单链表
void CreateList_L(LinkList& L, int n) {
	//逆位序输入n个元素的值，建立带表头结点的单链线性表L。
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;//先建立一个带头结点的单链表
	LinkList p;
	for (int i = n;i > 0;i--) {
		p = (LinkList)malloc(sizeof(LNode));
		scanf_s("%d", &p->data);//输入元素值
		p->next = L->next;//插入到表头
		L->next = p;
		//插入到表尾
		// LinkList T=L;
		// for循环，用下面三行替换插入表头两行
		//p->next=NULL;
		//T->next=p;
		//T=p;
	}
}

//算法2.8 函数GetElem在单链表中的实现。
Status GetElem_L(LinkList L, int i, ElemType& e) {
	//L为带头结点的单链表的头指针。
	//当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
	LinkList p = L->next;int j = 1;//初始化，p指向第一个结点，j为计数器
	while (p && j < i) {//顺指针向后查找，直到p指向第i个元素或p为空
		p = p->next;
		++j;
	}
	if (!p || j > i)
		return ERROR;//第i个元素不存在
	e = p->data;//取第i个元素
	return OK;
}

//算法2.9 函数ListInsert在单链表中的实现
Status ListInsert_L(LinkList& L, int i, ElemType e) {
	//在带头结点的单链线性表L中第i个位置之前插入元素e
	LinkList p = L;int j = 0;
	while (p && j < i - 1) {
		p = p->next;
		++j;//寻找第i-1个结点
	}
	if (!p || j > i - 1)
		return ERROR;//i小于1或者大于表长+1
	LinkList s = (LinkList)malloc(sizeof(LNode));//生成新结点
	s->data = e;s->next = p->next;//插入L中
	p->next = s;
}

//算法2.10 函数ListDelete在单链表中的实现
Status ListDelete_L(LinkList& L, int i, ElemType& e) {
	//在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
	LinkList p = L;int j = 0;
	while (p && j < i - 1) {
		p = p->next;
		++j;//寻找第i个结点,p->next所在的位置
	}
	if (!(p->next) || j > i - 1)
		return ERROR;//删除位置不合理
	LinkList q = p->next;p->next = q->next;//删除并释放结点
	e = q->data;free(q);
	return OK;
}

//算法2.12 合并非递减单链表
void MergeList_L(LinkList& La, LinkList& Lb, LinkList& Lc) {
	//已知顺序线性表La和Lb的元素按值非递减排列
	//归并La和Lb得到的新的顺序线性表Lc,Lc的元素也按值非递减排列
	LinkList pa = La->next;LinkList pb = Lb->next;
	LinkList pc = Lc = La;//用La的头结点作为Lc的头结点
	while (pa && pb) {
		if (pa->data <= pb->data) {
			pc->next = pa;
			pc = pa;
			pa = pa->next;
		}
		else {
			pc->next = pb;
			pc = pb;
			pb = pb->next;
		}
	}
	pc->next = pa ? pa : pb;//插入剩余段
	free(Lb);//释放Lb的头结点
}

void PrintList_L(LinkList L) {//打印链表
	LinkList p = L->next;
	while (p) {//while(p=p->next)这样写行吗？
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

Status DestroyList_L(LinkList& L) {//销毁链表
	LinkList p;
	while (L) {
		p = L;
		L = L->next;
		free(p);//free函数的释放是只释放一个结点，还是释放后面相关的所有结点？--已解决，只释放一个结点。
	}
	return OK;
}

测试代码（主函数）

#include "LinkList.h"

int main()
{
	LinkList La = NULL,Lb = NULL,Lc = NULL;
	int n1,n2;
	Status i = 0;
	ElemType e;//变量声明

	//测试算法2.11
	printf("请输入元素个数：");//构建单链表La
	scanf_s("%d", &n1);
	printf("请输入元素：");
	CreateList_L(La, n1);
	printf("\n");
	printf("头插法得到的元素逆序：");
	PrintList_L(La);

	//测试算法2.8
	i = GetElem_L(La, 3, e);
	if (i)
		printf("第3个元素为%d\n", e);
	else
		printf("第3个元素不存在\n");
	//测试算法2.9,2.10.
	i = ListInsert_L(La, 3, 3);
	if (i)
		printf("插入成功\n");
	else
		printf("插入失败\n");
	i = ListDelete_L(La, 5, e);
	if (i)
		printf("删除成功\n");
	else
		printf("删除失败\n");

	//测试算法2.12
	printf("请输入元素个数：");//构建单链表Lb
	scanf_s("%d", &n2);
	printf("请输入元素：");
	CreateList_L(Lb, n2);
	printf("\n");
	printf("头插法得到的元素逆序：");
	PrintList_L(Lb);

	MergeList_L(La, Lb, Lc);
	printf("新链表的元素：");
	PrintList_L(Lc);

	DestroyList_L(Lc);//因为Lc实质是La和Lb的合并，而且Lb的头结点已经被释放了。
	return 0;
}

测试结果

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

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

相关文章

基于机会网络编码(COPE)的卫星网络路由算法matlab仿真

基于机会网络编码(COPE)的卫星网络路由算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 4.1机会网络编码&#xff08;COPE&#xff09;概述 4.2COPE算法原理 4.2.1 编码机会预测 4.2.2 编码决策 4.2.3 数据包编码 4.2.4 数据包传输 4.2.5 数据包解码 5.完整程序 1.程序功能…
阅读更多...
从零学Java MySQL

从零学Java MySQL

MySQL 文章目录 MySQL初识数据库思考&#xff1a;1 什么是数据库&#xff1f;2 数据库管理系统 初识MySQLMySQL卸载MySQL安装1 配置环境变量2 MySQL目录结构及配置文件 连接MySQL数据库基本命令MySQL基本语法&#xff1a;1 查看MySQL服务器中所有数据库2 创建数据库3 查看数据库…
阅读更多...
12.前端--CSS-背景属性

12.前端--CSS-背景属性

1.背景颜色 样式名称&#xff1a; background-color 定义元素的背景颜色 使用方式: background-color:颜色值; 其他说明&#xff1a; 元素背景颜色默认值是 transparent&#xff08;透明&#xff09;      background-color:transparent; 代码演示&#xff1a; 背景色…
阅读更多...
【裁员潮】技术变革下的职业危机，程序员会有多大影响，又应该如何面对

【裁员潮】技术变革下的职业危机，程序员会有多大影响，又应该如何面对

大家好&#xff0c;我是全栈小5&#xff0c;欢迎阅读文章&#xff01; 此篇是【话题达人】序列文章&#xff0c;这一次的话题是《技术变革下的裁员潮》 文章将以博主的角度进行讲述&#xff0c;理解和水平有限&#xff0c;不足之处&#xff0c;望指正。 目录 背景硬实力职业危机…
阅读更多...
推荐收藏！48道数据分析师高频面试题汇总！

推荐收藏！48道数据分析师高频面试题汇总！

大家好&#xff0c;最近很多小伙伴私信我&#xff0c;讲一下数据分析的面试题&#xff0c;今天给大家整理了48道数据分析师面试时被频繁问到的题目&#xff0c;找数据分析岗位的同学一定要码住认真看。 想了解最新的面试动态、最新高频考点、技术交流的同学&#xff0c;可以文…
阅读更多...
notepad++ v8.5.3 安装插件，安装失败怎么处理？下载进度为0怎么处理？

notepad++ v8.5.3 安装插件，安装失败怎么处理？下载进度为0怎么处理？

notepad v8.5.3 安装插件&#xff0c;安装失败&#xff1f;下载进度为0&#xff0c;怎么处理&#xff1f; 安装 进度 进度条没有进度 &#xff0c;然后就退出了&#xff0c;自动打开程序&#xff0c;不知道什么问题&#xff0c;插件管理下面也没有插件显示 找到问题了&#x…
阅读更多...
C++ 数论相关题目（欧拉函数）

C++ 数论相关题目（欧拉函数）

欧拉函数 给定 n 个正整数 ai &#xff0c;请你求出每个数的欧拉函数。 欧拉函数的定义 1∼N 中与 N 互质的数的个数被称为欧拉函数&#xff0c;记为 ϕ(N) 。 若在算数基本定理中&#xff0c;Npa11pa22…pamm &#xff0c;则&#xff1a; ϕ(N) Np1−1p1p2−1p2…pm−1pm 输…
阅读更多...
BGP路由反射-数据中心IDC项目经验

BGP路由反射-数据中心IDC项目经验

一、背景描述 R1,R2,R3在AS200区域内&#xff0c;R1和R2,R1和R3建立OSPF&#xff0c;宣告接口互联. AS200区域内&#xff0c;R1和R2建立IBGP, R1和R3建立IBGP R2和R4建立EBGP, R3和R5建立EBGP。 网络拓扑&#xff1a; 二、故障现象 R1和R2可以收到来自AS100区域R4的E…
阅读更多...
技术驱动宠物健康：宠物在线问诊系统的高效搭建手册

技术驱动宠物健康：宠物在线问诊系统的高效搭建手册

在数字化时代&#xff0c;技术正在催生出许多创新的医疗服务&#xff0c;而宠物在线问诊系统便是其中一项引领潮流的创举。本文将为你提供一份高效搭建宠物在线问诊系统的手册&#xff0c;通过技术代码示例&#xff0c;让你轻松打造一套技术驱动的宠物健康管理系统。 1. 架构…
阅读更多...
CSS 楼梯弹弹球

CSS 楼梯弹弹球

<template><view class="loader"></view> </template><script></script><style>body {background-color: #212121;/* 设置背景颜色为 #212121 */}.loader {position: relative;/* 设置定位为相对定位 */width: 120px;/* 设…
阅读更多...
Linux之快速入门

Linux之快速入门

一、Linux目录结构 从Windows转到Linux最不习惯的是什么&#xff1a; 目录结构 Windows会分盘&#xff0c;想怎么放东西就怎么放东西&#xff0c;好处自由&#xff0c;缺点容易乱 Linux有自己的目录结构&#xff0c;不能随随便便放东西 /&#xff1a;根目录/bin:二进制文件&…
阅读更多...
【学术论文写作】 鲁棒性实验写作的行文逻辑

【学术论文写作】 鲁棒性实验写作的行文逻辑

文章目录 一、声明二、行文思路三、示例范文一范文二 一、声明 自己总结的&#xff0c;有问题望指正&#xff01; 二、行文思路 为什么要做鲁棒性测试怎么做实验结论对结果的解释 三、示例 PPT 范文一 2022, TIM, “A Robust and Reliable Point Cloud Recognition Netw…
阅读更多...
【C++干货铺】C++中的四种类型转换

【C++干货铺】C++中的四种类型转换

个人主页点击直达&#xff1a;小白不是程序员 C系列专栏&#xff1a;C干货铺 代码仓库&#xff1a;Gitee 目录 C语言中的类型转换 为什么C需要四种类型转化 C强制类型转换 static_cast reinterpret_cast const_cast dynamic_cast RTTI C语言中的类型转换 在C语言中&…
阅读更多...
建议CSDN不要这样吃人xue馒头

建议CSDN不要这样吃人xue馒头

程序员裁员潮&#xff1a;技术变革下的职业危机 2023年以来&#xff0c;谷歌、阿里巴巴各个科技公司都在裁员&#xff0c;程序员的日子也不好过。 讨论在技术变革下&#xff0c;裁员对于程序员的影响到底有多大&#xff0c;是非常有意义的话题&#xff0c;但是为什么要用“一…
阅读更多...
一些es的基本操作

一些es的基本操作

目录 给索引增加字段&#xff1a;给索引删除字段[^1]&#xff1a;创建索引&#xff1a;插入document删除document(应该是按ID) : 给索引增加字段&#xff1a; 用postMan: 给名为population_portrait_hash_seven的索引增加了一个text类型的字段。 用chrome插件Elasticvue 的Re…
阅读更多...
MySql索引事务讲解和(经典面试题)

MySql索引事务讲解和(经典面试题)

&#x1f3a5; 个人主页&#xff1a;Dikz12&#x1f525;个人专栏&#xff1a;MySql&#x1f4d5;格言&#xff1a;那些在暗处执拗生长的花&#xff0c;终有一日会馥郁传香欢迎大家&#x1f44d;点赞✍评论⭐收藏 目录 索引 概念 索引的相关操作 索引内部数据结构 事务 为…
阅读更多...
【软考】位示图

【软考】位示图

目录 一、基本概念二、位示图 一、基本概念 1.要将文件保存到外部存储器&#xff08;外存或辅存&#xff09;&#xff0c;首先得知道存储空间的使用情况 2.要清楚哪个物理块已经被占用&#xff0c;哪个物理块是空闲的 3.当对大容量的磁盘存储空间被多用户共享时&#xff0c;用户…
阅读更多...
深度学习——pycharm远程连接

深度学习——pycharm远程连接

目录 远程环境配置本地环境配置&#xff08;注意看假设&#xff01;&#xff01;!这是很多博客里没写的&#xff09;步骤1步骤2步骤2.1 配置Connection步骤2.2 配置Mappings 步骤3 配置本地项目的远程解释器技巧1 pycharm中远程终端连接技巧2 远程目录技巧3 上传代码文件技巧4 …
阅读更多...
（二）MySQL安装与部署（redhat9）

（二）MySQL安装与部署（redhat9）

前言 MySQL仅仅是一个产品&#xff0c;Oracle旗下的小型数据库。广泛应用在中小型项目中&#xff0c;特征体积小速度快整体成本低。尤其是开源&#xff0c;所以很多中小型项目为了降低成本纷纷选用MySql作为数控存储介质 MySql的特征 底层语言使用C、C编写的。并且使用多种编…
阅读更多...
学单片机前先学什么？

学单片机前先学什么？

学单片机前先学什么&#xff1f; 在开始前我有一些资料&#xff0c;是我根据网友给的问题精心整理了一份「单片机的资料从专业入门到高级教程」&#xff0c; 点个关注在评论区回复“888”之后私信回复“888”&#xff0c;全部无偿共享给大家&#xff01;&#xff01;&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023