Java數(shù)據(jù)結(jié)構(gòu)與經(jīng)典算法高手必會

第頁

大O表示法：粗略的量度方法即算法的速度是如何與數(shù)據(jù)項的個數(shù)相關(guān)的

2

排序 2優(yōu)先級隊列 6隊列 8棧 9鏈表 10單鏈表 12雙端鏈表 16有序鏈表 18雙向鏈表 20實(shí)現(xiàn)二叉樹前序遍歷迭代器 24迭代器 27合并搜索算法 30希爾排序 34快速排序 35二叉樹 37經(jīng)典算法的Java實(shí)現(xiàn) 42（1）河內(nèi)塔問題： 42（2）費(fèi)式數(shù)列 44（3）巴斯卡（Pascal）三角形 44（4）蒙地卡羅法求PI 46（5）最大公因數(shù)、最小公倍數(shù) 47（6）阿姆斯壯數(shù) 48（7）最大訪客數(shù) 48（8）洗撲克牌（亂數(shù)排列） 50（9）約瑟夫問題（JosephusProblem） 51（10）排列組合 53（11）得分排行 54（12）選擇、插入、氣泡排序 56（13）快速排序（一） 59（14）快速排序（二） 61（15）快速排序（三） 62（16）合并排序 63（17）基數(shù)排序 64（18）循序查找法（使用衛(wèi)兵） 66（20）插補(bǔ)查找法 68（21）費(fèi)式查找法 69（22）稀疏矩陣 72（23）多維矩陣轉(zhuǎn)一維矩陣 73（24）上三角、下三角、對稱矩陣 74（25）奇數(shù)魔方陣 76（26）4N魔方陣 77（27）2(2n+1)魔方陣 79大O表示法：粗略的量度方法即算法的速度是如何及數(shù)據(jù)項的個數(shù)相關(guān)的算法大O表示法表示的運(yùn)行時間線性查找O(N)二分查找O(logN)無序數(shù)組的插入O(1)有序數(shù)組的插入O(N)無序數(shù)組的刪除O(N)有序數(shù)組的刪除O(N)O(1)是最優(yōu)秀的,O(logN)良好,O(N)還可以,O(N2)稍差(在冒泡法中見到)排序publicclassJWzw{ //插入排序 publicvoidinsertArray(Integer[]in){ inttem=0; intnum=0; intupnum=0; for(inti=0;i<in.length;i++){ for(intj=i-1;j>=0;j--){ num++; if(in[j+1]<in[j]){ tem=in[j+1]; in[j+1]=in[j]; in[j]=tem; upnum++; else break; for(inti=0;i<in.length;i++){ System.out.print(in[i]); if(i<in.length-1) System.out.print(","); System.out.println(); System.out.println("插入排序循環(huán)次數(shù):"+num); System.out.println("移動次數(shù)："+upnum); System.out.print("\n\n\n"); //選擇排序 publicvoidchooseArray(Integer[]in){ inttem=0; intnum=0; intupnum=0; for(inti=0;i<in.length;i++) for(intj=i;j<in.length-1;j++){ num++; if(in[j+1]<in[j]){ tem=in[j+1]; in[j+1]=in[j]; in[j]=tem; upnum++; for(inti=0;i<in.length;i++){ System.out.print(in[i]); if(i<in.length-1) System.out.print(","); System.out.println(); System.out.println("選擇排序循環(huán)次數(shù):"+num); System.out.println("移動次數(shù)："+upnum); System.out.print("\n\n\n"); //冒泡排序 publicvoidefferArray(Integer[]in){ inttem=0; intnum=0; intupnum=0; for(inti=0;i<in.length;i++){ for(intj=i;j<in.length-1;j++) num++; if(in[j+1]<in[i]){ tem=in[j+1]; in[j+1]=in[i]; in[i]=tem; upnum++; for(inti=0;i<in.length;i++){ System.out.print(in[i]); if(i<in.length-1) System.out.print(","); System.out.println(); System.out.println("冒泡排序循環(huán)次數(shù):"+num); System.out.println("移動次數(shù)："+upnum); System.out.print("\n\n\n"); //打印乘法口訣 publicvoidprintMulti(){ for(intj=1;j<10;j++){ for(inti=1;i<=j;i++){ System.out.print(i+"*"+j+"="+j*i+"\t"); System.out.print("\t\n"); System.out.print("\n\n\n"); //打印N*1+N*2+N*3=num的所有組合 publicvoidprintNumAssemble(intnum){ for(inti=0;i<num+1;i++){ for(intj=0;j<num/2+1;j++){ for(intin=0;in<num/3+1;in++){ if(i*1+j*2+in*3==num){ System.out.println("小馬"+i+",\t中馬"+j+",\t大馬"+in); *@paramargs publicstaticvoidmain(String[]args){ JWzwjwzw=newJWzw(); intnum=3; jwzw.printMulti();//打印乘法口訣 jwzw.printNumAssemble(100);//打印N*1+N*2+N*3=num的所有組合 Integerin[]={8,89,5,84,3,45,12,33,77,98,456,878,654,213,897}; jwzw.efferArray(in);//冒泡排序 Integerin1[]={8,89,5,84,3,45,12,33,77,98,456,878,654,213,897}; jwzw.insertArray(in1);//插入排序 Integerin2[]={8,89,5,84,3,45,12,33,77,98,456,878,654,213,897}; jwzw.chooseArray(in2);//選擇排序 //inti=num++; //System.out.println(i); System.out.println(1000>>2);優(yōu)先級隊列classPriorityQueue{privatelong[]a=null;privateintnItems=0;privateintmaxSize=0;publicPriorityQueue(intmaxSize){a=newlong[maxSize];this.maxSize=maxSize;nItems=0;publicvoidinsert(longl){//優(yōu)先級隊列的插入不是隊尾,而是選擇一個合適的按照某種順序插入的//當(dāng)隊列長度為0時，如下//不為0時,將所有比要插入的數(shù)小的數(shù)據(jù)后移,這樣大的數(shù)就在隊列的頭部了inti=0;if(nItems==0){a[0]=l;}else{for(i=nItems-1;i>=0;i--){if(l<a[i])a[i+1]=a[i];elsebreak;a[i+1]=l;nItems++;publiclongremove(){//移出的是數(shù)組最上端的數(shù)，這樣減少數(shù)組元素的移動returna[--nItems];publicbooleanisEmpty(){return(nItems==0);publicbooleanisFull(){return(nItems==maxSize);publicintsize(){returnnItems;publicclassduilie{//隊列體類privateduilies;privateStringdata;duilie(Stringdata){this.data=data;publicStringgetData(){returndata;publicvoidsetData(Stringdata){this.data=data;publicduiliegetS(){returns;publicvoidsetS(duilies){this.s=s;publicclassduiliecz{//隊列操作類*@paramargsprivateinti=0;//隊列長privateduilietop=newduilie("");//隊列頭privateduilieend=newduilie("");//隊列尾publicvoidadd(Strings){//添加隊列duiliem=newduilie(s);if(i!=0){m.setS(top.getS());top.setS(m);}else{top.setS(m);end.setS(m);i++;隊列

publicvoiddel(){//刪除隊尾if(i==0){return;}elseif(i==1){top.setS(null);end.setS(null);}else{duilietop1=newduilie("");//隊列底查找用緩存top1.setS(top.getS());while(!top1.getS().getS().equals(end.getS())){top1.setS(top1.getS().getS());end.setS(top1.getS());i--;publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubduilieczm=newduiliecz();m.add("1");m.add("2");m.add("3");m.add("4");for(intn=0;n<4;n++){m.del();publicintgetI(){returni;publicduiliegetEnd(){returnend;publicduiliegetTop(){returntop;棧publicclassStack{ int[]arr; intlen=0; publicStack(){ arr=newint[100]; publicStack(intn){ arr=newint[n]; publicintsize(){ returnlen+1; //擴(kuò)大數(shù)組 publicvoidresize(){ int[]b=newint[arr.length*2]; System.arraycopy(arr,0,b,0,arr.length); arr=b; publicvoidshow(){ for(inti=0;i<len;i++){ System.out.print(arr[i]+""); System.out.println(); //進(jìn)棧 publicvoidpush(inta){ if(len>=arr.length) resize(); arr[len]=a; len++; //出棧 publicintpop(){ if(len==0){ System.out.println(); System.out.println("stackisempty!"); return-1; inta=arr[len-1]; arr[len-1]=0; len--; returna;鏈表classNode{ Objectdata; Nodenext; publicNode(Objectdata){ setData(data); publicvoidsetData(Objectdata){ this.data=data; publicObjectgetData(){ returndata;classLink{ Nodehead; intsize=0; publicvoidadd(Objectdata){ Noden=newNode(data); if(head==null){ head=n; }else{ Nodecurrent=head; while(true){ if(current.next==null){ break; current=current.next; current.next=n; size++; publicvoidshow(){ Nodecurrent=head; if(current!=null){ while(true){ System.out.println(current); if(current==null){ break; current=current.next; }else{ System.out.println("linkisempty"); publicObjectget(intindex){ publicintsize(){ returnsize;單鏈表classNode//節(jié)點(diǎn)類，單鏈表上的節(jié)點(diǎn) Stringdata;//數(shù)據(jù)域，存放String類的數(shù)據(jù) Nodenext;//指向下一個節(jié)點(diǎn) Node(Stringdata){ this.data=data;//構(gòu)造函數(shù) Stringget(){ returndata;//返回數(shù)據(jù)classMyLinkList//鏈表類 Nodefirst;//頭節(jié)點(diǎn) intsize;//鏈表長度 MyLinkList(Stringarg[]){ //Nodefirst=newNode("head");//生成頭節(jié)點(diǎn) first=newNode("head");//J.F.這里不需要定義局部變量first //如果定義了局部變量，那成員變量first就一直沒有用上 //所以，它一直為空 size=0; Nodep=first; for(inti=0;i<arg.length;i++)//將arg數(shù)組中的元素分別放入鏈表中 Nodeq=newNode(arg[i]); q.next=p.next;//每一個節(jié)點(diǎn)存放一個arg數(shù)組中的元素 p.next=q; p=p.next; size++; MyLinkList()//無參數(shù)構(gòu)造函數(shù) //Nodefirst=newNode("head"); first=newNode("head");//J.F.這里犯了和上一個構(gòu)造方法同樣的錯誤 size=0; intsize()//返回鏈表長度 returnsize; voidinsert(Nodea,intindex)//將節(jié)點(diǎn)a插入鏈表中的第index個位置 Nodetemp=first; for(inti=0;i<index;i++){ temp=temp.next;//找到插入節(jié)點(diǎn)的前一節(jié)點(diǎn) a.next=temp.next;//插入節(jié)點(diǎn) temp.next=a; size++; Nodedel(intindex)//刪除第index個節(jié)點(diǎn)，并返回該值 Nodetemp=first; for(inti=0;i<index;i++){ temp=temp.next;//找到被刪除節(jié)點(diǎn)的前一節(jié)點(diǎn) Nodenode=temp.next; temp.next=node.next; size--;//刪除該節(jié)點(diǎn)，鏈表長度減一 returnnode; voidprint()//在屏幕上輸出該鏈表（這段程序總是出錯，不知道錯在哪里） Nodetemp=first; for(inti=1;i<size;i++)//將各個節(jié)點(diǎn)分別在屏幕上輸出 temp=temp.next; System.out.print(temp.get()+"->"); voidreverse()//倒置該鏈表 for(inti=0;i<size;i++){ insert(del(size-1),0);//將最后一個節(jié)點(diǎn)插入到最前 //J.F.最后一個節(jié)點(diǎn)的index應(yīng)該是size-1 //因?yàn)榈谝粋€節(jié)點(diǎn)的index是0 Stringget(intindex)//查找第index個節(jié)點(diǎn)，返回其值 if(index>=size){ returnnull; Nodetemp=first; for(inti=0;i<index;i++){ temp=temp.next;//找到被查找節(jié)點(diǎn)的前一節(jié)點(diǎn) returntemp.next.get();classMyStack//堆棧類，用單鏈表實(shí)現(xiàn) MyLinkListtmp; Nodetemp; MyStack(){ //MyLinkListtmp=newMyLinkList(); tmp=newMyLinkList();//J.F.和MyLinkList構(gòu)造方法同樣的錯誤 voidpush(Stringa)//壓棧，即往鏈表首部插入一個節(jié)點(diǎn) Nodetemp=newNode(a); tmp.insert(temp,0); Stringpop()//出棧，將鏈表第一個節(jié)點(diǎn)刪除 Nodea=tmp.del(0); returna.get(); intsize(){ returntmp.size(); booleanempty()//判斷堆棧是否為空 if(tmp.size()==0) returnfalse; else returntrue;publicclassMyLinkListTest//測試程序部分 publicstaticvoidmain(Stringarg[])//程序入口 if((arg.length==0)||(arg.length>10)) System.out.println("長度超過限制或者缺少參數(shù)"); else{ MyLinkListll=newMyLinkList(arg);//創(chuàng)建一個鏈表 ll.print();//先輸出該鏈表（運(yùn)行到這一步拋出異常） ll.reverse();//倒置該鏈表 ll.print();//再輸出倒置后的鏈表 Stringdata[]=newString[10]; inti; for(i=0;i<ll.size();i++){ data[i]=ll.get(i);//將鏈表中的數(shù)據(jù)放入數(shù)組 //sort(data);//按升序排列data中的數(shù)據(jù)（有沒有現(xiàn)成的排序函數(shù)？） for(i=0;i<ll.size();i++){ System.out.print(data[i]+";");//輸出數(shù)組中元素 System.out.println(); MyStacks=newMyStack();//創(chuàng)建堆棧實(shí)例s for(i=0;i<ll.size();i++){ s.push(data[i]);//將數(shù)組元素壓棧 while(!s.empty()){ System.out.print(s.pop()+";");//再將堆棧里的元素彈出雙端鏈表classLink{ publicintiData=0; publicLinknext=null; publicLink(intiData){ this.iData=iData; publicvoiddisplay(){ System.out.print(iData+"");classFirstLastList{ privateLinkfirst=null; privateLinklast=null; publicFirstLastList(){ first=null; last=null; publicvoidinsertFirst(intkey){ LinknewLink=newLink(key); if(this.isEmpty()) last=newLink; newLink.next=first; first=newLink; publicvoidinsertLast(intkey){ LinknewLink=newLink(key); if(this.isEmpty()) first=newLink; else last.next=newLink; last=newLink; publicLinkdeleteFirst(){ Linktemp=first; if(first.next==null) last=null; first=first.next; returntemp; publicbooleanisEmpty(){ return(first==null); publicvoiddisplayList(){ System.out.print("List(first-->last):"); Linkcurrent=first; while(current!=null){ current.display(); current=current.next; System.out.println("");classFirstLastListApp{ publicstaticvoidmain(String[]args){ //TODOAuto-generatedmethodstub FirstLastListtheList=newFirstLastList(); theList.insertFirst(22);//insertatfront theList.insertFirst(44); theList.insertFirst(66); theList.insertLast(11);//insertatrear theList.insertLast(33); theList.insertLast(55); theList.displayList();//displaythelist theList.deleteFirst();//deletefirsttwoitems theList.deleteFirst(); theList.displayList();//displayagain有序鏈表packagearithmetic;classLink{ publicintiData=0; publicLinknext=null; publicLink(intiData){ this.iData=iData; publicvoiddisplay(){ System.out.print(iData+"");classSortedList{ privateLinkfirst=null; publicSortedList(){ first=null; publicvoidinsert(intkey){ LinknewLink=newLink(key); Linkprevious=null; Linkcurrent=first; //while的第一個條件是沒有到達(dá)鏈表的尾端,第二個是按順序找到一個合適的位置 while(current!=null&&key>current.iData){ previous=current; current=current.next; //如果是空表或者要插入的元素最小,則在表頭插入key if(current==first) first=newLink; else previous.next=newLink; newLink.next=current; *刪除表頭的節(jié)點(diǎn) *@return要刪除的節(jié)點(diǎn) publicLinkremove(){ Linktemp=first; first=first.next; returntemp; publicbooleanisEmpty(){ return(first==null); publicvoiddisplayList(){ System.out.print("List(first-->last):"); Linkcurrent=first;//startatbeginningoflist while(current!=null)//untilendoflist, current.display();//printdata current=current.next;//movetonextlink System.out.println("");classSortedListApp{ publicstaticvoidmain(String[]args){//createnewlist SortedListtheSortedList=newSortedList(); theSortedList.insert(20);//insert2items theSortedList.insert(40); theSortedList.displayList();//displaylist theSortedList.insert(10);//insert3moreitems theSortedList.insert(30); theSortedList.insert(50); theSortedList.displayList();//displaylist theSortedList.remove();//removeanitem theSortedList.displayList();//displaylist雙向鏈表classLink{ //雙向鏈表,有兩個指針,一個向前,一個向后 publicintiData=0; publicLinkprevious=null; publicLinknext=null; publicLink(intiData){ this.iData=iData; publicvoiddisplay(){ System.out.print(iData+"");classDoublyLinked{ //分別指向鏈表的表頭和表尾 privateLinkfirst=null; privateLinklast=null; publicbooleanisEmpty(){ returnfirst==null; *在表頭插入數(shù)據(jù) *@param要插入的節(jié)點(diǎn)的數(shù)據(jù) publicvoidinsertFirst(intkey){ LinknewLink=newLink(key); //如果開始鏈表為空,則插入第一個數(shù)據(jù)后,last也指向第一個數(shù)據(jù) if(this.isEmpty()) last=newLink; else{//表不為空的情況 first.previous=newLink; newLink.next=first; //無論怎樣,插入后都的讓first重新指向第一個節(jié)點(diǎn) first=newLink; publicvoidinsertLast(intkey){//在尾端插入數(shù)據(jù),同上 LinknewLink=newLink(key); if(this.isEmpty()) first=newLink; else{ last.next=newLink; newLink.previous=last; last=newLink; *在指定的節(jié)點(diǎn)后插入數(shù)據(jù) *@paramkey *指定的節(jié)點(diǎn)的值 *@paramiData *要插入的數(shù)據(jù) *@return是否插入成功 publicbooleaninsertAfter(intkey,intiData){ LinknewLink=newLink(key); Linkcurrent=first; //從first開始遍歷,看能否找到以key為關(guān)鍵字的節(jié)點(diǎn) while(current.iData!=key){ current=current.next; //若能找到就跳出循環(huán),否則返回false,插入失敗 if(current==null) returnfalse; //如果插入點(diǎn)在last的位置 if(current==last){ last=newLink; }else{//非last位置,交換各個next和previous的指針 newLink.next=current.next; current.next.previous=newLink; current.next=newLink; newLink.previous=current; returntrue; *刪除表頭的節(jié)點(diǎn) *@return publicLinkdeleteFirst(){ Linktemp=first; //如果表中只有一個元素,刪除后則為空表,所以last=null if(first.next==null) last=null; else //否則,讓第二個元素的previous=null first.next.previous=null; //刪除頭指針,則first指向原來的second first=first.next; returntemp; publicLinkdeleteLast(){//同上 Linktemp=last; if(last.previous==null) first=null; else last.previous.next=null; last=last.previous; returntemp; publicLinkdeleteKey(intkey){ Linkcurrent=first; //遍歷整個鏈表查找對應(yīng)的key,如果查到跳出循環(huán),否則... while(current.iData!=key){ current=current.next; //...否則遍歷到表尾,說明不存在此key,返回null,刪除失敗 if(current==null) returnnull; if(current==first) first=first.next; else current.previous.next=current.next; if(current==last) last=last.previous; else current.next.previous=current.previous; returncurrent; publicvoiddisplayForward(){ Linkcurrent=first; while(current!=null){ current.display(); current=current.next; System.out.println(); publicvoiddisplayBackward(){ Linkcurrent=last; while(current!=null){ current.display(); current=current.previous; System.out.println();classDoublyLinkedApp{ publicstaticvoidmain(String[]args){//makeanewlist DoublyLinkedtheList=newDoublyLinked(); theList.insertFirst(22);//insertatfront theList.insertFirst(44); theList.insertFirst(66); theList.insertLast(11);//insertatrear theList.insertLast(33); theList.insertLast(55); theList.displayForward();//displaylistforward theList.displayBackward();//displaylistbackward theList.deleteFirst();//deletefirstitem theList.deleteLast();//deletelastitem theList.deleteKey(11);//deleteitemwithkey11 theList.displayForward();//displaylistforward theList.insertAfter(22,77);//insert77after22 theList.insertAfter(33,88);//insert88after33 theList.displayForward();//displaylistforward實(shí)現(xiàn)二叉樹前序遍歷迭代器classTreeNode這個類用來聲明樹的結(jié)點(diǎn)，其中有左子樹、右子樹和自身的內(nèi)容。

classMyTree這個類用來聲明一棵樹，傳入根結(jié)點(diǎn)。這里設(shè)計的比較簡單

classTreeEum這個類是樹的迭代器，通過MyTree類的方法獲取，這里主要就是設(shè)計它了。代碼如下：

//TreeNode類，使用了泛型，由于比較簡單，考試.大提示不作解釋

classTreeNode<E>Enode;privateTreeNode<String>left;privateTreeNode<String>right;publicTreeNode(Ee)this(e,null,null);publicTreeNode(Ee,TreeNode<String>left,TreeNode<String>right)this.node=e;this.left=left;this.right=right;publicTreeNode<String>left()returnleft;publicTreeNode<String>right()returnright;//MyTree類，沒什么功能，傳入根結(jié)點(diǎn)構(gòu)造，getEnumerator()方法獲取迭代器。classMyTreeTreeNode<String>root;publicMyTree(TreeNode<String>root)this.root=root;publicTreeEnumgetEnumerator()returnnewTreeEnum(root);//這個類為迭代器，有詳細(xì)解釋，相信各位能看懂。在棧中用了兩次泛型。importjava.util.Stack;publicclassTreeEnumprivateTreeNode<String>root;privateStack<TreeNode<String>>store;/*保存遍歷左子樹但未遍歷右子樹的結(jié)點(diǎn)*/privateTreeNode<String>next;publicTreeEnum(TreeNode<String>root)this.root=root;store=newStack<TreeNode<String>>();next=root;publicTreeNode<String>next()TreeNode<String>current=next;if(next!=null)/*如果當(dāng)前結(jié)點(diǎn)的左子樹不為空,則遍歷左子樹,并標(biāo)記當(dāng)前結(jié)點(diǎn)未遍歷右子樹*/if(next.left()!=null)store.push(next);next=next.left();//如果當(dāng)前結(jié)點(diǎn)的左子樹為空,則遍歷右子樹elseif(next.right()!=null)next=next.right();/*如果當(dāng)前結(jié)點(diǎn)為葉子,則找未遍歷右子樹的結(jié)點(diǎn)并且遍歷它的右子樹*/else{if(!store.empty())/*判斷是否還有結(jié)點(diǎn)的右子樹未遍歷*/TreeNode<String>tmp=store.pop();/*如果有未遍歷右子樹的結(jié)點(diǎn),但它的右子樹為空,且還有結(jié)點(diǎn)的右子樹未遍歷,*//*則一直往上取,直到取到未遍歷右子樹且右子樹不為空的結(jié)點(diǎn),遍歷它的右子樹.*/while((tmp.right()==null)&&!store.empty())tmp=store.pop();next=tmp.right();else/*如果沒有哪個結(jié)點(diǎn)右子樹未遍歷,則表示沒有下一個結(jié)點(diǎn)了,設(shè)置next為null*/next=null;returncurrent;publicbooleanhasMoreElement()returnnext!=null;下面寫個測試類，不作解釋，相信大家看得懂publicclassTreeReader{publicstaticvoidmain(String[]args)TreeNode<String>n1=newTreeNode<String>("n1");TreeNode<String>n2=newTreeNode<String>("n2");TreeNode<String>n3=newTreeNode<String>("n3");TreeNode<String>n4=newTreeNode<String>("n4");TreeNode<String>n5=newTreeNode<String>("n5");TreeNode<String>n6=newTreeNode<String>("n6",null,n1);TreeNode<String>n7=newTreeNode<String>("n7",n2,null);TreeNode<String>n8=newTreeNode<String>("n8",n7,null);TreeNode<String>n9=newTreeNode<String>("n9",null,n5);TreeNode<String>n10=newTreeNode<String>("n10",n4,n9);TreeNode<String>n11=newTreeNode<String>("n11",n6,n8);TreeNode<String>n12=newTreeNode<String>("n12",n3,n10);TreeNode<String>root=newTreeNode<String>("root",n11,n12);MyTreetree=newMyTree(root);TreeEnumeum=tree.getEnumerator();while(eum.hasMoreElement())System.out.print(eum.next().node+"--");System.out.println("end");迭代器packageTreeIterator;publicinterfaceIterator{publicbooleanhasNext();publicObjectnext();這個接口我們有2個方法，hasNext()是否還有下一條數(shù)據(jù)，next返回具體的Object這里也就是樹。我們先不必要忙著做他的實(shí)現(xiàn)類，我們現(xiàn)在要來做的是這個容器（不是JAVA中容器，及arraylist什么的無關(guān)），正所謂樹的容器是什么，是山也！我們想想山應(yīng)該具有什么呢??？首先它要有種植樹的功能，這里可以看作添加樹。我們可以想像山的功能是和樹相互關(guān)聯(lián)的，那么他們之間是什么關(guān)系呢，我們給他們一種聚合的關(guān)系，聚合的關(guān)系大家可以參考UML圖，我在這里給出它的一種程序表現(xiàn)形式。packageTreeIterator;publicclassHall{Tree[]tree;//這里可以看作是聚合關(guān)系privateintindex;//指向Tree[]的標(biāo)簽publicHall(intmaxNumber){tree=newTree[maxNumber];index=0;publicvoidadd(Treetree)this.tree[index]=tree;index++;publicIteratorconnectIterator()returnnewTreeIterator(this);這里我們定義的山可以抽象出Hall類來，Tree[]tree可以看作是山和樹之間的一種聚合關(guān)系。add方法就是添加樹。問題來了，山和樹有了關(guān)系，那么山和迭代器有什么關(guān)系呢。它們之間肯定有一種關(guān)系。我們有了這個容器（山），就要把這個容器來實(shí)現(xiàn)迭代的方法：hasNext()和Next().恩這里我們可以看出，山和迭代器之間也是一種關(guān)聯(lián)關(guān)系。我們就把它看成是一種聚合關(guān)系（TIP：聚合關(guān)系一種特殊的關(guān)聯(lián)關(guān)系）。我們可以通過一個connectIterator方法來鏈接山和迭代器，接下來我們要去做一個具體的迭代類，這個具體的類中間有了hasNext()和Next()的具體實(shí)現(xiàn)方法packageTreeIterator;publicclassTreeIteratorimplementsIterator{privateintlast=0;privateHallhall;publicTreeIterator(Hallhall){this.hall=hall;publicbooleanhasNext(){if(last<hall.tree.length)returntrue;elsereturnfalse;publicTreenext(){Treet=hall.tree[last];last++;returnt;這里Hallhall就可以看作是一種關(guān)聯(lián)關(guān)系，我們要把山和迭代器聯(lián)系起來就通過構(gòu)造函數(shù)來實(shí)現(xiàn)，hasNext和next實(shí)現(xiàn)方法就體現(xiàn)出來了有了山，有了迭代器，可是樹還沒有定義，不過這個樹的方法還很好解決！樹不關(guān)聯(lián)其他的事務(wù)，我們可以簡單的這么寫：packageTreeIterator;publicclassTree{privateStringname;publicTree(Stringname){=name;publicStringgetName(){return;好了似乎我們整個工程完工了，我們現(xiàn)在來模擬一下農(nóng)民老大伯來種樹撒肥的過程；packageTreeIterator;publicclassPren{publicPren(){publicstaticvoidmain(String[]args){Hallhall=newHall(4);hall.add(newTree("蘋果樹"));hall.add(newTree("梨樹"));hall.add(newTree("橘子樹"));hall.add(newTree("鳳梨樹"));for(Iteratori=hall.connectIterator();i.hasNext();){StringType=((Tree)(i.next())).getName();if(Type=="蘋果樹"){System.out.println("灑蘋果樹的農(nóng)藥,");if(Type=="梨樹"){System.out.println("灑梨樹的農(nóng)藥");if(Type=="橘子樹"){System.out.println("灑橘子樹的農(nóng)藥,灑了也沒用,還沒到成熟日,現(xiàn)在沒結(jié)果實(shí)");if(Type=="鳳梨樹"){System.out.println("南風(fēng)天，濕氣大，讓它爛在地里吧");種4個樹，山小而五臟俱全，更像一個土包，再要有樹才行啊，所以4個樹的實(shí)例出現(xiàn)。好了接下來種樹，幾毫秒解決！山了有我們就要把山放到迭代器中間去了。遍歷這個山（容器）。聯(lián)想我們看看arrayList中的迭代器模式是怎么實(shí)現(xiàn)的！ArrayLista=newArrayList();a.add("a1");a.add("a2");a.add("a3");a.add("a4");for(Iteratori=a.iterator();i.hasNext();)System.out.println(i.next().toString());合并搜索算法publicclassMergeSortArray{ privatelong[]theArray; privateintnElems; publicMergeSortArray(intmax){ theArray=newlong[max]; nElems=0; publicvoidinsert(longvalue){ theArray[nElems]=value;//insertit nElems++;//incrementsize publicvoiddisplay(){ for(intj=0;j<nElems;j++) System.out.print(theArray[j]+""); System.out.println(""); publicvoidmergeSort(){ long[]workSpace=newlong[nElems]; recMergeSort(workSpace,0,nElems-1); privatevoidrecMergeSort(long[]workSpace,intlowerBound,intupperBound){ if(lowerBound==upperBound)//ifrangeis1, return;//nousesorting else{//findmidpoint intmid=(lowerBound+upperBound)/2; //sortlowhalf recMergeSort(workSpace,lowerBound,mid); //sorthighhalf recMergeSort(workSpace,mid+1,upperBound); //mergethem merge(workSpace,lowerBound,mid+1,upperBound); privatevoidmerge(long[]workSpace,intlowPtr,inthighPtr,intupperBound){ intj=0;//workspaceindex intlowerBound=lowPtr; intmid=highPtr-1; intn=upperBound-lowerBound+1;//#ofitems while(lowPtr<=mid&&highPtr<=upperBound) if(theArray[lowPtr]<theArray[highPtr]) workSpace[j++]=theArray[lowPtr++]; else workSpace[j++]=theArray[highPtr++]; while(lowPtr<=mid) workSpace[j++]=theArray[lowPtr++]; while(highPtr<=upperBound) workSpace[j++]=theArray[highPtr++]; for(j=0;j<n;j++) theArray[lowerBound+j]=workSpace[j]; publicstaticvoidmain(String[]args){ intmaxSize=100;//arraysize MergeSortArrayarr=newMergeSortArray(maxSize);//createthearray arr.insert(14); arr.insert(21); arr.insert(43); arr.insert(50); arr.insert(62); arr.insert(75); arr.insert(14); arr.insert(2); arr.insert(39); arr.insert(5); arr.insert(608); arr.insert(36); arr.display(); arr.mergeSort(); arr.display();遞歸publicclassRecursion{ *@paramargs publicstaticvoidmain(String[]args){ //TODOAuto-generatedmethodstub Recursionre=newRecursion(); System.out.println(re.RecursionNum(10)); publicintRecursionNum(intnum) if(num>0){ returnnum+RecursionNum(num-1); Else{ return0;歸并排序*歸并排序，要求待排序的數(shù)組必須實(shí)現(xiàn)Comparable接口publicclassMergeSortimplementsSortStrategy{ privateComparable[]bridge; *利用歸并排序算法對數(shù)組obj進(jìn)行排序 publicvoidsort(Comparable[]obj){ if(obj==null){ thrownewNullPointerException("Theparamcannotbenull!"); bridge=newComparable[obj.length];//初始化中間數(shù)組 mergeSort(obj,0,obj.length-1);//歸并排序 bridge=null; *將下標(biāo)從left到right的數(shù)組進(jìn)行歸并排序 *@paramobj *要排序的數(shù)組的句柄 *@paramleft *要排序的數(shù)組的第一個元素下標(biāo) *@paramright *要排序的數(shù)組的最后一個元素的下標(biāo) privatevoidmergeSort(Comparable[]obj,intleft,intright){ if(left<right){ intcenter=(left+right)/2; mergeSort(obj,left,center); mergeSort(obj,center+1,right); merge(obj,left,center,right); *將兩個對象數(shù)組進(jìn)行歸并，并使歸并后為升序。歸并前兩個數(shù)組分別有序 *@paramobj *對象數(shù)組的句柄 *@paramleft *左數(shù)組的第一個元素的下標(biāo) *@paramcenter *左數(shù)組的最后一個元素的下標(biāo) *@paramright *右數(shù)組的最后一個元素的下標(biāo) privatevoidmerge(Comparable[]obj,intleft,intcenter,intright){ intmid=center+1; intthird=left; inttmp=left; while(left<=center&&mid<=right){//從兩個數(shù)組中取出小的放入中間數(shù)組 if(obj[left]pareTo(obj[mid])<=0){ bridge[third++]=obj[left++]; }else bridge[third++]=obj[mid++]; //剩余部分依次置入中間數(shù)組 while(mid<=right){ bridge[third++]=obj[mid++]; while(left<=center){ bridge[third++]=obj[left++]; //將中間數(shù)組的內(nèi)容拷貝回原數(shù)組 copy(obj,tmp,right); *將中間數(shù)組bridge中的內(nèi)容拷貝到原數(shù)組中 *@paramobj *原數(shù)組的句柄 *@paramleft *要拷貝的第一個元素的下標(biāo) *@paramright *要拷貝的最后一個元素的下標(biāo) privatevoidcopy(Comparable[]obj,intleft,intright){ while(left<=right){ obj[left]=bridge[left]; left++;希爾排序間隔序列：h=3*h+1，h=(h-1)/3publicclassShellSort{ *@paramargs publicstaticvoidmain(String[]args){ //TODOAuto-generatedmethodstub ShellSortss=newShellSort(); intnum[]={546,87,21,3124,65,2,9,3,213,54,98,23,6,4,7, 8,123,872,61,5,8954}; ss.shellArray(num); for(inti=0;i<num.length;i++){ System.out.println(num[i]); publicvoidshellArray(int[]num){ inti=1; inttem,in; for(;i<num.length/3;){ i=3*i+1; for(;i>=1;){ for(intj=i;j<num.length;j++){ tem=num[j]; in=j; while(in>i-1&&num[in-i]>=tem){ num[in]=num[in-i]; in=in-i; num[in]=tem; i=(i-1)/3;快速排序classQuickSort{ privateint[]data; QuickSort(int[]data){ this.data=data; publicvoidquickSort(){ recQuickSort(data,0,data.length-1); privatevoidrecQuickSort(int[]data,intlow,inthigh){ //設(shè)置兩個滑標(biāo) intlowCursor=low+1; inthighCursor=high; //交換時的臨時變量 inttemp=0; //比較樞值,設(shè)為數(shù)組的第一個值 intmedi=data[low]; while(true){ //從低端開始查找，確定大于數(shù)data[low]所在的位置 while(lowCursor<high&&data[lowCursor]<medi){ lowCursor++; //從高端開始查找，確定小于數(shù)data[low]所在的位置。這里要使用>=判斷確定小于值 while(highCursor>low&&data[highCursor]>=medi){ highCursor--; //兩游標(biāo)位置出現(xiàn)越界，退出循環(huán) if