# 线性表

# 定义

零个或多个数据元素的有限序列。

强调几个点:

序列: 元素之间存在顺序，若元素存在多个，则第一个元素无前驱，最后一个元素无后继。
有限: 计算机中处理的对象都是有限的，无限的序列，只存在于数学的概念中。

# 线性表的操作方法

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的元素个数 */

# 线性表的顺序存储结构

线性表的顺序存储结构：指的是用一段地址连续的存储单元依次存储线性表的数据元素。

#define MAXSIZE 20  /* 存储空间初始分配量 */
typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */
typedef struct
{
    ElemType data[MAXSIZE];	/* 数组存储数据元素，最大值为MAXSIZE */
    int length;	/* 线性表当前长度 */
}SqList;

由此可见描述顺序存储结构需要三个属性:

存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。
线性表的最大存储容量：数组长度MaxSize。
线性表的当前长度：length。

# 数组长度与线性表长度的区别

数组的长度：存放线性表的存储空间的长度，存储分配后这个量一般是不变的。
线性表的长度：线性表中元素的个数，随着线性表插入和删除，量是变化的。

# 地址计算方法

数组的下标是从0开始的，于是第i个元素是存储在数组下标为i-1的位置。

存储器中每个存储单元都有自己的编号，这个编号称为地址。

假设LOC表示获得存储位置的函数，且每个元素(不考虑类型)占用c个存储单元。

那么线性表第i+1个数据元素的存储位置和第i个数据元素的存储位置满足以下关系：

LOC(a(i+1)) = LOC(a(i)) + c

通过这个公式可以计算出线性表任意位置的地址，不管是第一个还是最后一个，都是相同的时间。我们对于每个线性表位置的存入或者取出数据的时间，都是一个常数，所以它的时间复杂度为O(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;
}

# 插入操作

插入算法思路:

如果插入位置不合理，抛出异常
如果线性表长度大于等于数组长度，则抛出异常或动态增加容量
从最后一个元素开始向前遍历到第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 > length + 1) /* 当i不在范围内时 */
		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;
}

# 删除操作

删除算法的思路:

如果删除位置不合理，抛出异常
取出删除元素
从删除元素位置开始遍历到最后一个元素位置，分别将它们向前移动1个位置
表长减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(n)。

# 线性表顺序存储结构的优缺点

优点:

无须为表示表中元素之间的逻辑关系而增加额外的存储空间
可以快速地存取表中任一位置的元素

缺点:

插入和删除操作需要移动大量元素
当线性表长度变化较大时，难以确定存储空间的容量
造成存储空间的碎片

# 线性表的链式存储结构

← 算法