在数据结构 线性表的实现(1) ——创建与销毁 中，简要的说明了顺序表的声明、初始化和销毁。对于我们使用者来说，顺序表中最重要的就是对于线性表的操作
add(&L,e)向顺序表L中添加数据元素e，每次都添加到顺序表的末位，如果空间不足，则对顺序表进行扩容
void add(SqList *L,ElemType e){
if(L->length>=L->list_size){
ElemType * newBase = (ElemType *) realloc(L->elem, (L->list_size+LIST_INCREMENT)*sizeof(ElemType));
if(!newBase){
exit(OVERFLOW);
}
L->elem = newBase;
L->list_size += LIST_INCREMENT;
}
* (L->elem +(L->length)) = e;
L->length++;
}
判断顺序表的空间是否足够,
L->length>=L->list_size说明当顺序表中的元素个数与顺序表的总容量相同时，就意味着空间已经满了，需要进行扩容了对已有的空间进行扩容，我们要使用
realloc函数进行扩容，第一个参数为需要被扩展的空间指针，第二个参数为扩容后的大小，如果被扩展的指针空间尾部有足够的空间，则直接进行扩容，如果其尾部的空间不足，就从新分配一块空间，然后将原来空间上的数据拷贝到新的空间中，返回新空间的首地址扩容的空间大小为当前顺序表的长度与顺序表扩容增量的和，
(L->list_size+LIST_INCREMENT)*sizeof(ElemType)表示，扩容后顺序表空间总的字节数最后将要添加的元素，放到顺序表的
L->length处，再将顺序表的长度增加1
扩容函数
在add函数中，当顺序表的容量不足时，我们需要对顺序表进行扩容，如果我们要在顺序表的指定位置插入一个元素时，遇到容量不足，也需要对顺序表进行扩容，因此，可以将上述的add函数中的拓展容量的部分提取出来,作为一个具有容量检测和拓展容量功能的函数
void ensureCapacity(SqList * L){
if(L->length >= L->list_size){
ElemType * newBase = (ElemType *) realloc(L->elem, (L->list_size+LIST_INCREMENT)*sizeof(ElemType));
if(!newBase){
exit(ERROR);
}
L->elem = newBase;
L->list_size += LIST_INCREMENT;
}
}
那么上述的add函数也可以进行修改
void add(SqList *L,ElemType e){
ensureCapacity(L);
* (L->elem +(L->length))=e;
L->length++;
}
insertSqList(SqList *L,int index,ElemType e)向顺序表L的第index个位置插入元素e
- 首先，插入的位置一定要小于顺序表中的元素个数
- 向顺序表中的某个位置插入一个元素，确定顺序表的容量是否满足，若不满足就需要扩容
- 向第
index个位置插入元素，要确定顺序表中这个位置的索引
插入元素
如图所示，顺序表L的长度为5，假如我们现在要在第3个位置插入一个元素，那么我要操作的下标索引为2,此时，我们就需要将下标为2的元素以及其后面的元素向后移动，然后将插入的元素放到这个位置
void insertSqList(SqList *L,int index,ElemType e){
//判断index是否合法
if(index < 0 || index > L->length+1){
exit(ERROR);
}
//检测顺序表的空间是否足够,空间不足时，需要扩展空间
ensureCapacity(L);
ElemType * p = L->elem + (index - 1);
ElemType * q;
for(q=L->elem+(L->length-1);q>=p;q--){
*(q+1) = *q;
}
* p = e;
L->length ++;
}
代码中，ElemType * p = L->elem + (index - 1);声明一个临时变量，将下标索引为index-1的元素的地址赋值给这个临时变量，当index为3时，这里操作的元素就是L->elem+2,如同数组中的L[2]。然后从顺序表中的最后一个元素，及下标索引为L->elem+(L->length-1)的元素开始，统统向后移动一位，最后将数据e插入到顺序表中。
EelmType delete(SqList * L,int index) 从顺序表L中移除第index个元素
- 确定index的索引位置是否合法
- 从顺序表中获取到该位置的元素数据
- 将该元素后面的数据全部向前移动一位
- 顺序表的长度减1
ElemType delete(SqList * L,int index){
if(index<=0 || index>L->length+1){
exit(ERROR);
}
ElemType elem = * (L->elem + (index-1));
ElemType * p;
for(p =L->elem + (index-1);p<=L->elem+(L->length-2);p++ ){
* p = *(p+1);
}
L->length -- ;
return elem;
}
