共计 2574 个字符，预计需要花费 7 分钟才能阅读完成。
1、程序表的定义
程序表是用一组地址间断的存储单元顺次存储线性表中的数据元素。把逻辑上相邻的元素存储在物理地位上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。顺序存储构造如下图所示：
留神：线性表中的位序是从 1 开始的，而数组元素的下标是从 0 开始的。
2、程序表的实现
2.1 动态调配
#define MaxSize 10 // 定义最大长度
typedef int ElemType;
typedef struct {ElemType data[MaxSize]; // 用动态数组存放数据元素
int length; // 程序表的以后长度
} SqList; // 程序表的类型定义
/**
* 基本操作 - 初始化一个程序表
* @param L
*/
void InitList(SqList &L) {for (int i = 0; i < MaxSize; ++i) {L.data[i] = 0; // 将所有数据设为默认初始值, 否则会有脏数据
}
L.length = 0; // 程序表初始长度为 0
} 在动态调配时，数组的大小和空间是固定的，无奈更改，一旦空间占满，再退出新的数据就会产生溢出，进而导致程序解体。
思考：如果一开始就申请很大的内存空间呢？？？会存在什么问题？？？ 节约！!
2.2 动态分配
#define InitSize 10 // 默认的最大长度
typedef int ElemType;
typedef struct {
ElemType *data; // 批示动态分配数组的指针
int MaxSize; // 程序表的最大容量
int length; // 程序表的以后长度
} SeqList;
void InitList(SeqList &L) {
// 用 malloc 函数申请一片间断的内存空间
L.data = (int *) malloc(InitSize * sizeof(int));
L.length = 0;
L.MaxSize = InitSize;
}用 malloc 函数申请一片间断的存储空间。malloc 函数返回一个指针，须要强制转型为你定义的数据元素类型指针。
减少数组空间的办法：
/**
* 扩容
* @param L
* @param len
*/
void IncreaseSize(SeqList &L, int len) {
int *p = L.data;
L.data = (int *) malloc((L.MaxSize + len) * sizeof(int));
for (int i = 0; i < L.length; i++) {L.data[i] = p[i]; // 将数据复制到新区域
}
L.MaxSize = L.MaxSize + len; // 程序表最大长度减少 len, 事件开销大
free(p); // 开释原来的内存空间
}留神：动态分配并不是链式存储，它同样属于顺序存储构造，物理构造没有变动，仍然是随机存取形式，只是调配的空间大小能够在运行时动静决定。
3、程序表的特点
① 随机拜访 ，即能够通过首地址和元素序号在 O(1) 工夫内找到第 i 个元素；
②存储密度高，每个节点只存储数据元素；
③逻辑上相邻的元素物理上也相邻，扩容、插入、删除操作不不便。
4、程序表上基本操作的实现 (以动态调配的程序表为例)
4.1 插入操作
在程序表的第 i 个地位插入新元素，要将第 i 个及其后的所有元素往后挪动一个地位，腾出一个空位插入新的元素
逻辑构造：
代码实现：
/**
* 插入的代码，能解决异常情况
* @param L
* @param i
* @param e
* @return
*/
bool ListInsert(SeqList &L, int i, int e) {if (i < 1) { // 判断 i 的范畴是否无效
return false;
}
if (L.length >= L.MaxSize) { // 以后存储空间已满，要扩容
IncreaseSize(L, 1);
}
for (int j = L.length; j >= i; j--) { // 将第 i 个元素及之后的元素后移
L.data[j] = L.data[j - 1];
}
L.data[i - 1] = e; // 在 i 处放 e
L.length++; // 长度加 1
return true;
}工夫复杂度：
最好状况：新元素插入到表尾，不须要挪动元素，i = n + 1，循环 0 次，O(1)
最坏状况：新元素插入到表头，须要挪动全副元素，i = 1，循环 n 次，O(n)
均匀状况：假如新元素插入到任何一个地位的概率雷同，即 i = 1,2,3,4……length+ 1 的概率都是 1/(n+1)，均匀工夫 复杂度 O(n)
4.2 删除操作
删除第 i 个元素，须要将第 i + 1 个元素及其前面的所有元素往前挪动一个地位
逻辑构造：
代码实现：
/**
* 删除数据
* @param L 要操作的列表
* @param i 删除第 i 个元素，从 1 开始计数
* @param e 保留删除的元素
* @return
*/
bool ListDelete(SeqList &L, int i, int &e) {if (i < 1 || i > L.length) { // 判断 i 的范畴是否无效
return false;
}
e = L.data[i - 1]; // 将被删除的元素赋值给 e
for (int j = i; j < L.length; j++) { // 将第 i 个地位后的元素前移
L.data[j - 1] = L.data[j];
}
L.length--; // 线性表长度减 1
return true;
}工夫复杂度：
最好状况：删除表尾元素，不须要挪动其余元素，i = n，循环 0 次，O(1)
最坏状况：删除表头元素，须要将后续的 n + 1 个元素全副向前挪动，i = 1，循环 n – 1 次，O(n)
均匀状况：假如删除任何一个元素的概率雷同，即 i = 1,2,3,4……length+ 1 的概率都是 1/n，均匀工夫复杂度 O(n)
4.3 按位查找
获取表中第 i 个地位的元素值
ElemType GetElem(SqList L, int i) {return L.data[i - 1];
}工夫复杂度 O(1)
4.4 按值查找
在表中查找元素值等于指定值的元素，并返回其位序
/**
* 按值查找
* @param L
* @param e
* @return
*/
int LocateElem(SqList L, int e) {for (int i = 0; i < L.length; ++i) {if (L.data[i] == e) {return i + 1;}
}
return 0;
}工夫复杂度：
最好状况：指标元素在表头，循环 1 次，O(1)
最坏状况：指标元素在表尾，循环 n 次，O(n)
均匀状况：假如指标元素呈现在任何一个地位的概率雷同，都是 1/n，均匀工夫复杂度 O(n)
