数据结构

　　数据结构（data structure），研究非数值性程序设计中计算机操作的对象以及它们之间的关系和运算等的学科。它的研究重点是数据的组织形式。了解数据组织形式的目的是为了使计算机对数据进行加工时，能针对各种（抽象的）数据结构采用相应的（物理的）存储结构和合适的算法等。抽象的数据结构包括串、数组、队、栈、表、树和有向图等。内部存储的物理结构包括向量、链表和丛等。数据结构的研究涉及到数据的编码理论、存取方法、数据元素在存储器中的分配等问题。

基本概念

　　在计算机科学中，所谓数据是指描述客观事物的数、字符以及所有能输入计算机中并被计算机的程序所处理的符号集合，它是计算机程序加工的原料。构成数据的基本单位是数据元素，具有相同特性的数据元素的集合称为数据对象，带有结构的（相互有联系的）数据元素的集合称为数据结构。

基本结构

　　①线性表（linear list）。最简单的数据结构。一个线性表是n个数据元素的有限序列。数据元素ai可以是一个数、一个符号、一页书或其他信息。当数据元素是一个记录时，则含有一定数量的记录的线性表就构成一个文件。可采用不同方式把线性表存储在计算机内。最简单、最常用的方式是用一组地址连续的存储单元依次地存储线性表的元素，称为线性表的顺序存储结构或顺序映象。这与程序设计语言中的向量（一维数组）的机内表示相同，它的特点是逻辑关系上相邻的两个元素在物理位置上也是相邻的。但也可用另一个指针来指出每个元素的物理位置，使逻辑关系上相邻的元素不一定在物理位置上也是相邻的。当线性表结构中的元素本身又是具有某种结构的数据时，这种线性表可称为数组（array）及列表（lists）。

　　②栈（stack）和队列（queue)。两种特殊的 、受一定限制的线性表。栈是只能在表尾进行插入和删除（所谓的“后进先出”）运算的线性表，队列是只能在表的一端插入而在另一端删除元素（所谓的“先进先出”）的线性表。

　　③串（string ）。零个或多个字符所组成的有限序列。字符在序列中的序号称为该字符在串中的位置。零个字符的串称为空串，串中任意个连续字符所组成的子序列称为该串的子串。当把一个串存储在机器中时，可用顺序的方式存储，也可用链式的方式存储。

　　④树（tree）。非线性的数据结构，其中尤以二叉树形结构最为常见。许多客观事物都可用树形结构进行描述，如生物的分类、社会组织的结构等。树是n（n≥0）个结点的有限集，在任一非空树中，有且仅有一个根（root）结点，其余结点可分为m（m≥0）个互不相交的有限集，它们是根的子树。如每个结点最多只有二棵子树，子树有左右之分、不可任意互换时，则称为二叉树（binary tree）。

　　当把一个树结构存储在计算机中时，可采用多种存储方式，最常用的是：双亲表示法以一组连续的存储空间存储树的各结点，在每个结点中设一个表示其双亲位置的指示器，以此来说明各结点间的关系；子女表示法，由于树中的每个结点可能有多棵子树，则对每个结点设多个指针，每个指针指向一棵子树的根结点；二叉树表示法，以二叉链表作树的存储结构，链表中的两个链域分别指向该结点的第一个子女结点和下一个兄弟结点。

　　⑤图（graph）。一种比线性表和树更为复杂的数据结构。在图形的数据结构中，结点之间的关系是任意的，任意两个数据元素之间都可能是相关的。根据图的结构的不同，还可分为有向图、无向图和网等。由于图的结构比较复杂，因此图在机器中的存储结构也较复杂，例如，图就没有顺序映象的存储结构，在一般情况下是用数组的数据类型来表示图的元素之间的关系的。

意义和用途

　　首先，了解数据组织形式的目的是为了当计算机对数据进行加工时，能够针对各种不同的抽象数据结构采用相应的物理存储结构和合适的算法等。其次由于程序设计＝算法＋数据结构＋程序设计方法学，所以要设计出一个好的程序，也必须深入研究数据的特性及数据组织间的关系。程序设计的实质是对确定的问题选择一种好的数据结构并设计一种好的算法。