新編數據結構案例教程：C/C++語言（簡體書）

本書在主要介紹數據的邏輯結構、數據的存儲結構、數據的運算等基本知識的基礎上,從抽象數據類型的角度,討論各種基本類型的數據結構及相關應用。
全書共分5篇： 第1篇(第1章)為緒論篇,著重介紹數據結構的相關概念和算法的基礎知識；第2篇(第2～5章)為線性結構篇,著重討論線性結構的概念和基本運算的算法實現,介紹了一般的線性結構和特殊的線性結構在不同存儲結構之下的基本操作和應用； 第3篇(第6章)為樹形結構篇,著重介紹基本的樹形結構――二叉樹在不同存儲結構之下如何實現基本操作和應用； 第4篇(第7章)為圖形結構篇,介紹圖形結構在不同存儲結構之下的基本操作和應用； 第5篇(第8～10章)為數據運算篇,首先介紹數據的查找和排序基本運算的算法實現,接著介紹常見的查找和排序方法,分析並對比它們的算法效率，最後介紹數據結構的基礎知識在程序設計競賽中的應用。全書提供了大量應用實例,每種算法都採用C/C++語言進行描述,幫助讀者理解基礎理論。
本書敘述清楚，便於教學和讀者自學,適合作為高等院校計算機專業及信息相關專業的教材,也可作為計算機應用技術人員的參考書。

目錄


第1篇緒論篇




第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算法及其性能分析




1．3．1算法




1．3．2算法設計的目標




1．3．3算法的時間複雜度度量




1．3．4算法的空間複雜度度量




1．4STL概述




1．4．1STL的發展和特點




1．4．2C++標準庫和STL




1．4．3數據結構和STL的關係




1．5綜合案例




1．5．1哥德巴赫猜想問題




1．5．2連續整數問題




本章小結




第2篇線性結構篇




第2章線性表




2．1線性表的抽象數據類型




2．1．1線性表的定義




2．1．2線性表的抽象數據類型描述




2．2線性表的順序存儲結構




2．2．1線性表的順序存儲結構――順序表




2．2．2順序表基本運算的實現




2．3線性表的鏈式存儲結構




2．3．1線性表的鏈式存儲結構――鏈表




2．3．2單鏈表基本運算的實現




2．3．3雙鏈表




2．3．4循環鏈表




2．3．5STL與鏈表




2．4綜合案例




2．4．1一元多項式的表示及相加運算




2．4．2魔法師發牌問題




2．4．3約瑟夫問題




本章小結




第3章棧與隊列




3．1棧




3．1．1棧的概述




3．1．2棧的順序存儲結構




3．1．3棧的鏈式存儲結構




3．2棧綜合案例




3．2．1進制轉換




3．2．2表達式求值




3．2．3檢驗表達式中的括號匹配情況




3．2．4棧與遞歸問題




3．3隊列




3．3．1隊列的定義和抽象數據類型




3．3．2隊列的順序存儲




3．3．3隊列的鏈式存儲




3．3．4優先級隊列




3．4STL中的棧與隊列




3．4．1STL中的棧




3．4．2STL中的隊列




3．4．3STL中的優先隊列的使用方法




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串的KMP算法




4．4綜合案例




4．4．1文本編輯




4．4．2建立詞索引表




本章小結




第5章數組和廣義表




5．1數組的定義及抽象數據類型




5．1．1數組的定義




5．1．2數組的抽象數據類型




5．2數組的順序存儲與尋址




5．2．1以行序為主序




5．2．2以列序為主序




5．3特殊矩陣及其壓縮存儲




5．3．1對稱矩陣




5．3．2下(上)三角矩陣




5．3．3對角矩陣




5．4稀疏矩陣




5．4．1稀疏矩陣的三元組表示




5．4．2稀疏矩陣的十字鏈表表示




5．5廣義表




5．5．1廣義表的定義




5．5．2廣義表的存儲結構




5．5．3廣義表的運算




5．6綜合案例




5．6．1大整數相乘




5．6．2荷蘭國旗問題




本章小結




第3篇樹形結構篇




第6章樹和二叉樹




6．1樹




6．1．1樹的定義




6．1．2樹的術語




6．1．3樹的基本性質




6．1．4樹的抽象數據類型




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．3．4層次遍歷




6．3．5二叉樹遍歷的應用




6．3．6二叉樹遍歷的非遞歸實現




6．4線索二叉樹




6．4．1線索二叉樹的概念




6．4．2線索化二叉樹




6．4．3遍歷線索二叉樹




6．5樹與森林




6．5．1樹的存儲結構




6．5．2森林與二叉樹的轉換




6．5．3樹的遍歷與森林的遍歷




6．6哈夫曼樹及其應用




6．6．1哈夫曼樹的基本概念




6．6．2哈夫曼樹構造算法




6．6．3哈夫曼編碼




6．7STL中實現樹結構




6．7．1STL中的vector




6．7．2STL中的map




6．8綜合案例――學校建模問題




本章小結




第4篇圖形結構篇




第7章圖




7．1圖的概念




7．1．1圖的定義和術語




7．1．2圖的抽象數據類型




7．2圖的存儲表示




7．2．1鄰接矩陣




7．2．2鄰接表




7．2．3十字鏈表




7．3圖的遍歷與連通性




7．3．1深度優先遍歷




7．3．2廣度優先遍歷




7．3．3連通分量




7．4最小生成樹




7．4．1普裡姆算法




7．4．2克魯斯卡爾算法




7．5最短路徑




7．5．1單源最短路徑




7．5．2全源最短路徑




7．6活動網絡




7．6．1用頂點表示活動的AOV網絡




7．6．2AOE圖與關鍵路徑




7．7綜合案例




7．7．1道路修建問題




7．7．2回家路線問題




7．7．3棍子還原問題




本章小結




第5篇數據運算篇




第8章查找




8．1查找的基本概念




8．2靜態表的查找




8．2．1順序查找




8．2．2折半查找




8．2．3斐波那契查找




8．2．4分塊查找




8．3動態查找表




8．3．1二叉排序樹




8．3．2平衡二叉樹




8．3．3B-樹




8．3．4B+樹




8．4哈希表查找




8．4．1哈希表的基本概念




8．4．2哈希函數構造方法




8．4．3哈希衝突解決方法




8．4．4哈希表上的查找分析




8．5STL中的查找




8．6綜合案例――拼寫檢查問題




本章小結




第9章排序




9.1排序的基本概念




9.2插入排序




9.2.1直接插入排序




9.2.2希爾排序




9.3交換排序




9.3.1冒泡排序




9.3.2快速排序




9.4選擇排序




9.4.1簡單選擇排序




9.4.2錦標賽排序




9.4.3堆排序




9.5二路歸併排序




9.6基數排序




9.7內部排序方法的比較




9.8STL中的排序




9.9綜合案例――比賽排名問題




本章小結




第10章ACM經典案例




10.1遞歸算法




10.1.1三柱漢諾塔問題




10.1.2傳染病問題




10.1.3N皇后問題




10.2DFS與BFS問題




10.2.1DFS之迷宮難題




10.2.2BFS之管道和指針遊戲




本章小結




附錄A全國計算機專業數據結構考研大綱




參考文獻