数 据 结 构
数 据 结 构
计算机系
第一章 绪 论
第一章 绪 论
1.1 什么是数据结构
1.2 基本概念和术语
1.3 抽象数据类型的表示与实现
1.4 算法和算法分
1.4.1 算法
1.4.2 算法设计的要求
1.4.3 算法效率的度量
1.4.4 算法的存储空间的需求
第一章 绪 论
第一章 绪 论
计算机是一门研究用计算机进行信息表示和处理的科
学。这里面涉及到两个问题：
信息的表示
信息的处理
而信息的表示和组又直接关系到处理信息的程序
的效率。随着计算机的普及，信息量的增加，信息范
围的拓宽，使许多系统程序和应用程序的规模很大，
结构又相当复杂。因此，为了编写出一个“好”的程序，
必须分析待处理的对象的特征及各对象之间存在的关
系，这就是数据结构这门课所要研究的问题。
1.1 什么是数据结构
众所周知，计算机的程序是对信息进行加工处理。在
大多数情况下，这些信息并不是没有组织，信息（数据）
之间往往具有重要的结构关系，这就是数据结构的内容。
那么，什么是数据结构呢？先看以下几个例子。
例 1 、电话号码查询系统
设有一个电话号码薄，它记录了 N 个人的名字和其
相应的电话号码，假定按如下形式安排：
(a
1
， b
1
)(a
2
， b
2
)…(a
n
， b
n
)
其中 a
i
， b
i
(i=1 ， 2…n) 分别表示某人的名字和对应的电
话号码要求设计一个算法，当给定任何一个人的名字时，
该算法能够打印出此人的电话号码，如果该电话簿中根本
就没有这个人，则该算法也能够报告没有这个人的标志。
算法的设计，依赖于计算机如何存储人的
名字和对应的电话号码，或者说依赖于名字和其
电话号码的结构。
数据的结构，直接影响算法的选择和效率。
上述的问题是一种数据结构问题。可将名
字和对应的电话号码设计成：二维数组、表结构、
向量。
假定名字和其电话号码逻辑上已安排成 N
元向量的形式，它的每个元素是一个数对 (a
i
， b
i
) ， 1≤i≤n
数据结构还要提供每种结构类型所定义的
各种运算的算法。
