數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)

數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)北京大學(xué)信息科學(xué)技術(shù)學(xué)院張銘/mzhang/ds/shixi/(教育網(wǎng))./pkujpk/course/sjjg/shixi/(公網(wǎng))2008.4.20數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第1頁!課程目的配合“數(shù)據(jù)結(jié)構(gòu)與算法”主課，提高實際動手能力和程序設(shè)計的質(zhì)量基本數(shù)據(jù)結(jié)構(gòu)線性表(向量、串、棧和隊列)、二叉樹、樹、圖等ADT、STL綜合應(yīng)用程序排序、檢索、文件、索引等技術(shù)程序設(shè)計實踐和技巧數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第2頁!課程內(nèi)容C++編程技術(shù)補充標(biāo)準(zhǔn)模板庫STL的基本概念C++流處理程序設(shè)計實踐和技巧風(fēng)格、設(shè)計和實現(xiàn)界面、排錯測試、性能和可擴展性數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第3頁!成績評定辦法平時：20%

考勤、開卷隨堂測試、課堂表現(xiàn)ACM作業(yè)：20%

北大ACM結(jié)果、源程序、實習(xí)報告綜合上機題：40%

源程序、實習(xí)報告期末考試20%

有附加題數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第4頁!實習(xí)課程資源數(shù)據(jù)結(jié)構(gòu)實習(xí)（計算機和智能專業(yè)強化）./mzhang/DS/shixi//pkujpk/course/sjjg/shixi/算法與程序設(shè)計自評自測系統(tǒng)/JudgeOnline2000多道由淺入深設(shè)計數(shù)據(jù)結(jié)構(gòu)與算法程序設(shè)計各個知識點的競賽試題數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第5頁!教材1.張銘、趙海燕、王騰蛟、宋國杰，《數(shù)據(jù)結(jié)構(gòu)與算法實驗教程》，高等教育出版社，2009年6月。——國家級“十一五”規(guī)劃教材2.張銘、王騰蛟、趙海燕，《數(shù)據(jù)結(jié)構(gòu)與算法－－學(xué)習(xí)指導(dǎo)與習(xí)題解析》，高等教育出版社，2008年6月?！獓壹墶笆晃濉币?guī)劃教材書號:ISBN978-70-4-0239613.張銘、趙海燕、王騰蛟，《數(shù)據(jù)結(jié)構(gòu)與算法－－學(xué)習(xí)指導(dǎo)與習(xí)題解析》，高等教育出版社，2005年9月?！獓壹墶笆濉迸涮捉滩臅?ISBN7-04-017829-X4.許卓群、楊冬青、唐世渭、張銘，《數(shù)據(jù)結(jié)構(gòu)與算法》，高等教育出版社，2004年7月。——國家級“十五”規(guī)劃教材數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第6頁!程序設(shè)計實踐和技巧風(fēng)格、設(shè)計和實現(xiàn)程序的境界界面、排錯測試、性能和可擴展性數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第7頁!設(shè)計和實現(xiàn)問題求解數(shù)學(xué)建模、問題建模數(shù)據(jù)結(jié)構(gòu)抽象算法抽象效率分析選擇能在合理時間內(nèi)解決預(yù)期規(guī)模問題的簡單算法和數(shù)據(jù)結(jié)構(gòu)在一些互相沖突的需求和約束條件之間尋找平衡反復(fù)試驗，推倒重來，直至……數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第8頁!測試、性能和可擴展性測試(Testing)：用系統(tǒng)的方法來發(fā)現(xiàn)程序中可能存在的隱藏的bug黑盒測試白盒測試性能優(yōu)化編譯、代碼、算法優(yōu)化可擴展性軟件復(fù)用緊盯標(biāo)準(zhǔn)平臺無關(guān)數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第9頁!STL中的容器順序容器SequenceContainers關(guān)聯(lián)容器AssociativeContainers容器Containersvectordequelistset,multisetmap,multimap數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第10頁!基本算法問題的狀態(tài)空間窮舉法回溯、搜索貪心法遞歸分治動態(tài)規(guī)劃數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第11頁!八皇后問題的一個解

