线性表的特点概念：具有相同数据类型的n(n>0)个数据元素的有限序列,其中n为表长，当n=0时，为空表。若使用L命名线性表，其一边表示为
L = ( a 1 , a 2 , a 3 . . . a i , a i + 1 . . . a n ) L = (a_1,a_2,a_3...a_i,a_{i+1} ... a_n) L=(a1,a2,a3...ai,ai+1...an)
其中 a 1 a_1 a1为表头， a n a_n an为表尾
每个元素都有且仅有一个前驱和后继(除了表头和表尾)
ps: 区别数据元素和数据项。以链表为例，他的数据元素是节点。节点中有两个数据项。
线性表的基本操作
- 表中元素有限
- 表中元素有逻辑上的顺序性，其中元素有先后次序
- 每个数据都是数据元素，每个元素都是单个元素
- 表中元素的数据类型都相同，这意味着每个元素所占空间大小相同的存储空间
- 表中元素具有抽象性，仅讨论元素之间的相邻关系
InitList(L) 1.初始化表 Length(L) 2.求表长 LocateElement(L,b) 3.按位查找 GetElement(L,v) 4.按值查找 ListInsert(L,ind,v) 5.插入操作 ListDelete(L,ind) 6.删除操作 PrintList(L) 7.输出操作 Empty(L) 8.判空操作 Delete(L) 9.销毁操作顺序表
顺序表特点线性表的顺序存储称为顺序表，用一组地址连续的存储单元依次存储线性表中的数据元素。即顺序表的两元素不仅逻辑相邻，物理位置也相邻。逻辑顺序与物理顺序相同
顺序表可以按照数组来理解。
- 顺序表主要特点是随机访问，即通过首地址和元素序号可在时间O(1)内找到指定元素
- 顺序表的存储密度高，每个节点只存储数据元素
- 顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除需要大量元素。
我们使用C语言来实现，首先有两个准备知识，一个是结构体的使用，第二个我准备创建一个可动态分配空间的顺序表，所以我们需要使用stdlib.h头文件中的内存管理函数。
然后我们需要明确一个顺序表创建需要什么，以及有哪些操作方法。参照上面线性表的操作方式。
- 首先需要创造一个结构体作为顺序表，其中包括一维数组存放数据，还有当前表长度，以及容量上限(因为我们创建动态分配的)
- 其次我们需要有的操作有：初始化顺序表， 删除顺序表，另外对于数据有删除，和插入。以及为了我们方便检验还有一个输出。
#include#include //申请内存空间 typedef struct List{ int *data; // 数据 int len,cmp; // 当前长度, 容量 }list;
在创建结构体中可以看到，在数组定义时，我是采用了指针而非数组。如果直接定义数组，那么就直接指定了数组长度，就变成了静态分配，而且对于结构体来说也比较占用空间。定义指针之后开辟空间就只是指针大小，小了很多，也可以通过内存管理适当调整数组容量。
//初始化顺序表
list *InitList(){
list *a = (list *)malloc(sizeof(list));
a->data = (int *)malloc(sizeof(int) * 3);
a->len = 0;
a->cmp = 3;
return a;
}
初始化数组malloc()申请堆内存，可以看到data数组长度可以放3个int类型数据。同时记得初始化长度和容量的数值。
//删除顺序表
int DeleteList(list *p){
free(p->data);
free(p);
return 1;
}
有初始化就要有删除，但是要注意的是，不可以直接释放顺序表，因为在顺序表中的data数组也是申请的内存的空间，如果直接释放顺序表的结构体，那么就会找不到数组位置，但是它又是被占用的，造成内存泄漏。所以应该先释放数组，再释放顺序表。
//插入元素
int InsertData(list *p, int loc, int val){
if(loc > p->len || loc < 0){ //只允许在数据位置范围内插入
return -1;
}
if(p->len + 1 > p->cmp){ //当数据存储容量不够时进行扩容
p->cmp *= 2;
p->data = (int *)realloc(p->data, sizeof(int) * p->cmp);
printf("realloc done!n");
}
for(int t = p->len;t > loc;t--){
p->data[t] = p->data[t - 1];
}
p->data[loc] = val;
p->len++;
return 1;
}
插入元素时，我们应该考虑两种情况:
- 插入的位置是否合法，比如我们只有三个元素，就不能插入位置6
- 当达到我们的数据上限时，要进行扩容操作
插入时，若是尾部直接插如就好，但是其他位置就应该是，先把该位置到末尾的元素整体向后挪一位，之后再写入数据。一个萝卜一个坑嘛，要插入一个新萝卜就要把他的坑里原来的萝卜依次往后放。
//删除元素
int DeleteData(list *p, int loc){
if(p->len <= loc){
return -1;
}
for(int i = loc - 1; i < p->len; i++){
p->data[i] = p->data[i+1];
}
p->len--;
return 1;
}
删除元素的时候，也是同样的道理，这颗萝卜拔出来，那么他的坑就需要后面的萝卜向前补上，当然可能会对代码有疑问就是整体向前挪一位，那么最后一个数据元素不就有两个了，不需要删除吗？不需要，因为我们的顺序表大小由len体现，超过len的元素不属于我们需要的范畴。
//输出当前顺序表
void show(list *p){
for(int i = 0;i < p->len; i++){
printf("%d ",p->data[i]);
}
printf("n");
}
这个就是为了方便检验的输出函数，遍历数组输出。
int main(){
//初始化数组
list *p = InitList();
int a,b,c; //定义三个操作变量
a = 0;
while(a!=4){
printf("输入您的操作指令:");
scanf("%d %d",&a ,&b); //a是指令，b是位置
if(a == 1){ //a==1 插入操作
scanf("%d", &c);// c插入值
InsertData(p, b, c);
show(p);
}
if(a == 2){ //a == 2 删除操作
DeleteData(p, b);
//DeleteData
show(p);
}
if(a == 3){ // a==3 释放顺序表
DeleteList(p);
}
}
}
在主函数测试上述代码效果。
这里可以看到都是正常运行，也有正常的扩容操作，另外可以看到再第四次操作的时候1 4 5，结果并没有变化，就是因为当时我的输入位置是非法的。
这就是基本顺序表的内容啦!!!
复习线性表的顺序存储结构是一种随机存储结构，这是顺序表最主要的特点，可通过下标进行随机访问
另外顺序表存储密度高，他每个节点只存储数据元素
顺序表不仅仅是满足线性表的逻辑上相邻物理上也是相邻的，所以在进行删除，插入的时候需要大量移动元素
