1. Python技术站首页
  2. other

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

• other

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日

相关文章

  • java子类调用父类的方法中包含子类重写的实例方法

    当Java的子类重写了父类的实例方法时，我们可以使用关键字super来调用父类中的这个方法。但是，如果父类的方法中包含了子类重写的实例方法，我们该怎么调用呢？ 以下是几种方法： 1.使用super关键字和this关键字 我们可以在子类中使用super关键字调用父类的方法，然后再使用this关键字来调用子类的方法。 class Animal { public …

    other 2023年6月26日
    00

  • 路由器之vpn应用与配置指南

    以下是关于路由器之VPN应用与配置指南的完整攻略： 什么是VPN？ VPN（Virtual Private Network）是一种安全的网络连接方式，可以在公共网络上建立一个私有网络。VPN可以用于保护您的网络流量，使您的网络活动更加安全和私密。 为什么要在路由器上配置VPN？ 在路由器上配置VPN可以使所有连接到该路由器的设备都受到VPN的保护。这意味着您…

    other 2023年5月6日
    00

  • SpringBoot集成vue的开发解决方案

    下面我将详细介绍SpringBoot集成vue的开发解决方案，包括开发过程和两个示例说明。 一、开发过程 1. 创建SpringBoot项目 首先，我们需要创建一个SpringBoot项目。创建SpringBoot项目有多种方式，这里我们以使用Spring Initializr为例。使用该工具创建一个基本的SpringBoot项目，同时添加Web、Thyme…

    other 2023年6月26日
    00

  • Kotlin伴随对象的初始化方法示例讲解

    请看下面的攻略。 Kotlin伴随对象的初始化方法示例讲解 在Kotlin中，伴随对象是一种特殊类型的对象，它是某个类的单例对象。本文将对Kotlin伴随对象的初始化方法进行详细讲解，并给出两条示例说明。 1. 伴随对象的初始化方法 Kotlin中为伴随对象提供了多种初始化方法，主要有以下两种： init方法：该方法与普通类的init方法类似，用于在伴随对象…

    other 2023年6月20日
    00

  • Java super关键字的使用详解

    Java super关键字的使用详解 在Java中，super是一个关键字，用于访问父类中的属性和方法。通过使用super，我们可以调用父类中定义的属性和方法。本文将详细介绍super关键字的使用情况。 super的使用 在子类中，我们可以使用super来调用父类中的属性和方法。super可以使用两种方式来访问父类中的内容：访问父类中的属性以及调用父类中的方…

    other 2023年6月26日
    00

  • win11系统正式版怎么下载 win11正式版下载地址分享

    Win11系统正式版下载攻略 Win11系统正式版已经发布，以下是下载Win11系统正式版的详细攻略。 步骤一：检查系统要求 在下载Win11系统正式版之前，首先要确保你的计算机符合以下最低系统要求： 处理器：64位处理器，至少为1 GHz的时钟速度，双核心以上 内存：至少4 GB RAM 存储空间：至少64 GB的存储空间 显卡：兼容DirectX 12或…

    other 2023年8月3日
    00

  • node模块之path——path.join和path.resolve的区别

    node模块之path——path.join和path.resolve的区别 概述 在Node.js中，Path模块提供了一些用于处理文件路径的工具方法，如path.join()和path.resolve()。这两个方法都可以用于连接路径和解析相对路径，但是它们有不同的行为和适用场景，因此我们需要了解它们的区别。 path.join() path.join(…

    其他 2023年3月28日
    00

  • 使用justdecompile修改程序集

    什么是JustDecompile？ JustDecompile是一款免费的.NET反编译工具，可以将.NET程序集反编译为C#或VB.NET代码，并且可以修改反编译后的代码并重新编译为程序集。 使用JustDecompile修改程序集 以下是使用JustDecompile修改程序集的步骤： 步骤1：打开程序集 首先，需要打开需要修改的程序集。在JustDec…

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