数据结构——Java语言描述(上)ppt课件

1、第第1章章 绪论绪论第二章第二章 线性表线性表第三章第三章 堆栈和队列堆栈和队列第四章第四章 串串第五章第五章 数组，集合和矩阵数组，集合和矩阵第六章第六章 递归算法递归算法1.1 数据构造的根本概念数据构造的根本概念 1.2 笼统数据类型笼统数据类型1.3 算法和算法的时间复杂度算法和算法的时间复杂度1.4 算法的空间复杂度分析算法的空间复杂度分析1.5 Java言语的工具包言语的工具包本章主要知识点：本章主要知识点：数据构造的根本概念，包括数据、数据元素、笼统数据元数据构造的根本概念，包括数据、数据元素、笼统数据元素、数据的逻辑构造、数据的存储构造、数据的操作素、数据的逻辑构造、数据的存储

2、构造、数据的操作类型、数据类型和笼统数据类型的概念类型、数据类型和笼统数据类型的概念算法的根本概念，包括算法的定义、性质和算法的设计目算法的根本概念，包括算法的定义、性质和算法的设计目的的算法的时间复杂度分析，包括算法的时间复杂度分析，包括O( )函数的定义，几种典型函数的定义，几种典型算法的时间复杂度分析方法算法的时间复杂度分析方法1.1 数据构造的根本概念数据构造的根本概念 1 数据和数据元素 数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的笼统描画。 表示一个事物的一组数据称作一个数据元素；构成数据元素的数据称作该数据元素的数据项。 数据构造课程在讨论一种

3、类型的数据构造问题时，通常说的是笼统意义上的数据元素，是没有实践含义的。我们把没有实践含义的数据元素称作笼统数据元素。 2 数据的逻辑构造 数据元素之间的相互联络方式称为数据的逻辑构造。 按照数据元素之间的相互联络方式，数据的逻辑构造可分为线性构造、树构造和图构造。 线性构造的普通定义是：除第一个和最后一个数据元素外每个数据元素只需一个前驱数据元素和一个后继数据元素。 树构造的普通定义是：除根结点外每个数据元素只需一个前驱数据元素，可有零个或假设干个后继数据元素。 图构造的普通定义是：每个数据元素可有零个或假设干个前驱数据元素和零个或假设干个后继数据元素。 A ABCDA ABDFEGCA A

4、BDEFCG(a)(c)(b) (a)线性构造；线性构造； (b)树构造；树构造； (c)图构造图构造数据的存储构造数据的存储构造 任何需求计算机进展管理和处置的数据元素都必任何需求计算机进展管理和处置的数据元素都必需首先按某种方式存储在计算机中。数据元素在计算机需首先按某种方式存储在计算机中。数据元素在计算机中的存储方式称为数据的存储构造。中的存储方式称为数据的存储构造。 数据存储构造的根本方式有两种：一种是顺序存数据存储构造的根本方式有两种：一种是顺序存储构造，另一种是链式存储构造。储构造，另一种是链式存储构造。 顺序存储构造是把数据元素存储在一块延续地址顺序存储构造是把数据元素存储在一块

5、延续地址空间的内存中，程序设计方法是运用数组。顺序存储构空间的内存中，程序设计方法是运用数组。顺序存储构造的特点是，逻辑上相邻的数据元素在物理上也相邻，造的特点是，逻辑上相邻的数据元素在物理上也相邻，数据间的逻辑关系表如今数据元素的存储位置关系上。数据间的逻辑关系表如今数据元素的存储位置关系上。 链式存储构造是用对象的援用把相互直接关联的链式存储构造是用对象的援用把相互直接关联的结点即直接前驱结点或直接后继结点链接起来。结点即直接前驱结点或直接后继结点链接起来。链式存储构造的特点是，逻辑上相邻的数据元素在物链式存储构造的特点是，逻辑上相邻的数据元素在物理上即内存存储位置上不一定相邻，数据间的逻

6、理上即内存存储位置上不一定相邻，数据间的逻辑关系表如今结点的链接关系上。以下图是包含数据辑关系表如今结点的链接关系上。以下图是包含数据元素元素a0,a1,an-1的线性构造的链式存储构造表示图的线性构造的链式存储构造表示图.其中，上一个结点到下一个结点的箭头表示上一个结其中，上一个结点到下一个结点的箭头表示上一个结点中对象变量域所表示的下一个结点对象。对象变量点中对象变量域所表示的下一个结点对象。对象变量head表示了链式存储构造中的第一个结点对象。表示了链式存储构造中的第一个结点对象。 head.0a1a1na 2a.0a1a2a1na2na012n-2n-1(a)(b)(a) 顺序存储构造

7、；顺序存储构造； (b) 链式存储构造链式存储构造4 数据的操作数据的操作 对一种类型的数进展的某种方法的处置称作数据对一种类型的数进展的某种方法的处置称作数据的操作，一种类型的数据一切的操作集合称作数据的的操作，一种类型的数据一切的操作集合称作数据的操作集合。操作集合。数据构造课程讨论的内容数据构造课程讨论的内容 数据构造课程主要讨论线性表、堆栈、队列、串、数据构造课程主要讨论线性表、堆栈、队列、串、数组、树、二叉树、图等典型的常用数据构造，在讨数组、树、二叉树、图等典型的常用数据构造，在讨论这些典型的常用数据构造时，主要从它们的逻辑构论这些典型的常用数据构造时，主要从它们的逻辑构造、存储构

