当前位置:  编程技术>c/c++/嵌入式

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

    来源: 互联网  发布时间:2014-10-16

    本文导语:  已知两个链表list1和list,2,各自非降序排列,将它们合并成另外一个链表list3,并且依然有序,要求保留所有节点。实现过程中,list1中的节点和list2中的节点都转移到了list3中,注意泛型的友元函数的用法。程序如有不足之处...

已知两个链表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 < i - 1)
  {
   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 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 < head2->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 < head2->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

    
 
 
 
本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • 会javabean,用jbuiler的请进,呵呵,大家探讨探讨,参与者都有分!!
  • jsp/servlet开发网站,客户端打印解决方案探讨!
  • 厦门LINUX技术探讨群
  • 大家可以探讨一下Servlet的设计模式么?
  • 探讨Oracle中的&号问题
  • 大家来探讨!
  • 探讨如何学习j2ee!
  • 探讨下启动盘的制作原理!
  • 高分探讨小问题--关于jsp
  • [探讨]文件系统的控制问题
  • 欢迎高手指教,菜鸟来探讨!
  • 关于一个系统的探讨~
  • jbuilder6不稳定!请有使用经验的来探讨一下是什么原因?
  • C/C++代码格式工具探讨
  • 请教--父进程监控子进程,欢迎高手进来探讨!!!
  • 探讨下linux下pam验证中的crypt
  • 一个问题与大家探讨,各位请进,来者有分!!!
  • 关于学习Linux的一个问题(非技术的探讨)
  • makefile eval 问题--共同探讨
  • Linux Makefile探讨,产生的.d文件是.c文件的依赖?




  • 特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3