数据结构 线性表的实现(2) ——基本操作

在数据结构 线性表的实现(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;
}