IT Notes‎ > ‎

Data Structure

数据结构(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

数据结构中的“树”,和自然界中的树的结构是类似的。自然界中的树,有主干,主干上又有分支或树叶,分支上又有分支或树叶。数据结构中的“树”可以如此定义:

  1. 节点可以子节点,也可以没有
  2. 有一个节点只有子节点,他就是所谓的“根节点”,在一棵树中,有且只有一个“根节点”。
  3. 某些节点,没有子节点,它们就是所谓的“叶子节点”,在一棵树中,叶子节点个数是不确定的。

在 C 语言中,节点之间的关系用指针来完成。但在 Java 中,TODO。具体细分下来,树有很多种类:

  1. 二叉树:每个节点最多只有两个子节点的树。
  2. 最优二叉树(?TODO 是这个名字?)
  3. 哈夫曼树

等等,以上的树需要补全一下。

图状 Graph

集合 Set

资源

Subpages (5): array linked list list queue stack
Comments