 |
-- 會員 / 註冊 --
|
 |
|
|
|
數據結構與算法分析新視角 ( 簡體 字) |
| 作者：周幸妮等 | 類別：1. -> 程式設計 -> 演算法 |
| 譯者： |
| 出版社：電子工業出版社 |  3dWoo書號： 43744
詢問書籍請說出此書號！【缺書】
NT售價： 345 元 |
| 出版日：3/1/2016 |
| 頁數：515 |
| 光碟數：0 |
|
站長推薦：   |
| 印刷：黑白印刷 | 語系： ( 簡體 版 ) |
| |
加入購物車  │加到我的最愛
(請先登入會員) |
| ISBN：9787121280849 |
| 作者序 | 譯者序 | 前言 | 內容簡介 | 目錄 | 序 |
| (簡體書上所述之下載連結耗時費功, 恕不適用在台灣, 若讀者需要請自行嘗試, 恕不保證) |
| 作者序： |
| 譯者序： |
前言：從新視角來看待舊問題，則需要創造性的思維——愛因斯坦
數據結構的教與學經歷
六七年前上數據結構課時，駕輕就熟地依然按照一貫的講法上課。上了幾次課后，收到班上一位同學的E-mail，信中說：“我自己是特別熱愛寫程序的。一方面我很熟悉電腦，軟硬件都有涉獵，所以學起來就不缺基礎的相關知識（像內存、寄存器、電子電路等等這些都很熟悉）；另一方面我好像很能適應，也很喜歡這種思維方式……但好像班上不少的同學對數據結構的學習理解和接受起來還是比較困難的……”
教授數據結構的課程也有十余年了，一直以來，學生們總是認為數據結構不是一門容易學的課程，“在眾多的專業課中，數據結構被很多學生認為是一門很難學習的課程。”[1]雖然我在學校讀書時沒有學過數據結構的課程，只是因為后來要教書，才自學的數據結構。在自學的過程中，也并沒有覺著內容怎么難啊，這是怎么回事呢？
仔細回想一下自己學習與工作的經歷過程，或許就是來信的這位同學說的，是因為在學習數據結構書本知識之前，已經有了較強的編程的技能、一些數據結構實際應用的先驗知識吧。比如，在研究所工作時首次參加的軟件開發項目中，就有多進程、鏈表、隊列、散列等的實際應用，雖然在學校并沒有學過這些概念，而是先接觸到實際項目中要處理的問題，再看到其他程序員的具體算法處理和程序實現方法，從實際的問題切入，就比較容易理解相應的數據組織形式和對應的算法，等到后來再接觸到書本的理論知識，就有一種一通百通，豁然開朗的感覺。還有一個原因是在軟件開發過程中逐漸熟悉并掌握了程序調試方法，對例程通過跟蹤的方法，很容易弄清執行的路徑和結果，對算法的設計和實現的理解也起到了事半功倍的效果。
回頭來看學生們學習的教科書，概念的介紹是傳統意義上的敘述方式，抽象度很高，但從實際到抽象、從抽象到實際的過程介紹不足，即感性認識不足，抽象就難以理解接受。“現在有一個不好的傾向，就是教材或課堂過于重視抽象化的知識，忽視應用背景。數據結構的教材是這一傾向的代表。這對入門階段的學生來講是不適宜的，因為學生難以走進所涉及的抽象世界，最終表現為不知道在講什么。”[2]
再看我的學生，既沒有實際軟件開發的經驗也沒有熟練的編程調試基礎，對數據結構結構沒有感性認識，先接觸的是那些抽象的概念，感到理解和接受困難也就可以理解了。鄒恒明在《數據結構：炫動的0、1之弦》一書中指出，對于很多人來說，數據結構的概念并不難，真正的難點是：
（1）如何實現從數據結構概念到程序實現的跨越（即如何實現一個數據結構）；
（2）如何實現從實際應用到數據結構抽象的跨越（即如何利用數據結構解決實際問題）。
對于我來說，僅僅在學校學了一點點程序設計語言（記得所有上機時間加起來不超過20小時），沒有任何數據結構的知識，剛出校門就參與了歷時三年多后來獲得國家科技進步三等獎的大型軟件開發工作，以及后續多個電信用戶單位的實際軟件安裝、應用調試和維護工作，親歷了實現了上述兩個“跨越”的最實際生動的案例。雖然項目的開發過程非常艱苦，有在用戶單位調試現場連續大半年的天天加班到深夜、第二天依然要正點到機房的超負荷工作，有通宵的跟蹤調試，有24小時在線系統內存泄漏的巨大壓力，有上線后雙機備份系統同時崩潰爭分奪秒找bug的驚心動魄，等等。應該說自己是很幸運的，雖然在學校僅僅學習了一點點編程的概念，但在工作中根據需要自學和向同事學習了很多新知識、經驗和技巧，這樣的實踐磨練，對后來的程序設計類課程的理解和教授，是非常有益的。
學習數據結構困難的癥結所在
回想與總結起來，之所以要有上述兩個鴻溝要“跨越”，也是由于學校的傳統教科書教法和實際的應用要求脫節造成的。
弗里德里希?威廉?尼采曾寫道：“人們無法理解他沒有經歷過的事情。”[3]換句話來說，我們只接受與過去早已理解的事物相關的信息。這是一種比較學習的過程，在這個過程中，大腦要尋找每條信息之間的聯系，借助以往經驗來理解新事物[4]。
“歐拉認為，如果不能把解決數學問題背后的思維過程教給學生的話，數學教學就是沒有意義的。現代計算機實質上的發明者萊布尼茲也說過：在我看來，沒有什么能比探索發明的源頭還要重要，它遠比發明本身更重要。從小到大，我們看過的數學書幾乎無一不是歐幾里德式的：從定義到定理，再到推論。這樣的書完全而徹底地扭曲了數學發現的真實過程。目前幾乎所有的算法書的講解方式也都是歐幾里德式的，每一個推導步驟都是精準制導直接面向數據結構目標的，實際上，這完全把人類大腦創造發明的步驟給反過來了。對讀者來說，這就等于直接告訴你答案和做法了，然后讓你去驗證這個答案和做法是可行或成立的，而關于答案和做法到底是怎么來的，從問題到答案之間經歷了怎樣的思維過程，卻鮮有書能夠很好地闡釋。對于這類知識講述（歐幾里德方式）方式的批判，西方（尤其是在數學領域）早就有了。”[5]
傳統數據結構教科書的一般模式都是給出問題，然后直接給出算法，而實際上要用計算機解決問題，必須要考慮的處理步驟有：如何分析問題中的已知信息，如何提煉數據及數據間的聯系（數據的邏輯結構），如何選用合適的存儲方式（數據的存儲結構）將邏輯結構存到計算機中，然后在存儲結構之上按照自頂向下逐步細化的方法給出算法，這才是真正解決實際問題的思維方法和步驟，也是軟件開發中實際采用的方法。傳統教科書的問題在于沒有一個思維過程的引導與分析，致使概念論述、實現細節有余，設計實現過程描述不足，讓學生看到的只是一個個問題具體的詳解，而把握不住算法設計的總方法和原則。
本書嘗試從學以致用的角度，注意給出問題或算法的知識背景或應用背景，增加一些在實際軟件開發中的算法應用背景或實例；強調算法的分析方法、設計思路、給出重要算法的測試及調試分析，彌補上述傳統教科書中的不足。教學生以“軟件開發的方法”處理問題，使學生容易理解并掌握它，在實際的軟件開發過程中能靈活地選擇適當的邏輯結構、存儲結構及相應的算法，設計性能優、效率高、可讀性強、易維護的程序，達到數據結構課程最終的目的。
程序設計與數據結構的關系
我們在學習數據結構知識之前要有程序設計的基礎，那么我們先來看看與編程相關的問題。
什么是編程？編程不僅僅是對語法的掌握，還涉及下面的諸多方面：
（1）程序的解題思路——算法是基本運算及規定的運算順序所構成的完整的解題步驟，是程序的靈魂，算法的優劣直接影響程序的效率。本書的算法描述方法見稍后的說明。
（2）程序的運行速度——程序運行的速度受很多因素的影響。用戶對程序的運行速度往往是有要求的，如實時響應系統。
（3）程序的運行空間——代碼運行需要相應的內存空間及相關運行環境。在有些應用場合，對程序占用空間是有限制的，如嵌入式系統。
（4）代碼規范——代碼要按照一定的規范格式書寫，以保證代碼的一致性，便于交流和維護。
（5）程序的結構—— 一個功能復雜的程序由多個功能相對獨立的模塊組成。模塊內高內聚，模塊間低耦合，是判斷程序結構是否合理的標準。
（6）模塊接口——模塊間的信息交流通過接口完成，模塊間信息傳遞參數的設置應該合理有效。
（7）程序的測試與調試——要有精心設計的測試樣例來測試程序是否正確。調試是高效率完成軟件產品的有效方法。一個程序高手，也是調試專家，調試的經驗方法多數都是實踐中得到的。
我們在學習數據結構知識之前要有程序設計的基礎，那么數據結構與程序設計間的關系是怎樣的呢？應該說數據結構是編寫規模龐大、邏輯復雜的更高級程序所需的基礎。表0.1給出了程序設計與高級編程的特點。
表0.1 程序設計與高級編程
涉及課程 主要內容 課程目標
結構化程序
設計 程序設計基礎類課程 語言語法形式、語句使用規則
模塊設計思想 編寫簡單程序
解決簡單問題
高級編程技術 數據結構 數據的抽象思維方法 編寫規模龐大、
邏輯復雜的程序
算法的規范聲明、算法的性能分析、算法的性能評價
軟件工程 部件（模塊）設計思想、軟件工程思想
……
程序設計的首要問題是模塊劃分及相關問題，另一個重要方面，是把要解決問題的信息轉換成計算機能認識并接收的數據，這一轉換過程就是數據的抽象過程。要處理規模龐大的復雜問題，必須掌握數據的抽象思維方法，同時還要熟練掌握算法的規范聲明、算法的性能分析、算法的性能評價等諸多技能。
數據結構與其他課程的關系
作為一門重要的專業核心必修課程，“數據結構與算法”課程既是對以往課程的深入和擴展，也為深入學習其他專業課程打下基礎。課程中排序問題算法以及基本的樹、圖等數據結構，是計算機科學的基本功。B+樹、散列（Hash）等高級數據結構，也是數據庫、操作系統、編譯原理、計算機網絡等重要專業課程的基礎。本課程在計算機學科中與其他課程的關系如圖0.1所示。
圖0.1 “數據結構與算法”課程在計算機學科中的重要地位
數據結構的重要性
商用程序員肖舸在他的博客中寫道：“這么多年，我做過游戲、通信、工業控制、教育、VoIP、服務器集群等各個方向的項目，不可謂不寬。
但是我知道的是，其實我都是在用一種方法寫程序。那就是從最底層的數據結構和算法開始做起，用最基本的C、C++語言開發。用來用去，還是那么幾個數據結構，隊列、堆棧，等等。
這好比武俠小說里面的內功，內力修好了，學招式，非常容易。但如果沒有內力，練再好的招式，見到高手就軟了。一力破十慧，就是這個道理。在絕對的實力面前，任何花招都是沒有用的。”[6]
對清華大學計算機系歷屆畢業生和部分研究生追蹤調查顯示，幾乎所有的學生都認為“數據結構”是他們在學校里學過的最有用的課程之一；數據結構是國內外許多軟件開發機構要求考核的基本課程之一；IT業公司面試或筆試考核的絕大部分內容是數據結構或算法；數據結構也是計算機科學與技術、軟件工程等專業研究生考試必考科目。
數據結構會過時嗎
電子計算機自20世紀四十年代誕生以來硬件上不斷更新換代，軟件也是同步發展的，作為軟件的一個分支程序設計語言也從機器語言發展到了第四代，但無論軟件如何發展，無論開發工具如何進步，只要我們的計算機還是基于馮諾依曼體系，數據結構和算法仍然是程序的核心，永遠不會被淘汰。
學習數據結構和算法并不僅僅要求我們學會如何使用和實現某種數據結構，更重要的是學會分析解決問題的思想和方法。
本書關于算法與程序實現增加的內容
在基礎數據結構——線性表與運算受限的線性表棧與隊列章節中，特別增加了下列內容。
1．增加測試樣例的設計
從程序健壯性的角度出發，測試樣例的設計是開始程序設計就應該考慮的一個重要內容。一般的程序設計與數據結構教科書很少考慮測試樣例問題，本書在最初基本的算法設計中，給出了基礎程序的測試樣例設計，也是讓學習者以專業的方法學習程序設計，養成良好的設計習慣。
2．增加函數結構的設計
對初學者而言，在學習數據結構時，程序設計語言基礎并不扎實，特別是函數結構的設計不熟練。根據給定的功能、輸入輸出信息，在調用與被調用的函數關系中，信息是怎樣傳遞的，往往存在多種可能的選擇，該怎樣確定合適的形參類型、函數類型，初學者經常會無所適從，從而造成編程困難。根據這種情況，本書特別給出了典型數據結構運算的多種方案實現，在同一問題不同函數結構設計的比較中，讓讀者發現各種信息傳遞的方式和特點，鞏固和熟練編程知識和技巧，達到理論與實踐的統一。
函數結構樣例分別見表0.2和表0.3。
表0.2 函數結構樣例1
功能描述 輸入 輸出
順序表中查找給定的值
LocateElem_Sq 順序表地址SequenList * 正常：下標值int
結點值 ElemType 異常：?1
函數名 形參 函數類型
表0.3 函數結構樣例2
功能描述 輸入 輸出
順序表中取給定下標的元素值
GetElem_Sq 順序表地址SequenList * 返回 正常：1
下標int 異常：0
（結點值 ElemType） 結點值ElemType
函數名 形參 函數類型
說明：當函數中的輸入和輸出項中的內容一樣時，表示函數的返回信息是通過形參的址傳遞方式，而非return方式。如表0.3中函數結構樣例2中，輸入輸出都有“結點值ElemType”項，表示是形參采用“地址傳遞”方式。
3．增加重要程序的調試
程序設計的過程也是一個測試與調試的過程，程序的編與調是密不可分的。對于初學者而言，若調試不熟練，容易喪失繼續學習的信心。根據多年的教學經驗，若有程序調試演示，則相關程序比較容易掌握，特別是在學習鏈表等內容時，光是解釋數據結構、結點聯系，學生總覺得抽象難懂，若通過演示調試，觀察各結點間的聯系如何動態建立、消除等，則生動直觀，一目了然。由于調試過程步驟較多，學生看過了明白了，但要再回想并模擬跟蹤過程，則是不容易的事情，所以本書把一些重點例子的程序跟蹤過程記錄下來，以便學生學習。本書所有的源碼均以C語言編制，并在VS IDE環境下通過調試和測試。
4．算法描述方法
算法描述按照下面的順序給出（主要用于編程最基礎的線性表部分），內容詳見1.5.3節。
1）測試用例設計。
2）數據結構描述。
3）函數結構設計。
4）算法偽代碼描述。
5）程序實現。
6）算法效率分析：
注：#define TRUE 1
#define FALSE 0
數據結構課程簡介
用計算機解決實際問題，首先要做的事情就是要把涉及問題的相關信息存儲到計算機中，也就是需要把問題的信息表示為計算機可接收的數據形式，然后根據問題處理功能的要求，對存儲到計算機中的數據進行處理。歸結為一句話，可以這樣說，用計算機解題首先要用合理的結構表示數據，然后才能根據相應的算法處理數據，而數據表示和數據處理正是數據結構學科要研究的內容。
“數據結構”主要介紹如何合理地組織數據、有效地存儲和處理數據，正確地設計算法以及對算法的分析和評價。
通過本課程的學習，學生能深透地理解數據結構的邏輯結構和物理結構的基本概念以及有關算法，學會分析數據對象特征，掌握數據組織方法和計算機的表示方法，以便在實際的軟件開發過程中靈活的選擇適當的邏輯結構、存儲結構及相應的算法，設計性能優、效率高、可讀性強、易維護的程序，解決實際問題。
數據結構是實踐性很強的一門課程，本課程的特色就是注重實踐活動。通過大量上機實驗，能加深對課程理論知識的理解，增強學習的興趣，提高計算計算法思維邏輯能力，為以后的學習和工作打下堅實的基礎。
本課程的基本要求如下：
? 了解數據結構及其分類、數據結構與算法的密切關系。
? 熟悉各種基本數據結構及其操作，學會根據實際問題要求來選擇數據結構。
? 掌握設計算法的步驟和算法分析方法。
? 掌握數據結構在排序和查找等常用算法中的應用。
? 初步掌握索引技術。
? 了解經典算法。
本書的組織結構
本書共分9章。第1章介紹數據結構和算法的基本概念和算法分析方法。第2章至第6章從軟件開發的角度，通過應用背景或知識背景介紹、數據分析、函數設計、算法設計、調試等環節，分別對順序表、鏈表、棧、隊列、串、數組、樹、圖等基本類型的數據結構進行分析和討論。第7章排序技術介紹常見的數據排序方法，第8章索引查找技術介紹數據的查找方法，第7、8章的內容是對數據的典型操作方法的介紹。第9章經典算法，介紹一些常見的如遞歸、分治法、動態規劃、貪心法等經典算法。
前言、第1章至第6章由周幸妮老師完成；第7、9章由任智源老師完成；第8章由馬彥卓老師完成；樊凱老師提供了通信等方面的部分專業應用案例；周幸妮對全書進行了統稿。
書中設有“思考與討論”、“知識ABC”等欄目。在“思考與討論”欄目中提出問題，引起讀者思考，并對提出的問題進行探討，幫助讀者加深對相關概念等的理解，以期活躍思路擴展思維。“知識ABC”欄目主要介紹相應概念的知識、知識背景、算法的發明背景或故事等，以擴大讀者的知識面和了解數據結構的應用背景等。有些知識可能專業性比較強，對此可以“不求甚解”，大致了解即可，感興趣了可以再去查相關資料。
致謝
本書的寫作動力，依然是源自于我的學生，起因是09級教改班同學的提議，認為我的授課方式、思路都不錯，寫出來會別具一格，讓大家學習這個課程時能更好理解一些，這部分內容在我的《C語言程序設計新視角》一書中有所提及。
我的動力亦源于父親的鼓勵、家人的支持。感謝鐵滿霞教授、陳慧嬋教授的指點；感謝屈宇澄同學自始而至終的支持和幫助；感謝孫蒙、丁煜、孫舒、孫亞萍、張柯、楊恒杰、吳偉基、黃超、張平等同學的熱心幫助；感謝通信工程學院13級教改班、14級卓越班，空間科學與技術學院13級實驗班同學們對本書初稿講義提出的各種有益的意見和建議。
所有和同學們、同事們的討論都讓人受益匪淺，這些討論或開拓了視野，或引起了深入思考，所有的一切都是一種成長與完善的歷程。
感謝曾經給予我很多幫助、一起辛苦工作的同事們；感謝我有趣的人生經歷；感謝我可愛的學生們；感謝所有關心和幫助我的人們。
感謝Bandari的April，每天伊始，美妙的樂曲讓人在純凈、安定、溫暖的情緒中開始一天的寫作。
感恩一切。
周幸妮
2015年春于長安 |
內容簡介：數據結構是高等學校計算機及其相關專業的核心課程，是計算機程序設計的基礎。本書按照“像外行一樣思考，像專家一樣實踐”的解決問題的思維方法，列舉大量實際或工程案例，從具體問題中引出抽象概念，運用類比、圖形化描述等各種方式，對經典數據結構內容做深入淺出的介紹。在介紹數據結構和算法的基本概念和算法分析方法的基礎之上，從軟件開發的角度，通過應用背景或知識背景介紹、數據分析、函數設計、算法設計、測試調試等環節，分別對順序表、鏈表、棧、隊列、串、數組、樹、圖等基本類型的數據結構進行了分析和討論；介紹數據的典型操作方法，如數據排序方法和查找方法；介紹常見的如遞歸法、分治法、動態規劃、貪心法等經典算法。 |
目錄：第1章 緒論 1
1.1 從編程說起 1
1.2 程序要處理的數據 5
1.3 數據結構的引入 11
1.4 數據結構的基本概念 13
1.4.1 數據結構基本術語 13
1.4.2 數據結構的三個要素 13
1.5 如何設計算法 16
1.5.1 算法的定義及表示方法 16
1.5.2 算法設計與函數設計的關系 17
1.5.3 軟件設計描述方法 18
1.5.4 算法設計的一般步驟 19
1.6 如何評價算法的優劣 21
1.6.1 算法的設計要求 21
1.6.2 算法效率的度量方法 22
1.7 算法性能的事前分析方法 23
1.7.1 問題的規模與算法的策略 23
1.7.2 算法效率的上限與下限 25
1.7.3 漸進的上限——算法的時間
復雜度 28
1.7.4 算法時間復雜度的綜合討論 29
1.7.5 算法的空間效率分析方法 33
1.8 算法性能綜合考量 37
1.9 本章小結 38
習題 38
第2章 結點邏輯關系為線性的結構——線性表 41
2.1 從邏輯結構角度看線性表 41
2.1.1 實際問題中的線性關系 41
2.1.2 線性表的邏輯結構 42
2.2 線性表的存儲結構方法之一——順序表 43
2.2.1 順序表的存儲結構設計 43
2.2.2 順序表的運算 46
2.2.3 順序存儲結構的討論 53
2.3 線性表的存儲結構方法之二——鏈表 53
2.3.1 單鏈表的存儲 56
2.3.2 單鏈表的運算 60
2.3.3 單鏈表的討論 78
2.3.4 循環鏈表 78
2.3.5 雙向鏈表 81
2.3.6 鏈表小結 86
2.4 線性表的應用舉例 87
2.4.1 逆序輸出單鏈表結點值 87
2.4.2 一元多項式的相加 88
2.5 順序表和鏈表的比較 95
2.6 本章小結 96
習題 97
第3章 運算受限的線性表——棧和隊列 100
3.1 棧——按照先入后出的方式管理的線性表 100
3.1.1 棧處理模式的引入 100
3.1.2 棧的邏輯結構 104
3.1.3 棧的存儲結構設計 106
3.1.4 棧的操作 107
3.1.5 各種棧結構的比較 123
3.1.6 棧的應用舉例 123
3.2 隊列——按照先入先出方式管理的線性表 132
3.2.1 隊列處理模式的引入 133
3.2.2 隊列的邏輯結構 136
3.2.3 隊列的順序存儲結構 137
3.2.4 順序隊列的基本操作 148
3.2.5 隊列的鏈式存儲結構 152
3.2.6 鏈隊列的基本操作 153
3.2.7 各種隊列結構的比較 160
3.2.8 隊列的應用舉例 161
3.3 本章小結 171
習題 172
第4章 內容特殊的線性表——多維數組與字符串 175
4.1 多維數組 175
4.1.1 數組的概念 175
4.1.2 數組的存儲結構 177
4.2 矩陣的壓縮存儲 181
4.2.1 對稱矩陣的壓縮存儲 182
4.2.2 三角矩陣的壓縮存儲 183
4.2.3 對角矩陣的壓縮存儲 183
4.2.4 稀疏矩陣的壓縮存儲 185
4.3 字符串 189
4.3.1 字符串的定義 189
4.3.2 字符串的存儲結構 190
4.3.3 字符串的查找——模式匹配 195
4.4 本章小結 211
習題 213
第5章 結點邏輯關系分層次的非線性結構——樹 216
5.1 實際問題中的樹 216
5.2 樹的邏輯結構 219
5.2.1 樹的定義和基本術語 219
5.2.2 樹的操作定義 222
5.3 樹的存儲結構 222
5.3.1 樹的連續存儲方式 223
5.3.2 樹的鏈式存儲方式 224
5.4 二叉樹的邏輯結構 226
5.4.1 二叉樹的概念 229
5.4.2 二叉樹的基本性質 230
5.4.3 二叉樹的操作定義 231
5.5 二叉樹的存儲結構及實現 231
5.5.1 二叉樹的順序結構 232
5.5.2 二叉樹的鏈式存儲
結構——二叉鏈表 235
5.5.3 建立動態二叉鏈表 236
5.6 二叉樹結點的查找 問題——樹的遍歷 240
5.6.1 樹的廣度優先遍歷 242
5.6.2 樹的深度優先遍歷 244
5.6.3 樹的遍歷的應用 255
5.7 樹的應用 259
5.7.1 表達式樹 259
5.7.2 線索二叉樹 260
5.7.3 哈夫曼樹及哈夫曼編碼 265
5.8 廣義表 278
5.8.1 廣義表的定義 279
5.8.2 廣義表的存儲 281
5.8.3 廣義表的基本運算 287
5.9 本章小結 293
習題 295
第6章 結點邏輯關系任意的非線性結構——圖 299
6.1 實際問題中的圖及抽象 299
6.2 圖的邏輯結構 304
6.2.1 圖的定義和基本術語 304
6.2.2 圖的操作定義 307
6.3 圖的存儲結構及實現 308
6.3.1 圖的數組表示法1—— 鄰接矩陣 308
6.3.2 圖的數組表示法2—— 邊集數組 310
6.3.3 圖的鏈表表示法1——鄰接表 311
6.3.4 圖的鏈表表示法2—— 十字鏈表 316
6.3.5 圖的鏈表表示法3——鄰接多重表 317
6.3.6 圖各種存儲結構的歸結比較 319
6.4 圖的基本操作 320
6.4.1 鄰接矩陣的操作 320
6.4.2 鄰接表的操作 322
6.5 圖的頂點查找問題——圖的遍歷 328
6.5.1 圖的廣度優先遍歷BFS 329
6.5.2 圖的深度優先遍歷DFS 334
6.5.3 圖的遍歷小結 340
6.6 圖的經典應用——圖中的樹問題 340
6.6.1 生成樹 342
6.6.2 最小生成樹MST 343
6.6.3 求最小生成樹算法1——Prim 算法 344
6.6.4 求最小生成樹算法2——Kruskal算法 349
6.6.5 生成樹算法小結 356
6.7 圖的經典應用——最短路徑問題 357
6.7.1 最短路徑問題的引入 357
6.7.2 單源最短路徑算法——Dijkstra算法 359
6.7.3 各頂點對間最短路徑算法——Floyd算法 364
6.7.4 最短路徑問題小結 369
6.8 圖的經典應用——活動頂點與活動邊的問題 370
6.8.1 圖的活動頂點排序問題的引入 370
6.8.2 AOV網與拓撲排序——活動頂點排序問題 373
6.8.3 AOE網與關鍵路徑——活動邊最長問題 378
6.8.4 活動頂點與活動邊問題小結 390
6.9 本章小結 390
習題 391
第7章 數據的處理方法——排序技術 397
7.1 概述 397
7.1.1 排序的基本概念 397
7.1.2 排序算法的分類 399
7.2 插入排序 399
7.2.1 直接插入排序 399
7.2.2 希爾排序 402
7.3 交換排序 404
7.3.1 冒泡排序 404
7.3.2 快速排序 406
7.4 選擇排序 409
7.4.1 簡單選擇排序 410
7.4.2 堆排序 411
7.5 歸并排序 415
7.6 分配排序 418
7.6.1 桶排序 418
7.6.2 基數排序 421
7.7 各種排序算法的比較 424
7.8 本章小結 427
習題 428
第8章 數據的處理——索引與查找技術 431
8.1 索引的基本概念 433
8.1.1 索引的定義 433
8.1.2 索引的邏輯特征 434
8.1.3 索引的主要操作 435
8.2 線性索引技術 435
8.2.1 稠密索引 435
8.2.2 分塊索引 436
8.2.3 多重表 437
8.2.4 倒排表 439
8.3 樹形索引 441
8.3.1 二叉排序樹 441
8.3.2 B樹 448
8.4 查找概述 452
8.4.1 查找的基本概念 452
8.4.2 查找算法的性能 453
8.5 線性表的查找技術 453
8.5.1 順序查找 453
8.5.2 有序表查找 454
8.5.3 索引查找 459
8.6 樹表的查找技術 461
8.6.1 二叉排序樹 461
8.6.2 B樹 462
8.6.3 在非數值有序表上的查找——字典樹 462
8.7 散列表的查找技術 464
8.7.1 散列概述 465
8.7.2 散列函數的設計 467
8.7.3 處理沖突的方法 469
8.7.4 散列查找的性能分析 473
8.8 本章小結 474
習題 476
第9章 經典算法 479
9.1 遞歸算法 479
9.1.1 遞歸的概念及要素 479
9.1.2 遞歸的應用場景 481
9.1.3 遞歸的計算機實現 482
9.1.4 遞歸方法特點分析 483
9.1.5 遞歸算法實例 485
9.1.6 遞歸小結 487
9.2 分治算法 487
9.2.1 分治是什么 487
9.2.2 分治法的適用條件 488
9.2.3 分治問題的類型 488
9.2.4 分治法小結 490
9.3 動態規劃 491
9.3.1 什么是動態規劃 491
9.3.2 動態規劃的解題方法 493
9.3.3 動態規劃解題實例 495
9.3.4 動態規劃小結 500
9.4 貪心算法 501
9.4.1 貪心算法是什么 501
9.4.2 貪心算法經典問題 502
9.4.3 貪心算法小結 504
9.5 回溯法 504
9.5.1 回溯法是什么 504
9.5.2 回溯法經典問題 507
9.5.3 回溯法小結 509
9.6 分支限界法 509
9.6.1 什么是分支限界法 509
9.6.2 分支限界法的求解思想 511
9.6.3 分支限界法經典問題 512
9.6.4 分支限界法小結 514
9.7 本章小結 514
習題 516
附錄A 數據的聯系圖 517
附錄B 自定義頭文件的加入方法 518
附錄C 軟件設計說明書格式 519
參考文獻 521 |
| 序： |
|