QQQQQQQQ數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第12頁!窮舉法的代價窮舉問題域的所有解，找到所有最佳解減少窮舉次數(shù)窮舉的變量注意窮舉的順序減少判斷每種情況的時間時間代價最高問題規(guī)模n，搜索空間Σ，總搜索時間是：T=|Σ|t，O(n!)=O(nn)，O(2n)指數(shù)級時間代價數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第13頁!四皇后的解空間樹數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第14頁!回溯法圖示“可行則進(jìn)，不行則換、換不成則退”。簡化為4皇后問題。搜索過程如下：

01●●●●01

2

●●●●01

2

3數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第15頁!八皇后問題的表示棋盤行列、皇后依次編上0,1,…，7號A[0..n-1][0..n-1]表示n×n棋盤上的格行號從上至下、列號從左到右依次編號為0,1,…，n-1八后問題的全部解向量為(x0,x1,…，x7)。xi表示皇后i所處的列數(shù)對任何0≤i,j<8，及i≠j，有xi≠xj狀態(tài)空間縮小為在8!沒有兩個皇后在同一斜線上（斜率為±1）重點！數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第16頁!斜率-1，i-j={-7,6,…,7}0123456701234567數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第17頁!試探安排八個皇后從第0行開始，逐步安排每行皇后。對第i個皇后，找正確的位置(設(shè)為第j列A[j]、B[i+j]、C[i-j+7]都沒有被占用標(biāo)記A[j]、B[i+j]、C[i-j+7]為被占用狀態(tài)繼續(xù)安排下一個皇后(第i+1個)否則，如果找不到合適位置，應(yīng)該退回(即“回溯”)到第i-1行的皇后，重新安排前面的安排不太合理數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第18頁!回溯法的框架問題的解n元組(x0,x1,…，xn-1)：

voidrectry(k){//初始調(diào)rectry(0);

置X[k]為個可能值；

while(X[k]可能值沒有試完){

設(shè)置X[k]所涉及的標(biāo)記;

if((X[0],X[1]，…，X[n-1])是解)

打印一組解;

elserectry(k+1);

回溯，抹去X[k]涉及的標(biāo)記；

取下一個可能的X[k]值;

}

}數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第19頁!四皇后時，函數(shù)執(zhí)行模擬失敗情況下回溯過程模擬：queen(0)

試探x[0]=0,mark(0,0)queen(1)//for(j=0;j<n;j++)

試探x[1]=2,mark(1,2)queen(2)//擺不了，函數(shù)返回

erase(1,2)//回溯

試探x[1]=3,mark(1,3)……01●●●●數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第20頁!八皇后算法討論如果只要求出一個解，這個程序要作修改求一個解的程序比求所有解反而要多一些判斷。數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第21頁!貪心法問題的狀態(tài)空間很大時，窮舉法計算量可能會太大當(dāng)人們面對一個問題時，可能會采取目前看來最接近解狀態(tài)的選擇方案貪心法可以看作回溯的特例數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第22頁!部分裝入背包問題

一個旅行者準(zhǔn)備隨身攜帶一個背包?？梢苑湃氡嘲奈锲酚衝個，每個物品的重量和價值分別為wj，vj，j=1,2,…,n，旅行者可以選擇物品i的全部，也可以選擇i的xi部分，0≤xi≤1。如果背包的重量限制是c，怎么選擇放入背包的物品以使得背包的價值最大？數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第23頁!貪心法求解背包問題按照單位重量的價值從高到低對物品排序盡量裝入

“價值/重量”比最高的物品直到不能裝入一個整物品為止最后根據(jù)背包重量極限裝入部分物品數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第24頁!貪心法最小生成樹Prim算法數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第25頁!貪心法最小生成樹Kruscal算法數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第26頁!貪心法一般原則貪心法得到的可能是最優(yōu)解最小生成樹Huffman樹部分背包問題貪心法是否求得最優(yōu)解需要數(shù)學(xué)證明問題規(guī)模太大，最優(yōu)解代價太高時，用貪心法求近似解地圖著色巡回售貨員問題數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第27頁!動態(tài)規(guī)劃法問題某一類遞歸問題，如果直接用遞歸實現(xiàn)，可能會導(dǎo)致極低的效率往往是Ｏ(2n)上一級問題可以利用那些更小子問題的結(jié)果，例如Fibonacci問題組合數(shù)問題Hanoi問題不是動態(tài)規(guī)劃問題數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第28頁!遞歸調(diào)用樹C(5,3)

C(4,2)

C(2,2)=1C(2,1)C(3,2)

C(4,3)

C(3,3)=1

C(3,1)

C(2,2)=1C(2,1)

C(3,2)

C(1,0)=1C(1,1)=1

C(1,0)=1C(1,1)=1C(2,1)

C(2,0)=1

C(1,1)=1C(1,0)=1數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第29頁!遞推法intc[m][n];//假設(shè)初值為0矩陣intb(intm,intn){ inti,j; if((m==n)||(n==0))c[m][n]=1;//遞歸出口

elsefor(i=1;i<=m;i++)//遞推計算

for(j=0;j<=i,j<=n;j++) if((i==j)||(j==0)) c[i][j]=1; else[i][j]=c[i-1][j]+c[i-1][j-1];}時間代價O(mn)數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第30頁!動態(tài)規(guī)劃的條件最優(yōu)化原理無后效性最優(yōu)子結(jié)構(gòu)

