一、基本概念

顺序表是线性表的顺序存储结构，使用地址连续的存储单元存放数据元素。

顺序表的符号化表示：

假设有n个（n∈N）类型相同的数据元素，其中的第i个元素（1≤i≤n）表示为ai，则该顺序表记为L={a1, a2, …, ai, …, an}(1≤i≤n，n∈N)

顺序表的图形化表示：

顺序表的抽象数据类型：

ADT 顺序表（SqList）
Data
    顺序表的数据元素集合为L={a1, a2, …, ai, …, an}(1≤i≤n，n∈N)，每个元素的类型相同除第一个元素a1外，其他元素有且仅有一个前驱元素除最后一个元素an外，其他元素有且仅有一个后继元素
Operation
    InitList(*L);	# 顺序表初始化
    ListEmpty(L);	# 顺序表判空
    ClearList(L);	# 顺序表清空
    GetElem(L, i, *e);	# 按位查找
    LocateElem(L, e);	# 按值查找
    ListInsert(*L, i, e);	# 按位插入
    ListDelete(*L, i, *e);	# 按位删除
    ListLength(L);	# 返回顺序表的长度（元素个数）
EndADT

二、实现思路

基本思路很简单，就是利用数组和指针，声明顺序表的基本结构，然后对这个基本结构进行增删查改操作，注意增删查改操作是大部分数据结构的基本操作，大部分功能都是由这四个基本操作组成。最后再注意一些细节，例如基本的状态判断、边界判断、输入过滤等，这样做可以有效提高程序的鲁棒性。

将抽奖数据类型中的各个操作按照基本操作分个类：

增：InitList(*L)、ListInsert(*L, i, e)

删：ClearList(L)、ListDelete(*L, i, *e)

查：ListEmpty(L)、GetElem(L, i, *e)、LocateElem(L, e)、ListLength(L)

改：无，实际上“改”操作可以看作先增加新值再删除旧值，当然在顺序表里可以直接根据索引修改

三、代码实现

1. 基本数据结构

（1）状态常量

#define OK 1
#define ERROR 0
#define MAXSIZE 20	/*存储空间的初始分配量*/

（2）顺序表结构

typedef int Status;
typedef int ElemType;	/*ElemType类型可以根据实际情况而定*/
typedef struct {
	ElemType data[MAXSIZE];	/*数组存储数据元素，最大值为MAXSIZE*/
	int length;	/*记录顺序表的当前长度*/
}SqList;

2. 增删改查操作原型

void InitList(SqList *L);	/*初始化操作，建立一个空的顺序表L*/
bool ListEmpty(SqList L);	/*顺序表判空操作，若顺序表为空，返回true，否则返回false*/
void ClearList(SqList *L);	/*清空顺序表*/
Status ListInsert(SqList *L, int i, ElemType e);	/*在顺序表的第i个位置插入元素e*/
Status ListDelete(SqList *L, int i, ElemType *e);	/*删除顺序表L中第i个位置的元素，并用e返回其值*/
Status GetElem(SqList L, int i, ElemType *e);	/*将顺序表L中的第i个位置元素值返回给e*/
int LocateElem(SqList L, ElemType e);	/*在顺序表中查找与给定值e相等的元素，如果查找成功，返回该元素在表中的序号表示成功，否则返回0表示失败*/
int ListLength(SqList L);	/*返回顺序表L的元素个数*/
void UnionList(SqList *La, SqList Lb);	/*合并两个顺序表，将所有在顺序表Lb中但不在La中的数据元素插入到La中*/

3. 增操作

（1）顺序表初始化

/*
	初始化操作，建立一个空的顺序表L，并将其所有数据元素初始化，将顺序表的数据长度置为0
	@param *L 指向顺序表的指针
	@return 无
*/
void InitList(SqList *L) {
	int i;

	for (i = 0; i < MAXSIZE; i++) {
		L->data[i] = 0;
	}

	L->length = 0;
}

（2）按位插入

/*
	插入元素，当顺序表存在时，在顺序表的第i个位置插入元素e，顺序表的数据长度加1
	@param *L 指向顺序表的指针
	@param i 插入的位置
	@param e 插入的元素
	@return 返回插入操作的状态，OK表示插入成功，ERROR表示插入出错
*/
Status ListInsert(SqList *L, int i, ElemType e) {
	int k;

	if (L->length == MAXSIZE) {	/*若顺序表已满，则返回错误信息*/
		return ERROR;
	}

	if (i < 1 || i > L->length + 1) {	/*当插入的位置不在范围内，返回错误信息*/
		return ERROR;
	}

	if (i <= L->length) {	/*当插入的位置不在顺序表表尾*/
		for (k = L->length - 1; k >= i - 1; k--) {	/*将要插入位置后的数据元素依次向后移动一位*/
			L->data[k + 1] = L->data[k];
		}
	}

	L->data[i - 1] = e;	/*插入新元素*/
	L->length++;

	return OK;
}

4. 删操作

（1）顺序表清空

/*
	清空顺序表，删除顺序表中所有数据，并将数据长度置为0
	@param *L 指向顺序表的指针
	@return 无
*/
void ClearList(SqList *L) {
	int i;

	for (i = 0; i < MAXSIZE; i++) {
		L->data[i] = 0;
	}

	L->length = 0;
}

