链表基本操作（增、删、改、查、排序、头\尾插法）

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

#define SWAP(datatype, x, y) {datatype t = x; x = y; y = t;}
typedef char datatype;

struct List
{
    datatype data;
    struct List *next;
};

struct List *init_list(struct List *list)
{
    list = (struct List *)malloc(sizeof(struct List));
    return list;
}

void head_insert_node(struct List *prev, struct List *node)
{
    node->next = prev->next;
    prev->next = node;
}

struct List * tail_add_list(struct List *tail, datatype value)
{
    struct List *node = (struct List *)malloc(sizeof(struct List));
    node->data = value;
    node->next = NULL;

    tail->next = node;
    tail = tail->next;

    return tail;
}

void tail_add_node(struct List *head, datatype value)
{
    struct List *p = head;
    struct List *node = (struct List *)malloc(sizeof(struct List));
    node->data = value;
    node->next = NULL;

    while (p->next != NULL)
    {
        p = p->next;
    }

    p->next = node;
}

void head_add_list(struct List *head, datatype value)
{
    struct List *node = (struct List *)malloc(sizeof(struct List));
    node->data = value;
    node->next = NULL;

    head_insert_node(head, node);
}

void destroy_list(struct List *head)
{
    struct List *p = head;
    struct List *q = NULL;

    while (p->next != NULL)
    {
        q = p->next;
        p->next = q->next;
        free(q);
    }
}

struct List *find_list(struct List *head, struct List **prev, datatype value)
{
    struct List *p = head;

    while (p->next != NULL)
    {
        *prev = p;
        p = p->next;
        if (p->data == value)
        {
            return p;
        }
    }
    return NULL;
}

int delete_list(struct List *head, datatype value)
{
    struct List *prev = NULL;
    struct List *p = find_list(head, &prev, value);
    static int count = 0;

    while (p != NULL)
    {
        struct List *l = prev;
        prev->next = p->next;
        p->next = NULL;
        free(p);
        count++;
        p = find_list(l, &prev, value);
    }
    return count;
}

struct List *list_sort(struct List *head)
{
    struct List *list = head;
    struct List *p = head->next;
    struct List *q = p;
    datatype min;

    while (p != NULL && p->next != NULL)
    {
        min = p->data;
        q = p->next;
        while (q != NULL)
        {
            if (min > q->data)
            {
                min = q->data;
                SWAP(datatype, p->data, q->data)
            }
            q = q->next;
        }
        p = p->next;
    }

    return list;
}

void order_insert_list(struct List *head, datatype value)
{
    struct List *p = head;
    struct List *prev = p;
    struct List *node = (struct List *)malloc(sizeof(struct List));
    node->data = value;
    node->next = NULL;

    while (p->next != NULL)
    {
        prev = p;
        p = p->next;
        if (value < p->data)
        {
            node->next = prev->next;
            prev->next = node;
            return ;
        }
    }
    p->next = node;
    return ;
}

void modify_list(struct List *head, datatype src_value, datatype dst_value)
{
    struct List *p = head;

    while (p->next != NULL)
    {
        p = p->next;
        if (p->data == src_value)
        {
            p->data = dst_value;
        }
    }
}

struct List *print_list(struct List *head)
{
    struct List *p = head;

    while (p->next != NULL)
    {
        p = p->next;
        printf("%c ", p->data);
    }
    putchar('\n');
}

int main()
{
    struct List *head = init_list(head);
    struct List *prev = NULL;
    struct List *tail = head;
    datatype value;
//按照输入到序生成链表（头插法）
/*
    while ((value = getchar()) != '\n')
    {
        head_add_list(head, value);
    }
*/
//按输入顺序生成链表（尾插法）
    while ((value = getchar()) != '\n')
    {
        tail = tail_add_list(tail, value);
    }

    printf("原始数据:\n");
    print_list(head);
//查找操作
    struct List *p = find_list(head, &prev, 'x');

    if(p != NULL)
    {
        printf("node has founded\n");
    }
    else
    {
        printf("no node find\n");
    }
//删除操作
    int del_num = delete_list(head, 'x');
    printf("删除操作后:\n");
    printf("del_num = %d\n", del_num);
    print_list(head);
//前插节点擦作
//    head_add_list(head, 'o');
//尾插节点擦作
    tail_add_node(head, 'o');
    printf("尾部添加节点:\n");
    print_list(head);

//修改操作
    modify_list(head, 'd', 'D');
    printf("修改操作后:\n");
    print_list(head);

//链表排序
    head = list_sort(head);
    printf("链表排序后:\n");
    print_list(head);

    order_insert_list(head, 'x');
    printf("顺序添加节点后:\n");
    print_list(head);

    printf("destroy!\n");
    destroy_list(head);
    print_list(head);

    return 0;
}