8、造和数据操作三个方面进展分析讨论。造、存储构造和数据操作三个方面进展分析讨论。1.2 笼统数据类型 类型是一组值的集合。 数据类型是指一个类型和定义在这个类型上的操作集合。 在数据构造课程中，通常把在已有的数据类型根底上设计新的数据类型的过程称作数据构造设计，在这里，数据构造的含义和数据类型的含义一样。 笼统数据类型Abstract Data Type, 缩写为ADT是指一个逻辑概念上的类型和这个类型上的操作集合。 数据类型和笼统数据类型的不同之处仅仅在于：数据类型指的是高级程序设计言语支持的根本数据类型，而笼统数据类型指的是在根本数据类型支持下用户新设计的数据类型。数据构造课程主要讨论表、堆

9、栈、队列、串、数组、树、二叉树、图等典型的常用数据构造，这些典型的常用数据构培育是一个个不同的笼统数据类型。 1.3 算法和算法的时间复杂度1.3.1 算法 算法的定义和算法的表示方法 算法是描画求解问题方法的操作步骤集合。 算法要用某种言语来描画。描画算法的言语主要有三种方式：文字方式：运用文字言语伪码方式：运用类似于程序设计言语的言语程序设计言语方式：运用程序设计言语算法的性质算法的性质 算法满足以下性质：算法满足以下性质： 1输入性：具有零个或假设干个输入量；输入性：具有零个或假设干个输入量； 2输出性：至少产生一个输出或执行一个有输出性：至少产生一个输出或执行一个有意义操作；意义操作；

10、 3有限性：执行语句的序列是有限的；有限性：执行语句的序列是有限的； 4确定性：每一条语句的含义明确，无二义确定性：每一条语句的含义明确，无二义性；性； 5可执行性：每一条语句都应在有限的时间可执行性：每一条语句都应在有限的时间内完成。内完成。 程序和算法的独一区别是程序允许无限循环，而算法不允许无限循环。构成无限循环的一组语句可以如下： while(1)/循环条件永真 . /恣意语句序列 Java是一种纯面向对象程序设计言语，在Java中，一个详细的算法表示为类中的一个成员函数。带关键字static的成员函数是可以直接调用的成员函数；不带关键字static的成员函数要先定义对象，经过向对象发

11、音讯来调用成员函数。 1.3.2 算法设计目的算法设计目的 算法设计应满足以下五条目的：算法设计应满足以下五条目的： 1 正确性正确性 2 可读性可读性 3 强壮性强壮性 4 高时间效率高时间效率 5 高空间效率高空间效率 1.3.3 算法的时间复杂度分析 1 算法的时间效率度量方法 算法的时间效率反映了算法执行时间的长短。度量一个算法在计算机上的执行时间通常有如下两种方法： 1事后统计方法。计算机内部均设有计时功能，可设计一组或假设干组测试数据，然后分别运转根据不同的算法编制的程序，并比较这些程序的实践运转时间，从而确定算法时间效率的优劣。 2事前分析方法。用数学方法直接对算法的时间效率进展

12、分析。由于这种分析方法是在计算机上实践运转该算法之前进展的，所以称为事前分析方法。 根据算法编制的程序在计算机上运转时所耗费的根据算法编制的程序在计算机上运转时所耗费的时间与以下要素有关：时间与以下要素有关： a书写算法的程序设计言语书写算法的程序设计言语 b编译产生的机器言语代码质量编译产生的机器言语代码质量 c机器执行指令的速度机器执行指令的速度 d问题的规模，即算法的时间效率与算法所处置问题的规模，即算法的时间效率与算法所处置的数据元素个数的数据元素个数n的函数关系的函数关系O()函数函数 表示算法的时间效率与算法所处置的数据元素表示算法的时间效率与算法所处置的数据元素个数个数n函数关系

