編輯推薦

（1）基於抽象數據類型講解數據結構，以“積木式”組件方案構建程序。

（2）以算法分析為導嚮，以算法效率為準繩，實現數據結構的算法性能提升。

（3）以C++語言描述程序，遵循C++11標準。

（4）以標準模闆庫（STL）高效地編寫C++程序代碼。

內容簡介

　　本書按照計算機發展的時間和曆史，從理論到器件，從簡單器件到復雜器件，由淺到深，詳細描述計算機內部各種部件的原理和應用。本書學術思想新穎*麵，很多內容是國內書上*一次齣現，主要描述計算機數字和邏輯的基本原理及理論，如數字與邏輯的概念，數製、運算、編碼和數字係統，邏輯門，布爾代數和邏輯化簡，組閤邏輯，組閤邏輯電路函數，觸發器和相關器件，計數器，移位寄存器，內存和外存，微處理器、計算機和總綫，數字信號處理，集成電路技術，單片式計算機，計算機的發展與理論，錯誤檢測與糾錯代碼。另外本書還有附錄，包括本書關鍵術語、2的冪次錶、數量級錶等，本書的*後是參考文獻，以便讀者今後在程序設計和計算機及處理器的設計時查閱。本書適閤作為高等院校計算機專業及相關專業本科生及研究生的教材，也可以作為自學者和開發者的參考用書。

目錄

第1章算法

1.1概述

1.2[實例]二分查找

1.3程序性能與算法分析

1.3.1時間復雜度

1.3.2空間復雜度

1.4漸近記號

1.5[技巧]階的快速比較*

1.5.1加和型無窮大量階的比較

1.5.2乘積型無窮大量階的比較

1.5.3對數型無窮大量階的比較

1.6習題

第2章抽象數據類型

2.1概述

2.2[實例]在數據集中查找給定值

2.2.1缺點一：長度受限製

2.2.2缺點二：有序則難變

2.2.3缺點三：查變難兩全

2.2.4查找問題的抽象數據類型視角

2.3數據庫與數據集

2.3.1數據庫

2.3.2數據集

2.4功能與實現

2.4.1嚮量的伸縮

2.4.2有序嚮量實現

2.4.3無序嚮量實現

2.4.4對比

2.5[技巧]組裝使用

2.6STL容器一覽

2.7設計模式

2.7.1迭代器

2.7.2適配器

2.7.3組閤

2.8習題

第3章嚮量

3.1概述

3.2[使用]vectoz

3.3vector的簡要實現

3.4加倍技術*

3.5[技巧]物理存儲與進製換算

3.5.1一維數組

3.5.2二維數組

3.5.3多維嚮量

3.6[技巧]自然數映射與下標

3.7[實例]矩陣的嚮量實現

3.7.1矩陣的簡易實現

3.7.2稀疏矩陣

3.8習題

第4章遞歸

4.1概述

4.2[技巧]遞歸設計與歸納證明

4.3遞歸與進程模型

4.4遞歸算法性能分析

4.5[實例]排列生成器*

4.5.1利用vector傳值實現

4.5.2利用vector引用實現

4.6[實例]樂高鋪磚

4.7習題

第5章棧

5.1概述

5.2[使用]stack

5.3stack的簡要實現

5.4[技巧]邏輯錶達式優化

5.5[實例]路徑搜索

5.6習題

第6章隊列

6.1概述

6.2[使用]queue

6.3[技巧]循環嚮量設計

6.3.1使用兩個位置指示

6.3.2使用計數信息

6.4queue的簡要實現

6.5[實例]賈憲三角

6.6[技巧]排隊組織與內蘊次序

6.7習題

第7章鏈

7.1概述

7.2[使用]list

7.3[技巧]用於鏈接的指針

7.3.1利用指針實現鏈接功能

7.3.2使用真實鏈首元素指針

7.3.3使用啞結點解決空鏈判斷問題

7.4鏈的變種

7.4.1單鏈

7.4.2單循環鏈

7.4.3雙循環鏈

7.5list的簡要實現

7.6[技巧]基於歸納的初始條件選取

7.7[實例]歸並排序

7.8習題

第8章二叉樹

8.1概述.

8.2二叉樹與樹

8.3[技巧]二叉樹遍曆

8.4[技巧]遞歸處理二叉樹

8.5[實例]二叉查找樹

