厦门大学：《数据结构》课程教学课件（PPT讲稿）第一章 绪论（主讲：庄朝晖）

数据结构 主讲：庄朝晖 助教：曹冬林、陈南南

数据结构 主讲：庄朝晖 助教：曹冬林、陈南南

参考书籍 。计算机程序设计技巧(The art of computer programming)(美)克努特 (D.E.Knuth)著 ·数据结构，许卓群等著，北京：高等教育 出版社，1987 数据结构：C++语言描述（美）W.福特 (William Ford),(美)W.托普(William Topp)著北京：清华大学出版社，1997 讲义下载FTP地址：210.34.19.198端 口：21用户名：cai密码：cai

参考书籍 • 计算机程序设计技巧(The art of computer programming) (美)克努特 (D.E. Knuth)著 • 数据结构，许卓群等著，北京：高等教育 出版社，1987 • 数据结构：C++语言描述 (美)W.福特 (William Ford)，(美)W.托普(William Topp)著 北京：清华大学出版社，1997 • 讲义下载FTP地址：210.34.19.198 端 口：21 用户名：cai 密码：cai

第一章绪论 ● 计算机是一门研究用计算机进行信息表示和处理 的科学。这里面涉及到两个问题： 信息的表示 信息的处理 而信息的表示和处理又直接关系到处理信息的 程序的效率。随着计算机的普及，信息量的增加， 信息范围的拓宽，使许多系统程序和应用程序的 规模很大，结构又相当复杂。因此，为了编写出 一个“好”的程序，必须分析待处理的对象的特 征及各对象之间存在的关系，这就是数据结构这 门课所要研究的问题

第一章 绪 论 • 计算机是一门研究用计算机进行信息表示和处理 的科学。这里面涉及到两个问题： • 信息的表示 信息的处理 而信息的表示和处理又直接关系到处理信息的 程序的效率。随着计算机的普及，信息量的增加， 信息范围的拓宽，使许多系统程序和应用程序的 规模很大，结构又相当复杂。因此，为了编写出 一个“好”的程序，必须分析待处理的对象的特 征及各对象之间存在的关系，这就是数据结构这 门课所要研究的问题

1.1什么是数据结构 众所周知，计算机的程序是对信息进行加工处理。 在大多数情况下，这些信息并不是没有组织，信息 (数据)之间往往具有重要的结构关系，这就是数据 结构的内容。那么，什么是数据结构呢？先看以下几 个例子。 例1、电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和 其相应的电话号码，假定按如下形式安排： (a1,b1)(a2,b2)(an,bn) 其中ai,b(i=1,2.n)分别表示某人的名字和对应 的电话号码要求设计一个算法，当给定任何一个人的 名字时，该算法能够打印出此人的电话号码，如果该 电话簿中根本就没有这个人，则该算法也能够报告没 有这个人的标志

• 1.1什么是数据结构 • 众所周知，计算机的程序是对信息进行加工处理。 在大多数情况下，这些信息并不是没有组织，信息 （数据）之间往往具有重要的结构关系，这就是数据 结构的内容。那么，什么是数据结构呢？先看以下几 个例子。 • 例1、电话号码查询系统 • 设有一个电话号码薄，它记录了N个人的名字和 其相应的电话号码，假定按如下形式安排： • (a1，b1)(a2，b2).(an，bn) • 其中ai，bi(i=1，2.n) 分别表示某人的名字和对应 的电话号码要求设计一个算法，当给定任何一个人的 名字时，该算法能够打印出此人的电话号码，如果该 电话簿中根本就没有这个人，则该算法也能够报告没 有这个人的标志

算法的设计，依赖于计算机如何存储人的 名字和对应的电话号码，或者说依赖于名字和其 电话号码的结构。 数据的结构，直接影响算法的选择和效率。 上述的问题是一种数据结构问题。可将名字 和对应的电话号码设计成：二维数组、表结构、 向量。 假定名字和其电话号码逻辑上已安排成N元 向量的形式，它的每个元素是一个数对(ai,b), 1≤i≤n 数据结构还要提供每种结构类型所定义的 各种运算的算法

• 算法的设计，依赖于计算机如何存储人的 名字和对应的电话号码，或者说依赖于名字和其 电话号码的结构。 • 数据的结构，直接影响算法的选择和效率。 • 上述的问题是一种数据结构问题。可将名字 和对应的电话号码设计成：二维数组、表结构、 向量。 假定名字和其电话号码逻辑上已安排成N元 向量的形式，它的每个元素是一个数对(ai，bi)， 1≤i≤n 数据结构还要提供每种结构类型所定义的 各种运算的算法

