【C数据结构】带头双向循环链表_HDList

news/2024/9/9 12:33:48

目录

带头双向循环链表_HDList

【1】链表概念

【2】链表分类

【3】带头双向循环链表

【3.1】带头双向循环链表数据结构与接口定义

【3.2】带头双向循环链表初始化

【3.3】带头双向循环链表开辟节点空间

【3.4】带头双向循环链表销毁

【3.5】带头双向循环链表头插

【3.6】带头双向循环链表尾插

【3.7】 带头双向循环链表头删

【3.8】 带头双向循环链表尾删

【3.9】带头双向循环链表在pos位置插

【3.10】带头双向循环链表在pos位置删

【3.11】 无头单向非循环链表查找

【3.12】 无头单向非循环链表返回大小

【3.13】 无头单向非循环链表打印

【3.14】 无头单向非循环链表判空

带头双向循环链表_HDList

【1】链表概念

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

        链表是指逻辑结构上一个挨一个的数据，在实际存储时，并没有像顺序表那样也相互紧挨着。恰恰相反，数据随机分布在内存中的各个位置。

        由于分散存储，为了能够体现出数据元素之间的逻辑关系，每个数据元素在存储的同时，要配备一个指针，用于指向它的直接后继元素，即每一个数据元素都指向下一个数据元素（最后一个指向NULL(空)）。

        如图所示，当每一个数据元素都和它下一个数据元素用指针链接在一起时，就形成了一个链，这个链子的头就位于第一个数据元素，这样的存储方式就是链式存储。

【2】链表分类

  • 单向或者双向链表

  • 带头或不带头链表

  • 循环非循环链表

  • 虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

【3】带头双向循环链表

双向链表特点： 

  • 每次在插入或删除某个节点时, 需要处理四个节点的引用, 而不是两个. 实现起来要困难一些
  • 相对于单向链表, 必然占用内存空间更大一些.
  • 既可以从头遍历到尾, 又可以从尾遍历到头

双向链表的定义: 

        双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

下图为双向链表的结构图。

【3.1】带头双向循环链表数据结构与接口定义

链表中存放的不是基本数据类型，需要用结构体实现自定义：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
​
// 双向带头循环链表中数据元素的构成
typedef int DHLDataType;
typedef struct DHListNode
{
    DHLDataType data; // 数据存储区、
    struct DHListNode* prev;    // 记录上一个节点。
    struct DHListNode* next;    // 记录下一个节点。
}DHListNode;
​
// 双向带头循环链表 - 初始化函数声明。
DHListNode* DHListInit();
​
// 双向带头循环链表 - 开辟节点函数声明。
DHListNode* BuyDHListNode(DHLDataType val);
​
// 双向带头循环链表 - 内存销毁函数声明。
void DHListDestory(DHListNode* pHead);
​
// 双向带头循环链表 - 尾插函数声明。
void DHListPushBack(DHListNode* pHead, DHLDataType val);
​
// 双向带头循环链表 - 头插函数声明。
void DHListPushFront(DHListNode* pHead, DHLDataType val);
​
// 双向带头循环链表 - 尾删函数声明。
void DHListPopBack(DHListNode* pHead);
​
// 双向带头循环链表 - 头删函数声明。
void DHListPopFront(DHListNode* pHead);
​
// 双向带头循环链表 - 在任意位置前插函数声明。
void DHListInsert(DHListNode* pos, DHLDataType val);
​
// 双向带头循环链表 - 在任意位置前删函数声明。
void DHListErase(DHListNode* pos);
​
// 双向带头循环链表 - 打印函数声明。
void DHListPrint(DHListNode* pHead);
​
// 双向带头循环链表 - 判断链表是否为空函声明。
bool DHListEmpty(DHListNode* pHead);
​
// 双向带头循环链表 - 统计节点个数空函数声明。
size_t DHListSize(DHListNode* pHead);
​
// 双向带头循环链表 - 查找节点函数声明。
DHListNode* DHListFind(DHListNode* pHead, DHLDataType val);

