/*
数据结构上机实验1：有序单链表合并10.29
*/
#include<stdio.h>
#include<stdlib.h>
#define OK 1    //正常
#define ERROR 0 //错误
typedef int Status; //定义返回值类型
typedef int Elemtype; //定义数据元素类型
typedef struct LNode
 {
  Elemtype data;
  struct LNode *next;
 }LNode,*Linklist;

 Status Createlist_L(Linklist &L,int n)
 {
  int k;
  Linklist p;
   printf("请按递减顺序输入%d个元素：",n);
  L=(Linklist)malloc(sizeof(LNode));
  if(L==NULL)
 return ERROR;   //头插链表
  L->next=NULL;  //将最后一个节点的指针域赋空
  for(k=n;k>0;k--)
  {
   p=(Linklist)malloc(sizeof(LNode));
   if(p==NULL)
    return ERROR;
   scanf("%d",&p->data);
   p->next=L->next;
   L->next=p;
  }//for
return OK;
 }//status建立n个节点的单链表

void Display(Linklist &L)
 {
  Linklist p=L;
  p=p->next; //指针指到有数据的第一个节点
  while(p!=NULL)
  {
    printf("%d,",p->data);
      p=p->next;
  }

 }//输出单链表

void Unlist(Linklist &la,Linklist &lb)
{
 Linklist ha,h1,hb,temp;  //定义h1,ha两个相邻节点指针，便于在两者中间进行插入操作；temp用于暂时指向要被插入或删除的节点
 h1=ha=la;  
 ha=ha->next;
 hb=lb->next;
 while(ha!=NULL&&hb!=NULL)
 {
  if(hb->data>ha->data)
  {
   h1=h1->next;
   ha=ha->next;
  }  //大于时h1,ha向后以一个节点作比较
  else
   if(hb->data<ha->data)  //此时插入到h1所指节点后面
   {
       h1->next=hb;
       temp=hb;   //将b节点的地址付给temp，便于hb后移地址不丢失
       hb=hb->next; //hb后移
       temp->next=ha; 
       h1=temp;    //把temp节点插入到h1后
   }
     else
   if(ha->data==hb->data)
   {
                temp=hb->next;
       free(hb);  //释放hb空间
       hb=temp->next;  //hb后移一节点
       h1->next=temp;
       temp->next=ha;
   }
 //有值相同的节点删去h1指向hb的下一个节点，进入比较
 }
 if(ha==NULL&&hb!=NULL)
     h1->next=hb;    //当b节点有剩余时，直接连到la末尾极
}//合并两个有序链表

 int main()
 {
  int m,n;
  Linklist la,lb;
  printf("请输入链表a的长度：\n");
  scanf("%d",&m);
  printf("请输入链表b的长度：\n");
  scanf("%d",&n);
  Createlist_L(la,m);  //建立单链表
  Createlist_L(lb,n);
  Unlist(la,lb);
  Display(la);
     return 0;
 }
 

参考书目：清华大学<数据结构>