究竟用 LinkedList L 还是 LinkedList *L?

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

0%