C顺序表之2

上文提到了顺序表的定义与创建

本篇主要来讲其顺序表的基本操作

1.在指定位置插入给定的元素

对于插入操作问题，我们首先要从两方面考虑：

1. 指定位置position的合法性；
2. 顺序表自身的状态;(是否还有空间供Insert)

// 在第 i 个位置前插入元素
int insertPre(List list, int i, DataType x){
    /**
    * 1. 考虑 插入位置的合法性；
    */
    if(i <0  || i > list.length -1){
        printf("插入位置i不合法!\n");
        return 0;
    }

    /**
    * 2. 考虑顺序表是否还有Space;
    */
    if(list.n == MAX_SiZE){
        printf("表已满，无法插入");
         return 0;
    }

    /**
    * 3.执行插入的元素后移逻辑，即从 位置i  到  list.length-1以
    * 此向后移动一位;
    * 需要注意的是：必须先从list.length-1开始后移，机智如你
        Think twice , and you will know why.
    */
    int j  ;
    for(j = list.length -1,j >= i; j --){
        list.elem[j+1] = list.elem[j];
    }

    /**
    * 4. 将 元素 插入 到 第  i 个位置
    */
        list.elem[i] = x;

    /**
    * 5. list 添加进去一个元素，长度自然需要 +1 
    */
        list .length  ++ ;
        return 1 ;
    }
    // 特别需要注意的是： 这里的 return  0 or 1 表示的插入操作是否完成。 在 C 语言中， 0表示 false, 非0 表示true.

我们可以发现，算法的时间主要花费在移动元素上，所以该算法的执行时间与元素的插入位置有关。我们可以计算出在平均情况下插入一个元素需要移动的元素个数。

合法的插入位置一共有list.length+1个。当在第0个位置插入元素，需要移动的元素个数为list.length个，依此类推，当在list.length-1位置插入时,需要移动0个元素。(将 list.length 记为 n)。则平均移动次数k,则有：
k = [n + (n-1)+(n-2)+... +1+0] / (n+1) = n /2.
所以：
插入一个元素，平均要移动一半的元素，当 n 比较大时，效率较低。插入操作的时间复杂度为：T(n) = O(n);

2.删除指定元素

删除第 i 个元素

int deletePos(List list, int i){
    // 1.判断删除位置的i 的合法性
    if (i < 0 || i > list.length -1){
        printf("删除位置不合法");
        return 0;
    }

    //2. 判断顺序表的状态
    if(list.length == 0){
        printf("表为空");
        return 0;
    }

   // 3. 执行删除操作的 移动元素
    int j ;
    for(j = i+1; j <  list.length; j ++){
        list.elem[j-1] = list.elem[j]; 
    }

   // 4. 删除一个元素，长度自然减1
   list.length -- ;
   
   // 5. 返回删除成功的标志
   return 1; 
}

/**
* 需要注意的是：
* 3 部分的代码，[不能写成] 如下形式：
*   int j ;
*   for(j = i ; j < list.length; j ++){
*      list[j] = list[j+1];  
*  }
*  刚开始写的时候，我就这么做了，但是想了之后就发现有问题，因为当 j = list.length -1 时，如果执行 +1 操作，则数组越界。
*/

我们一定要注意的是：
删除操作所需移动的元素位置是 从 i +1 到 list.length -1的即可。

由上可知，插入和删除的都需要移动元素,机智如你，只需灵机一动，即可明白删除操作所需要移动元素的规律。
当删除第一个元素时,需要移动 list.length -1 个元素；
当删除最后一个元素时，需要移动 0 个元素；
则在平均情况下，平均移动次数 k ，则有
k = [(n -1)+(n -2)+...+0] / n = (n-1)/2
,则删除操作所需的时间复杂度T(n) = O(n).