数据结构与算法总论

说明：下面的文章小部分是参考了以前学校BBS上面的一篇文章，由于没有留下当时的出处，所以无法写下对这篇文章部分内容的原始作者，特此说明，并表示对他的感谢。

（一）何谓数据结构

数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。 数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。

数据结构主要研究什么？

数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。

什么是数据结构？什么是逻辑结构和物理结构？

数据是指由有限的符号（比如，"0"和"1"，具有其自己的结构、操作、和相应的语义）组成的元素的集合。结构是元素之间的关系的集合。通常来说，一个数据结构DS 可以表示为一个二元组：

…… 此处隐藏0字 ……

DS=(D,S), //i.e., data-structure=(data-part,logic-structure-part) 这里D是数据元素的集合（或者是“结点”，可能还含有“数据项”或“数据域”），S是定义在D（或其他集合）上的关系的集合，S = { R | R : D×D×...}，称之为元素的逻辑结构。逻辑结构有四种基本类型：集合结构、线性结构、树状结构和网络结构。表和树是最常用的两种高效数据结构，许多高效的算法可以用这两种数据结构来设计实现。表是线性结构的（全序关系），树(偏序或层次关系)和图（局部有序(weak/local orders)）是非线性结构。

数据结构的物理结构是指逻辑结构的存储镜像(image)。数据结构 DS 的物理结构 P对应于从 DS 的数据元素到存储区M（维护着逻辑结构S）的一个映射： P(D,S) -- > M 存储器模型：一个存储器 M 是一系列固定大小的存储单元，每个单元 U 有一个唯一的地址 A(U)，该地址被连续地编码。每个单元 U 有一个唯一的后继单元 U'=succ(U)。 P 的四种基本映射模型：顺序（sequential）、链接（linked）、索引（indexed）和散列（hashing）映射。

因此，我们至少可以得到4×4种可能的物理数据结构：

sequential (sets)

linked lists

indexed trees

hash graphs

（并不是所有的可能组合都合理）数据结构DS上的操作：所有的定义在DS