数据结构——实验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,即使用头插法创建链表LaList_HeadInsert(La);printf("链表La：\n");PrintLinkList(La);//正序创建链表Lb，即使用尾插法创建链表LbList_TailInsert(Lb);printf("链表Lb：\n");PrintLinkList(Lb);//合并La和Lb//先逆序LaReverseLinkList(La);printf("逆序后的链表La：\n");PrintLinkList(La);//调用函数合并La和LbMerge_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;}

测试结果截图：

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

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

相关文章

Pycharm python用matplotlib 3D绘图显示空白解决办法

Pycharm python用matplotlib 3D绘图显示空白解决办法

问题原因&#xff1a; matplotlib版本升级之后显示代码变了&#xff0c;修改为新的 # ax Axes3D(fig) # 原代码 ax fig.add_axes(Axes3D(fig)) # 新代码import numpy as np import matplotlib.pyplot as plt from matplotlib import cm from mpl_toolkits.mplot3d import Ax…
阅读更多...
五大架构风格之一：数据流风格

五大架构风格之一：数据流风格

数据流风格详细介绍 系统架构数据流风格是一种软件体系结构风格&#xff0c;它强调了系统内部不同部分之间的数据流动。这种风格侧重于描述系统中的数据处理过程&#xff0c;以及数据是如何从一个组件传递到另一个组件的。以下是系统架构数据流风格的详细介绍&#xff1a; 1 基…
阅读更多...
Hadoop：HDFS学习巩固——基础习题及编程实战

Hadoop：HDFS学习巩固——基础习题及编程实战

一 HDFS 选择题 1.对HDFS通信协议的理解错误的是&#xff1f; A.客户端与数据节点的交互是通过RPC&#xff08;Remote Procedure Call&#xff09;来实现的 B.HDFS通信协议都是构建在IoT协议基础之上的 C.名称节点和数据节点之间则使用数据节点协议进行交互 D.客户端通过一…
阅读更多...
代码随想录算法训练营29期Day41|LeetCode 343,96

代码随想录算法训练营29期Day41|LeetCode 343,96

文档讲解&#xff1a;整数拆分 不同的二叉搜索树 343.整数拆分 题目链接&#xff1a;https://leetcode.cn/problems/integer-break/description/ 思路&#xff1a; 题目要求我们拆分n&#xff0c;拆成k个数使其乘积和最大&#xff0c;然而题目中并没有给出k&#xff0c;所以…
阅读更多...
影院购票|电影院订票选座小程序|基于微信小程序的电影院购票系统设计与实现(源码+数据库+文档)

影院购票|电影院订票选座小程序|基于微信小程序的电影院购票系统设计与实现(源码+数据库+文档)

电影院订票选座小程序目录 目录 基于微信小程序的电影院购票系统设计与实现 一、前言 二、系统功能设计 三、系统实现 1、用户功能实现 2、管理员功能实现 &#xff08;1&#xff09;影院信息管理 &#xff08;2&#xff09;电影信息管理 &#xff08;3&#xff09;已…
阅读更多...
算法学习——华为机考题库6（HJ36 - HJ40）

算法学习——华为机考题库6（HJ36 - HJ40）

算法学习——华为机考题库6&#xff08;HJ36 - HJ40&#xff09; HJ36 字符串加密 描述 有一种技巧可以对数据进行加密&#xff0c;它使用一个单词作为它的密匙。下面是它的工作原理&#xff1a;首先&#xff0c;选择一个单词作为密匙&#xff0c;如TRAILBLAZERS。如果单词中…
阅读更多...
链表——C语言——day17

链表——C语言——day17

链表 链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。在用数组存放数据时&#xff0c;必须事先定义固定的长度&#xff08;即元素个数&#xff09;。链表则没有这种缺点&#xff0c;它根据需要开辟内存单元。 链表有一个“头指针“变量&#xff0c;图中…
阅读更多...
kubekey网页版安装k8s集群操作流程

kubekey网页版安装k8s集群操作流程

kubekey可以一键拉起k8s集群并完成kubesphere的部署&#xff0c;以后kubekey简称kk。kk 3.2版本以前都是在宿主机上完成对应的创建集群、添加节点、升级等操作的&#xff0c;3.2版本后开始往页面操作的方向演进&#xff0c;kk 3.2版本现在还是alpha&#xff0c;所以不推荐在生产…
阅读更多...
fastadmin后台自定义按钮和弹窗

fastadmin后台自定义按钮和弹窗

工具栏自定义按钮-ajax请求 前端代码 1.在对应模块的模板文件index.html添加自定义按钮&#xff0c;注意按钮要添加id以绑定点击事件 <div class"panel panel-default panel-intro">{:build_heading()}<div class"panel-body"><div id&qu…
阅读更多...
STM32通用定时器、计数器

STM32通用定时器、计数器

时间记录&#xff1a;2024/1/30 一、时钟介绍&#xff08;TIM2-TIM5&#xff09; &#xff08;1&#xff09;通用定时器时钟频率介绍 内部时钟AHB为72MHz&#xff0c;经过APB1预分频器2分频变为36MHz&#xff0c;TIMxClk定时器时钟由时钟树可以看出&#xff0c;如果APB1预分…
阅读更多...
C#，雅各布斯塔尔—卢卡斯（Jacobsthal Lucas Number）的算法与源代码

