C++实现接两个链表实例代码

 C++实现接两个链表实例代码

有以ha为头结点的链表，元素个数为m；以hb为头结点的链表，元素个数为n。现在需要你把这两个链表连接起来，并使时间复杂度最小，请分析并实现。

思路：

很简单的链表操作的题目，逆序头部插入，并将长度较长的一方接到较短的后面，时间复杂度为O(min(m,n))，注意free使用的地点！。

实例代码：

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef int ElemType; 

typedef struct Node
{
  ElemType data;
  struct Node *next;
}Lnode,*LinkList; 

//打印
void print(LinkList &head)
{
  LinkList plist=head->next;
  while(plist!=NULL)
  {
    cout<<plist->data<<" ";
    plist=plist->next;
  }
  cout<<endl;
} 

//逆序输入链表
void CreateList(LinkList &L,int m)
{
  LinkList p;
  L=(LinkList)malloc(sizeof(Node));
  L->next=NULL;
  cout<<"逆序输入元素，空格分隔:"<<endl;
  for(int i=m;i>0;--i)
  {
    p=(LinkList)malloc(sizeof(Node));
    cin>>p->data;
    p->next=L->next;
    L->next=p;
  }
  print(L);
} 

//连接链表
void Combine(LinkList &ha,int m,LinkList &hb,int n,LinkList &hc)
{
  LinkList selectMin;
  hc=(LinkList)malloc(sizeof(Node));
  int flag=0;
  if(m>n)
  {
    selectMin=hb;
    flag=1; //ha在后面
  }
  else
  selectMin=ha; 

  while(selectMin->next!=NULL)
  selectMin=selectMin->next; 

  if(flag)
  {
    selectMin->next=ha->next;
    hc=hb;
    free(ha);//notice
  }
  else
  {
    selectMin->next=hb->next;
    hc=ha;
    free(hb);
  }
  cout<<"合并后的链表为："<<endl;
  print(hc);
} 

