数据结构——实验01-线性表的链式存储和操作

一、实验内容

二、算法思想与算法实现

1、解题思想

（1）逆序创建链表La就是使用头插法创建一个链表，所谓头插法就是在创建链表时始终将新元素插入到头结点之后，而正序创建链表Lb就是使用尾插法创建一个链表，所谓尾插法创建一个链表就是在创建链表时始终将新元素插入到表尾

（2）合并两个升序序列，这个算法很基础，这里不做叙述，需要注意的是由于在创建La时我们是逆序创建的，也就是说此时La是降序排列，所以在做两个链表的合并操作之前我们需要先将链表La逆置

（3）删除Lc中的多余元素：这里我们可以用一个指针p表示当前链表的结点，然后用一个指针t指向第一个结点元素值不等于当前结点元素值的结点，然后让结点p的next指针域指向t即可，如下图所示

（4）逆置一个链表，可以借助头插法创建链表的思想，即扫描当前需要逆置的链表不断将当前结点插入到表头

2、算法实现

（1）定义链表结点

//定义链表节点
typedef struct LNode {
	int data;                          //数据域
	struct LNode* next;                //指针域
}LNode,*LinkList;

（2）头插法创建链表

//使用头插法创建一个带头结点的链表，当用户输入666时表示链表创建结束
bool List_HeadInsert(LinkList& L) {

	//对链表进行初始化操作
	L = (LNode*)malloc(sizeof(LNode) * 1);
	if (L == NULL)
	{
		return false;
	}
	L->next = NULL;

	LNode* p = NULL;
	int inputs = 0;
	
	printf("请输入链表元素:\n");
	while (1)
	{
		scanf("%d", &inputs);
		if (inputs == 666)
			break;

		p = (LNode*)malloc(sizeof(LNode) * 1);
		if (p == NULL)
		{
			return false;
		}

		p->data = inputs;
		p->next = L->next;
		
		L->next = p;
	}

	return true;
}

 （3）尾插法创建链表


//使用尾插法创建一个带头结点的链表，当用户输入666时表示链表创建结束
bool List_TailInsert(LinkList& L)
{
	//对链表进行初始化操作
	L = (LNode*)malloc(sizeof(LNode) * 1);
	if (L == NULL)
		return false;
	L->next = NULL;

	LNode* p, * t;   //p指针用于建立新结点，t用于指向当前链表的尾结点
	int inputs;
	t = L;

	printf("请输入链表元素:\n");
	while (1)
	{
		scanf("%d", &inputs);
		if (inputs == 666)
			break;

		p = (LNode*)malloc(sizeof(LNode) * 1);
		if (p == NULL)
			return false;

		p->data = inputs;
		p->next = NULL;

		t->next = p;
		t = p;
	}

	return true;
}

（4）合并两个升序链表

//合并两个有序链表
bool Merge_SortedLinkList(LinkList La, LinkList Lb, LinkList& Lc)
{
	LNode* a, * b, * c, * t;
	a = La->next;
	b = Lb->next;

	//初始化链表Lc；
	Lc = (LNode*)malloc(sizeof(LNode) * 1);
	if (Lc == NULL)
		return false;
	Lc->next = NULL;
	t = Lc;          //t指针指向Lc的尾部结点

	while (a != NULL && b != NULL)
	{
		c = (LNode*)malloc(sizeof(LNode) * 1);
		if (c == NULL)
			return false;
		

		if (a->data <= b->data)
		{
			c->data = a->data;
			c->next = NULL;

			t->next = c;
			t = c;

			a = a->next;
		}
		else
		{
			c->data = b->data;
			c->next = NULL;

			t->next = c;
			t = c;

			b = b->next;
		}
	}

	while (a == NULL && b != NULL)
	{
		c = (LNode*)malloc(sizeof(LNode) * 1);
		c->data = b->data;
		c->next = NULL;
		t->next = c;
		t = c;
		b = b->next;
	}

	while (b == NULL && a != NULL)
	{
		c = (LNode*)malloc(sizeof(LNode) * 1);
		c->data = a->data;
		c->next = NULL;
		t->next = c;
		t = c;
		a = a->next;
	}

	return true;
}

