【数据结构】双向带头循环链表实现及总结

简单不先于复杂,而是在复杂之后。

在这里插入图片描述

文章目录

      • 1. 双向带头循环链表的实现
      • 2. 顺序表和链表的区别

1. 双向带头循环链表的实现

List.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int LTDataType;

typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;

//初始化
LTNode* ListInit();

//打印
void ListPrint(LTNode* phead);

//尾插
void ListPushBack(LTNode* phead, LTDataType x);

//头插
void ListPushFront(LTNode* phead, LTDataType x);

//尾删
void ListPopBack(LTNode* phead);

//头删
void ListPopFront(LTNode* phead);

//链表判空
bool ListEmpty(LTNode* phead);

//链表长度
size_t ListSize(LTNode* phead);

//遍历查找(也可以充当修改的功能,所以链表不需要单独实现修改的功能)
LTNode* ListFind(LTNode* phead, LTDataType x);

//pos之前插入
void ListInsert(LTNode* pos, LTDataType x);

//删除pos位置
void ListErase(LTNode* pos);

//链表销毁
void ListDestory(LTNode* phead);

List.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"


LTNode* ListInit()
{
	LTNode* guard = (LTNode*)malloc(sizeof(LTNode));
	if (guard == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	guard->next = guard;
	guard->prev = guard;

	return guard;
}

LTNode* BuyListNode(LTDataType x)
{
	LTNode* Node = (LTNode*)malloc(sizeof(LTNode));
	if (Node == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	Node->next = NULL;
	Node->prev = NULL;
	Node->data = x;

	return Node;

}

void ListPrint(LTNode* phead)
{
	assert(phead);
	printf("phead<=>");
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}


void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	/*LTNode* newnode = BuyListNode(x);
	LTNode* tail = phead->prev;

	tail->next = newnode;
	newnode->prev = tail;
	phead->prev = newnode;
	newnode->next = phead;*/

	ListInsert(phead, x);
	//双向带头循环链表不需要专门写头插尾插
	//只需要复用ListInsert的代码即可
}

void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);

	//LTNode* newnode = BuyListNode(x);
	//
	先链接newnode和phead->next节点之间的关系
	//newnode->next = phead->next;
	//phead->next->prev = newnode;
	//phead->next = newnode;
	//newnode->prev = phead;

	//如果不想关心顺序
	LTNode* first = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;

	ListInsert(phead->next, x);
}


void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));

	/*LTNode* tail = phead->prev;
	LTNode* prev = tail->prev;

	prev->next = phead;
	phead->prev = prev;
	free(tail);
	tail = NULL;*/

	ListErase(phead->prev);
}

void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));

	/*LTNode* first = phead->next;
	LTNode* second = first->next;

	phead->next = second;
	second->prev = phead;

	free(first);
	first = NULL;*/

	ListErase(phead->next);
}

bool ListEmpty(LTNode* phead)
{
	assert(phead);

	return phead->next == phead;
}

size_t ListSize(LTNode* phead)
{
	assert(phead);

	size_t n = 0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		++n;
		cur = cur->next;
	}

	return n;
}


LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);

	size_t n = 0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
	}
}

void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* prev = pos->prev;
	LTNode* newnode = BuyListNode(x);

	//prev newnode pos 链接
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}


void ListErase(LTNode* pos)
{
	assert(pos);

	LTNode* prev = pos->prev;
	LTNode* next = pos->next;

	prev->next = next;
	next->prev = prev;
	free(pos);
	//pos = NULL;
}


//可以传二级指针,内部置空头结点
//建议:也可以考虑一级指针,让调用 ListDestory 的人置空(可以保持接口一致性)
void ListDestory(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(phead);
	//phead = NULL;
}

Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"

void TestList1()
{
	LTNode* plist = ListInit();
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);

	ListPrint(plist);


	ListPushFront(plist, 10);
	ListPushFront(plist, 20);
	ListPushFront(plist, 30);
	ListPushFront(plist, 40);
	ListPrint(plist);


	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPrint(plist);

}

void TestList2()
{
	LTNode* plist = ListInit();
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPrint(plist);

	ListPopFront(plist);
	ListPopFront(plist);
	ListPrint(plist);

	ListPopFront(plist);
	ListPopFront(plist);
	ListPrint(plist);

}

int main()
{
	TestList2();

	return 0;
}

2. 顺序表和链表的区别

不同点顺序表链表
存储空间物理上一定连续逻辑上连续,但物理上不一定连续
随机访问支持 O(1)不支持 O(N)
任意位置插入或删除元素可能需要搬移元素,效率低 O(N)只需修改指针指向
插入动态顺序表,空间不够时需要扩容没有容量的概念
应用场景元素高效存储+频繁访问任意位置插入和删除频繁
缓存利用率