【3.2】带头双向循环链表初始化

// 双向带头循环链表 - 初始化函数。
DHListNode* DHListInit()
{
    DHListNode* newNode = (DHListNode*)malloc(sizeof(DHListNode));
    // 判断是否开辟内存空间成功。
    if (newNode == NULL)
    {
        perror("ListInit malloc fail!");
        exit(-1);
    }
​
    // 程序走到这里说明开辟空间成功了。
    newNode->prev = newNode;
    newNode->next = newNode;
    newNode->data = 0;
    return newNode;
}

【3.3】带头双向循环链表开辟节点空间

// 双向带头循环链表 - 开辟节点函数。
DHListNode* BuyDHListNode(DHLDataType val)
{
    DHListNode* newNode = (DHListNode*)malloc(sizeof(DHListNode));
    // 判断是否开辟内存空间成功。
    if (newNode == NULL)
    {
        perror("ListInit malloc fail!");
        exit(-1);
    }
​
    // 程序走到这里说明开辟空间成功了。
    newNode->prev = NULL;
    newNode->next = NULL;
    newNode->data = val;
    return newNode;
​
}

【3.4】带头双向循环链表销毁

// 双向带头循环链表 - 内存销毁函数声明。
void DHListDestory(DHListNode* pHead)
{
    // 断言保护形参指针不为空。
    assert(pHead);
​
    // 遍历一个一个的进行销毁。
    DHListNode* pBegin = pHead->next;
    while (pBegin != pHead)
    {
        DHListNode* next = pBegin->next;
        free(pBegin);
        pBegin = NULL;
​
        // 迭代
        pBegin = next;
    }
​
    // 其实这里是无效的，因为传递的是一级指针，外部调用完进行置NULL；
    pHead = NULL;
}

【3.5】带头双向循环链表头插

// 双向带头循环链表 - 头插函数。
void DHListPushFront(DHListNode* pHead, DHLDataType val)
{   
    // 断言保护形参指针不为空。
    assert(pHead);
​
    /*
    // 开辟新的节点空间。
    DHListNode* newNode = BuyDHListNode(val);
​
    // 链接链表 - 指针交换。
    DHListNode* next = pHead->next;
​
    pHead->next = newNode;
    newNode->prev = pHead;
​
    newNode->next = next;
    next->prev = newNode;
    */
​
    DHListInsert(pHead->next, val);
}

【3.6】带头双向循环链表尾插

// 双向带头循环链表 - 尾插函数。
void DHListPushBack(DHListNode* pHead, DHLDataType val)
{
    // 断言保护形参指针不为空。
    assert(pHead);
​
    /*
    // 开辟新的节点空间。
    DHListNode* newNode = BuyDHListNode(val);
​
    // 链接链表 - 指针交换。
    DHListNode* pTail = pHead->prev;
    pTail->next = newNode;
​
    newNode->next = pHead;
    newNode->prev = pTail;
​
    pHead->prev = newNode;
    */
​
    DHListInsert(pHead, val);
}

【3.7】 带头双向循环链表头删

​
// 双向带头循环链表 - 头删函数。
void DHListPopFront(DHListNode* pHead)
{
    // 断言保护形参指针不为空，判断链表不为空。
    assert(pHead);
    assert(!DHListEmpty(pHead));
​
    /*
    DHListNode* pFirst = pHead->next;
    DHListNode* pSecond = pFirst->next;
​
    // 修改链接。
    pHead->next = pSecond;
    pSecond->prev = pHead;
    // 释放掉保留的最后一个节点。
    free(pFirst);
    pFirst = NULL;
    */
​
    DHListErase(pHead->next);
}

【3.8】 带头双向循环链表尾删

