550-数据结构DATA STRUCTURE.ppt

数据结构DATA STRUCTURE 概述 研究对象及内容： 学习目的 第一章 绪 论 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析 1.1 什么是数据结构 例1、电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排： (a1，b1)(a2，b2)…(an，bn) 要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。算法的设计，依赖于计算机如何存储人的名字和对应的电话号码。 1.2 基本概念和术语 数据：是对客观事物的符号表示，是能被计算机识别、存储、加工处理的符号总称。包括数、字符、表格、图像、声音等数值性数据和非数值性数据。 数据元素：是数据的基本单位，一个数据元素由一个或多个数据项组成，在计算机中通常被作为一个整体来处理。 数据项：具有独立含义的最小标识单位 例如：描述一个运动员的数据元素可以是 数据结构：由某一数据对象及该对象中所有数据成员之间的关系组成。记为： Data_Structure = {D, R} 其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。 数据逻辑结构和物理结构 逻辑结构：从解决问题的需要出发，为实现必要的功能所建立的数据结构，它属于用户的视图，是面向对象的。 物理结构：指数据该如何在计算机中存放，是数据逻辑结构的物理存储方式，是属于具体实现的视图，是面向计算机的。 关系：物理结构是逻辑数据的存储映象 数据的存储结构 数据元素的映象方法 抽象数据类型的描述方法 如何估算 算法的时间复杂度？ 算法的空间复杂度 抽象数据类型(Abstract Data Type 简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作,ADT和DT在实质上是一个概念。一般数据类型由具体语言系统内部定义；抽象数据类型通常由编程者自己定义，只需定义数据的逻辑结构和操作说明. 1.3 抽象数据类型的表示与实现 抽象数据类型可用（D，S，P）三元组表示 其中，D 是数据对象， S 是 D 上的关系集， P 是对 D 的基本操作集。 ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名 基本操作的定义格式为: 基本操作名（参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉 赋值参数 只为操作提供输入值； 引用参数 以打头，除可提供输入值外，还将返回操作结果。 初始条件 描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。 操作结果 说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。 格式说明： 算法： 是对特定问题求解步骤的一种描述，是指令的 有限序列，其中每一条指令表示一个或多个可 用计算机语言进行运算、操作和描述的命令。 算法具有以下五个特性： 1.4 算法和算法分析 （1）有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 （2）确定性 算法中每一条指令必须有确切的含义。不存在二义性。 （3）可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。 算法五个特性 4）输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。 5）输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。 评价一个好的算法有以下几个标准: 正确性(Correctness ) 算法应满足具体问题的需求。 对算法是否“正确”的理解可以有以下四个层次： 算法设计的要求 算法设计的要求 a．程序中不含语法错误； b．程序对于几组输入数据能够得出满足要求的结果； c．程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果； 通常以第 c 层意义的正确性作为衡量一个算法是否合格的标准。 d．程序对于一切合法的输入数据都能得出满足要求的结果； (2)可读性(Readability) 算法主要是为了人的阅读与交流， 其次才是为计算机执行。 所以算法应该好读。以有利于阅读者对程序的理解。 (3)健壮性(Robustness) 算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 算法设计