JAVA数据结构和算法笔记

第0讲综述

参考教材：Java数据结构和算法（第二版），[美]Robertlafore1.数据结构的特性

数据结构数组有序数组栈队列链表二叉树红-黑树2-3-4树哈希表堆图优点插入快；如果知道下标，可以非常快地存取比无序的数组查找快提供后进先出方式的存取提供先进先出方式的存取插入快，删除快查找、插入、删除都快（如果树保持平衡）查找、插入、删除都快；树总是平衡的查找、插入、删除都快；树总是平衡的；类似的树对磁盘存储有用如果关键字已知，则存储极快；插入快插入、删除快；对大数据项的存取很快对现实世界建模缺点查找慢，删除慢，大小固定删除和插入慢，大小固定存取其他项很慢存取其他项很慢查找慢删除算法复杂算法复杂算法复杂删除慢，如果不知道关键字则存储很慢，对存储空间使用不充分对其他数据项存取慢有些算法慢且复杂2.经典算法总结

查找算法：线性查找和二分查找排序算法：用表展示第一讲数组

1.Java中数组的基础知识

1）创建数组在Java中把数组当作对象来对待，因此在创建数组时必须使用new操作符：int[]intArr=newint[10];一旦创建数组，数组大小便不可改变。2）访问数组数据项数组数据项通过方括号中的下标来访问，其中第一个数据项的下标是0：intArr[0]=123;3）数组的初始化当创建数组之后，除非将特定的值赋给数组的数据项，否则它们一直是特殊的null对象。int[]intArr={1,2,3,4,5};等效于下面使用new来创建数组并初始化：int[]intArr=newint[5];intArr[0]=1;intArr[1]=2;intArr[2]=3;intArr[3]=4;intArr[4]=5;2.面向对象编程方式

