實用數據結構（C++描述）（第二版）

《實用數據結構（C++描述）（第二版）》是由徐士良、葛兵編著，2006年清華大學出版社出版的新世紀計算機基礎教育叢書。該教材可作為高等院校非計算機專業的學生學習數據結構的教材，也可作為數據結構的培訓班教材或自學教材。

該教材共8章，介紹了數據處理領域中常用的數據結構及其主要的運算，所有的算法均給出了C++的描述。

基本介紹

• 書名：實用數據結構（C++描述）（第二版）
• 作者：徐士良、葛兵
• ISBN：9787302136620
• 類別：新世紀計算機基礎教育叢書
• 頁數：263頁
• 出版社：清華大學出版社
• 出版時間：2006年10月1日
• 裝幀：平裝
• 開本：16開
• 字數：411千字
• CIP核字號：2006097543

成書過程

該教材由徐士良、葛兵編著。2006年10月1日，該教材由清華大學出版社出版。

出版社工作人員

組稿編輯	文稿編輯
焦虹	張為民

內容簡介

該教材介紹了數據處理領域中常用的數據結構及其主要的運算，所有的算法均給出了C++的描述。全書共8章，主要內容包括：數據結構與算法的基本概念、線性表及其順序存儲結構、線性鍊表及其運算、數組、樹與二叉樹、圖、查找技術、Hash表技術、排序技術。每章後面都有習題。

教材目錄

第1章緒論1.1數據結構的基本概念1; 1.1.1兩個例子1; 1.1.2什麼是數據結構4; 1.1.3數據結構的圖形表示7; 1.1.4線性數據結構與非線性數據結構8; 1.2算法方面的考慮9; 1.2.1什麼是算法9; 1.2.2算法的複雜度10; 習題12; 第2章線性表及其順序存儲結構; 2.1線性表的基本概念14; 2.1.1什麼是線性表14; 2.1.2線性表的順序存儲結構——順序表15; 2.1.3順序表的基本運算——插入與刪除16; 2.1.4順序表類20; 2.2棧及其套用24; 2.2.1什麼是棧24; 2.2.2棧的順序存儲及其運算26; 2.2.3順序棧類28; 2.2.4表達式的計算31; 2.3佇列及其套用37; 2.3.1什麼是佇列37; 2.3.2循環佇列及其運算37; 2.3.3循環佇列類40; 2.3.4佇列的套用44; 2.4字元串49; 2.4.1字元串的基本概念49; 2.4.2字元串匹配50; 習題55; 第3章線性鍊表; 3.1線性鍊表的基本概念57; 3.1.1線性表順序存儲的問題57; 3.1.2線性鍊表的存儲結構58; 3.1.3線性鍊表類62; 3.1.4帶鏈的棧65; 3.1.5帶鏈的佇列68; 3.2線性鍊表的插入與刪除72; 3.3循環鍊表77; 3.4多項式的表示與運算80; 習題88; 第4章數組; 4.1數組的順序存儲結構90; 4.2規則矩陣的壓縮91; 4.3一般稀疏矩陣的表示94; 4.3.1稀疏矩陣的三列二維數組表示95; 4.3.2稀疏矩陣的線性鍊表表示108; 4.3.3十字鍊表117; 習題121; 第5章樹與二叉樹; 5.1樹123; 5.2二叉樹及其基本性質126; 5.2.1什麼是二叉樹126; 5.2.2二叉樹的基本性質127; 5.2.3滿二叉樹與完全二叉樹128; 5.3二叉樹的遍歷129; 5.4二叉樹的存儲結構131; 5.4.1二叉鍊表131; 5.4.2二叉鍊表類133; 5.5穿線二叉樹137; 5.5.1穿線二叉樹的概念137; 5.5.2中序穿線二叉樹137; 5.5.3前序穿線二叉樹142

5.5.4後序穿線二叉樹145; 5.6表達式的線性化149; 5.6.1有序樹的二叉樹表示149; 5.6.2如何對表達式進行線性化151; 5.7最優二叉樹及其套用151; 5.7.1什麼是最優二叉樹151; 5.7.2最優二叉樹的構造153; 5.7.3霍夫曼編碼158; 習題159; 第6章圖; 6.1圖的基本概念161; 6.2圖的存儲結構162; 6.2.1關聯矩陣162; 6.2.2求值矩陣163; 6.2.3鄰接表164; 6.2.4鄰接多重表166; 6.3圖的遍歷166; 6.3.1縱向優先搜尋法167; 6.3.2橫向優先搜尋法167; 6.4圖鄰接表類167; 6.5最短距離問題173; 習題179; 第7章查找技術; 7.1順序查找180; 7.2有序表的對分查找180; 7.3分塊查找185; 7.4二叉排序樹查找186; 7.4.1二叉排序樹的基本概念187; 7.4.2二叉排序樹的插入188; 7.4.3二叉排序樹的刪除190; 7.4.4二叉排序樹查找192; 7.5多層索引樹查找195; 7.5.1B－樹195; 7.5.2B+樹205; 習題215; 第8章Hash表技術; 8.1Hash表的基本概念217; 8.1.1直接查找技術217; 8.1.2Hash表218; 8.1.3Hash碼的構造218; 8.2幾種常用的Hash表220; 8.2.1線性Hash表220; 8.2.2隨機Hash表224; 8.2.3溢出Hash表229; 8.2.4拉鏈Hash表234; 8.2.5指標Hash表239; 習題239; 第9章排序技術; 9.1互換類排序241; 9.1.1冒泡排序241; 9.1.2快速排序243; 9.2插入類排序246; 9.2.1簡單插入排序247; 9.2.2希爾排序249; 9.3選擇類排序251; 9.3.1簡單選擇排序251; 9.3.2堆排序252; 9.4拓撲分類255; 9.5其他排序方法簡介258; 9.5.1歸併排序258; 9.5.2基數排序261; 習題262; 參考文獻263

（註：目錄排版順序為從左列至右列）

教學資源

• 配套教材
  

該教材有配套教材——《實用數據結構（C++描述）（第二版）習題解答》。

書名	書號	出版社	出版時間	作者
《實用數據結構（C++描述）（第二版）習題解答》	9787302150824	清華大學出版社	2007.06.01	徐士良、葛兵

• 課程資源
  

該教材提供電子課件、原始碼。

教材特色

該教材內容的表現形式實用，書中所有的算法均採用C++語言描述，由於C++語言既可用於面向過程的程式設計，又支持面向對象的程式設計，因此，作者在對算法進行描述時，儘量採用合適的程式設計方法。例如，對於基本的數據結構（如順序存儲與鏈式存儲的線性表、棧、佇列等）採用面向對象的方法，將數據與運算封裝成類，以便在其他應用程式中直接使用；而對於同一批數據進行同類操作的各種算法（如對線性表的各種排序方法）採用面向過程的方法，將各種不同的算法用普通函式來描述。這樣，書中的所有算法就可以直接在實際套用中使用。

作者簡介

徐士良，清華大學信息認知與智慧型系統研究所老師，已經退休。