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

news/2024/12/15 12:52:38/

目录

带头双向循环链表_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;}// 返回NULLreturn 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://www.ppmy.cn/news/461723.html

相关文章

Window10专业版 激活

Window10专业版 激活

Windows 10 专业版用激活工具批量激活的&#xff0c;激活时间好像是180天。到期后激活工具会自动激活&#xff0c;或者需要重新激活。 1、首先查看自己系统的激活状态; 快捷键 win r 输入命令&#xff1a; slmgr.vbs -xpr 随后弹出窗口显示过期时间。 2 然后以管理员模式打开命…
阅读更多...
win10专业版系统激活

win10专业版系统激活

1、查看win10专业版系统激活状态 点击“此电脑”&#xff0c;右键“属性”可查看系统激活状态 2、在任务栏输入“cmd”搜索“命令提示符”&#xff0c;右键点击“以管理员身份运行”&#xff0c;此时将“以管理员身份”打开DOS窗口&#xff0c;在此界面下输入命令&#xff1a…
阅读更多...
Win10激活（家庭版升级到专业版）带你5分钟解决

Win10激活（家庭版升级到专业版）带你5分钟解决

作为一名计算机专业的学生&#xff0c;将自己的电脑激活到专业版是我们的必经之路。接下来的内容希望对在座的各位都是辣G有帮助。 一、误删密钥导致windows处于未激活状态的解决方法。 点击----激活----疑难解答。&#xff08;我这里是已经升级到专业版&#xff0c;需要产品…
阅读更多...
激活win10专业版

激活win10专业版

每180天激活一次 转载于:https://www.cnblogs.com/fanjie/p/7687206.html
阅读更多...
win10专业版激活方式

win10专业版激活方式

1.在此电脑图标上点击右键&#xff0c;打开属性&#xff0c;查看自己win10系统版本。 2.若未激活&#xff0c;则右键左下角开始&#xff0c;管理员身份进入命令提示符。 3.在此界面中&#xff0c;依次输出以下命令&#xff1a; slmgr.vbs /upk 回车&#xff0c;此时弹出窗口显未…
阅读更多...
WIN10专业版/家庭版激活

WIN10专业版/家庭版激活

1、CMD命令行用管理员模式打开 2、依次复制粘贴下面命令 slmgr.vbs /upk 弹出“已成功卸载了产品密钥” slmgr /ipk W269N-WFGWX-YVC9B-4J6C9-T83GX &#xff08;专业版&#xff09; slmgr /ipk TX9XD-98N7V-6WMQ6-BX7FG-H8Q99 &#xff08;家庭版&#xff09; 弹…
阅读更多...
如何成功激活win10专业版

如何成功激活win10专业版

如何成功激活win10专业版 以下图片参考至脚本之家&#xff0c;但本人也是亲自试验过的&#xff0c;从win10家庭版改成专业版&#xff0c;并成功激活了&#xff01;&#xff01; 方法/步骤 1、首先&#xff0c;我们先查看一下Win10正式专业版系统的激活状态&#xff1a; 点击…
阅读更多...
Win10专业版激活步骤

Win10专业版激活步骤

-----安装Win10专业版&#xff0c;请winR&#xff0c;键入winver回车&#xff0c;可查看版本------ 1.点击左下角windows按钮&#xff0c;找到设置并打开&#xff0c;依次点击“更新和安全”-”激活“&#xff0c;查看此电脑激活状态&#xff0c;若未激活... 2.右键单机windows…
阅读更多...
最新文章

Copyright @ 2022~2023