1.2基本概念和术语 逻辑结构一数据元素之间的逻辑关系,即结构中定义的“关系 逻辑结构可细分为4类: 集合结构 线性结构一对一关系○○○○O 一对多 3双 祖 树形结构一对多关系 图状结构多对多关系OQ 炅子 非线性 结构 多对多 北京 合肥一连云港一上海 開京 数据结构 公路交通网 ③◎@
17 逻辑结构--数据元素之间的逻辑关系，即结构中定义的“关系”。 逻辑结构可细分为4类： 集合结构 线性结构 树形结构 图状结构 一对一关系 一对多关系 多对多关系 非线性 结构 1.2 基本概念和术语
1.2基本概念和术语 物理结构—也称存储结构,是数据的逻辑结构在计算机存 储器内的表示(映像)。 顺序映像特点是借助元素在存储器中的对位置来表示数 据元素之间的逻辑关系。-顺序存储结构 非顺序映像特点是借助指示元素存储地址的指表示数据 元素之间的逻辑关系。 链式存储结构 例:算法的设计取决于选定的数据(逻辑)结构 算法的实现依赖于采用的存储结构 3.0 010030 01010201 0101-2.3 数据结构 820201-23 ③◎@
18 0100 0101 物理结构--也称存储结构，是数据的逻辑结构在计算机存 储器内的表示（映像）。 顺序映像 非顺序映像 特点是借助元素在存储器中的相对位置来表示数 据元素之间的逻辑关系。 特点是借助指示元素存储地址的指针表示数据 元素之间的逻辑关系。 例：复数 3.0-2.3i 的存储形式 3.0 -2.3 0100 0201 0101 0201 3.0 -2.3 算法的设计取决于选定的数据（逻辑）结构 算法的实现依赖于采用的存储结构 ----顺序存储结构 ----链式存储结构 1.2 基本概念和术语
1.3抽象数据类型的表示与实现 数据类型一是一个值的集合和定义在这个值集上的一组操作 的总称。 抽象数据类型一由用户定义,用以表示应用问题的数据模 型。它由基本的数据类型组成,并包含一组相关的操作。 抽象数据类型可用ADT=(D,S,P)三元组表示 数据对象D上的关系集D上的操作集 ADT ADT抽象数据类型名[ 常用 数据对象:〈数据对象的定义 定义 数据关系:〈数据关系的定义 格式 基本操作:〈基本操作的定义〉 }ADT抽象数据类型名 数据结构 ③◎@
19 数据类型--是一个值的集合和定义在这个值集上的一组操作 的总称。 抽象数据类型—由用户定义，用以表示应用问题的数据模 型。它由基本的数据类型组成，并包含一组相关的操作。 抽象数据类型可用ADT=（D，S，P）三元组表示 数据对象 D上的关系集 D上的操作集 ADT 抽象数据类型名{ 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名 ADT 常用 定义 格式 1.3 抽象数据类型的表示与实现
1.3抽象数据类型的表示与实现 例:给出自然数( Natural Number)的抽象数据类型定义。 ADT Natura/Numbert 数据对象:一个整数的有序子集合启开始于0结束于机器能表示的最大整数 数据关系: 数据操作: ISZero(x): Boolean f(x==0)返回ve elJe返回 False Add (x, v NaturalNumber f(x+y= MaxInt返回x+y elJe返回 MaxInt Subtract(x,y): NaturalNumber if(x<y)返回0 else返回x-y Equal(, v: Boolean f(x=y)返回T ele返回Fale NAtura/Number 数据结构 ③◎@
20 例：给出自然数（Natural Number）的抽象数据类型定义。 IsZero(x) : Boolean if (x==0) 返回True else 返回False Add (x, y) : NaturalNumber if (x+y<=MaxInt)返回x+y else 返回MaxInt Subtract (x, y) : NaturalNumber if (x < y) 返回 0 else 返回 x - y Equal (x, y) : Boolean if (x==y) 返回True else 返回 False ADT NaturalNumber { }NaturalNumber 数据对象: 数据关系: 数据操作: 一个整数的有序子集合,它开始于0, 结束于机器能表示的最大整数。 1.3 抽象数据类型的表示与实现
1.4算法和算法分析 、算法: 算法是对特定问题求解步骤的一种描述,它是指令的有限 序列,其中每一条指令表示一个或多个操作 、算法的5个特性: 有穷性、确定性、可行性、输入和输出 、算法设计的要求: 正确性、可读性、健壮性、效率与低存储需求 ∈时间复杂度3 空间复杂度 数据结构 21 ③◎@
21 一、算法： 算法是对特定问题求解步骤的一种描述，它是指令的有限 序列，其中每一条指令表示一个或多个操作。 二、算法的5个特性： 有穷性、确定性、可行性、输入和输出 三、算法设计的要求： 正确性、可读性、健壮性、效率与低存储需求 时间复杂度 空间复杂度 1.4 算法和算法分析