主题：[讨论]帮忙看看程序 两个单链表合并成一个链表
wk0721
[专家分：0] 发布于 2007-01-06 19:52:00
这是我做的两个单链表合成一个单链表的程序，不知道为什么执行后总是出现错误，哪位高手能帮我看看，多谢了。
void add(LinList<T> &la,LinList<T> &lb,LinList<T> &lc)
{
ListNode<T> *pa,*pb,*pc;
pa=la.head->next;
pb=lb.head->next;
delete(lb.head);
lc.head=la.head;
pc=lc.head;
pc->next=NULL;
if(la.Size()>lb.Size())
{
while(pa&&pb)
{
pc->next=pa;
pc=pa;
pa=pa->next;
pc->next=pb;
pc=pb;
pb=pb->next;
}
if(pa)
{
pc->next=pa;
pc=pa;
pa=pa->next;
}
else
{
pc->next=pb;
pc=pb;
pb=pb->next;
}
}
else
{
while(pa&&pb)
{
pc->next=pb;
pc=pb;
pb=pb->next;
pc->next=pa;
pc=pa;
pa=pa->next;
}
if(pa)
{
pc->next=pa;
pc=pa;
pa=pa->next;
}
else
{
pc->next=pb;
pc=pb;
pb=pb->next;
}
}
}
[em18][em18][em18]
回复列表 （共10个回复）
沙发
wk0721 [专家分：0] 发布于 2007-01-06 19:55:00
题目是这样地
（1）建立两个链表A和B，链表元素个数分别为m和n个。
（2）假设元素分别为(x1,x2,…xm)，和(y1,y2, …yn)。把它们合并成一个线形表C，使得：
当m>=n时，C=x1,y1,x2,y2,…xn,yn,…,xm
当n>m时，C=y1,x1,y2,x2,…ym,xm,…,yn
输出线形表C
板凳
雪光风剑 [专家分：27190] 发布于 2007-01-06 20:24:00
添加完m=n的元素之后单独添加x\y部分有问题
3 楼
wk0721 [专家分：0] 发布于 2007-01-06 21:08:00
x/y部分是正确的，那样写看着是有点复杂，但是是正确的
4 楼
雪光风剑 [专家分：27190] 发布于 2007-01-06 21:30:00
发一段你的输入和输出上来
还有你的主程序
5 楼
wk0721 [专家分：0] 发布于 2007-01-06 21:41:00
用的是C++编译的
单链表.h
template<class T>
class LinList;
template<class T>
class ListNode
{
friend class LinList<T>;
private:
ListNode<T> * next;
T data;
public:
ListNode(ListNode<T> * ptrNext=NULL)
{next=ptrNext;}
ListNode(const T& item,ListNode<T> * ptrNext=NULL)
{data=item;next=ptrNext;}
~ListNode(void){}
};
template<class T>
class LinList
{
private:
ListNode<T> * head;
int size;
ListNode<T> * Index(int i);
public:
LinList(void);
~LinList(void);
int Size(void)const;
void Insert(const T& item,int i);
T Delete(int i);
T GetData(int i);
void add(LinList<T> &la,LinList<T> &lb);
};
template<class T>
LinList<T>::LinList()
{
head=new ListNode<T>();
size=0;
}
template<class T>
LinList<T>::~LinList(void)
{
ListNode<T> *p,*q;
p=head;
while(p!=NULL)
{
q=p;
p=p->next;
delete q;
}
size=0;
head=NULL;
}
template<class T>
ListNode<T> * LinList<T>::Index(int i)
{
if(i<-1||i>size-1)
{
cout<<"参数i越界出错!"<<endl;
exit(0);
}
if(i==-1) return head;
ListNode<T> *p=head->next;
int j=0;
while(p!=NULL&&j<i)
{
p=p->next;
j++;
}
return p;
}
template<class T>
int LinList<T>::Size(void)const
{
return size;
}
template<class T>
void LinList<T>::Insert(const T& item,int i)
{
if(i<0||i>size)
{
cout<<"参数i越界出错!"<<endl;
exit(0);
}
ListNode<T> *p=Index(i-1);
ListNode<T> *q=new ListNode<T>(item,p->next);
p->next=q;
size++;
}
template<class T>
T LinList<T>::Delete(int i)
{
if(size==0)
{
cout<<"链表已空无元数可删!"<<endl;
exit(0);
}
if(i<0||i>size-1)
{
cout<<"参数i越界出错!"<<endl;
exit(0);
}
ListNode<T> *s,*p=Index(i-1);
s=p->next;
p->next=p->next->next;
T x=s->data;
delete s;
size--;
return x;
}
template<class T>
T LinList<T>::GetData(int i)
{
if(i<0||i>size-1)
{
cout<<"参数i越界出错!"<<endl;
exit(0);
}
ListNode<T> *p=Index(i);
return p->data;
}
template<class T>
void LinList<T>::add(LinList<T> &la,LinList<T> &lb)
{
ListNode<T> *pa,*pb,*pc;
pa=la.head->next;
pb=lb.head->next;
delete lb.head;
head=la.head;
head->next=NULL;
pc=head;
size=la.Size()+lb.Size();
if(la.Size()>=lb.Size())
{
while(pa&&pb)
{
pc->next=pa;
pc=pa;
pa=pa->next;
pc->next=pb;
pc=pb;
pb=pb->next;
}
if(pa)
{
pc->next=pa;
pc=pa;
}
else
{
pc->next=pb;
pc=pb;
}
}
else
{
while(pa&&pb)
{
pc->next=pb;
pc=pb;
pb=pb->next;
pc->next=pa;
pc=pa;
pa=pa->next;
}
if(pa)
{
pc->next=pa;
pc=pa;
}
else
{
pc->next=pb;
pc=pb;
}
}
}
6 楼
wk0721 [专家分：0] 发布于 2007-01-06 21:41:00
主程序为
#include<iostream.h>
#include<stdlib.h>
#include<string.h>
#include"单链表.h"
void main()
{
LinList<int> alist,blist,clist,dlist;
int a[]={30,41,15,12,56,80};
int b[]={23,56,78,23,12,33,79,90,55};
int i=0,j=0;
for(i=0;i<6;i++)
alist.Insert(a[i],i);
for(i=0;i<alist.Size();i++)
cout<<alist.GetData(i)<<" ";
cout<<endl;
for(j=0;j<9;j++)
blist.Insert(b[j],j);
for(i=0;i<blist.Size();i++)
cout<<blist.GetData(i)<<" ";
cout<<endl;
alist.add(alist,blist);
for(i=0;i<alist.Size();i++)
cout<<alist.GetData(i)<<" ";
cout<<endl;
}
7 楼
wk0721 [专家分：0] 发布于 2007-01-06 21:46:00
执行后输出的结果为
30 41 15 12 56 80
23 56 78 23 12 33 79 90 55
30 23 41 56 15 78 12 23 56 12 80 33 79 90 55
实际上输出结果应该为
30 41 15 12 56 80
23 56 78 23 12 33 79 90 55
23 30 56 41 78 15 23 12 12 56 33 80 79 90 55
8 楼
雪光风剑 [专家分：27190] 发布于 2007-01-07 09:54:00
if(la.Size()>lb.Size())
在这一句前面加上cout<<la.size()<<lb.size()<<endl;
跟一下看看是不是size计算出错
9 楼
zy1121 [专家分：7950] 发布于 2007-01-07 10:55:00
size = la.Size() + lb.Size();
if(la.Size() >= lb.Size() )
--------------------
la.Size() 是肯定大于lb.Size()的,
la.Size()已经是它们原来值的和了
[code]
template<class T>
void LinList<T>::add(LinList<T> &lb)
{
ListNode<T> *pa,*pb,*pc;
if(size < lb.size) // 使lb始终为size较小的链表
{
int temp = size;
size = lb.size;
lb.size = temp;
pc = head;
head = lb.head;
lb.head = pc;
}
pa = head->next;
pb = lb.head->next;
lb.head->next = NULL;
pc = head;
size += lb.size;
while(pb != NULL)
{
pc->next = pa;
pc = pa;
pa = pa->next;
pc->next = pb;
pc = pb;
pb = pb->next;
}
pc->next = pa;
}
[/code]
10 楼
雪光风剑 [专家分：27190] 发布于 2007-01-07 13:12:00
[quote]size = la.Size() + lb.Size();
if(la.Size() >= lb.Size() )
--------------------
la.Size() 是肯定大于lb.Size()的,
la.Size()已经是它们原来值的和了
[code]
template<class T>
void LinList<T>::add(LinList<T> &lb)
{
ListNode<T> *pa,*pb,*pc;
if(size < lb.size) // 使lb始终为size较小的链表
{
int temp = size;
size = lb.size;
lb.size = temp;
pc = head;
head = lb.head;
lb.head = pc;
}
pa = head->next;
pb = lb.head->next;
lb.head->next = NULL;
pc = head;
size += lb.size;
while(pb != NULL)
{
pc->next = pa;
pc = pa;
pa = pa->next;
pc->next = pb;
pc = pb;
pb = pb->next;
}
pc->next = pa;
}
[/code][/quote]
昏
对阿……
居然没注意到
晕死
我来回复
您所在位置：