后向动态链表增删查改

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

typedef uint32_t ElemTyp;

typedef struct st_single_chain_list {
    ElemTyp dat;
    struct st_single_chain_list *next;
} tagLink_t;

ElemTyp total;

tagLink_t *init_single_chain_list(ElemTyp value)
{
    tagLink_t *tmp = (tagLink_t *)malloc(sizeof(tagLink_t));
    if (tmp == NULL) {
        printf("original node create fail!\n");
        return NULL;
    }
    tmp->dat = value;
    tmp->next = NULL;
    total = 1;     // 头节点
    return tmp;
}

void insert_an_element(tagLink_t *p, ElemTyp value, ElemTyp posi)
{
    tagLink_t *head = NULL;
    tagLink_t *tmp = NULL;
    tagLink_t *q = p;
    tagLink_t *prev = NULL;
    ElemTyp append_flag = 0;
    ElemTyp i = 0;
    if (posi == 0) {
        printf("insert %d before head node!\n", value);
        return;
    }
    if (posi > total) {
        printf("insert position: %d invalid! total :%d\n", posi, total);
        return;
    } else if (posi == total) {
        append_flag = 1;
    } else {
        append_flag = 2;
    }
    tmp = (tagLink_t *)malloc(sizeof(tagLink_t));
    if (tmp == NULL) {
        printf("%d node create fail!\n", posi);
        return;
    }
    q = p;
    if (append_flag == 1) {
        while (q != NULL) {
            prev = q;
            q = q->next;
        }
        q = prev;
        tmp->dat = value;
        tmp->next = NULL;
        q->next = tmp;
        total++;
    } else {
        for (i = 0; i < posi - 1; i++) {
            q = q->next;
        }
        tmp->dat = value;
        tmp->next = q->next;
        q->next = tmp;
        total++;
    }
}

void delete_an_element_by_position(tagLink_t *p, ElemTyp posi)
{
    ElemTyp i = 0;
    tagLink_t *q = p;
    tagLink_t *tmp = p;

    if ( (posi >= total) || (posi == 0) ) {
        printf("delete position improper!\n");
        return;
    }

    if (posi < total - 1) {
        for (; i < posi; i++) {
            tmp = q;
            q = q->next;
        }
        tmp->next = q->next;
        total--;
    } else {
        for (; q->next != NULL; q = q->next) {
            tmp = q;
        }
        tmp->next = NULL;
        total--;
    }
}

void delete_an_element_by_value(tagLink_t *p, ElemTyp value)
{
    ElemTyp i = 0;
    tagLink_t *q = p;
    tagLink_t *tmp = p;
    ElemTyp value_found = 0;
    ElemTyp index = 0;

    for (q = p; q != NULL; q = q->next) {
        if (value != q->dat) {
            index++;
            continue;
        }
        value_found = 1;
        break;
    }

    if (value_found == 0) {
        printf("value not found!\n");
        return;
    }

    if (index == 0) {
        printf("prohibit to delete head node!\n");
        return;
    }

    if (index == total) {
        for (q = p; q->next != NULL; q = q->next) {
            tmp = q;
        }
        tmp->next = NULL;
        total--;
    } else {
        for (i = 0, q = p; i < index; i++) {
            tmp = q;
            q = q->next;
        }
        tmp->next = q->next;
        total--;
    }
}

ElemTyp search_an_element(tagLink_t *p, ElemTyp value)
{
    tagLink_t *q = p;
    ElemTyp value_found = 0;
    ElemTyp index = 0;

    for (q = p; q != NULL; q = q->next) {
        if (value != q->dat) {
            index++;
            continue;
        }
        value_found = 1;
        break;
    }

    if (value_found == 0) {
        return 0xFF;
    }
    return index;
}

void modify_an_elment(tagLink_t *p, ElemTyp posi, ElemTyp value)
{
    tagLink_t *q = p;
    ElemTyp value_found = 0;
    ElemTyp i = 0;

    if (posi >= total) {
        printf("modify position improper!\n");
    }

    if (posi == 0) {
        q->dat = value;
    } else {
        for (i = 0; i < posi; i++) {
            q = q->next;
        }
        q->dat = value;
    }
}

int main()
{
    tagLink_t *Link = NULL;
    tagLink_t *p = NULL;
    ElemTyp index = 0;
    ElemTyp value_id = 0xFF;
    ElemTyp seek_value = 0;

    Link = init_single_chain_list(36);
    insert_an_element(Link, 3, 0);
    insert_an_element(Link, 4, 1);
    insert_an_element(Link, 37, 2);
    insert_an_element(Link, 6, 3);
    insert_an_element(Link, 29, 4);
    insert_an_element(Link, 8, 5);
    insert_an_element(Link, 75, 6);
    insert_an_element(Link, 10, 7);
    insert_an_element(Link, 11, 8);
    insert_an_element(Link, 12, 9);
    insert_an_element(Link, 100, 6);
    insert_an_element(Link, 55, 5);

    printf("search process:\n");
    seek_value = 10;
    value_id = search_an_element(Link, seek_value);
    if (value_id != 0xFF) {
        printf("%d found, index: %d\n", seek_value, value_id);
    }
    for (p = Link; p != NULL; p = p->next) {
        printf("%d----%d\n", index++, p->dat);
    }

    printf("modify process:\n");
    modify_an_elment(Link, 5, 152);
    index = 0;
    for (p = Link; p != NULL; p = p->next) {
        printf("%d----%d\n", index++, p->dat);
    }

    printf("delete process by position:\n");
    delete_an_element_by_position(Link, 4);
    index = 0;
    for (p = Link; p != NULL; p = p->next) {
        printf("%d----%d\n", index++, p->dat);
    }

    printf("delete process by position:\n");
    delete_an_element_by_position(Link, 10);
    index = 0;
    for (p = Link; p != NULL; p = p->next) {
        printf("%d----%d\n", index++, p->dat);
    }

    printf("delete process by value:\n");
    delete_an_element_by_value(Link, 100);
    index = 0;
    for (p = Link; p != NULL; p = p->next) {
        printf("%d----%d\n", index++, p->dat);
    }

    printf("delete process by value:\n");
    delete_an_element_by_value(Link, 11);
    index = 0;
    for (p = Link; p != NULL; p = p->next) {
        printf("%d----%d\n", index++, p->dat);
    }

    free(Link);

    return 0;
}