（5）删除链表中的重复元素

//删除有序链表中的重复元素
bool DeleteRpeatElem(LinkList& L)
{
	//判断是否是空表
	if (L->next == NULL)
		return false;

	LNode* p, * e = NULL;   //p指针用于记录当前结点，e指针用于表示值等于当前结点的最后一个结点

	p = L->next;

	while (p != NULL)
	{
		e = p->next;
		if (e == NULL)
			break;
		while (p->data == e->data)
		{
			LNode* temp = e;
			e = e->next;
			free(temp);
		}

		p->next = e;
		p = p->next;	
	}
	return true;
}

（6）逆置一个链表

//逆置一个链表，从头开始扫描一个链表，不断将当前结点插入到链表的开始位置
bool ReverseLinkList(LinkList& L)
{
	if (L->next == NULL)
		return false;
	LNode* end = L->next;  //指向逆置以后的表尾元素
	LNode* p = end->next;  //指向当前元素

	while (p != NULL)
	{
		LNode* temp = p->next;

		p->next = L->next;
		L->next = p;

		p = temp;
	}
	
	end->next = NULL;

	return true;
}

三、代码测试

完整测试代码：

//用C语言编写程序，其中Lb={2,4,6,8,10} La={1,2,3,4,5,6,8},
//(1)逆序创建链表La, 正序创建链表Lb; .
//(2)将La与Lb有序合并，得到有序链表Lc：Lc = { 1,2,2,3,4,4,5,6,6,8,8,10 }
//(3)删除Lc中多余的重复元素，使得所有元素只保留一个;
//(4)将链表Lc倒置，并输出其内容。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
using namespace std;


//定义链表节点
typedef struct LNode {
	int data;                          //数据域
	struct LNode* next;                //指针域
}LNode,*LinkList;

//使用头插法创建一个带头结点的链表，当用户输入666时表示链表创建结束
bool List_HeadInsert(LinkList& L) {

	//对链表进行初始化操作
	L = (LNode*)malloc(sizeof(LNode) * 1);
	if (L == NULL)
	{
		return false;
	}
	L->next = NULL;

	LNode* p = NULL;
	int inputs = 0;
	
	printf("请输入链表元素:\n");
	while (1)
	{
		scanf("%d", &inputs);
		if (inputs == 666)
			break;

		p = (LNode*)malloc(sizeof(LNode) * 1);
		if (p == NULL)
		{
			return false;
		}

		p->data = inputs;
		p->next = L->next;
		
		L->next = p;
	}

	return true;
}


//使用尾插法创建一个带头结点的链表，当用户输入666时表示链表创建结束
bool List_TailInsert(LinkList& L)
{
	//对链表进行初始化操作
	L = (LNode*)malloc(sizeof(LNode) * 1);
	if (L == NULL)
		return false;
	L->next = NULL;

	LNode* p, * t;   //p指针用于建立新结点，t用于指向当前链表的尾结点
	int inputs;
	t = L;

	printf("请输入链表元素:\n");
	while (1)
	{
		scanf("%d", &inputs);
		if (inputs == 666)
			break;

		p = (LNode*)malloc(sizeof(LNode) * 1);
		if (p == NULL)
			return false;

		p->data = inputs;
		p->next = NULL;

		t->next = p;
		t = p;
	}

	return true;
}


