數據結構及套用算法教程

《數據結構及套用算法教程》是2001年清華大學出版社出版的圖書，作者是嚴蔚敏、陳文博。

基本介紹

• 書名：數據結構及套用算法教程(含光碟)
• 作者：嚴蔚敏、陳文博
• ISBN：730204012
• 頁數：309
• 定價：29
• 出版社：清華大學出版社
• 出版時間：2001-2-1
• 裝幀：平裝
• 開本：16開

內容簡介

本書從數據類型的角度，分別討論了4大類型的數據結構的邏輯特性、存儲表示及其套用。 為了便於讀者理解，書中對數據結構眾多知識點的來龍去脈都做了詳細的解釋和說明，並配有大量的算法實例穿插其間；書的最後還專門辟出一章，用來講解數據結構在解決實際問題中的套用示例，便於舉一反三。本書的第1章綜述數據、數據結構和抽象數據類型等基本概念和算法；第2章、第4至7章從數據類型的角度，分別討論線性表、棧和佇列、串和數組、二叉樹和樹以及圖和廣義表等數據結構的邏輯特性、存儲表示及其套用；第3章和第8章分別討論排序和查找表的各種實現方法，其中除介紹各種實現方法外，並著重對算法的時間效率做了定性的分析，對算法的套用場合及適用範圍進行了比較和介紹；第9章討論常用的檔案結構；第10章以8個數據結構的綜合套用為例，闡述以抽象數據類型為中心的程式設計方法，這一章的內容相當於“數據結構學習指導”，本意是為學生提供一個“綜合利用數據結構知識編制小型軟體”的規範示例。書的每一章都配有適量的習題，供讀者複習提高之用。　教授學時可為40至60，另外應留有一定的時間供學生完成適量的上機作業。　本書在編排方面注意了數據結構本身的內在聯繫和從易到難的學習規律。例如，將排序安排在第3章，因為對讀者來說，排序的內容比較容易理解，而且所涉及的數據結構主要是線性結構；又如對棧和佇列的學習重點應是它們的套用，因此在第4章里更多地列舉了棧和佇列的套用例子；在第5章中，結合C語言的串類型講解串結構的知識內容，以使實際和理論在套用中和諧統一起來，等等。又如為了降低理解難度，儘管廣義表屬線性結構，但由於它的“遞歸”特性，使得涉及廣義表操作的算法和樹更相似，因此將它放在圖之後進行討論。　全書採用了類C語言作為數據結構和操作算法的描述工具，它是C語言的一個精選子集，同時又採用了C++對C的非面向對象的增強功能。例如動態分配和釋放順序存儲結構的空間；利用引用參數傳遞運算的結果；使用預設參數以簡化函式參數表的描述，等等。這些措施使數據類型的定義和數據結構相關操作算法的描述更加簡明清晰、可讀性更好，轉變成C程式也極方便。另一方面又可把類型定義和操作算法稍加技術處理，就很容易將其封裝成類，並進一步轉化成面向對象的程式模型。　從課程性質上講，“數據結構”是一門專業技術基礎課。它的教學要求應當是：學會從問題入手，分析研究計算機加工的數據結構的特性，以便為套用所涉及的數據選擇適當的邏輯結構、存儲機構及其相應的操作算法，並初步掌握時間和空間分析技術。另一方面，要求學生會書寫符合軟體工程規範的檔案，編寫的程式代碼應結構清晰、正確易讀，能上機調試並排除錯誤。數據結構比高級程式設計語言課有著更高的要求，它重在培養學生的數據抽象能力。　在學習本書時應至少掌握一門高級程式設計的知識，如掌握的是C語言則最為理想；若能具有初步的離散數學和機率論的知識，對書中某些內容的理解會更容易。學習本書的同時還可把《數據結構》(C語言版)作為配套參考用書。與本書配套的還有一張軟碟。　本書內容豐富，概念闡述細緻清楚，除可作為普通高等院校計算機類專業的教材之外，還可作為信息類相關專業“數據結構”或“軟體基礎”課程的本科教材。對於計算機類專業的學生或從事計算機工程與套用工作的科技工作者，本書也是一本實用的參考手冊。

目錄

第1章緒論

1.1數據結構討論的範疇

1.2與數據結構相關的概念

1.2.1基本概念和術語

1.2.2數據結構(datastructures)

1.2.3數據類型和抽象數據類型

1.3算法及其描述和分析

1.3.1算法

1.3.2算法的描述

1.3.3算法效率的衡量方法和準則

1.3.4算法的存儲空間需求

習題

第2章線性表

2.1線性表的類型定義

2.1.1線性表的定義

2.1.2線性表的基本操作

2.2線性表的順序表示和實現

2.2.1順序表——線性表的順序存儲表示

2.2.2順序表中基本操作的實現

2.2.3順序表其他算法舉例