// 双向带头循环链表 - 尾删函数。
void DHListPopBack(DHListNode* pHead)
{
    // 断言保护形参指针不为空，判断链表不为空。
    assert(pHead);
    assert(!DHListEmpty(pHead));
​
    /*
    DHListNode* pTail = pHead->prev;
    DHListNode* pFirst = pTail->prev;
​
    // 修改链接。
    pHead->prev = pFirst;
    pFirst->next = pHead;
    // 释放掉保留的最后一个节点。
    free(pTail);
    pTail = NULL;
    */
​
    DHListErase(pHead->prev);
}

【3.9】带头双向循环链表在pos位置插

// 双向带头循环链表 - 在任意位置前插函数声明。
void DHListInsert(DHListNode* pos, DHLDataType val)
{
    // 断言保护形参指针不为空。
    assert(pos);
​
    // 定位置和开辟新节点。
    DHListNode* prev = pos->prev;
    DHListNode* newNode = BuyDHListNode(val);
​
    // 链接
    prev->next = newNode;
​
    newNode->prev = prev;
    newNode->next = pos;
​
    pos->prev = newNode;
​
}

【3.10】带头双向循环链表在pos位置删

// 双向带头循环链表 - 在任意位置前删函数声明。
void DHListErase(DHListNode* pos)
{
    // 断言保护形参指针不为空。
    assert(pos);
​
    // 定位置
    DHListNode* prev = pos->prev;
    DHListNode* next = pos->next;
​
    // 链接
    prev->next = next;
    next->prev = prev;
    //销毁pos节点
    free(pos);
    pos = NULL;
}

【3.11】 无头单向非循环链表查找

// 双向带头循环链表 - 查找节点函数。
DHListNode* DHListFind(DHListNode* pHead, DHLDataType val)
{
    // 断言保护形参指针不为空。
    assert(pHead);
​
    // 遍历所有节点统计大小
    DHListNode* pBegin = pHead->next;
    while (pBegin != pHead)
    {
        if (pBegin->data == val)
        {
            return pBegin;
        }
​
        pBegin = pBegin->next;
    }
    // 返回NULL
    return NULL;
}

【3.12】 无头单向非循环链表返回大小

// 双向带头循环链表 - 统计节点个数空函数。
size_t DHListSize(DHListNode* pHead)
{
    // 断言保护形参指针不为空。
    assert(pHead);
​
    // 遍历所有节点统计大小
    DHListNode* pBegin = pHead->next;
    size_t count = 0;
    while (pBegin != pHead)
    {
        count++;
        pBegin = pBegin->next;
    }
    // 返回个数
    return count;
}

【3.13】 无头单向非循环链表打印

// 双向带头循环链表 - 打印函数。
void DHListPrint(DHListNode* pHead)
{
    // 断言保护形参指针不为空。
    assert(pHead);
    // 打印一个头作为标志。
    printf("pHead");
​
    // 遍历节点打印数据
    DHListNode* pBegin = pHead->next;
    while (pBegin != pHead)
    {
        printf("<-%d->",pBegin->data);
        pBegin = pBegin->next;
    
    }
    printf("pHead");
    printf("\n");
}

【3.14】 无头单向非循环链表判空

// 双向带头循环链表 - 判断链表是否为空函数。
bool DHListEmpty(DHListNode* pHead)
{
    // 断言保护形参指针不为空。
    assert(pHead);
​
    // 判断链表是不是NULL链表。
    return pHead->next == pHead;
}


http://lihuaxi.xjx100.cn/news/1267689.html

相关文章

[Eigen中文文档] 稀疏矩阵操作

[Eigen中文文档] 稀疏矩阵操作

文档总目录 本文目录 稀疏矩阵格式SparseMatrix 类 第一个示例SparseMatrix 类矩阵和向量属性迭代非零系数 填充稀疏矩阵支持的运算符和函数基本操作矩阵乘积块操作三角形视图和自共轭视图 英文原文(Sparse matrix manipulations) 处理和解决稀疏问题涉及各种模块&#xff0c…
阅读更多...
Android Studio实现推箱子小游戏

