深入理解编程与数据结构

－1－

在计算机科学中，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。

对于存储程序结构的计算机，对于数据的运算或操作（如检索、插入、删除、更新、排序），数据如何存储，直接关系到执行能否有效地完成；实际的内存物理结构是，地址：值；对于程序的编码，则是变量：值；（内存与变量的关系）。同时，数据元素之间本身的逻辑关系也是不容忽视的。编程对于数据的处理，让数据变得更有规律可循，或都说通过数据的合理存储让数据更加结构化，选择合适的算法并让算法得以高效实现，这是数学建模和编程的核心内容。

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

数据结构是一切算法的基础，也是程序设计的基础。其重要的操作是存取的问题。正是由于对数据结构的深入理解，才导致多种多样的程序设计语言的诞生。

合理的数据结构能够提高算法的执行效率，还可以提高数据的存储效率。

数据结构一是指相互之间存在某种特定关系的数据的集合；二是指数据之间的相互关系，也就是数据之间的逻辑结构。因此，当我们说定义数据结构时，除了定义数据之间的相互关系，还包括根据这些关系组织在一起的数据。在建立数据模型的阶段，我们说的数据结构更偏重于定义数据之间的相互关系；设计具体的算法步骤时，考虑的是如何对构建在这些数据关系之上的实际数据进行加工和处理。

数据之间的逻辑结构包括线性结构和关联结构（集合、映射）、树形结构和图形结构，对于简单的问题，应用这些基于数据结构就可以解决问题——但对于复杂的算法，往往需要将这些基本的数据结构组合起来形成更复杂的逻辑结构。

掌握数据结构需要注意两个方面：

I 复杂数据结构的构造和实现原理；

II 数据结构的特性和对外接口。

－2－了解数据结构的7个要点（寻找内存地址或变量名称的规律性）

2.1 了解内存和变量的关系；

2.2 了解作为数据结构基础的数组；

2.3 了解数组的应用：作为典型算法的数据结构；

2.4 了解并掌握典型数据结构的类型和概念；

2.5 了解栈和队列的实现方法；

2.6 了解结构体的组成；

2.7 了解链表和二叉树的实现方法；

-3-数据结构的内容

• 逻辑结构：数据元素之间的逻辑关系；

• 存储结构：是逻辑结构在存储器中的表现形式；

• 数据运算：每种逻辑结构都可以归纳一个运算的集合，包括检索、插入、删除、更新、排序；

• 同一个逻辑结构可以有不同的存储结构；

• 同一种逻辑结构可以有不同的数据运算集合；

• 一个相同的逻辑结构和存储结构，而采用不同的去处集合及运算性质，将导致全新的数据结果。如线性表，如果将线性表的插入运算限制在表的一端，而删除操作限定在表的另一端，那么这种数据结构就是队列；如果将线性表的插入和删除操作都在表的同一段，那么这种数据结构就叫栈。

数据结构具体指同一类数据元素中，各元素之间的相互关系，数据的逻辑结构、数据的存储结构和数据运算结构是其主要的三个组成成分。

3.1 数据的逻辑结构：数据元素之间的逻辑关系，与数据在计算机中是如何存储无关的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。其中的逻辑关系是指数据元素之间的前后关系，而与他们在计算机中的存储位置无关。逻辑结构包括：

线性表中的数据元素之间并没有关系，只是通过不同的组织和管理方式将每个数据元素维护在一个线性表中，而表、图等复杂数据结构的每个数据元素之间也可能存在关系，如树的节点之间存在的父子关系，图的节点之间之间存在邻接关系。之所以称之为“复杂数据结构”，是因为相应的插入、删除操作不仅对数据元素进行操作，还要同时维护数据元素之间的关系。

3.1.1 线性结构：是表中各个结点具有线性关系。

线性表是数据结构中最简单的基本数据结构，线性表的使用和维护都很简单。这一特点使其成为很多算法的基础。数组、链表、栈和队列是四种最常见的线性表，其外部行为和内部接口都各有特色。

I 有且仅有一个开始结点和一个终端结点;

