2.7 动态扩容：编辑器1.1

2.7.1 问题与思路

把MAXSIZE临时改成4，重新编译编辑器1.0，输入第5个字符时屏幕上打出"插入失败"。改回100也一样，只是要多敲96个字符。定成10000呢？大多数时候又浪费。用户会输入多长，我们事先不知道，一个编译时定死的上限总是不对的。

思路是：不在编译时定死数组大小，而是运行时先申请一块不大的空间，满了再申请一块更大的，把已有元素搬过去。要做到这一点，需要改三处：结构体、Init，以及一个新的扩容函数。

2.7.2 结构体和Init的变化

结构体的变化

原来：

typedef struct {
    char data[MAXSIZE];
    int  length;
} SeqList;

现在：

#define INIT_CAPACITY 16

typedef struct {
    char *data;       /* 指向运行时申请的空间 */
    int   length;     /* 实际放了几个 */
    int   capacity;   /* 最多能放几个 */
} SeqList;

两处变化。data从定长数组变成指针，它不再自带空间，而是指向运行时申请来的一段格子；新增capacity记录这段格子有多少个。length是"实际放了几个"，capacity是"最多能放几个"，始终有length ≤ capacity。

Init的变化

原来：

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;
}

原来数组是现成的，Init只需把长度清零；现在要向系统申请空间。malloc(n)申请n个字节的连续格子，返回第一个格子的地址，我们把它存进data。INIT_CAPACITY定为16，先申请16个格子。申请可能失败（返回NULL），所以Init改为返回是否成功。需要#include <stdlib.h>。

2.7.3 扩容函数与接入Insert

static int 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(旧地址, 新大小)做三件事：申请一块新大小的空间，把旧空间的内容复制过去，释放旧空间，返回新空间的地址。注意返回值先存进临时变量p，确认不是NULL再赋给L->data——如果直接写L->data = realloc(...)，一旦申请失败返回NULL，旧空间的地址就被覆盖丢掉了，里面的元素再也找不回来。

Expand由Insert在表满时调用，Insert只改一行。

原来：

    if (L->length == MAXSIZE)   return 0;

现在：

    if (L->length == L->capacity && !Expand(L)) return 0;

满了先扩容，扩容成功再往下走，失败才返回0。其余五个操作一行不改。

2.7.4 走一遍：看见扩容发生

用户从空行开始打字。Init申请了16个格子，capacity=16。前16个字符依次填入，length从0到16。第17个字符到来，Insert发现length等于capacity，调用Expand：申请32个格子，把16个字符复制过去，释放旧的16个，capacity变成32。第17个字符放进去，length=17。此后到第33个字符时再扩到64，以此类推。用户完全感觉不到这些，只是一直在打字。

想亲眼看见，可以在Expand里临时加一行：

printf("[扩容] %d -> %d\n", L->capacity, newCap);

再把INIT_CAPACITY改成4，运行编辑器：第5个字符时出现[扩容] 4 -> 8，第9个字符时出现[扩容] 8 -> 16。同样是第5个字符，1.0版失败，现在自动扩容。看完把打印删掉。

2.7.5 释放、为什么翻倍、编辑器1.1

补充：释放空间

申请了就要释放，否则程序退出前这块空间一直占着。补一个销毁操作：

void Destroy(SeqList *L) {
    free(L->data);
    L->data = NULL;
    L->length = L->capacity = 0;
}

这是实现层面带来的需要，2.2节的ADT定义里没有它，但凡是动态申请空间的实现都得有。

为什么翻倍

Expand每次把容量扩大一倍，而不是每次多申请一格。如果每次只多一格，那么每插入一个元素都要复制整个表，追加n个元素总共要复制大约n²/2次，把O(1)的追加变成了O(n)。翻倍的话，容量从16到32到64……复制只在这些时刻发生，追加n个元素总共复制不超过2n次，平摊到每次追加上仍然是O(1)。代价是最多有一半空间暂时空着——用空间换时间，这类取舍后面还会反复遇到。

编辑器1.1

编辑器这边的改动很小：Init现在有返回值，main开头改成if (!Init(&text)) return 1;，循环结束后加一行Destroy(&text);，其余原样。这就是编辑器1.1——存储实现换了一种，应用层只动了两行。

到这里你有了：不会满的编辑器1.1，应用层只改了两行。 还没解决的：在行首打字是O(n)，根源在顺序存储的约定本身。 下一步：换一种存储方式。

2.7 动态扩容：编辑器1.1 ​

2.7.1 问题与思路 ​

2.7.2 结构体和Init的变化 ​

2.7.3 扩容函数与接入Insert ​