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

ops/2025/1/21 13:15:20/

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("销毁成功！");
}


http://www.ppmy.cn/ops/151920.html

相关文章

【漫话机器学习系列】054.极值（Extrema）

【漫话机器学习系列】054.极值（Extrema）

极值&#xff08;Extrema&#xff09; 定义 极值是数学分析和优化问题中的一个核心概念&#xff0c;指函数在某个定义域内取得的最大值或最小值。根据极值的性质&#xff0c;可以将其分为两类&#xff1a; 局部极值&#xff08;Local Extrema&#xff09;&#xff1a;函数在…
阅读更多...
Micrometer+Zipkin 分布式链路追踪

Micrometer+Zipkin 分布式链路追踪

MicrometerZipkin 分布式链路追踪&#xff08;Distributed Tracing&#xff09;是一种用于监控和分析分布式系统性能的技术。它允许开发人员和运维人员追踪请求在分布式系统中的传播路径&#xff0c;包括跨服务调用、数据库访问、缓存查询等操作。通过分布式链路追踪&#xff0…
阅读更多...
WPF基础 | 初探 WPF：理解其核心架构与开发环境搭建

WPF基础 | 初探 WPF：理解其核心架构与开发环境搭建

WPF基础 | 初探 WPF&#xff1a;理解其核心架构与开发环境搭建 一、前言二、WPF 核心架构2.1 核心组件2.2 布局系统2.3 数据绑定机制2.4 事件处理机制 三、WPF 开发环境搭建3.1 安装 Visual Studio3.2 创建第一个 WPF 应用程序 结束语优质源码分享 WPF基础 | 初探 WPF&#xff…
阅读更多...
游戏引擎学习第79天

游戏引擎学习第79天

当前任务回顾 我们目前的工作重点是碰撞检测的更新&#xff0c;特别是将游戏的世界表示方式扩展到三维空间。尽管游戏本身是二维的&#xff0c;但我们希望它能够在三维空间中处理更多的内容&#xff0c;以支持那些需要考虑高度的游戏元素&#xff0c;如楼层、台阶等。我们的目…
阅读更多...
【HF设计模式】06-命令模式

【HF设计模式】06-命令模式

声明&#xff1a;仅为个人学习总结&#xff0c;还请批判性查看&#xff0c;如有不同观点&#xff0c;欢迎交流。 摘要 《Head First设计模式》第6章笔记&#xff1a;结合示例应用和代码&#xff0c;介绍命令模式&#xff0c;包括遇到的问题、采用的解决方案、遵循的 OO 原则、…
阅读更多...
WinHttp API接口辅助类实现GET POST网络通讯

WinHttp API接口辅助类实现GET POST网络通讯

1、简述 近期需要在MFC基础上开发网络Http通讯，开始使用的WinINet进行通讯，后面发现WinINet对连接超时这块不支持设置，在网上搜索了几种方式效果都不太好，于是决定用WinHttp API接口进行通讯，分别对GET、POST进行了封装。 2、使用到接口 2.1、WinHttpOpen WinHttpOpen 是…
阅读更多...
Golang Gin系列-2：搭建Gin 框架环境

Golang Gin系列-2：搭建Gin 框架环境

开始网络开发之旅通常是从选择合适的工具开始的。在这个全面的指南中&#xff0c;我们将引导你完成安装Go编程语言和Gin框架的过程&#xff0c;Gin框架是Go的轻量级和灵活的web框架。从设置Go工作空间到将Gin整合到项目中&#xff0c;本指南是高效而强大的web开发路线图。 安装…
阅读更多...
1.简单的爬虫

1.简单的爬虫

1.数据在哪里&#xff1f; 在页面源码里 直接获取数据 不在页面源码里 找到真正获取数据的URL&#xff0c;再获取数据 2.requests模块 安装 pip install requests pip install -i https://pypi.tuna.tsinghua.edu.cn/simple requests抓网站文字数据 import requestsurl &qu…
阅读更多...
最新文章

Copyright @ 2022~2023