/*-------------------------------------
  程序说明：线性链表头文件 mylist.h
  日期：    2004.3.26
  作者：    junnyfeng
----------------------------------------*/

#define LIST_INIT_SIZE   20 //初始分配量
#define LISTINCREMENT    10  //增量
typedef int Elemtype;        //自定义基本类型
 
typedef struct
{
 Elemtype *elem;    // 存储空间基址
 int  length;       // 表长
 int  listsize;     //当前分配存储容量
}Sqlist;

int Creatlist_Sq(Sqlist *); // 建一个空表

int Listlength(Sqlist); // 返回表长
   
int ListInsert_Sq(Sqlist *, int i, Elemtype e); // 从第i个位置中插入e，i从1算起

int ListDelete_Sq(Sqlist *, int , Elemtype *);

int ListEmpty_Sq(Sqlist *);  // 空表返回1，否则返回0

int LocateElem_Sq(Sqlist *,int, int compare_elem(Elemtype,Elemtype)); //返回第一个与e相等的位序，否则返回零

int compare_elem(Elemtype,Elemtype); // 比较两个元素，相同返回1，不同返回零

void GetElem(Sqlist, int i, Elemtype *e); // 把第i个位置的元素赋给e

void Clearlist(Sqlist *); //let the length=0,and listsize=LIST_INIT_SIZE

void Destorylist(Sqlist *); //销毁链表

void union_Sq(Sqlist *A,Sqlist B);// 把B表中不在A表的部分接到A的后部

void Mergelist(Sqlist A,Sqlist B,Sqlist *); //A,B表均递增有序，合并到一个新表中，并保持递增

/*-------------------------------------
  程序说明：线性链表及其基本操作函数 mylist.c
  日期：    2004/03/26
  作者：    junnyfeng
----------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include "mylist.h"

int Creatlist_Sq(Sqlist *L)     // 建一个顺序表，成功返回1，不成功返回0
{
 
 L->elem=(Elemtype *)malloc(LIST_INIT_SIZE*sizeof(Elemtype));
 if(!L->elem)
  return 0;
 L->length=0;
 L->listsize=LIST_INIT_SIZE;
 return 1;
}

int Listlength(Sqlist L)
{
 if(L.length)
  return L.length;
 return 0;
}

   
int ListInsert_Sq(Sqlist *L, Elemtype i, Elemtype e) //在表中第i个位置（第一个位置为1）插入一个元素,               
                                                     // return 1 for success,0 for flase
{  
 Elemtype *q,*newbase,*p;
 if(i<1 || L->length+1<i)      //i 的范围可到（当前表长+1），就是插到表最后  
  return 0;
    if(L->length>=L->listsize)
 {
  newbase=(Elemtype *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(Elemtype));
     if(!newbase)
  {
  
   printf("can't assign a newbase\n");
   return 0;
  }
 
  L->elem=newbase;
     L->listsize+=LISTINCREMENT;
 }
 q=&L->elem[i-1];       // 待插入的位置地址q
 for(p=&L->elem[L->length-1];p>=q;p--)
  *(p+1)=*p;
 *q=e;
 L->length++;
 return 1;
}

int ListDelete_Sq(Sqlist *L, Elemtype i, Elemtype *e) //在顺序表中删除第i个元素，并用e返回其值,成功返回1
{
 if(i<1 || i>L->length)
 {
  printf("\ncan't locate the section %d",i);
  exit(1);
 }
 *e=L->elem[i-1];
 while(i<=L->length-1)
 {
  L->elem[i-1]=L->elem[i];
  ++i;
 }
 L->length--;
 return 1;
}

int ListEmpty_Sq(Sqlist *L)
{
 if(L->length==0)
  return 1;
 else return 0;
}

int compare_elem(Elemtype a,Elemtype b)
{
 if(a-b==0)
  return 1;
 else return 0;
}

int LocateElem_Sq(Sqlist *L, Elemtype e, int compare_elem(Elemtype,Elemtype))
{
 int i;
 for(i=0;i<=L->length-1;i++)
 {
  if(compare_elem(L->elem[i],e))
   return i+1;
  
 }
 return 0;
}
   
void GetElem(Sqlist L, int i, Elemtype *e)
{
 if( i<1 || i>L.length) 
 {
  printf("over the bound of the list!");
  system("pause");
  exit(1);
 }

 *e=L.elem[i-1];
}

void Clearlist(Sqlist *L)
{
 if(L->length!=0)
 {
  L->length=0;
  L->listsize=LIST_INIT_SIZE;
 }
}

void union_Sq(Sqlist *A, Sqlist B)
{
 int i,e;
 for(i=1;i<=B.length;i++)
 {
  GetElem(B,i,&e);
  if(!LocateElem_Sq(A,e,compare_elem))
   ListInsert_Sq(A,A->length+1,e);
    }
}
  
void Destorylist(Sqlist *L)
{
 if(L->elem)
 free(L->elem);
}

void Mergelist(Sqlist M,Sqlist L,Sqlist *R)
{
 int ma,la,i,j,k=0;
 i=j=1;
 if(!Creatlist_Sq(R))
 {
  printf("\ncan't creat a list!");
  exit(1);
 }
 while(i<=Listlength(M) && j<=Listlength(L))
 {
  GetElem(M,i,&ma);GetElem(L,j,&la);
  if(ma<la)
  {
   ListInsert_Sq(R,++k,ma);
   i++;
  }

  else
  {
   ListInsert_Sq(R,++k,la);
   j++;
  }
  
 }
 while(i<=Listlength(M))
 {
  GetElem(M,i++,&ma);
  ListInsert_Sq(R,++k,ma);
 }
 while(j<=Listlength(L))
 {
  GetElem(L,j++,&la);
  ListInsert_Sq(R,++k,la);
 }
}