数据结构与算法分析全套课件.PPTX

数据结构与算法分析;第一章 导论;1.1 数据结构讨论的范畴;Algorithm + Data Structures = Programs;1.2 基 本 概 念;一、数据与数据结构;是数据（集合）中的一个“个体”;数据结构：; 又例，在2行3列的二维数组的数据{a1, a2, a3, a4, a5, a6}中六个元素之间存在两个关系:;数据的逻辑结构可归结为以下四类:;数据结构的形式定义为:;数据的存储结构 ;关系的映象方法：;链式映象;class EmployeeCell { Object employee; EmployeeCell next; public EmployeeCell(Object o) { employee = o; } };二、数据类型;三、抽象数据类型 (Abstract Data Type 简称ADT);ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名; 基本操作有两种参数：赋值参数只为 操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。;抽象数据类型的表示和实现 ;抽象数据类型; 抽象数据类型通过类的设计可直接构造出来：;四、Java 的接口与ADT;1.3 算法和算法的衡量 ;一 算法设计的原则;二、算法效率的衡量方法和准则; 一个特定算法的“运行工作量” 的大小，只依赖于问题的规模（通常 用整数量n表示），或者说，它是问题 规模的函数。; 假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，则可记作：; 从算法中选取一种对于所研究的问题来说是 基本操作 的原操作，以该基本操作 在算法中重复执行的次数 作为算法运行时间的衡量准则。;例一;例二; T(n)与f(n)有相同的数量级，但f(n)更清晰揭示了算法基于时间优劣的本质趋势;三、算法的存储空间需求;1.4 算法的描述工具;ADT的程序级实现的技术要求：;主 要 参 考 书：;2.1 线性表的类型定义;2.1 线性表的类型定义;抽象数据类型线性表的定义如下：; 基本操作：; InitList( &L ) ; 结构销毁操作;ListEmpty( L );public interface LinearList { public boolean isEmpty(); public int size(); public Object get(int index); public int indexOf(Object theElement); public Object remove(int index); public void add(int index, Object theElement); public String toString(); }; 已知一个非纯???合 B，试构造一个纯集合 A，使 A中只包含 B 中所有值各不相同的数据元素。;集合 B;void union(List &La, List Lb) { La_len=ListLength(La); Lb_len=ListLength(Lb); } // union; 2.2 线性表类型的实现 ? 顺序映象;最简单的一种顺序映象方法是： 使 y 的存储位置和 x 的存储位置相邻。; 用一组地址连续的存储单元 依次存放线性表中的数据元素 ;顺序映像的 C 语言描述; 考虑移动元素的平均情况:;考虑移动元素的平均情况:; 使用实用类Vector的变长功能实现List;3.1 栈的类型定义;; A stack is a container of objects that are inserted and removed according to the last-in-first-out (LIFO) principle. ; 例一、 数制转换 算法基于原理： N = (N div d)×d + N mod d ;例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 81348 168 4 168 21 0 21 2 5