（2）按位删除

/*
	若顺序表存在，删除顺序表L中第i个位置的元素，并用e返回其值，L的长度减1
	@param *L 指向顺序表的指针
	@param i 删除的位置
	@param *e 指向删除元素的指针
	@return 返回删除操作的状态，OK表示删除成功，ERROR表示删除出错
*/
Status ListDelete(SqList *L, int i, ElemType *e) {
	int k;
	if (L->length == 0) {	/*若顺序表为空，则返回错误信息*/
		return ERROR;
	}

	if (i < 1 || i > L->length) {
		return ERROR;	/*如果删除的位置不正确，返回错误信息*/
	}

	*e = L->data[i - 1];	/*获取被删除的元素*/

	if (i < L->length) {	/*如果删除的不是最后位置*/
		for (k = i; k < L->length; k++) {
			L->data[k - 1] = L->data[k];	/*将删除的元素后的所有元素依次前移*/
		}
	}

	L->length--;
	return OK;
}

5. 查操作

（1）顺序表判空

/*
	顺序表判空操作，若顺序表为空（即数据长度为0），返回true，否则返回false
	@param L 已初始化的顺序表
	@return 返回一个布尔值
*/
bool ListEmpty(SqList L) {
	if (L.length > 0) {
		return false;
	} else {
		return true;
	}
}

（2）按位查找

/*
	按位查找，将顺序表L中的第i个位置元素值返回给e
	@param L 已初始化的顺序表
	@param i 查找的位置
	@param *e 指向查找元素的指针
	@return 返回查找操作的状态，OK表示查找成功，ERROR表示查找出错
*/
Status GetElem(SqList L, int i, ElemType *e) {
	if (L.length == 0 || i < 1 || i > L.length) {	/*当顺序表为空，或查找位置超出范围时，返回错误信息*/
		return ERROR;
	}

	*e = L.data[i - 1];

	return OK;
}

（3）按值查找

/*
	在顺序表中查找与给定值e相等的元素，如果查找成功，返回该元素在表中的序号表示成功，否则返回0表示失败
	@param L 已初始化的顺序表
	@param e 待查找的元素
	@return 查得元素的顺序表位置序号
*/
int LocateElem(SqList L, ElemType e) {
	if (L.length == 0) {	/*若顺序表为空，则返回错误信息*/
		return 0;
	}

	int k;
	for (k = 0; k < L.length; k++) {	/*遍历顺序表，对比每个元素值与给定元素值*/
		if (L.data[k] == e) {
			return k;
		}
	}

	return 0;
}

（4）获取顺序表长度（元素个数）

/*
	返回顺序表L的元素个数
	@param L 已初始化的顺序表
	@return 顺序表中当前元素个数
*/
int ListLength(SqList L) {
	return L.length;
}

6. 基本操作综合应用案例：合并顺序表

/*
	合并两个顺序表，将所有在顺序表Lb中但不在La中的数据元素插入到La中
	@param *La	指向链表a的指针
	@param Lb	已初始化的链表b
*/
void UnionList(SqList *La, SqList Lb) {
	int La_len, Lb_len, i;
	ElemType e;

	La_len = ListLength(*La);
	Lb_len = ListLength(Lb);	/*获取两个顺序表的长度*/

	for (i = 1; i < Lb_len; i++) {
		GetElem(Lb, i, &e);	/*取出Lb中第i个数据元素赋值给e*/
		if (!LocateElem(*La, e)) {	/*La中不存在和e相同的数据元素时，将该数据元素插入La中*/
			ListInsert(La, ++La_len, e);
		}
	}
}

四、时间复杂度分析

增：如果在顺序表表头增加一个元素，那么首元素之后的所有元素都要向后挪一个位置，那么时间复杂度为O(n)，如果在表尾增加一个元素，就没有需要挪动的元素，时间复杂度为O(1)。综合起来，平均时间复杂度还是O(n)。

删：如果在顺序表表头删除一个元素，那么首元素之后的所有元素都要向前挪一个位置，那么时间复杂度为O(n)，如果在表尾删除一个元素，就没有需要挪动的元素，时间复杂度为O(1)。综合起来，平均时间复杂度还是O(n)。

查：按位查找可以直接根据索引找到对应的元素，所以时间复杂度为O(1)；按值查找需要遍历顺序表，逐个比较顺序表中元素与给定元素是否相同，最好的情况是，在表头就找到了目标值，此时时间复杂度为O(1)，最差的情况是，遍历到表尾最后一个元素才找到目标值，此时的时间复杂度为O(n)，综合一下，平均时间复杂度还是O(n)。

五、顺序表的优缺点

优点：

（1）空间资源占用相对较少；

（2）可以进行随机存取

缺点：

（1）增删操作时间开销大

（2）顺序表的容量固定，不能动态拓展

（3）必须使用连续的地址存储数据元素，容易造成存储空间碎片

---

参考资料：

[1] 大话数据结构. 程杰.

[2] 数据结构（C语言版）. 严蔚敏, 吴伟民.