第10章 綜合應(yīng)用設(shè)計(jì)(Java版)

第10章綜合應(yīng)用設(shè)計(jì)10.1數(shù)組和集合10.2實(shí)現(xiàn)迭代器10.3算法設(shè)計(jì)策略10.4課程設(shè)計(jì)的目的、要求和選題數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》目的目的：綜合運(yùn)用數(shù)據(jù)結(jié)構(gòu)課程所討論的基

礎(chǔ)知識(shí)和基本理論，解決具有一定

規(guī)模的、中等難度的實(shí)際應(yīng)用問

題，培養(yǎng)綜合應(yīng)用設(shè)計(jì)能力。內(nèi)容：Java集合框架；多種算法設(shè)計(jì)策 略。數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》10.1數(shù)組和集合10.1.1Arrays數(shù)組類（1）比較兩個(gè)數(shù)組是否相等publicstaticbooleanequals(Object[]a,Object[]b)（2）填充publicstaticvoidfill(Object[]a,Objectobj)publicstaticvoidfill(long[]a,intbegin,intend,longvalue)數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》10.1.1Arrays數(shù)組類（3）排序publicstaticvoidsort(Object[]a)publicstatic<T>voidsort(T[]a,Comparator<?superT>c)（4）二分法查找publicstaticintbinarySearch(Object[]a,intbegin,intend,Objectkey)publicstatic<T>intbinarySearch(T[]a,Tkey,Comparator<?superT>c)數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》java.util.Comparator比較器接口publicinterfaceComparator<T>{intcompare(Tcobj1,Tcobj2); //指定比較兩個(gè)對(duì)象大小的規(guī)則}數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》10.1.2Java集合框架集合框架結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》表10-1集合框架中的主要接口和類接口實(shí)現(xiàn)接口的類一維數(shù)組循環(huán)雙鏈表平衡二叉樹散列表Set集合TreeSetHashSetList列表ArrayListLinkedListMap映射TreeMapHashMap數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》2.迭代（1）java.util.Iterator和ListIterator迭代器接口publicinterfaceIterator<T>//迭代器接口{booleanhasNext();//判斷是否有后繼元素Tnext();//返回后繼元素

voidremove();//刪除迭代器對(duì)象表示的集合當(dāng)前元素}數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》java.util.ListIterator列表迭代器接口publicinterfaceListIterator<T>extendsIterator<T>{booleanhasPrevious();//判斷是否有前驅(qū)元素

Tprevious();//返回前驅(qū)元素

intnextIndex();//返回后繼元素序號(hào)

intpreviousIndex();//返回前驅(qū)元素序號(hào)

voidset(Tx);//將集合當(dāng)前元素替換為x

voidadd(Tx);//增加元素x}數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》（2）java.lang.Iterable可迭代接口publicinterfaceIterable<T>{Iterator<T>iterator();}數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》3.Collection接口publicinterfaceCollection<T>extendsIterable<T>{Iterator<T>iterator();//獲得迭代器

booleanisEmpty();//判斷集合是否為空

intsize();//返回集合的元素個(gè)數(shù)

booleancontains(Objectobj);//判斷是否包含指定元素

booleanadd(Telement);//增加指定元素

booleanremove(Objectobj);//移去首次出現(xiàn)指定元素

voidclear(); //移去所有元素//以下方法描述集合運(yùn)算，參數(shù)是另一個(gè)集合

booleanequals(Objectobj);//比較兩個(gè)集合是否相等

booleancontainsAll(Collection<?>c);//判斷集合包含

booleanaddAll(Collection<?extendsT>c);//集合并

booleanremoveAll(Collection<?>c);//集合差

booleanretainAll(Collection<?>c);//僅保留那些也包含在集合c中的元素}數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》4.列表 （1）List接口publicinterfaceList<T>extendsCollection<T>{Tget(inti)//返回第i（i≥0）個(gè)元素Tset(inti,T

x)//用x替換原第i個(gè)元素

ListIterator<T>listIterator()//返回列表迭代器對(duì)象}（2）ArrayList類（3）LinkedList類數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》5.Collections類publicclassCollections{publicstatic<T>Tmax(Collection<?extendsT>coll,Comparator<?superT>c)//最大值

publicstatic<T>Tmin(Collection<?extendsT>coll,Comparator<?superT>c)//最小值

publicstatic<T>intbinarySearch(List<?extendsComparable<?superT>>list,Tkey)

publicstatic<T>voidsort(List<T>list,Comparator<?superT>c)//排序}數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》【例10.1】電話簿。Friend類表示電話簿對(duì)象，實(shí)現(xiàn)可比較、比較器和序列化接口。TelephoneBookTreeSet類實(shí)現(xiàn)電話簿的存儲(chǔ)和管理。TelephoneBookJFrame類實(shí)現(xiàn)電話簿的圖形用戶界面，提供添加、查找和刪除功能。數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》電話簿管理窗口中兩個(gè)分割窗格的布局層次數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》10.2實(shí)現(xiàn)迭代器10.2.1基于迭代器的操作10.2.2提供迭代器對(duì)象數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》10.2.1基于迭代器的操作抽象集合類publicabstractclassAbstractCCollection<T>implementsIterable<T>{publicabstractjava.util.Iterator<T>iterator();

