为什么空链表不能实现插入，如何将已排序的两集合放入第三集合排序用链表实现
//集合的交并用算法实现#include <iostream>
using namespace std;
template <class Type>//注意模板的声明方式
class LinkList
{
public:
LinkList();//构造空链表
LinkList(Type a[],int n);//构造非空链表，很重要
~LinkList();//析构函数
void insert(int i,Type x);//在第i个位置插入x
Type deleteLink(int i);//删除第i个位置的元素
int locate(Type x);//找元素x所在的位置
Type locatex(int i);//查找第i个位置的元素
int length();//求单链表的长度
void reverse();//逆置
void compare(LinkList q,LinkList p);
void printList();//输出链表
private:
struct Node//如何写链表中的数据
{
Type data;
Node *next;
} *first;
};
template <class Type>//注意模板的定义格式template<类型参数表> <返回类型> <类名><类型名表>::<函数名>
LinkList<Type>::LinkList()
{
first=new Node;
first->next=NULL;
}
template <class Type>
LinkList<Type>::LinkList(Type a[],int n)
{
first=new Node;//尾插法
Node * r=first;
for(int i=0; i<n; i++)
{
Node * s= new Node;
s->data=a[i];
r->next=s;
r=s;
}
r->next=NULL;
/*first=new Node;
first->next=NULL;
for(int i=0;i<n;i++)//头插法
{
Node* s=new Node;
s->data=a[i];
s->next=first->next;
first->next=s;
}*/
}
template<class Type>
LinkList<Type>::~LinkList()
{
Node *s;
s=first->next;
while(s!=NULL)
{
first->next=s->next;
delete s;
s=first->next;
}
delete first;
}
template<class Type>
void LinkList<Type>::insert(int i,Type x)
{
Node *p;
p=first;
int j=0;
while(p&&(j<i-1))
{
p=p->next;
j++;
}
if(p==NULL)
{
cout<<"位置："<<j<<endl;
}
else
{
Node *s=new Node;
s->data=x;
s->next=p->next;
p->next=s;
}
}
template <class Type>
Type LinkList<Type>::deleteLink(int i)
{
Node *p;
p=first;
int j=0;
while(p&&j<i-1)
{
p=p->next;
j++;
}
if(!p||!p->next)
{
cout<<"没有第i个元素可删除"<<endl;
}
else
{
Node *s;
int t;
s=p->next;
t=s->data;
p->next=s->next;
delete s;
return t;
}
}
template<class Type>
Type LinkList<Type>::locatex(int i)
{
Node *p;
p=first->next;
int j=1;
while(p&&j<i)
{
p=p->next;
j++;
}
if(!p)
{
cout<<"找不到x"<<endl;
}
else
return p->data;
}
template<class Type>
int LinkList<Type>::locate(Type x)
{
Node *p;
p=first;
int j=0;
while(p&&(p->data!=x))
{
p=p->next;
j++;
}
if(!p)
return 0;
else
return j;
}
template<class Type>
int LinkList<Type>::length()
{
Node* p;
int count=0;
p=first->next;
while(p)
{
p=p->next;
count++;
}
return count;
}
template <class Type>
void LinkList<Type>::reverse()
{
Node* p=first->next;
Node* pre=NULL;
while(p)
{
Node* r=p->next;//存放下一个节点
p->next=pre;//将p节点指向其前驱节点
pre=p;
p=r;
}
first->next=pre;
}
template<class Type>
void LinkList<Type>::compare(LinkList q,LinkList p)//此处有误，请高手赐教
{
//this.LinkList();
int i=1,j=1,k=0;
while(i<=q.length()&&j<=p.length())
{
if(q.locatex(i)<=p.locatex(j))
{
this.insert(k+1,q.locatex(i));
i++;
k++;
}
else
{
this.insert(k+1,p.locatex(j));
j++;
k++;
}
}
while(i<=q.length())
{
this.insert(k+1,q.locatex(i));
i++;
k++;
}
while(j<=p.length())
{
this.insert(k+1,p.locatex(j));
j++;
k++;
}
this.printList();
}
template <class Type>
void LinkList<Type>::printList()
{
Node *p;
p=first->next;//不能为p=first,否则输出的从头结点开始
while(p)
{
cout<<p->data<<' ';
p=p->next;
}
cout<<endl;
}
int main()
{
int a[3],b[5],g[0];
g[0]=NULL;
for(int i=0; i<3; i++)
{
a[i]=i+1;
}
for(int i=0; i<5; i++)
{
b[i]=i+1;
}
LinkList<int> q1(a,3);
LinkList<int> q2(b,5);
LinkList<int> q3(g,0);
(q1,q2);
/*for(int i=1;i<=q1.length()+q2.length();i++)
{
q3.insert(i,q1.locatex(i));
if(i>3)
q3.insert(i,b[q1.length()%i]);
}
cout<<"q3的值为："<<q3.printList();
q1.printList();
cout<<"q1逆置后的结果";
q1.reverse();
q1.printList();
q2.printList();
int n=0,k=0,x=0;
n=q1.length();
for(int i=1;i<=q2.length();i++)
{
x=q2.locatex(i);
k=q1.locate(x);
if(k==0)
{
q1.insert(n+1,x);
n=n+1;
}
// cout<<k<<" ";
}
q1.printList();*/
/*q1.printList();
cout<<endl;
q1.insert(2,40);
q1.printList();
cout<<endl;
cout<<"1的位置： "<<q1.locate(1);
q1.deleteLink(2);
cout<<endl;
q1.printList();*/
}
程序代码：