还剩45页未读，继续阅读
本资源只提供10页预览，全部文档请下载后查看！喜欢就下载吧，查找使用更方便
文本内容:
数据结构和算法Java第o讲综述参考教材:数据结构和算法（第二版），［美］Java Robertlafore数据结构的特性L数据结构优点缺点数组插入快；如果知道下标，可以非常快地存取查找慢，删除慢，大小固定有序数组比无序的数组查找快删除和插入慢，大小固定栈提供后进先出方式的存取存取其他项很慢队列提供先进先出方式的存取存取其他项很慢链表插入快，删除快查找慢删除算法复杂二叉树查找、插入、删除都快（如果树保持平衡）红-黑树查找、插入、删除都快；树总是平衡的算法复杂树2-3-4查找、插入、删除都快；树总是平衡的；类似算法复杂的树对磁盘存储有用哈希表如果关键字已知，则存储极快；插入快删除慢，如果不知道关键字则存储很慢，对存储空间使用不充分堆插入、删除快；对大数据项的存取很快对其他数据项存取慢图对现实世界建模有些算法慢且复杂.经典算法总结2查找算法线性查找和二分查找排序算法用表展示第一讲数组中数组的基础知识
1.Java）创建数组1~~在中把数组当作对象来对待，因此在创建数组时必须使用操作符:Java new//peek attop of stackpublic longreturnpeek{arr[top];㊀//tur ifstack isemptypublic boolean returnisEmpty{top==-1;㊀//tur ifstack isfullpublic booleanreturnisFull{top==arr.length-1;_________________________________________________________________________]测试栈的特性:public voidthrows newtestMyStackException{MyStack myStack=MyStack4;myStack.push12;myStack.push34;myStack.push56;myStack.push78;System.out.printinmyStack.isFull;//truewhile!myStack.isEmpty{System.out.printmyStack.pop;//78,56,34,12ifImyStack.isEmpty{nSystem.out.print,;System.out.printin;System.out.printinmyStack.isFull;//false队列
3.）i队列模型队列又先进先出）是一种插入时在一端进行而删除时在另一端进行的数据结构（Queue,FIFO:为解决顺序队列假溢出问题，而采用循环队列即让队头、队尾指针在达到尾端时，又绕回到开头）队列的数组实现2队列的代码Javapublic classprivate long[]private intprivate intprivate intMyQueue{arr;size;front;rear;public newlong[MyQueue{arr=10];size=0;front=0;rear=-1;public intnew longMyQueuemaxSize{arr=[maxSize];size=0;front=0;rear=-1;//put itemat rearof queuepublic void longinsert value{if thrownewisEmpty{//throw exceptionif queue is fullArraylndexOutOfBoundsException;环绕式处理ifrear==arr.length-1{//deal withwraparound rear=-1;arr[++rear]=value;//increment rearand insertsize++;//increment size//take itemfrom front of queuepublic longremove{long；ifvalue=arr[front++]//get valueand incrementfront front==arr.length{//deal withwraparound front=0;size--;//one lessitemreturnvalue;//peek atfront ofqueuepublic longreturnpeek{arr[front];//true ifqueue isemptypublic booleanreturnisEmpty{size==0;//true ifqueueisfullpublic booleanreturnisFull{size==arr.length;2_____________________________________________测试队列的特性:public voidthrowstestMyQueue Exception{newMyQueue myQueue=MyQueue4;myQueue.insert12;myQueue.insert34;myQueue.insert56;myQueue.insert78;System.out.printinmyQueue.isFull;//truewhile!myQueue.isEmpty{System.out.printmyQueue.remove;//12,34,56,78if!myQueue.isEmpty{nSystem.out.print,;System.out.printin;System.out.printinmyQueue.isEmpty;//true myQueue.insert99;System.out.printinmyQueue.peek;//99第四讲链表链结点
1.一个链结点或称结点）是某个类的对象，该对象中包含对下一个链结点引用的字段（Link,（通常叫）而链表本身的对象中有一个字段指向对第一个链结点的引用next类的定义Linkpublic classLink{public longdata;//data itempublicLinknext;//next linkin listpublic long this.Link data{data=data;public voidndisplayLink{//display ourselfSystem.out.printdata+--n;单链表
2.LinkList类显示了一个单链表，该链表可以进行的操作有•LinkList在链表头插入一个数据设置新添加的结点的设为原来的头结点，再将新添加的insertFirst:next结点设为头结点在链表头删除一个数据将第二个结点设为头结点deleteFirst:遍历链表显示所有数据使用临时指针从头结点开始，沿着链表先前移动，displayList current,依次遍历每个节点类LinkListpublic classLinkList{privateLink first;//reference tofirst linkon listpublicthis.=null;LinkList{first//insert atstart of listpublic void long newinsertFirstvalue{Link newLink=Link value;newLink.next=first;//newLink--old firstfirst=newLink;//first--newLink//delete firstitempublicLink deleteFirst{if==null{return null;firstLink temp=first;returnfirst=first.next;//delete it:first--old nexttemp;//return deletedlinkpublic voiddisplayList{while!=Link current=first;//start atbeginning of list currentnull{//until end of list current.displayLink;current=current.next;//move listto next link System.out.printin;}}测试类的方法LinkListpublic void throwstestLinkList Exception{newLinkList linkList=LinkList;linkList.insertFirst88;linkList.insertFirst66;linkList.insertFirst44;linkList,insertFirst22;linkList.displayList;//22--44--66--88--linkList.deleteFirst;linkList.displayList;//44--66--88--查找和删除指定链结点
3.•此外，还能对指定的结点值进行查找和删除查找指定结点类似于之前的方法find:displayList删除指定结点在删除指定结点时，必须把前一个结点和后一个结点连接在一起，delete所以需要一个临时指针来保存对前一个结点的引用previous向类中添加查找和删除方法LinkList finddelete public//find linkwith givenkey Linklongfindkey{while1Link current=first;//start atfirst,current.data!=keyif==null{//{current.next didnt find itreturn null;}else{//go to next link current=current.next;returncurrent;//delete linkwith givenkeypublic longLinkdelete key{Link current=first;//search forexpected link Link previous=first;while if==null{current.data!=key{current.nextreturn null;//1didn t find it}else{previous=current;current=current.next;//go to next link}//find itifcurrent==first{//if first link,change firstfirst=first.next;}else{//otherwise,bypass itprevious.next=current.next;returncurrent;}测试添加的和方法find deletepublic voidthrowstestLinkListException{newLinkList linkList=LinkList;linkList.insertFirst88;linkList.insertFirst66;linkList.insertFirst44;linkList.insertFirst22;linkList.displayList;//22--44--66--88--linkList.find
44.displayLink;//44一一〉System.out.printin;linkList.delete
44.displayLink;//44--System.out.printin;linkList.displayList;//22--66--88--第五讲双端链表和双向链表双端链表
1.链表中保存着对最后一个链结点的引用•从头部进行插入要对链表进行判断，如果链表为空，则设置尾结点为新添加的结insertFirst:点从尾部进行插入如果链表为空，则直接设置头结点为新添加的结点，否则设置insertLast尾结点的后一个节点为新添加的结点从头部进行删除判断头结点是否有下一个结点，如果没有则设置尾结点为deleteFirst nullo双端链表类FirstLastListpublic classFirstLastList{private privateLink first;//reference tofirst linkLink last;//referenceto last linkpublicFirstLastList{this.=null;firstthis.=null;lastpublic booleanreturn==null;isEmpty{//true if no linksfirst//insert atfront oflistpublic void longinsertFirst value{new ifLink newLink=Link value;isEmpty{//if emptylist last=newLink;//newLink--lastnewLink.next=first;//newLink--old firstfirst=newLink;//first--newLink//insert atend ofpublic void longnewlist insertLastvalue{Link newLink=Linkvalue;if}isEmpty{//if emptylist first=newLink;//first--newLinkelse{last.next=newLink;//old last--newLinklast=newLink;public//newLink last//delete first linkLink deleteFirst{Linktemp=first;if==null{//=null;//first.next ifonly oneitem lastnull--lastfirstreturn=first.next;//first--old nexttemp;public voiddisplayList{while!=Link current=first;//start atbeginning oflist currentnull{//until end oflistcurrent.displayLink;current=out.current.next;//move listtonext linkSystem.printin;测试类及输出结果FirstLastListpublic voidthrows newtestFirstLastListException{FirstLastList list=FirstLastList;list.insertLast24;list.insertFirst13;list.insertFirst5;list.insertLast46;list.displayList;//5--13--24--46--list.deleteFirst;list.displayList;//13--24--46--.双向链表2•双向链表既允许向后遍历，也允许向前遍历整个链表即每个节点除了保存了对下一个节点的引用，同时后保存了对前一个节点的引用•从头部进行插入要对链表进行判断，如果为空，则设置尾结点为新添加insertFirst:的结点；如果不为空，还需要设置头结点的前一个结点为新添加的结点•从尾部进行插入如果链表为空，则直接设置头结点为新添加的结点，否则设置insertLast:尾节点的后一个结点为新添加的结点同时设置新添加的结点的前一个结点为尾结点O•从头部进行删除判断头结点是否有下一个结点，如果没有则设置尾结点为deleteFirst null；否则设置头结点的下一个结点的为previous nulL•从尾部进行删除如果头结点后没有其他结点，则设置头结点为否则设置deleteLast null尾结点的前一个结点的为设置尾结点为其前一个结点next nulL在指定结点后插入insertAfter:删除指定结点不再需要在使用一个临时的指针域指向前一个结点deleteKey:双向链表的链接点类的定义Linkpublic classDoubleLink{public longdata;//data itempublicDoubleLinknext;//next linkin listpublicDoubleLinkprevious;//previous linkin listpublic long this.DoubleLink data{data=data;public voiddisplayLink{//display ourselfSystem.out.printdata+==n;双向链表类DoublyLinkedListpublic classDoublyLinkedList{private privateDoubleLinkfirst;//reference tofirstlinkDoubleLink last;㊀㊀㊀㊀//r fr ncto lastlinkpublic this.=null;DoublyLinkedList{firstthis.=null;last publicbooleanreturn==null;isEmpty{//true if no linksfirst//insert atfrontoflistpublic voidlong newinsertFirstvalue{DoubleLink newLink=ifDoubleLinkvalue;isEmpty{//if emptylistlast=newLink;//newLink--last}else{first.previous=newLink;//newLink--old firstnewLink.next=first;//newLink--old firstfirst=newLink;//first--newLink//insert atend oflistpublic voidlonginsertLast value{newDoubleLink newLink=DoubleLinkvalue;ifisEmpty{//if emptylistfirst=newLink;//first--newLink}else{last.next=newLink;//old last--newLink newLink.previous=last;//old last--newLinklast=newLink;//newLink--last//delete firstlinkpublicDoubleLink deleteFirst{DoubleLink temp=first;if==null{//=null;//first.next ifonly oneitem lastnull--last}else{null;//first.next.previous=null--old nextfirst=first.next;//first--old nextreturntemp;//delete lastlinkpublicDoubleLink deleteLast{DoubleLink temp=last;if==null{//=null;//first.next ifonly oneitem firstfirst--null}else{=null;last.previous.next//old previous--null last=last.previous;//old previous--lastreturntemp;int[]new int[intArr=10];一旦创建数组，数组大小便不可改变）访问数组数据项2数组数据项通过方括号中的下标来访问，其中第一个数据项的下标是0:intArr
[0]=123;）数组的初始化3当创建数组之后，除非将特定的值赋给数组的数据项，否则它们一直是特殊的对象null int[]intArr={1,2,3,4,5};等效于下面使用来创建数组并初始化:newint[]new int[intArr=5];intArr
[0]=1;intArr
[1]=2;intArr
[2]=3;intArr
[3]=4;intArr
[4]=5;.面向对象编程方式2使用自定义的类封装数组1类MyArraypublic classMyArray{private long[]arr;//记录数组的有效长度private intsize;public newlong[MyArray{arr=10];public intnew longMyArraymaxSize{arr=[maxSize];//向数组中插入数据public voidlonginsert element{arr[size]=element;++;㊀siz}//显示数组中的数据public voidforint ifshow{i=0;isize;i++{i==0{System.out.print[+arr[i]+,;//insert datajust afterkeypublic booleanlong longinsertAfterkey,data{whileDoubleLink current=first;//start atbeginning current.data!=if==null{return false;}elsekey{//until matchis foundcurrent.next{current=current.next;}//find theposition ofkey DoubleLinknewifnewLink=DoubleLinkdata;//make newlinkcurrent==last=null;//{//if lastlink,newLink.next newLink--null last=newLink;}else{////newLink--last not lastlink.newLink.next=current.next;//newLink--old nextcurrent.next.previous=newLink;//newLink--old nextcurrent.next=newLink;//old current--newLink newLink.previous=current;//oldreturn true;publiccurrent--newLink//delete linkwith givenkey DoubleLinklongdeleteKeykey{DoubleLink current=first;//search forexpected linkwhileif==null{return null;//current.data!=key{current.next didn*t}else{find itcurrent=current.next;//go tonext link}//find itifcurrent==first{//if firstlink,change firstfirst=first.next;}else{//first--old next//otherwise,old previous--old nextifcurrent.previous.next=current.next;}current==last{//last}else{item last=last.previous;//old previous--last//notlast:・old previous--old nextcurrent next.previous=returncurrent.previous;current;public voiddisplayForward{n HSystem.out.print first--last:;DoubleLink current=first;//start atbeginning oflistwhile!=null{//current untilendoflistcurrent.displayLink;current=current.next;//move listtonext linkSystem.out.printin;public voiddisplayBackward{n nSystem.out.print last--first:;while!=nullDoubleLink current=last;//start atendoflistcurrent{//until start oflistcurrent.displayLink;current=current.previous;//move listto previouslink System.out.printin;___________________________________________________________________________________]测试该类的主要方法:public voidthrowstestDoublyLinkedList Exception{DoublyLinkedList list=newDoublyLinkedList;list.insertLast24;list.insertFirst13;list.insertFirst5;list.insertLast46;list.displayForward;・//first--last:5==13==24==46==list displayBackward;//last--first:46==24==13==5==list.deleteFirst;list.displayForward;//first--last:13==24==46==list.deleteLast;list.displayForward;//first--last:13==24==list.insertAfter13,17;17==list.displayForward;//first--last:13==24==〉list.deleteKey24;list.displayForward;//first--last:13==17==第六讲递归的应用递归是一种在方法函数的定义中调用方法自身的编程技术Recursion递归算法解决问题的特点递归就是在过程或函数里调用自身1在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口2递归算法解题通常显得很简洁，但递归算法解题的运行效率较低所以一般不提倡用递3归算法设计程序在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储递归次数过4多容易造成栈溢出等所以一般不提倡用递归算法设计程序在实际编程中尤其要注意栈溢出问题构成递归需具备的条件子问题须与原始问题为同样的事，且更为简单；a.不能无限制地调用本身，须有个出口，化简为非递归状况处理b.三角数字.1该数列中的首项为第项是由第项加后得到的11,n n-1n使用循环查找第项2npublic staticint int int whiletriangleByWhilen{total=0;n0{total=totalreturn+n;n--;total;}triangleByWhileSystem.out.printinTriangle.5;//15使用递归查找第项3npublic staticint inttriangleByRecursion nifn==1{return1;}else{return triangleByRecursionn-1;n+triangleByRecursionSystem.out.printinTriangle.5;//15数歹Fibonacci
2.ij数歹的第项为第二项为第项为第项加上项后得到该数列的递归算Fibonacci U00,1,n n-1n-2法实现如下public staticint intiffibo n{n==l||n==2{return1;}else{return fibofibon-1+n-2;}}fiboSystem.out.printinFibonacciSequence.8;//21程序的运行流程如下:第七讲递归的高级应用汉诺塔问题
1.汉诺塔问题描述如下有三根杆子杆上有个穿孔圆盘，盘的尺寸由下到上依次变小要求按下A,B,C AN N1列规则将所有圆盘移至杆C每次只能移动一个圆盘；大盘不能叠在小盘上面提示可将圆盘临时置于杆，也可将从杆移出的圆盘重新移回杆，但都必须遵循上述两B AA条规则问如何移？最少要移动多少次？汉诺塔问题的递归求解方法移动子树把除了最低端盘子外的所有盘子形成的子树移动到一个中介塔上，然后把最低端盘子移到目标塔上，如此循环最终把那个子树移动到目标塔上代码实现如下Javapublic static void intchar charchar ifdoTowerstopN,from,inter,totopN==1{.out.n}elseSystem printIn Disk1from”+from+to+to;{doTowerstopN-1,from,to,inter;//from--intern n nSystem.out.printInDisk”+topN+from+from+to+to;doTowerstopN-1,inter,from,to;//inter--to}doTowers1111HanoiTower.3,A,B,C;//Disk1from Ato C//Disk2from Ato B//Disk1from Cto B//Disk3from Ato C//Disk1from Bto A//Disk2from Bto C//Disk1from Ato C递归的二分查找
2.归并排序
3.归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的然后再把有序子序列合并为整体有序序列消除递归
4.递归算法实际上是一种分而治之的方法，它把复杂问题分解为简单问题来求解对于某些复杂问题（例如塔问题），递归算法是一种自然且合乎逻辑的解决问题的方式，但是递归算hanio法的执行效率通常比较差因此，在求解某些问题时，常采用递归算法来分析问题，用非递归算法来求解问题；另外，有些程序设计语言不支持递归，这就需要把递归算法转换为非递归算法将递归算法转换为非递归算法有两种方法，一种是直接求值，不需要回溯；另一种是不能直接求值，需要回溯前者使用一些变量保存中间结果，称为直接转换法；后者使用栈保存中间结果，称为间接转换法，下面分别讨论这两种方法.直接转换法.1直接转换法通常用来消除尾递归和单向递归，将递归结构用循环结构来替代尾递归是指在递归算法中，递归调用语句只有一个，而且是处在算法的最后例如求阶乘的递归算法:public longfactint nifn==0return1;else returnn*factn-l;当递归调用返回时，是返回到上一层递归调用的下一条语句，而这个返回位置正好是算法的结束处，所以,不必利用栈来保存返回信息对于尾递归形式的递归算法，可以利用循环结构来替代例如求阶乘的递归算法可以写成如下循环结构的非递归算法public longfactint nints=0;for inti=l;i用保存中间结果s=s*i;//sreturn s;单向递归是指递归算法中虽然有多处递归调用语句，但各递归调用语句的参数之间没有关系，并且这些递归调用语句都处在递归算法的最后显然，尾递归是单向递归的特例例如求斐波那契数列的递归算法如下public intfint nifn==111n==0return1;else returnfn-l+fn-2;对于单向递归，可以设置一些变量保存中间结构，将递归结构用循环结构来替代例如求斐波那契数列的算法中用和保存中间的计算结果，非递归函数如下si s2public intfint ninti,s;int sl=l,s2=l;for i=3;i{s=sl+s2;s2=sl;〃保存f（n-2）的值〃保存（）的值sl=s;fn-l）return s;）.间接转换法2该方法使用栈保存中间结果，一般需根据递归函数在执行过程中栈的变化得到其一般过程如下将初始状态进栈sO（栈不为空）while（退栈，将栈顶元素赋给s;（是要找的结果）返回；if selse{寻找到的相关状态s si;将进栈S1））间接转换法在数据结构中有较多实例，如二叉树遍历算法的非递归实现、图的深度优先遍历算法的非递归实现等等，请读者参考主教材中相关内容第八讲希尔排序希尔排序是由提出来的，希尔排序基于插入排序，并且添加了一些新的特性，Donald L.Shell从而大大提高了插入排序的执行效率
1.插入排序的缺陷多次移动假如一个很小的数据在靠右端位置上，那么要将该数据排序到正确的位置上，则所有的中间数据都要向右移动一位2•希尔排序的优点希尔排序通过加大插入排序中元素元素之间的间隔，并对这些间隔的元素进行插入排序，从而使得数据可以大幅度的移动当完成该间隔的排序后，希尔排序会减少数据间的间隔再进行排序依次进行下去基本思想
3.希尔排序（最小增量排序）算法先将要排序的一组数按某个增量（为要排序数的d n/2,n个数）分成若干组，每组中记录的下标相差对每组中全部元素进行直接插入排序，然后再用d.一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序当增量减到1时，进行直接插入排序后，排序完成间隔的计算间隔的初始值为通过来循环计算，知道该间隔大于数组的大小h1,h=3*h+1时停止最大间隔为不大于数组大小的最大值间隔的减少通过公式来计算h=h-1/3算法实现
2.希尔排序的代码:Java//Shell sortpublic static voidlong[]she11Sort arr{inth=1;whileharr.length/3{//find initialvalue ofh h=h*3+1;・・・}//h={1,4,13,40,121,}while hlongh0{//decreasing runtil h=l//insert sorttemp;forinti=h;iarr.length;i++{//i ismarked locationtemp=arr[i];//remove markeditemintj=i;//start shiftsat iwhilejh-1arr[j-h]temp{//until oneis smallerarr[j]=arr[j-h];//shift itemright j-=h;//go lefthpositionarr[j]=temp;//insert markeditem//decrease hh=h-1/3;测试希尔排序及输出结果:public voidthrows long[]testShellSortException{arr={10,5,8,7,1,6,shellSort4,9,2,3};Sort,arr;toStringarr;7,System.out.printinArrays.//[I,2,3,4,5,6,8,9,10]第九讲快速排序快速排序的基本思想L快速排序选择一个关键字，通常选择第一个元素或者最后一个元素，通过一趟扫描,将待排序列分成两部分，一部分比关键字小，另一部分大于等于关键字，此时关键字在其排好序后的正确位置，然后再用同样的方法递归地排序划分出来的两部分如何进行划分设定关键字，将比关键字小的数据放在一组，比关键字大的放在另一组如何自动设定关键字设置数组最右端的数据为关键字.快速排序的算法实现2快速排序的代码Javapublic classSort{public static voidlong[]intintifquicksort arr,left,right{right-left=0{//return;}else{//longif size=1,//already sortedotherwise key=arr[right];int partition//rightmost item//partition rangepoint=arr,left,right,key;quicksort quicksortarrleft,point-1;//sort leftside arrzfpoint+1,right;//sort rightsidepublicstaticint long[]int㊀int longpartitionarr,1ft,right,key intleftP=left-1;//left after++intrightP=right;//right-1after--whiletrue{whileleftPrightarr[++leftP]key;//find biggeritemwhilerightPleftarr[--rightP]key;//find smalleritem//while arr[++leftP]key;//whilerightP0arr[--rightP]key;if break;leftP=rightP{//if pointerscross,//partition done}else{//longnot crossed,so swapelements temp=arr[leftP];arr[leftP]=arr[rightP];arr[rightP]=temp;//restore keylongtemp=arr[leftP];arr[leftP]=arr[right];arr[right]=temp;returnleftP;//return keylocation测试快速排序及输出结果public voidthrowstestQuickSort Exception{//also canfill arrwith randomlong[]quicksortnumbers arr={10,5,8,7,1,6,4,9,2,3};Sort.arr,toStringarr;0,arr.length-1;System.out.printinArrays.//[I,2,3,7,4,5,6,8,9,10]补充基数排序基数排序将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零然后，从最低位开始，依次进行一次排序这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列第十讲二叉树的基本概念树L）为什么要使用树1有序数组插入数据项和删除数据项太慢链表查找数据太慢在树中能快速地查找、插入和删除数据项）树的基本概念2路径顺着连接节点的边从一个节点到另一个节点，所经过的节点顺序排列称为路径根树最上面的节点称为根节点一棵树只有一个根，而且从根到任何一个节点有且只有一条路径父节点每个节点都有一条边向上连接到另一个节点，这个节点就称为是下面这个节点的父节点子节点每个节点都有一条边向下连接到另一个节点，下面的节点就是该节点的子节}else ifout.nni==size-l{System.printinarr[i]+];}else{System.out.printarr[i]+,;//根据值查找索引出现该值的第一个位置线性查找public intlong intqueryByValueelement{i;fori=0;isize;i++{//linear searchifbreak;arr[i]==elementif returni==size{-1;}else{returni;//根据索引查找值publiclongint ifqueryBylndexindex{index=size||index0{throw newArraylndexOutOfBoundsException;}else{returnarr[index];//删除数据public voidintdelete index{if thrownewindex=size||index0{ArraylndexOutOfBoundsException;}else{//当删除最后一个数时，不会执行forintsize=maxSize,for i=index;isize-l;i++{arr[index]=arr[index+1];H nSystem.out.printin for;size--;点叶子节点没有子节点的节点称为叶子节点子树每个节点都可以作为一个子树的根，它和它所有的子节点以及子节点的子节点组合在一起就是一个子树
2.访问访问一个节点是为了在这个节点上执行一些操作，如查看节点的数据项但是如果仅仅是经过了一个节点，不认为是访问了这个节点
3.层一个节点的层数是指从根节点开始到这个节点有多少代二叉树
4.树的每个节点最多只能有两个子节点的树，称为二叉树二叉树的代码实现节点类publicclass longNode{data;Node leftchild;Node righttChild;二叉树publiclongthis.public classNodedata{data=data;}BinaryTree{Node root;public voidlong public voidlongpublic voidinsertvalue{}delete value{}longfind value{}第十一讲二叉树的基本操作插入节点
1.从根节点开始查找一个相应的节点，这个节点将成为新插入节点的父节点当父节点找到后，通过判断新节点的值比父节点的值的大小来决定是连接到左子节点还是右子节点插入节点的代码实现:Javapublic voidlonginsertvalue{newNode newNode=Nodevalue;if null{root==//no nodein rootroot=newNode;}else{//root occupiedNode current=root;//start atrootNode parent;//point toparentwhiletrue{parent=current;ifvaluecurrent.data{//go leftcurrent=current.leftChild;if null{current==//if endof theline parent.leftchildreturn;=newNode;//insert onleft}else{//or gorightcurrent=current.righttChild;if==null{current//if endof theline parent.righttChildreturn;=newNode;//insert onright}测试该方法及输出:public voidthrows newtestBinaryTreeException{BinaryTree tree=BinaryTree;tree.insert34;tree.insert21;・tree insert67;・tree insert56;outSystem..printintree.root.data;//34outSystem..printintree.root.leftchild.data;//21System.out.printintree.root.righttChild.data;//67System.out.printintree.root.righttChild.leftchild.data;//56查找节点
2.从根节点开始查找，如果查找的值比当前节点的值小，则继续查找器做左子树，否则查找其右子树查找节点的代码实现:Java//find nodewith givenkeypublic longNodefind value{whileNode current=root;//start atroot current.data!=valueif{//while nomatch,valuecurrent.data{//go leftcurrent=current.leftChiId;}else{//or goright current=current.righttChild;if==null{//return null;current if no child,//didntfindreturn current;测试查找节点的方法及输出:System.out.printintree.find
21.data;第十二讲遍历二叉树
1.遍历树遍历树是根据一个特定的顺序访问树的每一个节点，根据顺序的不同分为前序中序和后序遍历三种前序遍历
2.前序遍历先访问根节点，再前序遍历左子树，最后前序遍历右子树；前序遍历的代码实现:Javapublic voidif!=null{frontOrderNode node{nodeSystem.out.printinnode.data;frontOrdernode.leftchild;frontOrdernode.righttChild;}}tree.frontOrdertree.root;//34216756中序遍历
3.中序遍历先中序遍历左子树，再访问根节点，最后中序遍历右子树;中序遍历按关键值的升序节点，从而形成一组有序数据中序遍历的代码实现Javapublic voidif!=null{inOrderNode node{nodeinOrdernode.leftchild;System.out.printinnode.data;inOrdernode.righttChild;}tree.inOrdertree.root;//
21345667.后序遍历3后序遍历先后序遍历左子树，再后序遍历右子树，最后访问根节点后序遍历的代码实现:Javapublic voidif!=null{afterOrderNode node{nodeafterOrdernode.leftchild;afterOrdernode.righttChild;System.out.printinnode.data;}tree.afterOrdertree.root;//21566734第十三讲删除二叉树节点删除节点的三种情况L•删除节点是二叉树操作中最复杂的在删除之前首先要查找要删的节点找到节点后,这个要删的节点可能会有三种情况需要考虑•该节点是叶子节点，没有子节点•要删除叶子节点，只需要改变该节点的父节点的引用值，将指向该节点的引用设置为null就可以了•该节点有一个子节点•改变父节点的引用，将其指向要删除节点的子节点•该节点有两个子节点
2.要删除节点有两个子节点，就需要使用它的中序后继来替代该节点.删除节点的代码实现3删除节点的代码实现Java//delete nodewith givenkeypublic booleanlongdelete value{Node current=root;Node parent=current;boolean true;isLeftChild=whilecurrent.data!=value{//while nomatch,parent=current;ifvaluecurrent.data{//go leftcurrent=current.leftChild;true;isLeftChild=}else{//or gorightcurrent=current.righttChild;false;isLeftChild=if==null{//return false;1current if no child,//didn tfind}}//find thenode todelete//if nochild,if tChild==nullifcurrent.lef current•righttChild==null{current===null;//root{//if rootroot treeid emptyz}else if=null;isLeftChild{parent.leftchild}else{null;parent.righttChild=}else if==null{current.leftChildif//if noleft child,replace withright subtreecurrent==root{root=current.righttChild;}else ifisLeftChild{//left childof parentparent.leftChild=current.righttChild;}else{//right childof parentparent.righttChild=current.righttChild;}}else ifnull{current.righttChild==if//ifnoright child,replace withleft subtreecurrent==root{root=current.leftchild;}else ifisLeftChild{//left childof parentparent.leftchild=current.leftchild;}else{//right childof parentparent.righttChild=current.leftchild;}else{//two children,so replacewith inordersuccessor//getsuccessor ofnode todelete currentNode successor=getSuccessor current;if//connect parentof currentto successorinstead current==root{root=successor;}else ifisLeftChild{parent.leftchild=successor;}else{parent.righttChild=successor;}1//connect successorto currents left child successor.leftchild=current.leftchild;return true;//get successorto replacedeleted node//returns nodewith next-highest valueafter deiNodeprivate//goes toright child,then rightchild*s leftdescendants NodegetSuccessorNodedelNode{Nodecurrent=deiNode.righttChild;//go toright childNode successorParent=deiNode;Nodesuccessor=deiNode;while null{current!=//until nomoresuccessorParent=successor;successor=current;current=current.leftchild;//go toleftchild//if successornot rightchild,make connectionsifsuccessor!=deiNode.righttChild{successorParent.leftChild=successor.righttChild;successor.righttChild=deiNode.righttChild;returnsuccessor;测试删除各种节点的情况:tree.delete56;//no childtree.inOrdertree.root;//21346770tree.delete67;//only leftchildtree.inOrdertree.root;//213456tree.delete21;//twochildren tree.inOrdertree.root;//345667第十四讲红黑树平衡树与非平衡树
1.）二叉树的问题1）前面介绍了二叉树，普通的二叉树作为数据存储的工具有很大的优势，可以快速插入、删除2和查找数据项遗憾的是，这仅仅是相对于插入随机数据，如果插入的数据是有序的，速度就变得特别的慢）平衡树和非平衡树3平衡树插入随机的数据非平衡树插入有序的数据完全平衡树红黑规则
2.）红黑规则1（）每个节点不是红色的就是黑色的1（）根总是黑色的2（）如果节点是红色的，则它的子节点必须是黑色的3
（4）从根节点到叶节点的每条路径，必须包含相同数目的黑色节点）纠正违规2将不符合红黑规则的数纠正为红黑树（）改变节点的颜色1
（2）执行旋转操作第十五讲哈希表什么是哈希表
1.
2.哈希表是一种数据结构，它可以提供快速的插入和查找操作哈希表是基于数组来实现的哈希化
3.直接将关键字作为索引1类Infopublic classprivate intprivateInfo{id;String name;public int this.this.Info id,String name{id=id;name=name;public intreturngetld{id;public voidintthis.setld id{id=id;public returnStringgetName{name;public voidthis・setNameString name{name=name;2____________________________________________________________关键字作为索引的代码实现:javapublic classHashTable{Info[]arr;public newHashTable{arr=Info
[10000];public intnewHashTable maxSize{arr=Info[maxSize];//insert elementpublic voidinsert Infoinfo{arr[info.getld]=info;}//find elementpublic int returnInfofind id{arr[id];2____________________________________测试插入和查找方法:public voidthrows newtestHashTableException{HashTable table=HashTable;newtable.insert Info1zhangSan;Anewtable.insert Info2,tianQi;System.out.printintable.find
1.getName;将单词转换成索引2
①将字母转换成码,然后进行相加ASCH转码索引的代码实现:Javapublic intinthashcodeString key{code=0;forinti=key.length-1;i=0;i--{intvalue=key.charAti-96;code+=value;return}code;//insert elementpublic voidinsert Infoinfo{arr[hashcodeinfo.getld]=info;//findelement测试及输出:public returnInfofindString key{arr[hashcodekey];public voidthrows newtestHashTableException{HashTable table=HashTable;newn ntable.insert Infoabc,zhangSan;newtable.insert Infobbb,tianQi;System.out.printintable.findabc.getName;//tianQinSystem.out.printintable.find bbb.getName;//tianQi从上可见上面的编码方式存在很高的重复率
②幕的连乘事的连乘编码代码实现:Javapublic inthashcodeString key{intcode=0;intpower27=1;forinti=key.length-1;i=0;i--{intvalue=key.charAti-96;code+=value*power27;power27*=27;returncode;测试及输出:n nSystem.out.printintable.find abc.getName;//zhangSanSystem.out.printintable.findbbb.getName;//tianQi
③压缩可选值为了解决编码后的数据过大，对其进行取模运算public inthashcodeStringkeynew new{Biginteger hashVal=Biginteger0;Biginteger pow27=forint intBiginteger1;i=key.length-1;i=0;i--{letter=key.charAti-96;new valueOfletter;Biginteger letterB=BigintegerString.hashVal=hashVal.addletterB.multiplypow27;new valueOfreturnpow27=pow
27.multiply BigIntegerString.27;hashVal.modnew valueOfarr.BigintegerString.length.intValue;压缩后仍可能出现的问题
3.冲突，不能保证每个单词都映射到数组的空白单元解决办法
①开放地址法
②链地址法//更新数据public voidint longupdateindex,value{ifindex=size||index0{throw newArraylndexOutOfBoundsException;}else{arr[index]=value;添加类方法实现数据操作2测试类方法MyArraypublic voidthrowstestMyArray Exception{newMyArray myArray=MyArray;myArray.insert123;myArray.insert456;myArray.insert789;myArray.show;//[123,456,789]System.out.printinmyArray.queryByValue111;//-Iout.System.printinmyArray.queryBylndex2;//789myArray.delete2;myArray.show;//[123,456]myArray.update00;rmyArray.show;//[0,456]有序数组
3.有序数组简介以及其优点1有序数组是一种数组元素按一定的顺序排列的数组，从而方便使用二分查找来查找数组中特定的元素有序数组提高了查询的效率，但并没有提高删除和插入元素的效率构建有序数组2将中自定义的类封装数组的方法改为如下
2.1MyArray insert//向有序数组中插入数据，按大小从前往后排列public voidlonginsert element{inti;fori=0;isize;i++{//find whereit goesifbreak;elementarr[i]forintj=size;ji;j--{//move biggerones uparr[j]=arr[j-1];第十六讲开放地址法什么是开放地址法
1.
2.当冲突发生时，通过查找数组的一个空位，并将数据填入，而不再用哈希函数得到的数组下标，即开放地址法数据的插入
3.数据插入的代码实现:Java//insert elementpublicvoidinsert Infoinfo{Stringkey=info.getld;intcode=hashcodekey;//hash thekeywhile null!=null{arr[code]!=arr[code].getNameO++code;//go tonextcell code%=arr.length;//wrap aroundif necessaryarr[code]=info;}new new，n nHashTabletable=HashTable;table.insert InfozhangSan;newn nn ntable.insert Infoct,tianQi;数据的查找
4.数据查找的代码实现Java//find elementwith keypublic intInfo findString key{code=hashcodekey;//hash thekeywhile!=null{arr[code]//until emptycell.if returnarr[code].getld==key{//found thekey arr[code];//yes,return element++code;//go tonext cellcode%=arr.length;//wrap aroundif necessaryreturn null;outSystem..printintable.finda.getName;//zhangSannSystem.out.printintable.findct.getName;//tianQi数据的删除
5.数据删除的代码实现:Java//delete elementpublic intInfo deleteStringkey{code=hashcodekey;//hash thekeywhile!=null{ifarr[code]//until emptycell,arr[code].getld==key{・Info temp=arr[code];//save itemtemp setNamecaonima;null;returnarr[code].setName//delete itemtemp;//return item++code;//go tonext cellcode%=arr.length;//wrap aroundifreturn null;necessary}nnSystem.out.printintable.delete a.getName;//null第十七讲链地址法什么是链地址法
1.在哈希表每个单元中设置链表某个数据项的关键字还是像通常映射到哈希表的单元中，而数据项本身插入到单元的链表中数据的插入
2.相关类:LinkListpublic classLink{publicInfo info;//data itempublicLinknext;//nextlinkin listpublicthis.LinkInfo info{info=info;2__________________________________________public classLinkList{privateLinkfirst;//reference tofirstlinkon listpublicthis.=null;public voidLinkList{first}//insert atstartoflistnewinsertFirst Infoinfo{LinknewLink=Linkinfo;newLink.next=first;//newLink--old firstfirst=newLink;//first--newLink//delete firstitempublic ifnull{return null;LinkdeleteFirst{first==Link temp=first;returnfirst=first.next;//delete it:first--old nexttemp;//returndeleted link//find linkwith givenkeypublicLink findStringkey{11Link current=first;//start atfirstwhile if==null{//!key.equalscurrent.info.getld{current.nextreturn null;1didn tfind it}else{//go tonextlinkcurrent=current.next;returncurrent;//delete linkwith givenkeypublicLink deleteStringkey{Link current=first;//search forexpectedlinkLink previous=first;while!if==null{key.equalscurrent.info.getld{current.nextreturn null;//didn*tfindit}else{previous=current;current=current.next;//go tonextlink}//find itifcurrent==first{//if firstlink,change firstfirst=first.next;}else{//otherwise,bypass itprevious.next=current.next;returncurrent;数据插入的代码实现Java publicvoid//insert elementinsert Infoinfo{Stringint if==key=info.getld;code=hashcodekey;//hash thekey arr[code]null{newarr[code]=LinkList;arr[code].insertFirstinfo;}newHashTable table=HashTable;newtable.insert Info,zhangSan;newntable.insert Infoct,wangWu;数据的查找
3.数据查找的代码实现:Java//find elementwith keypublicint returnInfofindStringkey{code=hashcodekey;//hash thekeyarr[code].findkey.info;}System.out.printintable.finda.getName;//zhangSanout.n HSystem.printintable.find ct.getName;//tianQi数据的删除
4.数据删除的代码实现:Java publicint//delete elementInfo deleteStringkey{codereturn=hashcodekey;//hash thekey arr[code].deletekey.info;}out.System.printintable.deletea.getName;//zhangSann nSystem.out.printintable.find a.getName;//java.lang.NullPointerException补充堆排序堆排序是一种树形选择排序，是对直接选择排序的有效改进堆的定义如下具有个元素的序列当且仅当满足或n hl,h2,…,hn,hi=h2i,hi=2i+l hi=h2i,hi=2i+l时称之为堆在这里只讨论满足前者条件的堆由堆的定义可以看出，堆顶元素即i=l,2,…,n/2第一个元素必为最大项大顶堆完全二叉树可以很直观地表示堆的结构堆顶为根，其它为左子树、右子树初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大然后将根节点与堆的最后一个节点交换然后对前面个数重新调整使之成为堆依此类推,直到只有两个节点的堆，并对它们作交换，最后得到n-l有个节点的有序序列从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的n最后一个元素交换位置所以堆排序有两个函数组成一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数第十八讲图简介图的基本概念L）什么是图1图是一种和树相像的数据结构，通常有一个固定的形状，这是由物理或抽象的问题来决定的）邻接2如果两个顶点被同一条边连接，就称这两个顶点是邻接的）路径3路径是从一个顶点到另一个顶点经过的边的序列）连通图和非连通图4至少有一条路径可以连接所有的顶点，那么这个图就是连通的，否则是非连通的）有向图和无向图5有向图的边是有方向的，如果只能从到不能从到A B,B A无向图的边是没有方向的，可以从到也可以从到A B,B A）带权图6有些图中，边被赋予了一个权值，权值是一个数字，可以代表如两个顶点的物理距离，或者是一个顶点到另一个顶点的时间等等这样的图叫做带权图图的代码实现
2.Java顶点类Vertexpublic classcharVertex{label;booleanwasVisited;public charthis.false;Vertex label{label=label;wasVisited=图类Graphpublic classGraph{private intmaxSize=20;private private int[][]Vertex[]vertexList;//array ofvertices adjmat;privateintprivate//adjacency matrixnVertex;//current numberof verticesMyStacktheStack;publicGraph{newvertexList=Vertex[maxSize];new intadjmat=[maxSize][maxSize];nVertex=0;newtheStack=MyStack;forinti=0;imaxSize;i++{forintj=0;jmaxSize;j++{adjmat[i][j]=0;publicvoidcharaddVertex label{newvertexList[nVertex4-+]=Vertex label;publicvoidint intaddEdgestart,end{adjmat[start][end]=1;adjmat[end][start]=1;public voiddisplay{forinti=0;inVertex;i++{out.System.printinvertexList[i].label;2______________________________测试的相关方法Graphpublic voidthrowstestGraph Exception{newGraph graph=Graph;1graph.addVertex A*;11graph.addVertex B;11graph.addVertex C;11graph.addVertex D;graph.addEdge0,1;graph.addEdge1,2;graph.addEdge2,3;graph.addEdge3,0;graph.display;//A BCD第十九讲图的搜索图的搜索
1.图的搜索是指从一个指定的顶点到达哪些顶点
2.有两种常用的方法可以用来搜索图深度优先搜索和广度优先搜索深度优先搜DFS BFS索通过栈来实现，而广度优先搜索通过队列来实现深度优先搜索
3.深度优先搜索的原则1
①如果可能，访问一个邻接的未访问的顶点，标记它，并把它放入栈中
②当不能执行规则时，如果栈不能空，就从栈中弹出一个顶点1
③当不能执行规则和规则时，就完成了整个搜搜过程12深度优先搜索的代码实现2Java//depth-first searchpublicvoid true;dfs{//begin atvertex0vertexList
[0].wasVisited=//markout.it System.printinvertexList
[0].label;theStack.push0;//push itwhile!theStack.isEmpty{//until stackempty,//get anunvisited vertexintintadjacent tostack topv=getAdjUnvisitedVertex theStack.peek;ifv==-1{//ifnosuch vertex,theStack.pop;}else{true;//if itexists,vertexList[v].wasVisited=//mark itSystem.out.printinvertexList[v].label;theStack.pushv;//pushforintit//stack isempty,so we*re donei=0;inVertex;i++false;{//reset flagsvertexList[i].wasVisited=publicintint//returns anunvisited vertexadj tov getAdjUnvisitedVertexvforint if{i=0;inVertex;i++{adjmat[v][i]==lvertexList==false{return[i].wasVisited i;return-1;graph.dfs;//A BCD广度优先搜索
4.）广度优先搜索的原则11访问下一个邻接的未访问过的顶点，这个顶点必须是当前节点的邻接点，标记它，并把它插入到队列中2如果无法执行规则1,那么就从队列头取出一个顶点，并使其作为当前顶点3当队列为空不能执行规则2时，就完成了整个搜索过程第二十讲图的最小生成树最小生成树
1.连接每个顶点最少的连线最小生成树边的数量总是比顶点的数量少lo最小生成树的代码实现
2.Java//minimum spanningtree depthfirstpublic voidmst{//start at0true;vertexList
[0].wasVisited=//mark ittheStack.push0;//push itwhile!int inttheStack.isEmpty{//until stackempty,currentvertex=theStack.peek;int//get anunvisited vertexadjacent tostack topv=ifgetAdjUnvisitedVertexcurrentvertex;v==-1{//ifnomoreneighbors,theStack.pop;//pop itaway}else{true;//got aneighbor,vertexList[v].wasVisited=//mark it//dispaly edgefrom currentvertexto voutSystem..printvertexList[currentvertex].label+;System.out.printinvertexList[v].label;theStack.pushv;//push it1//stack isempty,so were doneforinti=0;inVertex;i++{//reset flagsvertexList[i].wasVisited=false;}graph.mst;//A-B B-C C-Darr[i]=element;++;㊀siz}得到有序数组的类封装类，测试该类中的方法MyOrderedArray insertpublic voidthrowstestMyOrderedArrayException{newMyOrderedArray myOrderedArray=MyOrderedArray;myOrderedArray.insert999;myOrderedArray.insert555;myOrderedArray.insert777;myOrderedArray.show;//[555777,999]f查找算法
4.线性查找1在查找过程中，将要查找的数一个一个地与数组中的数据项比较，直到找到要找的数在中
2.1自定义的类封装数组的方法，使用的就是线性查找MyArray queryByValue二分查找2二分查找又称折半查找，即不断将有序数组进行对半分割，每次拿中间位置的数和要查找的数进行比较如果要查找的数〈中间数，则表明要查的数在数组的前半段；如果要查的数〉中间数，则表明该数在数组的后半段；如果要查的数=中间数，则返回中间数在有序数组的类封装类中添加方法MyOrderedAiray binarySearch//根据值二分查找索引前提有序publicintlongbinarySearch value{intmiddle=0;intleft=0;intright=size-1;whiletrue{middle=left+right/2;ifarr[middle]==value{returnmiddle;//found it}else ifleftright{return1-1;//can1found it}else{//divide rangeifarr[middle]value{right=middle-1;//in lowerhalf}else{left=middle+1;//in upperhalf测试该二分查找方法publicvoidthrowstestMyOrderedArrayException{newMyOrderedArray myOrderedArray=MyOrderedArray;myOrderedArray.insert999;myOrderedArray.insert555;myOrderedArray.insert777;myOrderedArray.insert333;System.out.printinmyOrderedArray.binarySearch333;//0第二讲简单排序
1.本讲提到的排序算法都假定了数组作为数据存储结构，本讲所有算法的时间复杂度都是在大多数情况下，假设当数据量比较小或基本上有序时，插入排序算法是三种简单排序算法中最好的选择，是应用最多的对于更大数据量的排序来说，后面讲到的快速排序通常是最快的方法冒泡排序
2.基本思想1在要排序的一组数中，对当前还未排好序的范围内的全部数，自下而上对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒即每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换算法实现2冒泡排序的代码:Java//bubble sortpublicstatic voidlong[]bubbleSort arr{longtemp;forint forinti=0;iarr.length-1;i++{//outer loopforward jif=arr.length-1;ji;j--{//inner loopbackward arr[j]arr[j-1]{//swap themtemp=arr[j];arr[j]=arr[j-1];arr[j-1]=temp;测试冒泡排序及输出结果:publicvoidthrowstestBubbleSort Exception{long[]arr={79,91,13,52,34;・bubbleSortSort arr;toStringarr;System.out.printInArrays.//[13,34,52,79,91]基本思想1在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止与冒泡排序相比，选择排序将必要的交换次数从减少到但比较次数仍然保持为ON*N0N,ON*N算法实现2选择排序的代码:Java//select sortpublicstaticvoidlong[]selectSort arr{longtemp;forinti=0;iarr.length-1;i++{//outer loopintk=i;//location ofminimumforintj=i+l;jarr.length;j++{//inner loopifarr[j]arr[k]{k=j;//a newminimum locationtemp=arr[i];arr[i]=arr[k];arr[k]=temp;测试选择排序及输出结果:publicvoidthrowstestSelectSortException{long[]arr={79,91,13,52,34;selectSortSort.arr;toStringarr;System.out.printInArrays.//[13,34,52,79,91]插入排序
4.）基本思想在要排序的一组数中，假设前面个数已经是排好顺序的局部有序，现在1n.l[n=2]要把第个数插到前面的有序数中，使得这个数也是排好顺序的如此反复循环，直到全部nn排好顺序在插入排序中，一组数据仅仅是局部有序的；而冒泡排序和选择排序，一组数据项在某个时刻是完全有序的算法实现2插入排序的代码Java//insert sortpublicstaticvoidlong[]insertSort arr{longtemp;for inti=l;iarr.length;i++{//i ismark㊀d locationtemp=intarr[i];//remove markeditem j=i;//start shiftsat iwhilej=1arr[j-1]temp{//until oneis smallerarr[j]=arr[j-1];//shift itemright j//go leftone positionarr[j]=temp;//insert markeditem测试插入排序以及输出结果publicvoidthrows long[]testInsertSortException{arr={79,91,13,52,34,34;insertSortSort,arr;toStringarr;System.out.printinArrays.//[13,34,34,52,79,91]第三讲栈和队列
1.栈和队列都是抽象数据类型它们既可以用数组实现，又可以用链表实abstract datatype,ADT,现.栈2栈模型1入栈出栈{A,B,C,D{D GB,A栈顶DCBA栈底栈（又后进先出）是一种只能在固定的一端进行插入和删除的数据结构栈只允许访Stack,LIFO:问一个数据项即最后插入的数据项，移除这个数据项后才能访问倒数第二个插入的数据项，以此类推栈可以用数组来实现，也可以用链表来实现）栈的数组实现2栈的代码Javapublic classMyStack{//底层使用数组实现private long[]private intarr;top;public newlong[MyStack{arr=10];top=-1;publicintnew longMyStackmaxSize{arr=[maxSize];top=-1;//put itemon topof stackpublicvoid longpushvalue{arr[++top]=value;publiclong//take itemfrom topofstackpop{returnarr[top--];。
个人认证
优秀文档
获得点赞 0
