AAAA级问题，老师最后通牒：链表的合并和数据排序
下面是我老师交给的作业，使属于课件设计类，我把代码已经编好，可是怎么也实现不了预期功能
望各位仁兄，救救我吧？
基本功能要求：
（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
（3） 用直接插入排序法对C进行升序排序，生成链表D，并输出链表D。
测试数据：
（1） A表（30，41，15，12，56，80）
B表（23，56，78，23，12，33，79，90，55）
（2） A表（30，41，15，12，56，80，23，12，34）
B表（23，56，78，23，12）
以下是我编的代码：
／／／／／／／linlist.h
#include <iostream.h>
#include <stdlib.h>
#include "datatype.h"
template <class T> class linlist;
template<class T> class listnode
{
friend class linlist<T>;
private:
listnode<T> *next;
public:
T data;
listnode(listnode<T> *ptrnext=NULL);
listnode(const T& item,listnode<T> *ptrnext=null);
~listnode(){};
};
template <class T>
listnode<T>::listnode(listnode<T> *ptrnext):next(ptrnext)
{}
template <class T>
listnode<T>::listnode(const T &item,listnode<T> *ptrnext)
{
data=item;
next=ptrnext;
}
template<class T> class linlist
{
private:
listnode<T> *head;
listnode<T> *currptr; //当前接点指针；
public:
int size;
linlist(void);
~linlist(void);
int listsize(void) const;
int listempty(void) const;
listnode<T> *index(int pos); //返回指向第pos个接点的指针；
void insert(const T& item,int pos);
T Delete(int pos);
T getdata(int pos);
void clearlist(void);
listnode<T> *reset(int pos=0); //currptr指向接点pos并返回currptr;
listnode<T> *next(void);
int endoflist(void) const;
};
template <class T>
linlist<T>::linlist()
{
head=new listnode<T>();
size=0;
}
template<class T>
linlist<T>::~linlist(void)
{
clearlist();
delete head;
head=NULL;
}
template <class T>
int linlist<T>::listsize (void) const
{
return size;
}
template<class T>
int linlist<T>::listempty(void) const
{
if(size<=0) return 1;
else return 0;
}
template<class T>
listnode<T> *linlist<T>::index(int pos)
{
if(pos<-1 ||pos>size)
{
cerr<<"参数越界出错！"<<endl;
exit(1);
}
if(pos==-1) return head;
listnode<T> *p=head->next;
int i=0;
while(p!=NULL&& i<pos) //寻找第pos个接点
{
p=p->next;
i++;
}
return p;
}
template<class T>
void linlist<T>::insert(const T &item,int pos)
{
listnode<T> *p=index(pos-1);
listnode<T> *newnode=new listnode<T>(item,p->next);
p->next=newnode;
size++;
}
template<class T>
T linlist<T>::Delete(int pos)
{
if(size=0)
{
cerr<<"链表已经空，没有可删除的元素 "<<endl;
exit(1);
}
listnode<T> *q,*p=index(pos-1);
q=p->next;
p->next=p->next->next;
T data=q->data;
delete q;
seze--;
return data;
}
template<class T>
T linlist<T>::getdata(int pos)
{
listnode<T> *p=index(pos);
return p->data;
}
template<class T>
void linlist<T>::clearlist(void)
{
listnode<T> *p,*q;
p=head->next; //此处P为第一个接点
while(p!=NULL)
{
q=p;
p=p->next;
delete q; //从第一个接点往下删除
}
size=0;
}
template<class T>
listnode<T> *linlist<T>::reset(int pos)
{
if(head==NULL) return NULL;
if(pos<-1 ||pos>size)
{
cerr<<"参数错误"<<endl;
exit(1);
}
if(pos==-1) return head;
if(pos==0) currptr=head->next;
else
{
currptr=head->next;
listnode<T> prevptr=head;
for(int i=0;i<pos;i++)
{
prevptr=currptr;
currptr=currptr->next;
}
}
return currptr;
}
template<class T>
listnode<T> *linlist<T>::next(void)
{
if(currptr!=NULL)currptr=currptr->next;
return currptr;
}
template<class T>
int linlist<T>::endoflist(void) const
{
if(currptr==NULL) return 1;
else return 0;
}
//***********附加部分1***************
void links(linlist<int> A1,linlist<int> A2,linlist<int> A3)
{
int m,n,i,j;
m=A1.listsize();
n=A2.listsize();
//上面是把A1和A2的大小付给m and n;
if(m>=n)
{
cout<<"单链表A的大小是："<<" ";
cout<<m<<endl;
cout<<"数据是："<<" ";
for(i=0;i<m;i++)
cout<<A1.getdata(i)<<" ";
cout<<endl;
cout<<"单链表B的大小是："<<" ";
cout<<n<<endl;
cout<<"数据是："<<"";
for(i=0;i<n;i++)
cout<<A2.getdata(i)<<" ";
cout<<endl;
//以下是实现两个链表合并的过程；
cout<<"以下是实现两个链表合并后的数据"<<endl;
for(i=0;i<m;i++)
A3.insert(A1.getdata(i),i);
for(j=0;j<n;j++)
A3.insert(A2.getdata(j),m+j);
for(i=0;i<m+n;i++)
cout<<A3.getdata(i)<<" ";//现在已经实现了两个链表的合并
}
if(m<n)
{
cout<<"单链表A的大小是：";
cout<<A1.listsize()<<" ";
cout<<"数据是："<<endl;
for(i=0;i<m;i++) //1
cout<<A1.getdata(i)<<""<<endl;
cout<<"单链表B的大小是：";
cout<<A2.listsize()<<" "<<endl;;
cout<<"数据是："<<endl;
for(i=0;i<n;i++) //2
cout<<A2.getdata(i)<<""<<endl;
cout<<"以下是实现两个链表合并后的数据"<<endl;
for(i=0;i<n;i++) //3
A3.insert(A2.getdata(i),i);
for(i=0;i<m;i++) //4
cout<<A3.getdata(i)<< " ,";
for(j=0;j<m;j++) //5
A3.insert(A1.getdata(j),m+j);
for(j=0;j<n;j++) //6
cout<<A3.getdata(m+j)<<" ,";//现在已经实现了两个链表的合并
}
}
//*******************附加部分2---数据排序******************************************
//关键码实现部分
//用直接插入发对a[] ---[n-1]排序
void insertsort(int a[],int n)
{
int i,j;
int temp;
for(i=0;i<n;i++)
{
temp=a[i+1];
j=i;
while(j>-1&& temp<a[j])
{
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
}
}
///////////main.cpp
#include "linlist.h"
void main(void)
{
welcome();
cout<<endl;
int i ,n=100000,num=1,m=1;
int end;
//*****************以下为连表的连接***********************8
linlist<int> A,B,C,D;
cout<<"请输入您的第一个连表数据，按空格键分开数据，按数字“10000”结束连表："<<endl;
for (i=0; i<n && num!=10000;i++)
{
if(num !=10000)
{
cin>>num;
A.insert(num,i);
}
if(num=10000)
A.insert(NULL,i);
}
cout<<"请输入您的第二个连表数据，按空格键分开数据，按数字“100000”结束连表："<<endl;
for (i=0; i<n && num!=100000;i++)
{
cin>>num;
B.insert(num,i);
}
links(A,B,C);
cout<<endl;
//·········下面是第二种扩充————排序············
//cout<<"请输入你选定的数据，我们将给于排序"<<endl;
int w=C.listsize();
//int a[0]=C.getdata(0);
// for(i=0;i<15;i++)
//cin>>a[i];
//cout<<"您输入的15个数据是："<<endl;
//for(i=0;i<w;i++)
//a[i]=C.getdata(i);
//cout<<endl;
//cout<<"下面是排序后的数据："<<endl;
int array[w];
for(i=0;i<w;i++)
array[i]=C.getdata(i);
insertsort(array,w);
for( i=0;i<w;i++)
cout<<array[i]<<",";
}
问题点数：20、回复次数：2Top
1 楼darkstar21cn（≮天残≯无畏)(死亡进行时）回复于 2005-06-04 21:00:48 得分 10
说个想法吧：
（２）用２个指针一个放短链表，另一个放长链表，这么操作就简单多了
（３）链表要能在任意处插入的话就好办了，从ｃ读取一个元素，放到Ｄ对应的位置，就可以了Top
2 楼MagicCarmack（MagiC++）回复于 2005-06-05 04:19:32 得分 10
第2题 大概思想如下：
void merge(LinkList A,LinkList B,LinkList &C)
{
p=A->next;q=B->next;C=A;
while(p&&q)
{
s=p->next;p->next=q; //将B的元素插入
if(s)
{
t=q->next;q->next=s; //如A非空,将A的元素插入
}
p=s;q=t;
}//while
}//mergeTop
相关问题
关键词
得分解答快速导航
相关链接
广告也精彩
反馈