备注:缓存利用率参考存储体系结构以及局部原理性

顺序表优点:

  1. 尾插尾删效率很高。
  2. 随机访问。(用下标访问)’
  3. 相比链表结构:cpu高速缓存命中率更高。

顺序表缺点:

  1. 头部和中部插入删除效率低。 —O(N)
  2. 扩容。 性能消耗+空间浪费

链表优点:

  1. 任意位置插入删除效率很高。 O(1)
  2. 按需申请释放。

链表缺点:

  1. 不支持随机访问

在这里插入图片描述
cpu执行指令,不会直接访问内存。

  1. 先看数据在不在三级缓存,在(命中)。直接访问
  2. 不在(不命中),先加载到缓存,再访问。当要访问一个数据时,不会只访问这个数据的几个字节,而是从这个位置开始的一段都加载进去缓存。(加载多少取决于硬件)

与程序员相关CPU缓存知识

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/360099.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

mycat-encrypt-server如何支持模糊查询的

最近在研究数据库加密&#xff0c;看到了mycat-encrypt-server项目&#xff0c;看了一下代码&#xff0c;说是支持加密字段的模糊查询&#xff1a; private void parserBinaryExpression(Expression expression, Set<String> columns, String tableAlias, String tableNa…

代码随想录算法训练营第36天 | 435.无重叠区间 763.划分字母区间 56.合并区间

无重叠区间 这道题按左边界排序和右边界排序都是可以的。主要就是要统计出不重合区间的数目。如果按照右区间排序&#xff0c;下面这张图十分形象&#xff1a; 这样去掉一组重叠区间后&#xff0c;剩下的那个区间它的右端点最小&#xff0c;能让后面产生尽量多的不重叠空间。 …

用GPT写PHP框架

参考https://www.askchat.ai?r237422 写一个mvc框架 上面是简单的案例&#xff0c;完整的PHP框架&#xff0c;其核心通常包含以下几个关键组件&#xff1a; 1. 路由&#xff08;Routing&#xff09;&#xff1a;路由组件负责解析请求的URL&#xff0c;并将其映射到相应的控制…

MySQL原理(三)锁定机制(1)综述

一、介绍&#xff1a; 1、锁的本质 业务场景中存在共享资源&#xff0c;多个进程或线程需要竞争获取并处理共享资源&#xff0c;为了保证公平、可靠、结果正确等业务逻辑&#xff0c;要把并发执行的问题变为串行&#xff0c;串行时引入第三方锁当成谁有权限来操作共享资源的判…

嵌入式——模拟/数字转换器(ADC)补充

目录 一、ADC简介 二、ADC功能 1.电压输入范围 2.输入通道 3. 转换顺序 &#xff08;1&#xff09;规则序列 &#xff08;2&#xff09; 注入序列 4.触发源 5. 转换时间 &#xff08;1&#xff09; ADC时钟 &#xff08;2&#xff09; 采样时间 6. 数据寄存器 &am…

ETL怎么实现文件处理

在现代企业及各类组织的日常运作中&#xff0c;数据作为一种关键的信息资源&#xff0c;其管理和分析能力直接影响到决策效率与准确性。文件作为数据的主要载体&#xff0c;承载着从运营报告、客户记录、交易明细等各种类型的数据信息。这些海量且多样的文件数据在未经处理的情…

母排设计时没有柜体3D数据?来试试SuperPanel的钣金功能!

CAD版SuperPanel软件能够助力用户快速、准确地设计和修改母排&#xff0c;同时快速输出加工图纸和数控加工代码。在壳体外购&#xff0c;没有柜体3D数据的情况下&#xff0c;如何轻松进行母排设计&#xff1f;一起来学习利驰数字母排的钣金功能吧&#xff01; SuperPanel的钣金…

通过实测,让你从书客、明基、好视力中选出最优质的护眼台灯

眼睛是我们与世界接触的最重要媒介之一&#xff0c;让我们能够观察到世间万物的美好。然而&#xff0c;由于种种原因&#xff0c;很多人都戴上了眼镜&#xff0c;这无疑在我们与世界的接触中增加了一层隔阂&#xff0c;给生活带来了诸多不便。为了缓解或避免近视的发生&#xf…

【前端-VUE+TS】Vue3组件化-下(五)

一. 插槽的使用 1.1. 认识插槽slot 在开发中&#xff0c;我们会经常封装一个个可复用的组件&#xff1a; 前面我们会通过props传递给组件一些数据&#xff0c;让组件来进行展示&#xff1b;但是为了让这个组件具备更强的通用性&#xff0c;我们不能将组件中的内容限制为固定的d…

