数据结构讲义概论.pdf

数 据 结 构 数 据 结 构 计算机系 中国系统分析员（） 第一章 绪 论 第一章 绪 论 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 ，b )(a ，b )…(a ，b ) 1 1 2 2 n n 其中a ，b (i=1，2…n) 分别表示某人的名字和对应的电 i i 话号码要求设计一个算法，当给定任何一个人的名字 时，该算法能够打印出此人的电话号码，如果该电话 簿中根本就没有这个人，则该算法也能够报告没有这 个人的标志。 中国系统分析员（） 中国系统分析员（） 算法的设计，依赖于计算机如何存储人的 名字和对应的电话号码，或者说依赖于名字和 其电话号码的结构。 数据的结构，直接影响算法的选择和效率。 上述的问题是一种数据结构问题。可将名 字和对应的电话号码设计成：二维数组、表结 构、向量。 假定名字和其电话号码逻辑上已安排成N 元向量的形式，它的每个元素是一个数对(ai ， bi) ， 1≤i≤n 数据结构还要提供每种结构类型所定义的 各种运算的算法。 中国系统分析员（） 中国系统分析员（） 例2 、图书馆的书目检索系统自动化问题 例3、教师资料档案管理系统 例4 、多叉路口交通灯的管理问题 P3 通过以上几例可以直接地认为：数据结构 就是研究数据的逻辑结构和物理结构以及它们 之间相互关系，并对这种结构定义相应的运算， 而且确保经过这些运算后所得到的新结构仍然