II 所有结点最多只有一个直接前趋结点和一个直接后继结点;

线性表，栈，队列，双队列，数组，串。

3.1.2 非线性结构，也线性结构刚好相对，二维数组，多维数组，广义表，树(二叉树等)，图。

3.1.3 具体可以分为：

• 集合

• 线性结构

• 树形结构

• 图形结构

3.2 数据的物理结构：也就是数据元素及其逻辑关系在计算机存储器中的表示形式。数据的存储结构依赖于计算机语言，是逻辑结构用计算机语言的实现。

3.2.1 数据结构的几种存储方式

I 每个结点按顺序依次存储在一片连续的存储单元中；

II 每个结存存储在分散的空间而使用引用将这些结点链接起来；

3.2.2 具体可以分为：

I 顺序Sequential Storage Structure，数组，在一块连续的存储区域一个接一个地存储数据；

II 链接Linked，不要求逻辑上相邻的结点在物理位置上相邻，结点间的逻辑关系由附加的字段表示，一个结点的引用字段往往指向下一个结点的存放位置；

III 索引Index，是采用附加的索引表的方式来存储结点信息，索引表由若干索引项（关键字、地址）组成；

IV 散列Hash，根据结点的关键字直接算出该结点的存储点；其思想是如果在结构中存在关键字和T相等的记录，那么就必定在F(T)的存储中以找到该刻录

3.3 数据结构的运算：也就是能够对数据施加的操作。数据的运算其基础在于数据的逻辑结构上，每种逻辑结构都可以归纳一个运算的操作。在数据结构范畴内，最常用的运算包括检索、插入、删除、更新、排序等。

-4- 逻辑、储存、运算三者的关系

同一个逻辑结构可以有不同的存储结构。

线性表是一种简单的逻辑结构，可以考虑三种方式的存储

• 线性表采用顺序方式存储，这种数据结构就是顺序表；

• 线性表采用链式方式存储，这种数据结构就是链表；

• 线性表采用散列方式存储，这种数据结构就是散列表；

一个相同的数据逻辑结构和存储结构，而采用不同的运算集合及运算性质，将导致全新的数据结构。例如线性表，如果将线性表的插入运算限制在表的一段，而删除操作限制在表的另一端，那么这种数据结构就是队列；如果将线性表的插入和删除操作都限制在表的同一段，那么这种数据结构就是栈。

数据结构中的这三个方面是一个有机的整体，缺一不可。数据的逻辑结构、数据的存储结构和数据的运算任何一个发生变化都将导致一个全新的数据结构出现。

同一种逻辑结构也可以有不同的数据运算集合

-5-线性表的两种存储方式

线性表Linear List：从逻辑上来看，线性表就是由n个数据元素组成的有限序列。

在计算机中线性表可以采用两种方法来保存，一种是顺序存储结构，另一种是链式存储结构。对于顺序存储结构的线性表称为顺序表，而链式存储的线性表称为链表。

顺序表结构的存储方式有如下一些缺点：

在插入元素和删除元素时（尤其不在尾部时），会移动大量的元素，造成性能和效率低下。

• 顺序表的长度是固定的，如果超出分配的长度就会造成溢出，如果存放的数据太少则会造成空间浪费。如果表比较大，有时比较难分配足够的连续存储空间，往往导致内存分配失败，而无法存储。

为了克服以上顺序表结构的缺点，我们可以采用链表结构。链表结构是一种动态存储分配的结构形式，可以根据需要动态申请所需的内存单元。

从上图可以看出，单链表中的每个结点都包含一个“数据域”和一个“指针域”。“数据域”中包含当前结点的数据，“指针域”包含下一节点的存储地址，头指针head是指向开始结点的，结束结点没有后继结点，所以结束结点的指针域为空，即null。

典型的链表结构的每个结点都应该包括如下两个部分：

• 数据部分，保存的是该结点的实际数据；

• 地址部分，保存的是下一个结点的地址。

