数据结构1章线性表.ppt

数据结构（Java版）,数据结构（Java版）,第1章 绪论第2章 线性表第3章 排序第4章 栈与队列第5章 数组和广义表第6章 树和二叉树第7章 查找第8章 图第9章 综合应用设计,第1章 绪论,软件设计是计算机学科各个领域的核心。软件设计时要考虑的首要问题是数据的表示、组织和处理方法。数据结构设计和算法设计是软件系统设计的核心。“数据结构十算法=程序”。1.1 数据结构的基本概念1.2 算法与算法分析1.3 Java语言简介,数据结构（Java版）叶核亚,1.1 数据结构的基本概念,1.1.1 抽象数据类型与数据结构1.1.2 数据的逻辑结构1.1.3 数据的存储结构1.1.4 数据的操作,数据结构（Java版）叶核亚,1.1.1 抽象数据类型与数据结构,数据、数据元素、数据项描述客观事物的数字、字符以及所有能输入到计算机中并能为计算机接受的各种符号集合统称为数据（data）。数据是计算机程序的处理对象。表示一个事物的一组数据称作一个数据元素（data element），数据元素是数据的基本单位；构成数据元素的数据称作该数据元素的数据项（data item），数据项是数据元素的不可分割的最小单位。数据类型类型是一组值的集合。数据类型（data type）是指一个类型和定义在这个类型上的操作集合。数据类型定义了数据元素的性质、取值范围以及对数据元素所能进行的各种操作。,数据结构（Java版）叶核亚,表1.1 学生信息表,class StudentString number;String name;String sex;int age;,数据结构（Java版）叶核亚,抽象数据类型抽象数据类型（Abstract Data Type，缩写为ADT）是指一个逻辑概念上的类型和这个类型上的操作集合。没有定义具体数据类型的数据元素称作抽象数据元素。数据结构对一个数据元素集合来说，如果在数据元素之间存在一种或多种特定的关系，则称为数据结构（data structure）。因此，“结构”就是指数据元素之间存在的关系。,数据结构（Java版）叶核亚,1.1.2 数据的逻辑结构,线性结构：数据元素只有一个前驱数据元素和一个后继数据元素。树结构：每个数据元素只有一个前驱数据元素，可有零个或若干个后继数据元素。图结构：每个数据元素可有零个或若干个前驱数据元素，零个或若干个后继数据元素。,图1.1 三种基本的数据结构,数据结构（Java版）叶核亚,1.1.3 数据的存储结构,数据元素在计算机中的存储表示方式称为数据的存储结构，也称为物理结构。顺序存储结构顺序存储结构是把数据元素存储在一块连续地址空间的内存中，其特点是逻辑上相邻的数据元素在物理上也相邻，数据间的逻辑关系表现在数据元素的存储位置关系上。链式存储结构指针是指向物理存储单元地址的变量。由数据元素域和指针域组成的一个整体称为一个结点（node）。链式存储结构是使用指针把相互直接关联的结点（即直接前驱结点或直接后继结点）链接起来，其特点是逻辑上相邻的数据元素在物理上（即内存存储位置上）不一定相邻，数据间的逻辑关系表现在结点的链接关系上。,数据结构（Java版）叶核亚,图1.2 两种存储结构,数据结构（Java版）叶核亚,1.1.4 数据的操作,对一种数据类型的数据元素进行的某种处理称作数据的操作。访问数据元素。统计数据元素个数。更新数据元素值。插入数据元素，在数据结构中增加新的结点。删除数据元素，将指定数据元素从数据结构中删除。查找在数据结构中查找满足一定条件的数据元素。插入、删除、更新操作都包括一个查找操作，以确定需要插入、删除、更新数据元素的确切位置。排序在线性结构中数据元素数目不变的情况下，将数据元素按某种指定的顺序重新排列。,数据结构（Java版）叶核亚,1.2 算法与算法分析,1.2.1 算法1.2.2 算法设计1.2.3 算法分析,数据结构（Java版）叶核亚,1.2.1 算法,算法定义有穷性算法必须在执行有穷步之后结束。确定性算法的每一个步骤必须是确切地定义的。输入算法有零个或多个输入。输出算法有一个或多个输出，即与输入有某种特定关系的量。可行性算法中有待执行的操作和操作必须是相当基本的，即是说，它们原则上都是能够精确地进行的，而且用笔和纸做有穷次就可以完成。算法的描述算法可用文字、高级程序设计语言或类同于高级程序设计语言的伪码描述。此时算法是由语义明确的操作步骤组成的有限序列，它精确地指出怎样从给定的输入信息得到要求的输出信息。,数据结构（Java版）叶核亚,【例1.3】学生信息表的顺序查找算法。,图1.5 学生信息表的顺序查找过程,数据结构（Java版）叶核亚,算法与数据结构 算法是建立在数据的逻辑结构与存储结构上的。对于同样的逻辑结构和存储结构，根据问题的不同要求，采用不同的算法。同样的数据结构，不同的存储结构，则采用的算法必然不同。例如，存储结构不同的线性表其排序算法必然不同。,数据结构（Java版）叶核亚,算法与程序算法用抽象的语言描述解决特定问题的每一步的操作。程序是计算机能理解和执行的指令序列。一个程序实现一个算法。算法和程序的区别是算法的执行是有穷的，而程序的执行可以是无限的。例如操作系统程序，只要系统不受破坏，操作系统的运行将不会停止。,数据结构（Java版）叶核亚,1.2.2 算法设计,算法设计目标正确性可读性健壮性高时间效率高空间效率算法设计实现,数据结构（Java版）叶核亚,【例1.4】求最大值算法的设计与调用。,从两个整数类型数据中得到较大数值的算法设计如下：int Max(int a,int b)return(a=b)?a:b;主函数中，调用Max(Max(a,b),c)将从三个整数中返回最大值，例如，System.out.println(max=+Max(Max(a,b),c);,数据结构（Java版）叶核亚,1.2.3 算法分析,算法的时间复杂度算法的执行时间等于所有语句执行时间的总和，是算法所处理的数据个数n的函数，表示为O(f(n)，O(f(n)称为该算法的时间复杂度。O(1)表示时间是一个常数，不依赖于n；O(n)表示时间与n成正比，是线性关系，O(n2)、O(n3)、O(2n)分别称为平方阶、立方阶和指数阶；O(log2n)为对数阶。算法的空间复杂度,数据结构（Java版）叶核亚,【例1.5】分析算法的时间复杂度。,一个简单语句的时间复杂度为O(1)。sum=0;一个循环的时间复杂度为O(n)。int n=10,sum=0;for(int i=0;in;i+)sum+=n;时间复杂度为O(n2)的二重循环。int n=9;for(int i=0;in;i+)for(int j=0;jn;j+)System.out.print(i*j);如果int n=9;for(int i=0;in;i+)for(int j=0;ji;j+)System.out.print(i*j);二重循环的执行次数为，时间复杂度仍为O(n2)。,数据结构（Java版）叶核亚,时间复杂度为O(nlog2n)的二重循环。int n=8;for(int i=1;i=n;i*=2)for(int j=1;j=n;j+)System.out.print(i*j);循环次数为。时间复杂度为O(nlog2n)。时间复杂度为O(n)的二重循环。int n=8;for(int i=1;i=n;i*=2)for(int j=1;j=i;j+)System.out.print(i*j);总的循环次数为。时间复杂度为O(n)。,数据结构（Java版）叶核亚,表1.2 时间复杂度随n变化情况的比较,数据结构（Java版）叶核亚,1.3 Java语言简介,1.3.1 Java的安装、编辑、编译和运行1.3.2 数据类型与流程控制1.3.3 类与对象1.3.4 类的继承性与多态性1.3.5 Java的接口、内部类与包1.3.6 异常处理1.3.7 Java的标准数据流,数据结构（Java版）叶核亚,1.3.1 Java的安装、编辑、编译和运行,安装Java的开发环境JDK1.3j2sdk1_3_0-win.exeJDK开发包。j2sdk1_3_0-doc.zip帮助文档。设置环境变量set path=c:jdk1.3.0_02bin/设置系统查找Java编译环境的路径set classpath=.;c:jdk1.3.0_02lib/设置系统查找Java包的路径,数据结构（Java版）叶核亚,可以使用UltraEdit编辑Java源程序。编译和运行Java程序打开MS-DOS窗口，进入Java源程序所在的文件夹（设为D:myjava）。D:myjavajavac Hello.java/编译D:myjavajava Hello/运行Hello.class文件,数据结构（Java版）叶核亚,1.3.2 数据类型与流程控制,数据类型在Java语言中，数据类型分为简单类型（primitive types）和引用类型（reference types）。Java的8种简单类型如下：整型：byte,short,int,long。浮点型：float,double。逻辑型：boolean。字符型：char。引用类型包括类（class）、数组（array）和接口（interface）。,数据结构（Java版）叶核亚,2操作符,表1.3 操作符的优先级,数据结构（Java版）叶核亚,3流程控制,if语句if(布尔表达式)语句1；else语句2；switch语句switch（表达式）case常量1：语句1；break；case常量2：语句2；break；default：语句；,数据结构（Java版）叶核亚,for语句for(表达式1；表达式2；表达式3)语句；while语句while(布尔表达式)语句；do-while语句do 语句；while(布尔表达式)；转向语句return，break和continue。,数据结构（Java版）叶核亚,4数组,一维数组类型 数组名/声明一维数组变量数组名=new 类型长度/使用new创建一维数组int a=1，2，3，4，5；/声明数组时赋初值数组名下标表达式/访问数组元素数组名.length/返回数组的长度二维数组int mat=new int 1010；int mat23=1，2，3，4，5，6；,数据结构（Java版）叶核亚,1.3.3 类与对象,类的声明类声明修饰符 class 类名 extends 超类名 implements接口名类主体的类结构类声明成员变量的声明成员方法的声明及实现声明成员变量修饰符staticfinal变量类型 变量名声明成员方法修饰符 返回值类型 方法名(参数列表)throws 异常类方法体,数据结构（Java版）叶核亚,2对象的创建和使用,声明对象类名 对象名类名对象名=new类名(参数列表)Date1 a=new Date1()；引用类成员对象名.变量名/引用类的成员变量对象名.方法名/调用成员方法Java只需要程序员创建所需的对象，而不需要显式地销毁它们。Java的垃圾回收机制自动判断对象是否在使用，并能够自动销毁不再使用的对象，收回对象所占的资源。,数据结构（Java版）叶核亚,1.3.4 类的继承性与多态性,创建子类public class 子类名 extends 超类名子类继承超类中所有可被子类访问的成员变量，当子类成员变量与超类成员变量同名时，称子类成员变量将超类同名成员变量隐藏。子类继承超类中所有可被子类访问的成员方法，子类成员方法与超类成员方法同名时，称子类成员方法覆盖了超类的同名成员方法。this、super引用和instanceof对象操作符Java中，每个对象都具有对自身的访问权，称为this引用。每个对象对超类的访问权，称为super引用。对象操作符instanceof用来测试一个指定对象是指定类（或它的子类）的实例，若是则返回true，否则返回false。最终类、抽象类,数据结构（Java版）叶核亚,1.3.5 Java的接口、内部类与包,接口接口是没有实现的方法和变量的集合。声明接口修饰符 interface 接口名 方法1；方法2；实现接口的类修饰符class类名extends超类名 implements 接口名1，接口名2,数据结构（Java版）叶核亚,内部类一个类被嵌套定义于另一个类中，称为内部类（inner class），也称为嵌套类。包含内部类的类称为外部类。引用Java定义的包包（package）是Java提供的一种区别类名字空间的机制。查看Java的包C:jdk1.3.0_02jdk1.3docsapiindex.html导入包import 包名1.包名1.包名1.类名1*；import java.awt.*；/导入java.awt包中的所有类,数据结构（Java版）叶核亚,1.3.6 异常处理,错误与异常致命性的错误非致命性的异常异常处理机制当程序发生异常时，发现异常的代码可以抛出（throw）一个异常，生成一个异常对象，并把它提交给运行系统，运行系统捕获（catch）该异常，交由程序员编写的相应代码进行异常处理。Java通过错误类（Error）和异常类（Exception）来处理错误和异常。,数据结构（Java版）叶核亚,异常的产生System.out.print(3/0=+(3/0);/因除数为0将会产生一个算术异常（ArithmeticException）int a=5,6,7,8；System.out.println(a5)；/产生一个数组越界异常（ArrayIndexOutOfBoundsException）使用try-catch-finally语句捕获和处理异常try语句1catch(ExceptionType1 e)语句2 finally 语句3,数据结构（Java版）叶核亚,1.3.7 Java的标准数据流,标准输入System.inSystem.in作为字节输入流类InputStream的对象in实现标准输入，其中有read()方法从键盘接收数据。public int read()throws IOException/返回读入的一个字节public int read(byte b)throws IOException/读入的多个字节返回缓冲区b中如果输入流结束，返回-1；发生I/O错时，抛出IOException异常。标准输出System.outSystem.out作为PrintStream类的对象out实现标准输出。其中有print()和println()两个方法，这两个方法支持Java的任意基本类型作为参数。public void print(long l)public void println(),数据结构（Java版）叶核亚,作业,熟悉实验环境：掌握Java程序的设计、编辑、编译与运行。,