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

數(shù)據(jù)結(jié)構(gòu)與算法實(shí)習(xí),北京大學(xué)信息科學(xué)技術(shù)學(xué)院 張 銘 /mzhang/ds/shixi/(教育網(wǎng)) /pkujpk/course/sjjg/shixi/(公網(wǎng)) 2008.4.20,課程目的,配合“數(shù)據(jù)結(jié)構(gòu)與算法”主課，提高實(shí)際動(dòng)手能力和程序設(shè)計(jì)的質(zhì)量 基本數(shù)據(jù)結(jié)構(gòu) 線性表(向量、串、棧和隊(duì)列)、二叉樹、樹、圖等 ADT、STL 綜合應(yīng)用程序 排序、檢索、文件、索引等技術(shù) 程序設(shè)計(jì)實(shí)踐和技巧,課程內(nèi)容,C+編程技術(shù)補(bǔ)充 標(biāo)準(zhǔn)模板庫 STL的基本概念 C+流處理 程序設(shè)計(jì)實(shí)踐和技巧 風(fēng)格、設(shè)計(jì)和實(shí)現(xiàn) 界面、排錯(cuò) 測試、性能和可擴(kuò)展性,基本算法 枚舉法、貪心法 遞歸、回溯、搜索與分支限界 分治法、動(dòng)態(tài)規(guī)劃 高級(jí)數(shù)據(jù)結(jié)構(gòu) 線性：多維矩陣、稀疏矩陣、廣義表、存儲(chǔ)管理 樹型：字符樹、 BestBST、AVL樹、伸展樹 問題建模 數(shù)學(xué)建模、軟件模型,成績評(píng)定辦法,平時(shí)：20% 考勤、開卷隨堂測試、課堂表現(xiàn) ACM作業(yè)：20% 北大ACM結(jié)果、源程序、實(shí)習(xí)報(bào)告 綜合上機(jī)題：40% 源程序、實(shí)習(xí)報(bào)告 期末考試 20% 有附加題,作業(yè)要求,實(shí)習(xí)課4道大綜合實(shí)習(xí)，6道ACM “誠實(shí)代碼” 要調(diào)試 要提交上機(jī)報(bào)告,實(shí)習(xí)課程資源,數(shù)據(jù)結(jié)構(gòu)實(shí)習(xí)（計(jì)算機(jī)和智能專業(yè)強(qiáng)化） /mzhang/DS/shixi/index.htm /pkujpk/course/sjjg/shixi/ 算法與程序設(shè)計(jì)自評(píng)自測系統(tǒng) /JudgeOnline 2000多道由淺入深設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)與算法程序設(shè)計(jì)各個(gè)知識(shí)點(diǎn)的競賽試題,理論課資源,數(shù)據(jù)結(jié)構(gòu)與算法（信息學(xué)院） /mzhang/DS/(教育網(wǎng)) /pkujpk/course/sjjg/ (公網(wǎng)) 課程答疑 /mzhang/ds/bbs/ 注冊：1-學(xué)號(hào)xxx,教材,1. 張銘、趙海燕、王騰蛟、宋國杰，數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)教程，高等教育出版社，2009年 6月。國家級(jí)“十一五”規(guī)劃教材 2. 張銘、王騰蛟、趙海燕，數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)指導(dǎo)與習(xí)題解析，高等教育出版社，2008年 6月。 國家級(jí)“十一五”規(guī)劃教材 書號(hào): ISBN 978-70-4-023961 3. 張銘、趙海燕、王騰蛟，數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)指導(dǎo)與習(xí)題解析，高等教育出版社，2005年 9月。 國家級(jí)“十五”配套教材 書號(hào): ISBN 7-04-017829-X 4. 許卓群、楊冬青、唐世渭、張銘，數(shù)據(jù)結(jié)構(gòu)與算法，高等教育出版社，2004年7月。 國家級(jí)“十五”規(guī)劃教材,參考教材,1. Brian W.Kernigham 著，裘宗燕 譯，程序設(shè)計(jì)實(shí)踐，機(jī)械工業(yè)出版社，2003年9月。 2. M. H. Alsuwaiyel, Algorithms Design Techniques and Analysis, 電子工業(yè)出版社影印，2003年1月。 3. Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest, Clifford Stein, Inroduction to Algorithms, MTI Press. 高等教育出版社影印。 4. Sartaj Sahni, Data Structures, Algorithms, and Applications in C+. 機(jī)械工業(yè)出版社影印版。 5. 數(shù)據(jù)結(jié)構(gòu)(用面向?qū)ο蠓椒ㄅcC+語言描述)第2版,殷人昆主編, 清華大學(xué)出版社,2007年6月. 清華大學(xué)信息學(xué)院計(jì)算機(jī)系、軟件學(xué)院教材 清華考研第一參考書。 /learn/courseinfo.jsp?course_id=50125,程序設(shè)計(jì)實(shí)踐和技巧,風(fēng)格、設(shè)計(jì)和實(shí)現(xiàn) 程序的境界 界面、排錯(cuò) 測試、性能和可擴(kuò)展性,風(fēng)格、設(shè)計(jì)和實(shí)現(xiàn),風(fēng)格 文件結(jié)構(gòu)、版式、命名、注釋 程序員的素質(zhì) 程序的境界,設(shè)計(jì)和實(shí)現(xiàn),問題求解 數(shù)學(xué)建模、問題建模 數(shù)據(jù)結(jié)構(gòu)抽象 算法抽象 效率分析 選擇能在合理時(shí)間內(nèi)解決預(yù)期規(guī)模問題的簡單算法和數(shù)據(jù)結(jié)構(gòu) 在一些互相沖突的需求和約束條件之間尋找平衡 反復(fù)試驗(yàn)，推倒重來，直至,界面(interface)與排錯(cuò),用戶界面、程序接口 字符界面：菜單型，命令行型 簡單、清晰、規(guī)范、統(tǒng)一 魯棒性 排錯(cuò) 注意程序風(fēng)格（避免全局變量、不用goto） 排錯(cuò)的時(shí)間至少跟寫程序一樣長 不要去懷疑編譯器和庫函數(shù) 讀程序，而不是馬上去改程序 不要過于依賴debug工具,測試、性能和可擴(kuò)展性,測試(Testing)：用系統(tǒng)的方法來發(fā)現(xiàn)程序中可能存在的隱藏的bug 黑盒測試 白盒測試 性能優(yōu)化 編譯、代碼、算法優(yōu)化 可擴(kuò)展性 軟件復(fù)用 緊盯標(biāo)準(zhǔn) 平臺(tái)無關(guān),在總體設(shè)計(jì)上要注意代碼風(fēng)格、可復(fù)用性和可擴(kuò)展性 在關(guān)鍵段要犧牲上面的內(nèi)容來追求性能 性能和可擴(kuò)展性是相互矛盾的,STL中的容器,順序容器 Sequence Containers 關(guān)聯(lián)容器 Associative Containers,容器 Containers,vector,deque,list,set, multiset map, multimap,STL中的容器,容器適配器,stack,queue,priority_queue,基本算法,問題的狀態(tài)空間 窮舉法 回溯、搜索 貪心法 遞歸分治 動(dòng)態(tài)規(guī)劃,八皇后問題,在88格的國際象棋棋盤上擺放8個(gè)皇后，使其不能互相攻擊 任意兩個(gè)皇后都不處于同一行、同一列或同一斜線上 問有多少種擺法？,八皇后問題的一個(gè)解,窮舉法（枚舉法）,4個(gè)皇后各占一行，窮舉每一行上可能占有的列 共有44 256種情況 枚舉時(shí)，可以排除直觀不符合條件的情況，減小候選集 有4! 24種情況 最后輸出合理的解,窮舉法的代價(jià),窮舉問題域的所有解，找到所有最佳解 減少窮舉次數(shù) 窮舉的變量 注意窮舉的順序 減少判斷每種情況的時(shí)間 時(shí)間代價(jià)最高 問題規(guī)模n，搜索空間，總搜索時(shí)間是： T= | t，O(n!) = O(nn)，O(2n) 指數(shù)級(jí)時(shí)間代價(jià),狀態(tài)空間,四皇后的解空間樹,解空間樹,根（root）：問題的起點(diǎn) 問題狀態(tài)（problem states）：樹中結(jié)點(diǎn) 狀態(tài)空間（state space）：由根結(jié)點(diǎn)到其它結(jié)點(diǎn)的所有路徑 解狀態(tài)（solution states）S：由根到S的路徑確定了解空間中的一個(gè)元組 答案狀態(tài)（answer states）S：由根到S的路徑確定了這問題的一個(gè)解（即，它滿足隱式約束條件）,回溯法圖示,“可行則進(jìn)，不行則換、換不成則退”。 簡化為4皇后問題。搜索過程如下：,四后問題求解,回溯算法,可行則進(jìn)，不行則換 換不成則退,八皇后問題的表示,棋盤行列、皇后依次編上0, 1,，7號(hào) A0n-10n-1 表示nn棋盤上的格 行號(hào)從上至下、列號(hào)從左到右依次編號(hào)為0, 1,，n-1 八后問題的全部解向量為(x0, x1,，x7)。 xi表示皇后i所處的列數(shù) 對(duì)任何0i, j8，及ij，有xixj 狀態(tài)空間縮小為在8! 沒有兩個(gè)皇后在同一斜線上（斜率為1 ） 重點(diǎn)！,斜率+1，i+j=0, 1, , 14,0 1 2 3 4 5 6 7,0 1 2 3 4 5 6 7,斜率-1，i-j=-7, 6, , 7,0 1 2 3 4 5 6 7,0 1 2 3 4 5 6 7,皇后的控制范圍,第i個(gè)皇后時(shí)，前面幾個(gè)皇后在各列、各對(duì)角線上的占用情況 bool An; / 前0i-1行皇后占用列 bool B2*n-1; / 斜率為+1的對(duì)角線 bool C2*n-1; / 斜率為-1， Ci-j+7,試探安排八個(gè)皇后,從第0行開始，逐步安排每行皇后。 對(duì)第i個(gè)皇后，找正確的位置(設(shè)為第j列 Aj、Bi+j、Ci-j+7都沒有被占用 標(biāo)記Aj、Bi+j、Ci-j+7為被占用狀態(tài) 繼續(xù)安排下一個(gè)皇后(第i+1個(gè)) 否則，如果找不到合適位置，應(yīng)該退回(即“回溯”)到第i-1行的皇后，重新安排 前面的安排不太合理,回溯過程,如果8個(gè)皇后都排好了，則打印這種方案 為了找到其它方案，應(yīng)該回溯，重新試探皇后的下一種安排方法 抹掉前面試探留下的標(biāo)記，即恢復(fù)Aj、Bi+j、Ci-j+7為未被占用狀態(tài) 這種回溯過程將逐步返回 使得各行的皇后都能試探到各種可能的擺法,回溯法的框架,問題的解n元組(x0, x1,，xn-1)： void rectry(k) / 初始調(diào)rectry(0); 置Xk為第一個(gè)可能值； while (Xk可能值沒有試完) 設(shè)置Xk所涉及的標(biāo)記; if (X0, X1，Xn-1)是解) 打印一組解; else rectry(k+1); 回溯，抹去Xk涉及的標(biāo)記； 取下一個(gè)可能的Xk值; ,八皇后的遞歸算法,void queen(int i) int j; for (j=0; jn; j+) if (place(i,j) / 能放置嗎 Xi = j; mark(i,j); / 標(biāo)記（i,j）的影響 if (i n-1) queen(i+1); / 接著試下一個(gè) else print(count); / 打印一個(gè)解 erase(i,j); / 回溯，去掉剛才標(biāo)記 ,四皇后時(shí)，函數(shù)執(zhí)行模擬,失敗情況下回溯過程模擬： queen(0) 試探x0=0, mark(0,0) queen(1) / for (j=0; jn;j+) 試探x1=2, mark(1,2) queen(2) / 擺不了，函數(shù)返回 erase(1,2) / 回溯 試探x1=3, mark(1,3) ,皇后函數(shù)執(zhí)行模擬(續(xù)),四皇后成功情況下，回溯，繼續(xù)求解： X = 1, 3, 0, 2為第一個(gè)解，求其他解 erase(3, 2) 試探下一個(gè)j=3, 當(dāng)然不能擺 erase(2, 0), 試探其他，都失/queen(2) erase(1, 3), 試探其他，都失敗/queen(1) erase(0, 1) / queen(0) x0 = 2, mark(0,2) queen(1) x1=0, mark(1, 0) .得到第二個(gè)解X=2, 0, 3, 1,八皇后算法討論,如果只要求出一個(gè)解，這個(gè)程序要作修改 求一個(gè)解的程序比求所有解反而要多一些判斷。,回溯算法,巡回售貨員問題,1,2,3,4,9,5,4,2,7,13,29,23,28,28,28,29,有一個(gè)售貨員，從他所在的城市出發(fā)去訪問n-1個(gè)城市，要求經(jīng)過每個(gè)城市恰好一次，然后返回原地問他的路線怎樣安排才最經(jīng)濟(jì)（即線路最短）？,貪心法,問題的狀態(tài)空間很大時(shí)，窮舉法計(jì)算量可能會(huì)太大 當(dāng)人們面對(duì)一個(gè)問題時(shí)，可能會(huì)采取目前看來最接近解狀態(tài)的選擇方案 貪心法可以看作回溯的特例,貪心法的過程,在搜索解的過程中，從根結(jié)點(diǎn)開始，設(shè)當(dāng)前結(jié)點(diǎn)為A，A的所有子結(jié)點(diǎn)中權(quán)值最大的為B，則選擇B作為下一個(gè)結(jié)點(diǎn) 可以貪心解的問題需要滿足的性質(zhì) 貪心選擇性質(zhì) 最優(yōu)子結(jié)構(gòu)性質(zhì) 時(shí)間代價(jià)多為線性,部分裝入背包問題,一個(gè)旅行者準(zhǔn)備隨身攜帶一個(gè)背包。可以放入背包的物品有n個(gè)，每個(gè)物品的重量和價(jià)值分別為wj，vj，j=1,2,n，旅行者可以選擇物品i的全部，也可以選擇i的xi部分，0xi1。如果背包的重量限制是c，怎么選擇放入背包的物品以使得背包的價(jià)值最大？,背包問題的形式定義,輸入：c0, wi0, vi0, i=1, n 輸出： 目標(biāo)函數(shù) 約束條件,貪心法求解背包問題,按照單位重量的價(jià)值從高到低對(duì)物品排序 盡量裝入 “價(jià)值/重量”比最高的物品 直到不能裝入一個(gè)整物品為止 最后根據(jù)背包重量極限裝入部分物品,最小生成樹,1,2,3,4,5,6,6,5,5,5,1,6,4,3,6,2,對(duì)圖G=(V, E) 的每一條邊 賦以相應(yīng)的實(shí)數(shù)權(quán) ，得到一個(gè)網(wǎng)絡(luò)，記為N=(V, E, W) 設(shè)T=(V, E)是N的一個(gè)生成樹(包括原圖所有頂點(diǎn)的連通樹)，樹T的權(quán)為 N中權(quán)最小的生成樹稱為N的最小生成樹。,貪心法,最小生成樹Prim算法,貪心法,最小生成樹Prim算法,1,2,3,4,5,6,3,1,6,4,4,2,2,5,5,3,貪心法,最小生成樹Kruscal算法,貪心法,最小生成樹Kruskal算法,1,2,3,4,5,6,1,2,3,4,5,貪心法一般原則,貪心法得到的可能是最優(yōu)解 最小生成樹 Huffman樹 部分背包問題 貪心法是否求得最優(yōu)解需要數(shù)學(xué)證明 問題規(guī)模太大，最優(yōu)解代價(jià)太高時(shí)，用貪心法求近似解 地圖著色 巡回售貨員問題,遞歸分治算法,分治策略的實(shí)例歸并排序,2,5,1,3,9,8,7,4,2,5,1,3,9,8,7,4,2,5,1,3,9,8,7,4,2,5,1,3,9,8,7,4,二分搜索、BST查找和插入 STL里面的quick_sort快速排序,治,合,分,動(dòng)態(tài)規(guī)劃法問題,某一類遞歸問題，如果直接用遞歸實(shí)現(xiàn)，可能會(huì)導(dǎo)致極低的效率 往往是(2n) 上一級(jí)問題可以利用那些更小子問題的結(jié)果，例如 Fibonacci問題 組合數(shù)問題 Hanoi問題不是動(dòng)態(tài)規(guī)劃問題,遞歸的效率,C(m,n) 兩個(gè)子問題C(m-1,n) 和 C(m-1,n-1),遞歸,遞歸調(diào)用樹,C(5,3),C(4,2),C(2,2) = 1,C(2,1),C(3,2),C(4,3),C(3,3) =1,C(3,1),C(2,2) = 1,C(2,1),C(3,2),C(1,0) = 1,C(1,1) = 1,C(1,0) = 1,C(1,1) = 1,C(2,1),C(2,0) =1,C(1,1) = 1,C(1,0) = 1,遞歸法,int comb(int m, int n) if (m=n) | (n=0) return 1; /處理邊界，遞歸出口 else return comb(m-1,n)+comb(m-1,n-1); 時(shí)間代價(jià)O(2m-2n),遞推法,int cmn; / 假設(shè)初值為0矩陣 int comb(int m, int n) int i,j; if (m=n) | (n=0) cmn = 1; /遞歸出口 else for (i=1; i=m; i+) / 遞推計(jì)算 for (j=0; j=i,j=n; j+) if (i=j) | (j=0) cij = 1; else ij = ci-1j + ci-1j-1; 時(shí)間代價(jià)O(mn),動(dòng)態(tài)規(guī)劃的基本概念,階段 狀態(tài) 決策,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E,5,3,1,6,3,8,4,5,5,6,8,3,3,4,3,圖中的每個(gè)頂點(diǎn)代表一個(gè)城市，兩個(gè)城市間的連線代表道路，連線上的數(shù)值代表道路的長度。從城市A到達(dá)城市E，怎樣走路程最短，最短路程的長度是多少？,動(dòng)態(tài)規(guī)劃的條件,最優(yōu)化原理 無后效性 最優(yōu)子結(jié)構(gòu),一個(gè)最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。 實(shí)際上就是把原問題轉(zhuǎn)換成規(guī)模更小的子問題時(shí)，原問題最優(yōu)當(dāng)且僅當(dāng)子問題最優(yōu)。,動(dòng)態(tài)規(guī)劃的條件,無后效性 過去的步驟只能通過當(dāng)前狀態(tài)影響未來的發(fā)展，當(dāng)前的狀態(tài)是歷史的總結(jié)。,動(dòng)態(tài)規(guī)劃的條件,1,2,3,4,5,6,7,8,9,最優(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的時(shí)候，到7的最短路與以前所經(jīng)過的結(jié)點(diǎn)無關(guān)，如到7經(jīng)過的點(diǎn)為1，2，5，7或1，3，5，7或1，3，6，7都對(duì)以后的求解無關(guān)。,動(dòng)態(tài)規(guī)劃法的思想,自底向上構(gòu)造 在原問題的小子集中計(jì)算 每一步列出局部最優(yōu)解 用一張表保留這些局部最優(yōu)解 用空間換時(shí)間 避免重復(fù)計(jì)算 子集越來越大 最終在問題的全集上計(jì)算，所得出的就是整體最優(yōu)解,多叉路口交通燈管理問題,五叉路口 右行規(guī)則 道路C、E是箭頭所示的單行道 把可以同時(shí)行駛而不發(fā)生碰撞的路線用一種顏色的交通燈指示 用多少種顏色的交通燈，怎樣分配給這些行駛路線？ 顏色越少則管理效率越高 不考慮過渡燈（例如黃燈）,13種行駛路線,AB,AC,AD BA,BC,BD DA,DB,DC EA,EB,EC ED 不能同時(shí) 如AB、BC；EB、AD 可以同時(shí) 如AB、EC,不能同時(shí)走的路線對(duì),(AB BC) (AB BD) (AB DA) (AB EA) (AC DA) (AC BD) (AC DB) (AC EA) (AC EB) (AD EA) (AD EB) (AD EC) (BC EB) (BC DB) (BD DA) (BD EB) (BD EC) (DA EB) (DA EC) (DB EC),多叉路口交通燈管理問題,13種行駛路線 AB,AC,AD