第四章Java常用数据结构.ppt

第四章算法与数据结构（数组、向量及字符处理）,1、数组（Array）2、向量（Vector）3、字符处理（String）4、算法：递归、排序、查找5、复杂数据结构,程序算法数据结构,软件：刻画现实世界，解决现实世界中的问题语言：实现的工具算法：问题的解的描述数据结构：现实世界的数据模型程序就是在数据的某些特定的表示方式和结构的基础上对抽象算法的具体表述。,瑞士科学家沃思（NiklausWirth，1984年图灵奖得主）在1976年出版了著名的程序算法数据结构一书。,不了解施加于数据上的算法就无法决定如何构造数据，反之，算法的结构和选择却常常在很大程度上依赖于作为基础的数据结构。简而言之，程序的构成（算法）与数据结构是两个不可分割地联系在一起的问题。,1、数组一维数组：定义,一维数组的定义方式为：typearrayName；,其中类型(type)可以为Java中任意的数据类型，包括基本类型和类类型，数组名arrayName为一个合法的标识符，指明该变量是一个数组类型变量。,例如：intintArray；声明了一个整型数组，数组中的每个元素为整型数据。,我们还可以定义一个类类型的数组，例如：DatedateArray；声明了一个容纳复合数据类型Date的数组。,1、数组一维数组：定义,与C、C+不同，Java在数组的定义中并不为数组元素分配内存，因此中不用指出数组中元素的个数，即数组长度，而且对于如上定义的一个数组是不能访问它的任何元素的。必须经过初始化后，才能应用数组的元素。,除了这种定义数组的方式之外，java语言还提供了其他的定义形式，如下所示：typearrayName；,1、数组一维数组：定义,对于以上举出的例子，我们也可以这样定义：intintArray；DatedateArray;,一维数组定义之后，必须经过初始化才可以引用。数组的初始化分为静态初始化和动态初始化两种：,1、数组一维数组：初始化,静态初始化：在定义数组的同时对数组元素进行初始化，例如：intintArray=1,2,3,4;/定义了一个含有4个/元素的int型数组。,动态初始化：使用运算符new为数组分配空间，对于简单类型的数组，其格式如下：typearrayName=newtypearraySize;typearrayName=newtypearraySize;,1、数组一维数组：初始化,对于复合类型的数组，需要经过两步空间分配。首先：typearrayName=newtypearraySize;然后：arrayName0=newtype(paramList);arrayNamearraySize-1=newtype(paramList);,例如：StringstringArrar;/定义一个String类型的数组stringArray=newString3;/给数组stringArray分配3个应用空间，初始化每个引用值为nullstringArray0=newString(“how”);stringArray1=newString(“are”);stringArray2=newString(“you”);,初始化各数组元素,1、数组一维数组：初始化,当定义了一个数组，并用运算符new为它分配了内存空间后，就可以引用数组中的每一个元素了。元素的引用方式为：arrayNameindex,1、数组一维数组：引用,index为数组下标，可以是整型常数或表达式，如：arrayName1,arrayNamei,arrayName6*i等。下标是0序的，即从0开始，一直到数组长度减1。,另外，与C、C+中不同，Java对数组元素要进行越界检查以保证安全性。同时，对于每个数组都有一个属性length指明它的长度，例如：intArray.length指明数组intArray的长度例:模拟抽彩游戏,1、数组一维数组：边界检查,PublicclassLotteryDrawing/模拟抽彩游戏publicstaticvoidmain(Stringargs)Stringinput=JOptionPane.showInputDialog(Howmanynumbersdoyouneedtodraw?);intk=Integer.parseInt(input);input=JOptionPane.showInputDialog(Whatisthehighestnumberyoucandraw?);intn=Integer.parseInt(input);/numbers用来存放123.nintnumbers=newintn;for(inti=0;inumbers.length;i+)numbersi=i+1;/result用不存放选取出的数intresult=newintk;for(inti=0;iresult.length;i+)/在0-N-1之间产生选取出的数intr=(int)(Math.random()*n);,/将选出的数放入resultresulti=numbersr;/movethelastelementintotherandomlocationnumbersr=numbersn-1;n-;/将result排序输出Arrays.sort(result);System.out.println(Betthefollowingcombination.Itllmakeyourich!);for(inti=0;iresult.length;i+)System.out.println(resulti);System.exit(0);,在任何语言中，多维数组都被看作数组的数组。比如二维数组是一个特殊的一维数组，其每一个元素又是一个一维数组。我们主要以二维数组为例来说明，高维数组与此类似。,1、数组多维数组,二维数组的定义方式typearrayName；例如：intintArray；,1、数组二维数组：定义,也可以采用另一种定义方式：typearrayName;与一维数组一样，这时对数组元素也没有分配内存空间，同样要使用运算符new来分配内存，然后才可以访问每个元素。,二维数组的初始化也分为静态和动态两种。静态初始化：在定义数组的同时为数组分配空间。intintArray=1,2,2,3,3,4;不必指出数组每一维的大小，系统会根据初始化时给出的初始值的个数自动算出数组每一维的大小。,1、数组二维数组：初始化,动态初始化：对高维数组来说，分配内存空间有下面两种方法：1.直接为每一维分配空间，如：typearrayName=newtypearraylength1arraylength2例如：inta=newint23；,1、数组二维数组：初始化,2.从最高维开始（而且必须从最高维开始），分别为每一维分配空间，如：Strings=newString2;s0=newString2;s1=newString3;s00=newString(“Good”);s01=newString(“Luck”);s10=newString(“to”);s11=newString(“you”);s12=newString(“!”);,1、数组二维数组：初始化,二维数组的引用对二维数组中每个元素，引用方式为：arrayNameindex1index2其中index1和index2为数组下标，为整型常数和表达式，都是0序的。,1、数组二维数组：引用及示例,数组是用来表达一组同类型数据的数据结构,1、数组java.util.Arrays,在Java中数组是定长的，数组的大小不会动态变化,数组变量的值是数组对象实例的引用,在java.util包中的Arrays类提供了一些操作数组的方法,在java.util包中的Vector提供了动态变长数组的功能，Vector的容量可以随着需要变化,intbinarySearch(typea,typekey)数组a必须已经排序，否则返回值无意义当数组a中有重复的值时，该方法返回的值不确定如果key存在，则返回它在数组a中的位置如果不存在，则返回它的“-(插入位置-1)”voidfill(typea,typeval)voidfill(typea,intfromIndx,inttoIndex,typeval)包括afromIndx，但不包括atoIndexfromIndx=toIndex时，范围是一个空的范围,1、数组java.util.Arrays,booleanequals(typea,typea2)两个数组大小相同，并且每一个元素相等两个null数组是相等的,1、数组java.util.Arrays,voidsort(typea)voidsort(typea,intfromIndx,inttoIndex)voidsort(typea,Comparatorc)voidsort(typea,intfromIndx,inttoIndex,Comparatorc)包括afromIndx，但不包括atoIndexfromIndx=toIndex时，范围是一个空的范围排序算法都具有n*log(n)的计算复杂性，效率高排序算法都保证稳定，即排序算法不会改变相等元素的顺序对不同类型的数组，算法的实现并不完全相同可以用自己的Comparator对象声明自定义的顺序,1、数组java.util.Arrays,java.lang.Systemvoidarraycopy(Objectsrc,intsrc_position,Objectdst,intdst_position,intlength)范围不能越界可对任何同类型的数组进行复制数组复制过程中做严格的类型检查更详细的内容参见JDK文档,1、数组数组的复制,向量(Vector)是java.util类包提供的一个工具类。它对应于类似数组的顺序存储的数据结构，但是具有比数组更强大的功能。它是允许不同类型元素共存的变长数组。每个Vector类的对象可以表达一个完整的数据序列。Vector类的对象不但可以保存顺序的一列数据，而且还提供了许多有用的方法来操作和处理这些数据。另外，Vector类对象所表达的序列中元素的个数是可变的，即Vector实现了变长数组。,2、向量,Java中的数组只能保存固定数目的元素，且必须把所有需要的内存单元一次性的申请出来，而不能先创建数组再追加数组元素数量，为了解决这个问题Java中引入了向量类Vector。Vector也是一组对象的集合，但相对于数组，Vector可以追加对象元素数量，可以方便的修改和维护序列中的对象。,2、向量,向量比较适合在如下情况下使用：1.需要处理的对象数目不定，序列中的元素都是对象或可以表示为对象。2.需要将不同类的对象组合成一个数据序列。3.需要做频繁的对象序列中元素的插入和删除。4.经常需要定位序列中的对象和其他查找操作。5.在不同的类之间传递大量的数据。Vector类的方法相对于数组要多一些，但是使用这个类也有一定的局限性，例如其中的对象不能是简单数据类型等。,2、向量,Vector类有三个构造函数：Vector()：构造一个空的向量Vector(intcapacity)：以指定的存储容量构造一个空的向量Vector(intcapacity,intcapacityIncrement)：以指定的存储容量和容量增量构造一个空的Vector。例如：VectorMyVector=newVector(100,50)；这个语句创建的MyVector向量序列初始有100个元素的空间，以后一旦使用殆尽则以50为单位递增，使序列中元素的个数变化成150，200，。在创建Vector序列时，不需要指明序列中元素的类型，可以在使用时确定。,2、向量创建向量类的对象,有两种添加元素的方法：addElement(Objectobj)：将新元素添加到序列尾部。insertElementAt(Objectobj,intindex)：将新元素插入到指定位置。,2、向量向向量序列中添加元素,下面是使用这两种方法的例子：,VectorMyVector=newVector()；for(inti=1;i1n!=n*(n-1)!;适合用递归方法求解的问题有一个初始状态后续的情况可由前面的状态推出如Fibonacci数列F1=F2=1;Fn=Fn-1+Fn-2(n=3),递归与循环,longFibonacci(intn)if(n=1|n=2)return1;elsereturnFactorial(n-1)+Factorial(n-2);,longFibonacci(intn)inti;longf1,f2,fn;if(n=1|n=2)return1;f1=1;f2=1;for(i=3;i=n;i+)fn=f1+f2;f1=f2;f2=fn;returnfn;,4、算法：递归、排序、查找递归,递归问题欣赏河内塔（HanoiTower）问题：这是一个流传很久的游戏。1.有三根杆子A,B,C。A杆上有n只碟子2.每次移动一块碟子,小的只能叠在大的上面3.把所有碟子从A杆经C杆全部移到B杆上.递归求解：1.若只有一只碟子，直接将它从A杆移到B杆；2.把n-1只碟子从A杆经B杆移动到C杆，将A杆上第n只碟子移到B杆；然后再将n-1只碟子从C杆经A杆移到B杆。,4、算法：递归、排序、查找递归,此外，递归是人工智能语言Lisp/Prolog等进行问题求解的基本手段。,递归问题欣赏8皇后问题：把8个皇后放在8x8的棋盘上，使得任何一个都不将其他7个的军。骑士巡游问题：给出一个nxn的棋盘，一位骑士按国际象棋的规则移动放在第（0,0）格里，找出一种可以走遍整个棋盘的方案（如果存在的话）。即做n2-1次移动，使得棋盘上每个格子都恰好只被访问一次。,4、算法：递归、排序、查找递归,4、算法：递归、排序、查找排序,排序是指对一些数据信息的重新组织，通常是对一个数组进行重新操作，使得信息由大到小（降序）或者由小到大（升序）存储。要求排序是很一种基本的需要。我们所感兴趣的是如何寻找到一个好的办法来进行排序。,就地排序算法：不增加新的存储空间1、插入排序法（InsertSort）将一个数插入到序列中的合适位置。2、选择排序法（SelectionSort）每次把最小（大）的元素交换到最前面。3、冒泡排序法（BubbleSort）比较并交换相邻的元素，直到所有元素都被放到合适的位置。,4、算法：递归、排序、查找排序,4、算法：递归、排序、查找排序：插入排序（思想）,4、算法：递归、排序、查找排序：插入排序（算法）,inta=19,2,35,-6,-12,5,23,16,9,0;inti,j,k;intx;for(i=1;i=0,Worstcase递增/递减Comparison=n(n-1)/2Average=n(n-1)/4SpaceNone,4、算法：递归、排序、查找排序：插入排序（分析）,4、算法：递归、排序、查找排序：选择排序（算法）,intnum=19,2,35,-6,-12,5,23,16,9,0;inti,j,k;intx;for(i=0;inum.length-1;i+)/最后一个元素无需比较k=i;x=numi;for(j=i+1;jn2SpaceNone,4、算法：递归、排序、查找排序：选择排序（分析）,4、算法：递归、排序、查找排序：冒泡排序（算法）,inta=19,2,35,-6,-12,5,23,16,9,0;inti,j,k;intx;for(i=1;i=i;j-)if(aj-1aj)x=aj-1;aj-1=aj;aj=x;,Worstcase递增/递减Comparison=n(n-1)/2-n2Averagecase=n2/4-n2SpaceNone,4、算法：递归、排序、查找排序：冒泡排序（分析）,其他就地排序算法：前面三种算法的变种快速排序算法（QuickSort）,4、算法：递归、排序、查找排序：其他就地排序算法,待排序的数据（N个）放在一个一维数组中，另设一个10*N的二维数组，设待排序数据中最大的数是4位，则排序需要4轮扫描，每轮包括分散扫描和集中扫描：分散扫描将数据分散到二维数组中。求出个待排序数据的个位数，以此个位数位行下标，保存到二维数组相应的行中。如104，24将保存到第三行中（0序），90则被保存到第一行中。如果两个数的个位数相同，则保存到同一行中，但它们列下标的先后顺序则由它们在一维数组中的先后顺序决定。集中扫描将二维数组中的数据按照行优先顺序返回到一维数组中。如上面的三个数据返回到一维数组中后成为：90，104，24。第二轮扫描针对十位数做分散扫描和集中扫描，扫描后一维数组中的数据为：104，24，90。第三轮针对百位数，扫描后得到最终排序：24，90，104。,4、算法：递归、排序、查找排序：桶排序（思想）,用空间换时间，效率高,4、算法：递归、排序、查找排序：桶排序（分析）,4、算法：递归、排序、查找查找,查找是利用给出的匹配关键值，在一个数据集合或数据序列中找出符合匹配关键值的一个或一组数据的过程。顺序查找：最简单的查找算法，程序从数据序列的第一个数据开始，逐个与匹配关键值比较，直到找到一个或所有的匹配数据为止（也可能找不到）。顺序查找不要求待查找的数据序列是否已经排好序。二分查找：当待查找数据序列中数据比较多时，顺序查找的效率将十分低。二分查找可以提高查找效率，但要求待查找的数据序列已经排好序。以序列中间数据为界将待查找的数据序列分成两个子序列，比较匹配关键值与中间数据的大小，再确定去哪个子序列中继续查找。这样逐步缩小范围，直到找到所需数据。,线性表堆栈（Stack）队列（Queue）列表（List）链表（LinkedList）集合（Set）树（Tree）图（Graph）,5、复杂数据结构,线性表数据元素（节点）的有限序列叫线性表，数组其实也是一种线性表,也叫顺序表。（a1,a2,an-1,an）a1为首元，an为末元，n叫线性表的长度ai的后继是ai+1,i=1,n-1.an没有后继。ai的前驱是ai-1,i=2,n.a1没有前驱。ai可以是基本数据类型也可以是引用数据类型。没有数据的线性表叫空表。空表的长度n=0。线性表是最简单的也是最基本的数据结构。不同的线性表具有不同的约束和不同的行为。,5、复杂数据结构线性表,堆栈（Stack）的概念LIFO（LastInFirstOut，后进先出）的线性表，元素的插入和删除必须在栈顶进行，不能在栈底进行。对堆栈的操作push(x)：在栈的顶部插入元素，简称入栈；pop()：删除栈顶的元素，简称出栈。,5、复杂数据结构线性表：堆栈（Stack）,5、复杂数据结构线性表：堆栈（Stack）,5、复杂数据结构线性表：堆栈（Stack）,堆栈的应用求表达式的值表达式的中缀表示法：31+2*(5-3)表达式的后缀表示法：31253-*+利用后缀表示法求表达式的值：顺序扫描表达式的后缀表示，遇到操作数则将操作数入栈，遇到运算符则将栈顶的两个操作数取出进行计算，并将计算结果入栈。递归、例外处理等也都是利用堆栈机制来实现。,5、复杂数据结构线性表：堆栈（Stack）,队列（Queue）是与堆栈不同的另一类数据结构。在一个队列中，最先入列的数据最先出列（先进先出），这与先入后出的堆栈形成了对比。在应用软件开发实践中，经常涉及到“先进先处理”的案例。比如，红绿灯下的车辆调度，飞机等候着陆时的机场跑道的指挥控制等。服务行业也有许多相同的情况，比如在一家银行或超市，顾客在服务员（出纳、收银员等）的前面排队的情况。,5、复杂数据结构线性表：队列（Queue）,5、复杂数据结构线性表：链表（LinkedList）,单链表循环链表双向链表双向循环链表,5、复杂数据结构线性表：链表单链表,单链表,插入,删除,AH:1-10 x6+2x8+7x14,BH:-x4+10 x6-3x10+8x14+4x18,单链表的应用：多项式加法,5、复杂数据结构线性表：链表单链表,5、复杂数据结构线性表：链表双向链表,双向链表,插入,删除,双向链表的应用：稀疏矩阵,5、复杂数据结构线性表：链表双向链表,5、复杂数据结构树（Tree）,与线性表不同，每个节点的后续可能大于1个。树(Tree)的定义树是n（n=0）个节点的有限集合，有且仅有一个称为根的节点；当n1时，其余节点可以分为m个互不相交的集合，其中每个集合又是一棵树，称为树的子树递归的定义现实世界中的树家谱目录,5、复杂数据结构树（Tree）,树的示例,A,B,C,D,E,节点(Node)节点的度(Degree)叶子（终端节点）非终端节点树的深度孩子(Child)双亲(Parent)兄弟(Sibling),5、复杂数据结构树（Tree）：树的相关概念,InitiateRootParentChildRight_SiblingLeft_SiblingCreateTreeInsertChildDeleteChildTraverseClear,5、复杂数据结构树（Tree）：树的操作,二叉树(BinaryTree)每个节点最多只有两棵子树，并且子树有左右之分，不能任意互换二叉树的五种形态空只有根只有左子树只有右子树左右子树均不空,5、复杂数据结构树（Tree）：二叉树,第I层上最多有2I-1个节点深度为K的二叉树最多有2k-1个节点对于任意一个二叉树，如果其叶子（终端节点）数目为n0，度为2的节点数目为n2，有n0=n2+1完全二叉树与满二叉树,5、复杂数据结构树（Tree）：二叉树的性质,完全二叉树,满二叉树,具有n个节点的完全二叉树的深度为log2n+1N个节点的完全二叉树，按照从顶到底，从左到右的顺序编号（1-N)如果I=1，根节点如果I1，则双亲为I/2如果2*IN，则节点I无左孩子，否则左孩子为2*I如果2*I+1N，则节点I无右孩子，否则右孩子为2*I+1,5、复杂数据结构树（Tree）：二叉树的性质,A+B*(C-D)-E/F,5、复杂数据结构树（Tree）：二叉树的应用（表达式）,与树和线性表不同，每个元素都可能与其它元素有关系。形式化定义Graph=(V,R)顶点，V是顶点的集合R是两个顶点之间关系的集合如果属于R，则表示一条弧,5、复杂数据结构图（Graph）,弧头，弧尾无向图、边顶点数目、边的数目完全图、有向完全图权网络子图,5、复杂数据结构图（Graph）：相关概念,V=V1,V2,V3,V4A=,5、复杂数据结构图（Graph）：例子,邻接点依附相关联顶点的度出度入度,5、复杂数据结构图（Graph）：其他概念,路径，回路和环连通连通图连通分量生成树生成森林,顶点定位取顶点求第一个邻接点求下一个邻接点插入顶点插入弧删除顶点删除弧,5、复杂数据结构图（Graph）：图的操作,数据类型（数据）DataType,节点（关系、自身行为）Node,容器（行为）数据结构（Queue）,5、复杂数据结构设计与实现,5、复杂数据结构设计与实现,classDataType,classNodeDataTypedata;/结点之间的关系/NodepreNode;/NodenextNode;/NodeleftNode;/NoderightNode;/结点自身的行为voidsetData(DataTyped)DataTypegetData()voidsetNext/Pre/Left(DataTyped)DataTypegetNext/Pre