publicStringtoString()

{java.util.Iterator<T>it=this.iterator();

Stringstr="(";while(it.hasNext())//若有后繼元素

{str+=it.next().toString();//添加后繼元素字符串

if(it.hasNext())str+=",";}returnstr+")";}}數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》2.抽象列表類publicabstractclassAbstractLList<T>extendsAbstractCCollection<T>{publicbooleanequals(Objectobj)

{if(obj==this)returntrue;if(!(objinstanceofAbstractLList))returnfalse;java.util.Iterator<T>it1=this.iterator();java.util.Iterator<T>it2=((AbstractLList<T>)obj).iterator();while(it1.hasNext()&&it2.hasNext())if(!(it1.next().equals(it2.next())))

returnfalse;return!it1.hasNext()&&!it2.hasNext();

}}數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》10.2.2提供迭代器對(duì)象順序表類提供迭代器對(duì)象publicclassSeqList<T>extendsAbstractLList<T>implementsLList<T>{

publicjava.util.Iterator<T>iterator(){//返回Java迭代器對(duì)象returnnewSeqIterator();}privateclassSeqIteratorimplementsjava.util.Iterator<T>//私有內(nèi)部類，實(shí)現(xiàn)迭代器接口{……}}數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》2.單鏈表類提供迭代器對(duì)象publicclassSinglyLinkedList<T>extendsAbstractLList<T>implementsLList<T>{publicjava.util.Iterator<T>iterator()

{//返回Java迭代器對(duì)象returnnewSinglyIterator();}privateclassSinglyIteratorimplementsjava.util.Iterator<T>//私有內(nèi)部類，實(shí)現(xiàn)迭代器接口

{……}}數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》本書線性表接口和類的層次關(guān)系數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》10.3算法設(shè)計(jì)策略10.3.1分治法10.3.2動(dòng)態(tài)規(guī)劃法10.3.3貪心法10.3.4回溯法數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》10.3.1分治法分治策略分治法（divideandconquer）采用分而治之、逐個(gè)解決的策略。孫子兵法曰“凡治眾如治寡，分?jǐn)?shù)是也。”分治與遞歸

結(jié)果求解問題（問題規(guī)模）{if（問題規(guī)模足夠?。?/遞歸邊界條件求解小規(guī)模子問題；

else

分解，求解問題（問題規(guī)?？s?。?；//遞歸調(diào)用

return各子問題合并后的解；}分治法的效率分析數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》深度優(yōu)先搜索遍歷二叉樹、樹和圖，以及折半查找、快速排序都是采用分治策略的算法。

void遍歷（問題規(guī)模）{if（問題規(guī)模>1）//繼續(xù)遞歸

{訪問當(dāng)前元素；

while（存在子問題）//分解成若干子問題遍歷（子問題規(guī)模）；//遞歸調(diào)用

}}數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》10.3.2動(dòng)態(tài)規(guī)劃法動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃法（dynamicprogramming）也是把一個(gè)大問題分解為若干較小的子問題，通過求解子問題而得到原問題的解。動(dòng)態(tài)規(guī)劃法采用備忘錄做法。動(dòng)態(tài)規(guī)劃法的基本要素最優(yōu)子結(jié)構(gòu)子問題重疊n數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》【例10.2】動(dòng)態(tài)規(guī)劃法求組合數(shù)。nnm012345111212131331414641515101051數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》10.3.3貪心法63.6元=10元×6+1元×3+0.1元×6//15張63.6=50+10+2+1+0.5+0.1//6張（個(gè)）貪心選擇策略貪心法（greedy）是運(yùn)用局部最優(yōu)選擇以期獲得全局最優(yōu)解的一種策略。數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》【例10.3】貪心法求解背包問題。給定n個(gè)物品和一個(gè)背包，物品i的重量為wi，價(jià)值為pi，背包能容納物品總重量為W；設(shè)xi（0≤xi≤1）表示物品i的幾分之幾，求如何選擇裝入背包的物品（全部或部分），使背包中物品總價(jià)值最大。背包問題的約束條件為≤W，滿足約束條件的n元組是一個(gè)可用解，使最大的可用解是最優(yōu)解。數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》表10-2背包問題的多個(gè)可用解n=3，物品序列為{(80,20),(50,25),(15,45)}，W=100。

方案可用解

背包重量背包價(jià)值1(1,20/50,0)80+20=10020+25*2/5=302(1,5/50,1)80+5=15=10020+25*5/50+45=67.53(50/80,1,0)50+50=10020*50/80+25=37.54(35/80,1,1)35+50+15=10020*35/80+25+45=78.75數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》10.3.3貪心法貪心法的基本要素貪心選擇性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)貪心法與動(dòng)態(tài)規(guī)劃法的區(qū)別數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（Java版）（第3版）》4.最小堆貪心選擇策略最簡單的應(yīng)用是求最小值。publicclassMinHeap<Textendsjava.lang.Comparable<T>>//最小堆類{Comparable[]element;//最小堆元素?cái)?shù)組intlen;//最小堆元素個(gè)數(shù)Comparatorcompa