數據結構：用麵嚮對象方法與C++語言描述（第二版） 下載 mobi epub pdf 電子書 在線閱讀 2026

內容簡介

　　《數據結構：用麵嚮對象方法與C++語言描述（第二版）》按照清華大學計算機係本科“數據結構”大綱的要求，從麵嚮對象的概念、對象類設計的風格和數據結構的層次開始，從綫性結構到非綫性結構，從簡單到復雜，深入地討論瞭各種數據結構內在的邏輯關係及其在計算機中的實現方式和使用。此外，對常用的迭代、遞歸、迴溯等算法設計技巧，搜索和排序算法等都做瞭詳盡的描述，並引入瞭簡單的算法分析。

內頁插圖

目錄

第1章 數據結構概論
1．1 數據結構的概念
1．1．1 數據結構舉例
1．1．2 數據與數據結構
1．1．3 數據結構的分類
1．1．4 數據結構課程的內容
1．2 數據結構的抽象形式
1．2．1 數據類型
1．2．2 數據抽象與抽象數據類型
1．3 作為ADT的C++類
1．3．1 麵嚮對象的概念
1．3．2 C++中的類
1．3．3 C++中的對象
1．3．4 C++的輸入輸齣
1．3．5 C++中的函數
1．3．6 動態存儲分配
1．3．7 C++中的繼承
1．3．8 多態性
1．3．9 C++的模闆
1．4 算法定義
1．5 算法性能分析與度量
1．5．1 算法的性能標準
1．5．2 算法的後期測試
1．5．3 算法的事前估計
1．5．4 算法的漸進分析
**1．5．5 最壞、最好和平均情況
習題

第2章 綫性錶
2．1 綫性錶
2．1．1 綫性錶的概念
2．1．2 綫性錶的類定義
2．2 順序錶
2．2．1 順序錶的定義和特點
2．2．2 順序錶的類定義及其操作
2．2．3 順序錶的性能分析
2．2．4 順序錶的應用
2．3 單鏈錶
2．3．1 單鏈錶的概念
2．3．2 單鏈錶的類定義
2．3．3 單鏈錶中的插入與刪除
2．3．4 帶附加頭結點的單鏈錶
2．3．5 單鏈錶的模闆類
2．4 綫性鏈錶的其他變形
2．4．1 循環鏈錶
2．4．2 雙嚮鏈錶
2．5 單鏈錶的應用：多項式及其運算
**2．5．1 多項式的錶示
**2．5．2 多項式的類定義
**2．5．3 多項式的加法
**2．5．4 多項式的乘法
2．6 靜態鏈錶
習題

第3章 棧和隊列
3．1 棧
3．1．1 棧的定義
3．1．2 順序棧
3．1．3 鏈式棧
**3．1．4 棧的應用之一——括號匹配
**3．1．5 棧的應用之二——錶達式的計算
3．2 棧與遞歸
3．2．1 遞歸的概念
3．2．2 遞歸過程與遞歸工作棧
**3．2．3 用迴溯法求解迷宮問題
3．3 隊列
3．3．1 隊列的概念
3．3．2 循環隊列
3．3．3 鏈式隊列
3．3．4 隊列應用舉例：打印二項展開式（a+6）i的係數
**3．3．5 隊列應用舉例：電路布綫
3．4 優先級隊列
3．4．1 優先級隊列的概念
**3．4．2 優先級隊列的存儲錶示和實現
3．5 雙端隊列
3．5．1 雙端隊列的概念
3．5．2 雙端隊列的數組錶示
3．5．3 雙端隊列的鏈錶錶示
習題

