/*-------------------------------------
程序说明：线性链表头文件 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);
}
}
