![](https://csdnimg.cn/release/download_crawler_static/88232946/bg4.jpg)
数据结构(C 语言版)
4
表 1-4 年级检索表
年 级 索 引 号 年 级 索 引 号
2011 级 1,2 2013 级 6,7,8
2012 级 3,4,5
诸如此类的还有电话号码查询问题、考试成绩查询问题和企业进销存管理系统等。在
这类文档管理系统的数学模型中,计算机处理的对象之间通常存在着一种简单的线性关系,
因此,这类数学模型可称为线性的数据结构。
例 1-2 计算机系统组成结构,如图 1-1 所示。
计算机系统
硬件系统 软件系统
系统软件 应用软件
CPU
存储器 输入/输出设备 外设
图 1-1 计算机系统组成结构图
计算机系统由硬件系统和软件系统组成,硬件系统由 CPU、存储器、输入/输出设备和
外设组成,软件系统由系统软件和应用软件组成。如果把它们视为数据元素,则这些元素
之间呈现的是一种层次关系,从上到下按层进行展开,可形成一棵倒立的“树”,最上层
是“树根”,依层向下射出“结点”和“树叶”。
同样是树结构的还有某个单位的组织机构、国家行政区域规划、书籍目录等。在这类
问题中,计算机处理的对象是树结构,元素之间是一对多的层次关系,这类数学模型被称
为树的数据结构。
例 1-3 最短路径问题。从城市 A 到城市 B 有多条线路可达,但每条线路的交通成本不同,
那么,应怎样选择一条线路,使得从城市 A 出发到达城市 B 所花费的费用最低呢?可以将
这类问题抽象为图的最短路径问题。如图 1-2 所示,图中的顶点代表城市,有向边代表两
个城市之间的通路,边上的权值代表两个城市之间的交通费。求解 A 到 B 的最低费用,就
是要在有向图从 A 点到 B 点的多条路径中,寻找到一条各边权值之和最小的路径,即求该
图的最短路径。
同样是图结构的还有网络工程图、教学计划编排问题和比赛编排问题等。在这类问题
中,元素之间是多对多的网状关系,这类数学模型被称为图的数据结构。
由以上 3 个例子可见,描述这类非数值计算问题的数学模型不再是数学方程,而是诸
如表、树、图之类的数据结构。因此,可以说“数据结构”课程主要是在研究非数值计算
的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。
1968 年,“数据结构”第一次在美国被确定为一门独立的课程。同年,著名的美国计