数据结构(一)链表

目录

链表

单向链表

单向链表结构与基本操作

插入节点

删除节点

搜索节点

遍历链表

反转链表

双向链表

双向链表结构与基本操作

节点定义和创建

插入节点

删除节点

搜索节点

遍历链表

转链表反

在开始讲线性表之前，先给各位读者重新回顾一下链表

链表

单向链表

单向链表是一种基本的数据结构，由一系列节点组成，每个节点包含两部分：数据域和指针域。数据域存储数据，而指针域存储指向列表中下一个节点的指针。单向链表的特点是数据元素的排列呈现单一方向，即每个节点仅指向下一个节点，直到最后一个节点的指针通常指向NULL，表示链表的结束。

单向链表结构与基本操作

在C语言中，单向链表的节点可以这样定义

typedef struct Node {
    int data;                 // 数据域，存储节点的数据
    struct Node* next;        // 指针域，指向下一个节点的指针
} Node;

 创建节点：初始化一个节点，通常需要提供数据，节点的next指针设置为NULL。

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode != NULL) {
        newNode->data = data;
        newNode->next = NULL;
    }
    return newNode;
}
插入节点

插入节点的基本过程：首先找到正确位置p，然后申请新结点t并对t的结点信息赋值，最后讲t插在p之后

插入到头部

void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

插入到尾部
在链表尾部插入节点需要遍历整个链表，直到找到最后一个节点。

void insertAtTail(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

插入到特定位置

在链表的特定位置插入节点需要遍历链表直到达到指定位置的前一个节点。

void insertAtPosition(Node** head, int data, int position) {
    Node* newNode = createNode(data);
    if (position == 1) {
        insertAtHead(head, data);
    } else {
        Node* temp = *head;
        for (int i = 1; temp != NULL && i < position - 1; i++) {
            temp = temp->next;
        }
        if (temp == NULL) {
            printf("Position exceeds the length of the list.\n");
        } else {
            newNode->next = temp->next;
            temp->next = newNode;
        }
    }
}
删除节点

注意：删除一个节点后必须释放该节点的空间

删除头部节点

void deleteFromHead(Node** head) {
    if (*head != NULL) {
        Node* temp = *head;
        *head = (*head)->next;
        free(temp);
    }
}

删除尾部节点

删除尾部节点需要遍历整个链表以找到倒数第二个节点。

void deleteFromTail(Node** head) {
    if (*head == NULL) return;
    if ((*head)->next == NULL) {
        free(*head);
        *head = NULL;
    } else {
        Node* temp = *head;
        while (temp->next->next != NULL) {
            temp = temp->next;
        }
        free(temp->next);
        temp->next = NULL;
    }
}

删除特定位置的节点

删除特定位置的节点需要遍历链表直到找到该位置的前一个节点。

void deleteAtPosition(Node** head, int position) {
    if (*head == NULL) return;
    if (position == 1) {
        deleteFromHead(head);
    } else {
        Node* temp = *head;
        for (int i = 1; temp != NULL && i < position - 1; i++) {
            temp = temp->next;
        }
        if (temp == NULL || temp->next == NULL) {
            printf("Position exceeds the length of the list.\n");
        } else {
            Node* next = temp->next->next;
            free(temp->next);
            temp->next = next;
        }
    }
}
搜索节点

搜索节点涉及遍历链表以查找具有特定值的节点。

Node* search(Node* head, int key) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == key) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}
遍历链表

遍历链表是访问链表中每个节点的基本操作。

void printList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}
反转链表

反转链表需要改变每个节点的指针方向。

Node* reverseList(Node* head) {
    Node* prev = NULL;
    Node* current = head;
    Node* next = NULL;
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

双向链表

双向链表（Doubly Linked List）是一种链式数据结构，其中每个节点包含数据部分以及两个指针，分别指向前一个节点和后一个节点。这种结构允许从两个方向遍历链表：向前和向后。双向链表在插入和删除操作中比单向链表更加灵活，因为可以直接访问前驱和后继节点。

双向链表结构与基本操作

节点定义和创建

创建一个双向链表节点，需要初始化数据和两个指针：

typedef struct Node {
    int data;                 // 数据域，存储节点的数据
    struct Node* prev;        // 指向前一个节点的指针
    struct Node* next;        // 指向下一个节点的指针
} Node;

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode != NULL) {
        newNode->data = data;
        newNode->prev = NULL;
        newNode->next = NULL;
    }
    return newNode;
}
插入节点

