seqlist.cpp

分水问题

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

#include "seqlist.h"

Status InitList_Sq(SqList &L)
{//构造一个空表L
  L.elem=(ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType)); //为表L动态分配存储空间
  if(!L.elem) return OVERFLOW;     //存储分配失败
  L.length=0;                      //空表长度为0
  L.listsize=LIST_INIT_SIZE;     //初始存储容量
  return OK;
}//InitList_Sq

Status DestroyList_Sq(SqList &L)
{ //表L已存在,销毁表L
      if(!L.elem) return ERROR;   // 若表L不存在
      free(L.elem);              // 若表L已存在，回收存储空间
      L.elem=NULL;
      L.length = 0;
      L.listsize = 0;
     // L.incresize=0;
      return OK;
}// DetroyList_Sq

Status ClearList_Sq(SqList &L)
{//表L已存在,将表L置空
   if (!L.elem) return ERROR;  // 若表L不存在
   L.length = 0;              //若表L已存在，将L置空
   return OK;
}// ClearList_Sq

Status ListEmpty_Sq(SqList L)
{//表L已存在
  if(L.length!=0) return FALSE;
  return TRUE;
}

int ListLength_Sq(SqList L)
{ //表L已存在
  return(L.length);
}

Status GetElem_Sq(SqList L, int i, ElemType &e)
{//表L已存在,将表L中第i 个元素赋值给 e
 if ((i<1)||(i>L.length)) return ERROR;
 e=L.elem[i-1];    //将表L中第i 个元素赋值给 e
 return OK;
}// GetElem_Sq

int LocateElem_Sq(SqList L,ElemType e, int(*compare)(ElemType e1,ElemType e2))
{/* 表L已存在,在L中查找与元素e满足关系compare()的第1个元素，返回该元素在表中的序号，
若表中不存在这样的元素，则返回0*/
  int i;
  if(L.length==0) return 0;
  i=0;
  while(i<=L.length-1&&!compare(L.elem[i],e))i++;
  if(i<=L.length-1) return(i+1);
  else return 0;
}//LocateElem_Sq

/*
ElemType *LocateElem_Sq(SqList L,ElemType e, Status(*compare)(ElemType e1,ElemType e2))
{// 表L已存在,在L中查找与元素e满足关系compare()的第1个元素，返回该元素的地址，若表中不存在这样的元素，则返回0
  int i;
  if(L.length==0) return NULL;
  i=0;
  while(i<=L.length-1&&!compare(L.elem[i],e))i++;
  if(i<=L.length-1) return(&L.elem[i]);
  else return NULL;
}//LocateElem_Sq
*/


Status ListInsert_Sq(SqList &L, int i, ElemType e)
{  //表L已存在,在表L中第i个位置之前插入新的元素e, i的合法值为1≤i≤ListLength_Sq(L)+1
  ElemType *newbase,*p,*q;
  if (i<1||i>L.length+1) return ERROR;     //i不合法
  if (L.length>=L.listsize)
  { //空间已满，重新分配空间
      newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
      if (!newbase) return OVERFLOW;//存储分配失败
      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;               //插入e
  ++(L.length);       //表长增1
  return OK;
}//ListInsert_Sq

Status ListDelete_Sq(SqList &L, int i, ElemType &e)
{ //表L已存在,在表L中删除第 i个元素，并用e返回其值   i的合法值为  1≤i≤L.length，
  ElemType *p,*q;
  if ((i<1)||(i>L.length)) return ERROR;  // 参数i不合法
  p=&(L.elem[i-1]);                       //p为被删除元素的位置
  e=*p;                                   // 被删除元素的值赋给e
  q=&L.elem[L.length-1];                  // 表尾元素的位置
  for (++p; p<=q;++p)*(p-1)=*p;           //被删除元素之后的元素前移
  --L.length;                             //表长减1
 return OK;
}//ListDelete_Sq

Status ListAppend_Sq(SqList &L, ElemType e) {
	//将元素e附加在表尾   
	ElemType *newbase;
	if (L.length>=L.listsize)
	{ //空间已满，重新分配空间
       newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
       if (!newbase) return OVERFLOW;//存储分配失败
       L.elem=newbase; 
       L.listsize+=LISTINCREMENT; //增加存储容量
	}
	 L.elem[L.length] = e; //将元素e插入在表尾
	 ++L.length; // 表长增1	
	 return 1;
}          

Status ListTraverse_Sq(SqList L,void(*Visit)(ElemType e))
{//表L已存在,遍历表L
    ElemType *p,*q;
    p=L.elem;
    q=&L.elem[L.length-1];
    for(p;p<=q;++p) Visit(*p);
    return OK;
}