线性表的顺序表示和实现（严蔚敏版）

定义变量

#include		//输入输出头文件
#include			//malloc和free都在这个头文件里
#define LIST_INIT_SIZE 100//线性表存储空间的初始分配量
#define LISTINCREMENT	10//线性表存储空间的分配增量
#define TRUE		1
#define FALSE		0
#define OK			1
#define ERROR		0
#define INFEASIBLE	-1
#define OVERFLOW	-2
typedef int Status;//函数类型，其值是函数结果状态代码
typedef int ElemType;
#define maxList		10
ElemType* q;
ElemType* p;
ElemType* pa;
ElemType* pb;
ElemType* pc;
ElemType* pa_last;
ElemType* pb_last;
int i;
/******************元素类型*******************/
typedef struct {
	ElemType* elem;//存储空间基址，L.elem[5]为第六位的地址
	int length;		//当前长度
	int listsize;	//当前分配的存储容量（以sizeof（ElemType）为单位）
}SqList;

初始化线性表

创建一个空表，并将length置零，初始化存储容量

Status  InitList_Sq(SqList& L)
{
	//构建一个空的线性表L
	L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));//给L分配一个地址
	if (!L.elem)exit(OVERFLOW);		//exit函数是退出应用程序，并将应用程序的一个状态返回给OS
									//此句表示，如果分配失败，退出程序，返回值为OVERFLOW（-2）
	L.length = 0;					//初始化长度为0
	L.listsize = LIST_INIT_SIZE;	//初始存储容量
	return OK;//返回1
}

插入元素

顺序表插入元素即为在位置i处插入一个元素，将原来i位置之后的所有元素向后移一位。 可以很明显的看出，此时的时间复杂度是线性的。

/***********插入**************/
Status ListInsert_Sq(SqList& L, int i, ElemType e)
{
	ElemType* newbase;
	//在顺序表L中插入第i个位置之前插入新的元素e
	//i的合法性  0= q; --p)
		*(p + 1) = *p;					//插入位置及向后的元素右移
	*q = e;			//插入e
	++L.length;		//表长+1
	return OK;

}

删除线性表中的元素

在顺序表中，删除一个元素和插入一个元素的操作非常相似。删除一个元素即是将i位置之后的所有元素向前移一位。 在顺序存储结构中，插入或者删除一个元素，平均移动线性表中一半元素，时间复杂度均是O（n）。

/**************************删除第i个元素********************************/
Status ListDelete_Sq(SqList& L, int i, ElemType& e)
{
	//在顺序表中删除第i个元素，并用e返回其值
	//i的合法性，0