数据结构(Data Structure),数据的依其组织方式所具有的一种结构。计算机程序离不开数据结构,严蔚敏的《数据结构》教材中提到,Niklaus Wirth 曾说过:
Algorithm + Data Structures = Programs
它还和算法密切相关,对算法效率有很大影响。
数据结构本身是独立于具体的编程语言的,但所有的编程语言都实现了一些数据结构,比如数组,以及 Java 中的集合等等。
描述数据结构,往往需要借助 ADT (抽象数据类型,Abastract Data Type),它一个由数据项和相关操作组成的集合。数据项是数据结构中处理的最小单位。ADT 只有定义,没有具体实现。各种数据结构都将通过 ADT 来描述。(参dads的资源)。
集合
这算是没有结构的结构吧。一般以 bag (An unordered collection of values that may have duplicates,参这里) 来表示可重集合,用 set 表示符合数学含义的集合。
线性 Line
线性的数据结构,包含 array, stack, queue, list(linked list, doubly linked list, circular list, self-organizing list, ordered linked list) 等。
树形 Tree
数据结构中的“树”,和自然界中的树的结构是类似的。自然界中的树,有主干,主干上又有分支或树叶,分支上又有分支或树叶。数据结构中的“树”可以如此定义:
在 C 语言中,节点之间的关系用指针来完成。但在 Java 中,TODO。具体细分下来,树有很多种类:
等等,以上的树需要补全一下。
图状 Graph
集合 Set