链表结构就是由许多这种结点构成的。在进行逻表操作时，首先需要定义一个“头引用”变量（一般以head表示），该引用变量指向链表结构的第一个结点，第一个结点的地址部分又指向第二个结点…，直到最后一个结点。最后一个结点不再指向其他结点，称为“表尾”，一般在表尾的地址部分放一个空地址“null“”，链表到此结束。

由于这里采用引用来指示下一个数据的地址。因此在链表结构中，逻辑上相信的结点在内存中并不一定相邻，逻辑相邻关系通过地址部分的引用变量来实现。

链表结构的缺点就是浪费存储空间，对于每个节点数据都需要额外保存一个引用变量。

对于链表的访问只能从表头逐个比较一直到找到需要的结点为止，而不能像顺序表那样进行随机访问。

链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性数据结构。

-7-

常用数据结构

7.1 数组 (Array)

在程序设计中，为了处理方便，把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。在C语言中， 数组属于构造数据类型。一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同，数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。

数组是数据结构的基础，因为在实际应用的程序中经常需要处理大量的数据，所以通过使用数组，可以一次性定义多个变量，可以提高编写程序的效率，可以高效地编写出能够实现排序等算法的程序。

说数组是数据结构的基础，是因为数组反映了内存的物理结构，在内存存储数据的空间是连续分布的。而在程序中，往往要从内存整体中分配出一块连续的空间供使用。如果用程序中的语句表示这种分配使用方式的话，就用到了数组。（《计算机是怎样跑起来的》（矢泽久雄））

数组是一种直接利用内存物理结构（计算机特性）的最基本的数据结构。只需要使用for语句，就可以连续地处理数组中所存储的数据，实现各种各样的算法。

数组是一种相对比较简单的数据组织关系，所有数据元素存储在一片连续的区域内，对数组的访问方式一般是通过下标直接访问数组元素，除此之外，对数组的基本操作还有插入、删除和查找，数组元素直接访问几乎没有开销，但是插入和删除操作需要移动数组元素，开销比较大。因此在插入和删除操作比较频繁的场合下，不适合使用数组。在数组中查找一个元素的时间复杂度是O(n)，如果数组元素是有序存储的，则使用二分查找可能将时间复杂度降为O(lgn)。

7.2 栈 (Stack)

是只能在某一端插入和删除的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。它有很多应用场景，比如食堂中的一叠盘子，我们只能从顶端一个一个地取。

Stack:在计算机程序设计中，特别是汇编程序中，栈通常用于中断或子程序调用过程，此时，首先将重要的寄存器或变量压入栈，然后进入中断例程或子程序，处理完后，通过栈操作恢复寄存器和变量的值；基本操作：入栈Push和出栈pop;

栈是一种特殊的纯属表，其特殊性在于只能在表的一端插入和删除数组元素；插入和删除动作分别被称为“入栈”和“出栈”。严格来说，栈不是一种数据存储方式，而是一种逻辑管理方式，它遵循“后进先出”（Last In First Out）的原则管理和维护表中的数据。栈的数据存储方式可以是数组，也可以使用链表，分别被称为“顺序栈”和“链式栈”，但是无论采用何种存储方式，其行为都是一样的，即只能通过“出栈”和“入栈”的方式在数据表的一端操作数据。

栈是一种非常有用的数据结构，利用栈的一些特性，可以将算法的递归实现转换成非递归袖，在使用穷尽搜索方法时，也会使用栈保存当前的状态。有时候，广度优先搜索和深度优先搜索的差异仅仅是使用栈还是使用队列；

7.3 队列 (Queue)

队列也是一种特殊的线性表，是一种操作受限的线性表。普通队列只能在表的一端插入数据，在另一端删除数据，不能在队列的其他位置插入和删除数据。插入和删除动作分别被称为“入队”和“出队”，能执行“入队”的一端称为“后端”（rear），能执行“出队”的一端称为“前端”（front）,与栈一样，队列也不是一种数据存储方式，而是一种逻辑管理方式，它遵循“先进先出”（First In First Out）的原则管理和维护表中的数据，队列的数据存储方式可以采用数组，也可以使用链表。 对于队列，与现实生活中的排队类似，新加入的成员总是在队尾，而排在队列最前面的总是最先离开队列，即先进先出，因此队列也称为先进先出表(FIFO)。

