1、数据结构

数据结构是一种计算机科学技术领域广泛使用的专业术语,在很多书籍以及博客中,对数据结构的解释为数据在计算机的存储方式,很容易让人误以为数据结构只是一种数据的物理存储方式,其实不然,数据结构可以理解为:数据 + 结构数据是描述客观事物的符号,为程序操控,存储在计算机上,结构包括数据的逻辑结构和存储结构。

2、数据的逻辑结构

数据元素间抽象化的相互关系,与数据的存储无关,独立于计算机,但逻辑结构决定元素的输入、存储、发送、处理和信息传递的基本操作功能。逻辑结构有四种基本类型:集合结构、线性结构、树形结构和图形结构表和树是最常用的两种高效数据结构,许多高效的算法能够用这两种数据结构来设计实现

2.1、主要分为以下这几种类型

  • 集合结构

    由若干元素集合在一起形成的团聚体(或称集合体)相互堆积起来的一种结构类型,数据元素之间无其他的关系,仅仅属于同一集合体而已。

 

  • 线性结构

    数据元素之间存在一一对应的关系,其开始节点和终端节点具有唯一性,除了开始开始节点和终端节点,其他的元素有且仅有一个前驱节点和后继节点,线性表就是一个典型。

 

  • 树形结构

  • 数据元素之间存在着一一对应的关系,每一个数据元素只有一个前驱节点,但是却又很多后继节点 终端节点可以有多个。二叉树就是一个典型。

 

  • 图形结构

  • 又称为非线性结构,数据元素之间存在着多对多的关系,其前驱节点和后继节点的个数可以是任意多个

注:四种逻辑结构存在着关系:树形结构是图形结构的特殊形式,而线性结构又是树形结构的特殊形式。

3、数据的存储结构

存储结构描述了数据在计算机内部的存储安排

3.1、顺序存储结构

把逻辑上相邻的数据存储在物理位置上相邻的存储单位里,用物理位置上的相邻来体现逻辑上的相邻,此种存储结构的又在于节省了存储空间,因为分配给数据的存储单元完全用于了数据的存储,数据之间的逻辑关系没有占用存储空间,可以实现对数据的随机存取,每个节点对应一个序号,由这个序号可以计算出数据的存储地址,缺点在于不变于数据的修改,对数据的插入和删除可能要移动一系列的数据。

3.2、链式存储结构

逻辑上相邻的两个数据元素不一定在物理位置上也要相邻,数据元素之间的相邻是用添加的指针来标识的,优点在于由于不要求在物理上的相邻,所以在进行插入,删除等时,只需要改变相邻节点的指针域,不必移动数据的位置,相对于顺序结构,链式的缺点在于存储空间利用率太低,因为存储数据的一部分单元用于了存储数据之间的逻辑关系,由于相邻的节点在物理位置上不一定相邻,所以不能进行随机存在。

3.3、索引存储结构

该结构在存储数据元素的同时,还建立了一个附加的索引表,索引表中的每一项称为索引项(关键字,地址),关键字唯一标识一个数据元素 ,地址是指向数据元素的指针,采用了索引的存储结构可以所及存取数据元素,在进行插入,删除等时,只需要移动相应索引表中的地址,不必移动数据,故而大大提高了数据的查找速度,缺点在于添加了索引表,降低了存储空间的利用率

3.4、散列(哈希)存储结构

就是根据数据元素的关键字通过哈希函数计算出一个数值用做数据元素的存储地址,优点在于查找速度快,只需要给出关键字可立即计算出该数据元素的地址 特点是指存储数据元素不存储数据之间的逻辑关系,只适合进行快速查找和插入的场合

 

也就是说可以用PHP的数组来实现一个B树或者别的数据结构的

参考

什么是数据结构

php实现B树

By cc

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注