数据结构——链表和单向链表

1、链表的先容

（1）界说
        链表是一种链式存储的线性表
        链表是一种根本的数据结构，它由一系列节点构成，每个节点包罗一个值和指向下一个节点的指针
节点如下图所示： 

        与数组差异，链表中的节点不愿定是一连的存储空间，因此可以有效地使用内存空间
（2）特点：可以动态添加和删除节点，而不须要预先知道数据的数目，不善于随机访问（要遍历）
（3）优缺点 
        长处：不要求大片一连空间，改变容量方便；可以动态的添加和删除节点
        缺点：不方便可随机存取，要泯灭肯定空间存放指针
2、链表的分类 

链表可以分为三种范例：
        单向链表：节点由2部门构成（数据域存储当前元素，指针域用来指向下一个节点），每个节点只有一个指针指向下一个节点，末了一个节点的指针指向NULL

        双向链表：节点由3部门构成（数据域存储当前元素，2个指针域：一个用来指向上一个节点地点，一个用来指向下一个节点地点），每个节点有两个指针，分别指向上一个节点和下一个节点，可以在O(1)时间内实现向前和向后遍历

        循环链表：在单向或双向链表的根本上，将末了一个节点的指针指向头节点，形成一个环

链表的种类着实有很多种，按照单双向、带头(没有元素值，只有指针)不带头、循环不循环，一共可以分为8种范例，但最常见就是单向链表和双向链表
3、链表的使用

        插入使用：可以在链表头或尾插入节点，也可以在指定位置插入节点（头插、尾插、中央插）
        删除使用：可以删除指定节点或按照值删除节点（头删、尾删、中央删）
        查找使用：可以查找指定节点或按照值查找节点
        遍历使用：可以遍历整个链表，输出每个节点的值或实行其他使用
4、 单向链表（单向、不带头、不循环）

4.1  01单向链表.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <Windows.h>
#include <stdlib.h>
#include <memory.h> 
#include <assert.h>
//界说单向、不带头、不循环链表的元素节点结构体范例
typedef int eleT;
typedef struct Link_Node {
    eleT val;  //数据域：存储节点元素值
    struct Link_Node* next;  //指针域，指向下一个节点
}LKNode;
void print_menu();
LKNode* init_List(eleT value);
void print_List(LKNode* LinkNode);
void head_Insert(LKNode** LinkNode, eleT value);
void tail_insert(LKNode* LinkNode, eleT value);
void head_delete(LKNode** LinkNode);
void tail_delete(LKNode** LinkNode);
LKNode* find_item(LKNode* LinkNode, eleT value);
void middle_delete(LKNode* LinkNode, eleT value);
void mid_insert(LKNode* temp, eleT newvalue);
void destroy(LKNode** LinkNode);
void fn3();
4.2 main.c

#include "01单向链表.h"
int main() {
    fn3();
    return 0;
}
4.3  01单向链表.c

