1. Python技术站首页
  2. other

C语言超详细讲解数据结构中双向带头循环链表

• other
yizhihongxing

C语言超详细讲解数据结构中双向带头循环链表

什么是双向带头循环链表

双向带头循环链表是一种非常常用的数据结构，它由多个节点组成，每个节点都有一个前驱指针和一个后继指针，形成一个双向链表；同时，它也是循环链表，即链表的头指针和尾指针是相连的形成一个环的结构；而带头链表则是在链表的开头添加一个头节点来方便书写，方便读者理解，常见于书籍和教程中。

因此，双向带头循环链表的结构可以表示为：

------         ------         ------   
|head | <----> |node1| <----> |node2| <----> ... <----> |nodeN| <----> |head |
------         ------         ------                       ------

双向带头循环链表的实现

定义节点结构体

首先，我们需要定义一个节点的结构体，如下所示：

typedef struct DNode {
    int data;                      // 节点数值 data
    struct DNode *prior, *next;    // 指向直接前驱和直接后继的指针
} DNode, *DLinkList;

节点结构体中，除了记录节点的数值外，还有指向前驱和后继节点的指针，此处用prior和next变量表示，方便我们理解。

初始化双向带头循环链表

接下来我们需要初始化双向带头循环链表，我们定义一个InitList()函数来实现链表的初始化。

int InitList(DLinkList *L) {
    DNode *head = (DNode*)malloc(sizeof(DNode));    // 为头节点分配内存空间
    if (!head)        // 内存分配失败
        return 0;   // 返回0表示初始化失败

    head->data = 0;                      // 头节点的数据域为0
    head->next = head;                   // 头节点的后继指针指向头节点本身
    head->prior= head;                   // 头节点的前驱指针指向头节点本身
    *L = head;                           // 将头节点赋给L指向的链表指针

    return 1;        // 返回1表示初始化成功
}

双向带头循环链表的插入

接下来，我们需要实现双向带头循环链表的插入，即在链表指定位置插入一个新节点。此处我们定义一个InsertList()函数来实现节点的插入。

int InsertList(DLinkList L, int pos, int e) {
    int i = 0;                // i为计数器
    DNode *p = L, *s;         // p为指向当前遍历到的节点, s为插入的新节点
    while (p && i < pos - 1) {   // 定位到 pos 的前一位，如果 pos 为 1，则 p 为头节点
        i++;
        p = p->next;
    }

    if (!p || i > pos - 1)    // 跳出循环有两种情况, i > pos - 1 表示 pos 已经越界
        return 0;            // 返回0表示插入失败 

    s = (DNode*)malloc(sizeof(DNode));   // 为新节点分配内存空间
    s->data = e;           // 新节点的数据域为e
    s->prior= p;           // 新节点的前驱指向p
    s->next = p->next;     // 新节点的后继指向p的后继
    p->next->prior= s;     // p的后继的前驱指向s
    p->next = s;           // p的后继指向s

    return 1;              // 返回1表示插入成功
}

双向带头循环链表的删除

除了插入节点，我们还需要实现双向带头循环链表的删除操作。这里我们定义一个DeleteList()函数来实现删除操作。

int DeleteList(DLinkList L, int pos) {
    int i = 0;                   // i为计数器
    DNode *p = L, *q;            // p为指向当前遍历到的节点，q为被删除的节点

    while (p->next != L && i < pos - 1) {  // 定位到 pos 的前一位，如果 pos 为 1，则 p 为头节点
        i++;
        p = p->next;
    }

    if (p->next == L || i > pos - 1)    // 跳出循环有两种情况, i > pos - 1 表示 pos 已经越界
        return 0;               // 返回0表示删除失败

    q = p->next;          // q指向要删除的节点 
    q->next->prior= p;   // q的后继的前驱指向p
    p->next = q->next;    // p的后继指向q的后继 
    free(q);             // 释放q节点的内存空间

    return 1;             // 返回1表示删除成功
}