STM32F407ZGT6——实验9-4 通用定时器脉冲计数实验

一、配置路线 二、问题及反思 配置的时候误以为需要先把【输入捕获配置】了再去配置【从模式】&#xff0c;后面验证了这样配置没办法产生预期的效果。 代码如下&#xff1a;void gtim_timx_cnt_chy_init(uint16_t psc, uint16_t arr) void gtim_timx_cnt_chy_init(uint16_t…

MyBatis 源码系列:MyBatis 解析配置文件、二级缓存、SQL

文章目录 解析全局配置文件二级缓存解析解析二级缓存缓存中的调用过程缓存中使用的设计模式 解析SQL 解析全局配置文件 启动流程分析 String resource "mybatis-config.xml"; //将XML配置文件构建为Configuration配置类 reader Resources.getResourceAsReader(re…

【3分钟开服】幻兽帕鲁服务器一键部署保姆教程

在帕鲁的世界&#xff0c;你可以选择与神奇的生物「帕鲁」一同享受悠闲的生活&#xff0c;也可以投身于与偷猎者进行生死搏斗的冒险。帕鲁可以进行战斗、繁殖、协助你做农活&#xff0c;也可以为你在工厂工作。你也可以将它们进行售卖&#xff0c;或肢解后食用。 引用自&#x…

脚本实现两台windows 机器间多个目录中文件同步到某个特定的目录里

脚本实现两台windows 机器间多个目录中文件同步到某个特定的目录里 要求&#xff1a;将172.20.26.74 中的test1、test2文件夹里的文件都同步到172.20.26.87机器上的t1文件夹里。 1、两台机器&#xff0c;关闭防火墙&#xff0c;能相互ping通&#xff0c;在172.20.26.87机器上将…

Windows编程入门-窗口控件-资源操作

window控件&#xff1a; 控件是常见的窗口上的交互元素例如&#xff1a;一个按钮&#xff0c;一个复选框&#xff0c;一个列表框等。 当控件的特定功能被触发后&#xff0c;会主动发送消息通知父窗口&#xff0c;父窗口可以通过发送消息给控件控制控件的行为。 控件的本质是一个…

Utreexo:优化Bitcoin UTXO集合的基于哈希的动态累加器

1. 引言 前序博客&#xff1a; Utreexo&#xff1a;比特币UTXO merkle tree proof以节约节点存储空间 MIT Digital Currency Initiative 的 Thaddeus Dryja 2019年论文 Utreexo: A dynamic hash-based accumulator optimized for the Bitcoin UTXO set。 开源代码实现见&…

Kafka 记录

推荐资源 官网http://kafka.apache.org/Githubhttps://github.com/apache/kafka书籍《深入理解Kafka 核心设计与实践原理》 Kafka 架构 Kafka使用ZooKeeper作为其分布式协调框架&#xff0c;其动态扩容是通过ZooKeeper来实现的。Kafka使用Zookeeper保存broker的元数据和消费者信…

使用流服务器m7s对接gb28181

优&#xff1a;sip品牌兼容性比较好&#xff0c;大华&#xff0c;海康都稳定可以&#xff0c;srs的5.0 sip品牌兼容性大华没反应&#xff0c;akstream-sip 大华也有问题&#xff0c;wvp也还可以 缺&#xff1a;目前最新的4.7.4版本&#xff0c;&#xff0c;sip协议用udp正常&a…

年底特殊时期外贸装柜多花点心思

如果可以&#xff0c;尽量不要在工厂快要放假的时候安排装柜了&#xff0c;一个是人手不够&#xff0c;一个是容易漏货&#xff0c;还有就是柜子不好定。 看到有人说自己客户收到货的时候比预期晚了两个星期&#xff0c;一直延误&#xff0c;已经比原来要计划开业的时间推迟&a…

mini-spring 实现应用上下文,自动识别、资源加载、扩展机制

我们不能让面向 Spring 本身开发的 DefaultListableBeanFactory 服务&#xff0c;直接给予用户使用 DefaultListableBeanFactory、XmlBeanDefinitionReader&#xff0c;是我们在目前 Spring 框架中对于服务功能测试的使用方式&#xff0c;它能很好的体现出 Spring 是如何对 xm…

Cocos creator 动作系统

动作系统简介 是用于控制物体运动的一套系统&#xff0c;完全依赖代码进行实现&#xff0c;动态调节节点的移动。 移动 cc.moveTo 移动到某个坐标&#xff08;x,y&#xff09; //1秒时间内&#xff0c;移动到0,0let action1 cc.moveTo(1,0,0)this.node.runAction(action1)c…