1. 顺序表定义
把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。
2.顺序表特点
1）线性表的逻辑顺序与物理顺序一致；
2）数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。设有非空的线性
表：（ a 1 ， a 2 ，… a n ） 。
3）设线性表的每个元素需占用 1 个存储单元，以所占的第一个单元的存储地址作为数据
元素的存储位置。则线性表中第 i+1 个数据元素的存储位置 LOC(a i+1 ) 和第 i 个数据元素的
存储位置 LOC(a i ) 之间满足下列关系： LOC(ai+1 )=LOC(a i )+l
线性表的第 i 个数据元素 ai 的存储位置为：LOC(ai )=LOC(a 1 )+i*l
3.定义顺序表(c语言)
#define MAXSIZE 100
typedef struct {int data[MAXSIZE];int length;
}SqListStruct, *SqList;/*
1、空间数组是 data
2、最大长度是 MAXSIZE
3、当前元素个数是 length
*/4.顺序表操作(c语言)
4.1.顺序表创建
SqList list_create() {SqList list =(SqList)malloc(sizeof(SqListStruct));if (list == nullptr) {return nullptr;}list->length = 0;return list;
}4.2.顺序表插入
在线性表 L= (a 1 ，… a i-1 ， a i ， a i+1 ，…， a n ) 中的第 i(1 ≦ i ≦ n) 个位置上插入一个新
结点 e ，使其成为线性表： L=(a 1 ，… a i-1 ， e ， a i ， a i+1 ，…， a n )
实现步骤
(1) 将线性表 L 中的第 i 个至第 n 个结点后移一个位置。
(2) 将结点 e 插入到结点 a i-1 之后。
(3) 线性表长度加 1
在顺序表上做插入运算，平均要移动表上一半结点。当表长 n 较大时，算法效率相当低。
因此算法的平均时间复杂度为 O(n) 。
//第i个位置，插入元素e ， 注意:i >= 1
bool list_insert(SqList list, int i, int e)
{if (list == nullptr || list->length > MAXSIZE) {return false;}if (i < 1 || i > list->length + 1) {return false;}for (int k = list->length-1; k >= i-1; k--) {list->data[k + 1] = list->data[k];}list->length += 1;list->data[i - 1] = e;return true;
}4.3.顺序表按索引删除
在线性表 L=(a 1 ，… a i-1 ， a i ， a i+1 ，…， a n ) 中删除结点 a i (1 ≦ i ≦ n) ，使其成为线性
表： L= (a1 ，… a i-1 ， a i+1 ，…， a n )
实现步骤
(1) 将线性表 L 中的第 i+1 个至第 n 个结点依此向前移动一个位置。
(2) 线性表长度减 1
在顺序表上做删除运算，平均要移动表上一半结点。当表长 n 较大时，算法的效率相当低。
因此算法的平均时间复杂度为 O(n) 。
//删除第i个元素，并将被删除的元素值存入e存储单元,注意：i >= 1
bool list_delete(SqList list, int i, int* e) {if (list == nullptr || list->length == 0) {return false;}if (i < 1 || i > list->length) {return false;}if (e != nullptr) {*e = list->data[i - 1];}for (int k = i; k < list->length; k++) {list->data[k - 1] = list->data[k];}list->length -= 1;return true;
}4.4.顺序表按值删除
在线性表 L= (a 1 ， a 2 ，…， a n ) 中删除值为 x 的第一个结点。
实现步骤
（ 1 ）在线性表 L 查找值为 x 的第一个数据元素。
（ 2 ）将从找到的位置至最后一个结点依次向前移动一个位置。
（ 3 ）线性表长度减 1 。
平均时间复杂度： O(n)
//删除值为e的第一个元素
bool list_delete(SqList list, int e)
{if (list == nullptr || list->length == 0) {return false;}for (int i = 0; i < list->length; i++) {if (list->data[i] == e) {for (int k = i+1; k < list->length; k++) {list->data[k-1] = list->data[k];}list->length--;return true;}}return false;
}4.5.打印顺序表(辅助)
bool print_sqlist(SqList list) {if (list == nullptr || list->length <= 0) {return false;}printf("[");for (int i = 0; i < list->length; i++) {printf("%d", list->data[i]);printf("%s", i == list->length-1 ? "" : ",");}printf("]\n");return true;
}5.顺序表总结
1、空间连续，逻辑相邻，物理位置也相邻2、指定位置访问 O（1），随机访问3、插入和删除元素往往会移动大量元素以使元素空间连续4、扩展相对困难，因为可能不存在大区域的连续内存空间5、空间连续，随机访问，查找容易，增删难
6.附件代码
namespace NS_02_SQLIST{#define MAXSIZE 100typedef struct {int data[MAXSIZE];int length;}SqListStruct, *SqList;SqList list_create() {SqList list =(SqList)malloc(sizeof(SqListStruct));if (list == nullptr) {return nullptr;}list->length = 0;return list;}bool list_free(SqList list) {if (list == nullptr) {return false;}free(list);return true;}//第i个位置，插入元素e ， 注意:i >= 1bool list_insert(SqList list, int i, int e) {if (list == nullptr || list->length > MAXSIZE) {return false;}if (i < 1 || i > list->length + 1) {return false;}for (int k = list->length-1; k >= i-1; k--) {list->data[k + 1] = list->data[k];}list->length += 1;list->data[i - 1] = e;return true;}//删除第i个元素，并将被删除的元素值存入e存储单元,注意：i >= 1 bool list_delete(SqList list, int i, int* e) {if (list == nullptr || list->length == 0) {return false;}if (i < 1 || i > list->length) {return false;}if (e != nullptr) {*e = list->data[i - 1];}for (int k = i; k < list->length; k++) {list->data[k - 1] = list->data[k];}list->length -= 1;return true;}//删除值为e的第一个元素bool list_delete(SqList list, int e) {if (list == nullptr || list->length == 0) {return false;}for (int i = 0; i < list->length; i++) {if (list->data[i] == e) {for (int k = i+1; k < list->length; k++) {list->data[k-1] = list->data[k];}list->length--;return true;}}return false;}bool print_sqlist(SqList list) {if (list == nullptr || list->length <= 0) {return false;}printf("[");for (int i = 0; i < list->length; i++) {printf("%d", list->data[i]);printf("%s", i == list->length-1 ? "" : ",");}printf("]\n");return true;}void test1() {printf("%d\n", sizeof(SqListStruct));}void test2() {SqList list = list_create();list_insert(list, 1, 10);list_insert(list, 2, 20);list_insert(list, 3, 30);list_insert(list, 4, 40);list_insert(list, 2, 15);print_sqlist(list);list_delete(list, 1, nullptr);print_sqlist(list);list_delete(list, 4, nullptr);print_sqlist(list);list_free(list);}void test3() {SqList list = list_create();list_insert(list, 1, 10);list_insert(list, 2, 20);list_insert(list, 3, 30);list_insert(list, 4, 40);print_sqlist(list);list_delete(list, 20);print_sqlist(list);list_free(list);}void main() {test3();}
};
