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

前言

計算機在各個領(lǐng)域的應(yīng)用過程中，都會涉及數(shù)據(jù)的組織與程序的編排等問題，都會用到各種各樣的數(shù)據(jù)結(jié)構(gòu)，特別是針對各種特殊數(shù)據(jù)的表示，就更需要學(xué)會分析和研究計算機加工對象的特性、選擇最合適的數(shù)據(jù)組織結(jié)構(gòu)及其存儲表示方法，以及編制相應(yīng)實現(xiàn)算法的方法，這是計算機工作者不可缺少的知識。因此“數(shù)據(jù)結(jié)構(gòu)”這門課一直是高等院校計算機專業(yè)教學(xué)中的一門主要技術(shù)基礎(chǔ)課程，在我國當前的計算機專業(yè)教學(xué)計劃中，它是主干課程之一。本書分數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計兩部分。在數(shù)據(jù)結(jié)構(gòu)中，討論了四大類型數(shù)據(jù)結(jié)構(gòu)的邏輯特性、存儲表示及其應(yīng)用。在算法設(shè)計中著重闡述典型算法的設(shè)計與分析。每一章后都配有適量的習(xí)題，以供讀者練習(xí)。全書分上、下兩篇，共16章。前9章為上篇，主要闡述數(shù)據(jù)結(jié)構(gòu)的相關(guān)內(nèi)容；后7章主要闡述算法設(shè)計的相關(guān)內(nèi)容。第1章至第4章主要介紹數(shù)據(jù)結(jié)構(gòu)的基本知識和幾種基本的數(shù)據(jù)結(jié)構(gòu)，即線性表、棧和隊列、串和數(shù)組，它們均屬于線性數(shù)據(jù)結(jié)構(gòu)。第5和第6章敘述非線性數(shù)據(jù)結(jié)構(gòu)，它們是樹、圖和廣義表；第7、8兩章分別介紹數(shù)據(jù)處理中廣泛使用的技術(shù)——排序和查找；第9章討論外存儲器上的數(shù)據(jù)結(jié)構(gòu)——文件；第10章至第14章介紹了蠻力法、貪心法、分治法、動態(tài)規(guī)劃法和回溯法等典型算法及應(yīng)用；第15章介紹計算復(fù)雜性理論；第16章介紹分布式算法的設(shè)計與分析。本書是在計算機科學(xué)與技術(shù)專業(yè)規(guī)范和作者多年的教學(xué)經(jīng)驗的基礎(chǔ)上編寫而成的。本書的編寫思路既注重基本原理的介紹又重視實踐能力的培養(yǎng)。書中還配有大量的例題和習(xí)題，供學(xué)生練習(xí)，加深對知識點的理解。本書講解詳細，通俗易懂，詳略得當。書中算法采用C語言進行描述，且所給的程序均已在計算機上運行調(diào)試，部分程序還做了較詳細的注解，以便于讀者了解算法的實質(zhì)和基本思想。書中每一章均有習(xí)題，可以檢驗讀者的學(xué)習(xí)效果和培養(yǎng)程序設(shè)計的能力。本書既可作為計算機專業(yè)學(xué)生的教材，亦可供從事計算機應(yīng)用的工程技術(shù)人員參考，特別適合于那些使用C語言編程的計算機應(yīng)用人員。使用本書作為本科生教材時，其內(nèi)容可以講授一個學(xué)期；若作為?？粕滩臅r，可以酌情精簡有關(guān)內(nèi)容。本書初稿經(jīng)過在我校的教學(xué)實踐的檢驗，教學(xué)效果較好，學(xué)生反映本書好學(xué)易懂。本書的第1章的前兩節(jié)、第4章、第5章、第6章和第9章由于曉敏編寫，第2章和第3章由于曉坤編寫，第7章和第8章由耿蕊編寫，第1章的第3節(jié)、第10章至第16章由袁琪編寫。由于作者水平有限，書中缺點或錯誤在所難免，殷切希望廣大讀者批評指正。

內(nèi)容概要

