当前位置: 编程技术>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中的节点都转移到了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