第4章 數組、串與廣義錶
4．1 多維數組的概念與存儲
4．1．1 多維數組的概念
4．1．2 多維數組的存儲錶示
4．2 特殊矩陣
4．2．1 對稱矩陣的壓縮存儲
**4．2．2 三對角綫／多對角綫矩陣的壓縮存儲
4．3 稀疏矩陣
4．3．1 稀疏矩陣及其三元組數組錶示
4．3．2 稀疏矩陣的轉置
**4．3．3 稀疏矩陣的相加和相乘
**4．3．4 矩陣的正交鏈錶錶示
4．4 字符串
4．4．1 字符串的概念
4．4．2 C++有關字符串的庫函數
4．4．3 字符串的實現
**4．4．4 字符串的自定義類
**4．4．5 字符串操作的實現
**4．4．6 字符串的模式匹配
**4．4．7 字符串的存儲方法
4．5 廣義錶
4．5．1 廣義錶的定義與性質
4．5．2 廣義錶的錶示
4．5．3 廣義錶存儲結構的實現
**4．5．4 廣義錶的遞歸算法
**4．5．5 三元多項式的錶示
習題

第5章 樹
5．1 樹的基本概念
5．1．1 樹的定義和術語
5．1．2 樹的抽象數據類型
5．2 二叉樹
5．2．1 二叉樹的定義
5．2．2 二叉樹的性質
5．2．3 二叉樹的抽象數據類型
5．3 二叉樹的存儲錶示
5．3．1 二叉樹的數組存儲錶示
5．3．2 二叉樹的鏈錶存儲錶示
5．4 二叉樹遍曆及其應用
5．4．1 二叉樹遍曆的遞歸算法
5．4．2 二叉樹遍曆的應用
5．4．3 二叉樹遍曆的非遞歸算法
5．4．4 二叉樹的計數
5．5 綫索二叉樹
5．5．1 綫索
5．5．2 中序綫索二叉樹的建立和遍曆
**5．5．3 中序綫索二叉樹的插入與刪除
**5．5．4 前序與後序的綫索化二叉樹
5．6 樹與森林
5．6．1 樹的存儲錶示
5．6．2 森林與二叉樹的轉換
5．6．3 樹與二叉樹的轉換
5．7 樹與森林的遍曆及其應用
5．7．1 樹與森林的深度優先遍曆
5．7．2 樹和森林的廣度優先遍曆
**5．7．3 樹遍曆算法的應用
**5．7．4 其他基於遍曆序列的幾種存儲錶示
5．8 堆
5．8．1 最小堆和最大堆
5．8．2 堆的建立
5．8．3 堆的插入與刪除
5．9 Huffman樹及其應用
5．9．1 路徑長度
5．9．2 Huffman樹
**5．9．3 Huffman樹的應用：最優判定樹
5．9．4 Huffman樹的應用：Huffman編碼
習題

第6章 集閤與字典
6．1 集閤及其錶示
6．1．1 集閤的基本概念
6．1．2 用位嚮量實現集閤抽象數據類型
6．1．3 用有序鏈錶實現集閤的抽象數據類型
6．2 並查集與等價類
6．2．1 並查集的定義及其實現
**6．2．2 並查集的應用：等價類劃分
6．3 字典
6．3．1 字典的概念
6．3．2 字典的綫性錶描述
6．4 跳錶
6．4．1 跳錶的概念
**6．4．2 跳錶的類定義
**6．4．3 跳錶的搜索、插入和刪除
6．5 散列
6．5．1 散列錶與散列方法
6．5．2 散列函數
6．5．3 處理衝突的閉散列方法
6．5．4 處理衝突的開散列方法
6．5．5 散列錶分析
習題
……
第7章 搜索結構
第8章 圖
第9章 排序
第10章 文件、外部排序與搜索
附錄A 程序索引
附錄B 詞匯索引
參考文獻

前言/序言

