数据结构（C++版）——顺序表

一、顺序表有关的基本操作

1、InitList(&L)：初始化线性表，构造一个空的线性表L

2、DestroyList(&L)：销毁线性表L

3、ClearList(&L)：将线性表L重置为空表

4、ListEmpty(L)：若L为空表，则返回TURE，否则返回FALSE

5、GetElem(L,i,&e)：用e返回L中第i个数据元素的值

6、LocateElem(L,e)：在线性表中查找与指定值相同的数据元素的位置，找到返回该元素的位置序号，未找到返回FALSE

7、ListInsert(&L,i,e)：在L中第i个位置前插入新的数据元素e，L的长度加1

8、ListDelete(&L,i,&e)：删除L的第i个元素，并用e返回其值，L的长度减1

二、代码实现

顺序表动态存储结构定义：

#define LIST_INIT_SIZE  100   //线性表存储空间的初始分配量
#define LISTINCREMENT   10    //线性表存储空间的分配增量
typedef  struct{
       ElemType  *elem; //存储空间基址
       int length;      //当前存储元素个数
       int listsize;    //当前分配的存储容量（以sizeof(ElemType)为单位）
}SqList;

1、InitList(&L)：初始化线性表，构造一个空的线性表L

int InitList(SqList& L){
	L.elem = new ElemType(LIST_INIT_SIZE );
	if (!L.elem) exit(OVERFLOW);//存储分配失败
	L.length = 0;
	L.listsize = LIST_INIT_SIZE;
	return OK;
}

  2、DestroyList(&L)：销毁线性表L

void DestroyList(SqList& L){
	if (L.elem) 
         delete L.elem;
}

3、ClearList(&L)：将线性表L重置为空表

void ClearList(SqList& L){
	L.length = 0;
}

4、ListEmpty(L)：若L为空表，则返回TURE，否则返回FALSE

int ListEmpty(SqList L){
	if (L.length==0)   return TRUE;
	else return FALSE;
}

5、GetElem(L,i,&e)：用e返回L中第i个数据元素的值

int GetElem(SqList L, int i, ElemType& e){
	if (i<1 || i>L.length)   return ERROR;  
	e = L.elem[i - 1];
	return OK;
}

6、LocateElem(L,e)：在线性表中查找与指定值相同的数据元素的位置，找到返回该元素的位置序号，未找到返回FALSE

int LocateElem(SqList L, ElemType e){
	for (int i = 0; i < L.length; i++){
		if (L.elem[i] == e)   return i + 1;
	}
	return FALSE;
    //或用while
	/*int i = 0;
	while (i < L.length && L.elem[i] != e)  i++;
	if (i < L.length)  return i + 1;
	else return FALSE;*/
}

时间复杂度：O(n)

7、ListInsert(&L,i,e)：在L中第i个位置前插入新的数据元素e，L的长度加1

int ListInsert(SqList& L, int i, ElemType e)  //i是插入线性表的位置，不是下标
{
	if (i<1 || i>L.length + 1) return ERROR;
    if (L.length == L.listsize)  return ERROR;  //存储空间已满，返回ERROR
	for (int j = L.length - 1; j >= i - 1; j--)
	{
		L.elem[j + 1] = L.elem[j];    //插入位置及以后的元素后移
	}
	L.elem[i - 1] = e;
	L.length++;
	return OK;
}

时间复杂度：O(n)

8、ListDelete(&L,i,&e)：删除L的第i个元素，并用e返回其值，L的长度减1

int ListDelete(SqList& L, int i, ElemType& e) {
	if (i<1 || i>L.length)   return ERROR;  //i值不合法
	e = L.elem[i - 1];
	for (int j = i; j <= L.length - 1; j++) {
		L.elem[j - 1] = L.elem[j];     //被删除元素之后的前移
	}
	L.length--;
	return OK;
}

时间复杂度O(n)