• 时间:
  • 分类:

前置条件

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

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

#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