struct LNode
{  // 定义单链表节点类型
    ElemType data;       // 存放结点中的数据信息
    LNode *next;            // 指示下一个结点地址的指针
};

void InitList (LNode* &H)      //初始化单链表
{
  H=(LNode *)malloc(sizeof(LNode));
  if(!H)
    exit(0);       // 存储分配失败，退出系统
    H->next=NULL;     // 指针域为空
}

void ClearList(LNode* &H)    //清除单链表
{
  LNode *cp;
  LNode *np;
  cp=H;
  while(cp!=NULL){
    np=cp->next;
    delete cp;
    cp=np;
  }
  H=NULL;
}

int LengthList (LNode* H)   //求单链表长度
{
  int i=0;
  H=H->next;
  while(H!=NULL){
    i++;
    H=H->next;
  }
  return i;
}

bool EmptyList (LNode* H)      //判断单链表是否为空表
{
  return H->next==NULL;
}

ElemType GetList (LNode* H, int pos)  //取单链表第 pos 位置上的元素  
{
  if(pos<1){
    cerr<<"pos is out range!"<<endl;
    exit(1);
  }
  int i=0;
  H=H->next;
  while(H!=NULL){
    i++;
    if(i==pos)
      break;
    H=H->next;
  }
  if(H!=NULL)
    return H->data;
  else
  {
    cerr<<"pos is out range!"<<endl;
    exit(1);
  }
}

void TraverseList(LNode* H)    //遍历单链表
{
  H=H->next;
  while(H!=NULL){
    cout<<H->data<<" ";
    H=H->next;
  }
  cout<<endl;
}

bool InsertList ( LNode* &H, ElemType item, int pos) //向单链表插入一个元素
{
  if(pos<-1){
    cout<<"pos is illegal!"<<endl;
    return false;
  }
  LNode* newptr;
  newptr=new LNode;
  newptr->data=item;
  LNode* cp=H;
  if(pos==0){
    while(cp!=NULL){
      if(item<cp->data)
        break;
      else
        cp=cp->next;
    }
  }
  else if(pos==-1)
    while(cp!=NULL)
      cp=cp->next;
  else{
    int i=0;
    while(cp!=NULL){
      i++;
      if(i==pos)
        break;
      else
        cp=cp->next;
    }
  }
  newptr->next=cp->next;
  cp->next=newptr;
  return true;
}

bool DeleteList ( LNode* &H, ElemType& item, int pos)   //从单链表中删除一个元素
{
  if(H==NULL){
    cerr<<"H is Null, fail to delete!"<<endl;
    return false;
  }
  if(pos<-1){
    cout<<"pos is illegal!"<<endl;
    return false;
  }
  LNode* cp=H;
  LNode* s=NULL;
  if(pos==0){
    while(cp!=NULL){
      if(item==cp->next->data)
        break;
      else
        cp=cp->next;
    }
    if(cp==NULL){
      cerr<<"error"<<endl;
      return false;
    }
  }
  else{
    int i=0;
    while(cp!=NULL){
      i++;
      if(i==pos)
        break;
      else
        cp=cp->next;
    }
    if(cp==NULL){
      cout<<"pos is illegal!"<<endl;
      return false;
    }
  }
  s=cp->next;
  cp->next=cp->next->next;
  delete s;
  return true;
}

void MergeList(LNode* &La, LNode* &Lb, LNode* &Lc)
{
  LNode* pa=La;
  LNode* pb=Lb;
  LNode* ptr;  //移动指针
  Lc=pa;  //将La的表头作为Lc的表头
  pa=pa->next;
  ptr=pb;
  pb=pb->next;
  delete ptr;  //清空Lb表头
  ptr=Lc;
  while (pa!=NULL && pb!=NULL){
    if (pa->data<=pb->data){
      ptr->next=pa;
      pa=pa->next;
      ptr=ptr->next;
    }
    else{
      ptr->next=pb;
      pb=pb->next;
      ptr=ptr->next;
    }
  }
  ptr->next=(pa==NULL)?pb:pa; //当比较结束后，将La或Lb中剩下的节点接在Lc后面
}

#include<stdio.h>
#include<iostream.h>
#include<stdlib.h>
typedef int ElemType;
#include"LinkList.h"
void main(void)
{
  int i=1,x;
  LNode* list;
  LNode* La;
  LNode* Lb;
  LNode* Lc;
  InitList(list);  //建立链表表头
  scanf("%d", &x);
  while(x!=-1)
  {  
    if(InsertList(list,x,i)==false){ //加入链表各个节点
      printf("错误!\n");
      return;
    }
    i++;
    scanf("%d", &x);
  }
  if(EmptyList(list)!=0) //测试EmptyList函数
    printf("The list is NULL.\n");  
  else
  {
    printf("The length of the list is %d \n",LengthList(list)); //测试LengthList函数
    printf("Traverse the List:\n");
    TraverseList(list); //输出链表
    printf("The top 5 is :\n");
    for(i=1;i<=5;i++)
      printf("%d ",GetList(list,i));  //测试GetList函数，输出前5个节点的值
    printf("\n");
    printf("enter the position you want to insert:\n");  //以下开始测试DeleteList函数
    printf("0: delete the element you want.\n");  //输入0删除具体元素值所在节点
    printf("others >-1: delete the element in that position.\n"); //输入其它（大于-1）按序号删除节点
    scanf("%d",&i);
    if(i==0){
      scanf("%d",&x);
      if(DeleteList(list,x,i)!=0){  //测试删除具体元素值所在节点
        printf("After Detete the element :");
      TraverseList(list);
      }
    }
    else{
      if(DeleteList(list,i,i)!=0){  //删除第i个节点
        printf("After Detete the element in position %d :",i);
      TraverseList(list);
      }
    }
    ClearList(list);  //删除链表
  }
  InitList(La);
  printf("input elements for La: \n");
  i=1;
  scanf("%d", &x);
  while(x!=-1)
  {  
    if(InsertList(La,x,i)==false){ //加入链表各个节点
      printf("错误!\n");
      return;
    }
    i++;
    scanf("%d", &x);
  }
  InitList(Lb);
  printf("input elements for Lb: \n");
  scanf("%d", &x);
  i=1;
  while(x!=-1)
  {  
    if(InsertList(Lb,x,i)==false){ //加入链表各个节点
      printf("错误!\n");
      return;
    }
    i++;
    scanf("%d", &x);
  }
  InitList(Lc);
  printf("after MergeList: \n");
  MergeList(La,Lb,Lc);
  TraverseList(Lc);
}