链表的合并，结点逆置，顺序表的高效划分（数据结构作业02）

目录

链表的合并

链表的结点逆置

 顺序表的高效划分

链表的合并

        已知两个递增有序的单链表A和B，分别表示两个集合。试设计一个算法，用于求出A与B的交集，并存储在C链表中。例如 : La = {2，4，6，8}；Lb = {4，6，8，10}；Lc = {4，6，8}。（要求上机实现完整程序代码、核心代码有注释，有运行结果）。 

        算法分析：遍历这两个链表A和B，使用两个指针，创建一个新的空链表C，然后比较当前节点的数据，如果相等，则将该数据添加到链表C中，然后同时移动两个链表的指针。如果不相等，则移动较小值所在链表的指针。这样可以确保只添加两个链表中共有的元素到链表C中。 

#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef struct LNode  
{ElemType data;struct LNode *next;		//指向后继结点
} LinkNode;		//创建单链表，头插法
LinkNode * createlist(int a[],int len) {//len是链表的长度LinkNode * L;LinkNode * s;L = (LinkNode *)malloc(sizeof(LinkNode));L -> next = NULL;//创建头结点，next指向为空for(int i = 0; i < len; i++) {s = (LinkNode*)malloc(sizeof(LinkNode));//创建结点ss -> data = a[i];s -> next = L -> next; //将s插入原首节点前，头结点后L -> next = s;}return L;
}//用于打印链表
//由于存储链表使用的是头插法，所以打印时我们现将链表存入一个数组
//再将那个数组反向输出就是我们需要的样子
void printlist(LinkNode *L) {LinkNode *p = L -> next;//让p指向首结点int arr[4];int len = 0,i = 0;while(p != NULL) {arr[i] = p -> data;p = p -> next;i++,len++;//只要没到尾结点就一直存入arr数组}len = len - 1;//最后多加了一次len所以要减去for(int i = len; i >= 0; i--) {printf("%d ",arr[i]);}printf("\n");
}//求两个链表的交集
LinkNode * intersection(LinkNode *a,LinkNode *b) {//传入a，b两个链表LinkNode *c;c = (LinkNode *)malloc(sizeof(LinkNode));LinkNode *r = c;//创建链表c的头结点,使用尾插法a = a -> next,b = b -> next;//让链表a和链表b指向它们的首结点LinkNode *p;while(a != NULL && b != NULL) {if(a -> data == b -> data) {//若二值相等，使用尾插法存入c中，并且让这两个指针都往后移动p = (LinkNode *)malloc(sizeof(LinkNode));p -> data = a -> data;r -> next = p;r = r -> next;a = a -> next,b = b -> next;}else {//由于创建列表时使用了尾插法，所以要变得相反//若二值不相等则值更大的往后移一格if(a -> data > b -> data)a = a -> next;if(b -> next > a -> next)b = b -> next;}}r -> next = NULL;//尾插法注意要让尾结点的next域置为空return c;
}int main() {//创建链表aint a[4];a[0] = 2,a[1] = 4,a[2] = 6,a[3] = 8;LinkNode *la;la = createlist(a,4);printf("链表a为：");printlist(la);//创建链表bint b[4];b[0] = 4,b[1] = 6,b[2] = 8,b[3] = 10;LinkNode *lb;lb = createlist(b,4);printf("链表b为：");printlist(lb);//得到链表la和lb的交集lcLinkNode *lc = intersection(la,lb);printf("链表a和链表b的交集链表c为：");printlist(lc);
}

 

链表的结点逆置

        假设有一个带头结点的单链表L=（2，4，6…，20）。设计一个算法将所有结点逆置，即：L=（20，18，…，2）。（要求要求上机实现完整程序代码、核心代码有注释，有运行结果） 

        算法分析：可以使用尾插法建立第一个链表，再写一个逆置函数，传入这个链表，在函数里面改变当前节点的指针使其指向其前一个节点，以此类推，直到遍历完所有的节点。 

