《数据结构(Java语言描述)：第1章 绪论(java版）》由会员分享，可在线阅读，更多相关《数据结构(Java语言描述)：第1章 绪论(java版）（69页珍藏版）》请在金锄头文库上搜索。
1、数数 据据 结 构构(Java语言描述言描述)第一章第一章 绪论绪论数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）第一章第一章 绪绪 论论章节目录章节目录章节目录章节目录章节目录章节目录作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映教学内容教学内容1.2 基本概念与术语基本概念与术语1.3 算法与算法分析算法与算法分析1.4 Java提供的泛型方法提供的泛型方法1.1 数据结构课程讨论的内容数据结构课程讨论的内容数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）
2、第一章第一章 绪绪 论论章节目录章节目录章节目录章节目录章节目录章节目录作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映教学重点与难点教学重点与难点重点：重点：u数据结构的基本概念及有关术语数据结构的基本概念及有关术语u算法及算法的分析方法算法及算法的分析方法难点：难点：u时间复杂度的估算时间复杂度的估算数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）第一章第一章 绪绪 论论章节目录章节目录章节目录章节目录章节目录章节目录作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束
3、放映结束放映课前思考课前思考你知道数据结构是一门讨论什么你知道数据结构是一门讨论什么内容的学科吗？内容的学科吗？数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.1 数据结构课程讨论的内容数据结构课程讨论的内容作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录著名的瑞士科学家沃思教授） Algorithm + Data Structures = Programs ( 算算 法法 + 数数 据据 结 构构 = 程程 序序 ）数据数据结构构:算算法法: 程程序序
4、:为计算机处理问题而编制的一组指令集处理问题的策略（是对数据运算的描述，是程序的逻辑抽象）问题的数学模型，它反映数据及其之间关系。（存储结构和逻辑结构）1.1 数据结构课程讨论的内容数据结构课程讨论的内容数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.1 数据结构课程讨论的内容数据结构课程讨论的内容作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录1.1.1 求解问题举例求解问题举例问题求解的主要步骤：问题求解的主要步骤： 1. 1.确定求解问题的确定求解
5、问题的数学模型数学模型 ( (逻辑结构逻辑结构) )； 2. 2.确定确定存储结构存储结构； 3. 3.设计设计算法算法； 4. 4.编程编程并测试结果。并测试结果。数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.1 数据结构课程讨论的内容数据结构课程讨论的内容作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录 程序设计的实质程序设计的实质是在于解决两是在于解决两个主要问题：个主要问题：一是一是根据实际问题选根据实际问题选择一种好的数据结构；择一种好的数据
6、结构；二是二是设计一设计一个好的算法，而好的算法在很大程个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结度上取决于描述实际问题的数据结构。构。1.1.1 求解问题举例求解问题举例数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.1 数据结构课程讨论的内容数据结构课程讨论的内容作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录【例例1】N个数的选择问题个数的选择问题 算法：算法：?模型：模型：?如何如何选择？N个数在个数在计算机中的算机中的组织1.
7、1.1 求解问题举例求解问题举例数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.1 数据结构课程讨论的内容数据结构课程讨论的内容作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录【例例2】生产订单的自动查询问题生产订单的自动查询问题 算法：算法：?模型：模型：?如何如何查询？生生产订单数据在数据在计算机算机中的中的组织1.1.1 求解问题举例求解问题举例数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.1 数据结
8、构课程讨论的内容数据结构课程讨论的内容作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录【例例3】城市网络的铺设问题城市网络的铺设问题 算法：算法：?模型：模型：?如何如何为城市的各小区之城市的各小区之间铺设网网络线路路,使投使投资最小最小?(对 n 个小区只需个小区只需铺设 n-1 条条线路路)图的最小生成的最小生成树1.1.1 求解问题举例求解问题举例数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.1 数据结构课程讨论的内容数据结构课程讨论的内容作业布
9、置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录1.1.2 本课程的内容本课程的内容方面方面过程程数据数据表示表示数据数据处理理抽象抽象逻辑结构构基本运算基本运算实现存存储结构构算法算法评价价不同数据不同数据结构的比构的比较和算和算法性能分析法性能分析数据数据结构构课程的内容体系程的内容体系:简单地地说, 本本课程程研究的内容包括以下三方面：研究的内容包括以下三方面：1. 数据的数据的逻辑结构构2. 数据的存数据的存储结构构/物理物理结构构3. 数据的运算数据的运算数据结构（数据结构（数据结构（数据结构（
10、JavaJava语言描述语言描述语言描述语言描述）1.2 基本概念与术语基本概念与术语作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录l数据与数据数据与数据结构构l数据数据类型型l抽象数据抽象数据类型型1.2 基本概念与基本概念与术语数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.2 基本概念与术语基本概念与术语作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录
11、1.2.1 数据与数据数据与数据结构构所有能所有能被被输入入到到计算机中，且能被算机中，且能被计算算机机处理理的的符号的符号的总称称。如：。如：实数、整数、数、整数、字符（串）、字符（串）、图形和声音等。形和声音等。数据数据(Data):是是计算机操作算机操作对象象的集合。的集合。是是计算机算机处理的理的信息的信息的某种特定的符某种特定的符号号表示形式表示形式。数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.2 基本概念与术语基本概念与术语作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目
12、录章节目录章节目录章节目录章节目录是数据（集合）中的一个是数据（集合）中的一个“个体个体”数据元素（数据元素（Data Element):是数据是数据结构中构中讨论的的基本基本单位位不同不同场合也叫合也叫结点、点、顶点、点、记录1.2.1 数据与数据数据与数据结构构数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.2 基本概念与术语基本概念与术语作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录 数据数据项（Data Item） ：是数据是数据结构中构中讨论
13、的的最小最小单位位数据元素是由若干个数据数据元素是由若干个数据项组成成例如：例如： 描述一个运描述一个运动员的数据元素的数据元素称之称之为组合合项,其它其它为简单项年年月月日日姓名姓名 俱俱乐部名称部名称 出生日期出生日期 参加日期参加日期 职务业绩1.2.1 数据与数据数据与数据结构构数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.2 基本概念与术语基本概念与术语作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录 数据数据对象（象（Data Object
14、） ：是性是性质相同的数据元素的集合相同的数据元素的集合例如：例如：学生成学生成绩表是一个表是一个数据数据对象象学号学号姓名姓名数学分析数学分析 普通物理普通物理高等代数高等代数2000120002200032000420005张三三李四李四丁一丁一马二二王五王五908067985656876790878967876768数据数据对象中的数据元素象中的数据元素不会是孤立的不会是孤立的，而是彼此相关的而是彼此相关的，这种彼此之种彼此之间的关系称的关系称为“结构构”,如如书中表中表1.1、图1.2(a)、图 1.3都都形成了其特定的形成了其特定的结构（构（线性表、性表、图、树）。）。行：行：数据元
15、素数据元素列：列：数据项数据项数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.2 基本概念与术语基本概念与术语作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录 数据数据结构（构（Data Structure） ：逻辑结逻辑结构构构构线性线性结构构(1:1)树形树形结构构(1:n)图状图状结构构(m:n)集合集合结构构(松散松散)非非线线性性结结构构 是相互之间存在是相互之间存在一种一种或或多种关系多种关系的数据元的数据元素的集合。素的集合。 按逻辑关系分
16、为：按逻辑关系分为：CADBEA AD DC CB BF FE EGGA AB BC CD DE EBCADE数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.2 基本概念与术语基本概念与术语作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录逻辑结构可用二元构可用二元组形式定形式定义为:Data_Structures = (D, R)其中其中: D 是数据元素的有限集合，是数据元素的有限集合，R是是 D上关系的有限集合。上关系的有限集合。也可用数据的也可用数
17、据的逻辑结构构图来形象表示之。来形象表示之。1.2.1 数据与数据数据与数据结构构数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.2 基本概念与术语基本概念与术语作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录【例例1】设有数据结构为：设有数据结构为： B=（D，R），其中：），其中： D=k1,k2,k3,.k9 R=,画出其逻辑结构的图示，并确定相对于关系画出其逻辑结构的图示，并确定相对于关系R，哪些，哪些结点是开始结点，哪些是终端结点？结点是开始结
18、点，哪些是终端结点？ k2 k1 k4 k5 k3 k8 k6 k9 k7开始结点为开始结点为k1,k2(无前驱的结点）无前驱的结点）终端结点为终端结点为k6,k7(无后继的结点）无后继的结点）数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.2 基本概念与术语基本概念与术语作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录【例例2】矩矩阵 中中9个元素之个元素之间存在存在两种关系，一种是行关系，一种是列关系，两种关系，一种是行关系，一种是列关系，试给出其出
19、其逻辑结构的二元构的二元组表示形式。表示形式。 ，其其逻辑结构的二元构的二元组表示形式表示形式为： B=（D，R），其中：，其中： D=a1,a2,a9 R=ROW,COL /ROW:行关系，行关系，COL:列关系列关系 ROW= , COL= ,数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.2 基本概念与术语基本概念与术语作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录存储存储结构结构 是是逻辑结构在构在计算机中的表示，算机中的表示，（即是（即是逻辑
20、结构在存构在存储器中的映象）器中的映象）“数据元素数据元素”的映象的映象 ？“关系关系”的映象的映象 ？1.2.1 数据与数据数据与数据结构构数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.2 基本概念与术语基本概念与术语作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录“数据元素数据元素”的映象方法：的映象方法：用二用二进制位制位(bit)的位串表示数据元素的位串表示数据元素(456)10 = (710)8 = (111001000)2 B = (102
21、)8 = (001000010)2存储存储结构结构 1.2.1 数据与数据数据与数据结构构数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.2 基本概念与术语基本概念与术语作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录存储存储结构结构 1.2.1 数据与数据数据与数据结构构“数据关系数据关系”的映象方法：的映象方法：如：表示如：表示如：表示如：表示 x, yx, yx, yx, y 的的的的方法：方法：方法：方法：1. 1. 顺序映象顺序映象 以相对的存
22、储位置来表示数据元素之间的以相对的存储位置来表示数据元素之间的逻辑关系。逻辑关系。u所有元素存放在一片连续的存贮单元所有元素存放在一片连续的存贮单元中中u整个整个存储结构中只含数据存储结构中只含数据元素值本身元素值本身的的信息信息 x y顺序存储结构顺序存储结构（逻辑位置关系与存储位置关系是一致的）（逻辑位置关系与存储位置关系是一致的）注意注意数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.2 基本概念与术语基本概念与术语作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录
23、章节目录章节目录存储存储结构结构 1.2.1 数据与数据数据与数据结构构2. 2. 链式（非线性）映象链式（非线性）映象以附加信息以附加信息( (指针指针) )表示后继关系。表示后继关系。 需要需要用一个和用一个和 x x附加附加附加附加在一起的在一起的指针指针指针指针来指示来指示 y y 的的存储位置。存储位置。y x链式存储结构链式存储结构 ( ( ( (表示表示表示表示 x, yx, yx, yx, y 的的的的方法方法方法方法) ) ) )u所有元素存放所有元素存放在可以不连续的在可以不连续的存贮单元存贮单元中中u逻辑上相邻的元素其存储位置不一定相邻逻辑上相邻的元素其存储位置不一定相邻
24、注意注意注意注意数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.2 基本概念与术语基本概念与术语作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录 数据的存储结构数据的存储结构 顺序存储顺序存储 链式存储链式存储 散列存储散列存储索引存储索引存储最常用最常用的两种的两种存储存储结构结构 1.2.1 数据与数据数据与数据结构构数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.2 基本概念与术语基本概念与术语作业布置
25、作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录1.2.2 数据数据类型型 其其实数据数据类型反映三个方面的内容：型反映三个方面的内容：存存储结构构，取取值范范围和和允允许进行的操作。行的操作。在用高在用高级程序程序语言言编写的程序中，写的程序中，每个数据都每个数据都应有一个有一个所属的、确定的数所属的、确定的数据据类型。型。数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.2 基本概念与术语基本概念与术语作业布置作业布置作业布置作业布置作业布置作业布置结束放映结
26、束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录在在Java语言中，言中，简单数据数据可描述可描述为Java内置的内置的8种种基本的数据基本的数据类型型之一；之一；而而对于于复复杂数据数据则可通可通过类的声明的声明来引来引入新的数据入新的数据类型。其中型。其中类的的对象象(object)是新的是新的类型的型的实例，例，类的成的成员变量确定量确定了新的数据了新的数据类型的数据表示方法和存型的数据表示方法和存储结构，构，类的构造函数和成的构造函数和成员函数确定了函数确定了新的数据新的数据类型的操作。型的操作。可用可用Java语言中的言中的“数数组”类型来型来实
27、现顺序存序存储结构构，用，用Java语言中提供言中提供的的“对象引用象引用”来来实现链式存式存储结构构。 数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.2 基本概念与术语基本概念与术语作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录例如：学生成例如：学生成绩表基于数表基于数组的的顺序序存存储结构可描述如下：构可描述如下：-学生成学生成绩记录的的类描述描述package ch01;public class ResultsRecord public Str
28、ing studentNum; / 学号学号 public String studentName; / 学生姓名学生姓名 public float mathScore; / 数学分析数学分析 public float physicalScore; / 普通物理普通物理 public float algebraScore; / 高等代数高等代数 public String getStudentNum( ) return studentNum; public void setStudentNum(String studentNum) this.studentNum=studentNum; 数据结构
29、（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.2 基本概念与术语基本概念与术语作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录-基于数基于数组的的顺序存序存储的的类描述描述package ch01;public class SqResults private ResultsRecord listElem； /存放学生成绩的存储空间存放学生成绩的存储空间 private int cluLen; / 当前学生成绩表的长度当前学生成绩表的长度 1.2.2 数据数据类
30、型型数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.2 基本概念与术语基本概念与术语作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录1.2.3 抽象数据抽象数据类型型抽象数据抽象数据类型型(Abstract Data Type,简称称ADT)是指一是指一数据数据值的集合和定的集合和定义在在这个集合上的一个集合上的一组操作操作。Abstract Data Type = Objects Operations 例如例如 int = 0, 1, 2, , INT
31、_MAX, INT_MIN , , , , , 数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.2 基本概念与术语基本概念与术语作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录例如例如 复数的复数的ADT：数据对象数据对象(Objects): (real, imag)数据操作数据操作(Operation): getReal( ):取当前复数的实部值；取当前复数的实部值； getImag():取当前复数的虚部值；取当前复数的虚部值； setReal( re
32、al):修改当前复数的实部值；修改当前复数的实部值； setImag(imag):修改当前复数的虚部值；修改当前复数的虚部值； add(z):与另一个复数的加法运算；与另一个复数的加法运算； minus(z):与另一个复数的减法运算与另一个复数的减法运算 multiply (z):与另一个复数的乘法运算；与另一个复数的乘法运算；数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.2 基本概念与术语基本概念与术语作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录
33、 以后将全部以后将全部采用采用Java接口表示接口表示抽象数据抽象数据类型型。下面通。下面通过两个具体两个具体实例来例来说明抽象数据明抽象数据类型的描述和型的描述和实现。1.2.2 数据数据类型型数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.2 基本概念与术语基本概念与术语作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录例例1.3 用用Java接口来描述复数的抽象数据接口来描述复数的抽象数据类型。假型。假设复数的操作只包含：构造一个复数的操作只包含：构
34、造一个实部部和虚部和虚部为给定定值的复数，的复数，读取和修改复数的取和修改复数的实部和虚部，以及两个复数的求和。部和虚部，以及两个复数的求和。 /复数抽象数据复数抽象数据类型的接口表示型的接口表示public interface IComplex public double getReal(); / 取实部取实部 public void setReal(double real); / 修改实部修改实部 public double getImag(); / 取虚部取虚部 public void setImag(double imag); / 修改虚部修改虚部 public void add(IC
35、omplex Z); / 两个实数的求和两个实数的求和 数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.2 基本概念与术语基本概念与术语作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录public class Complex implements IComplex 例例1.4编写写实现【例例1.3】中复数抽象中复数抽象数据数据类型的型的Java类代代码。 private double real; / 实部实部private double imag; /
36、虚部虚部/ 构造一个实数构造一个实数public ComplexComplex (double real, double imag) this.real = real;this.imag = imag;/ 取实部取实部public double getRealgetReal() () return real;数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.2 基本概念与术语基本概念与术语作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录public cla
37、ss Complex implements IComplex 例例1.4 编写写实现【例例1.3】中复数抽象数中复数抽象数据据类型的型的Java类代代码。 / 修改实部修改实部public void setRealsetReal(double real) this.real = real;/ 取虚部取虚部public double getImag() return imag; / 修改虚部修改虚部public void setImag setImag (double imag) this.imag = imag;数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语
38、言描述）1.2 基本概念与术语基本概念与术语作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录public class Complex implements IComplex 例例1.4 编写写实现【例例1.3】中复数抽象数中复数抽象数据据类型的型的Java类代代码。 / 两个实数的求和两个实数的求和public void addadd(IComplex Z) if (Z != null) real += Z.getReal();imag += Z.getImag();数据结构（数据结构（数据结构（数
39、据结构（JavaJava语言描述语言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录l算法的基本概念算法的基本概念l算法的描述算法的描述l算法分析算法分析1.3 算法与算法分析算法与算法分析数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章
40、节目录章节目录1.3.1 算法的基本概念算法的基本概念何何谓算法？算法？ 算法算法是是对特定特定问题求解步求解步骤的一种描的一种描述。述。严格来格来讲，一个算法一般，一个算法一般应具有以具有以下下5种性种性质：1有有穷性性2确定性确定性3有效性有效性4输入入5输出出算法与程序有区别吗？算法与程序有区别吗？数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录算法算法设计的目的目标:
41、设计算法算法时，通常，通常应考考虑达到以下目达到以下目标：1正确性正确性2. 可可读性性3健壮性健壮性4高效率高效率（时间与空与空间）1.3.1 算法的基本概念算法的基本概念数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录1.3.2 算法的描述算法的描述 本教程描述算法全部采用本教程描述算法全部采用Java程序程序设计语言言。 【例例1】给出求整型数出求整型数组a中最大中最大
42、值的的算法算法 。public static int maxEle( int a) int n=a.length; int max=a0; for (int i=1;in;i+) if (maxai) max=ai; return max;数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录 【例例2】给出将整型数出将整型数组a中数据元素中数据元素实现就地逆置的算法就地逆置的算法
43、 。1.3.2 算法的描述算法的描述public static void reverse(int a) int n=a.length; int temp; for (int i=0, j=n-1; ij; i+,j-) temp=ai; ai=aj; aj=temp; 数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录1.3.3 算法分析算法分析 算法分析算法分析算法复算法复杂
44、度的度的评判判 算法复算法复杂度度时间复复杂度度空空间复复杂度度数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录l时间复复杂度度通常有两种衡量算法通常有两种衡量算法时间(效率效率)的方法的方法:事后事后统计法法事前分析估算法事前分析估算法缺点：缺点：1必必须执行程序行程序2其它因素掩盖算法本其它因素掩盖算法本质数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语
45、言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录和算法和算法执行行时间相关的因素：相关的因素：1算法算法选用的策略用的策略2问题的的规模模3编写程序的写程序的语言言4编译程序程序产生的机器代生的机器代码的的质量量5计算机算机执行指令的硬件速度行指令的硬件速度6程序运行的程序运行的软件件环境境l时间复复杂度度数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作
46、业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录 一个特定一个特定算法的算法的“运行工作量运行工作量”的大小，只依的大小，只依赖于于问题的的规模模（通常用（通常用整数量整数量n表示），或者表示），或者说，它是它是问题规模模的函数。的函数。假如，假如，记为T(n),并将称并将称T (n) 为算法的算法的时间复复杂度。度。【定【定义】 算法的算法的时间复复杂度度 T (n) = O(f(n) 当且当且仅当当存在正常数存在正常数c和和N，对所有的所有的 n(n N)满足足0 T(n) cf(n)。例如：例如：T(n
47、)=4n3+3n2+2n+1= O(n3)?其中其中c=10,N=1数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录如何估算如何估算算法的算法的时间复复杂度？度？1.3.3 算法分析算法分析数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放
48、映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录算法算法 = 控制控制结构构 + 原操作原操作（固有数据类型的操作）算法的算法的执行行时间 =原操作原操作(i)的的执行次数行次数原操作原操作(i)的的执行行时间 算法的算法的执行行时间 与与 原操作原操作执行次数之和行次数之和 成正比成正比 1.3.3 算法分析算法分析数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录
49、章节目录章节目录章节目录【例例1】变量计量变量计量语句频度语句频度1n+1nn+1n(n+1)n2T(n)=2n2+4n+3=O(n2)1.3.3 算法分析算法分析x=0;y=0;s=0;for(k=1;k=n;+k) +x; s+=x; for(i=1;i=n;+i) for(j=1;j=n;+j) +y; s+=y;数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录【例例2
50、】两个矩两个矩阵相乘相乘语句句频度度n+1n(n+1)n2n2(n+1)n3T(n)=2n3+3n2+1=O(n3)1.3.3 算法分析算法分析public static void squareMult (int a, int b, int c, int n) for (int i=0;jn;j+) for (int j=0;jn;j+) cij=0; for (int k=0;kn;k+) cij+=aik*bkj; 数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作业布置作业布置作业布置作业布置作业布置结
51、束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录 简单地：地：从算法中从算法中选取一种取一种对于所于所研究的研究的问题来来说是是 关关键操作操作 的原操的原操作，以作，以该关关键操作操作 在算法中重复在算法中重复执行行的次数（的次数（语句句频度）度） 作作为算法运行算法运行时间的衡量准的衡量准则。1.3.3 算法分析算法分析数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目
52、录章节目录章节目录章节目录章节目录章节目录【例例3】求下列算法的关求下列算法的关键操作操作语句的句的语句句频度及算法的度及算法的时间复复杂度度public static myOut() for (i=1; i=n; i=10*i) printf(%4d, i);解：解：设关键操作语句的语句频度为设关键操作语句的语句频度为f(n), 则有则有10f(n) n,所以所以 f(n) log10n 故故: T(n)=O(log10n)1.3.3 算法分析算法分析数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作业布置
53、作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录有些算法在有些算法在规模相同的情况之下，模相同的情况之下，其其语句句频度会因度会因输入的入的数据数据值或或输入入的的数据数据顺序序不同而不同，不同而不同，则时间复复杂度也会不同，度也会不同，为此有此有最好最好、最坏最坏和和平平均均时间复复杂度之分。度之分。1.3.3 算法分析算法分析数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放
54、映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录【例例4】如下算法如下算法实现的功能是在数的功能是在数组a0:n-1中中查找找值为x的数据元素。若找到，的数据元素。若找到，则返回返回x在在a中的位置；否中的位置；否则，返回，返回-1。求其求其时间复复杂度度。public static int rSearch(int a,int x) int n=a.length; for(int i=0; in&!x.equals(ai);i+); if (i=n) return -1; else return i; 最好最好时间复杂度：O(1)最坏最坏时间复杂度：O(n)平
55、均平均时间复杂度：O(n)1.3.3 算法分析算法分析数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录【例例5】如下算法是用冒泡排序法如下算法是用冒泡排序法对数数组a中的中的n个整型数据元素个整型数据元素进行排序，求行排序，求该算法的算法的时间复复杂度。度。1.3.3 算法分析算法分析public static void bubbleSort(int a, int n) in
56、t temp,flag=1; for (int i=1;in&flag; i+) flag=0; for (int j=0;jaj+1) flag=1; temp=aj; aj=aj+1; aj+1=tmep; 最好最好时间复杂度：O(n)最坏最坏时间复杂度：O(n2)数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录按增长率由小至大的顺序排列有：按增长率由小至大的顺序排列有：
57、注意注意多项式时间算法多项式时间算法的时间复杂度：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指数时间算法指数时间算法的时间复杂度： O(2n)O(n!)O(nn)总之，总之，随着的增大，指数时间算法和多项式时随着的增大，指数时间算法和多项式时间算法在所需时间上间算法在所需时间上相差非常悬殊相差非常悬殊。1.3.3 算法分析算法分析数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目
58、录章节目录章节目录章节目录2 Asymptotic Notation2nn2n log nnLog nfn数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录1.3.3 算法分析算法分析数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放
59、映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录 s = microsecond = 10-6 secondsms = millisecond = 10-3 secondssec = secondsmin = minutes yr = yearshr = hoursd = daysn数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录1.3.4 算法算法
60、设计比比较【问题描述描述】给定一整数序列定一整数序列A1， A2，. An （可能有（可能有负数），求数），求A1An的一个子序列的一个子序列AiAj，使得，使得Ai到到Aj的和最大。例如：整数序列的和最大。例如：整数序列 -2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的的最大子序列的和和为21（从（从A2到到A9）；整数序列；整数序列4，-3，5，-2，1，2，6，-2的最大子序列的和的最大子序列的和为11（从（从A1到到A7）。下面介下面介绍四种四种实现方法方法数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）
61、1.3 算法与算法分析算法与算法分析作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录方法一方法一: 穷举法法(书中算法中算法1.1)public static int maxSub_1(int sequence) int max = 0; int n= sequence.length; int sum = 0; /第一重循环执行一次则计算出长度为第一重循环执行一次则计算出长度为i的所有子序列和的最大值的所有子序列和的最大值 for (int i = 1; i = n; i+) for (int j
62、= 0; j n; j+) sum = 0; for (int k = j; k j + i & k max) max = sum; return max;时间复杂度时间复杂度: O(n3)详细分析见详细分析见 P10数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录方法二方法二: (书中算法中算法1.2)public static int maxSub_2(int seque
63、nce) int max = 0; int n= sequence.length; int sum = 0; for (int i = 0; i n; i+) sum = 0; for (int j = i; j max) max = sum; return max;时间复杂度时间复杂度: O(n2)数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录4 35 2 126 2结果
64、结果分治分治45626811T (n/2 )T ( n/2 )O( n )T ( n ) = 2 T( n/2 ) + n , T(1) = O(1)= 2 2 T( n/22 ) + n/2 + n= 2k O(1) + k n 当当 N/2k = 1时时 = O( n log n )Also true for N 2k算法见算法见P22/算法算法1.3方法三方法三: 分治法分治法时间复杂度时间复杂度: O(nlogn)数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.3 算法与算法分析算法与算法分析作业布置作业布置作业布置作业布置作业布置作业布置
65、结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录方法四方法四: 动态规划法划法(书中算法中算法1.4)public static int maxSub_4(int sequence) int max = 0; int n= sequence.length; int sum = 0; for (int i = 0; i max) max = sum; else if (sum 0) sum = 0; return max;时间复杂度时间复杂度: O(n) 13 24 616 1 13 2 4 6数据结构（数据结构（数据结构（数据结构（JavaJav
66、a语言描述语言描述语言描述语言描述）1.4 Java提供的泛型方法提供的泛型方法作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录若若除去除去数据数据对象的基本象的基本类型外型外，实现方法相同方法相同的，的，则可用泛型方法来描述可用泛型方法来描述这种基本功能。种基本功能。 1.使用使用Object表示泛型表示泛型 2.使用使用Comparable接口接口类型表示泛型表示泛型型1.4 Java提供的泛型方法提供的泛型方法数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言
67、描述）1.4 Java提供的泛型方法提供的泛型方法作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录1.使用使用Object表示泛型表示泛型【例例1】 两个数的置换算法两个数的置换算法（要求方法与与被置换的数据对象的类型无关）public static void swap(Object a, Object b) Object temp=a; a=b; b=tmep;数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.4 Java提供的泛型方法提供的泛型方法作业
68、布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录1.使用使用Object表示泛型表示泛型【注意注意】 1.为了访问这种对象的一个特定方法，为了访问这种对象的一个特定方法，必须首先要必须首先要强制转换强制转换成正确的类型。成正确的类型。 2.基本类型不能作为基本类型不能作为Object类进行传递。类进行传递。因为只有引用类型能够与因为只有引用类型能够与Object类相容，而类相容，而Java中的中的8种基本类型都不能。种基本类型都不能。 解决方法：解决方法：利用利用Java为这为这8种基本类型的种基本类型
69、的每每 一个所提供的包装类。一个所提供的包装类。 3.只有当使用只有当使用Object类中已有的方法能类中已有的方法能够表示所执行的操作时，才能使用够表示所执行的操作时，才能使用Object类类作为泛型类来工作作为泛型类来工作 。数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）1.4 Java提供的泛型方法提供的泛型方法作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录2.使用使用Comparable接口接口类型表示泛型型表示泛型【例例2】 找出数组找出数组a
70、中的最大数中的最大数public calss FindMaxExamp public static Comparable findMax(Comparable a) int k=0; for(int i=1;i0) k=i; return ak; public static void main(String args) Integer sh1=2, 3,4; String st1= Joe, Bob, Bill, Zeke; System.out.println(findMax(sh1); System.out.println(findMax(st1); 数据结构（数据结构（数据结构（数据结构
71、（JavaJava语言描述语言描述语言描述语言描述）第一章第一章 绪绪 论论章节目录章节目录章节目录章节目录章节目录章节目录作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映本本 章章 小小 结结1. 1. 熟悉熟悉各名词、术语的含义，掌握基本概念，各名词、术语的含义，掌握基本概念，特别是数据的特别是数据的逻辑结构逻辑结构和和存储结构存储结构之间的关系。分之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。清哪些是逻辑结构的性质，哪些是存储结构的性质。 2. 2. 了解了解抽象数据类型的定义、表示和实现方抽象数据类型的定义、表示和实现方法。
72、法。 3. 3. 熟悉熟悉用用JavaJava语言描写算法的书写规范。语言描写算法的书写规范。 4. 4. 理解理解算法算法5 5个性质的确切含义和对算法正确个性质的确切含义和对算法正确性的理解。性的理解。5. 5. 掌握掌握计算语句频度和估算算法时间复杂度计算语句频度和估算算法时间复杂度的方法的方法数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）第一章第一章 绪绪 论论章节目录章节目录章节目录章节目录章节目录章节目录作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映作作 业业习题一中的习题一中的 一、一、8 二、二、1
