究竟用 LinkedList L 还是 LinkedList *L？

C
,

C 语言的学习总是遇到各种问题，而且很多问题几乎离不开指针这鬼玩意。在学习数据结构与算法之蜜汁 C 语言版的时候，我也是被 LinkedList 这个东西弄得心累啊！

毕竟后面发现严蔚敏版的教材的代码应该是遵循 C++ 风格（我还没学过），里面充斥着LinkedList &L这种写法。然后，每次将代码 copy 到编辑器后，一编译就泪流满面。事实上，LinkedList &L是 C++ 的一种引用语法。

其实在参数中究竟用哪一种不重要，关键是知道自己在做什么（换句话说就是为什么要用它）？

接下来有必要先说一下链表的数据结构：

1
2
3
4
5
6
typedef int ElemType;

typedef struct Node {
  ElemType data;
  struct Node *next;
} Node, *LinkedList;

如上，需要注意的地方是 LinkedList 的身份是什么。在这里，*LinkedList等同于struct Node，换句话说，LinkedList等同于struct Node *，它是一个指向结构体Node的指针！接着，我们要清楚，LinkedList *L就是指向结构体Node的指针的指针了！

  • 对于LinkedList L: L 是指向定义的 Node 结构体的指针，可以用->运算符来访问结构体成员，即L->data，而*L就是个 Node 型的结构体了，可以用点运算符访问该结构体成员，即(*L).data。

  • 对于LinkedList *L: L 是指向定义的 Node 结构体指针的指针，所以*L是指向 Node 结构体的指针，可以用->运算符来访问结构体成员，即(*L)->data，当然，**L就是 Node 型结构体了，所以可以用点运算符来访问结构体成员，即(**L).data。

在链表操作中，我们常常要用链表变量作为函数的参数。这时，用LinkedList L还是LinkedList *L就很值得考虑深究了，一个用不好，函数就会出现逻辑错误。

其准则是：如果函数会改变指针 L 的值，而你希望函数结束调用后保存 L 的值，那你就要用LinkedList *L。这样，向函数传递的就是指针的地址，结束调用后，自然就可以去改变指针的值；而如果函数只会修改指针所指向的内容，而不会更改指针的值，那么用LinkedList L就行了。

这里大家可能有点懵，我觉得关键在于理解C语言函数参数传递的原理！本质是值传递

1
2
3
4
int a = 6;
void getReturn(int a) {
  a = 10;
}

函数外部是得不到 a 变化为 10 的结果的，因为 a 在传进函数的时候被复制了一次，虽然两个 a 的内容相同，但是它们已经是两个不同的变量了！为了得到这个结果你需要使用：

1
2
3
4
5
int a = 6;
void getReturn(int *a) {
  *a = 10;
}
// getReturn(&a);

最后，结合具体实例来进一步理解下如上所有内容：

重点：当传进的变量的值被改变时需要用指针。

  1. 初始化链表 InitList

    malloc返回一个地址。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    // 想想如果用 InitList(LinkedList L) 会怎么样？
    // void InitList(LinkedList L) {
    //   L = (LinkedList) malloc(sizeof(Node));
    //   L->next = NULL;
    // }
    // L 在传进去的时候已经被复制了一遍，已不是函数外面那个指针变量。
    // 所以改变它的值不会改变外面那个指针变量的指
    // 这种情况只适用于结构体已经在外面被初始化，并且通过 InitList 改变它的值

    void InitList(LinkedList *L) {
      *L = (LinkedList) malloc(sizeof(Node));
      (*L)->next = NULL;
    }

    函数调用完毕后，L 会指向一个空的链表，即会改变指针的值，所以要用LinkedList *L。

  2. 清空链表 ClearList

    1
    2
    3
    4
    5
    6
    // 传进去的是头结点
    void ClearList(LinkedList L) {
      LinkedList p;
      while(p = L->next)
        free(p);
    }

    函数调用完后不会改变指针 L 的值，只会改变指针 L 所指向的内容（即L->next的值），所以可以用LinkedList L。

  3. 销毁链表 DestroyList

    1
    2
    3
    4
    5
    6
    7
    8
    // 头结点也需要被回收
    void DestroyList(LinkedList *L) {
      LinkedList p;
      while(p = (*L)->next)
        free(p);
      free(*L);
      *L = NULL;
    }

    释放链表 L 申请的内存，使 L 的值重新变为 NULL，所以会改变 L 的值，得用LinkedList *L。

最后，大家可能会遇到这个问题，what about Insert？这个是一个值得深思的问题呵呵！目前，我觉得在带有头结点上使用LinkedList L也是可以的。在没有头结点的时候，如果还是使用LinkedList L就可能有问题，因为我们可能会在第一个结点前插入新结点呢！所以，我也是一脸懵逼啊，可能大伙们都在遵循潜在规则吗？

潜在规则：访问用LinkedList L，修改用LinkedList *L。