数据结构教程（Java语言描述）（第2版 微课视频版） 课件全套 李春葆 第1-10章 绪论、线性表- 排序

第1章绪论1.1什么是数据结构1.3算法分析1.2算法及其描述1.4数据结构的目标CONTENTS提纲1/1111.1什么是数据结构1.1.1数据结构的定义用计算机解决一个具体问题的步骤（1）分析问题，确定数据模型。（2）设计相应的算法。（3）编写程序，运行并调试程序直至得到正确的结果。2/111需要从数据入手来分析并得到解决问题的方法数据是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。数据元素是数据的基本单位（例如，A班中的每个学生记录都是一个数据元素），也就是说数据元素是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理数据项是具有独立含义的数据最小单位，也称为域或域（例如，A班中每个数据元素即学生记录是由学号、姓名、性别和班号等数据项组成）。结构化数据3/111学号姓名分数2018001王华902018010刘丽622018006陈明542018009张强952018007许兵762018012李萍882018005李英82高等数学成绩表数据数据项数据元素4/111

数据对象是性质相同的有限个数据元素的集合，它是数据的一个子集。

如大写字母数据对象是集合C={'A'，'B'，'C'，…，'Z'}；1～100的整数数据对象是集合N={1，2，…，100}。

默认情况下，数据结构中的数据都指的是数据对象。5/111数据结构是指所有数据元素以及数据元素之间的关系，可以看作是相互之间存在着特定关系的数据元素的集合。可时把数据结构看成是带结构的数据元素的集合。数据结构＝数据对象＋结构数据元素之间的关系构成结构相同性质的数据元素的集合6/111数据元素之间的关系

结构,现实世界的结构是纷繁复杂的

微观世界―DNA结构7/111

宏观世界―建筑物的结构8/111数据结构中讨论的元素关系主要是指相邻关系或邻接关系。相邻不相邻学号姓名分数2018001王华902018010刘丽622018006陈明542018009张强952018007许兵762018012李萍882018005李英829/111一个数据结构的几个方面：逻辑结构存储结构数据运算数据元素之间的逻辑关系

数据的逻辑结构。数据元素及其关系在计算机存储器中的存储方式

数据的存储结构（或物理结构）。施加在该数据上的操作

数据运算。10/1111.1.2数据的逻辑结构数据的逻辑结构是数据元素逻辑关系的整体。逻辑结构是面向用户的，它反映数据元素之间的逻辑关系而不是物理关系，是独立于计算机的。11/1111.逻辑结构的表示

由于数据逻辑结构是面向用户的，可以采用表格、图等用户容易理解的形式表示。学号姓名分数2018001王华902018010刘丽622018006陈明542018009张强952018007许兵762018012李萍882018005李英82高等数学成绩表例1.112/111XX大学计算机学院电子信息学院……教务处学生处科学系工程系应用系招生办就业办……例1.213/111例1.3北京郑州武汉上海南京南昌长沙杭州14/111

为了更通用地描述数据的逻辑结构，通常采用二元组表示数据的逻辑结构，一个二元组如下：

B=(D，R)

其中，B是一种逻辑数据结构，D是数据元素的集合，在D上数据元素之间可能存在多种关系，R是所有关系的集合。即：D={di

|0≤i≤n-1，n≥0}R={rj

|1≤j≤m，m≥0}15/111R中的某个关系rj（1≤j≤m）是序偶的集合。对于rj中的任一序偶<x，y>（x，y∈D），把x叫做序偶的第一元素，把y叫做序偶的第二元素，又称序偶的第一元素为第二元素的前驱元素，称第二元素为第一元素的后继元素。如在<x，y>的序偶中，x为y的前驱元素，而y为x的后继元素。若某个元素没有前驱元素，则称该元素为开始元素；若某个元素没有后继元素，则称该元素为终端元素。对于对称序偶，即满足这样的条件：若<x，y>∈r（r∈R），则<y，x>∈r（x，y∈D），可用圆括号代替尖括号，即(x，y)∈r。R={rj

|1≤j≤m，m≥0}16/1112.逻辑结构的类型集合：结构中数据元素之间除了“同属于一个集合”的关系外，没有其他关系，与数学中的集合概念相同。17/111线性结构：若结构是非空的，则有且仅有一个开始元素和终端元素，并且所有元素最多只有一个前驱元素和一个后继元素。学号姓名分数2018001王华902018010刘丽622018006陈明542018009张强952018007许兵762018012李萍882018005李英82高等数学成绩表18/111树形结构：若结构是非空的，则有且仅有一个元素为开始元素（也称为根结点），可以有多个终端元素，每个元素有零个或多个后继元素，除开始元素外每个元素有且仅有一个前驱元素。XX大学计算机学院电子信息学院……教务处学生处科学系工程系应用系招生办就业办……19/111北京郑州武汉上海南京南昌长沙杭州图形结构：若结构是非空的，则每个元素可以有多个前驱元素和多个后继元素。20/1111.1.3数据的存储结构数据的存储结构是数据在计算机存储器中的存储方式。存储结构是面向程序员的。逻辑结构存储结构映射设计存储结构的这种映射应满足两个要求：存储所有元素存储数据元素间的关系21/111

