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