数据项、抽象数据类型和数据结 构之间的关系 数据项有逻辑形式和物理形式两个方面 用ADT给出的数据项的定义是它的逻辑形式 数据结构中对数据项的实现是它的物理形式。 比ADT更高层的抽象是对描述程序设计 (即对象和类的相互关系)的抽象
数据项、抽象数据类型和数据结 构之间的关系 • 数据项有逻辑形式和物理形式两个方面。 – 用ADT给出的数据项的定义是它的逻辑形式， – 数据结构中对数据项的实现是它的物理形式。 • 比ADT更高层的抽象是对描述程序设计 (即对象和类的相互关系)的抽象
数据项、抽象数据类型和数据结构之间的 关系图 数据类型 ADT 类型 数据项 操作 逻辑形式 数据结构 数据项: 存储空间 物理形式 子程序
数据类型 ADT: •类型 •操作 数据项： 逻辑形式 数据项： 物理形式 数据结构: •存储空间 •子程序 数据项、抽象数据类型和数据结构之间的 关系图
问题、算法和程序 问题: 是一个需要完成的任务,即一组输入就有 组相应的输出。 可以把问题看做函数。函数是输入和输出之 可的一种映射关系
问题、算法和程序 • 问题： – 是一个需要完成的任务，即一组输入就有一 组相应的输出。 – 可以把问题看做函数。函数是输入和输出之 间的一种映射关系
算法 算法是指解决问题的一种方法或者一个 过程。如果将问题看做函数,那么算法 就是把输入转换为输出 算法的性质: 1.正确性 2.具体步骤 3.确定性 4.有限性 5.可终止性
算法 • 算法是指解决问题的一种方法或者一个 过程。如果将问题看做函数，那么算法 就是把输入转换为输出。 • 算法的性质： – 1．正确性 – 2．具体步骤 – 3．确定性 – 4．有限性 – 5．可终止性
第二章数学预备知识 集合和关系 对数 递归 级数求和与递归 数学证明方法 反证法 数学归纳法
第二章 数学预备知识 • 集合和关系 • 对数 • 递归 • 级数求和与递归 • 数学证明方法 – 反证法 – 数学归纳法