当前位置: 首页 > news >正文

数据结构——实验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;}

测试结果截图:

相关文章:

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

一、实验内容 二、算法思想与算法实现 1、解题思想 &#xff08;1&#xff09;逆序创建链表La就是使用头插法创建一个链表&#xff0c;所谓头插法就是在创建链表时始终将新元素插入到头结点之后&#xff0c;而正序创建链表Lb就是使用尾插法创建一个链表&#xff0c;所谓尾插法…...

十分钟上手vue!

Vue 是一款用于构建用户界面的 JavaScript 框架。它基于标准 HTML、CSS 和 JavaScript 构建&#xff0c;并提供了一套声明式的、组件化的编程模型&#xff0c;帮助你高效地开发用户界面。无论是简单还是复杂的界面&#xff0c;Vue 都可以胜任。 一 vue.js的导入及使用 vue安装…...

day37WEB攻防-通用漏洞XSS跨站权限维持钓鱼捆绑浏览器漏洞

目录 XSS-后台植入 Cookie&表单劫持&#xff08;权限维持&#xff09; 案例演示 XSS-Flash 钓鱼配合 MSF 捆绑上线 1、生成后门 2、下载官方文件-保证安装正常 3、压缩捆绑文件-解压提取运行 4、MSF 配置监听状态 5、诱使受害者访问 URL-语言要适当 XSS-浏览器网马…...

【Java程序设计】【C00215】基于SSM的勤工助学管理系统(论文+PPT)

基于SSM的勤工助学管理系统&#xff08;论文PPT&#xff09; 项目简介项目获取开发环境项目技术运行截图 项目简介 这个一个基于SSM的勤工助学管理系统&#xff0c;本系统共分为三种权限&#xff1a;管理员、教师和学生 管理员&#xff1a;首页、个人中心、教师管理、学生管理…...

c#的反汇编对抗

文章目录 前记nim攻防基础FFI内存加载加解密、编码 后记C#类型转换表nim基础 前记 随便编写一个c#调用winapi并用vs生成dll,同时用csc生成exe using System; using System.Runtime.InteropServices; namespace coleak {class winfun{[DllImport("User32.dll")]publ…...

设计模式之框架源码剖析(实战+图解)

Java设计模式 1&#xff0c;概述 随着软件开发人员人数的增多&#xff0c;一些公司急需一些高端人才。作为一个高端人才&#xff0c;设计面向对象软件是必不可少的能力&#xff0c;而软件设计是需要很深的功力&#xff0c;设计模式就要求你必须掌握。 2&#xff0c;本章特色…...

SQL注入:sqli-labs靶场通关(1-37关)

SQL注入系列文章&#xff1a; 初识SQL注入-CSDN博客 SQL注入&#xff1a;联合查询的三个绕过技巧-CSDN博客 SQL注入&#xff1a;报错注入-CSDN博客 SQL注入&#xff1a;盲注-CSDN博客 SQL注入&#xff1a;二次注入-CSDN博客 ​SQL注入&#xff1a;order by注入-CSDN博客 …...

浙政钉(专有钉钉)

专有钉钉是浙政钉的测试版本&#xff0c;可在正式发布之前进行业务开发。 专有钉钉 原名政务钉钉 是高安全、强管控、灵活开放的面向大型组织专有独享的协同办公平台。支持专有云、混合云等多种方式灵活部署&#xff0c;以满足客户特定场景所需为目标&#xff0c;最大化以“平…...

【lesson2】定长内存池的实现

文章目录 介绍定长内存池的设计定长内存池的实现需要成员变量需要的成员函数定长内存池结构定长内存池Delete&#xff08;释放空间&#xff09;的实现定长内存池New&#xff08;申请空间&#xff09;的实现 定长内存池的实现完整版 介绍 作为程序员(C/C)我们知道申请内存使用的…...

C++迷宫游戏详解

个人主页&#xff1a;[PingdiGuo_guo] 收录专栏&#xff1a;[C干货专栏] 大家好呀&#xff0c;我是PingdiGuo_guo&#xff0c;今天我们来学习用C实现一个迷宫游戏。 目录 1.迷宫的具体步骤 1.1.迷宫的初始化 1.2.寻路算法 1.DFS算法 2.BFS算法 1.3.移动 2.总结 C迷宫游…...