插入到头部

在头部插入节点，需要更新头节点的prev指针和新节点的next指针。

void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head;
    if (*head != NULL) {
        (*head)->prev = newNode;
    }
    *head = newNode;
}

插入到尾部

在尾部插入节点，需要遍历链表找到尾节点，然后更新尾节点的next指针和新节点的prev指针。

void insertAtTail(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prev = temp;
    }
}

插入到特定位置

在特定位置插入节点，需要更新前一个节点的next指针和新节点的prev指针，以及新节点的next指针和后一个节点的prev指针。

void insertAtPosition(Node** head, int data, int position) {
    Node* newNode = createNode(data);
    if (position == 1) {
        insertAtHead(head, data);
    } else {
        Node* temp = *head;
        for (int i = 1; temp != NULL && i < position - 1; i++) {
            temp = temp->next;
        }
        if (temp == NULL) {
            printf("Position exceeds the length of the list.\n");
        } else {
            newNode->next = temp->next;
            newNode->prev = temp;
            if (temp->next != NULL) {
                temp->next->prev = newNode;
            }
            temp->next = newNode;
        }
    }
}
删除节点

删除头部节点：删除头部节点，需要更新头节点的prev指针和新头节点的next指针。

void deleteFromHead(Node** head) {
    if (*head == NULL) return;
    Node* temp = *head;
    *head = (*head)->next;
    if (*head != NULL) {
        (*head)->prev = NULL;
    }
    free(temp);
}

删除尾部节点：删除尾部节点，需要遍历链表找到倒数第二个节点，然后更新其next指针

void deleteFromTail(Node** head) {
    if (*head == NULL) return;
    if ((*head)->next == NULL) {
        free(*head);
        *head = NULL;
    } else {
        Node* temp = *head;
        while (temp->next->next != NULL) {
            temp = temp->next;
        }
        free(temp->next);
        temp->next = NULL;
    }
}

删除特定位置的节点：删除特定位置的节点，需要更新前一个节点的next指针和后一个节点的prev指针

void deleteAtPosition(Node** head, int position) {
    if (*head == NULL) return;
    if (position == 1) {
        deleteFromHead(head);
    } else {
        Node* temp = *head;
        for (int i = 1; temp != NULL && i < position; i++) {
            temp = temp->next;
        }
        if (temp == NULL) {
            printf("Position exceeds the length of the list.\n");
        } else {
            if (temp->prev != NULL) {
                temp->prev->next = temp->next;
            }
            if (temp->next != NULL) {
                temp->next->prev = temp->prev;
            }
            free(temp);
        }
    }
}
搜索节点

搜索节点，需要遍历链表直到找到具有特定值的节点。

Node* search(Node* head, int key) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == key) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}
遍历链表

向前遍历