一個最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。實際上就是把原問題轉(zhuǎn)換成規(guī)模更小的子問題時，原問題最優(yōu)當(dāng)且僅當(dāng)子問題最優(yōu)。數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第31頁!動態(tài)規(guī)劃的條件123456789最優(yōu)化原理最優(yōu)子結(jié)構(gòu)無后效性從1->3->5->8->9是1到9的最短路，則1->3->5->8是1到8的最短路，1->3->5是1到5的最短路……

當(dāng)前狀態(tài)為7的時候，到7的最短路與以前所經(jīng)過的結(jié)點無關(guān)，如到7經(jīng)過的點為1，2，5，7或1，3，5，7或1，3，6，7都對以后的求解無關(guān)。數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第32頁!多叉路口交通燈管理問題五叉路口右行規(guī)則道路C、E是箭頭所示的單行道把可以同時行駛而不發(fā)生碰撞的路線用一種顏色的交通燈指示用多少種顏色的交通燈，怎樣分配給這些行駛路線？顏色越少則管理效率越高不考慮過渡燈（例如黃燈）數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第33頁!不能同時走的路線對(ABBC)(ABBD)(ABDA)(ABEA)(ACDA)(ACBD)(ACDB)(ACEA)(ACEB)(ADEA)(ADEB)(ADEC)(BCEB)(BCDB)(BDDA)(BDEB)(BDEC)(DAEB)(DAEC)(DBEC)數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第34頁!有連線則不能同時通行數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第35頁!地圖著色問題最少著色分組的最優(yōu)解問題是NP復(fù)雜性問題窮舉法或回溯法來解決地圖著色問題。對于小型地圖可以使用對于大型模式，由于時間的指數(shù)上升，不可接受指數(shù)級或NP問題往往通過一些逼近方法來求近似最優(yōu)解數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第36頁!貪心法近似解按1，2，3，4，5順序著色貪心哪！15241，23，453數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第37頁!算法總結(jié)數(shù)學(xué)模型、狀態(tài)空間問題抽象數(shù)據(jù)抽象算法抽象窮舉法——萬能，低效避免窮舉測試數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第38頁!總結(jié)問題求解理論、抽象和設(shè)計的三個層次根據(jù)實際問題取舍數(shù)據(jù)結(jié)構(gòu)和算法在時間和空間復(fù)雜度之間進(jìn)行平衡軟件開發(fā)、工程的規(guī)范性實踐、自主學(xué)習(xí)、研究創(chuàng)新能力數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第39頁!基本算法枚舉法、貪心法遞歸、回溯、搜索與分支限界分治法、動態(tài)規(guī)劃高級數(shù)據(jù)結(jié)構(gòu)線性：多維矩陣、稀疏矩陣、廣義表、存儲管理樹型：字符樹、BestBST、AVL樹、伸展樹問題建模數(shù)學(xué)建模、軟件模型數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第40頁!作業(yè)要求實習(xí)課4道大綜合實習(xí)，6道ACM“誠實代碼”要調(diào)試要提交上機報告數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第41頁!理論課資源數(shù)據(jù)結(jié)構(gòu)與算法（信息學(xué)院）/mzhang/DS/(教育網(wǎng))./pkujpk/course/sjjg/(公網(wǎng))課程答疑/mzhang/ds/bbs/注冊：1-學(xué)號xxx數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第42頁!參考教材1.BrianW.Kernigham著，裘宗燕譯，《程序設(shè)計實踐》，機械工業(yè)出版社，2003年9月。2.M.H.Alsuwaiyel,AlgorithmsDesignTechniquesandAnalysis,電子工業(yè)出版社影印，2003年1月。3.ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,CliffordStein,InroductiontoAlgorithms,MTIPress.高等教育出版社影印。4.SartajSahni,DataStructures,Algorithms,andApplicationsinC++.機械工業(yè)出版社影印版。5.數(shù)據(jù)結(jié)構(gòu)(用面向?qū)ο蠓椒ㄅcC++語言描述)第2版,殷人昆主編,清華大學(xué)出版社,2007年6月.清華大學(xué)信息學(xué)院計算機系、軟件學(xué)院教材清華考研參考書。/learn/courseinfo.jsp?course_id=50125數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第43頁!風(fēng)格、設(shè)計和實現(xiàn)風(fēng)格文件結(jié)構(gòu)、版式、命名、注釋……程序員的素質(zhì)程序的境界數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第44頁!界面(interface)與排錯用戶界面、程序接口字符界面：菜單型，命令行型簡單、清晰、規(guī)范、統(tǒng)一魯棒性排錯注意程序風(fēng)格（避免全局變量、不用goto……）排錯的時間至少跟寫程序一樣長不要去懷疑編譯器和庫函數(shù)讀程序，而不是馬上去改程序不要過于依賴debug工具數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第45頁!在總體設(shè)計上要注意代碼風(fēng)格、可復(fù)用性和可擴展性在關(guān)鍵段要犧牲上面的內(nèi)容來追求性能性能和可擴展性是相互矛盾的數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第46頁!STL中的容器容器適配器stackqueuepriority_queue數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第47頁!八皇后問題在8×8格的國際象棋棋盤上擺放8個皇后，使其不能互相攻擊任意兩個皇后都不處于同一行、同一列或同一斜線上問有多少種擺法？數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第48頁!窮舉法（枚舉法）4個皇后各占一行，窮舉每一行上可能占有的列共有44＝256種情況枚舉時，可以排除直觀不符合條件的情況，減小候選集有4!＝24種情況最后輸出合理的解數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第49頁!狀態(tài)空間