計算機在各個領(lǐng)域的應(yīng)用過程中，都會涉及數(shù)據(jù)的組織與程序的編排等問題，都會用到各種各樣的數(shù)據(jù)結(jié)構(gòu)，選擇最合適的數(shù)據(jù)結(jié)構(gòu)和存儲表示方法，以及編制相應(yīng)的實現(xiàn)算法的方法是計算機工作者不可缺少的知識。本書根據(jù)計算機科學(xué)與技術(shù)專業(yè)規(guī)范的要求，全面、系統(tǒng)地介紹各種類型的、最常用的數(shù)據(jù)結(jié)構(gòu)及常用的算法。全書分上、下兩篇，上篇數(shù)據(jù)結(jié)構(gòu)，下篇算法設(shè)計與分析。在數(shù)據(jù)結(jié)構(gòu)中，討論了4大類型數(shù)據(jù)結(jié)構(gòu)的邏輯特性、存儲表示及其應(yīng)用。在算法設(shè)計中著重闡述典型算法的設(shè)計與分析。每一章后都配有適量的習(xí)題，以供讀者練習(xí)。概念清楚，內(nèi)容豐富，詳略得當，既可以作為高等院校計算機應(yīng)用本科等層次的教材，也可以供從事計算機工程與應(yīng)用的科技工作者參考或自學(xué)。

書籍目錄

第1章　緒論上篇　數(shù)據(jù)結(jié)構(gòu)　第2章　線性表　第3章　棧和隊列　第4章　串和數(shù)組　第5章　二叉樹和樹　第6章　圖和廣義表　第7章  排  序　第8章  查  找　第9章  文  件下篇　算法分析　第10章　蠻力法　第11章　貪心法　第12章　分治法　第13章　動態(tài)規(guī)劃法　第14章  回溯法　第15章　計算復(fù)雜性理論　第16章　分布式算法參考文獻

章節(jié)摘錄

插圖：分治法求解較大規(guī)模的問題時，先簡化問題規(guī)模，把該問題分解成幾個子問題，最終通過子問題的解獲得原問題的解。在分解問題的過程中采用的是自頂向下的方法，將大問題分割成獨立的子問題，再對子問題遞歸分解，最終通過最小子問題的解層層合并，最終獲得原問題的解。反之，如果在求解過程中采用自底向上的方法，先求出最小規(guī)模子問題的解，向上逐步擴大問題的規(guī)模，最終獲得原問題的解，這樣的處理過程就引出了動態(tài)規(guī)劃法。動態(tài)規(guī)劃法主要是針對最優(yōu)化問題采用的一種算法。其基本思想是，把求解的問題分成許多階段或多個子問題，然后按順序求解各個子問題。前一子問題的解，為后一子問題的求解提供了有用的信息。在求解任意子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問題，最后一個子問題就是初始問題的解?？梢钥闯觯瑒討B(tài)規(guī)劃法是對多階段決策過程的求解，它的決策不是線性的，而是全面考慮各種不同的情況分階段作出決策。每一階段的決策都會使問題的規(guī)模和狀態(tài)發(fā)生變化，而決策序列就是在這種變化的狀態(tài)中產(chǎn)生出來的，因此稱之為“動態(tài)”的。這種解決多階段決策最優(yōu)化的過程稱為動態(tài)規(guī)劃法。數(shù)據(jù)結(jié)構(gòu)中用于計算有向圖傳遞閉包的warshall算法、計算完全最短路徑的Floyed算法、最優(yōu)二叉查找樹等，數(shù)學(xué)應(yīng)用中的矩陣乘積問題、復(fù)雜工程問題的多種應(yīng)用如資源分配問題、前面介紹過的0／1背包問題、貨郎擔問題、作業(yè)調(diào)度問題等都可以通過動態(tài)規(guī)劃法獲得最優(yōu)解。那么到底哪些問題適用于動態(tài)規(guī)劃法呢？如果原問題能分解為獨立子問題，用分治法較為簡單方便。當子問題不獨立時，則采用動態(tài)規(guī)劃法。通常，能用動態(tài)規(guī)劃法解決的問題應(yīng)該具有下面三個性質(zhì)：1）最優(yōu)化子結(jié)構(gòu)如果問題的最優(yōu)解所包含的子問題也是最優(yōu)的，稱該問題具有最優(yōu)子結(jié)構(gòu)，滿足最優(yōu)化原理。2）無后向性某階段狀態(tài)一旦確定，不受這個狀態(tài)以后決策的影響，即某狀態(tài)以后的過程不會影響以前的狀態(tài)，只與當前狀態(tài)有關(guān)。3）子問題重疊子問題之間不獨立，一個子問題在下一階段決策中可能被多次使用到。該性質(zhì)不是動態(tài)規(guī)劃適用的必要條件，但如果該性質(zhì)無法滿足，動態(tài)規(guī)劃法解決相應(yīng)問題的優(yōu)勢將不復(fù)存在。

編輯推薦

《數(shù)據(jù)結(jié)構(gòu)與算法》：高等學(xué)校教材·計算機教學(xué)叢書。

圖書封面

評論、評分、閱讀與下載

---

    數(shù)據(jù)結(jié)構(gòu)與算法 PDF格式下載

---