void printListForward(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

向后遍历

void printListBackward(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d <- ", current->data);
        current = current->prev;
    }
    printf("NULL\n");
}
转链表反
void reverseList(Node** head) {
    Node* temp = NULL;
    Node* current = *head;
    while (current != NULL) {
        temp = current->prev;
        current->prev = current->next;
        current->next = temp;
        current = current->prev;
    }
    if (temp != NULL) {
        *head = temp->prev;
    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/919272.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

MiniMates：一款轻量级的图片数字人驱动框架

MiniMates：一款轻量级的图片数字人驱动框架

随着数字人技术的不断发展，越来越多的应用场景开始涌现，从虚拟主播到AI伴侣，数字人的应用范围越来越广。然而，现有的数字人驱动框架往往存在性能瓶颈、依赖性强、定制难度高等问题。近期，我发现了一款名为 MiniMates 的轻量级图片数字人驱动框架，它在性能、个性化定制和终…
阅读更多...
SpringBoot3_Web开发

SpringBoot3_Web开发

4. 内容协商 一套系统适配多端数据返回 移动端&#xff1a;返回JSON数据第三方&#xff1a;返回XMLIoT&#xff1a;返回自定义协议数据 1. 默认规则 1. SpringBoot 多端内容适配 基于请求头内容协商 【默认】 客户端向服务端发送请求&#xff0c;携带HTTP标准的 Accept 请求…
阅读更多...
C++ —— 剑斩旧我 破茧成蝶—C++11

C++ —— 剑斩旧我 破茧成蝶—C++11

江河入海&#xff0c;知识涌动&#xff0c;这是我参与江海计划的第2篇。 目录 1. C11的发展历史 2. 列表初始化 2.1 C98传统的{} 2.2 C11中的{} 2.3 C11中的std::initializer_list 3. 右值引用和移动语义 3.1 左值和右值 3.2 左值引用和右值引用 3.3 引用延长生命周期…
阅读更多...
mysql复习题（实验7-8）

mysql复习题（实验7-8）

建立一个学生入学信息管理&#xff08;x_y&#xff09;数据库&#xff0c;设计其数据库模式为&#xff1a; 学生表&#xff08;学号&#xff0c;姓名&#xff0c;性别&#xff0c;入学成绩&#xff0c;籍贯&#xff0c;院系编号&#xff09; 院系表&#xff08;院系编号&…
阅读更多...
详细分析ipvsadm负载均衡的命令

详细分析ipvsadm负载均衡的命令

目录 前言1. 基本知识2. 命令参数3. 拓展 前言 LVS四层负载均衡架构详解Lvs推荐阅读&#xff1a;添加链接描述 1. 基本知识 ipvsadm 是用于管理和配置 Linux 服务器上 IP Virtual Server (IPVS) 的工具&#xff0c;是 Linux 提供的一个负载均衡模块&#xff0c;支持多种负载…
阅读更多...
反向代理模块

反向代理模块

1 概念 1.1 反向代理概念 反向代理是指以代理服务器来接收客户端的请求&#xff0c;然后将请求转发给内部网络上的服务器&#xff0c;将从服务器上得到的结果返回给客户端&#xff0c;此时代理服务器对外表现为一个反向代理服务器。 对于客户端来说&#xff0c;反向代理就相当于…
阅读更多...
大数据新视界 -- Impala 性能突破：复杂数据类型处理的优化路径（上）（25 / 30）

大数据新视界 -- Impala 性能突破：复杂数据类型处理的优化路径（上）（25 / 30）

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…
阅读更多...
Excel使用-弹窗“此工作簿包含到一个或多个可能不安全的外部源的链接”的发生与处理

Excel使用-弹窗“此工作簿包含到一个或多个可能不安全的外部源的链接”的发生与处理

文章目录 前言一、探讨问题发生原因1.引入外部公式2.引入外部数据验证二、问题现象排查及解决1.排查公式2.排查数据验证3.特殊处理方式总结前言 作为一种常用的办公软件，Excel被大家所熟知。尽管使用了多年，有时候在使用Excel时候也会发生一些不太常见的现象，需要用心核查下…
阅读更多...
【小程序】dialog组件

【小程序】dialog组件

这个比较简单 我就直接上代码了 只需要传入title即可&#xff0c; 内容部分设置slot 代码 dialog.ttml <view class"dialog-wrapper" hidden"{{!visible}}"><view class"mask" /><view class"dialog"><view …
阅读更多...
跨平台WPF框架Avalonia教程 一

跨平台WPF框架Avalonia教程 一

安装 安装 Avalonia UI 模板​ 开始使用 Avalonia 的最佳方式是使用模板创建一个应用程序。 要安装 Avalonia 模板&#xff0c;请运行以下命令&#xff1a; dotnet new install Avalonia.Templates 备注 对于 .NET 6.0 及更早版本&#xff0c;请将 install 替换为 --inst…
阅读更多...
JSON.stringify的应用说明

JSON.stringify的应用说明

前言 JSON.stringify() 方法将 JavaScript 对象转换为字符串,在日常开发中较常用&#xff0c;但JSON.stringify其实有三个参数&#xff0c;后两个参数&#xff0c;使用较少&#xff0c;今天来介绍一下后两个参数的使用场景和示例。 语法及参数说明 JSON.stringify()&#xf…
阅读更多...
家庭网络常识：猫与路由器

家庭网络常识：猫与路由器

这张图大家应该不陌生——以前家庭网络的连接方式。 图1 家庭网络连接示意图 来说说猫/光猫&#xff1a; 先看看两者的图片。 图2 猫 图3 光猫 这个东西因为英文叫“modem”&#xff0c;类似中文的“猫”&#xff0c;所以简称“猫”。 猫和光猫的区别就是&#xff0c;一…
阅读更多...
core 不可变类型 线程安全 record

core 不可变类型 线程安全 record

当一个类型的对象在创建时被指定状态后&#xff0c;就不会再变化的对象&#xff0c;我们称之为不可变类型。这种类型是线程安全的&#xff0c;不需要进行线程同步&#xff0c;非常适合并行计算的数据共享。它减少了更新对象会引起各种bug的风险&#xff0c;更为安全。 System.D…
阅读更多...
机器学习 ---线性回归

机器学习 ---线性回归

目录 摘要&#xff1a; 一、简单线性回归与多元线性回归 1、简单线性回归 2、多元线性回归 3、残差 二、线性回归的正规方程解 1、线性回归训练流程 2、线性回归的正规方程解 &#xff08;1&#xff09;适用场景 &#xff08;2&#xff09;正规方程解的公式 三、衡量…
阅读更多...
基于Java Springboot甘肃旅游管理系统

基于Java Springboot甘肃旅游管理系统

一、作品包含 源码数据库设计文档万字PPT全套环境和工具资源部署教程 二、项目技术 前端技术&#xff1a;Html、Css、Js、Vue、Element-ui 数据库&#xff1a;MySQL 后端技术&#xff1a;Java、Spring Boot、MyBatis 三、运行环境 开发工具&#xff1a;IDEA/eclipse 数据…
阅读更多...
uniApp项目运行到鸿蒙手机，应用图标一直是H,应用名一直是HBuilder问题

uniApp项目运行到鸿蒙手机，应用图标一直是H,应用名一直是HBuilder问题

项目运行到鸿蒙手机&#xff0c;应用图标一直是H,应用名一直是HBuilder问题 应用运行到鸿蒙手机和鸿蒙模拟器&#xff0c;应用图标一直是H,应用名一直是HBuilder&#xff0c;在自动生成的harmony-configs文件夹下也没有配置的文件&#xff0c; 这时候需要你将DevEco Studio 下…
阅读更多...
Spring：IOC/DI注解开发管理第三方bean

Spring：IOC/DI注解开发管理第三方bean

前面定义bean的时候都是在自己开发的类上面写个注解就完成了&#xff0c;但如果是第三方的类&#xff0c;这些类都是在jar包中&#xff0c;我们没有办法在类上面添加注解&#xff0c;这个时候该怎么办? 遇到上述问题&#xff0c;我们就需要有一种更加灵活的方式来定义bean,这…
阅读更多...
单片机学习笔记 5. 数码管静态显示

单片机学习笔记 5. 数码管静态显示

更多单片机学习笔记&#xff1a;单片机学习笔记 1. 点亮一个LED灯单片机学习笔记 2. LED灯闪烁单片机学习笔记 3. LED灯流水灯单片机学习笔记 4. 蜂鸣器滴~滴~滴~ 目录 0、实现的功能 1、Keil工程 1-1 数码管显示原理 1-2 静态与动态显示 1-3 74HC573锁存器的工作原理 1-…
阅读更多...
使用Ollama和Open WebUI管理本地开源大模型

使用Ollama和Open WebUI管理本地开源大模型

Open WebUI和Ollama介绍 Open WebUI 是一个功能丰富且用户友好的自托管 Web 用户界面&#xff08;WebUI&#xff09;&#xff0c;它被设计用于与大型语言模型&#xff08;LLMs&#xff09;进行交互&#xff0c;特别是那些由 Ollama 或与 OpenAI API 兼容的服务所支持的模型。O…
阅读更多...
Debezium-EmbeddedEngine

Debezium-EmbeddedEngine

提示&#xff1a;一个嵌入式的Kafka Connect源连接器的工作机制 文章目录 前言一、控制流图二、代码分析 1.构造函数2.完成回调3.连接器回调4.RUN总结 前言 工作机制&#xff1a; * 独立运行&#xff1a;嵌入式连接器在应用程序进程中独立运行&#xff0c;不需要Kafka、Kafka C…
阅读更多...
最新文章

Copyright @ 2022~2023