BJFU-225-基于链表的两个递增有序序列的合并

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 typedef struct lnode{
  4     int num;
  5     struct lnode * next;
  6 }lnode,*linklist;
  7 
  8 typedef struct link{
  9     linklist data;
 10     struct link * next;
 11 }link,*list;
 12 void creatlist(linklist &l,int n)
 13 {
 14     l = (linklist)malloc(sizeof(lnode));
 15     l->next = null;
 16     linklist rear = l;
 17 
 18     for(int i=1;i<=n;i++)
 19     {
 20         linklist p = (linklist)malloc(sizeof(lnode));
 21 
 22         scanf("%d",&p->num);
 23         rear->next = p;
 24         p->next = null;
 25         rear = p;
 26     }
 27 }
 28 void traverse(linklist l)
 29 {
 30     linklist p = l->next;
 31     while(p)
 32     {
 33         if(p->next==null)
 34         {
 35             printf("%d",p->num);//最后一个数字的输出不能有空格，不然编译通不过。不要问我为什么！！！
 36         }else{
 37             printf("%d ",p->num);
 38         }
 39 
 40         p = p->next;
 41     }
 42     printf("\n");
 43 }
 44 linklist mergelist(linklist la,linklist lb,int n,int m)
 45 {
 46     linklist lc,a,b,c;
 47     lc = la;
 48     a = la->next;
 49     b = lb->next;
 50     c = lc;
 51 
 52     while(a&&b)
 53     {
 54         if(a->num > b->num)
 55         {
 56             c->next = b;
 57             c = b;
 58             b = b->next;
 59         }else if(a->num==b->num)
 60         {
 61             linklist q = b;
 62             c->next = a;
 63             c = a;
 64             a = a->next;
 65             b = b->next;
 66             free(q);
 67         }else
 68         {
 69             c->next = a;
 70             c = a;
 71             a = a->next;
 72         }
 73     }
 74 
 75     c->next = a?a:b;
 76     free(lb);
 77     return lc;
 78 }
 79 int main()
 80 {
 81     int n,m;
 82 
 83     list lc = (list)malloc(sizeof(link));
 84     list r = lc;
 85     while(1)
 86     {
 87         scanf("%d%d",&n,&m);
 88         if(n==0&&m==0) break;
 89         linklist la,lb;
 90         creatlist(la,n);
 91         creatlist(lb,m);
 92 
 93         list pc = (list)malloc(sizeof(link));
 94         linklist lc = mergelist(la,lb,n,m);
 95         pc->data = lc;
 96         r->next = pc;
 97         r = pc;
 98         pc->next = null;
 99 
100     }
101     list p = lc->next;
102     while(p)
103     {
104         traverse(p->data);
105         p = p->next;
106     }
107 }