//合并两个有序链表
bool Merge_SortedLinkList(LinkList La, LinkList Lb, LinkList& Lc)
{
	LNode* a, * b, * c, * t;
	a = La->next;
	b = Lb->next;

	//初始化链表Lc；
	Lc = (LNode*)malloc(sizeof(LNode) * 1);
	if (Lc == NULL)
		return false;
	Lc->next = NULL;
	t = Lc;          //t指针指向Lc的尾部结点

	while (a != NULL && b != NULL)
	{
		c = (LNode*)malloc(sizeof(LNode) * 1);
		if (c == NULL)
			return false;
		

		if (a->data <= b->data)
		{
			c->data = a->data;
			c->next = NULL;

			t->next = c;
			t = c;

			a = a->next;
		}
		else
		{
			c->data = b->data;
			c->next = NULL;

			t->next = c;
			t = c;

			b = b->next;
		}
	}

	while (a == NULL && b != NULL)
	{
		c = (LNode*)malloc(sizeof(LNode) * 1);
		c->data = b->data;
		c->next = NULL;
		t->next = c;
		t = c;
		b = b->next;
	}

	while (b == NULL && a != NULL)
	{
		c = (LNode*)malloc(sizeof(LNode) * 1);
		c->data = a->data;
		c->next = NULL;
		t->next = c;
		t = c;
		a = a->next;
	}

	return true;
}

//删除有序链表中的重复元素
bool DeleteRpeatElem(LinkList& L)
{
	//判断是否是空表
	if (L->next == NULL)
		return false;

	LNode* p, * e = NULL;   //p指针用于记录当前结点，e指针用于表示值等于当前结点的最后一个结点

	p = L->next;

	while (p != NULL)
	{
		e = p->next;
		if (e == NULL)
			break;
		while (p->data == e->data)
		{
			LNode* temp = e;
			e = e->next;
			free(temp);
		}

		p->next = e;
		p = p->next;	
	}
	return true;
}

//逆置一个链表，从头开始扫描一个链表，不断将当前结点插入到链表的开始位置
bool ReverseLinkList(LinkList& L)
{
	if (L->next == NULL)
		return false;
	LNode* end = L->next;  //指向逆置以后的表尾元素
	LNode* p = end->next;  //指向当前元素

	while (p != NULL)
	{
		LNode* temp = p->next;

		p->next = L->next;
		L->next = p;

		p = temp;
	}
	
	end->next = NULL;

	return true;
}

//顺序打印一个链表中的所有元素
bool PrintLinkList(LinkList L)
{
	if (L->next == NULL)
		return false;
	LNode* p = L->next;
	while (p != NULL)
	{
		printf("%d\t", p->data);
		p = p->next;
	}
	printf("\n");
	
	return true;
}


//测试程序
int main()
{
	LinkList La, Lb, Lc;

	//逆序创建链表La,即使用头插法创建链表La
	List_HeadInsert(La);
	printf("链表La：\n");
	PrintLinkList(La);

	//正序创建链表Lb，即使用尾插法创建链表Lb
	List_TailInsert(Lb);
	printf("链表Lb：\n");
	PrintLinkList(Lb);


	//合并La和Lb
	
	//先逆序La
	ReverseLinkList(La);
	printf("逆序后的链表La：\n");
	PrintLinkList(La);

	//调用函数合并La和Lb
	Merge_SortedLinkList(La, Lb, Lc);
	printf("合并链表La和链表Lb得到的链表Lc：\n");
	PrintLinkList(Lc);

	//删除Lc中的重复元素
	DeleteRpeatElem(Lc);
	printf("删除链表Lc中的重复元素的结果：\n");
	PrintLinkList(Lc);

	//将Lc逆序
	ReverseLinkList(Lc);
	printf("将链表Lc逆序之后的结果：\n");
	PrintLinkList(Lc);

    return 0;

}

测试结果截图：

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

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

相关文章

[晓理紫]每日论文分享(有中文摘要，源码或项目地址)--强化学习、模仿学习

[晓理紫]每日论文分享(有中文摘要，源码或项目地址)--强化学习、模仿学习

专属领域论文订阅 关注{晓理紫|小李子}&#xff0c;每日更新论文&#xff0c;如感兴趣&#xff0c;请转发给有需要的同学&#xff0c;谢谢支持 如果你感觉对你有所帮助&#xff0c;请关注我&#xff0c;每日准时为你推送最新论文。 为了答谢各位网友的支持&#xff0c;从今日起…
阅读更多...
Latex学习记录

Latex学习记录

