1.1.2 数据结构研究内容

当使用计算机来解决一个具体问题时，一般需要经过下列5个步骤。

1）如何用数据形式描述问题？即如何由问题抽象出一个适当的数学模型。

2）分析问题所涉及的数据量大小和数据之间的关系。

3）明确如何在计算机中存储数据及体现数据之间的关系。

4）明确处理问题时需要对数据进行何种运算。

5）判断所编写程序的性能是否良好。

1-2 数据结构研究内容

【例1-1】《红楼梦》中贾府人丁兴旺，如果给出一组人物：贾代善、贾敏、贾政、贾赦、林黛玉、贾珠、贾宝玉、贾元春、贾琏、贾兰和巧姐，分别找出其中人物之间的亲缘关系。

可以对该具体问题抽象出一个适当的数学模型，即图1-1所示的家谱图，可以从中容易地看出人物之间的亲缘关系。为便于计算机求解该问题，需要设计或选择一个解此数学模型的算法，然后编写出程序并进行调试、测试，直至得到最终的答案为止。

图1-1 家谱图

【例1-2】 在学生成绩信息检索系统中，经常需要按照条件进行成绩信息的检索，如按照班级统计学生的总分，或按照课程统计不及格学生的人数。只要收集到相应的数据，设计如图1-2所示的数学模型，建立相关的数据结构，按照某种算法编写相关程序，就可以实现计算机自动检索。

【例1-3】 一个大的工程或者某种流程可以分为若干小的工程或阶段，这些小的工程或阶段被称为活动。图1-3所示的顶点表示事件，带箭头的边表示活动，边上的值可以表示活动所需的时间。如果一个事件发生了，就说明触发该事件的所有活动已经完成。例如，要想事件E发生，那么必须先完成事件B和E、C和E之间的活动。在这类工程活动中，经常需要研究完成整个工程至少需要多少时间，以及哪些活动是影响工程进度（费用）的关键。

由图1-3可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。因此，可以说数据结构是一门研究非数值计算的程序设计问题中出现的计算机操作对象以及它们之间的关系和操作的学科。

学习数据结构的目的是理解计算机中的信息是如何表示和处理的，尤其是目前，随着计算机信息量的增加、信息范围的拓宽和结构的复杂化，组织和处理这类信息直接关系到处理信息的程序的效率，数据结构可用来分析处理对象以及各对象之间存在的关系，同时通过算法训练来提高读者的思维能力，通过程序设计的技能训练来促进读者综合应用能力和专业素质的提高。

图1-2 学生成绩

图1-3 工程活动