「数据结构」和「数据类型」两个概念的本质是什么,区别与联系是什么?

严蔚敏编著的《数据结构》教材对数据结构的定义: 相互之间存在一种或多种特定关系的数据元素的集合。有人说,数据结构就是用来存放有特定关系的数据的容器。 数据类型是数据的一种分类,是按照数据结构来分类的。数据类型的出现是为了把数据分成所需内存大小不同的数据。 还是不太明白,貌似数据结构中包含了数据类型,而数据类型又建立在数据结构之上? 那么数组到底是一种数据结构还是一种数据类型呢?是不是除了线性表、队列…
关注者
296
被浏览
28530

30 个回答

数据类型(data type) = 接口(interface) + 数据的表示(data representation)
数据表示有多种, 数据结构(data structural representation)的表示形式是其中一种.
Essential of Programming Languages, 3rd Edition (豆瓣) 第二章讲的应该就是这个了.

另外酷壳上的这篇 类型的本质和函数式实现 也相关.
感谢 Leo Ding毛自力 ,两位说的对我很有启发

我补充一下我的想法,还是延续 原子 和 分子 的比喻。
int char float double 这些是 数据类型 ,类比作原子,他们间的不同就是元素种类的不同,只涉及自身的不同,比如两种原子内的质子中子数不同,是一种内在属性。
链表 队列 堆栈 树 这些是数据结构,类比作分子,他们间描述的是数据间的关系,就如同分子描述了原子的组合方式,

/*
感谢 叶子童 的提醒,补充一下,如果觉得接下来的比喻不好理解,请依然按照 原子 和 分子 理解就行了
实际上,数据类型是一种 属性,数据结构是一种 关系,都很抽象,严格说起来,应该把数据类型比作元素种类,数据结构类比作化学式/分子式。但是这样没有起到比喻说理的效果,依然很抽象,所以依然选择 原子 和 分子 来说明(一般人想到原子应该都会觉得就像一个一个小球吧,这样就更易理解)。
*/

再说说只含有一个数据的链表/队列/堆栈/树,依据你给的定义:“相互之间存在一中或多种特定关系的数据元素的集合”,只含有一个数据甚至不含有数据也能算作一个“集合”;从实际结构上来说,一个链表只含有一个数据甚至不含数据,他还是会有指针域和表头,队列/堆栈等也一样,而这些部分就表现了“关系”。相反,单个int/char/float/double数据不含有这些表示关系的部分,所以不能算做一种特殊的 数据结构 。

最后,“数组”确实是一个令人头疼的概念,不过我觉得应该把他算作 数据结构 的一种。依然先从定义上来看,他确实描述了一种关系,只不过刚好描述的数据一个挨一个紧密排列的关系;从实际结构上来说,我和 陈岩 看法不同,单个char/int确实和数组一样内存上连续,但两个char间不一定是连续的,但数组中却一定是连续的,数组描述的正是这种紧密连续的 数据结构 数组在内存中储存时也有末尾的多余部分“\0”来描述“结束”这一关系。(关于 数组 ,一楼 狼大人 的叙述更精确)