7.4 链表 (Linked List)

是一种物理存储单元上非连续、非顺序的存储结构，它既可以表示线性结构，也可以用于表示非线性结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

在线性表长度不能确定的场合，一般会采用链表的形式。链表结构的每一个节点都由两个域组成，一个是存放实际数据元素的数据域，另一个就是构成链式结构的指针域。对于单式链表而言，指针域只有一个后向指针，对于双向链表，指针域由一个后向指针和一个前向指针组成。链表的插入和删除只需要修改指针域的指针指向即可完成。比数组的插入和删除操作效率高，但是访问数据元素的效率比较低，需要从链表头部向后（或向前）搜索，查找操作的时间复杂度是O(n)。链表长度可动态变化这一点，比数组具有更大的优势。

除了查找和访问效率没有数组高之外，链表的每个节点都要额外存储一个指针域，因此，需要一定的存储开销，对于一些插入和删除操作比较少，查找、遍历操作比较多的场合，应该优先选择使用可变数组代替链表。

7.5 树 (Tree)

有些问题无法抽象为线性数据结构，如一个国家的行政机构、一个家庭的家谱等。这些问题有个共同点，那就是可以表示成一个层次关系。这种层次关系可以抽象为树结构。

树结构是一种描述非线性层次关系的数据结构。树是n个数据结点的集合，在该集合中包含一个根结点，根结点之下分布着一些互不交叉的子集合，这些子集合也就是根结点的子树。

• 在一个树结点中，有且仅有一个结点没有直接前驱，这个结点就是树的根结点；

• 除根结点外，其余每个结点有且仅有一个直接前驱；

• 每个结点可以有任意多个直接后驱；

树中的每一个结点都处于一定的层次上。

二叉树：是树结构的一种特殊形式，其是n个结点的集合，每个结点最多只能有两个子结点。二叉树的子树仍然是二叉树。二叉树的一个结点上对应的两个子树分别称为左子树和右子树，由于子树有左右之分，因此二叉树是有序对。

按照数据的存储方式，树结构可以分为顺序存储结构和链式存储结构两种

• 二叉树的顺序存储，顺序存储方式一般较适合完全二叉树的情况，对于非完全二叉树，一般建议采用链式存储方式。（因为非完全二叉树缺少的部分，需填上空的数据结点。）

• 二叉树的链式存储，二叉树的链式存储结构包含结点元素以及分别指向左子树和右子树的引用；

树是一种表达数据之间层次关系的数据结构，树中的每个节点有0个或多个子结点，但是只有一个父节点，父节点为空的节点就是根节点。一棵树只有一个根节点，树适合用来表达有层次关系的数据，比如一个公司的分支机构，计算机上的目录和文件结构等。如果树的子节点之间没有大小关系，则这样的树称为无序树，也称为自由树；如果对的子节点之间有大小关系，则 这样的树称为有序树。树通常也是图的一种形式，是一种没有环路的图。

7.6 图

图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。

图Graph结构也是一种非线性数据结构，图结构在实际生活中具有丰富的例子。如，通信网络、交通网络、人际关系网络等都可以归结为图结构。图结构的组织形式要比树结构更为复杂，因此，图结构对存储和遍历等操作具有更高的要求。

树结构的各数据元素之间具有层次关系，每一层的元素可以和多个下层元素关联，但是只能和一个上层元素关联。如果把这个规则进一步扩展，也就是说，每个数据元素之间可以任意关联，这就构成了一个图结构。正是这种任意关联性，导致了图结构中数据关系的复杂性。研究图结构的一个专门理论工具便是图论。

一个典型的图结构包括两个部分：

• 顶点Vertex：图中的数据元素；

• 边Edge:图中连接这些顶点的线；

所有的顶点构成一个顶点集合，所有的边构成边集合，一个完整的图结构就是由顶点集合和边集合组成。