【例1.5】对于表1.1所示高等数学成绩表，设计多种存储结构，并讨论各种存储结构的特性。学号姓名分数2018001王华902018010刘丽622018006陈明542018009张强952018007许兵762018012李萍882018005李英82高等数学成绩表22/111存储结构1：用Java语言中的对象数组来存储高等数学成绩表。设计学生类Stud1如下：classStud1{

//学生类intno; //存放学号Stringname; //存放姓名intscore; //存放分数publicStud1(intno1,Stringname1,intscore1){//构造方法 no=no1;name=name1;score=score1;}}23/111Stud1[]st=newStud1[7]; //存放记录的数组st[0]=newStud1(2018001,"王华",90);st[1]=newStud1(2018010,"刘丽",62);st[2]=newStud1(2018006,"陈明",54);st[3]=newStud1(2018009,"张强",95);st[4]=newStud1(2018007,"许兵",76);st[5]=newStud1(2018012,"李萍",88);st[6]=newStud1(2018005,"李英",82);定义一个Stud1对象数组st用于存放高等数学成绩表如下：学号姓名分数2018001王华902018010刘丽622018006陈明542018009张强952018007许兵762018012李萍882018005李英8224/111…st[0]2018001王华90st[1]2018010刘丽62st[6]2018005李英82学号姓名分数2018001王华902018010刘丽622018006陈明542018009张强952018007许兵762018012李萍882018005李英82映射25/111该存储结构的特性：所有元素存放在一片地址连续的存储单元中。逻辑上相邻的元素在物理位置上也是相邻的，所以不需要额外空间表示元素之间的逻辑关系。这种存储结构称之为顺序存储结构。…st[0]2018001王华90st[1]2018010刘丽62st[6]2018005李英8226/111存储结构2：用Java语言中的单链表来存储高等数学成绩表。设计存放高等数学成绩表的结点类Stud2如下：classStud2{

//学生结点类publicintno; //存放学号publicStringname; //存放姓名publicintscore; //存放分数publicStud2next; //指向下一个结点}27/111建立一个用于存放高等数学成绩表的单链表（开始结点为head）如下：Stud2head; //学生单链表开始结点Stud2p1,p2,p3,p4,p5,p6,p7;p1=newStud2();p1.no=2018001;="王华";p1.score=90;p2=newStud2();p2.no=2018010;="刘丽";p2.score=62;p3=newStud2();p3.no=2018006;="陈明";p3.score=54;p4=newStud2();p4.no=2018009;="张强";p4.score=95;p5=newStud2();p5.no=2018007;="许兵";p5.score=76;p6=newStud2();p6.no=2018012;="李萍";p6.score=88;p7=newStud2();p7.no=2018005;="李英";p7.score=82;建立每个元素的结点28/111head=p1; //开始结点用head标识p1.next=p2; //建立结点之间的关系p2.next=p3;p3.next=p4;p4.next=p5;p5.next=p6;p6.next=p7;p7.next=null; //尾结点的next属性设置为null建立结点之间关系以表示对应元素的逻辑关系29/111head2018001王华902018010刘丽622018006陈明542018009张强952018007许兵762018012李萍882018005李英82null这种存储结构的特性：数据元素存放在任意的存储单元中，这组存储单元可以是连续的，也可以是不连续的。通过指针域来反映数据元素的逻辑关系。

称之为链式存储结构。用head唯一标识单链表30/111顺序存储结构链式存储结构索引存储结构哈希（散列）存储结构在软件开发中，人们设计了各种存储结构。归纳为4种基本的存储结构。31/1111.1.4数据的运算将数据存放在计算机中的目的是为了实现一种或多种运算。运算包括功能描述（或运算功能）和功能实现（或运算实现）。前者是基于逻辑结构的，是用户定义的，是抽象的。后者是基于存储结构的，是程序员用计算机语言或伪码表示的，是详细的过程，其核心是设计实现某一运算功能的处理步骤，即算法设计。32/111例如，对于高等数学成绩表这种数据结构，可以进行一系列的运算：增加一个学生成绩记录删除一个学生成绩记录求所有学生的平均分查找序号为i的学生分数等。学号姓名分数2018001王华902018010刘丽622018006陈明542018009张强952018007许兵762018012李萍882018005李英8233/111同一运算，在不同存储结构中的实现过程是不同的。例如，查找序号为i的学生分数，其本身就是运算的功能描述。但在顺序存储结构和链式存储结构中的实现过程不同的。publicstaticintFindi(Stud1[]st,inti){//求序号为i的学生分数if(i<0||i>st.length) //i错误时抛出异常thrownewIllegalArgumentException("参数i错误");else //i正确时返回分数returnst[i].score;}34/111publicstaticintFindi(Stud2head,inti){ //求序号为i的学生分数intj=0;Stud2p=head; //p指向第一个结点while(j<i&&p!=null){j++;p=p.next;}if(i<0||p==null) //i错误时抛出异常thrownewIllegalArgumentException("参数i错误");else //i正确时返回分数returnp.score;}35/111同一逻辑结构可以对应多种存储结构。同样的运算，在不同的存储结构中，其实现过程是不同的。提示36/1111.1.5数据结构和数据类型1.数据类型数据类型是一组性质相同的值的集合和定义在此集合上的一组操作的总称。例如，Java中的short就是整型数据类型。-32768~32767＋、－、*、／

值的集合一组操作37/111数据结构是指计算机处理的数据元素的组织形式和相互关系，而数据类型是某种程序设计语言中已实现的数据结构。在程序设计语言提供的数据类型支持下，就可以根据从问题中抽象出来的各种数据模型，逐步构造出描述这些数据模型的各种新的数据结构。38/1112.抽象数据类型

抽象数据类型（ADT）指的是从求解问题的数学模型中抽象出来的数据逻辑结构和运算（抽象运算），而不考虑计算机的具体实现。抽象数据类型=逻辑结构＋抽象运算39/111ADTComplex

{数据对象：

D={e1，e2|e1，e2均为实数}数据关系：

R={<e1，e2>|e1是复数的实部，e2

是复数的虚部

}一个复数的形式：e1+e2i或（e1，e2）例如，定义复数抽象数据类型Complex40/111基本运算：

AssignComplex(&z，v1，v2)：构造复数Z。GetReal(z，&real)：返回复数z的实部值。

GetImag(z，&Imag)：返回复数z的虚部值。

Add(z1，z2，&sum)：返回两个复数z1、z2的和。}运算功能描述41/111Complex编程实现该数据结构ADT抽象数据类型实质上就是对一个求解问题的形式化描述（与计算机无关），程序员可以在理解基础上实现它。42/1111.2算法及其描述1.2.1什么是算法算法是对特定问题求解步骤的一种描述，它是指令的有限序列。43/111算法具有以下五个重要的特性有穷性。指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。确定性。对于每种情况下执行的操作，在算法中都有确定的含义，不会出现二义性。并且在任何条件下，算法都只有一条执行路径。44/111可行性。算法的每条指令都可以通过已经实现的基本运算执行，并且能够在有限次内实现，即便人借助纸和笔都可以完成。设两数为a、b(a≥b)，求a和b最大公约数（a，b）的步骤如下：

（1）用a除以b(a≥b)，得a

b=q..r1（r1≥0）。

（2）若r1=0，则（a，b）=b，结束。

（3）若r1≠0，则再用b除以r1，得b

r1=q..r2（r2≥0）。

（4）若r2=0，则（a，b）=r1，结束；若r2≠0，则继续，…

，如此下去，直到能整除为止。其最后一个余数为0的除数即为（a，b）的最大公约数。

求最大公约数算法！45/111输入性。算法有零个或多个输入。大多数算法中输入参数是必要的，但对于较简单的算法，如计算1+2的值，不需要任何输入参数，因此算法的输入可以是零个。输出性。算法至少有一个或多个输出。算法用于某种数据处理，如果没有输出，这样的算法是没有意义的，算法的输出是和输入有着某些特定关系的量。46/111算法（有穷性、确定性、可行性）输入输出求解问题47/111【例1.7】考虑下列两段描述：（1）描述一

（2）描述二voidexam1() voidexam2(){intn=2; { intx,y=0;while(n%2==0) x=5/y; n=n+2; System.out.println(x);System.out.println(n); }}这两段描述均不能满足算法的特征，试问它们违反了哪些特性？有穷性可行性48/1111.2.2算法描述采用Java语言描述算法！49/1111.Java的8种基本数据类型（1）4种整数类型（byte、short、int、long）（2）2种浮点数类型（float、double）（3）一种字符类型（char）（4）一种布尔类型（boolean）由程序设计语言系统所定义、不可再划分的数据类型。所占内存大小是固定的，与软硬件环境无关。在内存中存放的是数据值本身。Java的8种基本数据类型50/111基本数据类型之间的转换bytecharshortintlongfloatdouble自动转换强制转换intn=(int)1.23;51/111基本数据类型的输入

从JavaSE5版本开始在java.util类库中新增了一个类专门用于输入操作的类Scanner，可以使用该类输入一个对象。例如建立一个Scanner对象fin：

Scannerfin=newScanner(System.in);

这样就可以用fin对象调用相应方法读取用户在键盘上输入的相应类型的数据，这些方法有:nextByte()nextDouble()nextFloat()nextInt()nextLong()nextShort()next()nextLine()52/111importjava.util.*; //加载java.util类库里的所有类publicclassProg{publicstaticvoidmain(String[]args){intnum1;doublenum2;

Scannerfin=newScanner(System.in);System.out.print("请输入第一个数：");num1=fin.nextInt();

//将输入的内容做int型数据赋值给变量num1System.out.print("请输入第二个数：");num2=fin.nextDouble();

//将输入的内容做double型数据赋值给变量num2System.out.println(num1+"*"+num2+"="+(num1*num2));}}53/111基本数据类型的输出System.out.println()：最常用的输出语句，会把括号里的内容转换成字符串输出到输出控制台，并且换行，当输出的是一个基本数据类型时，会自动转换成字符串，如果输出的是一个对象，会自动调用对象的toString()方法，将返回值输出到控制台。System.out.print()：与上一个语句很相似，区别就是上一个输出后会换行，而这个命令输出后并不换行。System.out.printf()：这个方法延续了C语言的输出方式，通过格式化文本和参数列表输出。54/111importjava.util.*;//加载java.util类库里的所有类publicclassProg{publicstaticvoidmain(String[]args){intnum1;doublenum2;

Scannerfin=newScanner(System.in);System.out.print("请输入第一个数：");

num1=fin.nextInt();

//将输入的内容做int型数据赋值给变量num1System.out.print("请输入第二个数：");num2=fin.nextDouble();

//将输入的内容做double型数据赋值给变量num2System.out.println(num1+"*"+num2+"="+(num1*num2));}}55/1112.Java的引用类型基本数据类型的变量（非引用变量）只有一块存储空间，即在栈空间中分配，而引用类型有两块存储空间，引用变量在栈空间中分配，实例在堆空间中分配。在Java中类型可分为两大类：值类型与引用类型。值类型就是前面就是的8种基本数据类型。引用类型是指除了基本的变量类型之外的所有类型（如通过class定义的类类型和数组等都是引用数据类型）。56/111publicstaticvoidmain(String[]args){inta=1;doubleb=2.2;}栈空间a1b1.2示例值类型变量存放的就是变量值。57/111classA{intn;publicA(){}publicA(intn1){n=n1;}} publicclasstmp{publicstaticvoidmain(String[]args){Aa=newA();Ab=newA(2);} }栈空间ab堆空间A()A(2)与C/C++中的指针一样与C/C++中的指针指向的数据一样引用类型变量存放的就是实例的地址。58/1113.Java中的类设计1）创建类[类修饰符]class类名{

成员变量;

成员方法;}public：共有类，可以被所有其他类访问和引用。abstract：抽象类，没有具体实现功能，只用于扩展子类。final：最终类，表示该类已经非常具体，没有子类可扩展。59/1112）类成员变量的定义及修饰符[变量修饰符]变量数据类型变量名1,变量名2[=变量初值]…;public:任何其他类、对象只要可以看到这个类的话，就可以存取变量的数据。protected：同一类，同一包可以使用。不同包的类要使用，必须是该类的子类。private：不允许任何其他类存取。default：指前面没有修饰符的情况，在同一包中出现的类才可以直接使用。static：说明该成员变量是类变量。final：说明为常量使用。60/1113）方法的声明与实现[方法修饰符]返回类型方法名(形参表)[throwsexceptionList]{…

//方法体}方法修饰符与变量修饰符相同。形参表指定参数，参数的类型可以是简单数据类型，也可以是引用数据类型（数组、类或接口），参数传递方式是值传递。方法体是对方法的实现。它包括局部变量的声明以及所有合法的Java指令。局部变量的作用域只在该方法内部。一个方法必须声明其返回类型，如果无返回值，则必须声明其返回类型为void。61/111Java支持方法名重载，即多个方法可以共享一个名字。重载的方法不一定返回相同的数据类型，但参数必须有所区别：参数的类型不同。参数的顺序不同。这里是指一个方法有多个不同类型参数的情况，改变参数的顺序也算是一种区分方法。参数的个数不同。doubleIt(intx){…}doubleIt(Stringx){…}62/1114）构造方法

构造方法是类的一种特殊方法，它的特殊性主要体现在如下几个方面：构造方法的方法名与类名相同。构造方法没有返回类型。构造方法的主要作用是完成对象的初始化工作。构造方法不能像一般方法那样用“对象.”显式地直接调用，应该用new关键字调用构造方法为新对象初始化。63/111classA { //类AfinalintMAXN=5; //常量privateintsize; //私有成员变量privateint[]a; //私有成员数组

publicA(){ //默认构造方法size=MAXN;a=newint[MAXN];}

publicA(intn){ //重载构造方法size=n;a=newint[size];}publicintgetsize(){ //方法returnsize; //返回size}}示例64/1114.创建对象类名对象名;对象名=new构造方法名([参数表]);类名对象名=new构造方法名([参数表]);合起来65/111使用对象的基本形式如下：对象名.成员变量名对象名.方法名Aa=newA(); //调用默认构造方法创建对象aAb=newA(10); //调用重载构造方法创建对象bSystem.out.println(a.getsize()); //输出5System.out.println(b.getsize()); //输出10示例66/111Java具有垃圾回收功能：当一个对象不再需要时，Java会自动回收其空间。所以用Java实现一个数据结构时不必像C/C++那样需要销毁该数据结构。说明67/1115.类变量和类方法类中static成员变量称为类变量（静态变量），非static成员变量称为实例变量。类变量在各实例间共享，其生存期不依赖于对象的实例，其他类可以不通过对象实例访问它们，甚至可以在它的类的任何对象创建之前访问。类中static方法称为类方法（静态方法），非static方法称为实例方法。类方法中只能直接访问类变量和调用其他类方法，不能直接访问类的其他非类成员（但可以通过对象名访问对象的其他成员）。类方法的调用是通过类名而不是对象来调用的。68/111publicclasstmp{publicstaticvoidReverse(SqListClass<Integer>L){…

}

publicstaticvoidmain(String[]args){

…

Reverse(L);System.out.println("L:"+L.toString());} }示例69/1116.方法中的参数传递在Java中，设计一个类的方法通常带有参数，称为“形参”，调用该方法时的参数称为“实参”。调用方法时涉及到参数传递，Java不同于C++中有值传递和引用传递两种方式，Java中只有值传递，即实参到形参的单向值传递。方法：fun(x)，形参为x。调用语句为fun(y)，实参为y，调用时先执行赋值x=y:若x，y为基本数据类型，将y的值赋值给x。若x，y为其他（均为引用类型），将y的引用（即地址）赋值给x，这样x和y指向相同的对象。说明70/111boolSum(intn,int&s){if(n<=0)returnfalse;s=n*(n+1)/2;returntrue;}intmain(){intn=5,s;if(Sum(n,s))printf("s=%d\n",s);elseprintf("参数错误\n");}C/C++程序：引用参数，用于回传计算结果！Java中不支持！71/1111）参数为基本数据类型的情况

这种情况中参数传递过程采用值拷贝的方式，即将实参值直接拷贝给对应的形参，再执行被调用的方法，返回时不会改变实参值。实参形参单向值传递72/111publicclasstmp{publicstaticvoidSum1(intn,ints){s=n*(n+1)/2;}publicstaticvoidmain(String[]args){ints1=0;intn1=5;

Sum1(n1,s1);System.out.println(s1); //输出0}}示例73/111publicclasstmp{publicstaticintSum2(intn){returnn*(n+1)/2;}publicstaticvoidmain(String[]args){ints1=0;intn1=5;s1=Sum2(n1);System.out.println(s1); //输出15}}要想得到正确的结果，可以将程序改为通过返回值来回传计算结果：74/111

一般方法的返回值只有一个，如果要回传多个值，可以采用返回一个数组的形式。例如以下实现实参a和b的交换：publicclasstmp{publicstaticint[]swap(intx,inty){ //交换x和yint[]tmp=newint[2];tmp[0]=y;tmp[1]=x;returntmp;}publicstaticvoidmain(String[]args){inta=1,b=2;int[]tmp=swap(a,b);a=tmp[0];b=tmp[1];System.out.printf("a=%d,b=%d\n",a,b); //输出a=2,b=1}}75/1112）参数为引用类型的情况当参数为引用类型时，参数由对象名和实例构成的，对象名中存放的是实例的地址。在调用方法时，也是采用值传递，即将实参对象名中存放的地址拷贝该给形参，这样形参和实参指向相同的实例，通过形参改变该实例，那么实参指向的实例也改变了，相当于将实例的改变回传给实参了。76/111classB { //类Bprivateintn;publicB(intn1){ //重载构造方法n=n1;}publicvoidadd(){ //方法n++;}publicintgetn(){ //方法returnn; //返回n}}示例77/111publicclasstmp{publicstaticvoidfun(Bo){ //改变o.no.add();}publicstaticvoidmain(String[]args){Ba=newB(1);System.out.printf("a.n=%d\n",a.getn()); //输出a.n=1

fun(a);System.out.printf("a.n=%d\n",a.getn()); //输出a.n=2}}78/111main栈空间a堆空间n=1fun栈空间oB的实例形参o的改变会回传给实参a！79/111若改为：publicclasstmp{publicstaticvoidfun(Bo){ //改变o.n

o=newB(10);o.add();}publicstaticvoidmain(String[]args){Ba=newB(1);System.out.printf("a.n=%d\n",a.getn()); //输出a.n=1

fun(a);System.out.printf("a.n=%d\n",a.getn()); //输出a.n=1}}80/111main栈空间a堆空间n=1fun栈空间oB的实例n=11B的实例形参o的结果不会回传给实参a！81/111a→o：那么是不是实参a和形参o是完全相同呢？答案是否定的，实参a和形参o的地址是不同的，只是它们指向的实例相同。如果改为如下程序：publicclasstmp{publicstaticvoidfun(Bo){ //改变o.no=newB(1);o.add();}publicstaticvoidmain(String[]args){Ba=null;

fun(a);

System.out.printf("a.n=%d\n",a.getn());}}出错在哪里82/111【例1.7】String为字符串引用类型，分析以下程序的输出结果。publicclasstmp{publicstaticvoidswap(Stringx,Stringy){ //交换x和yStringtmp=x;x=y;y=tmp;System.out.printf("x=%s,y=%s\n",x,y);}publicstaticvoidmain(String[]args){Stringa="Hello";Stringb="World";System.out.printf("a=%s,b=%s\n",a,b);

swap(a,b);System.out.printf("a=%s,b=%s\n",a,b);}}83/111main栈空间a堆空间HellobWorldswap栈空间xypublicclasstmp{publicstaticvoidswap(Stringx,Stringy){//交换x和yStringtmp=x;x=y;y=tmp;System.out.printf("x=%s,y=%s\n",x,y);//输出x=World,y=Hello}publicstaticvoidmain(String[]args){Stringa="Hello";Stringb="World";System.out.printf("a=%s,b=%s\n",a,b); //输出a=Hello,b=Worldswap(a,b);System.out.printf("a=%s,b=%s\n",a,b); //输出a=Hello,b=World}}84/111形参对象的实例不变（或者仅仅改变该实例的成员变量），结果会回传给实参对象。若形参对象的实例发生改变，结果不会回传给实参对象。参数为引用类型时fun(a)fun(x)单向值传递实参a实参xaxxa回传不回传85/1117.Java中泛型设计泛型的本质是参数化类型，也就是说所操作的数据类型被指定为一个参数。这种参数类型可以用在类、接口和方法的创建中，分别称为泛型类、泛型接口、泛型方法。Java语言引入泛型的好处是在编译的时候检查类型安全，并且所有的强制转换都是自动和隐式的，提高代码的重用率。泛型的类型参数只能是类类型（包括自定义类），不能是简单类型。同一种泛型可以对应多个版本（因为参数类型是不确定的），不同版本的泛型类实例是不兼容的。泛型的类型参数可以有多个。86/111Java程序先经过编译期把.java文件转变成字节码.class文件，再经过JIT编译器把字节码转变成机器码。在编译成.class文件时，会将.java文件中泛型做一些特殊处理，即将类的泛型参数E去掉，将类中方法中的泛型参数E变成Object。所以Java的泛型称为“伪泛型”。泛型传入的必须是包装类型，不能传入基本数据类型如int、double、char等，如果容器的数据类型为基本数据类型，需要使用相应的包装类。基本数据类型与其对应的包装类是：byte—Byte，short—Short，int—Integer，long—Long，float—Float，double—Double，char—Character，boolean—Boolean。Integer与int的区别是，Integer的默认值是null，int的默认值是0。87/111classArr<E>{ //自定义数组泛型类publicE[]data; //存放数组中元素publicintsize; //存放长度publicArr(intn){ //构造方法data=(E[])newObject[n]; //强制转换为E类型数组

size=0;}publicvoidadd(Ee){data[size]=e;size++;}publicvoiddisp(){for(inti=0;i<size;i++){if(i==0)System.out.print(data[i]);elseSystem.out.print(""+data[i]);}System.out.println();}}示例88/111publicclasstmp{publicstaticvoidmain(String[]args){

Arr<Integer>arr1=newArr<Integer>(5);//整数数组arr1arr1.add(1);arr1.add(2);arr1.add(3);System.out.print("arr1:");arr1.disp();

Arr<String>arr2=newArr<String>(3);

//字符串数组arr2arr2.add("Mary");arr2.add("John");arr2.add("Smith");System.out.print("arr2:");arr2.disp();}}89/111数据结构的实现通常用泛型来描述。这是由于数据结构关注的是数据元素及其关系是如何保存的，基于这些关系的运算是如何实现的，而数据元素可以是任意类型。使用泛型来描述可以避免对于具体数据元素类型的依赖。提示90/1118.继承

在继承关系中一般两个角色，父类和子类，其中父类也叫基类，子类也叫派生类。类的继承格式如下：class父类{…

}class子类

extends

父类{…}91/111注意：Java仅仅支持单继承，不支持多继承，但支持多重继承。AB单继承A1B多继承A2AB多重继承C92/111

为什么需要继承呢？通过示例来说明这个需求。开发一个学校师生管理系统，主要包含教师和学生，要求如下：教师：属性（编号，姓名，性别，职称），方法（授课，科研，输出个人信息）学生：属性（学号，姓名，性别，专业，分数），方法（上课，输出个人信息）示例93/111PersonTeacherStudent继承继承94/111classPerson{

//人员类publicStringname; //姓名publicStringgender; //性别publicvoiddisp() { //输出信息System.out.print(",姓名:"+name+",性别:"+gender);}}教师：属性（编号，姓名，性别，职称），方法（授课，科研，输出个人信息）学生：属性（学号，姓名，性别，专业，分数），方法（上课，输出个人信息）95/111classTeacherextendsPerson {//教师类从Person继承publicStringno; //编号publicStringjob; //职称publicvoidTeaching(){ //授课方法System.out.println("给学生授课");}publicvoidresearch(){ //科研方法System.out.println("做科研");}教师：属性（编号，姓名，性别，职称），方法（授课，科研，输出个人信息）学生：属性（学号，姓名，性别，专业，分数），方法（上课，输出个人信息）96/111publicvoiddisp() { //输出教师信息，重写Person的disp方法System.out.println("输出一个教师信息");System.out.print("编号:"+no);super.disp(); //调用父类的disp方法System.out.println(",职称:"+job);}}97/111classStudentextendsPerson { //学生类从Person继承publicStringid; //学号publicStringprofession; //专业publicdoublefraction; //分数publicvoidLearning(){ //上课方法System.out.println("上课");}publicvoiddisp() { //输出学生信息，重写Person的disp方法System.out.println("输出一个学生信息");System.out.print("学号:"+id);super.disp(); //调用父类的disp方法System.out.println(",专业:"+profession+",分数:"+fraction);}}教师：属性（编号，姓名，性别，职称），方法（授课，科研，输出个人信息）学生：属性（学号，姓名，性别，专业，分数），方法（上课，输出个人信息）98/111publicstaticvoidmain(String[]args){

Teachert=newTeacher();t.no="0020012";="王华";t.gender="女";t.job="副教授";t.disp(); //调用Teacher类的disp方法

Students=newStudent();s.id="2019002";="陈晶";s.gender="男";fession="计算机";s.fraction=86.5;s.disp(); //调用Student类的disp方法}99/1119.接口接口（interface）是一个抽象类型，是抽象方法（仅有方法声明，没有实现的方法为抽象方法）的集合。一个类通过继承接口的方式，从而来继承接口的抽象方法。接口与类的区别是，接口不能用于实例化对象，接口没有构造方法，接口中所有的方法必须是抽象方法，接口不能包含成员变量（除了static和final变量外），接口不是被类继承了，而是要被类实现。接口之间可以多继承。接口中的方法是不能在接口中实现的，只能由实现接口的类来实现接口中的方法。一个实现接口的类，必须实现接口内所描述的所有方法，否则就必须声明为抽象类。100/111声明接口的格式如下：interface接口名称[extends其他的接口名]{

//声明static或者final变量

//抽象方法}一个类可以同时实现多个接口，实现接口的格式如下：class类implements接口名称[,其他接口名称,…]{

…

//包含实现抽象方法的方法}101/111

声明了一个Area接口，包含静态变量PI和求面积抽象方法getarea()，定义4个类分别实现了Area接口的抽象方法。interfaceArea { //接口AreafinaldoublePI=3.142; //静态变量publicvoidgetarea(); //求面积抽象方法}classsquare

implementsArea { //正方形类publicintx; //长度

publicvoidgetarea(){ //求正方形面积doublearea=x*x;System.out.println("正方形面积:"+area);}}示例102/111classrectangle

implementsArea{ //长方形类publicintx; //长度publicinty; //宽度

publicvoidgetarea(){ //求长方形面积doublearea=x*y;System.out.println("长方形面积:"+area);}}classcircle

implementsArea { //圆类publicintr; //半径

publicvoidgetarea(){ //求圆面积doublearea=PI*r*r;System.out.println("圆面积:"+area);}}103/111classothers

implementsArea { //默认面积

publicvoidgetarea(){ //求长方形面积doublearea=1;System.out.println("默认面积:"+area);}}104/111Areasquarerectangle实现类接口circleothers105/111publicclassInterface{publicstaticvoidmain(String[]args){squares=newsquare();s.x=2;s.getarea(); //输出:4.0rectangler=newrectangle();r.x=2;r.y=5;r.getarea(); //输出:10.0circlec=newcircle();c.r=3;c.getarea(); //输出:28.278

Areao=newothers();

//others类中没有成员变量o.getarea(); //输出:1.0}}106/11110.迭代器Java中提供了一组集合，其接口为Collection<E>，其实现的类有ArrayList、LinkedList、PriorityQueue、Stack、TreeMap和TreeSet等。每个集合表示一组对象，这些对象也称为集合的元素，这组集合中有些集合允许有重复的元素，而另一些则不允许，有些集合是有序的，而另一些则是无序的。107/111对象1对象2对象n…Collection<E>集合迭代器←Iterator对象108/111booleanhasNext()：如果集合中仍有元素可以迭代，则返回true，否则返回false。换句话说，如果next()返回了元素而不是抛出异常，则返回true。Enext()：返回集合中迭代的下一个元素（E为泛型参数）。没有元素可以迭代时抛出NoSuchElementException异常。voidremove()：从迭代器指向的集合中移除迭代器返回的最后一个元素（可选操作）。每次调用next()只能调用一次此方法。Iterator提供的主要方法如下：109/111publicstaticvoidmain(String[]args){

TreeSet<Integer>myset=newTreeSet<>();

//定义集合对象mysetmyset.add(3);myset.add(1);myset.add(4);myset.add(2);myset.add(5);

Iterator<Integer>it=myset.iterator();

//定义myset的迭代器while(it.hasNext()) //顺序遍历System.out.print(it.next()+""); //输出:12345System.out.println();}示例110/1111.3算法分析1.3.1算法的设计目标正确性。可使用性。可读性。健壮性。高时间性能与低存储量需求。111/50分析算法占用的资源CPU时间内存空间时间性能分析空间性能分析算法分析目的：分析算法的时空效率以便改进算法性能。112/501.3.2算法时间性能分析

事后分析统计方法：编写算法对应程序，统计其执行时间。编写程序的语言不同执行程序的环境不同其他因素

事前估算分析方法：撇开上述因素，认为算法的执行时间是问题规模n的函数。

所以不能用绝对执行时间进行比较。算法分析方式：113/50

一个算法是由控制结构（顺序、分支和循环三种）和原操作（指固有数据类型的操作，如+、-、*、/、++和--等）构成的。算法执行时间取决于两者的综合效果。一个算法的基本构成：控制语句1原操作控制语句n原操作…控制语句2原操作1.分析算法的时间复杂度114/50ints=0;if(m!=n)thrownewException("m!=n");for(inti=0;i<m;i++)

s+=a[i][i];returns;doublesolve(intm,intn,double[][]a){顺序结构循环结构分支结构顺序结构}原操作算法的执行时间取决于控制结构和原操作的综合效果。在一个算法中，执行原操作的次数越少，其执行时间也就相对地越少；执行原操作次数越多，其执行时间也就相对地越多。算法中所有原操作的执行次数称为算法频度，这样一个算法的执行时间可以由算法频度来计量。115/501）计算算法频度T(n)假设算法的问题规模为n，例如对10个整数排序，问题规模为n就是10。算法频度是问题规模n的函数，用T(n)表示。算法执行时间大致等于原操作所需的时间×T(n)，也就是说T(n)与算法的执行时间成正比。为此用T(n)表示算法的执行时间。比较不同算法的T(n)大小得出算法执行时间的好坏。116/50voidmatrixadd(int[][]A,int[][]B,int[][]C,intn){for(inti=0;i<n;i++){ //语句①for(intj=0;j<n;j++) //语句② C[i][j]=A[i][j]+B[i][j]; //语句③}}【例1.9】求两个n阶方阵的相加C=A+B的算法如下，求T(n)。执行次数n+1n(n+1)n2T(n)=n+1+n(n+1)+n2

=2n2+2n+1。117/502）什么是算法时间复杂度算法中执行时间T(n)是问题规模n的某个函数f(n)，记作：

T(n)=O(f(n))cf(n)T(n)nn0执行时间118/50

“O”的形式定义为：T(n)=O(f(n))表示存在一个正的常数c，使得当n≥n0时都满足：

|T(n)|≤c|f(n)|f(n)是T(n)的上界这种上界可能很多，通常取最接近的上界，即紧凑上界大致情况：limn→∞T(n)f(n)=c（c>0）119/50

也就是只求出T(n)的最高阶，忽略其低阶项和常系数，这样既可简化T(n)的计算，又能比较客观地反映出当n很大时算法的时间性能。本质上讲，是一种T(n)最高数量级的比较提示120/50例1.9voidmatrixadd(int[][]A,int[][]B,int[][]C,intn){for(inti=0;i<n;i++){ //语句①for(intj=0;j<n;j++) //语句② C[i][j]=A[i][j]+B[i][j]; //语句③}}T(n)=2n2+2n+1=O(n2)121/50一个没有循环的算法的执行时间与问题规模n无关，记作O(1)，也称作常数阶。一个只有一重循环的算法的执行时间与问题规模n的增长呈线性增大关系，记作O(n)，也称线性阶。其余常用的算法时间复杂度还有平方阶O(n2)、立方阶O(n3)、对数阶O(log2n)、指数阶O(2n)等。一般地：122/50

各种不同算法时间复杂度的比较关系如下：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)指数阶：NP问题多项式阶：P问题NP=P？是目前计算机科学的难题之一123/50intSum1(intn){inti,s=0;for(i=1;i<=n;i++)s+=i;

returns;}intSum2(intn){ints;s=n*(n+1)/2;returns;}O(n)O(1)Sum2更好124/503）简化的算法时间复杂度分析一种简化的算法时间复杂度分析方法是，仅仅考虑算法中的基本操作。所谓基本操作是指算法中最深层循环内的原操作。而算法执行时间大致等于基本操作所需的时间×其运算次数。所以在算法分析时，计算T(n)时仅仅考虑基本操作的执行次数。125/50基本操作，执行次数为n2例1.9voidmatrixadd(int[][]A,int[][]B,int[][]C,intn){for(inti=0;i<n;i++){ //语句①for(intj=0;j<n;j++) //语句②

C[i][j]=A[i][j]+B[i][j];

//语句③}}T(n)=n2=O(n2)126/50【例1.10】分析以下算法的时间复杂度。voidfun(intn){ints=0;for(inti=0;i<=n;i++){for(intj=0;j<=i;j++){for(intk=0;k<j;k++)

s++;}}returns;}基本操作算法频度为：127/50

设一个算法的输入规模为n，Dn是所有输入的集合，任一输入I∈Dn，P(I)是I出现的概率，有

，T(I)是算法在输入I下的执行时间，则算法的平均时间复杂度为：2.算法的最好、最坏和平均时间复杂度128/50例如，10个1～10的整数序列递增排序：

n=10

I1={1，2，3，4，5，6，7，8，9，10}

I2={2，1，3，4，5，6，7，8，9，10}

…

Im