sponsored links

数据结构、逻辑结构、存储结构辨析

数据结构=逻辑结构(线性、非线性)+存储结构(顺序、链式、索引、散列) 

1)逻辑结构:数据元素间抽象化的相互关系

2)存储结构:(物理结构),在计算机存储器中的存储形式

逻辑结构的分类:

1.按逻辑结构分为:(线性结构+非线性结构)

2.逻辑结构的四种基本形态:

1)数据元素间没有任何关系——集合

2)数据元素间有线性关系——线性结构(所谓线性关系:除第一个元素外,其他元素有且只有一个前驱;除最后一个元素外,其他元素有且只有一个后继!)

3)数据元素间有层次关系——树结构

4)数据元素间有网状关系——图结构

常用的线性结构:线性表、栈、队列、双队列、数组、串 
常用的非线性结构:二维数组、多维数组、树(二叉树等)、图、广义表 
存储结构分类: 
1.顺序存储结构:把逻辑上相邻的节点存储在物理位置上相邻的存储单元中,结点之间的逻辑关系由存储单元的邻接关系来体现。 
优点:可实现对结点的随机存取 
缺点:不便于修改,对结点的插入、删除运算时,可能要移动一系列的结点,效率较低 
2.链式存储结构:把逻辑上相邻的节点存储在物理位置上相邻的存储单元中,结点之间的逻辑关系由存储单元的邻接关系来体现。 
优点:比顺序存储结构的存储密度小,逻辑上相邻的节点物理上不必相邻,插入、删除灵活 (不必移动节点,只要改变节点中的指针) 
缺点:查找结点时链式存储要比顺序存储慢 
3.索引存储:除建立存储结点信息外,还建立附加的索引表来标识结点的地址。 
4.散列存储:根据结点的关键字直接计算出该结点的存储地址。

Tags: