我现在教数据结构课程,我是用C++来描述的。对单链表的定义与实现都是通过类的方式完成的,最近写了一个将两个链表合并成为一个新的链表的函数,通过主函数调用时编译(c++Builder5.0)老是通不过。请教高手,这个问题可能需要C++非常有经验的高手才能解决。
以下是结点的定义,还有链表的定义,存成了头文件:linklist.h
#include<iostream.h>
#include<conio.h>
template <class Type> class LinkList;
template <class Type>
class LNode{
public:
friend class LinkList<Type> ;
friend void MergeList(LinkList<Type> &,LinkList<Type> &,LinkList<Type> &);
LNode(){
next=NULL;
}
LNode(const Type&e,LNode<Type>* l=NULL){
data=e;
next=l;
}
private:
Type data;
LNode<Type> *next;
};
template <class Type>
class LinkList{
public:
friend void MergeList(LinkList<Type> &,LinkList<Type> &,LinkList<Type> &);
LinkList(){
head=new LNode<Type>();
}
~LinkList();
int Length();
int Find(Type x);
bool Insert(int i,Type x);
bool Delete(int i);
bool Get(int i,Type &e);//取单链表中第i个元素的值,其值赋给e
private:
LNode<Type> *head;//单链表的头指针
} ;
template <class Type>
LinkList<Type>::~LinkList(){
LNode<Type> *p;
while(head!=NULL){
p=head;
head=head->next;
delete p;
}
}
template <class Type>
int LinkList<Type>::Length(){
LNode<Type> *p;
p=head->next;
int count=0;
while(p!=NULL){
count++;
p=p->next;
}
return count;
}
template <class Type>
bool LinkList<Type>::Insert(int i,Type x){
LNode<Type> *p;
p=head;
int j=0;
while(p&&j<i-1){
p=p->next;
++j;
}//若指针跳出循环非空的话,指针P就指向第i-1个结点
if(!p||j>i-1)
return false;
LNode<Type> *s=new LNode<Type>();
s->data=x;
s->next=p->next;
p->next=s;
return true;
}
template <class Type>
bool LinkList<Type>::Delete(int i){
LNode<Type> *p,*q;
p=head;
int j=0;
while(p->next&&j<i-1){
p=p->next;
++j;
}
if(!(p->next)||j>i-1)
return false;
q=p->next;
p->next=q->next;
delete q;
return true;
}
template <class Type>
bool LinkList<Type>::Get(int i,Type &e){
LNode<Type> *p;
p=head->next;
int j=1;
while(p&&j<i){//指针向后查找,直到p指向第i个元素或p为空
p=p->next;
++j;
}
if(!p||j>i)
return false;
e=p->data;
return true;
}
下面是调用的主程序,还有合并链表的函数mergelist,
#include"linklist.h"
template <class Type>
void MergeList(LinkList<Type> &La,LinkList<Type>&Lb,LinkList<Type>&Lc){
LNode<Type> *pa=(La.head)->next;
LNode<Type> *pb=Lb.head->next;
LNode<Type> *pc=Lc.head;
while(pa&&pb){
if(pa->data<=pb->data){
pc->next=pa;
pc=pa;
pa=pa->next;
}
else{
pc->next=pb;
pc=pb;
pb=pb->next;
}
}
pc->next=pa?pa:pb;
delete La->head;//释放La的头结点
delete Lb->head;//释放Lb的头结点
}
main()
{
LinkList<int> La;
LinkList<int>Lb,Lc;
int e,i;
cout<<"插入数据之后:"<<endl;
for(i =1;i<6;i++){
{bool b=La.Insert(i,i);//插入数据
if(b) cout<<"ture"<<endl;
else cout<<"false";}
}
for(i =1;i<6;i++){
{bool b=Lb.Insert(i,i+5);//插入数据
if(b) cout<<"ture"<<endl;
else cout<<"false";}
}
cout<<"线性表La的元素为:";
for(i=1;i<=La.Length();i++){
La.Get(i,e);
cout<<e<<" ";
}
cout<<endl;
cout<<"线性表Lb的元素为:";
for(i=1;i<=Lb.Length();i++){
Lb.Get(i,e);
cout<<e<<" ";
}
MergeList(La,Lb,Lc);//这句编译老是通不过
cout<<"线性表Lc的元素为:";
for(i=1;i<=Lc.Length();i++){
Lc.Get(i,e);
cout<<e<<" ";
}
getch();
}