线性表（线性表的链式表示和实现）

#include <stdlib.h>
#include <stdbool.h>

#define TYPE int

typedef struct Node
{
    TYPE data;
    struct Node* next;
}Node;

// 创建节点
Node* create_node(TYPE data)
{
    Node* node = malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    return node;
}


// 根据前驱节点删除元素
static bool _delete_list(Node* prev)
{
    if(NULL == prev || NULL == prev->next)
        return false;

    Node* node = prev->next;
    prev->next = node->next;
    free(node);
    return true;
}

static bool _insert_list(Node* prev,TYPE data)
{
    if(NULL == prev)
        return false;
        
    Node* node = create_node(data);
    node->next = prev->next;
    prev->next = node;
    return true;
}

// 返回index下标的前驱节点
static Node* _index_list(Node* head,int index)
{
    // 找下标为i的节点的前驱
    Node* prev = head;
    while(NULL != prev->next && index-- >= 1)
        prev = prev->next;

    // index 非法，超出了节点的数量
    if(NULL == prev->next || index < -1)
        return NULL;

    return prev;
}

// 查询出值为data的前驱节点
static Node* _query_list(Node* head,TYPE data)
{
    Node* prev = head;
    while(NULL != prev->next && data != prev->next->data)
        prev = prev->next;

    if(NULL == prev->next)
        return NULL;

    return prev;
}

// 创建带头的空链表
Node* create_list(void)
{
    Node* node = malloc(sizeof(Node));
    node->next = NULL;
    return node;
}

// 销毁链表
void destory_list(Node* head)
{
    while(NULL != head)
    {
        Node* node = head;
        head = head->next;
        free(node);
    }
}

// 在头部添加元素
void front_list(Node* head,TYPE data)
{
    _insert_list(head,data);
}

// 在指定位置插入元素
bool insert_list(Node* head,int index,TYPE data)
{
    
    return _delete_list(_index_list(head,index));
}

// 按值删除元素
bool delete_value_list(Node* head,TYPE data)
{

    return _delete_list(_query_list(head,data));
}

// 按值修改
bool modify_value_list(Node* head,TYPE old,TYPE new)
{
    Node* prev = _query_list(head,old);
    if(NULL == prev)
        return false;

    prev->next->data = new;
    return true;
}

// 按位置修改
bool modify_index_list(Node* head,int index,TYPE new)
{
    Node* prev = _index_list(head,index);
    if(NULL == prev)
        return false;

    prev->next->data = new;
    return true;
}

// 访问指定位置的元素
bool get_list(Node* head,int index,TYPE* data)
{
    Node* prev = _index_list(head,index);
    if(NULL == prev)
        return false;

    *data = prev->next->data;
    return true;
}

// 查询元素
int query_list(Node* head,TYPE key)
{
    int index = 0;
    for(Node* n=head->next; NULL!=n; n=n->next)
    {
        if(n->data == key)
            return index;
        index++;
    }
    
    return -1;
}

// 经典排序
void sort_list(Node* head)
{
    for(Node* i=head->next; NULL!=i->next; i=i->next)
    {
        for(Node* j=i->next; NULL!=j; j=j->next)
        {
            if(i->data > j->data)
            {
                TYPE tmp = i->data;
                i->data = j->data;
                j->data = tmp;
            }
        }
    }
}

void show_list(Node* head)
{
    // 要跳过头节点
    for(Node* n=head->next; NULL!=n; n=n->next)
    {
        printf("%d ",n->data);
    }
    printf("\n");
}

int main(int argc,const char* argv[])
{
    Node* list = create_list();
    for(int i=0; i<10; i++)
    {
        front_list(list,rand()%100);
    }
    show_list(list);
    //delete_index_list(list,-1);
    //delete_value_list(list,9);
    insert_list(list,9,100);
    sort_list(list);
    show_list(list);
    return 0;
}