2.3線性表的鏈式表示和實現

2.3.1單鍊表和指針

2.3.2單鍊表的基本操作

2.3.3單鍊表的其他操作舉例

2.3.4循環鍊表

2.3.5雙向鍊表

2.4有序表

2.5順序表和鍊表的綜合比較

習題

第3章排序

3.1排序的基本概念

3.2簡單排序方法

3.2.1插入排序

3.2.2起泡排序

3.3先進排序方法

3.3.1快速排序

3.3.2歸併排序

3.3.3堆排序

3.4基數排序

3.5各種排序方法的綜合比較

習題

第4章棧和佇列

4.1棧

4.1.1棧的結構特點和操作

4.1.2棧的表示和操作的實現

4.2棧的套用舉例

4.3佇列

4.3.1佇列的結構特點和操作

4.3.2佇列的表示和操作的實現

4.4佇列套用舉例

習題

第5章串和數組

5.1串的定義和操作

5.2串的表示和實現

5.2.1定長順序存儲表示

5.2.2堆分配存儲表示

5.2.3塊鏈存儲表示

5.3正文模式匹配

5.4正文編輯——串操作套用舉例

5.5數組

5.5.1數組的定義和操作

5.5.2數組的順序表示和實現

5.5.3數組的套用

5.6矩陣的壓縮存儲

5.6.1特殊形狀矩陣的存儲表示

5.6.2隨機稀疏矩陣的存儲壓縮

習題

第6章二叉樹和樹

6.1二叉樹

6.1.1二叉樹的定義和基本術語

6.1.2二叉樹的幾個基本性質

6.1.3二叉樹的存儲結構

6.2二叉樹遍歷

6.2.1問題的提出

6.2.2遍歷算法描述

6.2.3二叉樹遍歷套用舉例

6.2.4線索二叉樹

6.3樹和森林

6.3.1樹和森林的定義

6.3.2樹和森林的存儲結構

6.3.3樹和森林的遍歷

6.4樹的套用

6.4.1堆排序的實現

6.4.2二叉排序樹

6.4.3赫夫曼樹及其套用

習題

第7章圖和廣義表

7.1圖的定義和術語

7.2圖的存儲結構

7.2.1圖的數組(鄰接矩陣)存儲表示

7.2.2圖的鄰接表存儲表示

7.3圖的遍歷

7.3.1深度優先搜尋遍歷圖

7.3.2廣度優先搜尋遍歷圖

7.4連通網的最小生成樹

7.5單源最短路徑

7.6拓撲排序

7.7關鍵路徑

7.8廣義表

7.8.1廣義表的定義

7.8.2廣義表的存儲結構

7.8.3廣義表的遍歷

習題

第8章查找表

8.1靜態查找表

8.1.1順序查找

8.1.2折半查找

8.1.3分塊查找

8.2動態查找表

8.2.1二叉查找樹

8.2.2鍵樹

8.3哈希表及其查找

8.3.1什麼是哈希表

8.3.2構造哈希函式的幾種方法

8.3.3處理衝突的方法和建表示例

8.3.4哈希表的查找及其性能分析

8.3.5哈希表的套用舉例

習題

第9章檔案

9.1基本概念

9.1.1外存儲器簡介

9.1.2有關檔案的基本概念

9.2順序檔案

9.2.1存儲在順序存儲器上的檔案

9.2.2存儲在直接存儲器上的檔案

9.3索引檔案

9.3.1B樹

9.3.2B+樹和索引順序檔案

9.4哈希檔案

9.4.1檔案組織方式

9.4.2檔案的操作

9.5多關鍵碼檔案

9.5.1倒排檔案

9.5.2索引連結檔案

習題

第10章數據結構程式設計示例

10.1抽象數據類型

10.2從問題到程式的求解過程

10.2.1建立數據結構模型設計抽象數據類型

l0.2.2算法設計

10.2.3實現抽象數據類型

10.2.4編製程序代碼並進行靜態測試和動態調試

10.3程式的規範說明

10.4套用示例分析

10.4.1含並.交和差運算的集合類型

l0.4.2最佳任務分配方案求解

10.4.3排隊問題的系統仿真

l0.4.4十進制四則運算計算器

lo.4.5腳踏車零部件庫的庫存模型

l0.4.6教務課程計畫的輔助制定

lo.4.7一個小型全文檢索模型

10.4.8汽車牌照的快速查找

實習題

實習一鍊表的維護與檔案形式的保存

實習二用回溯法求解“穩定婚配”問題

實習三以佇列實現的仿真技術預測理髮館的經營狀況

實習四利用樹型結構的搜尋算法模擬網際網路域名的查詢

實習五管道鋪設施工的最佳方案選擇

實習六使用哈希表技術判別兩個源程式的相似性

附錄算法一覽表參考文獻