资源限制 资源限制包括空间和时间。 算法的代价(cost)是指这种算法消耗的资 源量 选择数据结构的步骤: 1.分析问题,以确定任何算法均会遇到的 资源限制 2.确定必须支持的基本操作,并度量每种 操作所受的资源限制。 3.选择最接近这些开销的数据结构
资源限制 • 资源限制包括空间和时间。 • 算法的代价(cost)是指这种算法消耗的资 源量。 • 选择数据结构的步骤： – 1．分析问题，以确定任何算法均会遇到的 资源限制。 – 2．确定必须支持的基本操作，并度量每种 操作所受的资源限制。 – 3．选择最接近这些开销的数据结构
选择数据结构需要考虑的问题 开始时是将所有数据项都插人数据结构, 还是与其他操作混合在一起插入 数据项能否删除 所有数据项是否按某一个已经定义好的 顺序排列,是否允许查找特定的数据项
选择数据结构需要考虑的问题 • 开始时是将所有数据项都插人数据结构， 还是与其他操作混合在一起插入。 • 数据项能否删除。 • 所有数据项是否按某一个已经定义好的 顺序排列，是否允许查找特定的数据项
代价与效益 家银行的简单交易情况: 顾客可以新开账户、注销账户以及从 账户上存款和取款。 可以从两个层面上考虑这个问题: (1)银行用来与顾客交互的物理基础结构和工 作处理流程的需求 (2)管理账户的数据库系统的需求
代价与效益 一家银行的简单交易情况： • 顾客可以新开账户、注销账户以及从 账户上存款和取款。 可以从两个层面上考虑这个问题： (1)银行用来与顾客交互的物理基础结构和工 作处理流程的需求， (2)管理账户的数据库系统的需求
抽象数据类型和数据结构 类型(ype)是一组值的集合。 数据项( data item)是一条信息或者其值属 于某种类型的一条记录,数据项又称数 据类型的成员( member) 数据类型( data type)是指一种类型和定义 在该类型上的一组操作
抽象数据类型和数据结构 • 类型(type)是一组值的集合。 • 数据项(data item)是一条信息或者其值属 于某种类型的一条记录，数据项又称数 据类型的成员(member)。 • 数据类型(data type)是指一种类型和定义 在该类型上的一组操作
抽象数据类型和数据结构(续) 抽象数据类型(ADT)是指数据结构作为 个软件组件的实现 ADT的接口用一种类型和该类型上的一组操 作来定义,每个操作由它的输入和输岀定义。 数据结构( data structure)是ADT的实现
抽象数据类型和数据结构(续) • 抽象数据类型(ADT)是指数据结构作为一 个软件组件的实现。 – ADT的接口用一种类型和该类型上的一组操 作来定义，每个操作由它的输入和输出定义。 • 数据结构(data structure)是ADT的实现