2.3 顺序表：结构与六个操作

2.3.1 结构定义

顺序存储的做法是申请一段连续的格子，把元素按逻辑顺序依次放进去。用C语言实现，连续的格子就是数组。但只有数组还不够：数组一旦定义，长度就固定了，而线性表的长度会变，还需要一个变量记录"当前实际有几个元素"。把两样东西放进一个结构体：

#define MAXSIZE 100

typedef struct {
    char data[MAXSIZE];   /* 存放元素的连续空间 */
    int  length;          /* 当前元素个数 */
} SeqList;

这样存储的线性表叫顺序表。data[0]到data[length-1]是有效元素，后面的格子空闲。以I love bananas为例，length为14，占据data[0]到data[13]：

下标	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	…
data	I	␣	l	o	v	e	␣	b	a	n	a	n	a	s		…

（␣表示空格）

元素类型直接写成char，因为本章的应用是编辑器。要存别的类型，把char换掉即可，操作的写法不变。

2.3.2 初始化、求长度、取第i个元素

为了先把注意力集中在操作本身，这一节把顺序表定义成一个全局变量L，六个操作函数直接访问它，不通过参数传递：

SeqList L;    /* 全局的顺序表 */

结构体的成员用点号访问，L.length是长度，L.data[i]是第i个格子。下面按2.2节的顺序逐个实现。

初始化

建立空表，就是把长度置为0。数组里原来有什么无所谓，length为0意味着没有任何格子是有效的。

void Init(void) {
    L.length = 0;
}

求长度

int Length(void) {
    return L.length;
}

取第i个元素

前提是0 ≤ i < length。位置合法就返回data[i]，不合法返回'\0'表示出错。

char Get(int i) {
    if (i < 0 || i >= L.length) return '\0';
    return L.data[i];
}

这是顺序表最省事的操作：不管表多长，一次下标运算就拿到了。

2.3.3 在第i个位置插入

这是顺序表上最需要仔细想的操作。回到编辑器的场景：当前一行是I love ba|nanas，光标在第9个位置，用户敲了一个x。按2.2节的约定这是Insert(L, 9, 'x')，插完应该是I love bax|nanas。

插入前：

下标	7	8	9	10	11	12	13	14
data	b	a	n	a	n	a	s

x要放进data[9]，但data[9]被n占着。为了保持"相邻格子放相邻元素"的约定，从n开始的5个元素nanas都要往后挪一格，把data[9]腾出来：

下标	7	8	9	10	11	12	13	14
data	b	a	x	n	a	n	a	s

挪动的顺序很关键。如果从前往后挪——先把data[9]的n挪到data[10]——data[10]原来的a就被覆盖丢掉了。所以必须从最后一个元素开始，倒着往后挪：先把data[13]的s挪到data[14]，再把data[12]的a挪到data[13]……最后把data[9]的n挪到data[10]。这样每次挪动的目标格子都已经是空的。

int Insert(int i, char x) {
    if (i < 0 || i > L.length) return 0;      /* 位置不合法 */
    if (L.length == MAXSIZE)   return 0;      /* 表满 */
    for (int j = L.length; j > i; j--)        /* 从后往前挪 */
        L.data[j] = L.data[j - 1];
    L.data[i] = x;
    L.length++;
    return 1;
}

返回1表示成功、0表示失败。i允许等于length，这时循环一次都不执行，x直接放到末尾，就是追加。

2.3.4 删除第i个元素

还是编辑器的场景：I love ba|nanas，用户按退格键，要删掉光标前的a，即Delete(L, 8)，结果应该是I love b|nanas。

删除前：

下标	7	8	9	10	11	12	13
data	b	a	n	a	n	a	s

data[8]的a删掉后那里空了一格，后面的nanas要往前挪一格填上：

下标	7	8	9	10	11	12	13
data	b	n	a	n	a	s

这次挪动方向和插入相反，要从前往后：先把data[9]的n挪到data[8]（直接覆盖掉要删的a），再把data[10]挪到data[9]……挪完把length减一。data[13]里还留着一个s，但它已在有效范围之外，不用管。

int Delete(int i) {
    if (i < 0 || i >= L.length) return 0;     /* 位置不合法 */
    for (int j = i; j < L.length - 1; j++)    /* 从前往后挪 */
        L.data[j] = L.data[j + 1];
    L.length--;
    return 1;
}

2.3.5 查找与验证程序

查找

从头到尾逐个比较，找到第一个等于x的就返回它的位置，走完都没有就返回−1。

int Locate(char x) {
    for (int i = 0; i < L.length; i++)
        if (L.data[i] == x) return i;
    return -1;
}

验证一下

六个操作写完，用上面的例子调用一遍，确认结果和图上一致：

int main(void) {
    Init();
    const char *s = "I love bananas";
    for (int i = 0; s[i]; i++) Insert(i, s[i]);   /* 逐个追加 */

    Insert(9, 'x');                 /* I love baxnanas */
    Delete(8);                      /* I love bxnanas  */
    printf("%d\n", Locate('x'));    /* 输出 8 */
    for (int i = 0; i < Length(); i++) putchar(Get(i));
    putchar('\n');
    return 0;
}

到这里你有了：顺序表的六个操作和一个验证程序，能在I love bananas上插入、删除、查找。 下一步：把全局变量L变成函数参数，为搭编辑器做准备。

2.3 顺序表：结构与六个操作 ​

2.3.1 结构定义 ​

2.3.2 初始化、求长度、取第i个元素 ​

2.3.3 在第i个位置插入 ​