数组满了怎么办
顺序表的数组大小,在编译时就定死了。定100,第101个字符插不进去;定一万,大多数时候又是浪费。用户会输入多少,事先不知道。
先看问题有多真实。把MAXSIZE改成4,重新编译编辑器1.0。敲到第4个字符,数组就满了:
text ┌───┬───┬───┬───┐
data │ c │ a │ t │ s │ length = 4
└───┴───┴───┴───┘
0 1 2 3
再敲第5个字符,Insert发现表满,返回0,屏幕上打出"插入失败"。
把MAXSIZE改回100也不能根治,敲到第101个字符时照样失败。
最直接的想法是:满了就把数组变长。但数组在内存里是一段固定的格子,比如从100号到103号。它后面的104号是谁的?可能已经被别的变量占了:
text data(4格,满了) 别的变量
┌───┬───┬───┬───┬───┬───┬───┐
… │ c │ a │ t │ s │ ? │ ? │ ? │ …
└───┴───┴───┴───┴───┴───┴───┘
100 101 102 103 104 105 106
要往104号写,就会把别人的东西覆盖掉。数组一旦定下来,两头的格子都不归它,没法就地变长。
什么是动态数组
动态数组就是:存放元素的那段连续格子,不在编译时定死,而是在程序运行时申请。装满了,就换一块更大的,把元素搬过去,再把旧的还回去。
比如4格装满了,就申请一块8格的新空间,把4个字符搬过去,然后把旧的4格还回去:
text 旧空间(还回去) 新空间(8格)
┌───┬───┬───┬───┐ ┌───┬───┬───┬───┬───┬───┬───┬───┐
│ c │ a │ t │ s │ 搬过去 ──► │ c │ a │ t │ s │ │ │ │ │
└───┴───┴───┴───┘ └───┴───┴───┴───┴───┴───┴───┴───┘
100 101 102 103 500 501 502 503 504 505 506 507
搬完之后,表的元素就从100号开始,变成了从500号开始。所以动态数组除了元素,还要记住三样东西:这段空间从哪里开始,现在实际放了几个元素,这段空间最多能放几个。
实际放了几个,就是长度。最多能放几个,叫容量。上图搬完之后,长度是4,容量是8。长度永远不会超过容量;长度等于容量时,就是满了,再插入就要先换更大的空间。
向系统申请空间
要在程序运行时申请空间,C语言在<stdlib.h>里提供了三个函数:
malloc(n):向系统申请n个字节的连续格子,返回第一个格子的地址。申请不到时,返回NULL。free(p):把以前申请的、起始地址为p的那段空间还给系统。realloc(p, m):申请一块m个字节的新空间,把p指向的旧空间里的内容复制过去,释放旧空间,返回新空间的地址。申请不到时返回NULL,这时旧空间原样保留。
程序自己定义的变量和数组,大小在编译时就定了。malloc申请来的空间,大小在运行时才决定,用完要自己free。
上一页图里"申请8格、搬过去、还回旧的4格"这三步,realloc一个函数全包了。
动态数组的定义和初始化
按动态数组的思路改顺序表。先改它的定义。
原来data是一个定长数组。现在它要记住"那段空间从哪里开始",而这段空间搬家之后起始地址会变,所以data要变成一个指针,指向运行时申请来的空间。另外新增一个capacity,记录这段空间的容量:
c/* 原来 */
typedef struct {
char data[MAXSIZE];
int length;
} SeqList;
/* 现在 */
#define INIT_CAPACITY 16
typedef struct {
char *data; /* 指向运行时申请的空间 */
int length; /* 实际放了几个 */
int capacity; /* 最多能放几个 */
} SeqList;
再改Init。原来数组是现成的,只要把长度清零。现在要先申请一块初始空间,比如16格。申请可能失败,所以Init改成返回是否成功:
c/* 原来 */
void Init(SeqList *L) {
L->length = 0;
}
/* 现在 */
int Init(SeqList *L) {
L->data = (char *)malloc(INIT_CAPACITY * sizeof(char));
if (L->data == NULL) return 0;
L->length = 0;
L->capacity = INIT_CAPACITY;
return 1;
}
动态数组的操作
插入。上一页的思路是:表满了,就先换一块更大的空间,再往里插。写成代码,Insert只改一行:
c/* 原来 */ if (L->length == MAXSIZE) return 0;
/* 现在 */ if (L->length == L->capacity && !Expand(L)) return 0;
长度等于容量,就是满了。满了先调用Expand扩容,扩容成功再往下走;扩容失败,才返回0。Length、Get、Delete一行都不用改。
扩容。Expand负责换空间:申请一块容量翻倍的新空间,把元素搬过去,旧的还回去。这三步,realloc一个函数全包了:
cint Expand(SeqList *L) {
int newCap = L->capacity * 2;
char *p = (char *)realloc(L->data, newCap * sizeof(char));
if (p == NULL) return 0;
L->data = p;
L->capacity = newCap;
return 1;
}
realloc的返回值先存进临时变量
realloc的返回值先存进p,确认不是NULL,再赋给L->data。如果直接写L->data = realloc(...),一旦申请失败返回NULL,旧空间的地址就被覆盖丢掉了,里面的元素再也找不回来。
为什么容量每次翻倍
每次翻倍,而不是每次多一格,搬家就很少发生。触发扩容的那一次插入要把整个表搬一遍,是O(n);但平均到每次插入上,仍是O(1)。这种分析方法叫平摊分析,有兴趣可以自行深入。
销毁。申请了就要还。补一个销毁操作,程序退出前调用:
cvoid Destroy(SeqList *L) {
free(L->data);
L->data = NULL;
L->length = L->capacity = 0;
}
这是动态申请空间带来的需要,2.2节的五个操作里没有它。凡是动态申请空间的实现,都得有这样一个操作。
动态数组实现编辑器
有了动态数组和它的操作,编辑器这边改动很小。Init有了返回值,main开头改成if (!Init(&L)) return 1;;循环结束后加一行Destroy(&L);。其余原样。这就是编辑器1.1。
要亲眼看见扩容,把INIT_CAPACITY改成4,再在Expand里临时加一行打印:
cprintf("[扩容] %d -> %d\n", L->capacity, newCap);
运行,输入五个以上的字符:
texti c c|
i a ca|
i t cat|
i s cats|
i _ [扩容] 4 -> 8
cats |
同样是第5个字符,1.0版插入失败,1.1版扩容后照常插入。再敲到第9个字符时,会看到[扩容] 8 -> 16。用户完全感觉不到这些,只是一直在打字。