前置条件

定义了一个表之后,我们就可以开始对这个表进行运算(运算无非就是增删查改)。

依然沿用这里所定义过的那个结构:

#define maximumLength 114514;
typedef int elemType;
typoedef struct {
  elemType *data;
  int size;
  int length;
}sequenceList;

调用:

sequenceList list;
list.data = (elemType*) malloc( sizeof(elemType) * maximumLength);

Insert

举个例子:
顺序表就像排队,就像在饭堂里边排队打饭一样,本来有一个好好队,突然来了一个插队的人插了在你前面,那它后面的人都要先后退一位给他腾出位置,他才能插的进去。

根据同样的思想,假设我现在有一个队列

+------+------+------+------+------+
| a[1] | a[2] | a[3] | a[4] | a[5] |
+------+------+------+------+------+

那现在突然来了个a[6],要插在a[2]a[3]之间,那么,a[3]后面的人就必须要给后退移动一位,让出位置,才能让a[6]插进去。

                     =>     =>     =>
+------+------+------+------+------+------+
| a[1] | a[2] |      | a[3] | a[4] | a[5] |
+------+------+------+------+------+------+
                ↓↓↓↓↓
+------+------+------+------+------+------+
| a[1] | a[2] | a[6] | a[3] | a[4] | a[5] |
+------+------+------+------+------+------+     

这样分析之后,插入算法就很明显了:

  1. 现在需要在list中的第 i 个位置插入一个新的element,叫做 e
  2. 判断一下i的位置是否合法( 1 <= i <= list.length + 1 ),就是比如防止明明你的表总共就只有1919这么长,却有人想在114514处插入数据这样子。如果插入的位置不合法,返回false,插入失败。以及,
  3. 判断 list 是不是已经满了。如果满了就 return false ,插入失败。否则,
  4. 将第 i 个及之后的element每一个(each)都向后移一位,给 e[i] 让出空间。注意这个往后移一位是要从最后开始移,比如最后一项是 a[n] ,那就要 a[n] = a[n+1]a[n-1] = a[n]...这样子。
  5. 在第 i 个位置插入 e[i]
  6. 将这个list的长度+1。
  7. 插入成功,return true

弄明白这个流程之后,就可以将上面的一坨东西翻译成谭语言叻,,,

// Process 1:
// &list   => 因为要修改这个list,所以应该把地址传进去
// i       => 表示在第 i 位插入这个 element
// element => 表示将要被插入的元素
bool insertElement(sequenceList &list, int i, elemType element) {
    // Process 2:
    if( i < 1 OR i > list.length+1 ) {
        return false;
    }
    // Process 3:
    if( list.length >= maximumLength) {
        return false;
    }
    // Process 4:
    for( int n = list.length; n >= i; n-- ) {
        list.data[n] = list.data[n-1];
    }
    // Process 5:
    list.data[i-1] = element;
    // Process 6:
    list.length = list.length + 1;
    // Process 7:
    return true;
}

这个算法的性能:
这种算法的时间复杂度要分三种情况讨论,分别是最好、最差和平均。
最好情况:直接就在表尾插入,循环直接不要,这时候时间复杂度是O(1)
最差情况:在表头哈如,循环被执行n次,这时候时间复杂度是O(n)
平均情况:$\frac{n}{2}$ ,不要问是怎么算的,我不会 :-P
反正这个算法的平均时间复杂度(不是平均情况,别搞反了)是O(n)就对了。

Delete

举个例子:
正在排队打饭的人发现有人插队了,于是把这个插队的人批判了一番,还要把他提出这个排队的队列中。

1:
                        a[3]: 插队guna
+------+------+------+------+------+------+
| a[1] | a[2] | a[6] | a[3] | a[4] | a[5] |
+------+------+------+------+------+------+ 

2:
                  a[6]: 妈的溜了
+------+------+------+------+------+------+
| a[1] | a[2] |      | a[3] | a[4] | a[5] |
+------+------+------+------+------+------+ 

3:
                    <=      <=      <=
+------+------+------+------+------+------+
| a[1] | a[2] |      | a[3] | a[4] | a[5] |
+------+------+------+------+------+------+ 

4:
+------+------+------+------+------+
| a[1] | a[2] | a[3] | a[4] | a[5] |
+------+------+------+------+------+

根据这样子的流程,可以看出,删除的算法是

  1. 现在需要删除 list 中第 i 个位置的元素
  2. 判断这个 i 的 value 合不合法。如果不合法,删除失败。否则,
  3. 将后面的 elements 都向前移动。
  4. 表长度-1.
// Process 1:
// &list    => 因为要修改这个list,所以应该把addr传进去
// i        => 指示要被删除的位置
// &element => 因为要修改这个element,所以应该把它的addr传进去
bool deleteElement(sequenceList &list, int i, elemType &element) {
    // Process 2:
    if ( i< 1 OR i > list.length ) {
        return false;
    }
    element = list.data[i-1];
    // Process 3:
    for ( int n = i; n < list.length; n++ ) {
        // 插入是从后向前移动;        ~~~
        // 删除是从前向后移动;        ^ 所以这里应该是n++
        // 这点一定要多加注意。
        list.data[n-1] = list.data[n];
    }
    list.length = list.length-1;
    return true;
}

这个算法的性能:
和楼上一样,这个也要分最好、最差和平均来讨论。
最好情况:删除表尾,O(1)
最差情况:删除表头,O(n)
平均情况:$\frac{n-1}{2}$ 不要问是怎么算的,我还是不会 :-P
∴这个算法的平均时间复杂度是O(n).

顺序存储结构的优缺点

优点:

  • 储存密度大,和 linked list 不一样,sequence list 不用储存下一个 element 的指针。
  • Random access, 依照公式就可以算出元素的 addr,可以直接快速地 access 这个 list 里边随便一个元素.

缺点:

  • Insert 和 Delete 操作都要大幅度移动。
  • 对存储空间要求高,会产生储存空间的“碎片”

标签: none