8.5.1特性

8.5.2查找

8.5.3插入

8.5.4：刪除

8.5.5迭代器

8.5.6效率

8.6習題

第9章集閤

9.1概述

9.2[使用]set與multiset

9.3[實例]尋找寶藏

9.4[技巧]哨兵

9.4.1綫性查找中的哨兵

9.4.2二叉查找樹中的哨兵

9.5[技巧]集閤與序關係

9.5.1排序

9.5.2中位數

9.6[技巧]不相交集

9.7習題

第10章優先級隊列

10.1概述

10.2[使用]priority—queue

10.3[技巧]維護最大元

10.4priority-queue的簡要實現

10.5[實例]堆排序

10.5.1數據組織與排序

10.5.2建堆算法

10.6[實例]Huffman編碼

10.7習題

第11章圖

11.1概述

11.2圖的錶示

11.2.1鄰接矩陣

11.2.2鄰接錶

11.2.3選用

11.3圖類

11.3.1有嚮圖類

11.3.2加權有嚮圖類

11.3.3加權無嚮圖類

11.4f技巧]編號與反嚮映射

11.5[技巧]DFS和BFS

11.5.1深度優先搜索

11.5.2廣度優先搜索

11.5.3若乾應用

11.6[實例]最短路徑*

11.6.1Diiikstra算法

11.6.2Bellman—Ford—Moore算法

11.6.3Floyd—Warshall算法

11.7[實例]最小生成樹

11.7.1Kruskal算法

11.7.2Prim算法

11.8習題

第12章實驗

12.1多維求和

12.1.1一維部分和

12.1.2實驗要求

12.1.3評注與引申

12.2幻方計數

12.2.1排列

12.2.2實驗要求

12.2.3評注與引申

12.3隨機行走

12.3.1僞隨機數生成

12.3.2實驗要求

12.3.3評注與引申

12.4紙牌遊戲

12.4.1可數集

12.4.2實驗要求

12.4.3評注與引申

12.5迷宮生成

12.5.1隔闆型迷宮

12.5.2實驗要求

12.5.3評注與引申

12.6數據壓縮

12.6.1.存儲數據

12.6.2實驗要求

12.6.3評注與引申

12.7會場安排

12.7.1時間格式

12.7.2實驗要求

12.7.3評注與引申

12.8排序測試

12.8.1隨機置換

12.8.2實驗要求

12.8.3評注與引申

附錄A頭文件

A.1計時類

A.2book.h

附錄B中文參考書目

B.1國內數據結構教材

B.2數據結構教材（翻譯版）

B.3算法教材（翻譯版）

英文參考文獻

前言/序言

範文瀾曾雲“闆凳要坐十年冷”, Peter Norvig也寫過一篇異麯同工的Teach Yourself Programming in Ten Years妙文. 盡管一般人不可能用十年去培養非常專業的功底, 但我們希望在有限的課程時間內培養齣學生的基本技能, 並為他們打開程序設計這扇神奇之窗.那麼如何盡快學會搭建程序呢? 樂高積木為我們提供瞭一種很好的思路, 學生隻需使用基本的“積木式”組件便可迅速完成程序設計. 抽象數據類型正是這樣的積木, 而C++的標準模闆庫(STL)已為我們準備好瞭.在學會組建程序的基礎上, 我們要求從算法角度分析效率, 而抽象數據類型的簡約性更利於我們在宏觀上盡快給齣優良的方案設計. 因此, 貫穿全書的主綫是抽象數據類型的選擇、使用和組閤.我們特彆強調在抽象數據類型選用時必須以算法分析為導嚮, 以算法效率為準繩. 對於以不同抽象數據類型為要素的實現方案, 其選擇標準是完成整個方案所需的時空開銷.此外, 我們還會關注同一抽象數據類型在不同數據結構實現下的性能差異. 在上述思想指導下, 本書力求給齣一種全新的模式, 讓學生盡快學會高效使用抽象數據類型, 最終為後續的算法設計課程打下堅實的基礎.

。。。。。。。。。。。。。

。。。。。。。。。。。。。

。。。。。。。。。。。。。

。。。。。。。。。。。。。

。。。。。。。。。。。。。

。。。。。。。。。。。。。

。。。。。。。。。。。。。

。。。。。。。。。。。。。

。。。。。。。。。。。。。