13、的最常用函数是函数关系的最常用函数是O()函数函数O()读做大读做大O。该函数表示算法和所处置数据元素个数。该函数表示算法和所处置数据元素个数n的数量的数量级关系。级关系。 定义定义 算法的时间复杂度算法的时间复杂度T(n) = O(f(n)当且仅当且仅当存在正常数当存在正常数c和和n0，对一切的，对一切的n(n n0)满足满足T(n) c*f(n)。 上述定义表示，算法的时间复杂度上述定义表示，算法的时间复杂度T(n)随数据随数据元素个数元素个数n的增长率和函数的增长率和函数f(n)的增长率在数量级上一的增长率在数量级上一样。样。3 算法的时间复杂度分析算法的时间复杂度分析 分析一个算法中根

14、本语句执行次数和数据元素个数分析一个算法中根本语句执行次数和数据元素个数n的函数关系，就可得出该算法的时间复杂度的函数关系，就可得出该算法的时间复杂度T(n)。4 指数级时间复杂度的问题指数级时间复杂度的问题 算法的时间复杂度是衡量一个算法好坏的重要目算法的时间复杂度是衡量一个算法好坏的重要目的。普通来说，具有多项式时间复杂度的算法，是可的。普通来说，具有多项式时间复杂度的算法，是可接受、可实践运用的算法；具有指数时间复杂度的算接受、可实践运用的算法；具有指数时间复杂度的算法，是只需当法，是只需当n足够小时才可运用的算法。足够小时才可运用的算法。 1.4 算法的空间复杂度分析 算法的空间复杂度

15、分析主要是分析算法在运转时所需求的内存空间的数量级。算法的空间复杂度通常也采用O()函数。 算法的空间复杂度分析方法和算法的时间复杂度分析方法类同。 1.5 Java言语的工具包 数据构造课程讨论的数据构造问题都是软件设计的根本构造问题。数据构造课程讨论的根本数据构造都可以设计成通用软件模块如线性表、堆栈、队列、串、二叉树等。 Java类库即Java API提供了许多系统定义的包。其中，工具包java.util包中给出了包括顺序表、单链表、堆栈、队列、串、二叉树、哈希表等功能丰富、运用方便的类。 第第2章章 线性表线性表 2.1 线性表线性表2.2 顺序表顺序表2.3 单链表单链表2.4 循环

16、单链表循环单链表2.5 双向链表双向链表2.6 仿真链表仿真链表2.7 面向对象的软件设计方法面向对象的软件设计方法本章主要知识点：本章主要知识点：线性表的定义，顺序存储构造，链式存储构造线性表的定义，顺序存储构造，链式存储构造顺序表类的设计方法，顺序表插入和删除操作的实现方法，顺序表类的设计方法，顺序表插入和删除操作的实现方法，顺序表插入和删除操作的时间复杂度顺序表插入和删除操作的时间复杂度单链表类的设计方法，单链表插入和删除操作的实现方法，单链表类的设计方法，单链表插入和删除操作的实现方法，单链表插入和删除操作的时间复杂度，顺序表和单链表单链表插入和删除操作的时间复杂度，顺序表和单链表的特

17、点对比的特点对比循环单链表和循环双向链表的构造和特点循环单链表和循环双向链表的构造和特点2.1 线性表线性表 2.1.1 线性表的定义 假设一个数据元素序列满足： 1除第一个和最后一个数据元素外，每个数据元素只需一个前驱数据元素和一个后继数据元素； 2第一个数据元素没有前驱数据元素； 3最后一个数据元素没有后继数据元素。那么称这样的数据构造为线性构造。 线性表是一种可以在恣意位置进展插入和删除数据线性表是一种可以在恣意位置进展插入和删除数据元素操作的、由元素操作的、由nn 0个一样类型数据元素个一样类型数据元素a0, a1, a2, ., an-1组成的线性构造。组成的线性构造。 一个有一个有

18、n个数据元素个数据元素a0, a1, a2, ., an-1的线性表通常的线性表通常用符号用符号a0, a1, a2, ., an-1表示，其中符号表示，其中符号ai0in-1表示第表示第i个笼统数据元素。空线性表用符号个笼统数据元素。空线性表用符号表示。表示。 数据集合数据集合 线性表的数据元素集合可以表示为序列线性表的数据元素集合可以表示为序列a0, a1, a2, ., an-1，每个数据元素的数据类型可以是恣意的，每个数据元素的数据类型可以是恣意的类类型。类类型。 操作集合操作集合 1求当前数据元素个数求当前数据元素个数length() 2插入数据元素插入数据元素insert(i, o

19、bj) 3删除数据元素删除数据元素delete(i) 4取数据元素取数据元素getData(i) 5线性表能否空线性表能否空isEmpty()2.1.2 线性表笼统数据类型线性表笼统数据类型顺序存储构造的线性表称作顺序表。顺序存储构造的线性表称作顺序表。 2.2.1 顺序表存储构造顺序表存储构造 实现顺序存储构造的方法是运用数组。实现顺序存储构造的方法是运用数组。 对于线性表，数组把线性表的数据元素存储在一对于线性表，数组把线性表的数据元素存储在一块延续地址空间的内存单元中。这样线性表中，逻辑块延续地址空间的内存单元中。这样线性表中，逻辑上相邻的数据元素在物理存储地址上也相邻，数据元上相邻的数

20、据元素在物理存储地址上也相邻，数据元素间的逻辑上的前驱、后继逻辑关系就表如今数据元素间的逻辑上的前驱、后继逻辑关系就表如今数据元素的存储单元的物理前后位置关系上。素的存储单元的物理前后位置关系上。 2.2 顺序表顺序表 顺序表的存储构造如下图。顺序表的存储构造如下图。 其中，其中，a0,a1,a2等表示顺序表中存储的数据元素，等表示顺序表中存储的数据元素，listArray表示存储数据元素的数组，表示存储数据元素的数组，maxSize表示数组表示数组的最大允许数据元素个数，的最大允许数据元素个数，size表示数组的当前数据元表示数组的当前数据元素个数。素个数。2.2.2 顺序表类顺序表类 类包

21、含成员变量和成员函数。成员变类包含成员变量和成员函数。成员变量用来表示笼统数据类型中定义的数据集量用来表示笼统数据类型中定义的数据集合，成员函数用来表示笼统数据类型中定合，成员函数用来表示笼统数据类型中定义的操作集合。顺序表类实现接口义的操作集合。顺序表类实现接口List。顺序表类的顺序表类的public成员函数主要是接口成员函数主要是接口List中定义的成员函数。中定义的成员函数。 2.2.3 顺序表的效率分析 插入和删除是顺序表中时间复杂度最高的成员函数。 插入时，主要的耗时部分是循环挪动数据元素部分。 循环挪动数据元素的效率和插入的位置i有关，最坏情况是i = 0，需挪动size个数据元

22、素；最好情况是i = size，需挪动0个数据元素。平均次数为：类似地，删除时，平均次数为：类似地，删除时，平均次数为： 2)(11)(00ninninpEniniiis21)(1)(1010ninninqEniniidl 顺序表中的其他操作都和数据元素个数n无关，因此在顺序表中插入和删除一个数据元素成员函数的时间复杂度为On。顺序表支持随机读取，因此，顺序表取数据元素的时间复杂度为O1。 顺序表的主要优点是：支持随机读取，以及内存空间利用效率高。顺序表的主要缺陷是：需求预先给出很难准确数组的最大数据元素个数，另外，插入和删除操作时需求挪动较多的数据元素。 2.3 单链表单链表指针表示一个数据

23、元素逻辑意义上的存储位置。指针表示一个数据元素逻辑意义上的存储位置。链式存储构造是基于指针实现的。我们把一个数据链式存储构造是基于指针实现的。我们把一个数据元素和一个指针称为一个结点。元素和一个指针称为一个结点。 链式存储构造是用指针把相互直接关联的结点即链式存储构造是用指针把相互直接关联的结点即直接前驱结点或直接后继结点链接起来。直接前驱结点或直接后继结点链接起来。 链式存储构造的线性表称为链表。链式存储构造的线性表称为链表。 根据结点构造链的方法不同，链表主要有单链表、根据结点构造链的方法不同，链表主要有单链表、单循环链表和循环双向链表三种。这样，一个数据元素单循环链表和循环双向链表三种。

24、这样，一个数据元素集就可以用链式存储构造来存储。集就可以用链式存储构造来存储。 2.3.1 单链表的构造单链表是构成链表的每个结点只需一个指向直接后继结点的指针。1 单链表的表示方法单链表中每个结点的构造：单链表有带头结点构造和不带头结点构造两种。我们把单链表有带头结点构造和不带头结点构造两种。我们把指向单链表的指针称为单链表的头指针。头指针所指的不指向单链表的指针称为单链表的头指针。头指针所指的不存放数据元素的第一个结点称作头结点。存放第一个数据存放数据元素的第一个结点称作头结点。存放第一个数据元素的结点称作第一个数据元素结点，或称首元结点。元素的结点称作第一个数据元素结点，或称首元结点。a

25、空链；空链；b非空链非空链 2 带头结点单链表和不带头结点单链表的比较从线性表的定义可知，线性表要求允许在恣意位置进展插入和删除。中选用带头结点的单链表时，插入和删除操作的实现方法比不用带头结点单链表的实现方法简单。设头指针用head表示，在单链表中恣意结点但不是第一个数据元素结点前插入一个新结点的方法如图2-6所示。算法实现时，首先把插入位置定位在要插入结点的前一个结点位置，然后把s表示的新结点插入单链表中。在单链表非第一个结点前插入结点过程在单链表非第一个结点前插入结点过程 要在第一个数据元素结点前插入一个新结点，假设采用不带头结点的单链表构造，那么结点插入后，头指针head就要等于新插入

26、结点s，这和在非第一个数据元素结点前插入结点时的情况不同。另外，还有一些不同情况需求思索。因此，算法对这两种情况就要分别设计实现方法。而假设采用带头结点的单链表构造，算法实现时，p指向头结点，改动的是p指针的next指针的值，而头指针head的值不变。因此，算法实现方法比较简单。在带头结点单链表中第一个数据元素结点前插入一个新结点的过程如下图。图在带头结点单链表第一个结点前插入结点过程图在带头结点单链表第一个结点前插入结点过程 2.3.2 结点类单链表是由一个一个结点组成的，因此，要设计单链表类，必需先设计结点类。结点类的成员变量有两个：一个是数据元素，另一个是表示下一个结点的对象援用即指针。

27、2.3.3 单链表类单链表类的成员变量至少要有两个：一个是头指针，另一个是单链表中的数据元素个数。但是，假设再添加一个表示单链表当前结点位置的成员变量，那么有些成员函数的设计将更加方便。2.3.4 单链表的效率分析单链表的效率分析在单链表的任何位置上插入数据元素的概率相等时，在单链表中在单链表的任何位置上插入数据元素的概率相等时，在单链表中插入一个数据元素时比较数据元素的平均次数为：插入一个数据元素时比较数据元素的平均次数为：2)(11)(00ninninpEniniiis删除单链表的一个数据元素时比较数据元素的平均次删除单链表的一个数据元素时比较数据元素的平均次数为：数为：21)(1)(10

28、10ninninqEniniidl因此，单链表插入和删除操作的时间复杂度均为On。另外，单链表取数据元素操作的时间复杂度也为On。2.3.5 顺序表和单链表的比较顺序表和单链表的比较顺序表的主要优点是支持随机读取，以及内存空间利顺序表的主要优点是支持随机读取，以及内存空间利用效率高；顺序表的主要缺陷是需求预先给出数组的最用效率高；顺序表的主要缺陷是需求预先给出数组的最大数据元素个数，而这通常很难准确作到。当实践的数大数据元素个数，而这通常很难准确作到。当实践的数据元素个数超越了预先给出的个数，会发生异常。另外，据元素个数超越了预先给出的个数，会发生异常。另外，顺序表插入和删除操作时需求挪动较多

29、的数据元素。顺序表插入和删除操作时需求挪动较多的数据元素。和顺序表相比，单链表的主要优点是不需求预先给出和顺序表相比，单链表的主要优点是不需求预先给出数据元素的最大个数。另外，单链表插入和删除操作时数据元素的最大个数。另外，单链表插入和删除操作时不需求挪动数据元素。不需求挪动数据元素。单链表的主要缺陷是每个结点中要有一个指针，因此单链表的主要缺陷是每个结点中要有一个指针，因此单链表的空间利用率略低于顺序表的。另外，单链表不单链表的空间利用率略低于顺序表的。另外，单链表不支持随机读取，单链表取数据元素操作的时间复杂度为支持随机读取，单链表取数据元素操作的时间复杂度为On；而顺序表支持随机读取，顺

30、序表取数据元素操作；而顺序表支持随机读取，顺序表取数据元素操作的时间复杂度为的时间复杂度为O1。循环单链表是单链表的另一种方式，其构造特点是链表中最后一个结点的指针不再是终了标志，而是指向整个链表的第一个结点，从而使单链表构成一个环。和单链表相比，循环单链表的优点是从链尾到链头比较方便。当要处置的数据元素序列具有环型构造特点时，适宜于采用循环单链表。2.4 循环单链表循环单链表和单链表一样，循环单链表也有带头结点构造和不带头结点构造两种，带头结点的循环单链表实现插入和删除操作时，算法实现较为方便。带头结点的循环单链表构造如下：. . .0a1a1 na( a )( b )h e a dh e

31、a da空链表；空链表；b非空链表非空链表带头结点的循环单链表的操作实现方法和带头结点的单链表的操作实现方法类同，差别仅在于：1在构造函数中，要加一条head.next = head 语句，把初始时的带头结点的循环单链表设计成图2-11 a所示的形状。2在index(i)成员函数中，把循环终了判别条件current != null改为current != head。双向链表是每个结点除后继指针外还有一个前驱指双向链表是每个结点除后继指针外还有一个前驱指针。和单链表类同，双向链表也有带头结点构造和不针。和单链表类同，双向链表也有带头结点构造和不带头结点构造两种，带头结点的双向链表更为常用；带头结

32、点构造两种，带头结点的双向链表更为常用；另外，双向链表也可以有循环和非循环两种构造，循另外，双向链表也可以有循环和非循环两种构造，循环构造的双向链表更为常用。环构造的双向链表更为常用。2.5 双向链表双向链表在双向链表中，每个结点包括三个域，分别是element域、next域和prior域，其中element域为数据元素域，next域为指向后继结点的对象援用，prior域为指向前驱结点的对象援用。图2-12为双向链表结点的图示构造。priornextdata双向链表结点的图示构造双向链表结点的图示构造图图2-13是带头结点的循环双向链表的图示构造。从图是带头结点的循环双向链表的图示构造。从图2

33、-13可见，循环双向链表的可见，循环双向链表的next和和prior各自构本钱人的循环各自构本钱人的循环单链表。单链表。带头结点的循环双向链表带头结点的循环双向链表a空链表；空链表；b非空链表非空链表0a1a. . .( a )( b )1 nah e a dh e a d在双向链表中，有如下关系：设对象援用p表示双向链表中的第i个结点，那么p.next表示第i+1个结点，p.next.prior仍表示第i个结点，即p.next.prior = p；同样地，p.prior表示第i-1个结点，p.prior.next仍表示第i个结点，即p.prior.next = p。图2-14是双向链表上述关

34、系的图示。 图图2-14双向链表的关系双向链表的关系循环双向链表的插入过程如图2-15所示。图中的指针p表示要插入结点的位置，s表示要插入的结点，、表示实现插入过程的步骤。0aia.1 na.x1 ia. pheads图图2-15 循环双向链表的插入过程循环双向链表的插入过程循环双向链表的删除过程如图循环双向链表的删除过程如图2-16所示。图中的指针所示。图中的指针p表示要插入结点的位置，、表示实现删除过程的表示要插入结点的位置，、表示实现删除过程的步骤。步骤。. . .1 ia. . .1 na 1 nah e a dp1 iaia 循环双向链表的删除过程循环双向链表的删除过程2.6仿真链表

35、仿真链表在链式存储构造中，我们实现数据元素之间的次序在链式存储构造中，我们实现数据元素之间的次序关系依托指针。我们也可以用数组来构造仿真链表。方关系依托指针。我们也可以用数组来构造仿真链表。方法是在数组中添加一个或两个法是在数组中添加一个或两个int类型的变量域，这类型的变量域，这些变量用来表示后一个或前一个数据元素在数组中些变量用来表示后一个或前一个数据元素在数组中的下标。我们把这些的下标。我们把这些int类型变量构造的指针称为仿真指类型变量构造的指针称为仿真指针。这样，就可以用仿真指针构造仿真的单链表或仿针。这样，就可以用仿真指针构造仿真的单链表或仿真的双向链表。真的双向链表。a常规单链表

36、；常规单链表；b仿真单链表一；仿真单链表一；c仿真单链表二仿真单链表二2.7 面向对象的软件设计方法面向对象的软件设计方法 面向对象软件设计方法是一种和人类认识事物、分析面向对象软件设计方法是一种和人类认识事物、分析事物方法一致的软件设计方法。不仅如此，面向对象设事物方法一致的软件设计方法。不仅如此，面向对象设计方法的模块化软件、数据封装、信息隐藏等特点，还计方法的模块化软件、数据封装、信息隐藏等特点，还可以使软件设计可以像其他工业产品一样，可以大规模可以使软件设计可以像其他工业产品一样，可以大规模协作开发。协作开发。 模块化软件设计的根本思想是：把根底软件设计成可模块化软件设计的根本思想是：

37、把根底软件设计成可反复运用的模块，这些模块提供外部调用的接口，其他反复运用的模块，这些模块提供外部调用的接口，其他程序经过接口运用这些根底软件模块。这样，软件工业程序经过接口运用这些根底软件模块。这样，软件工业将摆脱了小作坊任务方式，像现代的其他工业一样，可将摆脱了小作坊任务方式，像现代的其他工业一样，可以进展大规模的协作消费或开发。以进展大规模的协作消费或开发。第第3章章 堆栈和队列堆栈和队列 3.1 堆栈堆栈3.2 堆栈的运用堆栈的运用3.3 队列队列3.4 优先级队列优先级队列本章主要知识点：本章主要知识点： 堆栈的根本概念，堆栈的用途堆栈的根本概念，堆栈的用途 顺序堆栈类的设计方法，链

38、式堆栈类的设计方法顺序堆栈类的设计方法，链式堆栈类的设计方法 队列的根本概念，队列的用途队列的根本概念，队列的用途 顺序循环队列的根本实现原理，顺序循环队列的队空顺序循环队列的根本实现原理，顺序循环队列的队空和队满判别方法，顺序循环队列类的设计方法和队满判别方法，顺序循环队列类的设计方法 链式堆栈类的设计方法链式堆栈类的设计方法 优先级队列的概念，优先级队列的用途，顺序优先级优先级队列的概念，优先级队列的用途，顺序优先级 队列的入队列和出队列操作设计方法队列的入队列和出队列操作设计方法 3.1 堆栈堆栈3.1.1 堆栈的根本概念堆栈的根本概念堆栈也简称作栈是一种特殊的线性表，堆栈的堆栈也简称作

39、栈是一种特殊的线性表，堆栈的数据元素以及数据元素间的逻辑关系和线性表完全一样，数据元素以及数据元素间的逻辑关系和线性表完全一样，其差别是线性表允许在恣意位置进展插入和删除操作，而其差别是线性表允许在恣意位置进展插入和删除操作，而堆栈只允许在固定一端进展插入和删除操作。堆栈只允许在固定一端进展插入和删除操作。 堆栈中允许进展插入和删除操作的一端称为栈顶，堆栈中允许进展插入和删除操作的一端称为栈顶，另一端称为栈底。堆栈的插入和删除操作通常称为进栈或另一端称为栈底。堆栈的插入和删除操作通常称为进栈或入栈，堆栈的删除操作通常称为出栈或退栈。入栈，堆栈的删除操作通常称为出栈或退栈。从输入和输出数据元素的

40、位置关系看，堆栈的功能和一种火车调度安装的功能类同。3.1.2 堆栈笼统数据类型堆栈笼统数据类型数据集合数据集合 堆栈的数据集合可以表示为堆栈的数据集合可以表示为a0,a1,an-1，每个数据，每个数据元素的数据类型可以是恣意的类类型。元素的数据类型可以是恣意的类类型。操作集合操作集合 1入栈入栈push(obj)：把数据元素：把数据元素obj插入堆栈。插入堆栈。2出栈出栈pop()：出栈：出栈, 删除的数据元素由函数前往。删除的数据元素由函数前往。3取栈顶数据元素取栈顶数据元素getTop()：取堆栈当前栈顶的数：取堆栈当前栈顶的数据元素并由函数前往。据元素并由函数前往。4非空否非空否not

41、Empty()：假设堆栈非空那么函数前往：假设堆栈非空那么函数前往true，否那么函数前往，否那么函数前往false。 3.1.3 顺序堆栈1 顺序堆栈的存储构造顺序存储构造的堆栈称作顺序堆栈。 顺序堆栈的存储构造表示图如下图。 3.1.4 链式堆栈链式堆栈链式存储构造的堆栈称作链式堆栈。链式存储构造的堆栈称作链式堆栈。1 链式堆栈的存储构造链式堆栈的存储构造和单链表一样，链式堆栈也是由一个个结点组成和单链表一样，链式堆栈也是由一个个结点组成的，每个结点由两个域组成，一个是存放数据元素的的，每个结点由两个域组成，一个是存放数据元素的数据元素域数据元素域element，另一个是存放指向下一个结点

42、的，另一个是存放指向下一个结点的对象援用即指针域对象援用即指针域next。堆栈有两端，插入数据元素和删除数据元素的一堆栈有两端，插入数据元素和删除数据元素的一端为栈顶，另一端为栈底。链式堆栈都设计成把接近端为栈顶，另一端为栈底。链式堆栈都设计成把接近堆栈头堆栈头head的一端定义为栈顶。的一端定义为栈顶。依次向链式堆栈入栈数据元素a0, a1, a2, ., an-1后，链式堆栈的表示图如下图。 堆栈是各种软件系统中运用最广泛的数据构造之一。括号匹配和表达式计算是编译软件中的根本问题，其软件设计中都需求运用堆栈。3.2.1 括号匹配问题3.2.2 表达式计算问题3.2 堆栈的运用堆栈的运用3.

43、3 队列队列3.3.1 队列的根本概念队列的根本概念 队列简称作队也是一种特殊的线性表，队列的队列简称作队也是一种特殊的线性表，队列的数据元素以及数据元素间的逻辑关系和线性表完全一数据元素以及数据元素间的逻辑关系和线性表完全一样，其差别是线性表允许在恣意位置插入和删除，而样，其差别是线性表允许在恣意位置插入和删除，而队列只允许在其一端进展插入操作在其另一端进展删队列只允许在其一端进展插入操作在其另一端进展删除操作。除操作。 队列中允许进展插入操作的一端称为队尾，允许进队列中允许进展插入操作的一端称为队尾，允许进展删除操作的一端称为队头。队列的插入操作通常称展删除操作的一端称为队头。队列的插入操

44、作通常称作入队列，队列的删除操作通常称作出队列。作入队列，队列的删除操作通常称作出队列。 以下图是一个依次向队列中插入数据元素以下图是一个依次向队列中插入数据元素a0,a1,.,an-1后的表示图，其中，后的表示图，其中，a0是当前队头数据元素，是当前队头数据元素，an-1是当是当前队尾数据元素。前队尾数据元素。0a1a2a. . .1 na出队 头入队 尾3.3.2 队列的笼统数据类型队列的笼统数据类型1 数据集合数据集合 队列的数据集合可以表示为队列的数据集合可以表示为a0,a1,an-1，每个数据元素的数据，每个数据元素的数据类型可以是恣意的类类型。类型可以是恣意的类类型。2 操作集合操

45、作集合 1入队列入队列append(obj)：把数据元素：把数据元素obj插入队尾。插入队尾。 2出队列出队列delete()：把队头数据元素删除并由函数前往。：把队头数据元素删除并由函数前往。 3取队头数据元素取队头数据元素getFront()：取队头数据元素并由函数前往。：取队头数据元素并由函数前往。 4非空否非空否notEmpty()：非空否。假设队列非空，那么函数前往：非空否。假设队列非空，那么函数前往true，否那么函数前往，否那么函数前往false。队列笼统数据类型的队列笼统数据类型的Java接口定义如下：接口定义如下：public interface Queuepublic vo

46、id append(Object obj) throws Exception;public Object delete() throws Exception;public Object getFront() throws Exception;public boolean notEmpty();3.3.3 顺序队列1 顺序队列的存储构造 以下图是一个有6个存储空间的顺序队列的动态表示图，图中front指示队头，rear指示队尾。 43210=5frontrearCBA432105front=rear=C432105front=rear=EDC432105front=rear=(a)(b)(c)(

47、d)2 顺序队列的“假溢出问题 顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进展入队列操作的溢出称作假溢出。 EDC43210F5f r o n t =6r e a r =顺序循环队列的根本原理顺序循环队列的根本原理 假溢出是由于队尾假溢出是由于队尾rear的值和队头的值和队头front的值不的值不能由所定义数组下界值自动转为数组上界值而产生的。能由所定义数组下界值自动转为数组上界值而产生的。因此，处理的方法是把顺序队列所运用的存储空间构因此，处理的方法是把顺序队列所运用的存储空间构呵斥一个逻辑上首尾相连的循环队列。呵斥一个逻辑上首尾相连的循环队列。 当当rear和和front到达

48、到达maxSize-1后，再加后，再加1就自动就自动到到0。这样，就不会出现顺序队列数组的头部已空出。这样，就不会出现顺序队列数组的头部已空出许多存储空间，但队尾却因数组下标越界而引起溢出许多存储空间，但队尾却因数组下标越界而引起溢出的假溢出问题。的假溢出问题。4 顺序循环队列的队空和队满判别问题 顺序循环队列的队列满和队列空形状a初始化形状；b队列满形状；c队列空形状154032EDFABC154032rear=0front=0rear=0front=0154032rear=0front=0(a)(b)(c) 处理顺序循环队列的队列满和队列空形状判别问题通常有三种方法： 1少用一个存储空间

49、当少用一个存储空间时，以队尾rear加1等于队头 front为队列满的判别条件，即队列满的判别条件此时为： (rear + 1) % maxSize = front 队列空的判别条件依然为： rear = = front2设置一个标志位 添加一个标志位。设标志位为tag，初始时置tag=0；每当入队列操作胜利就置tag=1；每当出队列操作胜利就置tag=0。那么队列空的判别条件为： rear = front & tag=0 队列满的判别条件为： rear = = front & tag= =13设置一个计数器设置一个计数器 添加一个计数器。设计数器为添加一个计数器。设计数器为c

50、ount，初始时置，初始时置count=0；每当入队列操作胜利就使；每当入队列操作胜利就使count加加1；每当出；每当出队列操作胜利就使队列操作胜利就使count减减1。这样，该计数器不仅具有。这样，该计数器不仅具有计数功能，而且还具有像标志位一样的标志作用，那计数功能，而且还具有像标志位一样的标志作用，那么此时队列空的判别条件为：么此时队列空的判别条件为： count = 0 队列满的判别条件为：队列满的判别条件为： count 0 & rear = front 3.3.4 顺序循环队列类顺序循环队列类3.3.5 链式队列链式队列 链式存储构造的队列称作链式队列。链式存储构造的队列

51、称作链式队列。 1 链式队列的存储构造链式队列的存储构造 3.4 优先级队列优先级队列优先级队列是带有优先级的队列。优先级队列是带有优先级的队列。 用顺序存储构造实现的优先级队列称作顺序优先级队列。用顺序存储构造实现的优先级队列称作顺序优先级队列。 用链式存储构造存储的优先级队列称作链式优先级队列。用链式存储构造存储的优先级队列称作链式优先级队列。 3.4.1 顺序优先级队列类顺序优先级队列类 顺序优先级队列和顺序循环队列相比主要有两点不同：顺序优先级队列和顺序循环队列相比主要有两点不同：1对于顺序优先级队列来说，出队列操作不是把队头数据元对于顺序优先级队列来说，出队列操作不是把队头数据元素出

52、队列，而是把队列中优先级最高的数据元素出队列。素出队列，而是把队列中优先级最高的数据元素出队列。 2对于顺序优先级队列来说，数据元素由两部分组成，一部对于顺序优先级队列来说，数据元素由两部分组成，一部分是原先意义上的数据元素，另一部分是优先级。通常设计优分是原先意义上的数据元素，另一部分是优先级。通常设计优先级为先级为int类型的数值，并规定数值越小优先级越高。类型的数值，并规定数值越小优先级越高。 3.4.2 优先级队列的运用 操作系统中的进程管理软件中就运用了优先级队列。操作系统中运用一个优先级队列来管理进程。当优先级队列中有假设干个进程排队等待系统呼应，并且CPU资源空闲时，进程管理系统

53、就可从优先级队列中找出优先级最高的进程首先出队列，从而既到达了当系统忙碌时，一切进程都排队等待，又到达了实时性要求高的进程先被效力的双重要求。第第4章章 串串 4.1 串的根本概念及其笼统数据串的根本概念及其笼统数据 4.2 串的存储构造串的存储构造 4.3 串类串类 4.4 串的方式匹配算法串的方式匹配算法本章主要知识点：本章主要知识点：串的根本概念串的根本概念串的存储构造串的存储构造串类的设计方法，主要是拷贝、插入子串和删除子串串类的设计方法，主要是拷贝、插入子串和删除子串的设计方法的设计方法串的方式匹配算法，包括串的方式匹配算法，包括Brute-Force算法和算法和KMP算算法法4.1

54、 串的根本概念及其笼统数据类型串的根本概念及其笼统数据类型4.1.1 串的根本概念串的根本概念 串也称作字符串是由串也称作字符串是由nn0个字符组成的有限个字符组成的有限序列。序列。 一个串中恣意个延续的字符组成的子序列称为该串的一个串中恣意个延续的字符组成的子序列称为该串的子串。子串。 包含子串的串称为该子串的主串。包含子串的串称为该子串的主串。 一个字符在一个串中的位置序号为大于等于一个字符在一个串中的位置序号为大于等于0的正整的正整数称为该字符在串中的位置。当且仅当这两个串的值数称为该字符在串中的位置。当且仅当这两个串的值完全相等时，称这两个串相等。完全相等时，称这两个串相等。4.1.2

55、 串的笼统数据类型 数据集合：串的数据集合可以表示为字符序列s0, s1, , sn-1，每个数据元素的数据类型为字符类型。 操作集合： 1取字符charAt(index) ：取index下标的字符前往。 2求长度length()：前往串的长度。 3比较compareTo(anotherString)：比较当前对象串和串anotherString的Unicode码值的大小。 4取子串substring(beginIndex, endIndex)：取当前对象串中从beginIndex下标开场、至endIndex下标的前一下标止的子串 5衔接衔接concat(str)：把串：把串str衔接到当前对

56、象串的末尾。衔接到当前对象串的末尾。6插入子串插入子串insert(str, pos)：在当前对象串的第：在当前对象串的第pos个个字符前插入子串字符前插入子串str。7删除子串删除子串delete(beginIndex, endIndex)：删除当前：删除当前对象串中从对象串中从beginIndex下标开场、至下标开场、至endIndex下标的下标的前一下标止的子串前一下标止的子串 。8输出串值输出串值myPrint()：输出当前对象的串值。：输出当前对象的串值。9查找子串查找子串index(subStr, start)：在当前对象串的：在当前对象串的start下标开场，查找能否存在子串下标

57、开场，查找能否存在子串subStr。 4.2 串的存储构造串的存储构造 1 串的顺序存储构造 串的顺序存储构培育是用字符类型数组存放串的一切字符。 表示串的长度通常有两种方法： 1设置一个串的长度参数。 2在串值的末尾添加终了标志。 串值长度的第一种表示方法下，串的成员变量应包括如下两项： char value; int count; 其中，value为存储串值的字符类型数组名，count表示串值的长度。 2 串的链式存储构造 串的链式存储构培育是把串值分别存放在构成链表的假设干个结点的数据元素域上。 有单字符结点链和块链两种。 单字符结点链就是每个结点的数据元素域只包括一个字符。 块链就是每

58、个结点的数据元素域包括假设干个字符。4.3 串类串类4.3.1 MyString类类4.3.2 MyString类的测试类的测试4.3.3 MyStringBuffer类类4.3.4 MyStringBuffer类的测试类的测试4.4 串的方式匹配算法串的方式匹配算法4.4.1 Brute-Force算法1从主串s的第一个字符开场和方式串t的第一个字符比较,假设相等那么继续比较后续字符；2假设主串s的第一个字符和方式串t的第一个字符比较不相等，那么从主串s的第二个字符开场重新与方式串t的第一个字符比较，假设相等那么继续比较后续字符 3假设主串假设主串s的第二个字符与方式串的第二个字符与方式串t

59、的第一个字符比较的第一个字符比较不相等，那么从主串不相等，那么从主串s的第三个字符开场重新与方式串的第三个字符开场重新与方式串t的第一个字符比较；的第一个字符比较；4如此不断继续。假设存在方式串如此不断继续。假设存在方式串t中的每个字符依次中的每个字符依次和主串和主串s中的一个延续字符序列相等，那么方式匹配胜中的一个延续字符序列相等，那么方式匹配胜利，函数前往方式串利，函数前往方式串t的第一个字符在主串的第一个字符在主串s中的下标；中的下标；假设比较完主串假设比较完主串s的一切字符序列，不存在一个和方式的一切字符序列，不存在一个和方式串串t相等的子串，那么方式匹配失败，函数前往相等的子串，那么

60、方式匹配失败，函数前往-1。 设主串设主串s=“cddcdc,方式串方式串t=“cdc,方式匹配过程如图：方式匹配过程如图：第一次匹配s = c d d c d ct = c d ci=2j=2失败第二次匹配i=1j=0失败第三次匹配i=2j=0失败第四次匹配i=5j=2成功 s = c d d c d ct = c d c s = c d d c d ct = c d c s = c d d c d ct = c d c Brute-Force算法方式匹配的普通性过程如图 ：4.4.2 KMP算法Brute-Force算法的缺陷以及处理方法分析 KMP算法是在Brute-Force算法根底上的改良算法。KMP算法