图是一种特殊的数据组织方式，它不仅可以存储数据元素（对象），还可以存储数据元素之间和复杂关系。从直观上来看，图由一些顶点和连接这些顶点的边组成，顶点描述数据元素，边描述元素之间的关系。图的存储常采用邻接矩阵（二维数组方式）和邻接表（链表或或变长数组）方式。

图的遍历是一个非常重要的操作，一般可采用深度优先搜索和广度优先搜索两种策略。最佳路线选择往往会用到图的数据结构。

7.7 堆 (Heap)

在计算机科学中，堆是一种特殊的树形数据结构，每个结点都有一个值。通常我们所说的堆的数据结构，是指二叉堆。堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。

堆也是一种完全树，除了树的特点以外，堆的父节点和子节点还存在一些特殊关系。最大堆的每个节点的值都大于其子树上所有节点的值。最小堆的每个节点的值都小于子树上所有节点的值。堆的插入和删除操作除了维持堆的完全树特征之外，还要维护节点之间的特殊关系。

7.8 集合（set）

集合是具有某种特征的事物的整体。构成集合的事物或对象称为集合的元素或成员。集合的操作：1是对集合元素的操作，包括插入和删除元素，判断一个元素是否属于集合等；另一部分是集合之间的关系运算。

7.9 哈希表（hash）与映射（map）

哈希技术是在记录的存储位置和记录的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。查找时，根据这个确定的对应关系找到给定值的映射f(key),若查找集合中存在这个记录，则必定在f(key)的位置上。哈希技术既是一种存储方法，也是一种查找方法。

哈希表和映射都是通过一个哈希函数对关键字进行某种运算，得到对应的数据元素在表中的存储位置，然后访问其值，与普通的有序表查找相比，额外的哈希处理会造成数据访问的开销。其查找速度更快。

现实生活中很多采用“key-value”方式组织和存储数据的情况，学生成绩管理系统会通过一个唯一分配的学号建立与具体学生信息映射关系，可以通过学号查询和管理学生信息，这个学号就是key。

7.10 散列表 (Hash)

若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个思想建立的表为散列表。

－8－各种数据结构的比较

-9- 数据结构与数据类型

数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。数据类型可分为两类：原子类型、结构类型。一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。可以认为，数据类型是在程序设计中已经实现了的数据结构。另一方面，在程序设计过程中，当需要引入某种新的数据结构时，总是借助编程语言所提供的数据类型来描述数据的存储结构。

数据类型就是一个值的集合以及在这些值上定义的一系列操作的总称。如，对于C语言的整数类型，其有一定的取值范围，对于整数类型还定义了加法、减法、乘法、除法和取模运算等操作。

按照数据类型的值是否可以分解，数据类型可以分为基本数据类型和聚合数据类型。

把一个语言所处理的对象按其属性不同，分为不同的子集，对不同的子集规定不同的运算操作。

• 类型确定的值的范围。

• 类型确定了值的操作类型；

• 类型确定了值的存储空间大小；

• 类型确定了值的存储方式；

确定数据类型有助于程序设计的简明性和数据的可靠性；有助于数据的存储管理；有利于提高程序的运行效率。

－10－为什么存在各类不同的容器？

各种容器各有优势和短处。

在Java,Python,ruby等语言中都将数组作为一种最基本的容器标准。与此相对应，在LISP,Scheme,Haskell等语言中都将链表作为一种最基本的容器。

数组是整数和值的对应，与之相对应，字典是字符串和数值的对应；实现存放多个数值的目的的方法有数组和链表。同样地，实现字符串和值对应存储的也有多种实现方法。常用的方法是散列表和树；

散列表使用以字符串为参数返回整数的散列函数，实现了字符串与值的对应。存放值之前首先准备一个大的数组，然后使用散列函数（分散函数）将字符串转换成适当分散的整数，用来决定这个值在数组中存放的位置；

散列表要把键对应的值读取出来，首先要经过散列函数把键转换成数组中的位置信息，再把该位置上的值读取出来。

没有万能的容器，就节约内存和节约时间来说，要考虑所需处理的数据的数量级的大小。

参考：

1

The End