链表实现

1.定义

• 1.数据类型
  2.链表节点：数据类型Datatype、下一个节点的地址next
  3.链表结构体：头节点header、链表节点个数size

// 数据类型
typedef int Datatype;
// 链表节点
typedef struct Node{
        Datatype data;
        struct Node* next;
} Node;
// 链表结构体
typedef struct List{
        Node* header;
        int size;
} List;

注：链表节点中的成员struct Node* next中的Node为结构体名而不是重定义后的名字。

2.函数：创建链表

// 函数：创建链表
// 返回值：结构体指针
List* Create_list(){ 
        List* list = malloc(sizeof(List));
        list->header = NULL;
        list->size = 0;
        return list;
}

3.函数：添加元素

• 首添加

// 首添加
void prepend(List* list,Datatype data){
        Node* new_node = malloc(sizeof(Node));
        new_node->data = data;
        new_node->next = list->header;
        list->header = new_node;
        list->size++;
}

• 尾添加

// 尾添加
void append(List* list,Datatype data){
        Node* p = NULL;
        // 创建新的节点
        Node* new_node = malloc(sizeof(Node));
        new_node->data = data;
        new_node->next = NULL;

        // 空链表
        if(NULL == list->header) list->header = new_node;
        else{
                p = list->header;
                while(NULL != p->next){
                        p = p->next;
                }
                p->next = new_node;
        }
        list->size++;
}

4.函数：获取元素个数

// 函数：获取链表元素个数
int Get_List_size(List* list){
        return list->size;
}

5.函数：根据下标获取元素

// 函数：根据下标获取链表元素地址
// 返回链表元素地址（便于修改）
Datatype* Get_List_data(List* list,int index){
        if(NULL == list->header) return NULL;
        if(0 > index || index >= Get_List_size(list)) return NULL;
        Node* p = list->header;
        for(int i=0;i<index;i++){
                p = p->next;
        }
        return &(p->data);
}

6.函数：向链表中插入元素

• 考虑三种情况：
  1.空链表\插入到第一个位置：prepend()
  2.插入到最后一个位置：append()
  3.插入到中间的位置
• 需要找到要插入位置的前一个元素，先“启下”后“承上”

// 插入
// 需要找到要插入坐标的前一个元素
bool insert(List* list,int index,Datatype insert_data){
        Node* p = list->header;
        if(index < 0) return false;
        if(index > Get_List_size(list)) return false;
        // 情况1：空链表\插入到第一个位置
        if(NULL == list->header || index == 0){
                prepend(list,insert_data);
                return true;
        }
        // 情况2：插入到最后一个位置
        if(index == Get_List_size(list)){
                append(list,insert_data);
                return true;
        }
        // 情况3：插入到中间位置
        for(int i=0;i<index-1;i++){
                p = p->next;
        }
        Node* new_node = malloc(sizeof(Node));
        new_node->data = insert_data;
        new_node->next = p->next;
        p->next = new_node;
        list->size++;
        return true;
}

7.函数：删除链表元素

• 考虑三种情况：
  1.删除第一个元素
  2.删除最后一个元素
  3.删除中间元素
  其中2，3可合并
• 需要找到要删除元素的前一个元素

// 删除
// 找到要删除的前一个元素
bool delete(List* list,int index){
        // 情况1:空链表
        if(NULL == list->header) return false;
        if(index < 0) return false;
        if(index >= Get_List_size(list)) return false;

        Node* p = list->header;
        // 情况2：删除首元素
        if(0 == index){
                list->header = p->next;
                free(p);
                p = NULL;
                return true;
        }
        //
        // 找到要删除的前一个元素
        for(int i=0;i<index-1;i++){
                p = p->next;
        }
        //
        /*
        // 情况3：删除最后一个元素
        if(index == Get_List_size(*header) - 1){
                free(p->next);
                p->next = NULL;
                return true;
        }
        */
        // 情况3、4可以合并
        // 情况4：删除中间元素
        Node* delete_node = p->next;
        p->next = delete_node->next;
        free(delete_node);
        delete_node = NULL;
        list->size--;
        return true;
}

8.销毁链表

// 函数：销毁链表
void Destory_list(List** list){
        Node* p = (*list)->header;
        while(NULL != p){
                Node* next = p->next;
                free(p);
                p = next;
        }
        free(*list);
        *list = NULL;

}