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)