双向带头循环链表的遍历

最后，我们需要遍历整个双向带头循环链表，即输出链表中的每一个节点。此处我们定义一个TraverseList()函数来实现链表的遍历。

int TraverseList(DLinkList L) {
    DNode *p = L->next;    // 从第一个节点开始遍历

    while (p != L) {       // 遍历到尾节点为止
        printf("%d ", p->data);  // 输出节点的数据域
        p = p->next;      // 指向下一个节点
    }
    printf("\n");

    return 1;    // 返回1表示遍历成功
}

示例说明

示例1：向链表中插入3个节点，并输出链表

#include <stdio.h>
#include <stdlib.h>

typedef struct DNode {
    int data;                      // 节点数值 data
    struct DNode *prior, *next;    // 指向直接前驱和直接后继的指针
} DNode, *DLinkList;

int InitList(DLinkList *L) {
    DNode *head = (DNode*)malloc(sizeof(DNode));    // 为头节点分配内存空间
    if (!head)        // 内存分配失败
        return 0;   // 返回0表示初始化失败

    head->data = 0;                      // 头节点的数据域为0
    head->next = head;                   // 头节点的后继指针指向头节点本身
    head->prior= head;                   // 头节点的前驱指针指向头节点本身
    *L = head;                           // 将头节点赋给L指向的链表指针

    return 1;        // 返回1表示初始化成功
}

int InsertList(DLinkList L, int pos, int e) {
    int i = 0;                // i为计数器
    DNode *p = L, *s;         // p为指向当前遍历到的节点, s为插入的新节点
    while (p && i < pos - 1) {   // 定位到 pos 的前一位，如果 pos 为 1，则 p 为头节点
        i++;
        p = p->next;
    }

    if (!p || i > pos - 1)    // 跳出循环有两种情况, i > pos - 1 表示 pos 已经越界
        return 0;            // 返回0表示插入失败 

    s = (DNode*)malloc(sizeof(DNode));   // 为新节点分配内存空间
    s->data = e;           // 新节点的数据域为e
    s->prior= p;           // 新节点的前驱指向p
    s->next = p->next;     // 新节点的后继指向p的后继
    p->next->prior= s;     // p的后继的前驱指向s
    p->next = s;           // p的后继指向s

    return 1;              // 返回1表示插入成功
}

int DeleteList(DLinkList L, int pos) {
    int i = 0;                   // i为计数器
    DNode *p = L, *q;            // p为指向当前遍历到的节点，q为被删除的节点

    while (p->next != L && i < pos - 1) {  // 定位到 pos 的前一位，如果 pos 为 1，则 p 为头节点
        i++;
        p = p->next;
    }

    if (p->next == L || i > pos - 1)    // 跳出循环有两种情况, i > pos - 1 表示 pos 已经越界
        return 0;               // 返回0表示删除失败

    q = p->next;          // q指向要删除的节点 
    q->next->prior= p;   // q的后继的前驱指向p
    p->next = q->next;    // p的后继指向q的后继 
    free(q);             // 释放q节点的内存空间

    return 1;             // 返回1表示删除成功
}

int TraverseList(DLinkList L) {
    DNode *p = L->next;    // 从第一个节点开始遍历

    while (p != L) {       // 遍历到尾节点为止
        printf("%d ", p->data);  // 输出节点的数据域
        p = p->next;      // 指向下一个节点
    }
    printf("\n");

    return 1;    // 返回1表示遍历成功
}

int main() {
    DLinkList L;     // 声明双向带头循环链表

    if (InitList(&L)) {     // 初始化链表
        InsertList(L, 1, 1);   // 向链表的第一个位置插入节点1
        InsertList(L, 2, 2);   // 向链表的第二个位置插入节点2
        InsertList(L, 3, 3);   // 向链表的第三个位置插入节点3
        TraverseList(L);       // 输出链表

        return 0;
    }
}