　　計算機的普及極大地改變瞭人們的工作和生活。目前各個行業、各個領域都與計算機建立瞭緊密的聯係，也隨之帶來瞭開發各種軟件的需求。為瞭能夠以最少的成本，最快的速度，最好的質量開發齣閤乎需要的軟件，必須遵循軟件工程的原則，把軟件的開發、維護標準化、工程化，不能再像以前那樣，把軟件看作是個人雕琢的精品。就軟件産品而言，最重要的就是建立閤理的軟件體係結構和程序結構，設計有效的數據結構。因此，要做好軟件開發工作，必須瞭解如何組織各種數據在計算機中的存儲、傳遞和轉換。這樣，“數據結構”這門課程顯得格外重要。自1978年美籍華裔學者冀中田在國內首開這門課程以來（當時作者也在場），經過20餘年的發展，本課程已成為各大學計算機專業本科的主乾課程，也成為非計算機類學生和研究生學習計算機的必修課程。
　　“數據結構”課程脫胎於“離散數學結構”，它涉及各種離散結構（如嚮量、集閤、樹、圖、代數方程、多項式等）在計算機上如何存儲和處理。其內容豐富，涉及麵廣泛，而且還在隨各種基於計算機的應用技術的發展，不斷增加新的內容。特彆是麵嚮對象技術齣現以後，人們認識到，用它開發齣來的軟件體係結構更加符閤人們的習慣，質量更容易得到保證.尤其是更容易適應使用者和用戶不斷提齣的新的需求。因此，在國際上，麵嚮對象技術得到迅速普及，齣現瞭大批麵嚮對象的軟件開發工具。為瞭適閤形勢的要求，有必要開設結閤麵嚮對象技術的數據結構課程。
　　用麵嚮對象的觀點討論數據結構，與傳統的麵嚮過程的講法相比，變化較大。各種數據結構的討論都是基於抽象數據類型和軟件復用的，有新意，也有繼承。我們力圖與過去的講授體係保持一緻，但又必須引入一些新的概念。為瞭能夠讓讀者容易學習，我們對內容進行瞭精選。許多從基本數據結構派生齣來的概念，如雙端堆、二項堆、最小一最大堆、斐波那契堆、左斜樹、扁樹、B*樹等都捨去瞭。同時，把動態存儲管理部分歸到“操作係統”課程，把文件組織部分歸到“數據庫原理”，隻保留瞭重要的應用最廣泛的一些結構。對這些結構做全麵深入的講解，闡明數據結構內在的邏輯關係，討論它們在計算機中的存儲錶示，並結閤各種典型事例說明它們在解決應用問題時的動態行為和各種必要的操作，並以C++語言為錶述手段，介紹在麵嚮對象程序設計過程中各種數據結構的錶達和實現。隻要是學過C或PASCAL語言，就能夠很容易地閱讀和理解，並因此學習C++語言，提高讀者的軟件設計和編程能力。
　　本書是作為清華大學信息學院平颱課“數據結構”的教材編寫的，在編寫過程中得到清華大學信息學院領導的支持，並獲得教育部“十一五”規劃教材的資助。參與策劃的有計算機係教師殷人昆、鄧俊輝、舒繼武、硃仲濤，電子係教師硃明方、吳及，自動化係教師李宛洲、劉義，微納電子學係教師李樹國，軟件學院教師張力以及信息學院辦公室的教師王娜等。第4章由舒繼武執筆，第5章由硃仲濤執筆，第8章由鄧俊輝執筆，第9章由吳及執筆，其他各章由殷人昆執筆。作者們都是在清華大學從事“數據結構”課程第一綫教學的教師，有著豐富的數據結構和軟件工程教學的經驗，教學效果良好。
　　全書共分10章。第1章是預備知識，主要介紹什麼是數據，數據與信息的關係；什麼是數據結構，數據結構的分類。通過學習，讀者能夠瞭解抽象數據類型和麵嚮對象的概念。並對對象、類、繼承、消息以及其他關係的定義、使用有基本認識。由於我們選擇瞭具有麵嚮過程和麵嚮對象雙重特點的C++語言，可以幫助讀者自然而輕鬆地從傳統程序設計觀念嚮麵嚮對象方法轉變。在這一章的最後還討論瞭算法設計和簡單的算法分析方法。
　　第2章是全書的基礎，討論瞭綫性錶、它的數組錶示和鏈錶錶示，以及利用它們定義齣來的各種結構，如順序錶、代數多項式等。通過學習，讀者可以瞭解對象和類的基本實現，並通過模闆、多態性等的使用，對數據抽象概念有進一步的理解。
　　第3章引入4種存取受限的錶，即棧、隊列、優先級隊列和雙端隊列。通過對它們的定義、實現和應用的深入介紹，使讀者能夠瞭解在什麼場閤使用它們，為以後更復雜的數據結構和算法的實現，提供瞭多種輔助手段。
　　第4章介紹在許多領域中經常遇到的多維數組、字符串和廣義錶。這些都是應用廣泛又十分靈活的結構。
　　第5章和第8章介紹在實際應用中最重要的非綫性結構——樹與圖。在管理、電子設計、機械設計、日常生活中許多方麵都會用到它們。
　　第6章、第7章和第10章介紹集閤、跳錶、散列、搜索樹、索引以及文件等結構。在實際與信息處理相關的應用中，這些結構十分重要。許多非數值處理都涉及這些結構，它們與內存、外存上的數據組織關係密切。例如在外存組織文件時全麵應用瞭這些結構。它們又是許多新結構的生長點。因此，讀者學習這些內容將獲益匪淺。
　　第9章介紹排序。這也是應用十分廣泛的技術。隻要是數據處理，就少不瞭排序。如何纔能高效地完成排序，本章分彆就內、外存使用的多種排序方法進行介紹和討論，讀者可以深入瞭解排序的機製，也能從中學到許多程序設計的技巧。
　　本書的篇幅雖然較大，但給讀者以選擇。可以根據時間、能力，適當對學習的內容加以剪裁。本著少講多練的原則，可以對每種結構隻介紹類定義和關鍵操作的實現，其他內容可自學。通過上機練習，加深理解。在本書目錄中加xx的章節可以酌情不講。

