1、算法與數(shù)據(jù)結(jié)構(gòu) C語(yǔ)言描述張乃孝 主編高等教育出版社張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述2第一章 緒 論 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的必要性 1.1 問題求解 1.2 數(shù)據(jù)結(jié)構(gòu) 1.3 算法 1.4 算法分析 1.5 抽象數(shù)據(jù)類型 計(jì)算機(jī)信息表示A信息表示B張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述3張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述4為一個(gè)實(shí)際問題開發(fā)一個(gè)程序系統(tǒng)通常可以分成以下四個(gè)階段 3。編碼階段2。設(shè)計(jì)階段1。分析階段4。測(cè)試和維護(hù)（與本課程關(guān)系最密切）張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述5 C D B A E 圖1.1 一 個(gè) 交 叉 路 口 的 模 型 對(duì)于一個(gè)多叉路口，設(shè)計(jì)一個(gè)交通信號(hào)燈的管理系統(tǒng)。首先需要分析一

2、下所有車輛的行駛路線的沖突問題。這個(gè)問題可以歸結(jié)為對(duì)車輛的可能行駛方向作某種分組，對(duì)分組的要求是使任一個(gè)組中各個(gè)方向行駛的車輛可以同時(shí)安全行駛而不發(fā)生碰撞。 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述6 C D B A E 圖1.1 一 個(gè) 交 叉 路 口 的 模 型 可通行方向AB AC A DB A BC BD DA DB D CE A EB ECED張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述7有些通行方向顯然不能同時(shí)進(jìn)行，相應(yīng)的結(jié)點(diǎn)間畫一條連線。ABACADBABCBDDAD BDCEAEBECED圖1.2 交叉路口的圖示模型張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述8 把圖1.2中的結(jié)點(diǎn)進(jìn)行分組，使得有邊相連的結(jié)點(diǎn)

3、不在同一個(gè)組里。 地圖著色問題 如果把上圖中的一個(gè)結(jié)點(diǎn)理解為一個(gè)國(guó)家， 結(jié)點(diǎn)之間的連線看作兩國(guó)有共同邊界，上述問題 就變成著名的“著色問題”：即求出最少要幾種顏 色可將圖中所有國(guó)家著色，使得任意兩個(gè)相鄰的 國(guó)家顏色都不相同。 通過上面的分析，我們就獲得了該交通管系統(tǒng)的數(shù)學(xué)模型。下面就可以著手進(jìn)行算法的設(shè)計(jì)。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述91.1.2 程序設(shè)計(jì) 算法設(shè)計(jì)方法2. “貪心法” while 有結(jié)點(diǎn)未著色； 選擇一種新顏色； 在未著色的結(jié)點(diǎn)中,給盡可能多的彼此結(jié) 點(diǎn)之間沒有邊連接的點(diǎn)著色； 方法1. 對(duì)n個(gè)結(jié)點(diǎn)，逐個(gè)測(cè)試其所有組合；張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述10有些通行方向顯然

4、不能同時(shí)進(jìn)行，相應(yīng)的結(jié)點(diǎn)間畫一條連線。ABACADBABCBDDAD BDCEAEBECED圖1.2 交叉路口的圖示模型張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述11 把上面方法應(yīng)用于圖1.2，得到下面的分組： 綠色：AB, AC, AD, BA, DC, ED 藍(lán)色：BC, BD, EA 紅色：DA, DB 白色：EB, EC張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述12 假設(shè)需要著色的圖是G，集合V1包括圖中所有未被著色的結(jié)點(diǎn)，著色開始時(shí)V1是G所有結(jié)點(diǎn)集合。NEW表示已確定可以用新顏色著色的結(jié)點(diǎn)集合。 從V1中找出可用新顏色著色的結(jié)點(diǎn)集的程序框架描述為： NEW= ; for 每個(gè)v V1 do if v與

5、NEW中所有結(jié)點(diǎn)間都沒有邊 從V1中去掉v ; NEW=NEWv ; 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述13 對(duì)集合和圖的操作: 判斷一個(gè)集合是否為空:isSetEmpty(V1); 置一個(gè)集合為空: emptySet(NEW); 從集合中去掉一個(gè)元素:removeFromSet(V1,v); 向集合里增加一個(gè)元素:addToSet(NEW,v); 檢查結(jié)點(diǎn)v與結(jié)點(diǎn)集合中各結(jié)點(diǎn)之間在圖G中是 否有邊連接: notAdjacentWithSet(NEW,v,G); 有了圖、集合這樣的結(jié)構(gòu)和基于其上的操作，程序的實(shí)現(xiàn)非常簡(jiǎn)單。 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述14算法： int colorUp( G

6、raph G) int color=0; V1=G.V; while(!isSetEmpty(V1) emptySet(NEW); while(vV1& notAdjacentWithSet(NEW,v,G) addToSet(NEW,v); removeFromSet(V1,v); +color; return(color); 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述151.2 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)數(shù)據(jù)( (Data)Data)：在計(jì)算機(jī)科學(xué)中是所有能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序處理的符號(hào)的總稱。數(shù)據(jù)元素?cái)?shù)據(jù)元素( (Data Element)Data Element)：數(shù)據(jù)的基本單位，在

