没有合适的资源?快使用搜索试试~ 我知道了~
首页18个高级数据结构整理归纳
18个高级数据结构整理归纳
3星 · 超过75%的资源 需积分: 49 52 下载量 50 浏览量
更新于2023-03-16
评论 10
收藏 1.79MB PDF 举报
东南大学高级数据结构课程 自己和基友整理归纳的课上所讲16个高级数据结构以及它们之间的逻辑关系
资源详情
资源评论
资源推荐
DataStructureDataStructure
.数据结构的基本问题
数据在计算机系统中的表和组织,但是有约束
内存结构:叉树-平衡-近似平衡-不平衡 优化 时间
外存结构:B+树、R树、希尔伯特树 优化 I/O次数
云存储结构:分布式散列表(巨规模)
Compact(紧缩)存储:哈夫曼编码、FP树(前缀、trie树)、
Lossy-Counting(有损计数)
区间树、k-d 树、红树、红树的拓展(应)
数据压缩
算法:搜索、排序、匹配(matching)
.基本思想基本法
A)空间换时间 跳表 树节点增加更多指针
B)困难:
(1)访问的次线性 O(logn) 线性的困难在于扫描整个数据集
(2)数据
a)规模 访问的规模 巨规模
b)动态性
c)复杂性(链值、结构化数据、结构化数据)
d)安全性
(3)外存的访问模式(如何减 I/O 次数)
(4)存储体系/平台/介质
a)内存:树(平衡树 近似平衡树 不平衡树) 访问 O(logn)
b)外存:B+树(维)、R 树(维到维)、Hilbert树(维到维)
c)分布式:CAN 散列表、CHORD 链表、BATON B+树
C)具体法:希尔排序(初等数论、数逆序)、数学期望(和的期望等于期望的
和)、分形
有哪些数据结构 应场景 解决什么问题 是怎么做的 背后原理 为什么这么做 如
何改进 相互关系
哪些情况会让问题变得困难 如何解决
对数据结构的整理分类的理解
关键技术的基本思想 简短清晰表达 重点突出 总分结构
表达能是评价的因素
例题:
1.写出BST/红树/B+/Spaly树之间的区别和应场景
2.致哈希表在分布式络中的应和性能优化
分布式哈希(DHT)
两个关键点:每个节点只维护部分路由;每个节点只存储部分数据。从实现整个络
中的寻址和存储。
致性哈希:
DHT的种实现。本质还是个哈希算法。
四个概念和原则:
a)balance:哈希结果尽可能的平均分散到各个节点上,使得每个节点都能得到充分利。
b)Monotonicity:上也说了,如果是签名取模算法,节点变更会使得整个络的映射关
系更改。如果是carp,会使得1/n的映射关系更改。致性哈希的标,是节点变更,不会
改变络的映射关系。
c)spread:同份数据,存储到不同的节点上,换之就是系统冗余。致性哈希致于降
低系统冗度。
d)load:负载分散,和balance其实是差不多的意思,不过这更多是指数据存储的均
衡,balance是指访的均衡。
致性哈希基本解决了在P2P环境中最为关键的问题——如何在动态的络拓扑中分布存储
和路由。每个节点仅需维护少量相邻节点的信息,并且在节点加/退出系统时,仅有相关
的少量节点参与到拓扑的维护中。所有这切使得致性哈希成为第个实的DHT算法。
但是致性哈希的路由算法尚有不之处。在查询过程中,查询消息要经过O(N)步
(O(N)表与N成正关系,N代表系统内的节点总数)才能到达被查询的节点。不难想象,当
系统规模常时,节点数量可能超过百万,这样的查询效率显然难以满使的需要。换
个度来看,即使户能够忍受漫的时延,查询过程中产的量消息也会给络带来不
必要的负荷。
3.内存/外存对于数据结构选择的影响?
内存指的就是主板上的存储部件,CPU直接与之沟通,并其存储数据的部件,存放当前正
在使的(即执中的)数据和程序,它的物理实质就是组或多组具备数据输输出和数
据存储功能的集成电路,内存只于暂时存放程序和数据,旦关闭电源或发断电,其中
的程序和数据就会丢失。外存包括软盘、硬盘和光盘,存放在其中的数据靠磁来维持,因此
可永久保存数据。
特点:内存处理速度快、存储容量、断电后信息丢失;外存处理速度慢、存储容量、信
息永久保存
4.R树在地图/打软件中的应和性能分析
数据结构
本质:Data Structure == ( Data Set, Pointer ) == (存储结构,指针)
定义:A particular way to organize data in the operation system to access
data efficiently.
内容:(1)数据的各种逻辑结构和物理结构,以及他们之间的相应关系
(2)并对每种结构定义相适应的各种运算
(3)设计出相应的算法 分析算法的效率
逻辑结构:线性(栈、队列) 线性(树、图)
数据的存储结构:线性连续的存储单元
数据操作的集合:查询、更新和聚集
什么是好的数据结构:(1) O(logn)时空复杂度 (2)合理的内存开销 (3)正确性
(4)易编程、易读
级数据结构
对于数据密集型(数据)的应,能够设计出种数据结构,让我们的算法有
很好的响应性
算法
定义:解题案的准确完整的描述,是系列解决问题的清晰指令,对系列
规范的输,在有序的时间内获得所要求的输出;有基本运算及规定的运算顺序
所构成的完整的解题步骤。按照要求设计好的有限的确切的计算序列,并且这样
的步骤和序列可以解决类问题。
内容:排序、分治法(divide and conquer)、随机算法、数据结构的算法、动
态规划、贪算法、图算法、数论算法
三.具体数据结构及关系
Skiplist 跳表
1.为什么选择跳表?
跳表是种随机化的数据结构,它的效率和红树以及 AVL 树不相上下,跳表的原理相当
简单,只要能熟练操作链表,就能轻松实现个 SkipList。
有序数组,如果数据量不断变化,有序数组很难能够效的进写。
链表是种最容易处理数据不断增加结构的有序数据结构,并且链表对于并发的持度是
常好的,然链表却不能够进分查找,因为法取到任意集的中值。
树,如平衡有序叉树。不过,论是AVL还是红树,这个预先找到中值并写到节点
的操作的都是常复杂的,对于复杂的操作来说,想使常的锁操作就乎不可能了。
所以,跳表是种满这样条件的很好的数据结构。
2.定义:
是种随机化数据结构,基于并联的链表,其效率可拟于叉查找树(对于多数操作需
要O(log n)平均时间)
跳跃列表是对有序的链表增加上附加的前进链接,增加是以随机化的式进的,所以在列
表中的查找可以快速的跳过部分列表。所有操作都以对数随机化的时间进O(logn)。
3.描述:
跳跃列表是按层建造的。底层是个普通的有序链表。每个更层都充当下列表的“快速
跑道”,这在层 i 中的元素按某个固定的概率 p (通常为0.5或0.25)出现在层 i+1 中。平均起
来,每个元素都在 1/(1-p) 个列表中出现,最层的元素(通常是在跳跃列表前端的个
特殊的头元素)在 O(log
1/p
n) 个列表中出现。
每个节点包含2个指针。个指向同层中下元素,另个指向下层元素。
要查找个标元素,起步于头元素和顶层列表,并沿着每个链表搜索,直到到达于或着
等于标的最后个元素。通过跟踪起标直到到达在更列表中出现的元素的反向查找
路径,在每个链表中预期的步数显易是 1/p。所以查找的总体代价是 O((log
1/p
n) / p),
当p 是常数时是 O(log n)。通过选择不同 p 值,就可以在查找代价和存储代价之间作出权
衡。
插时被插元素的层数也是随机化得到。
跳跃列表不像某些传统平衡树数据结构那样提供绝对的最坏情况性能保证,因为来建造跳
跃列表的扔硬币法(随机的)总有可能(尽管概率很)成个糟糕的不平衡结构。但是
在实际中它作的很好,随机化平衡案在平衡叉查找树中的确定性平衡案容易实
现。跳跃列表在并计算中也很有,这的插可以在跳跃列表不同的部分并的进,
不全局的数据结构重新平衡。
4.核思想:空间换取时间,在每个节点中增加向前的指针,提查找的效率
5.优点:
a)持范围查找
因为是有序结构,所以能够很好的持范围查找。截取中间集只需两次定位。耗时
2*log2n
b)能够随着数据的增动扩展。核数据结构是链表,可以很好的持数据的不断增
c)读写性好
因为从宏观上可以做到次排除半的数据,并且在写时也没有进其他额外的数据查找
剩余18页未读,继续阅读
ACMuscle
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- ExcelVBA中的Range和Cells用法说明.pdf
- 基于单片机的电梯控制模型设计.doc
- 主成分分析和因子分析.pptx
- 共享笔记服务系统论文.doc
- 基于数据治理体系的数据中台实践分享.pptx
- 变压器的铭牌和额定值.pptx
- 计算机网络课程设计报告--用winsock设计Ping应用程序.doc
- 高电压技术课件:第03章 液体和固体介质的电气特性.pdf
- Oracle商务智能精华介绍.pptx
- 基于单片机的输液滴速控制系统设计文档.doc
- dw考试题 5套.pdf
- 学生档案管理系统详细设计说明书.doc
- 操作系统PPT课件.pptx
- 智慧路边停车管理系统方案.pptx
- 【企业内控系列】企业内部控制之人力资源管理控制(17页).doc
- 温度传感器分类与特点.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论1