例2、图书馆的书目检索系统自动化问题 例3、教师资料档案管理系统 例4、多叉路口交通灯的管理问题 P3 通过以上几例可以直接地认为：数据结构 就是研究数据的逻辑结构和物理结构以及它们 之间相互关系，并对这种结构定义相应的运算， 而且确保经过这些运算后所得到的新结构仍然 是原来的结构类型

例2、图书馆的书目检索系统自动化问题 例3、教师资料档案管理系统 例4、多叉路口交通灯的管理问题 P3 通过以上几例可以直接地认为：数据结构 就是研究数据的逻辑结构和物理结构以及它们 之间相互关系，并对这种结构定义相应的运算， 而且确保经过这些运算后所得到的新结构仍然 是原来的结构类型

1.2 基本概念和术语 数据(Data):是对信息的一种符号表示。在计算 机科学中是指所有能输入到计算机中并被计算机 程序处理的符号的总称。 数据元素(Data Element):是数据的基本单位， 在计算机程序中通常作为一个整体进行考虑和处 理。 个数据元素可由若干个数据项组成。数据 项是数据的不可分割的最小单位。 数据对象(Data Object):是性质相同的数据元 素的集合。是数据的一个子集。 数据结构(Data Structure):是相互之间存在 种或多种特定关系的数据元素的集合

• 1.2 基本概念和术语 • 数据(Data):是对信息的一种符号表示。在计算 机科学中是指所有能输入到计算机中并被计算机 程序处理的符号的总称。 • 数据元素(Data Element):是数据的基本单位， 在计算机程序中通常作为一个整体进行考虑和处 理。 • 一个数据元素可由若干个数据项组成。数据 项是数据的不可分割的最小单位。 • 数据对象(Data Object)：是性质相同的数据元 素的集合。是数据的一个子集。 • 数据结构(Data Structure)：是相互之间存在 一种或多种特定关系的数据元素的集合

·数据结构主要指逻辑结构和物理结构 数据之间的相互关系称为逻辑结构。通常分为 四类基本结构： 一、 集合结构中的数据元素除了同属于一种类 型外，别无其它关系。 二、线性结构 结构中的数据元素之间存在一对 一1 的关系。 三、树型结构 结构中的数据元素之间存在一 对多的关系。 四、图状结构或网状结构 结构中的数据元素之 间存在多对多的关系

• 数据结构主要指逻辑结构和物理结构 • 数据之间的相互关系称为逻辑结构。通常分为 四类基本结构： • 一、集合 结构中的数据元素除了同属于一种类 型外，别无其它关系。 • 二、线性结构 结构中的数据元素之间存在一对 一的关系。 • 三、树型结构 结构中的数据元素之间存在一 对多的关系。 • 四、图状结构或网状结构 结构中的数据元素之 间存在多对多的关系。 •

米 数据结构的形式定义为：数据结构是一个二元组： 米 Data-Structure=(D,S) 米其中：D是数据元素的有限集，S是D上关系的有 限集。 类例 复数的数据结构定义如下： 米 Complex=(C,R) 米 其中：C是含两个实数的集合(C1,C2】,分别 表示复数的实部和虚部。R={P},P是定义在集 合上的一种关系{〈C1,C2〉}。 装数据结构在计算机中的表示称为数据的物理结构， 又称为存储结构

数据结构的形式定义为：数据结构是一个二元组： Data-Structure=(D，S) 其中：D是数据元素的有限集，S是D上关系的有 限集。 例 复数的数据结构定义如下： Complex=(C，R) 其中：C是含两个实数的集合﹛C1，C2﹜，分别 表示复数的实部和虚部。R={P}，P是定义在集 合上的一种关系{〈C1，C2〉}。 数据结构在计算机中的表示称为数据的物理结构， 又称为存储结构

数据对象可以是有限的，也可以是无限的。 数据结构不同于数据类型，也不同于数据对象， 它不仅要描述数据类型的数据对象，而且要描述 数据对象各元素之间的相互关系。 ·抽象数据类型：一个数学模型以及定义在该模型 上的一组操作。 抽象数据类型实际上就是对该数据结构的定 义。因为它定义了一个数据的逻辑结构以及在此 结构上的一组算法。 用三元组描述如下： (D,S,P)

• 数据对象可以是有限的，也可以是无限的。 • 数据结构不同于数据类型，也不同于数据对象， 它不仅要描述数据类型的数据对象，而且要描述 数据对象各元素之间的相互关系。 • 抽象数据类型：一个数学模型以及定义在该模型 上的一组操作。 • 抽象数据类型实际上就是对该数据结构的定 义。因为它定义了一个数据的逻辑结构以及在此 结构上的一组算法。 • 用三元组描述如下： • （Ｄ，Ｓ，Ｐ）