7、計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（Data Structures): Data Structures): 由若干數(shù)據(jù)元素（點(diǎn)點(diǎn)）按照一定方式構(gòu)成的復(fù)合數(shù)據(jù)以及作用于其上的函數(shù)或運(yùn)算。一種數(shù)據(jù)結(jié)構(gòu)包含下面三個(gè)方面：張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述161. . 邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)：表示數(shù)據(jù)元素之間的邏輯關(guān)系。 B=( K, R )2. 2. 物理結(jié)構(gòu)：物理結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的 映射（或表示），又稱存儲(chǔ)結(jié)構(gòu)，也稱存 儲(chǔ)表示。3 .3 .這個(gè)結(jié)構(gòu)的行為特征。這個(gè)結(jié)構(gòu)的行為特征。 作用于數(shù)據(jù)結(jié)構(gòu)上的運(yùn)算。例如：檢索， 插入，刪除等。本書將要討論的主要數(shù)據(jù)結(jié)構(gòu)：

8、 線性表，字符串，堆棧與隊(duì)列，樹與二叉樹，字典，圖。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述17問題機(jī)外表示處理要求邏輯結(jié)構(gòu)基本運(yùn)算數(shù)學(xué)模型存儲(chǔ)結(jié)構(gòu) 實(shí)現(xiàn)實(shí)現(xiàn)建模求精數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容不同結(jié)構(gòu)的比較及算法分析張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述18 1.3 算法（Algorithm) 解題過程的精確描述，由有限條可完全機(jī)械執(zhí)行的，有確切含義的指令（或命令，語(yǔ)句）構(gòu)成。 算法算法是用計(jì)算裝置能夠理解的語(yǔ)言描述的解題過程，具有如下性質(zhì)： 1. 將它作用于所求解的問題的給定輸入集上， 或作用于問題自身的描述上，將產(chǎn)生唯一 確定的動(dòng)作序列，此序列是有限的； 2. 此序列或終止于給出問題的解，或終止于 指出問題對(duì)此

9、輸入無(wú)解。有窮性; 確定性; 可行性; 輸入; 輸出張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述19 在實(shí)際應(yīng)用中，算法的表現(xiàn)形式千變?nèi)f化，但是算法的情況也和數(shù)據(jù)結(jié)構(gòu)類似，許多算法的設(shè)計(jì)思想具有相似之處，我們可以對(duì)它們分類進(jìn)行學(xué)習(xí)和研究。 常用的算法大致有如下一些：分治法：如二分法檢索分支限界法動(dòng)態(tài)規(guī)劃法貪心法回溯法張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述20 1.4算法分析 評(píng)價(jià)一個(gè)程序優(yōu)劣的重要依據(jù)是看這個(gè)程序的執(zhí)行需要占用多少機(jī)器資源。人們最關(guān)心的就是程序所用算法運(yùn)行時(shí)所要花費(fèi)的時(shí)間代價(jià)和程序中使用的數(shù)據(jù)結(jié)構(gòu)占有的空間代價(jià)。 算法的空間代價(jià)算法的空間代價(jià)(或稱空間復(fù)雜性空間復(fù)雜性)：當(dāng)被解決問題的規(guī)模(以某

10、種單位計(jì)算)由1增至n時(shí)，解該問題的算法所需占用的空間也以某種單位由f(1) 增至f(n)，這時(shí)我們稱該算法的空間代價(jià)是f(n)。 算法的時(shí)間代價(jià)算法的時(shí)間代價(jià)(或稱時(shí)間復(fù)雜性時(shí)間復(fù)雜性)：當(dāng)問題規(guī)模以某種單位由1增至n時(shí)，對(duì)應(yīng)算法所耗費(fèi)的時(shí)間也以某種單位由g(1)增至g(n)，這時(shí)我們稱算法的時(shí)間代價(jià)是g(n)。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述21三個(gè)值得注意的概念： *問題規(guī)模 *空間單位空間單位一般規(guī)定為一個(gè)簡(jiǎn)單變量(如整型、實(shí)型等) 所占存儲(chǔ)空間的大小； *時(shí)間單位時(shí)間單位則一般規(guī)定為執(zhí)行一個(gè)簡(jiǎn)單語(yǔ)句(如賦值語(yǔ)句、判斷語(yǔ)句等)所用時(shí)間。 例如，直接選擇排序 主要運(yùn)算： 比較運(yùn)算 空間單