●

●

●

●

●●

●●

●●

●●

●●

●●●

●●●

●

●●●

●●●

●●●●●●●●

●●●●

●數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第50頁!解空間樹根（root）：問題的起點問題狀態(tài)（problemstates）：樹中結(jié)點狀態(tài)空間（statespace）：由根結(jié)點到其它結(jié)點的所有路徑解狀態(tài)（solutionstates）S：由根到S的路徑確定了解空間中的一個元組答案狀態(tài)（answerstates）S：由根到S的路徑確定了這問題的一個解（即，它滿足隱式約束條件）數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第51頁!四后問題求解回溯算法可行則進(jìn)，不行則換換不成則退數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第52頁!斜率+1，i+j={0,1,…,14}0123456701234567數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第53頁!皇后的控制范圍第i個皇后時，前面幾個皇后在各列、各對角線上的占用情況boolA[n];//前0..i-1行皇后占用列boolB[2*n-1];//斜率為+1的對角線boolC[2*n-1];//斜率為-1，C[i-j+7]數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第54頁!回溯過程如果8個皇后都排好了，則打印這種方案為了找到其它方案，應(yīng)該回溯，重新試探皇后的下一種安排方法抹掉前面試探留下的標(biāo)記，即恢復(fù)A[j]、B[i+j]、C[i-j+7]為未被占用狀態(tài)這種回溯過程將逐步返回使得各行的皇后都能試探到各種可能的擺法數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第55頁!八皇后的遞歸算法

