当前位置：首页 > 编程日记 > 正文

C++的多个有序链表合并

编程日记 2024-04-23 03:30:00

已知k个已排序链表头节点指针，将这k个链表合并，合并后仍为有序的，返回合并后的头节点
如下三个链表：
在这里插入图片描述
合并后的结果如下：

方法一（STL sort算法进行排序）：

先将输入的排序链表插入一个迭代器中，vector数组中国呢
直接对数组中的链表节点进行按值排序即可

实现算法如下,最终实现源码见文末:

bool cmp(Data *A, Data *B) {return A->data < B->data;
}
Data *merge_list2(vector<Data*> &list) {/*如果传入的链表数组大小为0，则返回空*/if(list.size() == 0) {return NULL;}/*传入的数组大小为1，则返回第一个链表头节点*/if(list.size() == 1) {return list[0];}/*遍历所有的链表，并将每个链表的所有节点插入一个vector中*/vector<Data*> result;for (int i = 0;i < list.size(); ++i) {while(list[i]) {result.push_back(list[i]);list[i] = list[i] -> next;}}/*对vector按照升序排序，其中排序规则可以由cmp函数自定义指定*/sort(result.begin(),result.end(),cmp);return result[0];
}

方法二（分治归并）：
使用合并两个有序链表的实现，对所有链表进行两两合并至仅剩下两个，最后合并最后的两个链表,关于合并两个有序链表可以参考C语言的有序单链表合并
这里面的思想就是分而治之，将整体分割为一个个独立的个体分别处理，再进行最后的整合。
算法使用递归方式实现如下，最终实现源码见文末:

Data *merge_list(vector<Data *> &list) {/*如果传入的链表数组大小为0，则返回空*/if(list.size() == 0) {return NULL;}/*传入的数组大小为1，则返回第一个链表头节点*/if (list.size() == 1) {return list[0];}/*将链表分为两部分，分别放入不同的链表结构*/int mid = list.size() / 2;int i;vector <Data *> sub_list1,sub_list2;for (i = 0; i < mid; ++i) {sub_list1.push_back(list[i]);}for (i = mid; i < list.size(); ++i) {sub_list2.push_back(list[i]);}/*分别进行递归处理*/Data *list1 = merge_list(sub_list1);Data *list2 = merge_list(sub_list2);/*将以上两部分处理的最终结果返回，进行两个有序链表的合并*/return merge_two_list(list1,list2);
}

