双链表操作

/*
 * 该例程实现了双链表的声明，创建，插入，删除等功能。
 */

 

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

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

struct NODE *creat_root()
{
    Node *rootp;
    rootp = (Node *)malloc(sizeof(Node));
    rootp->fwd = NULL;
    rootp->bwd = NULL;
    rootp->value = 0;

    return rootp;
}

/*
 * 把一个值插入到一个双链表中，rootp 是一个指向根节点的指针，value 是欲插入的新值。
 * 返回值：如果 value 已在链表中，返回0;内存不足，返回-1;插入成功，返回1。
 */

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

    /* this 首先指向跟节点，根节点只用两个指针字段，值字段不用 */
    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) {/* 情况1或2:不是位于链表的尾部 */
        if (this != rootp) {/* 情况1:不是位于链表的起始位置，即在第一个节点跟最后一个节点之间 */
            newnode->fwd = next;
            this->fwd = newnode;
            newnode->bwd = this;
            next->bwd = newnode;
        }
        else {/* 情况2:位于链表的起始位置，即第一个节点且后面还要节点 */
            newnode->fwd = next;
            rootp->fwd = newnode;
            newnode->bwd = NULL;
            next->bwd = newnode;
        }
    }
    else {/* 情况3或4:位于链表的尾部 */
        if (this != rootp) {/* 情况3:不是位于链表的起始位置，即最后一个节点的后面 */
            newnode->fwd = NULL;
            this->fwd = newnode;
            newnode->bwd = this;
            rootp->bwd = newnode;
        }
        else {/* 情况4:位于链表的起始位置，即是第一个节点也是最后一个节点*/
            newnode->fwd = NULL;
            rootp->fwd = newnode;
            newnode->bwd = NULL;
            rootp->bwd = newnode;
        }
    }
}

/*
 * 从双链表中移除一个节点。
 *
 * rootp :包含链表根指针的节点的指针。
 * delete:要删除的节点的指针。
 */

int dou_remove(Node *rootp, Node *delete)
{
    register Node *this;
    assert(delete != NULL);

    for (this = rootp; this != NULL; this = this->link)
        if (this == delete)
            break;

    if (this == delete) {
        // 更新 delete 节点的前面那个节点的 fwd 字段
        if (this->bwd == NULL)
            rootp->fwd = this->fwd;
        else
            this->bwd-fwd = this->fwd;

        // 更新 delete 节点的后面那个节点的 bwd 字段
        if (this->fwd == NULL)
            rootp->bwd = this->bwd;
        else
            this->fwd->bwd = this->bwd;

        free(this);
        return TRUE;
    }
    else
        return    FALSE;
}

int main()
{
    Node *rootp, *ptr;

    // test function dll_insert1
    rootp = creat_root();
    dll_insert1(rootp, 10);
    dll_insert1(rootp, 20);
    dll_insert1(rootp, 30);

    printf("the dou_link contains :");
    for (ptr = rootp->fwd; ptr != NULL ; ptr = ptr->fwd) {
            printf("%4d", ptr->value);
    }
    printf("\n");

    exit(0);
}