北航 2010年考研复试题2

2.归并两个有序字符串，要求输出不能有重复字符（数据结构上做过N遍的Merge函数）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void Merge(char *a,char *b)
{
    int l1=strlen(a);
    int l2=strlen(b);
    char *c=(char *)malloc((l1+l2+1)*sizeof(char));
    int i=0,j=0,k=0;
    for(;i<l1 && j<l2;)
    {
        if(a[i]<b[j])
        {
            c[k++]=a[i];
            i++;
        }
        else if(a[i]==b[j])
        {
            c[k++]=a[i];
            i++;
            j++;
        }
        else
        {
            c[k++]=b[j];
            j++;
        }
    }
    
    if(i==l1 && j<l2)
    {
        for(;j<l2;j++)
            c[k++]=b[j];
    }
    else if(i<l1 && j==l2)
    {
        for(;i<l1;i++)
            c[k++]=a[i];
    }
    else;
    c[k]='';
    for(i=0;i<k;i++)
        putchar(c[i]);
    printf("
");
    free(c);
}
int main()
{
    char a[500],b[500];
    while(scanf("%s%s",a,b))
    {
        Merge(a,b);
    }
    
return 0;
} 

 

 变形题目：

1.  ///顺序表合并
template <class T>
void Arraylist<T>:: MergeList(Arraylist<T> &pb)
{
 Arraylist<T> pc(curlen+pb.curlen);
 int i=0,j=0,k=0;
 for(i=0,j=0;i<curlen && j<pb.curlen;)
 {

        if(alist[i] < pb.alist[j])
  {
   pc.alist[k++] = alist[i] ;
   i++;
  }
      else
  {
     pc.alist[k++] = pb.alist[j] ;
     j++;
  }
 }
       if(j==pb.curlen && i<curlen)
  {
    for(;i<curlen;i++)
        pc.alist[k++] =alist[i] ;
  }
  else if(i==curlen && j<pb.curlen)
  {
             for(;j<pb.curlen;j++)
     pc.alist[k++] =pb.alist[j] ;
  }
  else;
  cout<<"合并 "<<endl;
  for(i=0;i<curlen+pb.curlen;i++)
   cout<<pc.alist[i]<<' ';
 cout<<endl;
}

2.  //合并两个有序单链表
template <class T>
void Linklist<T>::Merge(Linklist<T> &La,Linklist<T> &Lb)
{
   Linknode<T> *pa,*pb,*pc,*p;
   pa=La.head;
   pb=Lb.head;
   if(pa->data <= pb->data)
   {
  p=pc=pa;//记录头结点是pa还是pb
  pa=pa->link;
   }
   else
   {
    p=pc=pb;
    pb=pb->link;
   }
   while(pa && pb)
   {
      if(pa->data <= pb->data )
    {
   pc->link = pa ;
   pc = pa ;
   pa = pa->link;
  }
  else
   {
   pc->link = pb ;
    pc = pb;
    pb= pb->link ;
  }
 }
   if( pa!=NULL&&pb==NULL)
     pc->link = pa ;
   else
     pc->link = pb ;
   head=p;
   ///pc->link=NULL; //有问题
}