数据结构1章线性表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 Student String 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.3 j2sdk1_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); /因除