`
hideto
  • 浏览: 2678940 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

CLRS笔记10、基本数据结构

阅读更多
数学中的集合是不变的,而算法所操作的集合是可以增大、缩小或产生其他变化的,称这种集合为动态集合
支持插入元素、删除元素和测试元素是否属于集合操作的动态集合称为字典

栈和队列
栈为后进先出LIFO,队列为先进先出FIFO
栈的INSERT操作称为PUSH,DELETE操作成为POP
队列的INSERT操作称为ENQUEUE,DELETE操作称为DEQUEUE

链表
链表L中包含一个key域和两个指针域prev和next
prev指向链表中前驱元素,next指向链表中后继元素
如果prev[x]=NIL,则元素x没有前驱节点,即x为head
如果next[x]=NIL,则元素x没有后继节点,即x为tail
属性head[L]指向head,如果head[L]=NIL,则链表L为空

单链接的链表中每个元素没有prev指针
已排序的链表的线性顺序对应着链表中各元素的key的线性顺序
环形链表的head元素的prev指向tail,tail元素的next指向head

链表的Search时间为Θ(n),Insert时间为Θ(1),Delete时间为Θ(1)

哨兵(sentinel)可以用来简化边界条件
假设链表L和一个对象nil[L],它表示NIL,但有prev和next域
这样就可以将一个双向链表变成一个带哨兵的环形双向链表,哨兵元素介于head和tail之间

有根树
对二叉树T中的元素x,p[x]表示父亲,left[x]表示左儿子,right[x]表示右儿子
如果p[x]=NIL,则x为根
T的根用root[T]表示,如果root[T]=NIL,则树T为空

如果节点的子女数无限制,则无法事先知道多少域要分配
如果节点的最多子女数为常数k,那么用child1,child2,...,childk来代替left和right域,这样会浪费大量的存储空间,因为大多数节点只有少量子女

可以用left和right-sibling来表示这种树
left[x]表示x的最左孩子,right-sibling[x]表示x紧右边的孩子
如果x没有孩子,则left[x]=NIL
如果x是其父节点的最右孩子,则right-sibling[x]=NIL
分享到:
评论

相关推荐

    基于Springboot的实验报告系统源码数据库文档.zip

    基于Springboot的实验报告系统源码数据库文档.zip

    ERA5_Climate_Single_Month.txt

    GEE训练教程——Landsat5、8和Sentinel-2、DEM和各2哦想指数下载

    基于springboot智能健康饮食系统源码数据库文档.zip

    基于springboot智能健康饮食系统源码数据库文档.zip

    基于SpringBoot的校园服务系统源码数据库文档.zip

    基于SpringBoot的校园服务系统源码数据库文档.zip

    史上最全IXIA测试仪配置使用指导手册(含IxNetwork,图文并茂超详细!).zip

    内容概要: IXIA测试仪的基本配置.doc ixia测试仪基础使用示例.doc IxNetwork如何进行抓包回放-V1.0.pdf IxNetwork如何自定义报文-V2.0.pdf ixia构造ip分片方法.txt IxNetwork使用简介.pdf 适用人群:网络协议造包、打流相关的测试工程技术人员,想要学习的同学可以下载哈 使用场景:构造pcap包,打流 Ixia简介 IXIA使用的是Server-client模式,Server端在测试仪表的主机上,在开机后会随着主机内的操作系统的启动而自动启动,一般情况下不需要人为的手工启动。因此在通常不需要为主机配置专用的显示器和键盘。 client端包括两个测试软件: Ixia Explorer和ScriptMate。这两个软件一般安装在测试用计算机上,在仪表自带的主机中也有这两个软件。根据测试项目的不同来选择使用不同的软件。Ixia Explorer主要提供数据流的测试,针对设备的功能进行测试; ScriptMate提供各种性能测试窗口,针对设备的性能进行测试。 Auto:自动分配;

    基于Python+Django花卉商城系统源码数据库文档.zip

    基于Python+Django花卉商城系统源码数据库文档.zip

    Umi-OCR-main.zip

    Umi-OCR-main.zip

    微信小程序源码-促销抽奖.zip

    基于微信小程序开发的促销抽奖小工具源码,适用于初学者了解小程序开发过程以及简单抽奖工具的实现。

    Sen2_median.txt

    GEE训练教程——Landsat5、8和Sentinel-2、DEM和各2哦想指数下载

    springboot的概要介绍与分析

    以下是一个关于Spring Boot设计的资源描述及项目源码的简要概述: Spring Boot设计资源描述 Spring Boot是一个为基于Spring的应用提供快速开发工具的框架,其设计旨在简化Spring应用的初始搭建和开发过程。以下是一些关键资源: Spring Boot官方文档:详细阐述了Spring Boot的核心特性、自动配置原理、起步依赖、内嵌式服务器等关键概念。这是学习和掌握Spring Boot设计的首选资源。 在线教程与视频:各大在线教育平台提供了丰富的Spring Boot教程和视频课程,从基础入门到高级应用,帮助开发者全面了解和掌握Spring Boot设计。 书籍与电子资料:许多技术书籍和在线电子资料深入讲解了Spring Boot的设计原理、最佳实践和项目案例,为开发者提供了宝贵的学习资源。 项目源码示例 以下是一个简单的Spring Boot项目源码示例,用于演示Spring Boot的基本结构和自动配置功能: java // 引入Spring Boot依赖 @SpringBootApplication public class MySpri

    基于springboot美妆领域管理系统源码数据库文档.zip

    基于springboot美妆领域管理系统源码数据库文档.zip

    tables-3.7.0+gpl-cp37-cp37m-win_amd64.whl

    tables-3.7.0+gpl-cp37-cp37m-win_amd64.whl

    算法实现的概要介绍与分析

    算法是计算机科学的核心,它们在解决各种问题时发挥着关键作用。一个好的算法不仅可以提高程序的效率,还可以简化复杂的问题。下面我将通过一个具体的例子——快速排序算法(Quick Sort)——来展示算法的实现过程,包括资源描述和项目源码。 ### 快速排序算法简介 快速排序是一种高效的排序算法,采用分治法的思想。其基本步骤如下: 1. 从数列中挑出一个元素,称为“基准”(pivot)。 2. 重新排序数列,所有比基准值小的元素放到基准前面,所有比基准值大的元素放到基准后面(相同的数可以到任一边)。在这个分割结束之后,该基准就处于数列的中间位置。这个称为分割(partition)操作。 3. 递归地(recursive)把小于基准值的子数列和大于基准值的子数列排序。 ### 资源描述 快速排序算法因其高效性和简洁性,在实际应用中非常受欢迎。它的时间复杂度平均为 O(n log n),最坏情况下为 O(n^2),但这种情况很少发生。快速排序的空间复杂度为 O(log n),因为它使用了递归来实现。 快速排序的一个典型应用场景是在数据库系统中对大量数据进行排序。由于它的高效性,快速排序

    基于springboot农场投入品运营线上管理系统源码数据库文档.zip

    基于springboot农场投入品运营线上管理系统源码数据库文档.zip

    基于springboot个性化影院推荐系统源码数据库文档.zip

    基于springboot个性化影院推荐系统源码数据库文档.zip

    linux基础进阶笔记

    linux基础进阶笔记,配套视频:https://www.bilibili.com/list/474327672?sid=4493093&spm_id_from=333.999.0.0&desc=1

    微信自动抢红包动态库.zip程序资源学习资料参考

    小程序 微信自动抢红包动态库.zip程序资源学习资料参考

    iOS版微信抢红包插件(支持后台抢红包).zip

    小程序 iOS版微信抢红包插件(支持后台抢红包).zip

    经典-FPGA时序约束教程

    经典-FPGA时序约束教程

    基于springboot的智慧点餐系统源码数据库文档.zip

    基于springboot的智慧点餐系统源码数据库文档.zip

Global site tag (gtag.js) - Google Analytics