一个链表的合并问题,实在是不知道哪里出错了.
将两个非递减有序链表 合并为一个非递增有序链表.里面有很多没用到的函数,把结点类和链表类一下复制过来的,本来是在头文件的.大家主要看看merge函数有没问题.
测试的时候能通过,可是弹出一个警告对话框,debug看去全是汇编代码,看不太明白.
#include <iostream>
using namespace std;
class Slnode;
class Node
{
friend class Slnode;
private:
int data;
Node *link;
public:
Node():link(NULL){};
Node(int value):data(value),link(NULL){};
~Node(){};
Node *getNode(){return link;}
int getdata(){ if(this==NULL) return 0; return data;}
friend void merge(Slnode &la,Slnode &lb);
};
class Slnode
{
private:
Node *first;
public:
//Slnode();
~Slnode(){Makempty(); delete first;}
Node *Locate(int i);
Makempty();
Node *max();
int number(int x);
Slnode& create(int a[],int n);
void createx(int a[],int n,int i,Node* *p);
void tidyup();
void display();
friend void merge(Slnode &la,Slnode &lb);
};
Node* Slnode::Locate(int i)
{
int pos=0;
Node *p=first;
while(p-> link!=NULL && pos <i)
{
p=p-> link;
pos++;
}
if(pos!=i) { cout < < "ûÓÐÕÒµ½ " < <endl; return NULL;}
return p;
}
Node* Slnode::max()
{
if(first-> link==NULL) { cout < < "ûÓÐÊý¾Ý " < <endl; return NULL;}
Node *p=first;
int max=p-> link-> data;
Node *pmax=p-> link;
while(p-> link-> link!=NULL)
{
if(max <p-> link-> link-> data)
{
max=p-> link-> link-> data;
pmax=p-> link-> link;
}
p=p-> link;
}
return pmax;
}
void Slnode::display()
{
Node *p=first-> link;
while(p!=NULL)
{
cout < <p-> getdata() < < " ";
p=p-> link;
}
cout < <endl;
}
int Slnode::number(int x)
{
int num=0;
Node *p=first;
while(p-> link!=NULL)
{
if(p-> link-> data==x)
num++;
p=p-> link;
}
return num;
}
/*Slnode& Slnode::create(int a[],int n)
{
Node *p,*q;
p=first=new Node;
for(unsigned int i=0;i <n;i++)
{
p-> link=new Node(a[i]);
p=p-> link;
}
return *this;
}
*/
Slnode& Slnode::create(int a[],int n)
{
first=new Node;
createx(a,n,0,&first-> link);
return *this;
}
void Slnode::createx(int a[],int n,int i,Node* *p)
{
if(i==n) ;
else
{
*p=new Node(a[i]);
createx(a,n,i+1,&(*p)-> link);
}
}
void Slnode::tidyup()
{
Node *q,*p;
q=first-> link;
while(q-> link!=NULL && q!=NULL)
{
p=q-> link;
if(q-> data==p-> data)
{q-> link=p-> link;
delete p;
}
elseq=q-> link;
}
}
Slnode::Makempty()
{
Node *p=first-> link;
while(p!=NULL)
{
first-> link=p-> link;
delete p;
p=first-> link;
}
}
void merge(Slnode &la,Slnode &lb)
{
Node *pa=la.first-> link;
Node *pb=lb.first-> link;
la.first-> link=NULL;
Node *p;
while(pa!=NULL && pb!=NULL)
{
if(pa-> data <pb-> data)
{
p=pa-> link;
pa-> link=la.first-> link;
la.first-> link=pa;
pa=p;
}
else
{
p=pb-> link;
pb-> link=la.first-> link;
la.first-> link=pb;
pb=p;
}
}
while(pa!=NULL)
{
p=pa-> link;
pa-> link=la.first-> link;
la.first-> link=pa;
pa=p;
}
while(pb!=NULL)
{
p=pb-> link;
pb-> link=la.first-> link;
la.first-> link=pb;
pb=p;
}
}
void main()
{
int a[7]={3,5,5,8,10,15,20};
int b[8]={2,6,9,14,15,18,21,23};
Slnode sa;
sa.create(a,7);
sa.display();
Slnode sb;
sb.create(b,8);
sb.display();
merge(sa,sb);
sa.display();
}
[解决办法]
先给一个参考:
#include <iostream>
using namespace std;
#define NOFOUND -1
#define FOUND 0
#define SUCCEED 0
#define FAIL -1
typedef struct {
int x,y;
}ElemType;
class Item
{
public:
int mx,my;
Item(int a=0,int b=0)
{
mx=a;my=b;
}
Item *mNxtItem; //Point to Next Element
};
//Define Abstract Data Type-----List
class List
{
public:
//Element Set
Item *mList;
//Operator Set
void mfInitList(List &l);
void mfDestoryList(List &l);
void mfClearList(List &l);
bool mfListEmpty(List l);
int mfListLength(List &l);
int mfGetElem(List l,int i,Item &e);
int mfLocateElem(List l,Item e,bool compare(Item e1,Item e2));
void mfPrior(List l,int i,Item &e);
void mfNextElem(List l,int i,Item &e);
int mfListInsert(List &l,int i,Item e);
void mfListDelete(List &l,int i,Item &e);
void mfListTraverse(List l,void visit(Item e));
};
//Define Global Function
bool gfEqual(Item e1,Item e2)
{
return((e1.mx==e2.mx)&&(e1.my==e2.my));
};
void gfDisplay(Item e)
{
cout < < "mx= " < <e.mx < < ";my= " < <e.my < <endl;
}
//End Define Global Function
void List::mfInitList(List &l)
{
l.mList=NULL;
};
bool List::mfListEmpty(List l)
{
return(l.mList==NULL);
};
void List::mfDestoryList(List &l)
{
delete l.mList;
};
void List::mfClearList(List &l)
{
Item *p,*temp;
p=l.mList;
while(p)
{
temp=p-> mNxtItem;
delete p;
p=temp;
}
delete p;
l.mList=NULL;
};
int List::mfListLength(List &l)
{
int ilen=0;
Item *p=l.mList;
while(p)
{
ilen++;
}
return ilen;
};
int List::mfGetElem(List l,int i,Item &e)
{
int j=1;
Item *p;
p=l.mList;
while(p&&j!=i)
{
p=p-> mNxtItem;
j++;
}
if(p) {e=*p;return FOUND;}
return NOFOUND;
};
int List::mfLocateElem(List l,Item e,bool compare(Item e1,Item e2))
{
Item *p=l.mList;
int i=0;
while(p)
{
i++;
if(compare(*p,e)) break;
p=p-> mNxtItem;
}
if(p) return i;
return NOFOUND;
};
int List::mfListInsert(List &l,int i,Item e)
{
Item *p=l.mList;
Item *insP,*nxtP;
int j=1;
if(!l.mList) {insP=new Item();insP-> mx=e.mx;insP-> my=e.my;insP-> mNxtItem=NULL;l.mList=insP;return SUCCEED;}
if(i==1) {
insP=new Item();insP-> mx=e.mx;insP-> my=e.my;nxtP=l.mList;
l.mList=insP;insP-> mNxtItem=nxtP;return SUCCEED;
}
while(p&&j <i-1)
{
j++;
p=p-> mNxtItem;
}
if(p){
insP=new Item();
if(insP==NULL) return FAIL;
insP-> mx=e.mx;insP-> my=e.my;
nxtP=p-> mNxtItem;
insP-> mNxtItem=nxtP;
p-> mNxtItem=insP;
return SUCCEED;
}
return FAIL;
};
void List::mfListTraverse(List l,void visit(Item e))
{
Item *p=l.mList,e;
if(!l.mList) {cout < < "List Is Empty,Traverse Failed! " < <endl;return;}
while(p)
{
e.mx=p-> mx;e.my=p-> my;
visit(e);
p=p-> mNxtItem;
}
}
void List::mfListDelete(List &l,int i,Item &e)
{
Item *p,*preP,*nxtP;
p=l.mList;
if(!l.mList) {cout < < "ERROR,The List Is Empty! " < <endl;
return ; }
if(i==1) {l.mList=p-> mNxtItem;delete p;return;}
while(p&&i> 2)
{
p=p-> mNxtItem;
i--;
}
preP=p; //指向删除结点的前一个结点
nxtP=p-> mNxtItem-> mNxtItem; //指向删除结点的后一个结点
preP-> mNxtItem=nxtP; //要删除的结点前一个结点的指针域,指向删除结点的后一个结点
p=p-> mNxtItem;
delete p;
}
int main()
{
int i;
List l;
//List *k=new List();
Item e;
l.mfInitList(l);
for(i=1;i <=10;i++)
{
e.mx=i;e.my=i;
l.mfListInsert(l,i,e);
}
l.mfListTraverse(l,gfDisplay);
l.mfListDelete(l,10,e);
l.mfListTraverse(l,gfDisplay);
system( "pause ");
return 0;
}
[解决办法]
main 文件不修改,
把 class 的定义放在另外一个 h 文件中,
修改如下:
#ifndef TEST_H
#define TEST_H
#include <stdio.h> //不要声明 std 空间
class Slnode;
class Node
{
friend class Slnode;
private:
int data;
Node *link;
public:
Node():link(NULL){};
Node(int value):data(value),link(NULL){};
~Node(){};
Node *getNode(){return link;}
int getdata(){ if(this==NULL) return 0; return data;}
friend void merge(Slnode &la,Slnode &lb);
};
class Slnode
{
private:
Node *first;
public:
// Slnode();
~Slnode(){Makempty(); delete first;}
Node *Locate(int i);
void Makempty(); //成员函数的返回类型 !
Node *max();
int number(int x);
Slnode& create(int a[],int n);
void createx(int a[],int n,int i,Node* *p);
void tidyup();
void display();
friend void merge(Slnode &la,Slnode &lb);
};
Node* Slnode::Locate(int i)
{
int pos=0;
Node *p=first;
while(p-> link!=NULL && pos <i)
{
p=p-> link;
pos++;
}
if(pos!=i) { cout < < "ûÓÐÕÒµ½ " < <endl; return NULL;}
return p;
}
Node* Slnode::max()
{
if(first-> link==NULL) { cout < < "ûÓÐÊý¾Ý " < <endl; return NULL;}
Node *p=first;
int max=p-> link-> data;
Node *pmax=p-> link;
while(p-> link-> link!=NULL)
{
if(max <p-> link-> link-> data)
{
max=p-> link-> link-> data;
pmax=p-> link-> link;
}
p=p-> link;
}
return pmax;
}
void Slnode::display()
{
Node *p=first-> link;
while(p!=NULL)
{
cout < <p-> getdata() < < " ";
p=p-> link;
}
cout < <endl;
}
int Slnode::number(int x)
{
int num=0;
Node *p=first;
while(p-> link!=NULL)
{
if(p-> link-> data==x)
num++;
p=p-> link;
}
return num;
}
/*Slnode& Slnode::create(int a[],int n)
{
Node *p,*q;
p=first=new Node;
for(unsigned int i=0;i <n;i++)
{
p-> link=new Node(a[i]);
p=p-> link;
}
return *this;
}
*/
Slnode& Slnode::create(int a[],int n)
{
first=new Node;
createx(a,n,0,&first-> link);
return *this;
}
void Slnode::createx(int a[],int n,int i,Node* *p)
{
if(i==n) ;
else
{
*p=new Node(a[i]);
createx(a,n,i+1,&(*p)-> link);
}
}
void Slnode::tidyup()
{
Node *q,*p;
q=first-> link;
while(q-> link!=NULL && q!=NULL)
{
p=q-> link;
if(q-> data==p-> data)
{ q-> link=p-> link;
delete p;
}
else q=q-> link;
}
}
void Slnode::Makempty()
{
Node *p=first-> link;
while(p!=NULL)
{
first-> link=p-> link;
delete p;
p=first-> link;
}
}
void merge(Slnode &la,Slnode &lb)
{
Node *pa=la.first-> link;
Node *pb=lb.first-> link;
la.first-> link=NULL;
Node *p;
while(pa!=NULL && pb!=NULL)
{
if(pa-> data <pb-> data)
{
p=pa-> link;
pa-> link=la.first-> link;
la.first-> link=pa;
pa=p;
}
else
{
p=pb-> link;
pb-> link=la.first-> link;
la.first-> link=pb;
pb=p;
}
}
while(pa!=NULL)
{
p=pa-> link;
pa-> link=la.first-> link;
la.first-> link=pa;
pa=p;
}
while(pb!=NULL)
{
p=pb-> link;
pb-> link=la.first-> link;
la.first-> link=pb;
pb=p;
}
};
#endif
[解决办法]
没看具体代码,
copy 下来放在两个文件中,
编译了一下,
然后根据错误提示修改了一下,
结果似乎没有问题了 ~