《數據結構：用麵嚮對象方法與C++語言描述（第二版）》 內容簡介 本書深入淺齣地闡述瞭數據結構的基本概念、核心算法以及它們在實際應用中的體現，尤其強調瞭麵嚮對象的設計思想與C++語言的結閤應用。旨在為讀者構建紮實的數據結構理論基礎，並掌握利用現代C++特性實現高效、可維護數據結構的實踐能力。 核心內容概述： 本書將數據結構的概念與麵嚮對象的思想緊密融閤，引導讀者從類、對象、封裝、繼承、多態等麵嚮對象的核心原則齣發，去理解和構建各種經典數據結構。C++作為強大的麵嚮對象編程語言，被充分利用來演示這些抽象概念的落地實現。 第一部分：基礎迴顧與麵嚮對象初步 在正式進入數據結構的核心之前，本書會快速迴顧C++語言的基礎知識，並重點講解麵嚮對象編程的關鍵概念。這包括： 類與對象： 如何定義抽象的數據類型，以及如何創建和操作對象。 封裝： 數據與操作數據的函數打包在一起，隱藏內部實現細節，提供清晰的接口。 繼承： 允許創建新的類（派生類），繼承現有類（基類）的屬性和行為，實現代碼復用。 多態： 同一個接口，不同的實現。通過虛函數等機製，實現運行時類型的動態綁定。 模闆（Templates）： 泛型編程的概念，允許編寫與類型無關的代碼，從而實現數據結構的通用性。 理解這些麵嚮對象的基石，將有助於讀者更深刻地理解數據結構的抽象本質，並能夠設計齣更加靈活和可擴展的數據結構。 第二部分：綫性結構 這一部分將詳細介紹各種綫性數據結構，並演示如何利用麵嚮對象的思想和C++的特性來實現它們。 數組（Arrays）： 從靜態數組到動態數組（如C++的`std::vector`）的演進，討論其優缺點、訪問效率和內存管理。 鏈錶（Linked Lists）： 單嚮鏈錶： 節點間的單嚮連接，實現插入、刪除、查找等操作，深入分析其時間復雜度。 雙嚮鏈錶： 節點間雙嚮連接，提供更方便的遍曆和刪除能力。 循環鏈錶： 鏈錶的尾節點指嚮頭節點，常用於某些特定算法。 麵嚮對象實現：將鏈錶節點設計為獨立的類，鏈錶本身也作為管理節點的類，封裝瞭操作接口。 棧（Stacks）： “後進先齣”（LIFO）的數據結構，介紹其應用場景（如函數調用棧、錶達式求值），並用鏈錶或數組實現。 隊列（Queues）： “先進先齣”（FIFO）的數據結構，介紹其應用場景（如任務調度、廣度優先搜索），並用鏈錶或數組實現。 第三部分：非綫性結構 本部分將深入探討更為復雜的數據結構，這些結構中的元素之間不一定是簡單的綫性關係。 樹（Trees）： 二叉樹（Binary Trees）： 每個節點最多有兩個子節點。 二叉搜索樹（Binary Search Trees, BST）： 左子節點小於父節點，右子節點大於父節點，高效實現查找、插入、刪除。 平衡二叉搜索樹（Balanced BST）： 如AVL樹、紅黑樹，通過自平衡機製保證樹的高度，從而保證查找效率。 堆（Heaps）： 完全二叉樹，滿足堆序性質（最大堆或最小堆），常用於優先隊列和堆排序。 多叉樹（M-ary Trees）： 介紹N叉樹的概念及其應用。 麵嚮對象實現：將樹節點設計為具有指嚮子節點的指針（或指針數組）的類，樹本身作為管理者。 圖（Graphs）： 圖的錶示： 鄰接矩陣（Adjacency Matrix）和鄰接錶（Adjacency List）。 圖的遍曆： 深度優先搜索（DFS）和廣度優先搜索（BFS）。 圖的算法： 最短路徑算法（Dijkstra、Floyd-Warshall）、最小生成樹算法（Prim、Kruskal）等。 麵嚮對象實現：將頂點和邊設計為類，圖類管理這些頂點和邊的關係。 第四部分：哈希錶與排序/搜索算法 哈希錶（Hash Tables）： 哈希函數（Hash Functions）： 如何設計一個好的哈希函數來映射鍵到存儲位置。 衝突解決（Collision Resolution）： 開放尋址法（綫性探測、二次探測）、鏈地址法。 應用： 快速查找、字典（Map）的實現。 麵嚮對象實現：封裝哈希函數和衝突解決策略。 排序算法（Sorting Algorithms）： 比較排序： 冒泡排序、選擇排序、插入排序、希爾排序、快速排序、歸並排序、堆排序。 非比較排序： 計數排序、桶排序、基數排序。 深入分析各種排序算法的時間復雜度和空間復雜度，以及它們的適用場景。 搜索算法（Searching Algorithms）： 綫性搜索。 二分搜索（Binary Search）： 在有序數據中高效查找。 第五部分：高級主題與實踐 算法分析： 漸進記號（大O、小o、大Ω、小ω、Θ）用於描述算法的漸進時間復雜度和空間復雜度。 STL（Standard Template Library）： 介紹C++標準模闆庫中的容器（如`vector`, `list`, `set`, `map`）、算法和迭代器，展示如何利用現有成熟的庫高效實現數據結構和算法。 實際應用案例： 結閤前麵介紹的數據結構和算法，分析一些典型的實際應用場景，例如： 文件係統設計中的樹結構。 搜索引擎中的哈希錶和圖。 編譯器中的語法樹。 網絡路由中的圖算法。 本書的特點： 麵嚮對象驅動： 強調從麵嚮對象的視角理解和設計數據結構，培養良好的麵嚮對象設計能力。 C++實踐導嚮： 充分利用C++語言特性，提供清晰、可執行的代碼示例，幫助讀者將理論轉化為實踐。 循序漸進： 從基礎概念到高級主題，逐步深入，適閤不同水平的讀者。 理論與實踐結閤： 不僅講解抽象的理論，還通過大量實例展示數據結構在實際問題中的應用。 深入的算法分析： 詳細討論各種算法的時間和空間復雜度，幫助讀者做齣最優選擇。 通過學習本書，讀者將能夠深入理解數據結構在計算機科學中的核心地位，掌握利用麵嚮對象方法和C++語言構建高效、可擴展的數據結構和算法的能力，為進一步學習更高級的計算機科學理論和工程實踐打下堅實的基礎。