2.4 把L变成参数：值传递、指针与地址传递

2.4.1 为什么要改，以及一次失败的尝试

上一节的六个函数直接操作全局变量L，写起来最省事，但有三个问题。第一，它们只能操作L这一个表，第3章要同时用到好几个栈，这套函数就一个也用不上了。第二，2.2节定义的操作是Insert(L, i, x)，表是作为参数传进去的，代码理应和定义长得一样，现在的Insert(i, x)少了一个参数。第三，全局变量谁都能改，主程序完全可以绕过六个函数直接去动L.length，后面要讲的"应用层只通过操作访问数据"就没有约束力。所以要把L从全局变量改成函数的参数。

直接传结构体：一次失败的尝试

最自然的改法是给函数加一个参数，函数体里的L照旧用点号访问：

int Insert(SeqList L, 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;
}

调用方写成Insert(L, 9, 'x')。编译通过，运行也不报错，可是插入之后再看，L.length没有变，x也没有进去，表和调用前一模一样。

要弄清楚为什么，得先看看变量在内存里到底是怎么回事。

2.4.2 补充：地址与指针

如果你已经熟悉C语言的指针，可以直接跳到2.4.3。

第1章说过，内存是一排编了号的格子，编号就是地址。这不是比喻。定义一个变量：

int a = 10;
printf("%d\n", a);
printf("%llu\n", (unsigned long long)&a);

第一行打印10，是a的值；第二行打印一个很大的整数，比如140732784132684，这就是a所在格子的编号。&读作"取地址"。你运行时看到的数字会和这里不同，每次运行也可能变，这没有关系——我们关心的不是具体数值，而是"每个变量都住在一个有编号的格子里"。（%p是打印地址的标准写法，输出十六进制；这里转换成整数打印，是为了让它看起来就是一个编号。）

有了编号，就有了第二种访问变量的办法。除了用名字a，也可以先把它的地址存起来，再顺着地址去找：

int *pa = &a;
printf("%d\n", *pa);      /* 10 */
*pa = 20;
printf("%d\n", a);        /* 20 */

int *pa定义了一个存放int变量地址的变量，叫指针。*pa读作"pa指向的那个变量"，读它就是读a，改它就是改a。这就是顺着地址找到原件。

再看数组：

int b[3] = {1, 2, 3};
printf("%llu %llu %llu\n",
       (unsigned long long)&b[0],
       (unsigned long long)&b[1],
       (unsigned long long)&b[2]);

三个地址依次递增，相差正好4，因为一个int占4个字节。这是"相邻格子放相邻元素"的物理证据：数组就是一段连续的格子。既然连续，知道第一个的地址就能算出任何一个的地址：

int *pb = &b[0];
printf("%d %d %d\n", *pb, *(pb + 1), *(pb + 2));   /* 1 2 3 */

pb + 1不是把编号加1，而是往后挪一个int，也就是加4个字节，指向b[1]。顺序表的Get只要一次计算就能取到第i个元素，原因就在这里。

最后是指向结构体的指针，这正是下面要用的：

SeqList L;
SeqList *p = &L;
L.length = 5;
printf("%d %d\n", (*p).length, p->length);   /* 5 5 */

(*p).length是"p指向的结构体的length成员"。这个写法太啰嗦，C语言提供了等价的简写p->length。后面所有通过指针访问结构体成员的地方，都用箭头。

2.4.3 值传递与地址传递

原因：值传递

回到失败的Insert。在main里和Insert里各打印一次L的地址：

/* main 里 */
printf("main: %llu\n", (unsigned long long)&L);
Insert(L, 9, 'x');

/* Insert 里第一行 */
printf("Insert: %llu\n", (unsigned long long)&L);

两个数字不一样。也就是说，Insert里的L和main里的L根本不是同一个格子。调用Insert(L, 9, 'x')时，C语言把main里L的内容——整个数组加上length——完整地复制了一份，放进一个新格子，交给函数里的参数L。函数体里所有的修改，改的都是这份复制品；函数一返回，复制品就销毁了，main里的L纹丝不动。这叫值传递。

对int这样的小东西，复制一份没什么。对一个结构体，不但改不到原件，光复制这一百多个字节本身就是浪费——Length、Get这种根本不修改表的操作，每调用一次也要白白复制一遍。

改法：传地址

要在函数里改到原来那个L，就不能传它的复制品，而要告诉函数L住在哪个格子，也就是传L的地址。函数拿到地址，顺着地址去找，找到的就是原件。

参数类型改成指向SeqList的指针SeqList *L，调用时传&L。函数体里L现在是一个地址，访问成员用箭头：

int Insert(SeqList *L, 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;
}

对比一下两个版本，函数体只有两处变化：参数类型多了一个*，L.全部变成L->。调用方变成Insert(&L, 9, 'x')。再做一次刚才的打印，这回在Insert里打印的是(unsigned long long)L（L本身就是地址，不用再取），和main里&L的数字相同——找到的是原件，插入生效了。

只读的操作也一律传指针，一是避免复制整个结构体，二是六个函数写法统一。

2.4.4 六个操作的完整版本

按同样的方法改完六个函数，以下是完整版本，从现在起本章都用这一套：

#define MAXSIZE 100

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

void Init(SeqList *L) {
    L->length = 0;
}

int Length(SeqList *L) {
    return L->length;
}

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

int Insert(SeqList *L, 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;
}

int Delete(SeqList *L, 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;
}

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

全局变量SeqList L;删掉，表由使用者自己定义，比如在main里写SeqList L;，然后Init(&L)。上一节的验证程序照此改一下参数即可。