第五话:数据的物理结构

顺序存储与链式存储
服务器君一共花费了284.216 ms进行了6次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议
  • 数据除了有前面说的逻辑结构,还分为物理结构。那么这个物理结构又是什么回事呢?
  • 物理结构在很多书中也叫做存储结构,不过你只要在理解上把它们当一回事就可以了。

物理结构:是指数据的逻辑结构在计算机中的存储形式。

数据是数据元素的集合,那么根据物理结构的定义,实际上就是如何把数据元素存储到计算机的存储器中。存储器主要是针对内存而言的,像硬盘、软盘、光盘等外部存储器的数据组织通常用文件结构来描述。

数据的存储结构应正确反映数据元素之间的逻辑关系,这才是最为关键的,如何存储数据元素之间的逻辑关系,是实现物理结构的重点和难点。

数据元素的存储结构形式有两种:顺序存储和链式存储。

1. 顺序存储结构

顺序存储结构:是把数据元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的。

  • 这种存储结构其实很简单,说白了,就是排队占位。大家都按顺序排好,每个人占一小段空间,大家谁也别插谁的队。我们之前学计算机语言时,数组就是这样的顺序存储结构。当你告诉计算机,你要建立一个有9个整型数据的数组时,计算机就在内存中找了片空地,按照一个整型所占位置的大小乘以9,开辟一段连续的空间,于是第一个数组数据就放在第一个位置,第二个数据放在第二个,这样依次摆放。

2. 链式存储结构

  • 如果就是这么简单和有规律,一切就好办了。可实际上,总会有人插队,也会有人要上厕所、有人会放弃排队。所以这个队伍当中会添加新成员,也有可能会去掉老元素,整个结构时刻都处于变化中。显然,面对这样时常要变化的结构,顺序存储是不科学的。那怎么办呢?

现在如银行、医院等地方,设置了排队系统,也就是每个人去了,先领一个号,等着叫号,叫到时去办理业务或看病。在等待的时候,你爱在哪在哪,可以坐着、站着或者走动,甚至出去逛一圈,只要及时回来就行。你关注的是前一个号有没有被叫到,叫到了,下一个就轮到了。

链式存储结构:是把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的。数据元素的存储关系并不能反映其逻辑关系,因此需要用一个指针存放数据元素的地址,这样通过地址就可以找到相关联数据元素的位置。

  • 显然,链式存储就灵活多了,数据存在哪里不重要,只要有一个指针存放了相应的地址就能找到它了。
  • 前几年香港有部电影叫《无间道》,大陆还有部电视剧叫《潜伏》,都很火。大致说的是,某一方潜伏在敌人的内部,进行一些情报收集工作。为了不暴露每个潜伏人员的真实身份,往往都是单线联系,只有上线知道下线是谁,并且是通过暗号来联络。正常情况下,情报是可以顺利地上传下达的,但是如果某个链条中结点的同志牺牲了,那就麻烦了,因为其他人不知道上线或者下线是谁, 后果就很严重。比如在《无间道》中,梁朝伟是警方在黑社会中的卧底,一直是与黄秋生扮演的警官联络,可当黄遇害后,梁就无法证明自己是一个替察。所以影片的结尾,当梁朝伟用枪指着刘德华的头说,“对不起,我是替察。”刘德华马上反问道:“谁知道呢?”是呀,当没有人可以证明你身份的时候,谁知道你是谁呢?影片看到这里,多少让人有些唏嘘感慨。这其实就是链式关系的一个现实样例。

逻辑结构是面向问题的,而物理结构就是面向计算机的,其基本的目标就是将数据及其逻辑关系存储到计算机的内存中。

延伸阅读

此文章所在专题列表如下:

  1. 第一话:你的数据结构怎么学的?
  2. 第二话:数据结构的历史与来由
  3. 第三话:关于数据结构的一些概念
  4. 第四话:数据的逻辑结构
  5. 第五话:数据的物理结构
  6. 第六话:关于数据类型
  7. 第七话:抽象数据类型ADT
  8. 第八话:补充数据结构基本概念的关系
  9. 第九话:数据结构与算法的关系
  10. 第10话:什么是算法?
  11. 第11话:算法的五个基本特征
  12. 第12话:什么样的算法才是好算法
  13. 第13话:算法的性能分析
  14. 第14话:如何计算算法的时间复杂度
  15. 第15话:算法的最坏情况与平均情况
  16. 第16话:算法的空间复杂度

本文地址:http://www.nowamagic.net/librarys/veda/detail/2178,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2178

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《php和mysql web开发(原书第4版)》 Luke Welling (作者), Laura Thomson (作者), 武欣 (译者)

《php和mysql web开发(原书第4版)》将PHP开发与MySQL应用相结合,分别对PHP和MySQL做了深入浅出的分析,不仅介绍PHP和MySQL的一般概念,而且对PHP和MySQL的Web应用做了较全面的阐述,并包括几个经典且实用的例子。《php和mysql web开发(原书第4版)》是第4版,经过了全面的更新、重写和扩展,包括PHP 5.3最新改进的特性(例如,更好的错误和异常处理),MySQL的存储过程和存储引擎,Ajax技术与Web 2.0以及Web应用需要注意的安全问题。

更多计算机宝库...