热门标签 | HotTags
当前位置:  开发笔记 > IOS > 正文

探讨:将两个链表非降序合并为一个链表并依然有序的实现方法

本篇文章是对将两个链表非降序合并为一个链表并依然有序的实现方法进行了详细的分析介绍,需要的朋友参考下
已知两个链表list1和list,2,各自非降序排列,将它们合并成另外一个链表list3,并且依然有序,要求保留所有节点。
实现过程中,list1中的节点和list2中的节点都转移到了list3中,注意泛型的友元函数的用法。
程序如有不足之处,还望指正!!!
定义List类
代码如下:

#include "stdafx.h"
#include

using namespace std;
template
struct Node
{
 T data;
 Node * next;
};
template
class MyList
{
public:
 //构造函数,初始化一个头结点,data为空,next指向第一个节点
 MyList()
 {
  phead = new Node;
  phead->data = NULL;
  phead->next = NULL;
 }
 //析构函数,将整个链表删除,这里采用的是正序撤销
 ~MyList()
 {
  Node* p;
  p = phead;
  while (p)
  {
   Node* q;
   q = p;
   p = p->next;
   delete q;
  }
 }
 //复制构造函数
 MyList(MyList& mylist)
 {
  Node* q = mylist.phead->next;
  Node* pb = new Node;
  this->phead = pb;
  while (q != NULL)
  {
   Node* p = new Node;
   p->data = q->data;
   p->next = NULL;
   pb->next = p;
   pb = p;
   q = q->next;
  }
 }
 //插入一个元素的方法,在第i个元素插入一个元素e,
 //返回值为NOTE型指针,指向插入的那个元素
 Node* Insert(int i, T e)
 {
  //在链表的第i个位置,插入一个元素e
  int j = 0;
  Node* p;
  p = phead;
  while (p && j   {
   p = p->next;
   ++j;
  }
  if (!p || j > i -1)
  {
   return phead;
  }
  Node* q;
  q = new Node;
  q->data = e;
  q->next = p->next;
  p->next = q;
  return q;
 }
 //输出list中的元素
 void Show()
 {
  Node *p = phead->next;
  while (NULL != p)
  {
   cout <data <<" ";
   p = p->next;
  }
 }
  template friend void MergeList(MyList &list1, MyList &list2, MyList &list3);
private:
 Node* phead;};  

代码如下:

// 
//将两个链表合并成一个链表,并且依然有序。方法保留了合并之前list1和list2的节点,
//合并之后list1和list2消失。将list1和list2合并为list3
template
void MergeList(MyList &list1, MyList &list2, MyList &list3)
{
 Node *head1 = list1.phead, *head2 = list2.phead;
 Node *head3 = list3.phead, *temp = NULL;
 if (head1->next == NULL)
 {//如果list1为空,则list3头指针指向list2
  head3 = head2;
  list2.phead->next = NULL;//将list2消除,防止析构函数析构list2时找不到对象
 }
 else if (head2->next == NULL)
 {//如果list1为空,则list3头指针指向list2
  head3 = head1;
  list1.phead->next = NULL;//将list1消除,防止析构函数析构list2时找不到对象
 }
 head1 = head1->next;
 list1.phead->next = NULL;//将list1消除,防止析构函数析构list2时找不到对象
 head2 = head2->next;
 list2.phead->next = NULL;//将list2消除,防止析构函数析构list2时找不到对象
 if (head1->data data)
 {//如果list1的第一个元素小于list2的第一个元素
  head3->next = head1;//将list1的第一个元素接到list3上
  head1 = head1->next;
 }
 else
 {
  head3->next = head2;//将list2的第一个元素接到list3上
  head2 = head2->next;
 }
 temp = head3->next;//指向list3当前最后一个节点
 while (head1 != NULL && head2 != NULL)
 {
  if (head1->data data)
  {
   temp->next = head1;//将list1中的元素接到list3的后面
   temp = head1;
   head1 = head1->next;
  }
  else
  {
   temp->next = head2;//将list2中的元素接到list3的后面
   temp = head2;
   head2 = head2->next;
  }
 }
 if (NULL == head1) //将list1或者list2中的剩余部分接到list3的后面
 {
  temp->next = head2;
 }
 else if (NULL == head2)
 {
  temp->next = head1;
 }
}
 
//主函数
int _tmain(int argc, _TCHAR* argv[])
{
 MyList list1, list2, list3; 
    for (int i = 1; i <= 10; i ++) 
    { 
       list1.Insert(i, 3*i); 
    list2.Insert(i, 2*i);
   }
   MergeList(list1, list2, list3);
 list3.Show();

 return 0;
}













推荐阅读
  • 本文总结了2018年的关键成就,包括职业变动、购车、考取驾照等重要事件,并分享了读书、工作、家庭和朋友方面的感悟。同时,展望2019年,制定了健康、软实力提升和技术学习的具体目标。 ... [详细]
  • 在计算机技术的学习道路上,51CTO学院以其专业性和专注度给我留下了深刻印象。从2012年接触计算机到2014年开始系统学习网络技术和安全领域,51CTO学院始终是我信赖的学习平台。 ... [详细]
  • 本文介绍如何在 Xcode 中使用快捷键和菜单命令对多行代码进行缩进,包括右缩进和左缩进的具体操作方法。 ... [详细]
  • 如何在PHPcms网站中添加广告
    本文详细介绍了在PHPcms网站后台添加广告的方法,涵盖多种常见的广告形式,如百度广告和Google广告,并提供了相关设置的步骤。同时,文章还探讨了优化网站流量的SEO策略。 ... [详细]
  • 当iOS设备越狱后,某些插件可能会导致系统崩溃(白苹果)。此时,可以通过进入安全模式来排查并删除有问题的插件。本文将详细介绍如何通过特定按键组合进入不加载MobileSubstrate的安全模式,并提供相关背景知识。 ... [详细]
  • 在Linux系统中配置并启动ActiveMQ
    本文详细介绍了如何在Linux环境中安装和配置ActiveMQ,包括端口开放及防火墙设置。通过本文,您可以掌握完整的ActiveMQ部署流程,确保其在网络环境中正常运行。 ... [详细]
  • C++: 实现基于类的四面体体积计算
    本文介绍如何使用C++编程语言,通过定义类和方法来计算由四个三维坐标点构成的四面体体积。文中详细解释了四面体体积的数学公式,并提供了两种不同的实现方式。 ... [详细]
  • 本文介绍如何通过Windows批处理脚本定期检查并重启Java应用程序,确保其持续稳定运行。脚本每30分钟检查一次,并在需要时重启Java程序。同时,它会将任务结果发送到Redis。 ... [详细]
  • 如何优化2060显卡设置以提升《Apex英雄》游戏体验
    《Apex英雄》作为一款热门的战术竞技游戏,吸引了大量玩家。本文将探讨如何通过优化GeForce RTX 2060显卡设置,确保在《Apex英雄》中获得最佳性能和流畅的游戏体验。 ... [详细]
  • 本章将深入探讨移动 UI 设计的核心原则,帮助开发者构建简洁、高效且用户友好的界面。通过学习设计规则和用户体验优化技巧,您将能够创建出既美观又实用的移动应用。 ... [详细]
  • 本文介绍如何通过SQL查询从JDE(JD Edwards)系统中提取所有字典数据,涵盖关键表的关联和字段选择。具体包括F0004和F0005系列表的数据提取方法。 ... [详细]
  • 如何高效创建和使用字体图标
    在Web和移动开发中,为什么选择字体图标?主要原因是其卓越的性能,可以显著减少HTTP请求并优化页面加载速度。本文详细介绍了从设计到应用的字体图标制作流程,并提供了专业建议。 ... [详细]
  • 本文详细介绍了如何通过命令行启动MySQL服务,包括打开命令提示符窗口、进入MySQL的bin目录、输入正确的连接命令以及注意事项。文中还提供了更多相关命令的资源链接。 ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • 本文将详细介绍在Windows 7环境下,检查U盘启动盘是否制作成功的多种方法,包括通过BIOS设置和使用模拟启动工具。 ... [详细]
author-avatar
手机用户随便转转
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有