输出结果为：

1 2 3

示例2：删除链表中第二个节点，并输出链表

#include <stdio.h>
#include <stdlib.h>

typedef struct DNode {
    int data;                      // 节点数值 data
    struct DNode *prior, *next;    // 指向直接前驱和直接后继的指针
} DNode, *DLinkList;

int InitList(DLinkList *L) {
    DNode *head = (DNode*)malloc(sizeof(DNode));    // 为头节点分配内存空间
    if (!head)        // 内存分配失败
        return 0;   // 返回0表示初始化失败

    head->data = 0;                      // 头节点的数据域为0
    head->next = head;                   // 头节点的后继指针指向头节点本身
    head->prior= head;                   // 头节点的前驱指针指向头节点本身
    *L = head;                           // 将头节点赋给L指向的链表指针

    return 1;        // 返回1表示初始化成功
}

int InsertList(DLinkList L, int pos, int e) {
    int i = 0;                // i为计数器
    DNode *p = L, *s;         // p为指向当前遍历到的节点, s为插入的新节点
    while (p && i < pos - 1) {   // 定位到 pos 的前一位，如果 pos 为 1，则 p 为头节点
        i++;
        p = p->next;
    }

    if (!p || i > pos - 1)    // 跳出循环有两种情况, i > pos - 1 表示 pos 已经越界
        return 0;            // 返回0表示插入失败 

    s = (DNode*)malloc(sizeof(DNode));   // 为新节点分配内存空间
    s->data = e;           // 新节点的数据域为e
    s->prior= p;           // 新节点的前驱指向p
    s->next = p->next;     // 新节点的后继指向p的后继
    p->next->prior= s;     // p的后继的前驱指向s
    p->next = s;           // p的后继指向s

    return 1;              // 返回1表示插入成功
}

int DeleteList(DLinkList L, int pos) {
    int i = 0;                   // i为计数器
    DNode *p = L, *q;            // p为指向当前遍历到的节点，q为被删除的节点

    while (p->next != L && i < pos - 1) {  // 定位到 pos 的前一位，如果 pos 为 1，则 p 为头节点
        i++;
        p = p->next;
    }

    if (p->next == L || i > pos - 1)    // 跳出循环有两种情况, i > pos - 1 表示 pos 已经越界
        return 0;               // 返回0表示删除失败

    q = p->next;          // q指向要删除的节点 
    q->next->prior= p;   // q的后继的前驱指向p
    p->next = q->next;    // p的后继指向q的后继 
    free(q);             // 释放q节点的内存空间

    return 1;             // 返回1表示删除成功
}

int TraverseList(DLinkList L) {
    DNode *p = L->next;    // 从第一个节点开始遍历

    while (p != L) {       // 遍历到尾节点为止
        printf("%d ", p->data);  // 输出节点的数据域
        p = p->next;      // 指向下一个节点
    }
    printf("\n");

    return 1;    // 返回1表示遍历成功
}

int main() {
    DLinkList L;     // 声明双向带头循环链表

    if (InitList(&L)) {     // 初始化链表
        InsertList(L, 1, 1);   // 向链表的第一个位置插入节点1
        InsertList(L, 2, 2);   // 向链表的第二个位置插入节点2
        InsertList(L, 3, 3);   // 向链表的第三个位置插入节点3

        DeleteList(L, 2);      // 删除节点2

        TraverseList(L);       // 输出链表

        return 0;
    }
}

输出结果为：

1 3

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：C语言超详细讲解数据结构中双向带头循环链表 - Python技术站

赞 (0)
0 0 打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023年6月27日
下一篇 2023年6月27日

