热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

数据结构详解:带头双向循环链表及其代码实现

本文将详细介绍带头双向循环链表的基本概念和实现方法,包括结构体定义、链表创建、初始化、查找、插入、删除及打印等操作。

带头双向循环链表

  • 1. 带头双向循环链表介绍
  • 2. 代码实现带头双向循环链表
    • 2.1 创建结构体
    • 2.2 链表创建
    • 2.3 链表初始化(哨兵位)
    • 2.4 查找链表中某一元素的位置
    • 2.5 任意位置插入数据(在pos位置之前)
    • 2.6 任意位置删除数据
    • 2.7 打印链表
  • 3. 总结
1. 带头双向循环链表介绍

带头双向循环链表是一种特殊的链表结构,它包含一个哨兵节点,并且每个节点都包含指向前一个节点和后一个节点的指针。这种结构使得链表的操作更加灵活和高效。

2. 代码实现带头双向循环链表

2.1 创建结构体

首先,我们需要定义一个结构体来表示链表中的节点:


typedef int LTDataType; // 定义数据类型,可以随时更改

typedef struct ListNode {
    LTDataType data; // 节点数据
    struct ListNode* pre; // 指向前一个节点的指针
    struct ListNode* next; // 指向后一个节点的指针
} LSTNode; // 重命名结构体类型

2.2 链表创建

接下来,我们编写一个函数来创建新的节点:


LSTNode* BuyNode(LTDataType x) {
    LSTNode* newnode = (LSTNode*)malloc(sizeof(LSTNode));
    if (newnode == NULL) {
        perror("malloc fail");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    newnode->pre = NULL;
    return newnode;
}

2.3 链表初始化(哨兵位)

为了方便后续操作,我们通常会在链表中添加一个哨兵节点:


LSTNode* Init() {
    LSTNode* phead = BuyNode(-1); // 初始化哨兵节点,数据为-1
    phead->pre = phead; // 哨兵节点的前指针指向自身
    phead->next = phead; // 哨兵节点的后指针指向自身
    return phead;
}

2.4 查找链表中某一元素的位置

我们可以编写一个函数来查找链表中某个特定元素的位置:


LSTNode* LSTFind(LSTNode* phead, LTDataType x) {
    assert(phead); // 哨兵节点不能为空
    LSTNode* cur = phead->next; // 从哨兵节点的下一个节点开始查找
    while (cur != phead) { // 循环链表,直到回到哨兵节点
        if (cur->data == x) {
            return cur; // 找到目标节点,返回该节点
        }
        cur = cur->next; // 继续查找下一个节点
    }
    return NULL; // 未找到目标节点,返回空
}

2.5 任意位置插入数据(在pos位置之前)

我们可以在指定位置之前插入一个新的节点:


void LSTInsert(LSTNode* pos, LTDataType x) {
    assert(pos); // 插入位置不能为空
    LSTNode* newnode = BuyNode(x); // 创建新节点
    LSTNode* prev = pos->pre; // 获取插入位置的前一个节点
    prev->next = newnode; // 更新前一个节点的后指针
    newnode->pre = prev; // 更新新节点的前指针
    newnode->next = pos; // 更新新节点的后指针
    pos->pre = newnode; // 更新插入位置的前指针
}

2.6 任意位置删除数据

我们也可以删除指定位置的节点:


void LSTErase(LSTNode* pos) {
    assert(pos); // 删除位置不能为空
    LSTNode* pos_pre = pos->pre; // 获取删除位置的前一个节点
    LSTNode* pos_next = pos->next; // 获取删除位置的后一个节点
    free(pos); // 释放删除节点的内存
    pos_pre->next = pos_next; // 更新前一个节点的后指针
    pos_next->pre = pos_pre; // 更新后一个节点的前指针
}

2.7 打印链表

最后,我们可以编写一个函数来打印链表中的所有节点:


void LSTPrint(LSTNode* phead) {
    assert(phead); // 哨兵节点不能为空
    LSTNode* cur = phead->next; // 从哨兵节点的下一个节点开始打印
    while (cur != phead) { // 循环链表,直到回到哨兵节点
        printf("%d ", cur->data); // 打印当前节点的数据
        cur = cur->next; // 移动到下一个节点
    }
}
3. 总结

带头双向循环链表通过引入哨兵节点,使得链表的插入和删除操作变得更加简单和高效。无论是头插、尾插、头删还是尾删,都可以借助哨兵节点轻松实现。希望本文能帮助你更好地理解和掌握这种数据结构。


推荐阅读
  • 本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法,通过具体示例代码加深理解。 ... [详细]
  • 本文深入探讨 MyBatis 中动态 SQL 的使用方法,包括 if/where、trim 自定义字符串截取规则、choose 分支选择、封装查询和修改条件的 where/set 标签、批量处理的 foreach 标签以及内置参数和 bind 的用法。 ... [详细]
  • Explore how Matterverse is redefining the metaverse experience, creating immersive and meaningful virtual environments that foster genuine connections and economic opportunities. ... [详细]
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 本文详细介绍了Java中org.w3c.dom.Text类的splitText()方法,通过多个代码示例展示了其实际应用。该方法用于将文本节点在指定位置拆分为两个节点,并保持在文档树中。 ... [详细]
  • 本文详细介绍了 Apache Jena 库中的 Txn.executeWrite 方法,通过多个实际代码示例展示了其在不同场景下的应用,帮助开发者更好地理解和使用该方法。 ... [详细]
  • 本实验主要探讨了二叉排序树(BST)的基本操作,包括创建、查找和删除节点。通过具体实例和代码实现,详细介绍了如何使用递归和非递归方法进行关键字查找,并展示了删除特定节点后的树结构变化。 ... [详细]
  • 本文详细介绍了C语言中链表的两种动态创建方法——头插法和尾插法,包括具体的实现代码和运行示例。通过这些内容,读者可以更好地理解和掌握链表的基本操作。 ... [详细]
  • 根据最新发布的《互联网人才趋势报告》,尽管大量IT从业者已转向Python开发,但随着人工智能和大数据领域的迅猛发展,仍存在巨大的人才缺口。本文将详细介绍如何使用Python编写一个简单的爬虫程序,并提供完整的代码示例。 ... [详细]
  • Linux设备驱动程序:异步时间操作与调度机制
    本文介绍了Linux内核中的几种异步延迟操作方法,包括内核定时器、tasklet机制和工作队列。这些机制允许在未来的某个时间点执行任务,而无需阻塞当前线程,从而提高系统的响应性和效率。 ... [详细]
  • 双向链表的定义与基本操作
    双向链表是一种在每个节点中包含两个指针的数据结构,分别指向其前驱和后继节点。这种特性使得双向链表在某些操作上比单向链表更为灵活和高效。本文将详细介绍双向链表的基本概念及其常见的操作。 ... [详细]
  • 1:有如下一段程序:packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]
  • 本文基于刘洪波老师的《英文词根词缀精讲》,深入探讨了多个重要词根词缀的起源及其相关词汇,帮助读者更好地理解和记忆英语单词。 ... [详细]
  • 本文介绍了Java并发库中的阻塞队列(BlockingQueue)及其典型应用场景。通过具体实例,展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递,并结合线程池和原子类优化性能。 ... [详细]
  • 1.如何在运行状态查看源代码?查看函数的源代码,我们通常会使用IDE来完成。比如在PyCharm中,你可以Ctrl+鼠标点击进入函数的源代码。那如果没有IDE呢?当我们想使用一个函 ... [详细]
author-avatar
輕風斬情絲
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有