张家界有没有做网站的公司,手机微信官方网站首页,建管家公司简介,做网站 怎么发布逻辑结构反映的是数据元素之间的关系#xff0c;它们与数据元素在计算机中的存储位置无关#xff0c;是数据结构在用户面前所呈现的形式。根据不同的逻辑结构来分#xff0c;数据结构可分为集合、线性结构、树形结构和图形结构4种形式#xff0c;接下来分别进行简要介绍。 …逻辑结构反映的是数据元素之间的关系它们与数据元素在计算机中的存储位置无关是数据结构在用户面前所呈现的形式。根据不同的逻辑结构来分数据结构可分为集合、线性结构、树形结构和图形结构4种形式接下来分别进行简要介绍。
1集合
在集合中数据元素都属于这个集合但数据元素之间并没有什么关系。它类似于数学中的集合如图所示。 集合
2线性结构
线性结构中的元素具有一对一的关系通过前一个结点可以找到后一个结点图1-1的学生信息表就是一个线性结构数据元素逐个排列。线性结构中前后两个结点互有联系。
线性结构分为顺序存储和链式存储两种。
顺序存储是由一段地址连续的空间来存储元素链式存储是由分散的单元空间来存储元素存储单元由指针相连接。简单的线性结构如图所示。
在线性结构中除头尾结点外可以通过前一个结点来寻找后一个结点也可以通过后一个结点来寻找前一个结点。
3树形结构
树形结构中数据元素之间存在一对多的层次关系。图1-4为一棵普通的树。除根结点外树形结构的每一个结点都必须有一个且只有一个前驱结点但可以有任意个后继结点。这些数据元素有自顶向下的层次关系。 4图形结构
图形结构中的数据元素存在多对多的关系每个结点的前驱和后继结点都可以是任意个如图1-5所示。 按照逻辑结构数据结构可以分为上述4种类型在后续的深入学习中本书会逐一详细讲解。
2.存储结构
数据结构除了按照逻辑结构来分还可以按照存储结构来分。
存储结构反映的是数据元素在计算机中的存储形式如何在计算机中正确地描述数据元素之间的逻辑关系才是数据结构的关键与重点。常用的存储结构有顺序存储结构、链式存储结构、索引存储结构和散列表4种接下来分别进行简要介绍。
1顺序存储结构
顺序存储结构是把逻辑上相邻的结点存储在地址连续的存储单元里数据元素之间的关系由存储单元是否相邻来体现。这种存储结构通常用高级语言上的数组来描述数据的逻辑关系与物理关系是一致的。以数组inta[5]{10020356266}为例其中的元素a[0]~a[4]在逻辑上是连续的在存储器中的物理地址也是连续的如图1-6所示。 使用顺序存储结构存储数据时系统为数据元素分配一段连续的地址空间。顺序存储结构可以提高空间利用率而且对于随机访问元素其效率非常高因为逻辑上相邻的数据元素其存储地址也是紧邻的所以可以按元素序号来快速查找到某一个元素。
但也正因如此如果要对顺序存储结构实现元素的插入和删除效率则非常低。因为如果要插入一个元素需要将这个位置之后的所有元素都向后移动一个位置同样如果要删除一个元素需要将这个位置之后的所有元素都向前移动一个位置。
顺序存储结构在使用时有空间限制当需要存取元素的个数多于预先分配的空间时会出现“溢出”问题当元素个数少于预先分配的空间时又会造成空间浪费。
2链式存储结构
链式存储结构在空间上是一些不连续的存储单元这些存储单元的逻辑关系通过附加的指针字段来表示例如C/C语言中的指针类型通过这些指针的指向来表明结点之间的联系。图1-3b为链式存储结构的示意图但在此图中没有标明指针的指向。在链式存储结构中可以有指向后继元素的指针字段也可以有指向前驱元素的指针字段如图1-7和图1-8所示。 这样在插入元素时不必移动任何一个元素高效简洁。同理当删除某一个元素时只需将其前后两个元素连接起来即可也无须移动其他元素。
但链式存储结构无法进行元素的随机访问。
对链式存储结构而言空间利用率也较低因为分配的内存单元有一部分被用来存储结点之间的逻辑关系。但链式存储在存储元素时没有空间限制顺序存储与链式存储都是按需分配只是链式存储可以在需要时方便地分配新空间不会造成空间不足或者浪费。
3索引存储结构
这种存储结构主要是为了方便查找数据它通常是在存储结点信息的同时还建立附加的索引表。索引表中的每一项称为索引项它由两个字段组成关键字与地址。其中关键字唯一标识一个结点地址是指向结点的指针。这种结构类似于人们常用的字典如图所示。 索引存储结构
这种索引表一个索引项对应一个结点叫作稠密索引。如果索引表中一个索引项对应一组结点叫作稀疏索引稀疏索引表如图1-11所示。 稀疏索引
索引表可以快速地对数据进行随机访问。又因为在进行数据的插入和删除时只需要更改索引表中的地址值不必移动结点所以在数据更改方面也具有较高的效率。但是索引存储结构在建立结点时会额外分配空间来建立一个索引表因此降低了空间利用率。
4散列存储结构
散列hash存储又称为哈希存储是一种力图将数据元素的存储位置与关键字之间建立确定对应关系的查找技术。它的基本思想是通过一定的函数关系散列函数也称为哈希函数计算出一个值将这个值作为元素的存储地址。
散列存储的访问速度是非常迅速的只要给出相应结点的关键字它会立即计算出该结点的存储地址。因此它是一种非常重要的存储方法。数据存储的几种方式各有其优点也各有其用途不能说哪一种存储结构就比另一种好。在使用时它们既可以单独使用也可以组合起来使用具体要根据操作和实际情况来决定采取哪一种方式或者哪几种方式结合使用。