voidqueen(inti){

intj;

for(j=0;j<n;j++){

if(place(i,j)){//能放置嗎

X[i]=j;

mark(i,j);//標(biāo)記（i,j）的影響

if(i<n-1)

queen(i+1);//接著試下一個

elseprint(count);//打印一個解

erase(i,j);//回溯，去掉剛才標(biāo)記

}

} }數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第56頁!皇后函數(shù)執(zhí)行模擬(續(xù))四皇后成功情況下，回溯，繼續(xù)求解：X=[1,3,0,2]為個解，求其他解……erase(3,2)

試探下一個j=3,當(dāng)然不能擺erase(2,0),試探其他，都失//queen(2)

erase(1,3),試探其他，都失敗//queen(1)erase(0,1)//queen(0)x[0]=2,mark(0,2)queen(1)x[1]=0,mark(1,0)…….得到第二個解X=[2,0,3,1]01

2

3數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第57頁!回溯算法巡回售貨員問題123495427131234342423434232292328282829有一個售貨員，從他所在的城市出發(fā)去訪問n-1個城市，要求經(jīng)過每個城市恰好一次，然后返回原地問他的路線怎樣安排才最經(jīng)濟（即線路最短）？數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第58頁!貪心法的過程在搜索解的過程中，從根結(jié)點開始，設(shè)當(dāng)前結(jié)點為A，A的所有子結(jié)點中權(quán)值最大的為B，則選擇B作為下一個結(jié)點可以貪心解的問題需要滿足的性質(zhì)貪心選擇性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)時間代價多為線性數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第59頁!背包問題的形式定義輸入：c>0,wi>0,vi>0,i=1,…,n輸出：<x1,x2,…,xn>目標(biāo)函數(shù)約束條件

數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第60頁!最小生成樹1234566555164362對圖G=(V,E)的每一條邊賦以相應(yīng)的實數(shù)權(quán)，得到一個網(wǎng)絡(luò)，記為N=(V,E,W)設(shè)T=(V,E’)是N的一個生成樹(包括原圖所有頂點的連通樹)，樹T的權(quán)為N中權(quán)最小的生成樹稱為N的最小生成樹。數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第61頁!貪心法最小生成樹Prim算法12345665551643621234563164422553數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第62頁!貪心法最小生成樹Kruskal算法123456655516436212345612345數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第63頁!遞歸分治算法分治策略的實例——歸并排序25139874251398742513987425139874二分搜索、BST查找和插入STL里面的quick_sort——快速排序治合分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第64頁!遞歸的效率C(m,n)兩個子問題C(m-1,n)和C(m-1,n-1)遞歸數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第65頁!遞歸法intb(intm,intn){ if((m==n)||(n==0))return1;//處理邊界，遞歸出口

elsereturnb(m-1,n)+b(m-1,n-1);}時間代價O(2m-2n)數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)共76頁，您現(xiàn)在瀏覽的是第66頁!動態(tài)規(guī)劃的基本概念階段狀態(tài)決策AB1B2C1C2C3C4D1