void Destory(LinkList &hc) //仅释放hc即可
{
  LinkList temp;
  while(hc!=NULL)
  {
    temp=hc;
    hc=hc->next;
    free(temp);
  }
}
int main()
{
  int m,n;
  cout<<"请输入以ha为head节点链表的元素个数："<<endl;
  cin>>m;
  LinkList ha,hb,hc;
  CreateList(ha,m);
  cout<<"请输入以hb为head节点链表的元素个数："<<endl;
  cin>>n;
  CreateList(hb,n);
  Combine(ha,m,hb,n,hc); 

  Destory(hc);
  return 0;
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

赞 (0)

相关推荐

  • C++实现的链表类实例

    本文实例讲述了C++实现的链表类.分享给大家供大家参考.具体如下: #include <iostream> using namespace std; class linklist { private: struct node { int data; node *link; }*p; public: linklist(); void append( int num ); void add_as_first( int num ); void addafter( int c, int num );

  • C++利用静态成员或类模板构建链表的方法讲解

    C++利用静态成员或类模板构建链表的方法讲解

    直接上代码了,说明看注释就可以: 利用静态成员构建链表 #include <IOSTREAM.H> class Node { public: Node(int val, Node* next):val(val),next(next){} //~Node(){cout<<"del "<<val<<endl;} static void showAll();//打印全部节点的值 static void insertHead(int);//头插

  • C++ 数据结构链表的实现代码

    C++ 数据结构链表的实现代码

    C++ 链表 之前一直没怎么在意C++中的链表,但是突然一下子让自己写,就老是出错.没办法,决定好好恶补一下该方面的知识,也为今后的数据结构大下个良好的基础,于是我总结出以下几点,有些地方可能不正确,还望大家不吝赐教,旨在共同进步. 总结: 1.链表List的基本单元是节点Node,因此想要操作方便,就必须为每一步打好基础,Node的基本结构如下: class Node{ public: int data; Node *next; Node(int da=0,Node *p=NULL){ thi

  • 关于双向链表的增删改查和排序的C++实现

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. 由于双向链表可以方便地实现正序和逆序两个方向的插入.查找等功能,在很多算法中经常被使用, 这里用C++构造了一个双向链表,提供了对双向链表的插入.查找.删除节点.排序等功能,其中排序提供了插入排序和冒泡排序两种方式 #include<iostream> using namespace std;

  • C++语言实现线性表之链表实例

    本文实例讲述了C++语言实现线性表之链表实现方法.分享给大家供大家参考.具体分析如下: 插入.删除结点的代码有点多,但这样提高了代码的可读性,且不增加时间复杂度,不会影响程序性能 #include <iostream> using namespace std; template<typename T> class CList; template<class T> class Node { friend CList<T>; private: T m_data;

  • C++中单链表的建立与基本操作

    C++中单链表的建立与基本操作

    准备数据 准备在链表操作中需要用到的变量及数据结构 示例代码如下: 复制代码 代码如下: struct Data   //数据结点类型 { string key;  //关键字  string name; int age;};struct CLType  //定义链表结构 { Data nodeData; Data *nextNode;}; 定义了链表数据元素的类型Data以及链表的数据结构CLType.结点的具体数据保存在一个结构Data中,而指针nextNode用来指向下一个结点. 我们可以

  • C++循环链表之约瑟夫环的实现方法

    本文实例形式展示了C++实现循环链表中约瑟夫环的方法,分享给大家供大家参考之用.具体方法如下: 主要功能代码如下: #include <iostream> using namespace std; typedef struct student { int data; struct student* next; }node,*LinkList; //约瑟夫环 void printfList(LinkList head){ LinkList p=head; if (head!=NULL) { do

  • C++将二叉树转为双向链表及判断两个链表是否相交

    C++将二叉树转为双向链表及判断两个链表是否相交

    把二叉查找树转变成排序的双向链表 例如: 转换成双向链表 4=6=8=10=12=14=16 struct BSTreeNode { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node }; 首先阐述下二叉排序树: 它首先要是一棵二元树,在这基础上它或者是一棵空树:或者是具有下列性质的二元树: (1)若左子树不空

  • 浅析C++中单链表的增、删、改、减

    浅析C++中单链表的增、删、改、减

    首先是是一个简单的例子,单链表的建立和输出.程序1.1 复制代码 代码如下: #include<iostream>#include<string>using namespace std;struct Student{ string name; string score; Student *next;//定义了指向Candidate类型变量的指针};int main(){ int n;// cout<<"请输入学生的总数:"; cin>>n

  • C++实现接两个链表实例代码

    C++实现接两个链表实例代码

     C++实现接两个链表实例代码 有以ha为头结点的链表,元素个数为m:以hb为头结点的链表,元素个数为n.现在需要你把这两个链表连接起来,并使时间复杂度最小,请分析并实现. 思路: 很简单的链表操作的题目,逆序头部插入,并将长度较长的一方接到较短的后面,时间复杂度为O(min(m,n)),注意free使用的地点!. 实例代码: #include <iostream> #include <string> #include <algorithm> using namespa

  • Python 实现链表实例代码

    Python 实现链表实例代码 前言 算法和数据结构是一个亘古不变的话题,作为一个程序员,掌握常用的数据结构实现是非常非常的有必要的. 实现清单 实现链表,本质上和语言是无关的.但是灵活度却和实现它的语言密切相关.今天用Python来实现一下,包含如下操作: ['addNode(self, data)'] ['append(self, value)'] ['prepend(self, value)'] ['insert(self, index, value)'] ['delNode(self,

  • Springboot整合MongoDB进行CRUD操作的两种方式(实例代码详解)

    1 简介 Springboot是最简单的使用Spring的方式,而MongoDB是最流行的NoSQL数据库.两者在分布式.微服务架构中使用率极高,本文将用实例介绍如何在Springboot中整合MongoDB的两种方法:MongoRepository和MongoTemplate. 代码结构如下: 2 项目准备 2.1 启动MongoDB实例 为了方便,使用Docker来启动MongoDB,详细指导文档请参考:基于Docker的MongoDB实现授权访问的方法,这里不再赘述. 2.2 引入相关依赖

  • 使用Python将图片转正方形的两种方法实例代码详解

    一.将原图粘贴到一张正方形的背景上 def trans_square(image): r"""Open the image using PIL.""" image = image.convert('RGB') w, h = image.size background = Image.new('RGB', size=(max(w, h), max(w, h)), color=(127, 127, 127)) # 创建背景图,颜色值为127 leng

  • 利用正则表达式校验金额最多保留两位小数实例代码

    目录 正则表达式校验金额最多保留两位小数,那么必须满足如下条件: 部分正则表达式符号说明: 第一步,小数点之前表达式 第二步,小数点及小数位置 总结 先给出表达式结果:^(([1-9]{1}\d*)|(0{1}))(\.\d{1,2})?$ 有同学留言0识别错误,可用这个:(([1-9]{1}\d*)(.\d{1,2})?)|(0{1}.\d{1,2})思路:1.小数点前非0,则小数位置可有可无: 2.小数点前为0,那么小数位置必有修改于 2022-08-03 不熟悉正则表达式的同学,咋一看,一

  • C#实现Web文件上传的两种方法实例代码

    1. C#实现Web文件的上传 使用C#如何实现文件上传的功能呢?下面笔者简要介绍一下. 首先,在你的Visual C# web project 中增加一个上传用的Web Form,为了要上传文件,需要在ToolBox中选择HTML类的File Field控件,将此控件加入到Web Form中,然而此时该控件还不是服务端控件,我们需要为它加上如下一段代码:<input id=PreviousFile1 type=file size=49 runat="server">,这样

  • php产生随机数的两种方法实例代码 输出随机IP

    分享下php生成随机数的三种方法,生成1-10之间的不重复随机数,php生成不重复随机数的例子,需要的朋友参考下. 如何用php生成1-10之间的不重复随机数? 例1,使用shuffle函数生成随机数. <?php $arr=range(1,10); shuffle($arr); foreach($arr as $values) { echo $values." "; } ?> 例2,使用array_unique函数生成随机数. <?php $arr=array();

  • MyBatis批量插入数据到Oracle数据库中的两种方式(实例代码)

    一.mybatis批量插入数据到Oracle中的两种方式: 第一种: <insert id="addList" parameterType="java.util.List" useGeneratedKeys="false"> INSERT ALL <foreach item="item" index="index" collection="list"> INTO

  • Java实现单链表翻转实例代码

    Java实现单链表翻转实例代码

    Java实现单链表反转,递归和非递归两种形式 /** * 反转单链表 */ /** * 定义链表 * * @author 16026 * */ class Node { int val; Node next; public Node(int val) { this.val = val; } } public class ReverseList { /** * 反转链表 * * @param head * @return */ public static Node reverseList(Node

  • C语言中数据结构之链表归并排序实例代码

    C语言中数据结构之链表归并排序实例代码

    C语言中数据结构之链表归并排序实例代码 问题 设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增排序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏. 源程序 #include <stdio.h> #include<stdlib.h> #define N1 6 /*链表La的长度*/ #define N2 6 /*链表Lb的

随机推荐