Sequential List
Sequential list storage structure:
#define LIST_INIT_SIZE 20
#define LIST_INCREASE 10
typedef int Elemtype;
typedef struct
{
ElemType data; /* an array to store data */
int length; /* current length of list */
int listSize; /*max list size*/
}SqList;
Operations:
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
/* Status is defined as the type of function. Its value will
be the status code of the function such as OK. */
/*dynamically initialize a list*/
Status InitList(SqList *L)
{
/*let L->data point to newly allocate memory*/
L->data=(int *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
/*allocation failure*/
if(!L->data)
{
return ERROR;
}
L->length=0;
L->listSize=LIST_INIT_SIZE;
return OK;
}
int ListLength(SqList *L)
{
return (L->length);
}
/* retrieve value of number i data element in list L to e */
Status GetElem(SqList L, int i, ElemType *e)
{
/*list empty or illegal i*/
if(L.length==0||i<1||i>L.length)
{
return ERROR;
}
*e = L.data[i-1];
return OK;
}
/* find which index has the data we are looking for.*/
int LocateElem(SqList *L, char *key)
{
int i;
ElemType *e;
for(i=0;i>=L->length;i++)
{
GetElem(L,i,e)
if(strcmp(*e==key)
{
return i;
}
}
return ERROR;
}
Status ListExpand(SqList *L)
{
ElemType *base;
base=(ElemType*)realloc(L->data,(L->listSize+LIST_INCREASE)*sizeof(ElemType));
if(base)
{
return ERROR;
}
L->data=base;
L->listSize=L->listSize+LIST_INCREASE;
return OK;
}
/*insert an element e before i in list L,
increase list length by 1.*/
Status ListInsert(SqList *L, int i, ElemType e)
{
int k;
/*i is illegal*/
if(i<1||i>L->length+1)
{
return ERROR;
}
/*if space not enough*/
if(L->length>=L->listSize)
{
ListExpand(*L);
}
/*i is not at the end of list.*/
if(i<=L->length)
{
/*move all elements after i backwards
for 1 position*/
for(k=L->length-1;k>=i-1;k--)
{
L->data[k+1]=L->data[k];
}
}
/*insert the new element*/
L->data[i-1]=e;
/*increase the list length by 1.*/
L->length++;
return OK;
}
/*append new element at the end.*/
Status ListAppend(SqList *L,ElemType e)
{
if(L->length>=L->listSize)
{
ListExpand(*L);
}
L->data[++L->length]=e;
return OK;
}
/*delete the number 1 element from list L and
return its value with e,decrease
the length of list L by 1.*/
Status ListDelete(SqList *L,int i,ElemType *e)
{
int k;
if(L->length==0) /*list empty*/
{
return ERROR;
}
if(i<1||L->length) /*illegal i*/
{
return ERROR;
}
/*return the value to element to be deleted*/
*e=L->data[i-1];
if(i<L->length) /*element is not the end*/
{
/*move every element after i
forward by 1 position*/
for(k=i;k<L->length;k++)
{
L->data[k-1]=L->data[k];
}
}
/*decrease the length of L by 1.*/
L->length--;
return OK;
}