java下载网络文件

/*** 下载文件** param fileId* param response* throws Exception*/ GetMapping("/downLoadFile") public void downLoadFile(Long fileId, HttpServletResponse response) throws Exception{// 根据文件ID查询文件路径FileDO fileDO fileService.get(fileId);// 定…...

大数据信用报告查询费用一般要多少钱?

一些不少朋友在申贷的时候被拒贷之后&#xff0c;得到的原因就是因为大数据不良被拒&#xff0c;这时候很多人都反过来查询自己的大数据信用报告&#xff0c;而查询的价格也是不少朋友都比较关注的&#xff0c;那大数据信用报告查询费用一般要多少钱呢?下面本文就为你介绍一下…...

【操作宝典】IntelliJ IDEA新建maven项目详细教程

目录 &#x1f33c;1. 配置maven环境 &#x1f33c;2. 创建maven项目 &#x1f33c;3. 创建maven项目完整示例 a. 导入spring boot环境 b. 修改maven配置 c. 下载jar包 d. 创建Java类 &#x1f33c;1. 配置maven环境 【安装指南】maven下载、安装与配置详细教程-CSDN博客…...

【Java程序设计】【C00196】基于(JavaWeb+SSM)的旅游管理系统(论文+PPT)

基于&#xff08;JavaWebSSM&#xff09;的旅游管理系统&#xff08;论文PPT&#xff09; 项目简介项目获取开发环境项目技术运行截图 项目简介 这是一个基于ssm的旅游平台 本系统分为前台、管理员2个功能模块。 前台&#xff1a;当游客打开系统的网址后&#xff0c;首先看到的…...

pdmodel从动态模型转成静态onnx

1.下载项目 git clone https://github.com/jiangjiajun/PaddleUtils.git 2.新建两个新的文件夹 第一个文件夹放两个必要文件 第二个文件夹可以设置为空&#xff0c;用来存放转换后的模型 如图&#xff1a; 3.在终端运行 python paddle/paddle_infer_shape.py --model_dir …...

git 如何修改仓库地址

问题背景&#xff1a;组内更换大部门之后&#xff0c;代码仓的地址也迁移了&#xff0c;所以原来的git仓库地址失效了。 虽然重新建一个新的文件夹&#xff0c;再把每个项目都git clone一遍也可以。但是有点繁琐&#xff0c;而且有的项目本地还有已经开发一半的代码&#xff0c…...

基于springboot篮球论坛系统源码和论文

首先,论文一开始便是清楚的论述了系统的研究内容。其次,剖析系统需求分析,弄明白“做什么”,分析包括业务分析和业务流程的分析以及用例分析,更进一步明确系统的需求。然后在明白了系统的需求基础上需要进一步地设计系统,主要包罗软件架构模式、整体功能模块、数据库设计。本项…...

【三维重建】运动恢复结构(SfM)

运动恢复结构是通过三维场景的多张图像&#xff0c;恢复出该场景的三维结构信息以及每张图片对应的摄像机参数。 欧式结构恢复(内参已知&#xff0c;外参未知) 欧式结构恢复问题&#xff1a; 已知&#xff1a;1、n个三维点在m张图像中的对应点的像素坐标 2、相机内参 求解&…...

Android Studio非UI线程修改控件——定时器软件

目录 一、UI界面设计 1、UI样式 2、XML代码 二、功能编写 1、定义 2、实现方法 3、功能实现 一、UI界面设计 1、UI样式 2、XML代码 <?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android…...

canvas的一些基础

在 Canvas 中&#xff0c;基本图形有两种&#xff1a;直线图形和曲线图形 直线图形&#xff1a;直线、矩形(描边矩形和填充矩形)、多边形 曲线图形&#xff1a;曲线和弧线&#xff08;弧线是圆的一部分&#xff0c;曲线则不一定&#xff0c;弧线上的每个点都具有相同的曲率&…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...