璺冲埌涓诲唴瀹?/a>
← 返回博客列表
C语言

从单链表尾插彻底搞懂C语言二级指针

Spider
#C语言#二级指针#单链表#数据结构

在C语言学习中，当刚学习到二级指针的时候，我们很容易可以理解它的含义，无非就是存放一级指针变量的地址，对他进行解引用可以得到一级指针，但是我们并不能想象到它的用处。

最近在学习数据结构和算法中的链表时，在写单链表的尾插函数时，我遇到了二级指针的真实应用场景，讲解如下。

问题的出现

在单链表的尾插函数中，按照正常的编程思路，要判断传进来的链表是不是空的，如果链表为空(phead == NULL)，则应该新建一个结点，然后把链表头指针指向这个新结点；如果链表不为空，则应该先寻找该链表的尾部，再把尾部的next指针指向新结点。按照这个思路，我们很容易写出如下代码：

// 在单链表末尾添加元素
void SListPushBack(SListNode *phead, SListDataType x) {
    // 初始化新节点
    SListNode *tail = CreatSListNode(x);

    // 当链表为空,phead==NULL
    if(NULL == phead){
        phead = tail;
    }
    else{
        SListNode *current = phead;
        // 找尾部
        while (current->next != NULL) {
            current = current->next;
        }
        // 添加新结点到尾部
        current->next = tail;
    }
}

这个代码乍一看没什么问题，先把新结点初始化，然后判断当前链表是否为空，为空则把头指针指向新节点，不为空则把尾部结点的next指向新节点，但是它犯了一个巨大的错误，就是形参和实参的问题。

我们先看一下当初指针是怎么被提出的。

追溯：指针的提出

记得在大多数课程中，指针的提出都来自于一个很经典的问题：用一个函数来交换两个数。新手拿到这个问题，很容易写出下面的代码：

void swap(int a, int b){
    int tmp;
    tmp = a;
    a = b;
    b = tmp;
}

但是这样就落入了形参和实参的陷阱，传进来的参数并不会参与操作，而是会在函数内部新建参数，把传过来的参数复制过去，然后进行函数内部的操作，等到函数结束，函数内部的参数被销毁，整个函数相当于啥都没做。

因此，提出了指针的概念，既然会创建一个临时变量，那我们能不能拿到原始的数据并修改它呢，指针便是这个用处，这一块便不详细讲了，想要学习指针的用处，可以查看其它博客。

最终修改后的swap函数为：

void swap(int *a, int *b){
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

这样便能达到交换两个数据的目的。

将二级指针与一级指针类比

从上面的代码可以得到一级指针的用处：当我们需要更改一个数据的时候，用指针解引用，可以找到需要修改的数据的位置，然后进行修改，再回到刚才写错的单链表尾插函数，分两部分来看，先看后半部分：

else{
        SListNode *current = phead;
        // 找尾部
        while (current->next != NULL) {
            current = current->next;
        }
        // 添加新结点到尾部
        current->next = tail;
    }

这一部分的代码其实是没有问题的，在 else 分支里，SListNode *current = phead;。虽然 current 也是形参，但它获取到了那个真实结构体的地址（phead），执行 current->next = tail; 时，修改的是内存中那个结构体实体内部的 next 成员，而不是修改 current 指针本身。所以即使 current 被销毁，内存里的结构体已经被修改成功了。但是前半部分的问题就大了：

if(NULL == phead){
        phead = tail;
    }

这里并不是修改指针指向位置的值，而是直接修改了指针，按照前面错误的swap函数的讲解，我们可以知道，函数内部的指针变量，也是一个形参，它相当于在函数内部新建了一个指针变量来存放我们传给他的指针，因此phead = tail这个改变指针的操作，只是改变的形参，传过来的指针并没有被改变！这样函数结束的时候，函数内部的变量被销毁，便什么都没有改变，和上面的swap函数犯了同样的错误。

由此，便引出了二级指针，既然我们要在函数内部改变指针的值，那对这个指针取地址，得到二级指针，我们只需要改变二级指针指向空间的值（也就是一级指针的值），不就真正改变了一级指针的值嘛，因此，正确的尾插代码如下：

// 在单链表末尾添加元素
void SListPushBack(SListNode **pphead, SListDataType x) {
    assert(pphead != NULL);
    // 初始化新节点
    SListNode *tail = CreatSListNode(x);

    // 当链表为空,*pphead==NULL
    if(NULL == *pphead){
        *pphead = tail;
    }
    else{
        SListNode *current = *pphead;
        // 找尾部
        while (current->next != NULL) {
            current = current->next;
        }
        // 添加新结点到尾部
        current->next = tail;
    }
}
← 返回博客列表