#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef struct LNode  
{ElemType data;struct LNode *next;		//指向后继结点
} LinkNode;		//创建单链表，尾插法
LinkNode * createlist(int a[],int len) {LinkNode *L,*r,*s;L = (LinkNode*)malloc(sizeof(LinkNode));//L为头结点r = L;for(int i = 0; i < len; i++) {s = (LinkNode *)malloc(sizeof(LinkNode));s -> data = a[i];r -> next = s;r = r -> next;//将数据存入s中并且让r的next指向它//再将r向后移动一格}r -> next = NULL;//记得要让尾结点的next域为空return L;
}//打印单链表
void printlist(LinkNode * l) {l = l -> next;//让l指向它的首结点while(l != NULL) {printf("%d ",l -> data);l = l -> next;}printf("\n");
}//打印逆置后的单链表
void printreverselist(LinkNode *l) {//采用这种逆置方法后不用指向首结点，此时l即为首结点while(l != NULL) {printf("%d ",l -> data);l = l -> next;}printf("\n");
}//逆置链表函数
LinkNode * reverselist(LinkNode * head) {//创建新的头结点pLinkNode *p;LinkNode *l,*r;l = head -> next;//l表示left，是左边的指针//r表示right，是右边的指针//让s指向首结点，头结点的next指向空head -> next = NULL;//核心代码while(l != NULL) {r = l -> next;//保存当前节点的下一个节点l -> next = p;//将当前节点的next指向前一个节点p = l;//更新p为当前节点l = r;//移动到下一个节点}return p;
}int main() {//创建逆置前的链表int a[100];int n = 1;for(int i = 0; i < 10; i++) {a[i] = 2 * n;n++;}LinkNode *l = createlist(a,10);printf("逆置前的链表为：");printlist(l);//逆置链表l = reverselist(l);printf("逆置后的链表为：");printreverselist(l);
}

 

 顺序表的高效划分

        对有n个整形元素的顺序表以第一个元素为基准进行高效划分，将所有大于该基准的所有元素放在该基准的右边；将所有小于等于该基准的所有元素放在该基准的左边。例如对于线性表（17,2,3,5,4,20,1,18,19,20,21,6,22）要求要求上机实现完整程序代码、核心代码有注释，有运行结果）

