1.2 数据结构的有关概念和术语
抽象数据类型的定义可以由元素、元素之间的关系及操作三部分构 成。
抽象数据类型的定义格式 ADT 抽象数据类型名｛ 数据对象：<数据对象的定义> 数据关系：<数据关系的定义> 基本操作：<基本操作的定义> ｝ADT 抽象数据类型名
例如：P4 例1-4
1.2 数据结构的有关概念和术语
指令的集合。 ✓ 算法的特性：有穷性、确定性、可行性、输
入、输出
算法的基本特征
有穷性：算法中的操作步骤为有限个，且每个步骤都能在有限时 间内完成。 确定性：组成算法的操作必须清晰无二义性。 可行性：算法中的所有操作都必须足够基本，都可以通过已经实 现的基本操作运算有限次实现之。 输入：作为算法加工对象的量值，通常体现为算法中的一组变量 。些算法的字面上可以没有输入，实际上已被嵌入算法之中。 输出：它是一组与输入有确定关系的量值，是算法进行信息加工 后得到的结果，这种确定关系即为算法的功能。
工号：1985070016 电话号码： 邮编：233000 身份证号码：3461011
结论1：杂乱无章的数据不能表达和交流。
例2
电话号码簿（a1,b1）（ a2,b2 ）（ …… ）（ an,bn ）, 其中，ai为某人姓名，bi为该人的电话号码。
结论2：数据之间是有联系的。
例3
家族的族谱: 假设某家族有10个成员A, B,C,D,E,F,G,H,I,J， 他们之间的血缘关系可以用如下图表示。
数据结构：相互之间存在一种或多种特定关 系的数据元素的集合。
形式定义为： Data_Structure(D, R)
例如：P5 例1-5
1.2 数据结构的有关概念和术语
数据结构包括以下内容：
（1）数据的逻辑结构。从逻辑关系上描述数 据，与数据存储无关，独立于计算机。它包括 以下四类基本结构：
✓ 集合： 同属一个集合 ✓ 线性结构： 一对一 ✓ 树形结构： 一对多 ✓ 图状结构或网状结构：
B
E
F
A
CDGH源自IJ结论3：数据之间是有结构的。
例4 已知某级学生情况,要求分班按入学成绩排列顺序。
学号 00201 00102 00202 00301
姓名 性别 杨润生 男 石磊 男 李梅 女 马耀先 男
出生日期 82/06/01 83/12/21 83/02/23 82/07/12
入学成绩 561 512 532 509
✓ 索引 ✓ 散列
对每种数据结构，主要讨论如下三方面的问题： ①数据的逻辑结构
数据元素之间的逻辑关系，是具体关系的抽象。 ②数据的存储结构(物理结构)：
数据元素及其关系在计算机内存中的表示； ③数据的运算（或算法）
即对数据施加的操作。定义在数据的逻辑结构上的抽 象的操作。
1.3 算法和算法描述
1、算法 ✓ 算法是对特定问题求解步骤的一种描述，是
多对多
数据结构类型
线性结构 数据结构
非线性结构
线性表 栈 队列 串 数组 广义表
树
图
1.2 数据结构的有关概念和术语
（2）数据的物理结构，数据结构在计算机存 储器中的表示，又称存储结构。它包括：
✓ 顺序存储结构：借助数据元素在存储器中相对 位置表示逻辑关系
✓ 链式存储结构：依靠数据元素中的指针表示元 素之间的逻辑关系
一个数据元素可以由若干个数据项构成。 4、数据对象：性质相同的数据元素的集合。如所有班名相同的记录集 合。 5、数据类型：是指一个类型和定义在这个类型上的操作集合。
分为：原子类型和结构类型 6、抽象数据类型：是指一个逻辑概念上的类型和这个类型上的操作集 合。优点：将数据和操作封装在一起实现了信息隐藏。
非数值数据
1.1 为什么要学习数据结构
数据结构是一门研究“非数值计算程序设计问题 中计算机的操作对象以及它们之间的关系和操作" 的学科。 学习数据结构的原因： ① 计算机处理的数据量越来越大。 ② 数据类型越来越多。 ③ 数据的结构越来越复杂。
例1 已知数据如下：
1985782335902261011
1.3 算法和算法描述
2、算法设计的要求 ✓ 正确性 ✓ 可读性 ✓ 健壮性 ✓ 高效性
算法的设计要求
➢ 算法必须是“正确的”
所谓算法是正确的，除了应该满足算法说明中写明的“功能”之外，应 对各组典型的带有苛刻条件的输入数据得出正确的结果。
在算法是正确的前提下，算法的可读性是摆在第一位的，这在当今大型软 件需要多人合作完成的环境下是换重要的，另一方面，晦涩难读的程序 易于隐藏错误而难以调试。
所在班级 00计算机2 00计算机1 00计算机2 00计算机3
说明：在此类文档管理中,可以有查找、修改、插入、删 除等操作。
结论4：在某种数据结构上可以定义一组运算。
1.2 数据结构的有关概念和术语
1、数据：对客观事物的符号表示，信息的载体，能被计算机识别、存 储和加工处理。如整数，实数，字符串、图象、声音等都是数据。 2、数据元素：数据的基本单位，又可称为元素、结点、顶点、记录等。 3、数据项: 是数据不可分割的最小单位。如学号、姓名等。
第1章
1.1 为什么要学习数据结构 1.2 数据结构的基本概念和术语 1.3 算法和算法描述 1.4 算法时空效率分析方法
本章重点难点
重点: ①数据结构的逻辑结构、存储结构以及基本操
作的概念及相互关系； ②抽象数据类型(ADT)的概念和实现方法，算
法的时间复杂性和空间复杂性分析。 难点:
①抽象数据类型(ADT)的概念和实现方法； ②算法的时间复杂性和空间复杂性分析。
1.1 为什么要学习数据结构
问题
构建数学模型
算法实现
算法+数据结构 = 程序设计
处
给
理
出
问
问
题
题
的
的
策
数
略
学
模
型
处编 理制 问出 题用 的计 指算 令机
p计算机的发展 软件 硬件 应用领域
原始数据
程序
结果数据
p数据处理的种类 数 (整数,实数)
字符 字符串 文字
数值数据
图形 图象 声音
p数据 对客观对象的符号表示
➢ 应有很好的“可读性”
一个算法应当思路清晰、层次分明、简单明了、易读易懂。
算法的设计要求
➢ 必须具有“健壮性”
算法的健壮性指的是，算法应对非法输入的数据作出恰当反映 或进行相应处理，一般情况下，应向调用它的函数返回一个表 示错误或错误性质的值。
➢ 算法的效率