18个高级数据结构整理归纳_高级数据结构资源-CSDN文库

数据结构

3星 · 超过75%的资源需积分: 49 152 浏览量 2015-06-17 17:14:09 上传评论 10 收藏 1.79MB PDF 举报

资源推荐

资源详情

资源评论

DataStructureDataStructure

.数据结构的基本问题

数据在计算机系统中的表和组织，但是有约束

内存结构：叉树-平衡-近似平衡-不平衡优化时间

外存结构：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树在地图/打软件中的应和性能分析

有序数组，如果数据量不断变化，有序数组很难能够效的进写。
链表是种最容易处理数据不断增加结构的有序数据结构，并且链表对于并发的持度是
常好的，然链表却不能够进分查找，因为法取到任意集的中值。
树，如平衡有序叉树。不过，论是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)读写性好
          因为从宏观上可以做到次排除半的数据，并且在写时也没有进其他额外的数据查找