线性表(List):零个或多个数据元素的有限序列。
一、 线性表的抽象数据类型定义
ADT 线性表(List)
Data
线性表的数据对象集合为{a1,a2,...an},每个元素的类型均为DataType.数据元素之间的关系是一对一关系。
Operation
InitList(*L): 初始化操作,建立一个空的线性表L.
ListEmpty(L): 若线性表为空,返回true, 否则返回false.
ClearList(*L): 将线性表清空。
GetElem(L, i, *e): 将线性表L中的第i个位置元素值返回给e
LocateElem(L, e):在线性表L中,查找与给定值e相等的元素,如果查找成功,返回该元素在表中的序号表示成功。否则,返回0表示失败。
ListInsert(*L, i, e): 在线性表L中的第i个位置插入新元素e.
ListDelete(*L, i, *e):删除线性表L中第i个位置元素,并用e返回其值。
ListLength(L): 返回线性表L的元素个数。
endADT
二、线性表的顺序存储结构
线性表的顺序存储结构,指的是用一段连续的存储单元依次存储线性表的数据元素

#define MAXSIZE 20 //存储空间初始分配量
typedef int ElemType; //ElemType类型根据实际情况而定,这里假设为int
typedef struct {
ElemType data[MAXSIZE];//数组存储数据元素,最大值为MAXSIZE
int length; // 线性表当前长度
}SqList;
描述顺序存储结构需要三个属性:
- 存储空间的起始位置:数组data,它的存储位置就是存储空间的存储位置。
- 线性表的最大存储容量: 数组长度MaxSize。
- 线性表的当前长度:length.

1. 获取元素操作
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
/*Status是函数的类型,其值是函数结果状态代码,如OK等*/
/*初始条件:顺序线性表L已存在,1<=i<=ListLength(L)*/
/*操作结果:用e返回L中第i个元素的值*/
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;
}
2. 插入操作
插入算法思路:
- 如果插入位置不合理,抛出异常;
- 如果线性表长度大于等于数组长度,则抛出异常或动态增加容量;
- 从最后一个元素开始向前遍历到第i个位置,分别将它们都向后移动一个位置;
- 将要插入元素填入位置i处;
- 表长加1
/*初始条件: 顺序线性表L已存在,1<=i<=ListLength(L),*/
/*操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1*/
Status ListInsert(SqList *L, int i, ElemType e)
{
int k;
if (L->length == MAXSIZE) /**顺序线性表已经满*/
return ERROR;
if (i<1 || i>L->length+1) //当i不在范围内时
return ERROR;
if (1<=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;
}
3. 删除操作
删除算法思路:
- 如果删除位置不合理,抛出异常
- 取出删除元素;
- 从删除元素位置开始遍历到最后一个元素位置, 分别将它们都向前移动一个位置
- 表长减1
/*初始条件:顺序线性表L已经存在,1<=i<=ListLength(L) */
/*操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1 */
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;
}
线性表 存,读数据时 时间复杂度为O(1)
线性表 插入、删除时 时间复杂度为O(n)