#include "01单向链表.h"
//逻辑结构：线性结构
//存储结构（物理结构）：链式存储（存储序次和逻辑序次不在乎是否划一）
//头节点变传地点，稳固传值
void fn3() {
    int order = 0;
    print_menu();
    LKNode* LinkNode = NULL;  //存放头节点指针
    eleT value = 0;
    eleT newvalue = 0;
    LKNode* temp = NULL;
    while (1) {
        printf("请输入使用指令：");
        scanf("%d", &order);
        switch (order) {
        case 1:  //链表初始化，初始化一个头节点（包罗元素）
            printf("请输入头节点元素值：");
            scanf(" %d", &value);
            LinkNode = init_List(value);
            break;
        case 2:  //打印链表，遍历
            print_List(LinkNode);
            break;
        case 3:  //链表头插
            printf("请输入要插入的元素：");
            scanf(" %d", &value);
            head_Insert(&LinkNode, value);
            break;
        case 4:  //链表尾插
            printf("请输入要尾插的元素：");
            scanf(" %d", &value);
            tail_insert(LinkNode, value);
            break;
        case 5:  //链表头删
            head_delete(&LinkNode);
            break;
        case 6:  //链表尾删
            tail_delete(&LinkNode);
            break;
        case 7:  //链表的查找
            //思绪：找到了，返回当前元素节点的指针；找不到，返回NULL
            printf("请输入要查找的元素：");
            scanf(" %d", &value);
            temp = find_item(LinkNode, value);
            if (temp == NULL) {
                printf("没有此元素！\n");
            }else {
                printf("找到了，该元素值为：%d\n", temp->val);
            }
            break;
        case 8:  //链表的中央删，至少要3个元素
            printf("请输入要删除的元素：");
            scanf(" %d", &value);
            middle_delete(LinkNode, value);
            break;
        case 9:  //链表的中央插
            //要求：至少有1个元素
            printf("请输入要插入的元素：");
            scanf(" %d", &newvalue);
            printf("请输入要在哪个元素的后边插入：");
            scanf(" %d", &value);
            temp = find_item(LinkNode, value);
            if (temp == NULL) {
                printf("没有此元素，无法插入！\n");
            }else{
                mid_insert(temp, newvalue);
            }
            break;
        case 10:  //链表烧毁
            destroy(&LinkNode);
            break;
        case 11:  //退出
            return;
        default:
            printf("输入错误，请重新输入！\n");
        }
    }
}
//打印菜单
void print_menu(){
    system("cls");  //屏幕清空
    printf("使用指令分析：\n");
    printf("1：链表初始化\n2：打印链表\n");
    printf("3：链表头插\n4：链表尾插\n");
    printf("5：链表头删\n6：链表尾删\n");
    printf("7：链表的查找\n8：链表的中央删\n");
    printf("9：链表的中央插\n10：链表烧毁\n");
    printf("11：退出\n");
    printf("************************\n");
}
//链表初始化，初始化一个头节点（包罗元素）
LKNode* init_List(eleT value) {
    //申请节点内存
    LKNode* newNode = (LKNode*)malloc(sizeof(LKNode));
    ////判定内存是否申请乐成
    //if (!newNode) {
    //    printf("内存申请失败！\n");
    //    return;
    //}
    //增补两个调试代码常用的方法
    //exit(参数)  //用于制止步调实行，输出一些参数，一样平常用0表现正常退出，非0非常退出
    //assert(条件)  //条件为真，步调正常实行；条件为假，步调报错，退出（须要导入<assert.h>）
    
    //简化   判定内存是否申请乐成
    assert(newNode);
    newNode->val = value;
    newNode->next = NULL;
    printf("初始化乐成！\n");
    return newNode;
}
//打印链表，遍历
void print_List(LKNode* LinkNode) {
    assert(LinkNode);
    ////遍历
    //LKNode* temp = LinkNode;
    //while (temp->next != NULL) {
    //    printf("%d ", temp->val);
    //    temp = temp->next;
    //}
    //printf("%d ", temp->val);
    //另一种遍历方法
    LKNode* temp = LinkNode;
    while (1) {
        printf("%d ", temp->val);
        if (temp->next == NULL) {  //尾节点
            break;
        }
        temp = temp->next;  //temp是一个指针；temp->next也是一个指针，它存储在当前节点temp中，指向链表中的下一个节点，我将其明确为存储的是下一个节点的地点
    }
    printf("\n");
}
//链表头插
void head_Insert(LKNode** LinkNode, eleT value) {
    assert(*LinkNode);
    //(1)创建新节点
    LKNode* newNode = (LKNode*)malloc(sizeof(LKNode));
    assert(newNode);
    //(2)给新节点成员赋值
    newNode->val = value;
    newNode->next = *LinkNode;
    //(3)更新头节点
    *LinkNode = newNode;
    printf("头插乐成！\n");
}
//链表尾插
void tail_insert(LKNode* LinkNode, eleT value) {
    assert(LinkNode);
    //(1)创建新节点
    LKNode* newnode = (LKNode*)malloc(sizeof(LKNode));
    assert(newnode);
    //(2)给新节点成员赋值
    newnode->val = value;
    newnode->next = NULL;
    //(3)将新节点放到链表的尾部
    //起首找到链表的尾节点
    LKNode* temp = LinkNode;
    while (1) {
        if (temp->next == NULL) {  //尾节点
            //是尾节点，将新节点插到尾节点的后边
            temp->next = newnode;
            break;
        }
        temp = temp->next;  //temp是一个指针，temp->next也是一个指针，它存储在当前节点temp中，指向链表中的下一个节点
    }
    printf("尾插乐成！\n");
}
//链表头删
void head_delete(LKNode** LinkNode) {
    assert(*LinkNode);
    //(1)生存当前头节点的后一个节点
    LKNode* temp = (*LinkNode)->next;  
    //(2)开释原来头节点
    free(*LinkNode);  
    //(3)更新头节点
    *LinkNode = temp;  
    printf("头删乐成！\n");
}
//链表尾删
void tail_delete(LKNode** LinkNode) {
    assert(*LinkNode);
    //须要思量到只有一个节点的环境
    if ((*LinkNode)->next == NULL) {
        free(*LinkNode);  //开释当前节点
        *LinkNode = NULL;
    }else {
        //找到链表的倒数第二个元素节点
        LKNode* temp = *LinkNode;
        while (1) {
            if (temp->next->next == NULL) {  //temp->next：倒数第二个元素节点中的next；temp->next->next：尾节点中next
                break;
            }
            temp = temp->next;
        }
        //开释尾节点
        free(temp->next);  //temp：倒数第二个元素节点
        temp->next = NULL;  //更新尾节点
        printf("尾节点删除乐成！\n");
    }
}
//链表的查找
//思绪：找到了，返回当前元素节点的指针；找不到，返回NULL
LKNode* find_item(LKNode* LinkNode, eleT value) {
    assert(LinkNode);
    LKNode* temp = LinkNode;
    while (temp) {
        if (temp->val == value) {
            //找到了
            return temp;
        }
        temp = temp->next;
    }
    return NULL;
}
//链表的中央删
void middle_delete(LKNode* LinkNode, eleT value) {
    assert(LinkNode);
    //查找到删除元素的前一个元素的地点
    LKNode* temp = LinkNode;
    while (temp) {
        if (temp->next->val == value) {  //temp：当前节点（删除元素的前一个元素）；temp->next：当前节点的下一个节点
            //找到了，删除temp->next
            LKNode* ptr = temp->next;  //生存要删除的节点
            temp->next = temp->next->next;
            free(ptr);  //开释要删除的节点
            printf("删除乐成！\n");
            break;
        }
        temp = temp->next;
        if (temp->next == NULL) {
            printf("没有此元素，无法删除！\n");
            break;
        }
    }
}
//链表的中央插
//要求：至少有1个元素
void mid_insert(LKNode* temp, eleT newvalue) {
    //(1)创建新节点
    LKNode* newnode = (LKNode*)malloc(sizeof(LKNode));
    assert(newnode);
    //(2)给新节点数据域赋值
    newnode->val = newvalue;
    //(3)将新节点插入
    newnode->next = temp->next;
    temp->next = newnode;
    printf("插入乐成！\n");
}
//链表烧毁
void destroy(LKNode** LinkNode) {
    //遍历出来一个一个删除，并更新头节点
    assert(*LinkNode);  //*LinkNode：头节点
    while (*LinkNode) {
        LKNode* temp = (*LinkNode)->next;
        free(*LinkNode);
        *LinkNode = temp;
    }
    *LinkNode = NULL;
    printf("烧毁乐成！");
}