#include<iostream>
using namespace std;
template<class T>
class LinkNode
{
template<class T>
friend class LinkList;
public:
LinkNode()
{
next =NULL;
}
T data;
LinkNode<T>*next;
};
template<class T>
class LinkList
{
public:
LinkList();
~LinkList();
LinkList<T>&Insert(int k,const T&x);
LinkList<T>&DeleteByIndex(int k, T&x);
int GetLength()const;
bool GetData(int k,T &x);
void Merge(LinkList<T> L1,LinkList<T> L2,LinkList<T>&L3);
void OutPut(ostream& out);
LinkNode<T>*head;
};
template<class T>
LinkList<T>::LinkList()
{
head=new LinkNode<T>();
}
template<class T>
LinkList<T>::~LinkList()
{
T x;
int len=GetLength();
for(int i=len;i>=1;i--)
DeleteByIndex(i,x);
delete head;
}
template <class T>
int LinkList<T>::GetLength()const
{
int length=0;
LinkNode<T>*p=head->next;
while(p)
{
length++;
p=p->next;
}
return length;
}
template<class T>
LinkList<T>&LinkList<T>::DeleteByIndex(int k,T &x)
{
if(GetData(k,x))
{
LinkNode<T> *p=head;
LinkNode<T> *q=NULL;
for(int i=1;i<k;i++)
p=p->next;
q=p->next;
p->next=q->next;
delete q;
}
else
cout<<"元素下标越界,删除失败"<<endl;
return *this;
}
template<class T>
bool LinkList<T>::GetData(int k,T&x)
{
LinkNode<T>*p=head->next;
int index=1;
if(k<1||k>GetLength())
return false;
while(p!=NULL&&index<k)
{
index++;
p=p->next;
}
if(p==NULL)
return false;
else
{
x=p->data;
return true;
}
}
template<class T>
void LinkList<T>::OutPut(ostream &out)
{
LinkNode<T>*p=head->next;
while(p!=NULL)
{
out<<p->data<<endl;
p=p->next;
}
}
template<class T>
ostream &operator<<(ostream &out ,LinkList<T>&x)
{
x.OutPut(out);
return out;
}
template<class T>
LinkList<T>&LinkList<T>::Insert(int k,const T&x)
{
LinkNode<T>*p=head;
LinkNode<T>*newNode=new LinkNode<T>;
newNode->data=x;
int len=GetLength();
if(k<1||k>len+1)
cout<<"元素下标越界,添加元素失败";
else
{
for(int i=1;i<k;i++)
p=p->next;
newNode->next=p->next;
p->next=newNode;
}
return *this;
}
template<class T>
void Merge(LinkList<T> L1,LinkList<T> L2,LinkList<T>&L3)
{
LinkNode<T>*p=L3.head;
LinkNode<T>*newNode=new LinkNode<T>;
LinkNode<T>*m=L1.head;
LinkNode<T>*n=L2.head;
for(int i=0;i<L1.GetLength()+L2.GetLength();i++)
{
while(m!=NULL&&m->data<n->data)
{
p->data=m->data;
m=m->next;
p=p->next;
}
while(n!=NULL&&n->data<m->data)
{
p->data=n->data;
n=n->next;
p=p->next;
}
while(m=NULL)
{
p->data=n->data;
}
while(n=NULL)
{
p->data=m->data;
}
}
}
#include"Linklist.h"
#include<iostream>
using namespace std;
int main()
{
LinkList<int>L1,L2,L3;
L1.Insert(1,100);
L1.Insert(2,200);
L1.Insert(3,300);
L1.Insert(4,400);
L2.Insert(1,50);
L2.Insert(2,150);
L2.Insert(3,250);
L2.Insert(4,270);
Merge(L1,L2,L3);
cout<<"当前链表1和2的元素为:"<<endl<<L1<<L2<<endl;
cout<<"元素合并之后的链表是:"<<L3<<endl;
return 0;
}
template<class T>
void Merge(const LinkList<T> &L1, const LinkList<T> &L2, LinkList<T>&L3)
{
LinkNode<T>*p = L3.head;
LinkNode<T>*m = L1.head->next;
LinkNode<T>*n = L2.head->next;
for (int i = 0; i < L1.GetLength() + L2.GetLength(); i++)
{
if (m!=NULL&&n!=NULL)
{
if (m->data<n->data)
{
LinkNode<T>*newNode = new LinkNode<T>;
newNode->data = m->data;
p->next = newNode;
p = newNode;
m = m->next;
}
else{
LinkNode<T>*newNode = new LinkNode<T>;
newNode->data = n->data;
p->next = newNode;
p = newNode;
n = n->next;
}
}else if (m!=NULL)
{
LinkNode<T>*newNode = new LinkNode<T>;
newNode->data = m->data;
p->next = newNode;
p = newNode;
m = m->next;
}
else{
LinkNode<T>*newNode = new LinkNode<T>;
newNode->data = n->data;
p->next = newNode;
p = newNode;
n = n->next;
}
}
}
这么改
C和C++完整教程:https://blog.csdn.net/it_xiangqiang/category_10581430.html
C和C++算法完整教程:https://blog.csdn.net/it_xiangqiang/category_10768339.html