11、位： 一個(gè)元素占存儲(chǔ)空間s 時(shí)間單位： 一次比較所用時(shí)間t (n-1)+(n-2)+2+1=n*(n-1)/2張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述22 在描述算法分析的結(jié)果時(shí)，人們通常采用“大大O O”表示法表示法：說某個(gè)算法的時(shí)間代價(jià)(或者空間代價(jià))為O(f(n)，則表示如果存在正的常數(shù)c和n0，當(dāng)問題的規(guī)模nn0后，該算法的時(shí)間(或空間)代價(jià)T(n)cf(n)。這時(shí)也稱該算法的時(shí)間(或空間)代價(jià)的增長(zhǎng)率為f(n)。這種說法意味著：當(dāng)當(dāng)n n充分充分大時(shí)大時(shí)，該算法的復(fù)雜性不大于該算法的復(fù)雜性不大于f(n)f(n)的一個(gè)常數(shù)倍。的一個(gè)常數(shù)倍。 常用的計(jì)算規(guī)則：1. 加法規(guī)則 T(n) = T1(

12、n)+ T2(n) = O(f1(n) + O(f2(n) = O(max(f1(n), f2(n)張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述23 2. 乘法規(guī)則 T(n) = T1(n)T2(n) = O(f1(n) O(f2(n)= O(f1(n)f2(n) 采用 “大大O表示法表示法”簡(jiǎn)化了時(shí)間和空間代價(jià)的度量，其基本思想是主要關(guān)注復(fù)雜性的量級(jí)：最壞情況下的代價(jià)(對(duì)同樣規(guī)模的問題所花費(fèi)的最大代價(jià))、最好情況下的代價(jià)和平均情況下的代價(jià)等。關(guān)心當(dāng)n充分大時(shí)，函數(shù)T(n)=？ c logn n n2 2n 常數(shù)，對(duì)數(shù)，線性，二次，指數(shù)（增長(zhǎng)率）。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述2410203040502

13、0040060080010001200140010n20n5n log n2n22n張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述25張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述26Cnn =Ann Bnn for(i=0; in; i+) for(j=0; jn; j+) cij=0; for(k=0; kn; k+) cij = cij+aik*bkj; T(n)=O(f1(n ) f2(n ) (1+n)=O(n2+n3)=O(n3)張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述27 1.5抽象數(shù)據(jù)類型 抽象數(shù)據(jù)類型是模塊化的思想的發(fā)展，它為模塊的劃分提供了理論依據(jù)。 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(Abstract Data Ty

14、pe 簡(jiǎn)稱為ADT)可以看作是定義了一組操作的一個(gè)抽象模型。 例如，集合與集合的并、交、差運(yùn)算就可義為一個(gè)的抽象數(shù)據(jù)類型。一個(gè)抽象數(shù)據(jù)類型要包括哪些操作，這一點(diǎn)由設(shè)計(jì)者根據(jù)需要確定。例如，對(duì)于集合，如果需要，也可以把判別一個(gè)集合是否空集或兩個(gè)集合是否相等作為集合上的操作。張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述28抽象數(shù)據(jù)類型用數(shù)學(xué)方法定義對(duì)象集合和運(yùn)算集合，僅通過運(yùn)算的性質(zhì)刻畫數(shù)據(jù)對(duì)象，而獨(dú)立于計(jì)算機(jī)中可能的表示方法。其目的在于隱藏運(yùn)算實(shí)現(xiàn)的細(xì)節(jié)和內(nèi)部數(shù)據(jù)結(jié)構(gòu)。同時(shí)向用戶提供該數(shù)據(jù)類型的完整信息。例1。ADT pointer例2。ADT circle張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述29 ADT ci

15、rcle is data float r ; operations void constructor( ) 處理： 構(gòu)造一個(gè)圓 float area ( ) return(3.14*r*r); float circumference( ) return(2*3.14*r); end ADT circle;張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述30ADTuser1user2usern.實(shí)現(xiàn)1實(shí)現(xiàn)2實(shí)現(xiàn)3張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述31 從使用的角度看，一個(gè)抽象數(shù)據(jù)類型隱藏了所有使用者不關(guān)心的實(shí)現(xiàn)細(xì)節(jié)。使用抽象數(shù)據(jù)類型觀點(diǎn)，可以使程序模塊的實(shí)現(xiàn)與使用分離，從而能夠獨(dú)立地考慮模塊的外部界面,內(nèi)部算法和數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)。這也可以使應(yīng)用程序只要按抽象數(shù)據(jù)類型的觀點(diǎn)統(tǒng)一其調(diào)用方式，不管其內(nèi)部換用其他的任何數(shù)據(jù)表示方式和運(yùn)算實(shí)現(xiàn)算法，對(duì)應(yīng)用程序都沒有影響。這個(gè)特征對(duì)系統(tǒng)的維護(hù)和修改非常有利。 在許多程序設(shè)計(jì)語(yǔ)言中預(yù)定義的類型，例如整數(shù)類型、浮點(diǎn)類型、指針類型等，都可以看作是簡(jiǎn)單的抽象數(shù)據(jù)類型。 從原則上講，數(shù)據(jù)結(jié)構(gòu)課程中討論的各種表、棧、隊(duì)列、二叉樹和字典等，也可以像整數(shù)、浮點(diǎn)數(shù)等一樣定義為程序設(shè)計(jì)語(yǔ)言預(yù)定義的抽象數(shù)據(jù)類型 張乃孝 算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述32 小 結(jié) 在用計(jì)算機(jī)解題過程中，算法和數(shù)據(jù)結(jié)構(gòu)是