第 绪论Java学习教程.pptx

第1章 绪论l1.1 数据结构的基本概念l1.2 算法l1.3 Java开发运行环境第1页/共42页目的和要求目的：勾勒数据结构课程的轮廓。内容：数据结构概念，算法设计与分析。要求：理解数据结构基本概念，理解抽象数据 类型概念；熟悉算法设计和分析方法。掌 握编辑、编译、运行Java Application程 序的基本技能。重点：数据的逻辑结构和存储结构概念。难点：抽象数据类型，算法分析。实验：简单算法设计，回顾Java+语言的基本 语法和面向对象基本概念。第2页/共42页1.1 数据结构的基本概念1.1.1 为什么要学习数据结构1.1.2 什么是数据结构1.1.3 数据类型与抽象数据类型 第3页/共42页1.1.1 为什么要学习数据结构l软件设计是计算机学科各个领域的核心。软件设计时要考虑的首要问题是数据的表示、组织和处理方法。数据结构设计和算法设计是软件系统设计的核心。l“数据结构十算法=程序”。第4页/共42页1.1.2 什么是数据结构数据（data）、数据元素（data element）、数据项（data item）。数据结构（data structure）指数据元素之间存在的关系。第5页/共42页1.数据的逻辑结构（1）线性结构：数据元素只有一个前驱数据元素和一个后继数据元素。（2）树结构：每个数据元素只有一个前驱数据元素，可有零个或若干个后继数据元素。（3）图结构：每个数据元素可有零个或若干个前驱数据元素，零个或若干个后继数据元素。第6页/共42页（1）线性结构 学学 号号姓姓 名名年年 龄龄2002000120020001王红王红18182002000220020002张明张明19192002000320020003吴宁吴宁18182002000420020004秦风秦风1717表表1-1 学生信息表学生信息表 第7页/共42页（2）树结构 第8页/共42页（3）图结构图1-3南京飞往昆明的航班路线图 第9页/共42页2.数据的存储结构（1）顺序存储结构（2）链式存储结构第10页/共42页3.数据操作初始化。判断是否空状态。求长度：统计元素个数。包含：判断是否包含指定元素。遍历：按某种次序访问所有元素，每个元素只被访问一次。取值：获取指定元素值。置值：设置指定元素值。插入：增加指定元素。删除：移去指定元素。第11页/共42页1.1.3 数据类型与抽象数据类型 数据类型（data type）是指一个类型和定义在这个类型上的操作集合。抽象数据类型（Abstract Data Type，ADT）是指一个逻辑概念上的类型和这个类型上的操作集合。第12页/共42页复数抽象数据类型 ADT Complex double real,imag;/实部和虚部 Complex(real,imag);Complex add(Complex c);/加法 Complex sub(Complex c);/减法;第13页/共42页ADT Set 数据：集合中有n（n0）个数据元素，元素类型为T 操作：boolean isEmpty();/判断集合是否为空 int size();/返回集合的元素个数 boolean contains(T x);/判断集合是否包含元素x boolean add(T x);/增加元素x boolean remove(T x);/删除首次出现的元素x void clear();/删除集合所有元素 void print();/输出集合中所有元素 boolean equals(Set s);/比较集合是否相等 boolean containsAll(Set s);/判断是否包含s中的所有元素，s是否子集 boolean addAll(Set s);/集合并 boolean removeAll(Set s);/集合差 boolean retainAll(Set s);/仅保留那些也包含在集合s中的元素第14页/共42页1.1.6 用Java语言描述数据结构public interface SSet /集合接口，T是泛型参数，指定元素类型 boolean isEmpty();/判断集合是否为空 int size();/返回集合的元素个数 String toString();/返回集合元素的描述字符串 T search(T key);/查找，返回关键字为key元素 boolean contain(T x);/判断集合是否包含元素x void add(T x);/增加元素x void remove(T x);/删除首次出现的元素x void removeAll();/删除集合所有元素第15页/共42页1.2 算法1.2.1 什么是算法1.2.2 算法分析1.2.3 算法设计第16页/共42页1.2.1 什么是算法算法定义有穷性确定性输入输出可行性2.算法设计目标正确性可读性健壮性高时间效率高空间效率第17页/共42页3.算法描述元素 search(关键字 key)e=数据序列的第一个元素;while(数据序列未结束&e的关键字不是key)e=数据序列的下一个元素;返回查找到的元素或查找不成功标记;第18页/共42页4.算法与数据结构图1-6 1-6 线性表插入操作 第19页/共42页1.2.2 算法分析度量算法的时间效率算法的时间效率指算法的执行时间随问题规模的增长而增长的趋势，通常采用时间复杂度来度量算法的时间效率。T(n)=O(f(n)2.度量算法的空间效率空间复杂度指算法在执行时为解决问题所需要的额外内存空间，不包括输入数据所占用的存储空间。S(n)=O(f(n)第20页/共42页表1-2 时间复杂度随n变化情况的比较时间复杂度时间复杂度n=8(23)n=10n=100n=1000O(1)1111O(log2n)33.3226.6449.966O(n)8101001000O(nlog2n)2433.22664.49966O(n2)6410010000106第21页/共42页一个简单语句的时间复杂度为O(1)。int count=0;一个循环的时间复杂度为O(n)。int n=8,count=0;for(int i=1;i=n;i+)count+;时间复杂度为O(log2 n)的循环语句。int n=8,count=0;for(int i=1;i=n;i*=2)count+;时间复杂度为O(n2)的二重循环。int n=8,count=0;for(int i=1;i=n;i+)for(int j=1;j=n;j+)count+;【例1.1】算法时间复杂度分析。第22页/共42页【例1.1】算法时间复杂度分析。5.时间复杂度为O(nlog2n)的二重循环。int n=8,count=0;for(int i=1;i=n;i*=2)for(int j=1;j=n;j+)count+;循环次数为 。时间复杂度为O(nlog2n)。6.时间复杂度为O(n)的二重循环。int n=8,count=0;for(int i=1;i=n;i*=2)for(int j=1;j=i;j+)count+;总的循环次数为 。时间复杂度为O(n)。第23页/共42页1.2.3 算法设计【例1.2】求两个整数的最大公约数。说明算法的必要性。质因数分解法。已知则 更相减损术。(91,49)=(42,49)=(42,7)=7 欧几里德（Euclid）的辗转相除法。第24页/共42页【例1.3】数组的顺序查找算法。基本数据类型数组的顺序查找算法实现对象数组的顺序查找算法实现 public class Object /比较当前对象与obj是否相等 public boolean equals(Object obj)return(this=obj);/若两个对象引用同一个实例，返回true 第25页/共42页public final class Integer extends Number implements Comparable private final int value;public boolean equals(Object obj)/覆盖Object类中方法 if(obj instanceof Integer)return value=(Integer)obj).intValue();/比较两个Integer对象的值 return false;第26页/共42页理解数组的动态特性和引用模型 图1-7 一维数组的引用模型 第27页/共42页public static void swap(Object value,int i,int j)/交换下标为i、j的两个数组元素 if(i!=j)/若i、j超出0value.length-1范围，将抛出数组下标越界异常 Object temp=valuej;valuej=valuei;valuei=temp;第28页/共42页public static int concat(int x,int y)/合并数组x和y中的元素，返回新创建的数组 int i,temp=new intx.length+y.length;for(i=0;ix.length;i+)tempi=xi;for(int j=0;jy.length;j+)tempi+j=yj;return temp;第29页/共42页 理解运行时多态性 Object obj=new Integer(123);/父类对象obj引用子类Integer实例System.out.println(obj.toString();/运行时多态性，执行子类Integer的toString()方法obj=new String(123);System.out.println(obj.toString();public static void print(Object value)public static int indexOf(Object value,Object key)第30页/共42页【例1.4】排序数组的顺序查找算法。对基本数据类型的排序数组进行顺序查找Java定义、=关系运算符比较两个基本数据类型数据值的大小。对引用数据类型的排序数组进行顺序查找对象用Comparable接口中的compareTo()方法比较大小。public interface Comparable/可比较接口 int compareTo(T obj)/约定比较对象大小的规则第31页/共42页public final class Integer extends Number implements Comparable public int compareTo(Integer iobj)/比较两个对象值大小，返回-1、0或1 return(this.value iobj.value?-1:(this.value=iobj.value?0:1);第32页/共42页public final class String extends Object implements Serializable,Comparable,CharSequence public int compareTo(String s)/比较字符串的大小，实现Comparable接口 public int compareToIgnoreCase(String s)/比较字符串的大小，忽略字母大小写第33页/共42页例1.5 判断给定字符串是否为Java关键字。第34页/共42页例1.6 排序算法及其必要性。排序算法的必要性直接插入排序直接选择排序 第35页/共42页1.3.1 JDK1.3.2 MyEclipse要求：掌握编辑、编译、运行Java Application程序的基本技能。重点：编辑、编译、运行Java程序。难点：包，MyEclipse的项目、工作区，程序调试技术。1.3 Java开发运行环境第36页/共42页1.3.1 JDK安装JDK设置环境变量在Windows XP中设置环境变量设置环境变量的批命令编译和运行Java程序执行批命令设置环境变量编译运行Application应用程序命令行参数第37页/共42页4.包（1）包的概念（2）Java API的常用包（3）引用包中的类（4）查看Java API（5）查看Java API源程序及包等级（6）导入包（7）声明类所在的包 【例1.7】创建及使用dataStructure包。（8）默认包路径（9）Java源程序结构（10）包可以压缩成jar文件第38页/共42页1.3.2 MyEclipse1.MyEclipse集成开发环境（1）安装MyEclipse并启动（2）界面（3）代码提示和源代码查看（4）项目和工作区第39页/共42页2.创建Java项目并运行（1）新建Java项目（2）新建Java类（3）编辑、编译和运行（4）重构（5）切换工作区（6）访问其他项目中的类和添加JAR包（7）选择运行的类和设置命令行参数第40页/共42页3.程序调试技术程序错误、发现时刻及错误处理原则 语法错、语义错、逻辑错 程序运行方式 正常运行 单步运行 分段运行 3.调试过程 设置断点调试界面单步或分段运行 查看变量的当前值 第41页/共42页数据结构（Java版）（第3版）感谢您的观看！第42页/共42页