目录 1.Latex各种箭头符号总结 2.[Latex]公式编辑&#xff0c;编号、对齐 3.Latex公式编号: 多行公式多编号&#xff0c;多行公式单编号 4.LaTex中输入空格以及换行 1.Latex各种箭头符号总结 箭头符号 - ➚ (piliapp.com)https://cn.piliapp.com/symbol/arrow/Latex各种箭头…
阅读更多...
【LeetCode: 462. 最小操作次数使数组元素相等 II + 贪心】

【LeetCode: 462. 最小操作次数使数组元素相等 II + 贪心】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…
阅读更多...
根据路由动态注册组件失败

根据路由动态注册组件失败

动态注册组件 方式1 import 这种跟webpack的版本有关系 import低版本不支持传入动态参数 <template><components :is"componentName" v-show"isShow" :key"componentName"></components> </template>const _import fi…
阅读更多...
网络基础【Linux网络编程】

网络基础【Linux网络编程】

目录 一、网络发展 二、协议和协议分层 OSI七层网络模型 TCP/IP协议栈 三、网络和OS的关系 四、网络传输基本流程 五、数据包封装和分用 六、IP地址和MAC地址 MAC地址 局域网通信原理 IP地址 一、网络发展 详细参考此篇博文&#xff1a;网络发展史 独立模式 计算机…
阅读更多...
第三百零三回

第三百零三回

文章目录 1. 概念介绍2. 实现方法2.1 文字信息2.2 红色边框 3. 示例代码4. 内容总结 我们在上一章回中介绍了"如何实现密码输入框"相关的内容&#xff0c;本章回中将介绍如何在在输入框中提示错误.闲话休提&#xff0c;让我们一起Talk Flutter吧。 1. 概念介绍 我们…
阅读更多...
Qt加载网页崩溃 ASSERT:“m_adapterClient“ in file ...

Qt加载网页崩溃 ASSERT:“m_adapterClient“ in file ...

1、软件启动后加载网页无异常&#xff0c;点击按钮&#xff0c;加载新网页时崩溃 崩溃代码&#xff1a; QWebEngineView *createWindow(QWebEnginePage::WebWindowType type) { Q_UNUSED(type); return this; } 2、原因 Qt只是调用谷歌的浏览器引擎&#xff…
阅读更多...
构建用于预警大型语言模型辅助生物威胁创建的系统

构建用于预警大型语言模型辅助生物威胁创建的系统

深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领域的领跑者。点击订阅&#xff0c;与未来同行&#xff01; 订阅&#xff1a;https://rengongzhineng.io/ 。 Op…
阅读更多...
vivado jesd204核综合错误

vivado jesd204核综合错误

用204核的时候老是报如下错误。 [Opt 31-67] Problem: A LUT2 cell in the design is missing a connection on input pin I0, which is used by the LUT equation. This pin has either been left unconnected in the design or the connection was removed due to the trimm…
阅读更多...
ubuntu 上安装和配置Apache2+Subversion

ubuntu 上安装和配置Apache2+Subversion

目录 一、安装Apache2和SVN 二、Apache2设置 三、subversion配置 四、创建仓库和设置权限 五、仓库备份和恢复 系统环境 Ubuntu Linux (20.04) apache2 Subversion(1.13.0) 一、安装Apache2和SVN 通过命令在线安装apache2和subversion apt-get install apache2 libap…
阅读更多...
Maven高级知识——分模块开发、继承与聚合

Maven高级知识——分模块开发、继承与聚合

目录 一、分模块设计与开发 1.1 不分模块的问题 1.2 分模块设计 二、 继承与聚合 2.1 继承 2.1.1 继承关系 2.1.2 版本锁定 2.1.2.1 场景 2.1.2.2 介绍 2.1.2.3 实现 2.1.2.4 属性配置 2.2 聚合 2.2.1 介绍 2.2.2 实现 2.3 继承与聚合对比 三、Maven打包方式&#xff08;jar、w…
阅读更多...
数据结构—动态查找

数据结构—动态查找

动态查找介绍 1. 动态查找的引入&#xff1a;当查找表以线性表的形式组织时&#xff0c;若对查找表进行插入、删除或排序操作&#xff0c;就必须移动大量的记录&#xff0c;当记录数很多时&#xff0c;这种移动的代价很大。 2. 动态查找表的设计思想&#xff1a;表结构本身是…
阅读更多...
只用一台服务器部署上线（宝塔面板） 前后端+数据库

