链表

链表(linked list)就是一些包含数据的独立的数据结构(节点)的集合. 每个节点通过链或指针连结在一起. 程序通过指针访问链表中的节点.

单链表

在单链表中, 每个节点包含一个指向链表下一结点的指针. 链表最后一个节点的指针字段值为 NULL.

需要使用一个根指针 (root pointer) 记住链表的起始位置.

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

在单链表中插入

为了返回到上一个节点, 需要 始终保存一个指向链表当前节点之前的那个节点的指针.

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

#define FALSE 0
#define TRUE 1

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

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

    while (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;
    previous->link = new;
    return TRUE;
}

这个插入函数是不正确的. while 循环会越过链表尾部, 并对一个 NULL 指针进行间接访问操作. 改变 while 循环解决这个问题

while (current != NULL && current->value < value){

为了在链表插起始位置插入一个节点, 函数必须修改根指针. 但是函数不能访问变量 root. 我们需要就爱那个指向 root 的指针作为参数传递给函数.

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

#define FALSE 0
#define TRUE 1

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

int sll_insert(Node **rootp, int new_value)
{
    Node *current;
    Node *previous;
    Node *new;

    current = *rootp;

    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;
}

优化插入函数

/*
 * 插入到一个有序单链表. 函数的参数是一个指向链表第一个节点的指针,
 * 以及一个需要插入的新值
 */
#include <stdlib.h>
#include <stdio.h>

#define FALSE 0
#define TRUE  1

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

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 = new;
    return TRUE;
}

双链表

双链表每个节点都包含两个指针----指向前一个节点的指针和指向后一个节点的指针. 这可以使我们以任何方向遍历双链表.

typedef struct NODE{
    struct NODE *fwd;
    struct NODE *bwd;
    int value;
} Node;

在双链表中插入

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

typedef struct NODE{
    struct NODE *fwd;
    struct NODE *bwd;
    int value;
} Node;


int dll_insert(Node *rootp, int value)
{
    Node *this;
    Node *next;
    Node *newnode;
    
    for (this = rootp; (next = this->fwd) != NULL; this = next){
        if (next->value == value)
            return 0;
        if (next->value > value)
            break;
    }
    newnode = (Node *) malloc (sizeof(Node));
    if (newnode == NULL)
        return -1;
    newnode->value = value;
    
    if (next != NULL){
        newnode->fwd = next;
        if (this != rootp){
            this->fwd = newnode;
            newnode->bwd = this;
        } else {
            rootp->fwd = newnode;
            newnode->bwd = NULL;
        }
        next->bwd = newnode;
    }else{
        newnode->fwd = NULL;
        if (this != rootp){
            this->fwd = newnode;
            newnode->bwd = this;
        }else{
            rootp->fwd = newnode;
            newnode->bwd = NULL;
        }
        rootp->bwd = newnode;
    }
    return 1;
}

双链表最简版

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

typedef struct NODE{
    struct NODE *fwd;
    struct NODE *bwd;
    int value;
} Node;

int
dll_insert(register Node *rootp, int value)
{
    register Node *this;
    register Node *next;
    register Node *newnode;

    for (this = rootp; (next=this->fwd) != NULL; this=next){
        if (next->value == value)
            return 0;
        if (next->value > value)
            break;
    }
    newnode = (Node *) malloc(sizeof(Node));
    if (newnode == NULL)
        return -1;
    newnode->value = value;
    newnode->fwd = next;
    this->fwd = newnode;
    if (this != rootp)
        newnode->bwd = this;
    else
        newnode->bwd = NULL;
    if (next != NULL)
        next->bwd = newnode;
    else
        rootp->bwd = newnode;
    return 1;
}