1）使用自定义的类封装数组MyArray类：publicclassMyArray{privatelong[]arr;privateintsize;//记录数组的有效长度publicMyArray(){}arr=newlong[10];publicMyArray(intmaxSize){}arr=newlong[maxSize];//向数组中插入数据publicvoidinsert(longelement){arr[size]=element;size++;}//显示数组中的数据publicvoidshow(){if(i==0){for(inti=0;i=size||index<0){}else{}thrownewArrayIndexOutOfBoundsException();returnarr[index];}//删除数据publicvoiddelete(intindex){if(index>=size||index<0){}else{thrownewArrayIndexOutOfBoundsException();//当size=maxSize，删除最后一个数时，不会执行forfor(inti=index;i=size||index<0){thrownewArrayIndexOutOfBoundsException();}else{}arr[index]=value;}}2）添加类方法实现数据操作测试MyArray类方法：publicvoidtestMyArray()throwsException{MyArraymyArray=newMyArray();myArray.insert(123);myArray.insert(456);myArray.insert(7);myArray.show();//[123,456,7]System.out.println(myArray.queryByValue(111));//-1System.out.println(myArray.queryByIndex(2));//7myArray.delete(2);myArray.show();//[123,456]myArray.update(0,0);myArray.show();//[0,456]}3.有序数组

1）有序数组简介以及其优点有序数组是一种数组元素按一定的顺序排列的数组，从而方便使用二分查找来查找数组中特定的元素。有序数组提高了查询的效率，但并没有提高删除和插入元素的效率。2）构建有序数组将2.1中自定义的类封装数组MyArray的insert方法改为如下：//向有序数组中插入数据，按大小从前往后排列publicvoidinsert(longelement){inti;for(i=0;ii;j--){}arr[j]=arr[j-1];//movebiggeronesuparr[i]=element;}size++;得到有序数组的类封装MyOrderedArray类，测试该类中的insert方法：publicvoidtestMyOrderedArray()throwsException{myOrderedArray.insert(999);myOrderedArray.insert(555);myOrderedArray.insert(777);}myOrderedArray.show();//[555,777,999]MyOrderedArraymyOrderedArray=newMyOrderedArray();4.查找算法

1）线性查找在查找过程中，将要查找的数一个一个地与数组中的数据项比较，直到找到要找的数。在2.1中自定义的类封装数组MyArray的queryByValue方法，使用的就是线性查找。2）二分查找二分查找（又称折半查找），即不断将有序数组进行对半分割，每次拿中间位置的数和要查找的数进行比较：如果要查找的数<中间数，则表明要查的数在数组的前半段；如果要查的数>中间数，则表明该数在数组的后半段；如果要查的数=中间数，则返回中间数。在有序数组的类封装类MyOrderedArray中添加binarySearch方法//根据值二分查找索引（前提：有序）publicintbinarySearch(longvalue){intmiddle=0;intleft=0;intright=size-1;while(true){middle=(left+right)/2;if(arr[middle]==value){}elseif(left>right){}else{returnmiddle;//founditreturn-1;//can'tfounditif(arr[middle]>value){}else{}right=middle-1;left=middle+1;//dividerange//inlowerhalf//inupperhalf}}}测试该二分查找方法：publicvoidtestMyOrderedArray()throwsException{myOrderedArray.insert(999);myOrderedArray.insert(555);myOrderedArray.insert(777);myOrderedArray.insert(333);}MyOrderedArraymyOrderedArray=newMyOrderedArray();System.out.println(myOrderedArray.binarySearch(333));//0第二讲简单排序

本讲提到的排序算法都假定了数组作为数据存储结构，本讲所有算法的时间复杂度都是。在大多数情况下，假设当数据量比较小或基本上有序时，插入排序算法是三种简单排序算法中最好的选择，是应用最多的。对于更大数据量的排序来说，后面讲到的快速排序通常是最快的方法。1.冒泡排序

1）基本思想在要排序的一组数中，对当前还未排好序的范围内的全部数，自下而上对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。2）算法实现冒泡排序的Java代码：//bubblesortpublicstaticvoidbubbleSort(long[]arr){longtemp;for(inti=0;ii;j--){//innerloop(backward)if(arr[j]1）基本思想在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。与冒泡排序相比，选择排序将必要的交换次数从O(N*N)减少到O(N)，但比较次数仍然保持为O(N*N)。2）算法实现选择排序的Java代码：//selectsortpublicstaticvoidselectSort(long[]arr){longtemp;for(inti=0;i1）基本思想在要排序的一组数中，假设前面(n-1)[n>=2]个数已经是排好顺序的（局部有序），现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。在插入排序中，一组数据仅仅是局部有序的；而冒泡排序和选择排序，一组数据项在某个时刻是完全有序的。2）算法实现插入排序的Java代码：//insertsortpublicstaticvoidinsertSort(long[]arr){longtemp;for(inti=1;i=1&&arr[j-1]>temp){//untiloneissmallerarr[j]=arr[j-1];//shiftitemrightj--;//goleftoneposition}arr[j]=temp;//insertmarkeditem}}测试插入排序以及输出结果：publicvoidtestInsertSort()throwsException{long[]arr={79,91,13,52,34,34};Sort.insertSort(arr);System.out.println(Arrays.toString(arr));//[13,34,34,52,79,91]}第三讲栈和队列

栈和队列都是抽象数据类型（abstractdatatype，ADT），它们既可以用数组实现，又可以用链表实现。1.栈

1）栈模型栈（Stack，又LIFO：后进先出）是一种只能在固定的一端进行插入和删除的数据结构。栈只允许访问一个数据项：即最后插入的数据项，移除这个数据项后才能访问倒数第二个插入的数据项，以此类推。栈可以用数组来实现，也可以用链表来实现。2）栈的数组实现栈的Java代码：publicclassMyStack{privatelong[]arr;//底层使用数组实现privateinttop;publicMyStack(){top=-1;arr=newlong[10];}publicMyStack(intmaxSize){arr=newlong[maxSize];top=-1;}//putitemontopofstackarr[++top]=value;publicvoidpush(longvalue){}//takeitemfromtopofstackpubliclongpop(){}returnarr[top--];//peekattopofstackpubliclongpeek(){}returnarr[top];//tureifstackisemptyreturn(top==-1);publicbooleanisEmpty(){}//tureifstackisfullpublicbooleanisFull(){}return(top==arr.length-1);}测试栈的特性：publicvoidtestMyStack()throwsException{MyStackmyStack=newMyStack(4);myStack.push(12);myStack.push(34);myStack.push(56);myStack.push(78);System.out.println(myStack.isFull());//truewhile(!myStack.isEmpty()){System.out.print(myStack.pop());//78,56,34,12if(!myStack.isEmpty()){System.out.print(\\");}}System.out.println();System.out.println(myStack.isFull());//false}2.队列

1）队列模型队列（Queue，又FIFO：先进先出）是一种插入时在一端进行而删除时在另一端进行的数据结构。为解决顺序队列假溢出问题，而采用循环队列：即让队头、队尾指针在达到尾端时，又绕回到开头。2）队列的数组实现队列的Java代码：publicclassMyQueue{privatelong[]arr;privateintsize;privateintfront;privateintrear;publicMyQueue(){size=0;arr=newlong[10];front=0;}rear=-1;publicMyQueue(intmaxSize){arr=newlong[maxSize];size=0;front=0;}rear=-1;//putitematrearofqueuepublicvoidinsert(longvalue){if(isEmpty()){//throwexceptionifqueueisfull}thrownewArrayIndexOutOfBoundsException();if(rear==arr.length-1){//dealwithwraparound(环绕式处理)rear=-1;}arr[++rear]=value;//incrementrearandinsert}size++;//incrementsize//takeitemfromfrontofqueuepubliclongremove(){longvalue=arr[front++];//getvalueandincrementfrontif(front==arr.length){//dealwithwraparound}front=0;size--;//onelessitem}returnvalue;//peekatfrontofqueuepubliclongpeek(){}returnarr[front];//trueifqueueisemptyreturn(size==0);publicbooleanisEmpty(){}//trueifqueueisfullpublicbooleanisFull(){}return(size==arr.length);}测试队列的特性：publicvoidtestMyQueue()throwsException{MyQueuemyQueue=newMyQueue(4);myQueue.insert(12);myQueue.insert(34);myQueue.insert(56);myQueue.insert(78);System.out.println(myQueue.isFull());//truewhile(!myQueue.isEmpty()){System.out.print(myQueue.remove());//12,34,56,78if(!myQueue.isEmpty()){System.out.print(\\");}}System.out.println();System.out.println(myQueue.isEmpty());//truemyQueue.insert(99);System.out.println(myQueue.peek());//99}第四讲链表

1.链结点

一个链结点（Link，或称结点）是某个类的对象，该对象中包含对下一个链结点引用的字段（通常叫next）。而链表本身的对象中有一个字段指向对第一个链结点的引用。Link类的定义：publicclassLink{publiclongdata;//dataitempublicLinknext;//nextlinkinlistpublicLink(longdata){}this.data=data;publicvoiddisplayLink(){//displayourself}System.out.print(data+\"-->\");}2.单链表（LinkList）

LinkList类显示了一个单链表，该链表可以进行的操作有：在链表头插入一个数据（insertFirst）：设置新添加的结点的next设为原来的头结点，再将新添加的结点设为头结点。在链表头删除一个数据（deleteFirst）：将第二个结点设为头结点。遍历链表显示所有数据（displayList）：使用临时指针current，从头结点开始，沿着链表先前移动，依次遍历每个节点。LinkList类：publicclassLinkList{privateLinkfirst;//referencetofirstlinkonlistpublicLinkList(){}this.first=null;//insertatstartoflistpublicvoidinsertFirst(longvalue){LinknewLink=newLink(value);newLink.next=first;//newLink-->oldfirst}first=newLink;//first-->newLink//deletefirstitempublicLinkdeleteFirst(){if(first==null){}returnnull;Linktemp=first;first=first.next;//deleteit:first-->oldnext}returntemp;//returndeletedlinkpublicvoiddisplayList(){Linkcurrent=first;while(current!=null){//untilendoflistcurrent.displayLink();//startatbeginningoflist}}current=current.next;//movelisttonextlinkSystem.out.println();}测试LinkList类的方法：publicvoidtestLinkList()throwsException{LinkListlinkList=newLinkList();linkList.insertFirst(88);linkList.insertFirst(66);linkList.insertFirst(44);linkList.insertFirst(22);linkList.displayList();//22-->44-->66-->88-->linkList.deleteFirst();}linkList.displayList();//44-->66-->88-->3.查找和删除指定链结点

此外，还能对指定的结点值进行查找和删除：查找指定结点（find）：类似于之前的displayList方法。删除指定结点（delete）：在删除指定结点时，必须把前一个结点和后一个结点连接在一起，所以需要一个临时指针（previous）来保存对前一个结点的引用。向LinkList类中添加查找（find）和删除（delete）方法：//findlinkwithgivenkeypublicLinkfind(longkey){Linkcurrent=first;//startat'first'while(current.data!=key){if(current.next==null){//didn'tfinditreturnnull;}else{}current=current.next;//gotonextlink}}returncurrent;//deletelinkwithgivenkeypublicLinkdelete(longkey){Linkprevious=first;Linkcurrent=first;//searchforexpectedlinkwhile(current.data!=key){if(current.next==null){}else{returnnull;//didn'tfinditprevious=current;}}current=current.next;//gotonextlinkif(current==first){//iffirstlink,changefirst}else{}}first=first.next;//otherwise,bypassit//finditprevious.next=current.next;returncurrent;测试添加的find和delete方法：publicvoidtestLinkList()throwsException{LinkListlinkList=newLinkList();linkList.insertFirst(88);linkList.insertFirst(66);linkList.insertFirst(44);linkList.insertFirst(22);linkList.displayList();//22-->44-->66-->88-->linkList.find(44).displayLink();//44-->System.out.println();System.out.println();}linkList.delete(44).displayLink();//44-->linkList.displayList();//22-->66-->88-->第五讲双端链表和双向链表

1.双端链表

链表中保存着对最后一个链结点的引用从头部进行插入（insertFirst）：要对链表进行判断，如果链表为空，则设置尾结点为新添加的结点。从尾部进行插入（insertLast）：如果链表为空，则直接设置头结点为新添加的结点，否则设置尾结点的后一个节点为新添加的结点。从头部进行删除（deleteFirst）：判断头结点是否有下一个结点，如果没有则设置尾结点为null。双端链表FirstLastList类：publicclassFirstLastList{privateLinkfirst;//referencetofirstlinkprivateLinklast;//referencetolastlinkpublicFirstLastList(){this.first=null;this.last=null;}publicbooleanisEmpty(){//trueifnolinks}returnfirst==null;//insertatfrontoflistpublicvoidinsertFirst(longvalue){LinknewLink=newLink(value);if(isEmpty()){//ifemptylist}last=newLink;//newLink<--lastnewLink.next=first;//newLink-->oldfirst}first=newLink;//first-->newLink//insertatendoflistpublicvoidinsertLast(longvalue){LinknewLink=newLink(value);if(isEmpty()){//ifemptylist}else{first=newLink;//first-->newLink}}last.next=newLink;//oldlast-->newLinklast=newLink;//newLink<--last//deletefirstlinkpublicLinkdeleteFirst(){Linktemp=first;if(first.next==null){//ifonlyoneitem}last=null;//null<--lastfirst=first.next;}returntemp;//first-->oldnextpublicvoiddisplayList(){Linkcurrent=first;while(current!=null){//untilendoflistcurrent.displayLink();//startatbeginningoflist}}current=current.next;//movelisttonextlinkSystem.out.println();}测试FirstLastList类及输出结果：publicvoidtestFirstLastList()throwsException{FirstLastListlist=newFirstLastList();list.insertLast(24);list.insertFirst(13);list.insertFirst(5);list.insertLast(46);list.displayList();//5-->13-->24-->46-->list.deleteFirst();}list.displayList();//13-->24-->46-->2.双向链表

双向链表既允许向后遍历，也允许向前遍历整个链表。即每个节点除了保存了对下一个节点的引用，同时后保存了对前一个节点的引用。从头部进行插入（insertFirst）：要对链表进行判断，如果为空，则设置尾结点为新添加的结点；如果不为空，还需要设置头结点的前一个结点为新添加的结点。从尾部进行插入（insertLast）：如果链表为空，则直接设置头结点为新添加的结点，否则设置尾节点的后一个结点为新添加的结点。同时设置新添加的结点的前一个结点为尾结点。从头部进行删除（deleteFirst）：判断头结点是否有下一个结点，如果没有则设置尾结点为null；否则设置头结点的下一个结点的previous为null。从尾部进行删除（deleteLast）：如果头结点后没有其他结点，则设置头结点为null。否则设置尾结点的前一个结点的next为null。设置尾结点为其前一个结点。在指定结点后插入（insertAfter）：删除指定结点（deleteKey）：不再需要在使用一个临时的指针域指向前一个结点。双向链表的链接点Link类的定义：publicclassDoubleLink{publiclongdata;//dataitempublicDoubleLinknext;//nextlinkinlistpublicDoubleLinkprevious;//previouslinkinlistpublicDoubleLink(longdata){}this.data=data;publicvoiddisplayLink(){//displayourself}System.out.print(data+\"<==>\");}双向链表DoublyLinkedList类：publicclassDoublyLinkedList{privateDoubleLinkfirst;//referencetofirstlinkprivateDoubleLinklast;//referencetolastlinkpublicDoublyLinkedList(){this.first=null;this.last=null;}publicbooleanisEmpty(){//trueifnolinks}returnfirst==null;//insertatfrontoflistpublicvoidinsertFirst(longvalue){if(isEmpty()){//ifemptylistDoubleLinknewLink=newDoubleLink(value);}else{}last=newLink;//newLink<--lastfirst.previous=newLink;//newLink<--oldfirstnewLink.next=first;//newLink-->oldfirst}first=newLink;//first-->newLink//insertatendoflistpublicvoidinsertLast(longvalue){if(isEmpty()){//ifemptylist}else{DoubleLinknewLink=newDoubleLink(value);first=newLink;//first-->newLinklast.next=newLink;//oldlast-->newLink}}newLink.previous=last;//oldlast<--newLinklast=newLink;//newLink<--last//deletefirstlinkpublicDoubleLinkdeleteFirst(){DoubleLinktemp=first;if(first.next==null){//ifonlyoneitem}else{}last=null;//null<--lastfirst.next.previous=null;//null<--oldnext//first-->oldnextfirst=first.next;}returntemp;//deletelastlinkpublicDoubleLinkdeleteLast(){DoubleLinktemp=last;if(first.next==null){//ifonlyoneitem}else{}first=null;//first-->nulllast.previous.next=null;//oldprevious-->nulllast=last.previous;//oldprevious<--last}returntemp;//insertdatajustafterkeypublicbooleaninsertAfter(longkey,longdata){DoubleLinkcurrent=first;while(current.data!=key){//untilmatchisfoundif(current.next==null){}else{}returnfalse;//startatbeginningcurrent=current.next;}//findthepositionofkeyDoubleLinknewLink=newDoubleLink(data);//makenewlinkif(current==last){//iflastlink,newLink.next=null;//newLink-->nulllast=newLink;//newLink<--last//notlastlink.}else{newLink.next=current.next;//newLink-->oldnext}current.next.previous=newLink;//newLink<--oldnextcurrent.next=newLink;//oldcurrent-->newLinkreturntrue;newLink.previous=current;//oldcurrent<--newLink}//deletelinkwithgivenkeypublicDoubleLinkdeleteKey(longkey){while(current.data!=key){DoubleLinkcurrent=first;//searchforexpectedlinkif(current.next==null){}else{}returnnull;//didn'tfinditcurrent=current.next;//gotonextlink}if(current==first){//iffirstlink,changefirst}else{first=first.next;//first-->oldnextcurrent.previous.next=current.next;//otherwise,oldprevious-->oldnext}//finditif(current==last){//lastitem?}else{}}last=last.previous;//oldprevious<--lastcurrent.next.previous=current.previous;//notlast:oldprevious<--oldnextreturncurrent;publicvoiddisplayForward(){System.out.print(\"first-->last:\");DoubleLinkcurrent=first;current.displayLink();while(current!=null){//untilendoflist//startatbeginningoflist}}current=current.next;//movelisttonextlinkSystem.out.println();publicvoiddisplayBackward(){DoubleLinkcurrent=last;current.displayLink();System.out.print(\"last-->first:\");while(current!=null){//untilstartoflist//startatendoflist}}current=current.previous;//movelisttopreviouslinkSystem.out.println();}测试该类的主要方法：publicvoidtestDoublyLinkedList()throwsException{DoublyLinkedListlist=newDoublyLinkedList();list.insertLast(24);list.insertFirst(13);list.insertFirst(5);list.insertLast(46);list.displayForward();//first-->last:5<==>13<==>24<==>46<==>list.displayBackward();//last-->first:46<==>24<==>13<==>5<==>list.deleteFirst();list.deleteLast();list.displayForward();//first-->last:13<==>24<==>46<==>list.displayForward();//first-->last:13<==>24<==>list.insertAfter(13,17);list.deleteKey(24);}list.displayForward();//first-->last:13<==>17<==>24<==>list.displayForward();//first-->last:13<==>17<==>第六讲递归的应用

递归（Recursion）是一种在方法（函数）的定义中调用方法自身的编程技术。递归算法解决问题的特点：(1)递归就是在过程或函数里调用自身。(2)在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。(3)递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。(4)在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。在实际编程中尤其要注意栈溢出问题。构成递归需具备的条件：a.子问题须与原始问题为同样的事，且更为简单；b.不能无地调用本身，须有个出口，化简为非递归状况处理。1.三角数字

该数列中的首项为1，第n项是由第n-1项加n后得到的。1）使用循环查找第n项publicstaticinttriangleByWhile(intn){inttotal=0;while(n>0){n--;total=total+n;}}returntotal;System.out.println(Triangle.triangleByWhile(5));//152）使用递归查找第n项publicstaticinttriangleByRecursion(intn){if(n==1){}else{}return1;returnn+triangleByRecursion(n-1);}System.out.println(Triangle.triangleByRecursion(5));//152.Fibonacci数列

Fibonacci数列的第0项为0，第二项为1，第n项为第n-1项加上n-2项后得到。该数列的递归算法实现如下：publicstaticintfibo(intn){if(n==1||n==2){return1;}else{returnfibo(n-1)+fibo(n-2);}}System.out.println(FibonacciSequence.fibo(8));//21程序的运行流程如下：第七讲递归的高级应用

1.汉诺塔问题

汉诺塔问题描述如下：有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：每次只能移动一个圆盘；大盘不能叠在小盘上面。提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。问：如何移？最少要移动多少次？汉诺塔问题的递归求解方法（移动子树）：把除了最低端盘子外的所有盘子形成的子树移动到一个中介塔上，然后把最低端盘子移到目标塔上，如此循环最终把那个子树移动到目标塔上。Java代码实现如下：publicstaticvoiddoTowers(inttopN,charfrom,charinter,charto){if(topN==1){System.out.println(\"Disk1from\"+from+\"to\"+to);}else{doTowers(topN-1,from,to,inter);//from-->interSystem.out.println(\"Disk\"+topN+\"from\"+from+\"to\"+to);doTowers(topN-1,inter,from,to);//inter-->to}}HanoiTower.doTowers(3,'A','B','C');//////////////Disk1fromAtoCDisk2fromAtoBDisk1fromCtoBDisk3fromAtoCDisk1fromBtoADisk2fromBtoCDisk1fromAtoC2.递归的二分查找

3.归并排序

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。4.消除递归

递归算法实际上是一种分而治之的方法，它把复杂问题分解为简单问题来求解。对于某些复杂问题(例如hanio塔问题)，递归算法是一种自然且合乎逻辑的解决问题的方式，但是递归算法的执行效率通常比较差。因此，在求解某些问题时，常采用递归算法来分析问题，用非递归算法来求解问题；另外，有些程序设计语言不支持递归，这就需要把递归算法转换为非递归算法。将递归算法转换为非递归算法有两种方法，一种是直接求值，不需要回溯；另一种是不能直接求值，需要回溯。前者使用一些变量保存中间结果，称为直接转换法；后者使用栈保存中间结果，称为间接转换法，下面分别讨论这两种方法。1.直接转换法直接转换法通常用来消除尾递归和单向递归，将递归结构用循环结构来替代。尾递归是指在递归算法中，递归调用语句只有一个，而且是处在算法的最后。例如求阶乘的递归算法：publiclongfact(intn){if(n==0)return1;elsereturnn*fact(n-1);}当递归调用返回时，是返回到上一层递归调用的下一条语句，而这个返回位置正好是算法的结束处，所以，不必利用栈来保存返回信息。对于尾递归形式的递归算法，可以利用循环结构来替代。例如求阶乘的递归算法可以写成如下循环结构的非递归算法：publiclongfact(intn){ints=0;for(inti=1;is=s*i;//用s保存中间结果returns;}单向递归是指递归算法中虽然有多处递归调用语句，但各递归调用语句的参数之间没有关系，并且这些递归调用语句都处在递归算法的最后。显然，尾递归是单向递归的特例。例如求斐波那契数列的递归算法如下：publicintf(intn){if(n==1||n==0)return1;elsereturnf(n-1)+f(n-2);}对于单向递归，可以设置一些变量保存中间结构，将递归结构用循环结构来替代。例如求斐波那契数列的算法中用s1和s2保存中间的计算结果，非递归函数如下：publicintf(intn){inti,s;ints1=1,s2=1;for(i=3;i{s=s1+s2;s2=s1;//保存f(n-2)的值s1=s;//保存f(n-1)的值}returns;}2.间接转换法该方法使用栈保存中间结果，一般需根据递归函数在执行过程中栈的变化得到。其一般过程如下：将初始状态s0进栈while(栈不为空){退栈，将栈顶元素赋给s;if(s是要找的结果)返回;else{寻找到s的相关状态s1;将s1进栈}}间接转换法在数据结构中有较多实例，如二叉树遍历算法的非递归实现、图的深度优先遍历算法的非递归实现等等，请读者参考主教材中相关内容第八讲希尔排序

希尔排序是由DonaldL.Shell提出来的，希尔排序基于插入排序，并且添加了一些新的特性，从而大大提高了插入排序的执行效率。插入排序的缺陷：多次移动。假如一个很小的数据在靠右端位置上，那么要将该数据排序到正确的位置上，则所有的中间数据都要向右移动一位。希尔排序的优点：希尔排序通过加大插入排序中元素元素之间的间隔，并对这些间隔的元素进行插入排序，从而使得数据可以大幅度的移动。当完成该间隔的排序后，希尔排序会减少数据间的间隔再进行排序。依次进行下去。1.基本思想

希尔排序（最小增量排序）：算法先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成。间隔的计算：间隔h的初始值为1，通过h=3*h+1来循环计算，知道该间隔大于数组的大小时停止。最大间隔为不大于数组大小的最大值。间隔的减少：通过公式h=(h-1)/3来计算。2.算法实现

希尔排序的Java代码：//ShellsortpublicstaticvoidshellSort(long[]arr){inth=1;while(h0){//decreasingh,untilh=1for(inti=h;ih-1&&arr[j-h]>temp){//untiloneissmallerarr[j]=arr[j-h];//shiftitemrightj-=h;//golefthposition}}arr[j]=temp;//insertmarkeditem//decreaseh}h=(h-1)/3;}测试希尔排序及输出结果：publicvoidtestShellSort()throwsException{long[]arr={10,5,8,7,1,6,4,9,2,3};Sort.shellSort(arr);System.out.println(Arrays.toString(arr));//[1,2,3,4,5,6,7,8,9,10]}第九讲快速排序

1.快速排序的基本思想

快速排序：选择一个关键字，通常选择第一个元素或者最后一个元素，通过一趟扫描，将待排序列分成两部分，一部分比关键字小，另一部分大于等于关键字，此时关键字在其排好序后的正确位置，然后再用同样的方法递归地排序划分出来的两部分。如何进行划分：设定关键字，将比关键字小的数据放在一组，比关键字大的放在另一组。如何自动设定关键字：设置数组最右端的数据为关键字。2.快速排序的算法实现

快速排序的Java代码：publicclassSort{publicstaticvoidquickSort(long[]arr,intleft,intright){if(right-left<=0){//ifsize<=1,return;//alreadysorted}else{//otherwiselongkey=arr[right];//rightmostitem//partitionrangeintpoint=partition(arr,left,right,key);quickSort(arr,left,point-1);//sortleftsidequickSort(arr,point+1,right);//sortrightside}}publicstaticintpartition(long[]arr,intleft,intright,longkey)intleftP=left-1;//left(after++)while(true){{intrightP=right;//right-1(after--)while(leftPleft&&arr[--rightP]>key)////while(arr[++leftP]=rightP){;//findsmalleritem;//findbiggeritemwhile(rightP>0&&arr[--rightP]>key);break;//partitiondonelongtemp=arr[leftP];arr[rightP]=temp;//ifpointerscross,}else{//notcrossed,soswapelementsarr[leftP]=arr[rightP];}}//restorekeylongtemp=arr[leftP];arr[leftP]=arr[right];arr[right]=temp;}returnleftP;//returnkeylocation}测试快速排序及输出结果：publicvoidtestQuickSort()throwsException{//alsocanfillarrwithrandomnumberslong[]arr={10,5,8,7,1,6,4,9,2,3};Sort.quickSort(arr,0,arr.length-1);System.out.println(Arrays.toString(arr));//[1,2,3,4,5,6,7,8,9,10]}补充基数排序

基数排序：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。第十讲二叉树的基本概念

1.树

1）为什么要使用树有序数组插入数据项和删除数据项太慢链表查找数据太慢在树中能快速地查找、插入和删除数据项2）树的基本概念路径：顺着连接节点的边从一个节点到另一个节点，所经过的节点顺序排列称为路径。根：树最上面的节点称为根节点。一棵树只有一个根，而且从根到任何一个节点有且只有一条路径。父节点：每个节点都有一条边向上连接到另一个节点，这个节点就称为是下面这个节点的父节点。子节点：每个节点都有一条边向下连接到另一个节点，下面的节点就是该节点的子节点。叶子节点：没有子节点的节点称为叶子节点。子树：每个节点都可以作为一个子树的根，它和它所有的子节点以及子节点的子节点组合在一起就是一个子树。访问：访问一个节点是为了在这个节点上执行一些操作，如查看节点的数据项。但是如果仅仅是经过了一个节点，不认为是访问了这个节点。层：一个节点的层数是指从根节点开始到这个节点有多少代。2.二叉树

树的每个节点最多只能有两个子节点的树，称为二叉树。二叉树的代码实现：节点类：publicclassNode{longdata;NodeleftChild;NoderighttChild;publicNode(longdata){}this.data=data;}二叉树：publicclassBinaryTree{Noderoot;publicvoidinsert(longvalue){}publicvoiddelete(longvalue){}publicvoidfind(longvalue){}}第十一讲二叉树的基本操作

1.插入节点

从根节点开始查找一个相应的节点，这个节点将成为新插入节点的父节点。当父节点找到后，通过判断新节点的值比父节点的值的大小来决定是连接到左子节点还是右子节点。插入节点的Java代码实现：publicvoidinsert(longvalue){NodenewNode=newNode(value);if(root==null){//nonodeinrootroot=newNode;}else{//rootoccupiedNodecurrent=root;//startatrootNodeparent;//pointtoparentwhile(true){parent=current;if(value从根节点开始查找，如果查找的值比当前节点的值小，则继续查找器做左子树，否则查找其右子树。查找节点的Java代码实现：//findnodewithgivenkeypublicNodefind(longvalue){Nodecurrent=root;//startatrootwhile(current.data!=value){//whilenomatch,if(value遍历树：遍历树是根据一个特定的顺序访问树的每一个节点，根据顺序的不同分为前序。中序和后序遍历三种。1.前序遍历

前序遍历：先访问根节点，再前序遍历左子树，最后前序遍历右子树；前序遍历的Java代码实现：publicvoidfrontOrder(Nodenode){if(node!=null){System.out.println(node.data);frontOrder(node.leftChild);frontOrder(node.righttChild);}}tree.frontOrder(tree.root);//342167562.中序遍历

中序遍历：先中序遍历左子树，再访问根节点，最后中序遍历右子树；中序遍历按关键值的升序节点，从而形成一组有序数据。中序遍历的Java代码实现：publicvoidinOrder(Nodenode){if(node!=null){inOrder(node.leftChild);System.out.println(node.data);}inOrder(node.righttChild);tree.inOrder(tree.root);//21345667}3.后序遍历

后序遍历：先后序遍历左子树，再后序遍历右子树，最后访问根节点。后序遍历的Java代码实现：publicvoidafterOrder(Nodenode){if(node!=null){afterOrder(node.leftChild);afterOrder(node.righttChild);System.out.println(node.data);}}tree.afterOrder(tree.root);//21566734第十三讲删除二叉树节点

1.删除节点的三种情况

删除节点是二叉树操作中最复杂的。在删除之前首先要查找要删的节点。找到节点后，这个要删的节点可能会有三种情况需要考虑：该节点是叶子节点，没有子节点要删除叶子节点，只需要改变该节点的父节点的引用值，将指向该节点的引用设置为null就可以了。该节点有一个子节点。改变父节点的引用，将其指向要删除节点的子节点。该节点有两个子节点。要删除节点有两个子节点，就需要使用它的中序后继来替代该节点。2.删除节点的代码实现

删除节点的Java代码实现：//deletenodewithgivenkeypublicbooleandelete(longvalue){Nodecurrent=root;Nodeparent=current;booleanisLeftChild=true;parent=current;while(current.data!=value){//whilenomatch,if(value1.平衡树与非平衡树

1）二叉树的问题前面介绍了二叉树，普通的二叉树作为数据存储的工具有很大的优势，可以快速插入、删除和查找数据项。遗憾的是，这仅仅是相对于插入随机数据，如果插入的数据是有序的，速度就变得特别的慢。2）平衡树和非平衡树平衡树：插入随机的数据。非平衡树：插入有序的数据。完全平衡树：2.红黑规则

1）红黑规则（1）每个节点不是红色的就是黑色的（2）根总是黑色的（3）如果节点是红色的，则它的子节点必须是黑色的（4）从根节点到叶节点的每条路径，必须包含相同数目的黑色节点2）纠正违规将不符合红黑规则的数纠正为红黑树。（1）改变节点的颜色（2）执行旋转操作第十五讲哈希表

1.什么是哈希表

哈希表是一种数据结构，它可以提供快速的插入和查找操作。哈希表是基于数组来实现的。2.哈希化

1）直接将关键字作为索引Info类：publicclassInfo{privateintid;privateStringname;publicInfo(intid,Stringname){this.id=id;this.name=name;}publicintgetId(){}returnid;publicvoidsetId(intid){}this.id=id;publicStringgetName(){}returnname;publicvoidsetName(Stringname){}this.name=name;}关键字作为索引的Java代码实现：publicclassHashTable{Info[]arr;publicHashTable(){arr=newInfo[10000];}publicHashTable(intmaxSize){arr=newInfo[maxSize];}//insertelementpublicvoidinsert(Infoinfo){arr[info.getId()]=info;}//findelementpublicInfofind(intid){returnarr[id];}}测试插入和查找方法：publicvoidtestHashTable()throwsException{HashTabletable=newHashTable();table.insert(newInfo(1,\"zhangSan\"));table.insert(newInfo(2,\"tianQi\"));System.out.println(table.find(1).getName());}2）将单词转换成索引①将字母转换成ASCII码，然后进行相加转码索引的Java代码实现：publicinthashcode(Stringkey){intcode=0;for(inti=key.length()-1;i>=0;i--){intvalue=key.charAt(i)-96;code+=value;}returncode;}//insertelementpublicvoidinsert(Infoinfo){}arr[hashcode(info.getId())]=info;//findelementpublicInfofind(Stringkey){}returnarr[hashcode(key)];测试及输出：publicvoidtestHashTable()throwsException{HashTabletable=newHashTable();table.insert(newInfo(\"abc\",\"zhangSan\"));table.insert(newInfo(\"bbb\",\"tianQi\"));System.out.println(table.find(\"abc\").getName());//tianQiSystem.out.println(table.find(\"bbb\").getName());//tianQi}从上可见上面的编码方式存在很高的重复率。②幂的连乘幂的连乘编码Java代码实现：publicinthashcode(Stringkey){intcode=0;intpower27=1;for(inti=key.length()-1;i>=0;i--){intvalue=key.charAt(i)-96;code+=value*power27;}}power27*=27;returncode;测试及输出：System.out.println(table.find(\"abc\").getName());//zhangSanSystem.out.println(table.find(\"bbb\").getName());//tianQi③压缩可选值为了解决编码后的数据过大，对其进行取模运算publicinthashcode(Stringkey){BigIntegerhashVal=newBigInteger(\"0\");BigIntegerpow27=newBigInteger(\"1\");for(inti=key.length()-1;i>=0;i--){intletter=key.charAt(i)-96;BigIntegerletterB=newBigInteger(String.valueOf(letter));hashVal=hashVal.add(letterB.multiply(pow27));pow27=pow27.multiply(newBigInteger(String.valueOf(27)));}returnhashVal.mod(newBigInteger(String.valueOf(arr.length))).intValue();}3.压缩后仍可能出现的问题

冲突，不能保证每个单词都映射到数组的空白单元。解决办法：①开放地址法②链地址法第十六讲开放地址法

1.什么是开放地址法

当冲突发生时，通过查找数组的一个空位，并将数据填入，而不再用哈希函数得到的数组下标，即开放地址法。2.数据的插入

数据插入的Java代码实现：//insertelementpublicvoidinsert(Infoinfo){Stringkey=info.getId();intcode=hashcode(key);//hashthekeywhile(arr[code]!=null&&arr[code].getName()!=null){++code;//gotonextcellcode%=arr.length;//wraparoundifnecessary}arr[code]=info;}HashTabletable=newHashTable();table.insert(newInfo(\"a\",\"zhangSan\"));table.insert(newInfo(\"ct\",\"tianQi\"));3.数据的查找

数据查找的Java代码实现：//findelementwithkeypublicInfofind(Stringkey){intcode=hashcode(key);//hashthekeywhile(arr[code]!=null){//untilemptycell.if(arr[code].getId()==key){//foundthekey?returnarr[code];//yes,returnelement}++code;//gotonextcellcode%=arr.length;//wraparoundifnecessary}returnnull;}System.out.println(table.find(\"a\").getName());//zhangSanSystem.out.println(table.find(\"ct\").getName());//tianQi4.数据的删除

数据删除的Java代码实现：//deleteelementpublicInfodelete(Stringkey){intcode=hashcode(key);//hashthekeyif(arr[code].getId()==key){temp.setName(\"caonima\");while(arr[code]!=null){//untilemptycell,Infotemp=arr[code];//saveitemarr[code].setName(null);//deleteitem}returntemp;//returnitem++code;//gotonextcell}}code%=arr.length;//wraparoundifnecessaryreturnnull;System.out.println(table.delete(\"a\").getName());//null第十七讲链地址法

1.什么是链地址法

在哈希表每个单元中设置链表。某个数据项的关键字还是像通常映射到哈希表的单元中，而数据项本身插入到单元的链表中。2.数据的插入

LinkList相关类：publicclassLink{publicInfoinfo;//dataitempublicLinknext;//nextlinkinlistpublicLink(Infoinfo){}this.info=info;}publicclassLinkList{privateLinkfirst;//referencetofirstlinkonlistpublicLinkList(){}this.first=null;//insertatstartoflistpublicvoidinsertFirst(Infoinfo){LinknewLink=newLink(info);newLink.next=first;//newLink-->oldfirst}first=newLink;//first-->newLink//deletefirstitempublicLinkdeleteFirst(){if(first==null){}returnnull;Linktemp=first;first=first.next;//deleteit:first-->oldnext}returntemp;//returndeletedlink//findlinkwithgivenkeyLinkcurrent=first;publicLinkfind(Stringkey){while(!key.equals(current.info.getId())){if(current.next==null){}else{}returnnull;//startat'first'//didn'tfinditcurrent=current.next;//gotonextlink}}returncurrent;//deletelinkwithgivenkeypublicLinkdelete(Stringkey){Linkprevious=first;Linkcurrent=first;//searchforexpectedlinkwhile(!key.equals(current.info.getId())){if(current.next==null){}else{returnnull;//didn'tfinditprevious=current;}current=current.next;//gotonextlink}if(current==first){//iffirstlink,changefirst}else{}}first=first.next;//otherwise,bypassit//finditprevious.next=current.next;returncurrent;}数据插入的Java代码实现：//insertelementpublicvoidinsert(Infoinfo){Stringkey=info.getId();intcode=hashcode(key);//hashthekeyif(arr[code]==null){arr[code]=newLinkList();}arr[code].insertFirst(info);}HashTabletable=newHashTable();table.insert(newInfo(\"a\",\"zhangSan\"));table.insert(newInfo(\"ct\",\"wangWu\"));3.数据的查找

数据查找的Java代码实现：//findelementwithkeypublicInfofind(Stringkey){intcode=hashcode(key);//hashthekeyreturnarr[code].find(key).info;}System.out.println(table.find(\"a\").getName());//zhangSanSystem.out.println(table.find(\"ct\").getName());//tianQi4.数据的删除

数据删除的Java代码实现：//deleteelementpublicInfodelete(Stringkey){intcode=hashcode(key);//hashthekey}returnarr[code].delete(key).info;System.out.println(table.delete(\"a\").getName());//zhangSan//java.lang.NullPointerExceptionSystem.out.println(table.find(\"a\").getName());补充堆排序

堆排序是一种树形选择排序，是对直接选择排序的有效改进。堆的定义如下：具有n个元素的序列（h1,h2,…,hn),当且仅当满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,…,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项（大顶堆）。完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。第十八讲图简介

1.图的基本概念

1）什么是图图是一种和树相像的数据结构，通常有一个固定的形状，这是由物理或抽象的问题来决定的。2）邻接如果两个顶点被同一条边连接，就称这两个顶点是邻接的。3）路径路径是从一个顶点到另一个顶点经过的边的序列。4）连通图和非连通图至少有一条路径可以连接所有的顶点，那么这个图就是连通的，否则是非连通的。5）有向图和无向图有向图的边是有方向的，如果只能从A到B，不能从B到A。无向图的边是没有方向的，可以从A到B，也可以从B到A。6）带权图有些图中，边被赋予了一个权值，权值是一个数字，可以代表如两个顶点的物理距离，或者是一个顶点到另一个顶点的时间等等。这样的图叫做带权图。2.图的Java代码实现

Vertex顶点类：publicclassVertex{charlabel;booleanwasVisited;publicVertex(charlabel){this.label=label;wasVisited=false;}}Graph图类：publicclassGraph{privateintmaxSize=20;privateVertex[]vertexList;//arrayofverticesprivateint[][]adjmat;//adjacencymatrixprivateintnVertex;//currentnumberofverticesprivateMyStacktheStack;publicGraph(){vertexList=newVertex[maxSize];nVertex=0;adjmat=newint[maxSize][maxSize];theStack=newMyStack();for(inti=0;i1.图的搜索

图的搜索是指从一个指定的顶点到达哪些顶点。有两种常用的方法可以用来搜索图：深度优先搜索（DFS）和广度优先搜索（BFS）。深度优先搜索通过栈来实现，而广度优先搜索通过队列来实现。2.深度优先搜索

1）深度优先搜索的原则①如果可能，访问一个邻接的未访问的顶点，标记它，并把它放入栈中。②当不能执行规则1时，如果栈不能空，就从栈中弹出一个顶点。③当不能执行规则1和规则2时，就完成了整个搜搜过程。2）深度优先搜索的Java代码实现//depth-firstsearchpublicvoiddfs(){//beginatvertex0vertexList[0].wasVisited=true;//markitSystem.out.println(vertexList[0].label);theStack.push(0);//pushitwhile(!theStack.isEmpty()){//untilstackempty,//getanunvisitedvertexadjacenttostacktopif(v==-1){//ifnosuchvertex,}else{//ifitexists,theStack.pop();intv=getAdjUnvisitedVertex((int)theStack.peek());vertexList[v].wasVisited=true;//markitSystem.out.println(vertexList[v].label);theStack.push(v);//pushit}}//stackisempty,sowe'redonefor(inti=0;i1）广度优先搜索的原则①访问下一个邻接的未访问过的顶点，这个顶点必须是当前节点的邻接点，标记它，并把它插入到队列中。②如果无法执行规则1，那么就从队列头取出一个顶点，并使其作为当前顶点。③当队列为空不能执行规则2时，就完成了整个搜索过程。2）广度优先搜索的Java代码实现第二十讲图的最小生成树

1.最小生成树

连接每个顶点最少的连线。最小生成树边的数量总是比顶点的数量少1。2.最小生成树的Java代码实现

//minimumspanningtree(depthfirst)publicvoidmst(){//startat0theStack.push(0);//pushitvertexList[0].wasVisited=true;//markitwhile(!theStack.isEmpty()){//untilstackempty,intcurrentVertex=(int)theStack.peek();//getanunvisitedvertexadjacenttostacktopintv=getAdjUnvisitedVertex(currentVertex);if(v==-1){//ifnomoreneighbors,}else{//gotaneighbor,theStack.pop();//popitawayvertexList[v].wasVisited=true;//markit//dispalyedgefromcurrentVertextovSystem.out.print(vertexList[currentVertex].label+\"-\");System.out.println(vertexList[v].label);}}theStack.push(v);//pushit//stackisempty,sowe'redonefor(inti=0;i