Android Studio实现推箱子小游戏

项目目录 一、项目概述二、开发环境三、详细设计四、运行演示五、项目总结 一、项目概述 推箱子是一款非常受欢迎的益智游戏&#xff0c;游戏的玩法简单&#xff0c;但是需要玩家具备一定的逻辑思维能力和空间感知能力&#xff0c;因此深受广大玩家的喜爱。在游戏中&#xff0…
阅读更多...
macOS Monterey 12.6.7 (21G651) 正式版发布，ISO、IPSW、PKG 下载

macOS Monterey 12.6.7 (21G651) 正式版发布，ISO、IPSW、PKG 下载

macOS Monterey 12.6.7 (21G651) 正式版发布&#xff0c;ISO、IPSW、PKG 下载 本站下载的 macOS 软件包&#xff0c;既可以拖拽到 Applications&#xff08;应用程序&#xff09;下直接安装&#xff0c;也可以制作启动 U 盘安装&#xff0c;或者在虚拟机中启动安装。另外也支持…
阅读更多...
你的电脑该如何选择？-涵子的个人想法

你的电脑该如何选择？-涵子的个人想法

最近&#xff0c;苹果出了一系列的新的电脑&#xff0c;例如Mac Studio&#xff0c;Mac Pro和MacBook Air。三个电脑彻底向我们诠释了&#xff1a;电脑的性能&#xff0c;可以“无限”扩大。至于我们这些“程序猿”&#xff0c;比较钟爱Windows和Linux&#xff0c;那么&#xf…
阅读更多...
【账号篇】华硕电脑-华硕账号注销教程

【账号篇】华硕电脑-华硕账号注销教程

【账号篇】华硕电脑-华硕账号注销教程 手机号和邮箱号注册的华硕账户无法合并&#xff0c;无法互相关联&#xff0c;需要数据同步的可以选择先注销删除其中一个账号再关联—【蘇小沐】 文章目录 【账号篇】华硕电脑-华硕账号注销教程1.实验环境 &#xff08;一&#xff09;华硕…
阅读更多...
Elasticsearch“滚动查询“（Scrolling）的机制的与Java使用ES Client 调用滚动查询

Elasticsearch“滚动查询“（Scrolling）的机制的与Java使用ES Client 调用滚动查询

Elasticsearch"滚动查询"&#xff08;Scrolling&#xff09;的机制的与Java使用ES Client 调用滚动查询 前言1. 滚动查询的一般步骤1.1 发起初始搜索请求,返回命中结果和滚动ID1.2 使用滚动ID检索下一页结果1.4 重复执行直到没有检索结果返回1.5 清除滚动上下文释放资…
阅读更多...
基于spss的多元统计分析 之 实例１（挤压塑料胶卷的最优工艺研究）（6/8）

基于spss的多元统计分析 之 实例１（挤压塑料胶卷的最优工艺研究）（6/8）

挤压塑料胶卷的最优工艺研究 摘要 多元方差分析是同时分析多个响应变量和一个共同预测变量集之间关系的检验。与方差分析一样&#xff0c;多元方差分析需要连续响应变量和类别预测变量。与运行多个方差分析&#xff08;一次一个响应变量&#xff09;相比&#xff0c;多元方差分…
阅读更多...
Pytorch数据类型Tensor张量操作(操作比较全)

Pytorch数据类型Tensor张量操作(操作比较全)

文章目录 Pytorch数据类型Tensor张量操作一.创建张量的方式1.创建无初始化张量2.创建随机张量3.创建初值为指定数值的张量4.从数据创建张量5.生成等差数列张量 二.改变张量形状三.索引四.维度变换1.维度增加unsqueeze2.维度扩展expand3.维度减少squeeze4.维度扩展repeat 五.维度…
阅读更多...
最新文章

Copyright @ 2022~2023