数据结构与数据类型相信我们并不陌生,在日常开发中天天都能接触到,但如果要让你解释一下它们的本质区别和联系,你是否能准确的描述呢?
为了便于更加清晰的理解概念,我们应该先理解每一个简单的术语,然后在去理解它们组合后的术语意义。
数据是指未经过处理的原始记录,是关于事件之一组离散且客观的事实描述,是构成消息和知识的原始材料。一般而言,数据缺乏组织及分类,无法明确的表达事物代表的意义,它可能是一堆的杂志、一大叠的报纸、数种的开会记录或是整本病人的病历纪录。
结构是指在一个系统或者材料之中,互相关联的元素的排列、组织。结构按类别可分为等级结构(有层次地排列,由上至下,一对多)、网络结构(多对多)、晶格结构(临近的个体互相连接)等。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合,简单的说是计算机中存储、组织数据的方式。其包括逻辑结构和物理结构。
逻辑结构是指数据元素之间的逻辑关系,独立于数据在计算机的存储方式,数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
逻辑结构又分为:
线性结构:(有且只有一个开始结点和一个终端结点,并且所有结点都最多只有一个直接前驱和一个直接后继)。线性结构典型的包括数组,链表,栈和队列。
非线性结构:(对应于线性结构,非线性结构也就是每个结点可以有不止一个直接前驱和直接后继)。非线性结构包括集合(集合结构中的数据元素之间除了“同属于一个集合”的关系外,别无其他关系。类似于数学上的集合),图,树。
存储结构是指数据结构在计算机中的表示(又称映像),也称物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是逻辑结构用计算机语言的实现,它依赖于计算机语言。数据的存储结构主要有:顺序存储、链式存储、索引存储和散列存储。注意具体的实现存储的时候,可以选择在内存里面开辟连续内存空间或者不连续的内存空间来进行存储。当然也可以混搭组成更复杂的存储方式。
顺序存储:存储的物理位置通常情况是连续分布的
链接存储:存储的物理位置未必连续,看实现方式,通过记录相邻元素的物理位置来找到相邻元素。
索引存储:类似于树状目录,存储形式看实现方式
散列存储:通过关键字直接计算出元素的物理地址。存储形式看实现方式
数据类型是一个值的集合和定义在此集合上一组操作(通常是增删改查或者操作读写的方法)的总称。
其中数据类型,总的来说又分:
原子类型:比如编程语言的int,double,char,byte,boolean。
复合类型:又称结构类型,通过原子类型封装的更复杂的类型,比如面向对象语言里面的类。
另外还有一种更高层级的类型称为抽象数据类型:是指抽象数据组织和与之相关的操作。 抽象数据类型(ADT)是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性,而与其在计算机内部如何表示和实现无关。即无论其内部结构如何变化,只要它的数学特性不变,都不影响其外部的使用。”抽象“的意义在于数据类型的数学抽象特性。
即无论其内部结构如何变化,只要它的数学特性不变,都不影响其外部的使用。”抽象“的意义在于数据类型的数学抽象特性
数据类型和数据结构之间的关系如下:
本文主要介绍了计算机科学领域一些基本的术语概念,在开发程序时如何选择一个合适的数据结构和高效的算法其实是非常重要的,这直接会影响到我们程序的性能,尤其是在面对数据集巨大的情况下,了解这些数据结构的概念,执行原理和底层实现对我们开发程序和调优程序是非常有帮助的,也是每一位优秀程序员进阶的必经之路。