指针的指针在单项链表中的运用

头文件:sll_node.h

#ifndef _SLL_NODE_H
#define _SLL_NODE_H

typedef struct _Node {
    struct _Node *link;
    int    value;
} Node;

#endif

实现文件:single_linked_list.c

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

#define FALSE 0
#define TRUE  1

int sll_insert(register Node **linkp, int new_value)
{
    register Node *current;
    register Node *new;

    while((current = *linkp) != NULL && current->value < new_value){
        linkp = &current->link;
    }

    new = (Node *)malloc(sizeof(Node));
    if(new == NULL){
        return FALSE;
    }
    new->value = new_value;
    new->link = current;
    // 注意这里 *linkp 有可能是修改root,也可能不是,原因是上面的linkp = &current->link
    *linkp = new;
    return TRUE;
}

void sll_free(Node **linkp)
{
    Node *next = *linkp;
    Node *current;
    while(next != NULL){
        current = next;
        // debug
        //printf("[debug] %d\n", current->value);
        next = next->link;
        free(current);
    }
}

int main(int argc, char **argv){
    int i;
    Node *rootp = NULL;
    int ints[] = {1,6,5,9,3,2,4,7,8,0};

    for(i=0; i < sizeof(ints)/sizeof(ints[0]); i++){
        sll_insert(&rootp, ints[i]);
    }

    // loop
    Node *cur = rootp;
    while(cur != NULL){
        printf("%d\n", cur->value);
        cur = cur->link;
    }
    sll_free(&rootp);
    return 0;
}

该版本的优点是,插入新节点操作,不需要声明Node *previous,也不需要做 previous == NULL 这样的判断:

//普通实现版本
int sll_insert_general(Node **rootp, int new_value)
{
    Node *current;
    Node *previous;
    Node *new;

    current = *rootp;
    previous = NULL;

    while( current != NULL && current->value < new_value){
        previous = current;
        current = current->link;
    }

    new = (Node *)malloc(sizeof(Node));
    if(new == NULL){
        return FALSE;
    }
    new->value = new_value;
    new->link = current;
    if(previous == NULL){
        *rootp = new;
    } else {
        previous->link = new;
    }
    return TRUE;
}

Leave a Comment

Your email address will not be published. Required fields are marked *

PHP 8.1.1 - 16.488 ms, 0 Q