---

定义

顺序表使用一组地址连续的存储单元，依次存储线性表中的数据元素，使得逻辑上相邻的两个元素在物理位置上也相邻。

当做数组来思考与使用。

大致为这个样子：

线性表顺序存储描述为：

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int lenght;
}Sqlist;

优缺点

随机访问快，因为地址连续，可通过地址直接访问。
插入删除慢，因为需要移动大量元素，所以慢。

 

顺序表的操作

只需要掌握插入、删除、查找

1.插入

 

 

bool ListInsert(SqList &L,int i,ElemType e){
	if(i<1 || i>L.length + 1)
		return false;
	if(L.length >= MaxSize)
		return false;

	for(int j = L.length;j>=i;j--){
		L.data[j] = L.data[j-1];
	}
	L.data[i-1] = e;
	L.length++;
	return true;
}

第一步，判断插入的位置对不对，不可小于1，因为1是最开始的位置；不可大于长度 +1，因为最后一个元素所在位置为长度最大处，但插入时可以插入到最后一个元素的后面，所以插入位置最大为长度 +1。
第二步，数组是否满了，满了就无法插入新元素了，即判断数组长度是否大于空间长度，如图，共有8个空间，判断length是否大于等于8。
第三步，后移元素，给插入的元素腾出空间。
第四步，插入元素，长度 +1。

注意点：
数组下标从0计数，插入的时候要位置 -1。
L.data[i-1] = e;
当插入位置为1，赋值时是data[0]的值被改变。

平均情况下，插入一个结点要移动 n/2 个 元素。

因此时间复杂度为O(n)。

 

2.删除

 

 

bool ListDe...