以上两个过程实现代码如下：

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>using namespace std;typedef struct LinkList {int data;struct LinkList *next;
}Data;
/*打印链表节点数值*/
void print_list(Data *head) {while (head) {printf("%d ",head->data);head = head -> next;}printf("\n");
}
/*尾插法创建链表*/
Data *insert_tail(Data *head, int n) {head = (Data *)malloc(sizeof(Data));head->next = NULL;Data *r = head;while(n--) {Data *p = (Data *)malloc(sizeof(Data));int data;scanf("%d", &data);p->data = data;r->next = p;r = p;p->next = NULL;}return head->next;
}
/*合并两个有序链表算法实现*/
Data *merge_two_list(Data *headA, Data *headB) {Data p;p.data = 0;p.next = NULL;Data *result = &p;while (headA && headB) {if (headA->data < headB->data) {result->next = headA;headA = headA->next;} else {result->next = headB;headB = headB ->next;} result = result -> next;}if (headA == NULL) {result ->next = headB;}    if (headB == NULL) {result ->next = headA;}return p.next;
}
/*分治归并算法实现的链表合并*/
Data *merge_list(vector<Data *> &list) {if(list.size() == 0) {return NULL;}if (list.size() == 1) {return list[0];}int mid = list.size() / 2;int i;vector <Data *> sub_list1,sub_list2;for (i = 0; i < mid; ++i) {sub_list1.push_back(list[i]);}for (i = mid; i < list.size(); ++i) {sub_list2.push_back(list[i]);}Data *list1 = merge_list(sub_list1);Data *list2 = merge_list(sub_list2);return merge_two_list(list1,list2);
}
/*控制排序的规则，当前为升序*/
bool cmp(Data *A, Data *B) {return A->data < B->data;
}
/*排序算法实现链表的链表*/
Data *merge_list2(vector<Data*> &list) {if(list.size() == 0) {return NULL;}if(list.size() == 1) {return list[0];}vector<Data*> result;for (int i = 0;i < list.size(); ++i) {while(list[i]) {result.push_back(list[i]);list[i] = list[i] -> next;}}sort(result.begin(),result.end(),cmp);return result[0];
}int main() {vector<Data*> list;printf("input the num of the construct list \n");int num;scanf("%d",&num);for (int i = 0; i < num; ++i){Data *p;printf("construct the %d list:\n",i+1);list.push_back(insert_tail(p,3)); //尾插法构造三个节点的链表}printf("merget the mulity list with method 1 is \n");Data *result = merge_list(list);print_list(result);printf("merge the mulity list with method 2 is \n");Data *result2 = merge_list2(list);print_list(result2);return 0;
}

最终输出如下

input the num of the construct list 
4  
construct the 1 list:
1 2 3
construct the 2 list:
3 4 5
construct the 3 list:
4 5 6
construct the 4 list:
6 7 8
merget the mulity list with method 1 is 
1 2 3 3 4 4 5 5 6 6 7 8 
merget the mulity list with method 2 is 
1 2 3 3 4 4 5 5 6 6 7 8

https://www.dkcj.cn/info/5089.html

c# 垃圾回收是引用类型而言的

c# 垃圾回收是引用类型而言的转载于:https://www.cnblogs.com/C-CHERS/p/3646387.html

编程日记2024/04/23 03:00:00

java unlimited_具有无限参数的Java方法(Java method with unlimited arguments)

具有无限参数的Java方法(Java method with unlimited arguments)Spring框架使用方法，您可以根据需要传递尽可能多的参数。我想写一个函数，也可以采取无限量的数据。这个功能是如何调用的，以便我可以阅读它。或者我该如何定义它？…

编程日记2024/04/23 02:30:00

2013-3-10日记

2019独角兽企业重金招聘Python工程师标准>>> 今天星期日，在家早上看NBA，中午去买菜，下午在家种花，晚上看CBA。转载于:https://my.oschina.net/guanyun/blog/112801

编程日记2024/04/23 02:00:00

P1522 牛的旅行

这题挺好……有几个坑……（反正我都跳进去了） 对于新的更大的图，由于求的是最小连接边，所以它的值可能小于之前单独一个图的最长的最短路…… 所以之后的值应该取个max（emmm……） 所以第一次我只拿了70。。…

编程日记2024/04/23 01:30:00

C++ algorithm的sort函数总结

sort函数 sort对给定区间进行排序，支持各种数据类型，迭代器，结构体，自定义排序规则stable_sort 对给定区间进行稳定排序,且可保证相等元素的原本相对次序在排序后保持不变partial_sort 对给定区间部分元素排序partial_sort_copy …

编程日记2024/04/23 01:00:00

加密解密php,PHP实现的加密解密处理类

本文实例讲述了PHP实现的加密解密处理类。分享给大家供大家参考，具体如下：/* 版权协议： GPL (The GNU GENERAL PUBLIC LICENSE Version 2, June 1991)------------------------------------------------------------ 文件名称：cls…

编程日记2024/04/23 00:30:00

技术人生：本周改进计划

分配时间学习领域知识和管理知识。更慎重的命名。注意交流的态度和方式（特别是在出现不同意见的时候）。对待任何工作内容都不能应付了事。转载于:https://www.cnblogs.com/happyframework/p/3695596.html

编程日记2024/04/23 00:00:00

linux下batik-rasterizer.jar生成图片中文乱码

为什么80%的码农都做不了架构师？>>> 发现原来jdk5.0在linux下和以前的版本还不一样，默认不支持中文字体的。得手动去搞一个fontconfig配置， 此文件在$JAVA_HOME/jre/lib/下， 果然有一大堆fontconfig.XX.properties, 官…

编程日记2024/04/22 23:30:00

小记，springboot项目中自己常用的logback配置文件

把配置文件放到resources这个classpath目录即可生效，日志输入样式是从springboot中日志配置中copy过来的, 其他常用配置不做过多注释了。 logback-spring.xml <?xml version"1.0" encoding"UTF-8"?> <configuration><conversi…

编程日记2024/04/22 23:00:00

s-sar命令（System Activity Reporter系统活动情况报告）

文章目录前言语法格式查看CPU使用情况保存统计结果到文件中查看磁盘平均负载和队列长度查看内存使用情况查看系统swap分区情况查看IO和传递速率查看磁盘使用情况输出inode、文件和其他内核表的信息统计网络信息查看网络接口信息网络设备通信失败信息统计socket连接信息TCP连接的…

编程日记2024/04/22 22:30:00

基础设计模式：单例模式+工厂模式+注册树模式

单例模式： 通过提供自身共享实例的访问，单例设计模式用于限制特定对象只能被创建一次。使用场景： 一般数据库实例都会用单例模式实现： 单例设计模式就是要一个类只能实例化一个对象。要想让一个类只能实例化一个对象&#xff0…

编程日记2024/04/22 22:00:00

mac 配置 php,mac如何配置php环境

一、启动Apache两种方法1、打开网络共享打开"系统偏好设置"->"共享"，在"互联网共享"那一项前面打√。2、打开终端，输入sudo apachectl start这时需要输入密码，输入电脑密码即可,然后输入sudo apachectl &am…

编程日记2024/04/22 21:30:00

LinkedBlockingQueue应用实例

并发库中的BlockingQueue是一个比较好玩的类，顾名思义，就是阻塞队列。该类主要提供了两个方法put()和take()，前者将一个对象放到队列中，如果队列已经满了，就等待直到有空闲节点；后者从head取一个对象&#…

编程日记2024/04/22 21:00:00

s-stat 查看文件或者文件系统的状态信息

命令用法 stat [OPTION]... FILE... -L 查看链接文件-f 查看文件系统信息，而非文件信息-c --format%a 支持使用格式化字符串输出结果，支持\n,\t等转义字符,详细格式化情况使用man stat查看--printfFORMAT 支持格式化输出-t 以简洁的方式输出结果常用…

编程日记2024/04/22 20:30:00

梦想的地方！地球上最值得去的20个地方【组图】

如果你是一个热爱大自然的人你肯定会喜欢这个集合。地球上有太多的地方和风景值得我们这辈子至少要去看一次。大多数自然摄影师喜欢没有人出现在他们的照片中，他们想获得纯净、完美的风景，没有人类的影响。这篇文章展示了20个地球上最惊人的地方的照片&a…

编程日记2024/04/22 20:00:00

php读取js验证码,PHP + JS 实现验证码功能

验证码是网站防止恶意攻击最常用的手段，怎样使用PHP来生成验证码呢，下面就直接上例子首先给出生成验证码的PHP代码：将上面的代码放在一个单独的php文件中，如：auth_code.php，最好不要讲验证码的代码放到其他…

编程日记2024/04/22 19:30:00

poj1692

题意：两个数列，第一行的数字可以和第二行的数字连线。连线有如下条件，被连上的两数字必须相等，且每个数字只能连一条线，每条连线必须与且仅与另一条连线相交，相交两连线上的数字不能相等。问最多能连多少条…

编程日记2024/04/22 19:00:00

MongoDB 学习使用

博客教程： https://jingyan.baidu.com/article/dca1fa6f0428a4f1a440522e.html转载于:https://www.cnblogs.com/harlem/p/10148315.html

编程日记2024/04/22 18:30:00

C语言的双向链表头插法和尾插法，指定节点删除

文章目录前言头插法尾插法删除节点测试代码如下前言双向链表和单链表的唯一区别就是多个一个指针域而已，该指针域可以访问链表的上一个节点。关于构造双向链表的过程我们常见的有两种方法，和单链表一样：头插法和尾插法。头插法&#xff…

编程日记2024/04/22 18:00:00

机房收费系统之uml图——初版

说起uml图，在我心中最难的当属类图无疑。虽然敲了三层的小例子，但真正让把三层和uml图结合起来，并且还要考虑设计模式的时候，总是让人有一种无从下手的感觉，不过还好，通过这半个多月的思考与探索&#xff0…

编程日记2024/04/22 17:30:00

php扩展开发中文教程.pdf,PHP扩展开发系列教程-1

PHP的核心由两部分组成。最底层是zend引擎(ZE)。另一部分是PHP内核，她绑定了SAPI层(Server Application Programming Interface).###扩展的内存管理_____________________________________________________________1 依赖ZE内部管理2 自己写内存管理##创建基础hello…

编程日记2024/04/22 17:00:00

2019独角兽企业重金招聘Python工程师标准>>> 1.简介 Node.js is a platform built on Chromes JavaScript runtime for easily building fast, scalable network applications. Node.js uses an event-driven, non-blocking I/O model that makes it light…

编程日记2024/04/22 16:30:00

Android Wifi 主动扫描被动扫描

介绍主动扫描，被动扫描以及连接的wifi的扫描过程参考文档《802.11无线网络权威指南》《80_Y0513_1_QCA_WCN36X0_SOFTWARE_ARCHITECTURE.pdf》(高通文档) 被动扫描（passive scanning） 可以节省电池的电力，因为不需要传送任何信号…

编程日记2024/04/22 16:00:00

C语言的单链表实现队列

队列是一种FIFO（先入先出）的数据结构 C的STL std::queue q; 相关的队列操作，包括 q.empty() 判读队列是否为空 q.front() 返回队列的首元素 q.back() 返回队列的末尾元素 q.pop() 弹出队列的头部 q.push(x) 将x添加至队列 q.size() 返回队列…

编程日记2024/04/22 15:30:00

hdu 1561 The more, The Better_树状dp

题目链接题意：给你一棵树，各个节点都有价值（除根节点），从根节点出发，选择m个节点，问最多的价值是多小。思路：很明显是树状dp，遍历树时背包最优价值，dp[i][k…

编程日记2024/04/22 15:00:00

java课设推荐,《Java程序设计》课程设计报告推荐.docx

《Java程序设计》课程设计报告推荐《Java程序设计》课程设计报告2015—2016学年第一学期设计题目整数进制转换学生姓名邹晓刚学号0专业班级信管1303指导教师姜国权 2015年12月31日整数进制转换设计任务书1.1题目与要求本人计划编写一个十进制整数转换为二八十六进制整数的进…

编程日记2024/04/22 14:30:00

解析Erlang日志组件lager的lager_transform模块

为什么80%的码农都做不了架构师？>>> 使用 lager 的时候，在编译应用的时候，需要加入选项 {parse_transform, lager_transform} erlc 会在编译你的项目源代码的时候，把生成的 abstract format forms 交给 lager_transfo…

编程日记2024/04/22 14:00:00

Session 常见操作

对于敏感、重要的信息，建议要存储在服务器端（Session是存储在服务器端的），不能存储在浏览器中，如用户名、余额、等级、验证码等信息 Session依赖于Cookie session数据的获取 session:请求上下文对象，用于处…

编程日记2024/04/22 13:30:00

C++的STL队列实现栈

使用C的队列STL实现一个栈的数据结构实现以下四个函数： 1.push(x) : 将元素x压入栈中 2.pop() : 弹出(移除)栈顶元素 3.top() : 返回栈顶元素 4.empty() : 判断栈是否是空队列的数据结构为先入先出，栈的数据结构为先入后出； 即队列的元素顺…

编程日记2024/04/22 13:00:00

PHP实现XML传输

sendXML.php  <?php$xml_data <xml>...</xml>;//发送的xml $url http://localhost/getXML.php;//接收XML地址$header "Content-type: text/xml";//定义content-type为xml $ch curl_init(); //初始化curl curl_setop…

编程日记2024/04/22 12:30:00