相关文章

  • Android启动初始化方案App StartUp的应用详解

    Android启动初始化方案App StartUp的应用详解 什么是App StartUp App StartUp是Android Jetpack库中的一部分，提供了一种标准化的方式来在应用程序启动时执行后台初始化任务，以便在应用程序启动后更快地响应用户操作。 如何集成App StartUp 集成时需要创建一个实现了AppInitializer接口的类，在这…

    other 2023年6月20日
    00

  • Win10预览版9860自制ISO镜像下载

    Win10预览版9860自制ISO镜像下载攻略 本攻略将详细介绍如何下载Win10预览版9860的自制ISO镜像。请按照以下步骤进行操作： 步骤一：准备工作 在开始之前，请确保您已经完成以下准备工作： 确保您的计算机已经安装了合适的操作系统和软件，以便进行下载和制作ISO镜像。 确保您的计算机已经连接到互联网，并且网络连接稳定。 步骤二：查找可靠的下载源 在…

    other 2023年8月3日
    00

  • 手把手教你Vue3如何封装组件

    标题：手把手教你Vue3如何封装组件 1. 确定组件功能和需求 在封装组件之前，需要明确组件的功能和需求。这里我们以一个基础的计数器组件为例，具体的需求包括： 组件中包含一个按钮和一个显示计数器值的标签。 点击按钮可以实现加1操作。 可以设置计数器的初始值。 可以设置计数器的最大值，当计数器值达到最大值时，不能再进行加1操作。 2. 创建组件 在确定了组件的…

    other 2023年6月25日
    00

  • 通过Java创建Socket连接到服务器方式

    通过Java创建Socket连接到服务器的方式实际上就是通过Java Socket API来实现。 下面是该方式的详细攻略： 步骤一：导入java.net包 import java.net.*; 步骤二：创建一个Socket对象 String host = "服务器地址或域名"; int port = 8080; Socket socke…

    other 2023年6月27日
    00

  • 详解Java中的内存屏障

    详解Java中的内存屏障 内存屏障（Memory Barrier）是一种同步机制，用于控制指令的执行顺序和内存的可见性。在Java中，内存屏障主要用于解决多线程并发访问共享数据时的一致性问题。本文将详细讲解Java中的内存屏障，并提供两个示例说明。 1. 内存屏障的作用 内存屏障的作用主要有两个方面： 保证指令的执行顺序：内存屏障可以防止指令重排序，确保指令…

    other 2023年8月2日
    00

  • 用securecrt连接虚拟机中的linux系统(ubuntu)

    用SecueCRT连接虚拟机中的Linux系统（Ubuntu） 随着云计算技术的发展，虚拟机技术在日常工作中越来越常见。有时我们需要使用SecureCRT等终端工具连接到虚拟机中的Linux系统进行操作。本文将介绍如何使用SecureCRT连接到虚拟机中的Linux系统（Ubuntu）。 前提条件 在开始本文前，需要满足以下条件： 已成功创建虚拟机且安装好L…

    其他 2023年3月28日
    00

  • Jquery实现图片预加载与延时加载的方法

    以下是详细讲解 “JQuery实现图片预加载与延迟加载的方法”的完整攻略： 什么是图片预加载？ 图片预加载是在网页加载时提前把所需的图片加载进缓存，从而提高用户访问网页时的速度体验。而不是等到需要显示出来的时候再去加载，造成用户等待时间过长。 JQuery实现图片预加载的方法 实现图片预加载的方法一般有两种方式： 1. 利用JQuery的ajax请求 可以用…

    other 2023年6月25日
    00

  • RSync实现文件同步备份配置详解

    RSync实现文件同步备份配置详解 什么是RSync RSync (remote synchronization) 是一个快速、灵活、可靠的远程文件复制工具。 常用于将数据从一个位置同步到另一个位置（比如从本地服务器同步到远程服务器），也用于备份、镜像、迁移数据。 RSync具有以下特点： 可以在本地或远程之间进行同步，支持使用SSH等网络协议进行安全连接 …

    other 2023年6月25日
    00
合作推广
合作推广
分享本页
返回顶部