#include <stdio.h>
#include <malloc.h>
#define MaxSize 50
typedef int ElemType; 
typedef struct 
{	int data[MaxSize];		//存放顺序表元素int length;					//存放顺序表的长度
} SqList;						//顺序表的类型//建立顺序表
SqList * createlist(int a[],int len) {SqList *l;l = (SqList *)malloc(sizeof(SqList));int k = 0;//k用于记录顺序表的长度for(int i = 0; i < len; i++) {l -> data[i] = a[i];k++;}l -> length = k;return l;
}void partitionlist(SqList * list) {int l = 0,r = list -> length - 1;//让l指向头，r指向尾int base = list -> data[0];//将第一个数设置为基准while(l < r) {while(r > l && list -> data[r] > base)r--;//先从右往左遍历，找到第一个小于等于base的数list -> data[l] = list -> data[r];//将这个数放入l的位置上while(l < r && list -> data[l] <= base)l++;//再从左往右，找到第一个大于base的数list -> data[r] = list -> data[l];//将这个数放在r的位置上}list -> data[l] = base;//最后把这个数放在位置l处
}//打印顺序表
void printlist(SqList *l) {for(int i = 0; i < l -> length; i++) {printf("%d ",l -> data[i]);}printf("\n");
}int main() {//创建顺序表int arr[100];arr[0] = 17;arr[1] = 2;arr[2] = 3;arr[3] = 5;arr[4] = 4;arr[5] = 20;arr[6] = 1;arr[7] = 18;arr[8] = 19;arr[9] = 20;arr[10] = 21;arr[11] = 6;arr[12] = 22;SqList *l;l = createlist(arr,13);printf("初始的顺序表为：");printlist(l);//进行高效划分partitionlist(l);printf("高效划分后的顺序表为：");printlist(l);}

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

如何使用命令行快速下载Google Drive/OneDrive大文件

如何使用命令行快速下载Google Drive/OneDrive大文件

OneDrive OneDrive使用wget下载会出现403 forbidden&#xff0c;可通过下面方法下载。 浏览器右键进入检查界面&#xff0c;选择netowork&#xff0c;搜索download.aspx&#xff0c;然后在待下载文件处点击下载&#xff0c;即可出现下载链接&#xff0c;复制为cURL即可下载。…
阅读更多...
【Prompt Engineering：ReAct 框架】

【Prompt Engineering：ReAct 框架】

ReAct 框架 从 Yao 等人&#xff0c;2022(opens in a new tab) 引入了一个框架&#xff0c;其中 LLMs 以交错的方式生成 推理轨迹 和 任务特定操作 。 生成推理轨迹使模型能够诱导、跟踪和更新操作计划&#xff0c;甚至处理异常情况。操作步骤允许与外部源&#xff08;如知识…
阅读更多...
硬件工程师笔试面试——开关

硬件工程师笔试面试——开关

目录 11、开关 11.1 基础 开关原理图 开关实物图 11.1.1 概念 11.1.2 常见的开关类型及其应用 11.2 相关问题 11.2.1 开关的工作原理是什么? 11.2.2 在设计一个电子系统时，如何选择最适合的开关类型? 11.2.3 不同类型的开关在实际应用中有哪些优势和局限性? 11.…
阅读更多...
Rust GUI框架Tauri V1 入门

Rust GUI框架Tauri V1 入门

文章目录 Tauri介绍Vite开始创建 Rust 项目 调用指令window.__TAURI_INVOKE__.invoke is undefined 问题 参考资料JavaScript 模块Vue 框架Vue RouteviteNuxt gitignore文件上传到csdn gitcode网站端本地端 gitcode发布 Tauri介绍 Tauri是一款用Rust构建的开源框架&#xff0c…
阅读更多...
Linux操作系统面试题记录

Linux操作系统面试题记录

一、进程与线程 1.并发和并行的区别 并发&#xff1a;一个cpu处理器处理多个任务&#xff1b; 并行&#xff1a;多个cpu处理器处理多个任务&#xff1b; 2.进程和线程是什么&#xff1f;区别&#xff1f;何时用线程何时用进程&#xff1f; Linux中其实没有进程线程之分&…
阅读更多...
少儿编程小游戏 —— Scratch 火柴人勇者传说

少儿编程小游戏 —— Scratch 火柴人勇者传说

在线玩&#xff1a;Scratch动作冒险游戏 – 火柴人勇者传说免费下载-小虎鲸Scratch资源站 在少儿编程的世界里&#xff0c;创造属于自己的游戏是一件既有趣又富有挑战的事情。而今天要介绍的游戏——《火柴人勇者传说》&#xff0c;便是一个充满冒险精神的作品&#xff0c;专为…
阅读更多...
【PCB工艺】表面贴装技术中常见错误

【PCB工艺】表面贴装技术中常见错误

系列文章目录 1.元件基础 2.电路设计 3.PCB设计 4.元件焊接 5.板子调试 6.程序设计 7.算法学习 8.编写exe 9.检测标准 10.项目举例 11.职业规划 文章目录 1、什么是SMT和SMD2、表面贴装技术的优势是什么&#xff1f;3、通孔和表面贴装技术之间的区别是什么&#xff1f;4、焊…
阅读更多...
MySQL-DQL（数据查询语言）

MySQL-DQL（数据查询语言）

数据查询语言(DQL-Data Query Language) 代表关键字&#xff1a;select MySQL语句执行顺序 1、基础操作 1.1 启动服务 a.手动启动 我的电脑->右键->管理->服务->mysql->右键启动/启动 b.命令方式 在管理员模式下运行cmd,执行如下操作&#xff1a; net sta…
阅读更多...
轻量桌面应用新星：Electrico，能否颠覆Electron的地位？

轻量桌面应用新星：Electrico，能否颠覆Electron的地位？

在桌面应用开发的世界里，Electron曾经是一位风云人物。它让开发者可以用熟悉的Web技术构建跨平台应用，但它的重量级体积和系统资源的高消耗一直让人头疼。现在，一个新工具悄然登场，试图解决这些问题——Electrico，一个轻量版的桌面应用开发框架。 10MB取代数百MB，你不…
阅读更多...
计算机人工智能前沿进展-大语言模型方向-2024-09-16

计算机人工智能前沿进展-大语言模型方向-2024-09-16

计算机人工智能前沿进展-大语言模型方向-2024-09-16 1. Securing Large Language Models: Addressing Bias, Misinformation, and Prompt Attacks B Peng, K Chen, M Li, P Feng, Z Bi, J Liu, Q Niu - arXiv preprint arXiv:2409.08087, 2024 保护大型语言模型&#xff1a;…
阅读更多...
Solid Converter PDF10.1安装教程

Solid Converter PDF10.1安装教程

软件介绍 Solid Converter PDF是一套专门将PDF文件转换成word的软件&#xff0c;除了转换成word文件外&#xff0c;还可以转换成RTF以及Word XML文件。除此之外&#xff0c;它还有一个图片撷取功能&#xff0c;可以让我们]将PDF档里的图片撷取出来&#xff0c;以及将PDF档里的…
阅读更多...
【计算机基础】关于存储的各种概念

【计算机基础】关于存储的各种概念

综述 在了解存储设备的过程中涉及到了很多的概念&#xff0c;本文将一一说明。 在介绍存储设备的时候会出现很多概念&#xff0c;这里简单说明下。 总线&#xff1a;这里指的是CPU与存储设备的链路。目前有SATA、PCIe、SAS等。协议&#xff1a;这里指的是CPU与存储设备之间约…
阅读更多...
二、Servlet

二、Servlet

文章目录 1. Servlet技术1.1 什么是Servlet1.2 手动实现 Servlet 程序1.3 url 地址到 Servlet 程序的访问1.4 Servlet 的生命周期1.5 GET 和 POST 请求的分发1.6 通过继承 HttpServlet 实现 Servlet 程序1.7 使用 IDEA 创建 Servlet 程序1.8 Servlet 类的继承体系 2. ServletCo…
阅读更多...
OpenFeign接口调用日志

OpenFeign接口调用日志

一、介绍 在开发或测试环境中&#xff0c;需要更多的调试信息&#xff1b;在通过 Spring Cloud OpenFeign 调用远程服务的接口时&#xff0c;可能需要记录接口调用的日志详情&#xff0c;比如&#xff1a;请求头、请求参数、响应等。 Spring Cloud OpenFeign 打印 FeignClien…
阅读更多...
Golang | Leetcode Golang题解之第413题等差数列划分

Golang | Leetcode Golang题解之第413题等差数列划分

题目&#xff1a; 题解&#xff1a; func numberOfArithmeticSlices(nums []int) (ans int) {n : len(nums)if n 1 {return}d, t : nums[0]-nums[1], 0// 因为等差数列的长度至少为 3&#xff0c;所以可以从 i2 开始枚举for i : 2; i < n; i {if nums[i-1]-nums[i] d {t}…
阅读更多...
java四种内置线程池介绍

java四种内置线程池介绍

目录 java线程池概述Executor接口ExecutorService接口 工具类快速创建线程池FixedThreadPoolSingleThreadExecutorCachedThreadPoolScheduledThreadPool内置线程池总结 java线程池概述 Executor框架是Java提供的一个用于处理并发任务的工具。它简化了线程管理&#xff0c;提供…
阅读更多...
用Python实现时间序列模型实战——Day 24: 时间序列中的贝叶斯方法

用Python实现时间序列模型实战——Day 24: 时间序列中的贝叶斯方法

一、学习内容 1. 贝叶斯时间序列分析的基本概念 贝叶斯方法基于贝叶斯统计&#xff0c;通过对数据的先验分布和似然函数进行推断&#xff0c;更新为后验分布。贝叶斯时间序列分析使用贝叶斯推断处理时间序列中的不确定性&#xff0c;适合处理复杂、不确定性高的时间序列问题。…
阅读更多...
【RabbitMQ】可靠性传输

【RabbitMQ】可靠性传输

概述 作为消息中间件来说&#xff0c;最重要的任务就是收发消息。因此我们在收发消息的过程中&#xff0c;就要考虑消息是否会丢失的问题。结果是必然的&#xff0c;假设我们没有采取任何措施&#xff0c;那么消息一定会丢失。对于一些不那么重要的业务来说&#xff0c;消息丢失…
阅读更多...
中秋佳节，月圆人团圆

中秋佳节，月圆人团圆

文章目录 历史和文化起源与演变文化内涵习俗与活动 军事中秋节的军事背景中秋节的军事象征现代军营中的中秋节 月圆之夜&#xff0c;共赏婵娟传统文化&#xff0c;薪火相传团圆时刻&#xff0c;温馨满溢展望未来&#xff0c;祈愿美好 在这个金秋送爽、丹桂飘香的季节里&#xf…
阅读更多...
web基础—dvwa靶场（五）File Upload

web基础—dvwa靶场（五）File Upload

File Upload(文件上传) 上传的文件对 web 应用程序来说是一个巨大的风险&#xff0c;许多攻击的第一步是上传攻击代码到被攻击的系统上&#xff0c;然后攻击者只需要找到方法来执行代码即可完成攻击。也就是是说&#xff0c;文件上传是攻击者需要完成的第一步。 不受限制的文件…
阅读更多...
最新文章

Copyright @ 2022~2023