只用一台服务器部署上线（宝塔面板） 前后端+数据库

所需材料 工具&#xff1a;安装宝塔面板服务器至少一台、域名一个 前端&#xff1a;生成dist文件&#xff08;前端运行build命令&#xff09; 后端&#xff1a;生成jar包&#xff08;maven运行package命令&#xff09; 准备&#xff1a; 打开宝塔面板&#xff0c;点击进入软…
阅读更多...
element-ui link 组件源码分享

element-ui link 组件源码分享

link 组件的 api 涉及的内容不是很多&#xff0c;源码部分的内容也相对较简单&#xff0c;下面从以下这三个方面来讲解&#xff1a; 一、组件结构 1.1 组件结构如下图&#xff1a; 二、组件属性 2.1 组件主要有 type、underline、disabled、href、icon 这些属性&#xff0c;…
阅读更多...
OpenCV+ moviepy + tkinter 视频车道线智能识别项目源码

OpenCV+ moviepy + tkinter 视频车道线智能识别项目源码

项目完整源代码&#xff0c;使用 OpenCV 的Hough 直线检测算法&#xff0c;提取出道路车道线并绘制出来。通过tkinter 提供GUI界面展示效果。 1、导入相关模块 import matplotlib.pyplot as plt import numpy as np import cv2 import os import matplotlib.image as mpimg …
阅读更多...
虚幻UE 特效-Niagara特效实战-魔法阵

虚幻UE 特效-Niagara特效实战-魔法阵

回顾Niagara特效基础知识&#xff1a;虚幻UE 特效-Niagara特效初识 其他四篇实战&#xff1a;UE 特效-Niagara特效实战-烟雾、喷泉、 虚幻UE 特效-Niagara特效实战-火焰、烛火、 虚幻UE 特效-Niagara特效实战-雨天、 虚幻UE 特效-Niagara特效实战-眩晕。 本篇笔记记录了使用空模…
阅读更多...
Scrum敏捷开发企业培训-敏捷研发管理

Scrum敏捷开发企业培训-敏捷研发管理

课程简介 Scrum是目前运用最为广泛的敏捷开发方法&#xff0c;是一个轻量级的项目管理和产品研发管理框架。 这是一个两天的实训课程&#xff0c;面向研发管理者、项目经理、产品经理、研发团队等&#xff0c;旨在帮助学员全面系统地学习Scrum和敏捷开发, 帮助企业快速启动敏…
阅读更多...
【循环结构·js】

【循环结构·js】

变量命名原则 变量名由字母、下划线、$ 或数字组成&#xff0c;并且必须由字母、下划线、$ 开头。 变量名不能命名为系统关键字和保留字。 JS代码在sourse里面调试 document.write(str); /*在页面上输出变量 str 的值*/数据类型的分类 为什么要标识数据类型&#xff1a; 不…
阅读更多...
【Java开发岗面试】八股文—微服务、消息中间件

【Java开发岗面试】八股文—微服务、消息中间件

声明&#xff1a; 背景&#xff1a;本人为24届双非硕校招生&#xff0c;已经完整经历了一次秋招&#xff0c;拿到了三个offer。本专题旨在分享自己的一些Java开发岗面试经验&#xff08;主要是校招&#xff09;&#xff0c;包括我自己总结的八股文、算法、项目介绍、HR面和面试…
阅读更多...
IT部门规划：构建高效、创新的技术引擎

IT部门规划：构建高效、创新的技术引擎

序言 在当今这个信息化、数字化的时代&#xff0c;IT部门的重要性日益凸显。一个高效、创新的IT部门&#xff0c;不仅是企业稳定运营的保障&#xff0c;更是推动企业持续发展的核心动力。那么&#xff0c;如何规划一个优秀的IT部门呢&#xff1f; 一、明确IT部门的战略定位 …
阅读更多...
最新文章

Copyright @ 2022~2023