C#，雅各布斯塔尔—卢卡斯（Jacobsthal Lucas Number）的算法与源代码

1 雅各布斯塔尔序列 雅各布斯塔尔序列是一个与斐波那契序列类似的加法序列&#xff0c;由递归关系JnJn-12Jn-2定义&#xff0c;初始项J00&#xff0c;J11。序列中的一个数字称为雅可布沙尔数。它们是卢卡斯序列Un&#xff08;P&#xff0c;Q&#xff09;的一种特殊类型&#x…
阅读更多...
微软Office Plus与WPS Office的较量：办公软件市场将迎来巨变？

微软Office Plus与WPS Office的较量：办公软件市场将迎来巨变？

微软Office Plus在功能表现上远超WPS Office&#xff1f; 微软出品的Office套件实力强劲&#xff0c;其不仅在办公场景中扮演着不可或缺的角色&#xff0c;为用户带来高效便捷的体验&#xff0c;而且在娱乐生活管理等多元领域中同样展现出了卓越的应用价值 作为中国本土办公软…
阅读更多...
IO多路复用机制——select、poll、epoll的原理和区别

IO多路复用机制——select、poll、epoll的原理和区别

select&#xff0c;poll&#xff0c;epoll都是IO多路复用的机制。I/O多路复用就通过一种机制&#xff0c;可以监视多个描述符&#xff0c;一旦某个描述符就绪&#xff08;一般是读就绪或者写就绪&#xff09;&#xff0c;能够通知程序进行相应的读写操作。但select&#xff0c;…
阅读更多...
西瓜书学习笔记——k近邻学习（公式推导+举例应用）

西瓜书学习笔记——k近邻学习（公式推导+举例应用）

文章目录 算法介绍实验分析 算法介绍 K最近邻&#xff08;K-Nearest Neighbors&#xff0c;KNN&#xff09;是一种常用的监督学习算法&#xff0c;用于分类和回归任务。该算法基于一个简单的思想&#xff1a;如果一个样本在特征空间中的 k k k个最近邻居中的大多数属于某个类别…
阅读更多...
使用ngrok内网穿透

使用ngrok内网穿透

没有服务器和公网IP&#xff0c;想要其他人访问自己做好的网站&#xff0c;使用这款简单免费的内网穿透小工具——ngrok&#xff0c;有了它轻松让别人访问你的项目~ 一、下载ngrok 官网地址&#xff1a;ngrok | Unified Application Delivery Platform for Developers&#x…
阅读更多...
IP定位在社交行业应用

IP定位在社交行业应用

网络社交正成为当下最便捷的交友方式。社交服务平台使用IP地址数据服务&#xff0c;解析用户的地理位置和网络环境等信息&#xff0c;支撑精准配对和用户推荐&#xff0c;帮助用户在海量的网络社交用户中寻找性情相投的好友&#xff0c;建立有价值的社交关系。 匹配目标好友 通…
阅读更多...
未来电话呼叫技术的全球影响与社会变革----云微呼

未来电话呼叫技术的全球影响与社会变革----云微呼

随着科技的快速发展和全球通信网络的日益完善&#xff0c;未来电话呼叫技术将在全球范围内产生深远的影响&#xff0c;并引发社会结构、经济模式和文化交流等多个方面的变革。以下将更详细地探讨未来电话呼叫技术可能带来的全球影响与社会变革&#xff1a; 通信普及与数字鸿沟缩…
阅读更多...
人工智能(pytorch)搭建模型23-pytorch搭建生成对抗网络(GAN):手写数字生成的项目应用

人工智能(pytorch)搭建模型23-pytorch搭建生成对抗网络(GAN):手写数字生成的项目应用

大家好&#xff0c;我是微学AI&#xff0c;今天给大家介绍一下人工智能(pytorch)搭建模型23-pytorch搭建生成对抗网络(GAN):手写数字生成的项目应用。生成对抗网络&#xff08;GAN&#xff09;是一种强大的生成模型&#xff0c;在手写数字生成方面具有广泛的应用前景。通过生成…
阅读更多...
Mysql学习记录补充

Mysql学习记录补充

索引 在无索引情况下&#xff0c;就需要从第一行开始扫描&#xff0c;一直扫描到最后一行&#xff0c;我们称之为 全表扫描&#xff0c;性能很低。 如果我们针对于这张表建立了索引&#xff0c;假设索引结构就是二叉树&#xff0c;那么也就意味着&#xff0c;会对age这个字段…
阅读更多...
MySQL EXPLAIN查询执行计划

MySQL EXPLAIN查询执行计划

EXPLAIN 可用来查看SQL执行计划&#xff0c;常用来分析调试SQL语句&#xff0c;来使SQL语句达到更好的性能。 1 前置知识 在学习EXPLAIN 之前&#xff0c;有些基础知识需要清楚。 1.1 JSON类型 MySQL 5.7及以上版本支持JSON数据类型。可以将数组存为JSON格式的字符串&#…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023