单链表操作

 

该例程包含了单链表的声明，创建，顺序插入，反序排列，

查找节点，删除节点的功能，并在 main 函数中一一得到了验证。

/*
 * 实现链表的存储需要下列机制
 * 1、一种定义节点结构点机制，节点结构含有所有的域。
 * 2、一种在需要时创建节点的方法，可由 malloc 函数完成。
 * 3、一种删除不再需要节点的方法，可由 free 函数完成。
 *
 * 该例程包含了单链表的声明，创建，顺序插入，反序排列，查找节点，删除节点的功能，
 * 并在 main 函数中一一得到了验证。
 */

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

#define FALSE 0
#define TRUE 1
#define IS_FULL(ptr) ((!ptr))

/* Node 为类型名，NODE 为标签名 */

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

/* 创建一个单向节点 */
struct NODE *creat1()
{
    Node *first;
    first = (Node *)malloc(sizeof(Node));
    first->link = NULL;
    first->value = 5;
    return first;
}

/*
 * 总是在单链表起始端插入一个新值。
 */

int sll_insert1(Node **rootp, int new_value)
{
    Node *current, *new;
    current = *rootp;

    new = (Node *)malloc(sizeof(Node));
    if (new == NULL)
        return FALSE;

    new->link = current;
    *rootp = new;

    return TRUE;
}

/*
 * 总是在单链表末尾插入一个新值。
 */

int sll_insert4(Node **rootp, int new_value)
{
    Node *previous, *current, *new;
    previous = NULL;
    current = *rootp;

    while (current != NULL) {
        previous = current;
        current = current->link;
    }

    new = (Node *)malloc(sizeof(Node));
    if (new == NULL)
        return FALSE;

    new->link = current;
    previous->link = new;
}
/*
 * 插入到一个有序的单链表，按从小到大顺序。
 * 第一个参数是一个指向链表根指针的指针，第二个参数是需要插入的新值。
 * 起始位置、中间位置、末尾均可插入值。
 */

int sll_insert2(Node **rootp, int new_value)
{
    Node *previous, *current, *new;
    previous = NULL;
    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;
}

/*
 * 插入到一个有序的单链表。
 * 第一个参数是一个指向链表第一个节点link字段的指针，第二个参数是需要插入的新值。
 * 起始位置、中间位置、末尾均可插入值。
 * 要理解好指向当前节点的指针和指向当前节点 link 字段的指针，一个指向的是节点，另一个
 * 指向的是节点里面的值。
 */

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

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

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

/*
 * 计算一个单链表的节点数
 */

int count_node(Node *root)
{
    int count;

    for (count = 0; root != NULL; root = root->link)
        count += 1;

    return count;
}

/* 在一个无序单链表中寻找一个特定的值 */
struct NODE *find_value(Node *root, int value)
{
    while (root != NULL) {
        if (root->value == value)
            return root;

        root = root->link;
    }

    return NULL;
}

/*
 * 反序排列一个单链表的所有节点。当链表重排之后，返回一个指向新链表的头节点的指针。
 * 不使用额外的内存。
 */

struct NODE *sin_reverse(Node *current)
{
    Node *previous = NULL, *next;

    /*for (previous = NULL; current != NULL; current = next) {
        next = current->link;
        current->link = previous;
        previous = current;
    }*/

    /* 三个指针的位置为：previous,current,next */

    while (current != NULL) {
        next = current->link; //保存下一节点指针
        current->link = previous; //将节点的箭头反向
        previous = current; //一个节点的箭头反向后previous向后移动一步
        current = next;     //一个节点的箭头反向后current    向后移动一步
    }

    return previous;
}

/*
 * 从单链表中移除一个节点。
 */

int sin_remove(Node **linkp, Node *delete)
{
    register Node *current;
    current = *linkp;

    assert(delete != NULL);

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

    if (current == delete) {
        *linkp = current->link; //指向delete后面的节点
        free(current);
        return TRUE;
    }
    else    return FALSE;
}

int main()
{
    Node *root, *ptr;
    int count;

    //test the function sll_insert1
    /*root = creat1();//5
    sll_insert2(&root, 3);
    sll_insert2(&root, 4);
    printf("the sin_link contains :");
    for (ptr = root; ptr != NULL; ptr = ptr->link) {
            printf("%4d", ptr->value);
    }
    printf("\n");

    //test the function sll_insert4
    root = creat1();//5
    sll_insert2(&root, 6);
    sll_insert2(&root, 7);
    printf("the sin_link contains :");
    for (ptr = root; ptr != NULL; ptr = ptr->link) {
            printf("%4d", ptr->value);
    }
    printf("\n");

    //test the function sll_insert2
    root = creat1();//5
    sll_insert2(&root, 3);
    sll_insert2(&root, 6);
    sll_insert2(&root, 10);
    printf("the sin_link contains :");
    for (ptr = root; ptr != NULL; ptr = ptr->link) {
            printf("%4d", ptr->value);
    }
    printf("\n");*/

    //test the function sll_insert3，find_value ，count_node，sin_reverse
    root = creat1();//5
    sll_insert3(&root, 3);
    sll_insert3(&root, 6);
    sll_insert3(&root, 10);

    ptr = find_value(root, 10);
    printf("find_value=%d \n", ptr->value);

    count = count_node(root);
    printf("count_node=%d \n", count);

    ptr = sin_reverse(root);

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

    exit(0);
}