由链表初始化看C语言的二级指针

先来看C语言创建链表、插入节点和遍历链表的一段代码：

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

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

//void init_linkedlist(LinkedList *list) {
void init_linkedlist(LinkedList *list) {
    *list = (LinkedList)malloc(sizeof(Node));
    (*list)->next = NULL;
}

void insert(LinkedList list, ElemType elem) {
    Node *p, *q;
    q = list;
    p = (Node *)malloc(sizeof(Node));
    p->elem = elem;
    p->next = NULL;
    while(q->next != NULL) q = q->next;
    q->next = p;
}

void main() {
    LinkedList list, p;
    init_linkedlist(&list);
    insert(list, 3);
    insert(list, 4);
    insert(list, 5);
    p = list->next;
    while(p != NULL) {
        printf("%4d", p->elem);
        p = p->next;
    }
    printf("\n");
}

 这个小程序完成的功能很简单，创建一个链表，然后插入3,4,5这三个整数，最后遍历链表输出每个节点中的整数。但是大家注意到没有，在main函数中，初始化链表的函数参数的是一个二级指针，为什么要使用一个二级指针作为参数呢？在任何一本C语言的教材上，都会写C语言的函数参数传递是值传递方式，所有的参数都是通过值传递的，使用指针作为参数可以在函数中改变参数的值(此处感觉表达有误，但是想不到更好的表达方式)。可能有人会有疑问了，在上面代码的main函数中初始化链表的调用函数代码

init_linkedlist(&list);

 list已经是一个指针了，为什么要传递一个指针的地址，直接使用指针不行吗？确实不行。

为什么？那么我们来看看不使用二级指针会发生什么情况，先来看看不使用二级指针的代码：

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

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


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

void insert(LinkedList list, ElemType elem) {
    Node *p, *q;
    q = list;
    p = (Node *)malloc(sizeof(Node));
    p->elem = elem;
    p->next = NULL;
    while(q->next != NULL) q = q->next;
    q->next = p;
}

void main() {
    LinkedList list, p;
    printf("%d\n", list);
    init_linkedlist(list);
    printf("%d\n", list);
}

 这段代码的main函数中有两处输出，分别是在初始化链表函数之前和之后，如果运行这段代码，会发现两处输出都是一样的值：

 

 但是如果在使用二级指针的代码(本文的第一段代码)中插入相同的两处输出代码，会发现输出的两个值是不同的：

 为什么会这样，原因就在于本文的第一段代码使用的是二级指针作为参数传递，而第二段代码使用的是一级指针作为参数传递。这个问题最终还是回归到了C语言参数传递是值传递了。

如果是使用一级参数传递，首先是main函数中定义一个Node类型的指针，这个指针用list表示，C语言在定义指针的时候也会分配一块内存，一般会占用2个字节或4个字节，现在在大部分的编译器中占用4个字节，这里用4个字节算。在这4个字节的内存中，没有任何值，所以这个指针不指向任何值。然后传递到函数init_linkedlist中，在init_linkedlist函数中，编译器首先为形参list分配一个临时指针内存块，而语句

 

list = (LinkedList)malloc(sizeof(Node));

 中函数malloc分配一块内存，并向该程序返回一个指向这块内存的指针，这样形参list就有值了，在list所表示的临时内存区域中填入刚刚分配的内存的这块内存的地址，假设为0x10086，这样使用(*list)就可以访问这块内存（0x10086）中的内容了。此时在函数init_linkedlist中list所代表的这块内存中的内容是有值的，为0x10086，用图可表示为：

 

但是现在的list只是占据了一个零时的内存空间，这种改变并不能反映到main函数中，init_linkedlist函数执行完了，临时的list内存块就被回收了，这样刚刚分配的内存块的地址0x10086没有被记录下来。而我们如果要初始化main函数中的链表list的话，就必须记录记录下这块内存空间(0x10086)。

     下面我们来考虑使用二级指针的代码，在使用二级指针的代码(本文第一段代码)中，首先定义了一个指针

 

LinkedList list

 然后调用init_linkedlist，调用代码是

 

init_linkedlist(&list);

 这样传递的参数就是一个指针的地址，在函数的参数列表中就表现为指针的指针，函数的定义为

 

void init_linkedlist(LinkedList *L)

 函数的参数是一个二级指针，同样，在执行调用这个函数的时候，临时分配一个指针，这个指针占据一个占用4个字节的内存块（函数执行完要回收的），同时这个临时指针L指向主函数main中定义的list指针，这里假设主函数main中的list指针在内存中的地址为0x12306，用图表示为

 

 其中L是一块临时内存，list是主函数main的中定义的一个指针，此时list代表的内存块中还没有内容（貌似这样说法有误，或者说这块内存还没有初始化）。下面执行内存分配的代码

 

*L = (LinkedList)malloc(sizeof(Node));

 malloc函数分配了一块内存空间，假设地址为0x10010，由于L指向list所代表的内存块，所以*L等价于list，这样将malloc函数分配的内存块赋值给*L就相当于执行语句

 

list = 0x10010

 那么在list代表的内存块中所存储的值就为0x10010，用图表示为

 

 

 这样在函数init_linkedlist中分配的一段内存也就能在main函数中反映出来了，main函数中list代表的内存块的就指向了新分配的内存，链表初始化完成。

 

评论

3 楼 一袋大米 2014-07-08  

感谢！这是我看了几个回答里最清楚的一个！

2 楼 andy0566 2013-11-20  

看错了，请楼主删回帖

1 楼 andy0566 2013-11-20  

非常不错，不过函数init_linkedlist中的二级指针参数漏了一个*吧

void init_linkedlist(LinkedList [color=red]*[/color]*list) {  
    *list = (LinkedList)malloc(sizeof(Node));  
    (*list)->next = NULL;  
}