数据结构中逻辑结构和存储结构对应有哪些

逻辑结构数据之间的抽象关系 存储结构这些关系在计算机内存中的具体实现方式 数据结构一、逻辑结构完整分类注集合结构有时单独列出有时归入非线性结构。类别子类型典型例子线性结构一般线性表顺序表、链表受限线性表栈、队列推广线性表串字符线性表非线性结构树形结构二叉树、二叉搜索树、堆、B树图形结构有向图、无向图集合结构哈希表逻辑上可视为集合、并查集集合数据元素间无特定关系属于同一集合。线性结构一对一关系如线性表、栈、队列。树形结构一对多关系如树、堆。图形结构多对多关系如有向图、无向图。二、存储结构计算机中的实现方式主要有四种基本方式可组合使用存储结构核心特点对应的逻辑结构示例顺序存储用连续内存单元存储逻辑相邻→物理相邻线性结构数组、栈、队列、完全二叉树堆链式存储用附加指针连接结点不要求物理连续线性表链表、树二叉链表、图邻接表索引存储建立索引表通过索引项访问数据线性结构索引顺序表、树B树等哈希存储通过哈希函数直接计算存储地址集合、线性结构哈希表“逻辑上相邻物理上不一定相邻”顺序存储逻辑相邻 → 物理相邻链式存储逻辑相邻 → 物理不一定相邻靠指针“存储密度”对比顺序存储存储密度 ≈ 1几乎没有额外开销链式存储存储密度 1每个节点多一个/多个指针三、逻辑结构与存储结构的完整对应表逻辑结构常用存储结构组合线性表顺序存储顺序表链式存储单/双/循环链表索引存储索引顺序表栈顺序存储顺序栈链式存储链栈队列顺序存储循环队列链式存储链队列串顺序存储定长/堆分配链式存储块链树 / 二叉树顺序存储完全二叉树/堆链式存储二叉/三叉链表索引存储B/B树图顺序存储邻接矩阵链式存储邻接表、十字链表索引/散列边集数组索引集合哈希表散列存储 顺序/链式处理冲突四、逻辑结构的“操作特性”与存储结构的“实现约束”不能只看对应关系还要看约束逻辑结构隐含的操作特性存储结构带来的限制栈后进先出LIFO顺序栈有最大容量限制链栈无容量上限但需要额外指针空间队列先进先出FIFO顺序队列容易“假溢出”所以常用循环队列链队列则无此问题树二叉树父子关系、层次遍历顺序存储只适合完全二叉树普通二叉树会浪费大量空间图任意顶点间可达邻接矩阵适合稠密图邻接表适合稀疏图关键点逻辑结构定义“能做什么”存储结构决定“做得好不好”时间/空间代价。五、不同存储结构的对比存储结构优点缺点顺序存储随机访问快O(1)、空间利用率高无指针开销插入/删除慢需移动元素、需预先分配连续空间链式存储插入/删除快O(1) 已知位置、动态扩展随机访问慢O(n)、额外指针占用空间索引存储查找较快、支持范围查询维护索引有额外开销、索引本身也占空间散列存储查找极快O(1) 平均不支持顺序遍历、存在冲突问题、空间利用率不稳定复杂度对比同一逻辑结构不同存储结构逻辑结构存储结构访问第i个插入/删除已知位置查找按值空间占用线性表顺序表O(1)O(n)O(n)较省线性表链表O(n)O(1)O(n)额外指针栈顺序栈O(1)仅栈顶O(1)—固定容量栈链栈O(1)仅栈顶O(1)—动态扩展队列循环队列O(1)仅队首/队尾O(1)—可能假溢出队列链队列O(1)仅队首/队尾O(1)—无假溢出六、容易被忽略的“混合存储结构”实际中很多数据结构是混合使用多种存储方式的数据结构实际存储方式混合成分哈希表拉链法散列存储 链式存储数组顺序 链表链式B树索引存储 顺序存储多级索引 叶子节点顺序链表邻接表图顺序存储 链式存储顶点数组顺序 边链表链式跳表链式存储 索引存储多级链表 前进指针类似索引结论不要认为一个数据结构只用一种存储方式组合往往更强大。