顺序表的操作
前置条件
定义了一个表之后,我们就可以开始对这个表进行运算(运算无非就是增删查改)。
依然沿用这里所定义过的那个结构:
#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] |
+------+------+------+------+------+------+
这样分析之后,插入算法就很明显了:
- 现在需要在list中的第
i
个位置插入一个新的element,叫做e
。 - 判断一下i的位置是否合法( 1 <= i <= list.length + 1 ),就是比如防止明明你的表总共就只有1919这么长,却有人想在114514处插入数据这样子。如果插入的位置不合法,返回false,插入失败。以及,
- 判断 list 是不是已经满了。如果满了就 return false ,插入失败。否则,
- 将第
i
个及之后的element每一个(each)都向后移一位,给e[i]
让出空间。注意这个往后移一位是要从最后开始移,比如最后一项是a[n]
,那就要a[n] = a[n+1]
、a[n-1] = a[n]
...这样子。 - 在第
i
个位置插入e[i]
。 - 将这个list的长度+1。
- 插入成功,
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] |
+------+------+------+------+------+
根据这样子的流程,可以看出,删除的算法是
- 现在需要删除 list 中第
i
个位置的元素 - 判断这个
i
的 value 合不合法。如果不合法,删除失败。否则, - 将后面的 elements 都向前移动。
- 表长度-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 操作都要大幅度移动。
- 对存储空间要求高,会产生储存空间的“碎片”
知识共享署名-署名-非商业性使用-相同方式共享 4.0 国际许可协议