《数据结构与算法 C语言版》—— 1.1数据结构的研究对象

本节书摘来自华章出版社《数据结构与算法 C语言版》一 书中的第1章，第1.1节，作者：徐凤生，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

1.1数据结构的研究对象

自然界中的许多问题是可以用数学工具进行描述的。例如，造桥中的受力问题可描述为线性方程，人口增长的情况可描述为微分方程。但更多的非数值计算问题无法用数学方程加以描述。因此，解决这类问题的关键不再是数学分析和计算方法，而是要设计出合适的数据结构，才能有效地解决问题。请看以下列举的具体问题。
例1学生信息检索系统。当我们需要查找某个学生的有关信息或某个专业的情况时，只要建立了相应的数据结构，按照某种算法编写了程序，就可以实现计算机自动检索。由此，可以在学生信息检索系统中建立一个按学号顺序排列的学生信息表和按专业排列的索引表，如表11所示。由这个表构成的文件便是学生信息检索的数学模型，计算机的操作就是按照某种要求对学生信息文件进行查询。

诸如此类的还有电话自动查号系统、考试查分系统、仓库库存管理系统等。在这类文档管理的数学模型中，计算机处理的对象之间存在一种简单的线性关系，因此这类数学模型可称为线性数据结构。
例2八枚硬币问题。假设有八枚硬币，分别表示为a，b，c，d，e，f，g，h，其中有且仅有一枚硬币是假币，并且假币的重量与真币的重量不同，可能比真币轻，也可能比真币重。现要求以天平为工具，用最少的比较次数挑选出假币，并同时确定这枚假币的重量比其他真币轻还是重。解决这个问题的最自然的想法就是把硬币分成两组，依次进行判断。其判断的全过程如图11所示。这里用到的是树形数据结构。

例3教学计划编排问题。一个教学计划包含许多课程，在这些课程之间，有些课程要按规定的先后次序进行，有些则没有次序要求。也就是说，有些课程之间有先修和后继的关系，有些课程可以任意安排次序。假设计算机专业的课程设置如表12所示，则这些课程之间的次序关系可以用一个称为有向图的数据结构来表示，如图12所示。有向图的每个结点表示一门课程，若从结点Ci到Cj之间存在有向边，则表示课程Ci必须先于课程Cj开设；若两门课程之间没有有向边，则表示这两门课程之间没有开设的先后次序。

由以上例子可知，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。使用计算机解决这些实际问题，大致需要经过下列三个步骤：
1)从具体问题中抽象出一个适当的数学模型。
2)设计一个解此数学模型的算法。
3)编出程序、进行测试、调整直至得到最终答案。
数据结构这门课程就是要解决这三个步骤中的第一步和第二步中所提到的问题。建立数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。设计解数学模型的算法就是给出处理问题的策略。
概括地说，数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。实质上，好的程序设计就是好的算法加上好的数据结构。
数据结构在计算机科学中是一门综合性的专业基础课。数据结构的研究不仅涉及计算机硬件(特别是编码理论、存储装置和存取方法等)的研究范围，而且和计算机软件的研究有着密切的关系，无论是编译程序还是操作系统，都涉及数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便更为方便地查找和存取数据元素。因此，数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。在计算机科学中，数据结构不仅是一般程序设计(特别是非数值计算的程序设计)的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。
数据结构课程集中讨论软件开发过程中的设计阶段，同时涉及编码和分析阶段的若干基本问题。此外，为了构造好的数据结构及其实现，还需考虑数据结构及其实现的评价与选择。因此，数据结构的内容包括3个层次的5个要素，如表13所示。