ls.cpp

数据结构中所有算法的实现

#include "head.h"

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

typedef char ElemType;
typedef struct{
  ElemType *elem;
  int length;
  int listsize;
}SqList;

Status InitList(SqList &L){
  //Create a empty sequent list
  L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
  if(L.elem==NULL)exit(OVERFLOW);
  L.listsize=LIST_INIT_SIZE;
  L.length=0;
  return OK;
}//InitList

Status DestroyList(SqList &L){
  //Destroy a exist list
  free(L.elem);
  L.length=0;
  L.listsize=0;
  return OK;
}//DestroyList
Status ClearList(SqList &L){
  //clear a exist list to empty list
  L.elem=(ElemType*)realloc(L.elem,LIST_INIT_SIZE*sizeof(ElemType));
  if(!L.elem) return ERROR;
  L.listsize=100;
  L.length=0;
  return OK;
}//ClearList
Status ListEmpty(SqList L){
  //if list is empty ,return OK,else return FALSE
  if(L.length==0)return OK;
  else return FALSE;
}
Status ListLength(SqList L){
  //Return the length of a exist list
  return L.length;
}
Status GetElem(SqList L,int i,ElemType &e){
  //return the value of element i use e
  //1<=i<=Listlength(L)
  if(i>L.length||i<1)return ERROR;
  e=L.elem[i-1];  //e=*(L.elem+i);
  return OK;
}
//-------------------------------------------------------
Bool Compare(ElemType e1,ElemType e2){
  Bool z;
  if(e1==e2)z=1;
  else z=0;
  return z;
}
Status LocateElem(SqList L,ElemType e,Bool (*Compare)(ElemType,ElemType)){
  //return the first element NO that compare e is true
  int i=1;
  if(L.length<=0)return ERROR;
  while(i<=L.length&&!Compare(L.elem[i-1],e))i++;
  if(i<=L.length) return i;
  else return ERROR;
}
//--------------------------------------------------------
Status PriorElem(SqList L,ElemType cur_e,ElemType &pre_e){
  int i;
  i=LocateElem(L,cur_e,Compare);
  if(i<=1)return ERROR;
  pre_e=L.elem[i-1-1];
  return OK;
}

Status NextElem(SqList L,ElemType cur_e,ElemType &next_e){
  int i;
  i=LocateElem(L,cur_e,Compare);
  if(i<1||i>=L.length)return ERROR;
  next_e=L.elem[i+1-1];
  return OK;
}
Status ListInsert(SqList &L,int i,ElemType e){
  ElemType *newbase,*p,*q;
  if(i<1||i>L.length+1)return ERROR;
  if(L.listsize<=L.length){
    newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
    if(!newbase)return ERROR;
    L.elem=newbase;
    L.listsize+=LISTINCREMENT;
  }
  q=&(L.elem[i-1]);
  p=&(L.elem[L.length-1]);
  for(;p>=q;--p)*(p+1)=*p;
  *q=e;
  ++L.length;
  return OK;
}
Status ListDelete(SqList &L,int i,ElemType &e){
  ElemType *p,*q;
  if((i<1)||(i>L.length))return ERROR;
  p=&(L.elem[i-1]);
  e=*p;
  q=L.elem+L.length-1;
  for(++p;p<=q;++p) *(p-1)=*p;
  --L.length;
  return OK;
}
void visit(ElemType e){
  printf("%c",e);
}
void ListTraverse(SqList &L,void (*visit)(ElemType e)){
  int i;
  for(i=0;i<L.length;i++) visit(L.elem[i]);
  printf("\n");
}