· 数据抽象 用ADT描述程序处理的实体时，强
调的是其本质的特征、其所能完成的功 能以及它和外部用户的接口（即外界使 用它的方法）。
· 数据封装 将实体的外部特性和其内部实现细
节分离，并且对外部用户隐藏其内部实 现细节。
精选ppt
17
• 抽象数据类型的形式描述为：
ADT = ( D，S，P ) 其中：D 是数据对象，
其中：C是含两个实数的集合﹛C1，C2﹜，分别表示复数的 实部和虚部。R={P}，P是定义在集合上的一种关系{〈C1， C2〉}。
精选ppt
10
● 数据结构包括： 1. 数据逻辑结构：是对数据元素之间存在的
逻辑关系的描述，它可以用一个数据元素的集 合和定义在此集合上的若干关系表示。
2. 数据物理结构：是数据逻辑结构在计算机 中的表示和实现（逻辑结构在存储器中的映 象），故又称数据“存储结构”。它包含数据 元素的映象和关系的映象。
人的标志。
精选ppt
4
算法的设计，依赖于计算机如何存储人的名 字和对应的电话号码，或者说依赖于名字和其 电话号码的结构。
数据的结构，直接影响算法的选择和效率。
上述的问题是一种数据结构问题。可将名字 和对应的电话号码设计成：二维数组、表结构、 向量。
比如，名字和其电话号码逻辑上可安排成N 元向量的形式，它的每个元素是一个数对(ai ， bi)， 1≤i≤n
• 一类是不可分割的“原子”型数据元素，如： 整数“5”，字符 “N” 等；
• 另一类是由多个款项构成的数据元素，其中 每个款项被称为一个“数据项”。数据项是 数据结构中讨论的“最小单位”。
姓名 学号 性别
班号
出生日期
入学成绩
年月日
精选ppt
8
• 数据对象
性质相同的数据元素的集合。是数 据的一个子集。
精选ppt
9
• 1.2.2 数据结构
数据结构是带“结构”的数据元素的集合。“结构”即指 数 据元素之间存在的关系。
• 数据结构的形式定义为： 数据结构是一个二元组 Data_Structures = ( D,S )
其中：D是数据元素的有限集， S是D上关系的有限集。
例 复数的数据结构定义如下： Complex=(C，R)
精选环境的不同而不同，当用高
级程序编程时，通常可用高级编程语言 中提供的数据类型描述之。
• 例 当以“顺序存储结构”表示长度为3 的长整数表时，可将它定义为： typedef int Long_int[3];
精选ppt
14
• 不同数据结构其操作集不同，但下列操 作必不可缺： 1) 结构的生成； 2) 结构的销毁； 3) 在结构中查找满足规定条件的数 据元素； 4) 在结构中插入新的数据元素； 5) 删除结构中已经存在的数据元素； 6) 遍历。
3. 对数据元素的操作：对每一个数据结构 而言，必定存在与它密切相关的一组操作。
精选ppt
11
• 数据的逻辑结构可归结为以下四类：
一、集合 结构中的数据元素除了同属于一种 类型外，别无其它关系。
二、线性结构 结构中的数据元素之间存在一 对一的关系。
三、树型结构 结构中的数据元素之间存在一 对多的关系。
程要讨论的数据结构。
精选ppt
3
• 例1、电话号码查询系统 设有一个电话号码薄，它记录了N个
人的名字和其相应的电话号码，假定按 如下形式安排：
(a1，b1)(a2，b2)…(an，bn) 其中ai，bi(i=1，2…n) 分别表示某人的 名字和对应的电话号码
要求设计一个算法，当给定任何一个 人的名字时，该算法能够打印出此人的 电话号码，如果该电话簿中根本就没有 这个人，则该算法也能够报告没有这个
精选ppt
15
• 1.2.3 数据类型和抽象数据类型
• 数据类型：在一种程序设计语言中，变量所具有的数据 种类。是一个“值”的集合和定义在此集合上的“一组操作” 的总称。
• 例、在C语言中,数据类型包括基本类型和构造类型 基本类型：整型、浮点型、字符型 构造类型：数组、结构、联合、指针、枚举型、自定义
• 抽象数据类型（Abstract Data Type 简称 ADT）：是指一 个数学模型以及定义在此数学模型上的一组操作。 例如，矩阵的抽象数据类型定义为，矩阵是一个由 m x n 个数排成 m 行 n 列的表，它可以进行初等变换、相加、 相乘、求逆、……等运算。
精选ppt
16
抽象数据类型有两个重要特性：
四、图状结构或网状结构 结构中的数据元素 之间存在多对多的关系。
精选ppt
12
●数据的物理结构可分为（关系的表示方法）： 一. “顺序映象”。以 “y 相对于 x 的存储位置” 表 示 “y 是x的后继”，由此得到的数据存储结构为 “顺序存储结构”。
二. "链式映象"。以和x绑定在一起的附加信息(指针) 表示后继关系，这个指针即为 y 的存储地址，由此 得到的数据存储结构为"链式存储结构"。
S 是 D 上的关系集， P 是 D 的基本操作集。
精选ppt
6
1.2 与数据结构相关的基本概念
• 1.2.1 基本概念和术语
·数据 是所有能被输入到计算机中，且能被计算机处
理的符号(数字、字符等)的集合，它是计算机操作对 象的总称。
是计算机处理的信息的某种特定的符号表示形 式。
精选ppt
7
• 数据元素 是数据(集合)中的一个“个体”，在计
算机中通常作为一个整体进行考虑和处理， 是数据结构中讨论的“基本单位”。两类数 据元素：
数据结构还要提供每种结构类型所定义的各 种运算的算法。
精选ppt
5
• 例2、图书馆的书目检索系统 • 例3、人-机对弈问题 • 例4、多岔路口的交通灯管理问题
以上例子中的数学模型正是数据结构要讨论 的问题。
数据结构是一门讨论"描述现实世界实体的数 学模型(非数值计算)及其上的操作在计算机中如 何表示和实现"的学科。
教材
《数据结构》（C语言版）
严蔚敏 吴伟民编著 清华大学出版社
精选ppt
1
第一章 绪论
精选ppt
2
1.1 数据结构讨论的范畴
●算法+数据结构 = 程序设计 ●算法即处理问题的策略 ●数据结构即为问题的数学模型。 ●数值计算问题的数学模型通常可用一组线性
或非线性的代数方程组或微分方程组来描述
●大量非数值计算问题的数学模型正是本门课