基本介紹
- 書名：數據結構基礎(C語言版)
- 作者：（美國）(EllisHorowitz)霍羅維茲 （美國）(SusanAnderson-Freed)安德爾森-費里德
- ISBN：9787302186960
- 定價：49.00 元
- 出版社：清華大學出版社
- 出版時間：2009年
- 開本：16開
內容簡介,作者簡介,目錄,
內容簡介
《數據結構基礎（C語言版）第2版》是最經典數據結構教材的最新版本，國內外大多數的同類教材都是以《數據結構基礎（C語言版）第2版》為藍本編寫而來的。《數據結構基礎（C語言版）第2版》用C作為描述語言，全面而生動地介紹了數據結構的有關知識，如數組、棧、佇列、鍊表、樹和圖，以及構成所有軟體基礎的排序散列技術。此外，《數據結構基礎（C語言版）第2版》還介紹了各種高級或特殊數據結構，如優先權佇列、高效二叉查找樹、多路查找樹等。《數據結構基礎（C語言版）第2版》對大多數算法都給出了計算時間在最優、最差情形下的複雜度分析。《數據結構基礎（C語言版）第2版》不僅可以作為計算機及相關專業本科生“數據結構”課程的教材，也可以作為研究生第一學年的“高等數據結構”課程的教材，同時，《數據結構基礎（C語言版）第2版》所介紹的各種算法的C語言實現，對有關專業人員也具有很好的參考價值。
作者簡介
Ellis Horowitz是南加州大學計算機與電子工程系的教授。Horowitz博士已編著了10多本教材，並發表了大量學術論文。
SartajSahni是佛羅里達大學計算機與信息科學系的傑出教授和講座教授。Sahni博士已發表300多篇學術研究論文，編著了15本教材。
SusanAnderson-Freed是伊利諾伊衛斯理大學計算機教授。她的研究領域是資料庫管理系統、Web設計與開發。她畢業於諾伯特大學，並在印第安納大學獲得碩士和博士學位，以及在Bradley大學獲得計算機理學地碩士學位。她從1977年起就供職於伊利諾伊衛斯理大學。
目錄
第1章基本概念
§1.1概觀：系統生命周期
§1.2指針和動態存儲分配
§1.2.1指針
§1.2.2動態存儲分配
§1.2.3指針隱患
§1.3算法形式規範
§1.3.1綜論
§1.3.2遞歸算法
§1.4數據抽象
§1.5性能分析
§1.5.1空間複雜度
§1.5.2時間複雜度
§1.5.3漸近記號(O，Q，)
§1.5.4實際複雜度
§1.6性能度量
§1.6.1定時
§1.6.2生成測試數據
§1.7參考文獻和選讀材料
第2章數組和結構
§2.1數組
§2.1.1數組的抽象數據類型
§2.1.2c語言的數組
§2.2數組的動態存儲分配
§2.2.1一維數組
§2.2.2二維數組
§2.3結構體和聯合體
§2.3.1結構體
§2.3.2聯合體
§2.3.3結構的內部實現
§2.3.4自引用結構
§2.4多項式
§2.4.1多項式的抽象數據類型
§2.4.2多項式的表示
§2.4.3多項式加法
§2.5稀疏矩陣
§2.5.1稀疏矩陣的抽象數據類型
§2.5.2稀疏矩陣的表示
§2.5.3矩陣轉置
§2.5.4矩陣相乘
§2.6多維數組的表示
§2.7字元串
§2.7.1字元串的抽象數據類型
§2.7.2C語言的字元串
§2.7.3模式匹配
§2.8參考文獻和選讀材料
§2.9補充習題
第3章棧與佇列
§3.1棧
§3.2動態棧
§3.3佇列
§3.4動態循環佇列
§3.5迷宮問題
§3.6表達式求值
§3.6.1表達式
§3.6.2後綴表達式求值
§3.6.3中綴表達式轉換成後綴表達式
§3.7多重棧與多重佇列
§3.8補充習題
第4章鍊表
§4.1單向鍊表
§4.2用C語言表示單向鍊表
§4.3鏈式棧與鏈式佇列
§4.4多項式
§4.4.1多項式表示
§4.4.2多項式加法
§4.4.3銷毀多項式
§4.4.4循環鍊表與多項式
§4.4.5小結
§4.5其它鍊表操作
§4.5.1單向鍊表操作
§4.5.2循環鍊表操作
§4.6等價類
§4.7稀疏矩陣
§4.7.1稀疏矩陣表示
§4.7.2輸入稀疏矩陣
§4.7.3輸出稀疏矩陣
§4.7.4銷毀稀疏矩陣
§4.8雙向鍊表
第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.3.3後序遍歷
§5.3.4非遞歸(循環)中序遍歷
§5.3.5層序遍歷
§5.3.6不設棧遍歷二叉樹
§5.4其它二叉樹操作
§5.4.1複製二叉樹
§5.4.2判斷兩個二叉樹全等
§5.4.3可滿足性問題
§5.5線索二叉樹
§5.5.1線索
§5.5.2中序遍歷線索二叉樹
§5.5.3線索二叉樹插入結點
§5.6堆
§5.6.1優先權佇列
§5.6.2大根堆定義
§5.6.3大根堆插入操作
§5.6.4大根堆刪除操作
§5.7二叉查找樹
§5.7.1定義
§5.7.2二叉查找樹的查找
§5.7.3二叉查找樹的插入
§5.7.4二叉查找樹的刪除
§5.7.5二叉查找樹的合併與分裂
§5.7.6二叉查找樹的高度
§5.8選拔樹
§5.8.1引子
§5.8.2優勝樹
§5.8.3淘汰樹
§5.9森林
§5.9.1森林轉換為二叉樹
§5.9.2遍歷森林
§5.10不相交集合的表示
§5.10.1引子
§5.10.2合併與查找操作
§5.10.3劃分等價類
§5.11二叉樹的計數
§5.11.1不同態二叉樹
§5.11.2棧置換
§5.11.3矩陣乘法
§5.11.4不同二叉樹的數目
§5.12參考文獻和選讀材料
第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.2.5重連通分量
§6.3最小代價生成樹
§6.3.1Kruskal算法
§6.3.2Prim算法
§6.3.3SoUin算法
§6.4最短路徑和遷移閉包
§6.4.1單源點至所有其它節點：邊權值非負
§6.4.2單源點至所有其它節點：邊權值正負無限制
……
第7章排序
第8章Hash法
第9章優先權佇列
第10章高效二叉查找樹
第11章多路查找樹
第12章數字查找結構
索引
……
1.1 概觀：系統生命周期
本書讀者應具備紮實的結構化程式設計技能。要獲得這些技能，讀者通常應學過程式設計基礎一類課程。這類課程的培養目標就是傳授結構化程式設計技能，但課程強調的是語言本身的語法形式與語句使用規則，學生在這個階段通常只能編寫很簡單的程式，解決的問題不用說也是很簡單的。這類簡單問題，一般而言，只要直接選用程式設計語言提供的某語句也許就能完成求解，例如，用數組存儲數據，再利用while循環語句，可能就足以解決這一階段的許多問題了。
本書要指導讀者向前邁一大步，大幅度提高編程能力，因為以後編寫的程式，其規模要大很多，功能也要複雜得多。不用說，編寫規模龐大而複雜的程式，不但需要更強有力的工具，還一定需要更高級的編程技術。我們希望在隨後的學習過程，讀者應紮實掌握數據的抽象思維方法，同時必須熟練掌握算法的規範聲明、算法的性能分析、算法的性能評價等諸多技能。設定本章的目的就是要詳細論述這些內容。此外，遞歸程式設計方法同樣至關重要，讀者也必須熟練掌握，因此也是本章討論的內容，但論述得較為簡明而且篇幅不很大。我們提請讀者注意，如果讀者以前對遞歸程式設計基礎未給予足夠重視，了解流於膚淺，那么必須仔細研讀這方面內容，以後一定會深感大有益處。然而，在討論各種工具與各項技術之前，我們必須強凋，編程可不僅僅是寫程式代碼，即寫完一條條程式語句就萬事大吉了。與之截然相反，優秀的程式設計師有完全不同的觀點。程式設計的首要問題，應該是首先把大規模程式系統分解成許許多多自成體系且相對獨立的組成部件，然後再為各部分之間存在的相互調用，定義嚴格的調用格式。
本書讀者應具備紮實的結構化程式設計技能。要獲得這些技能，讀者通常應學過程式設計基礎一類課程。這類課程的培養目標就是傳授結構化程式設計技能，但課程強調的是語言本身的語法形式與語句使用規則，學生在這個階段通常只能編寫很簡單的程式，解決的問題不用說也是很簡單的。這類簡單問題，一般而言，只要直接選用程式設計語言提供的某語句也許就能完成求解，例如，用數組存儲數據，再利用while循環語句，可能就足以解決這一階段的許多問題了。
本書要指導讀者向前邁一大步，大幅度提高編程能力，因為以後編寫的程式，其規模要大很多，功能也要複雜得多。不用說，編寫規模龐大而複雜的程式，不但需要更強有力的工具，還一定需要更高級的編程技術。我們希望在隨後的學習過程，讀者應紮實掌握數據的抽象思維方法，同時必須熟練掌握算法的規範聲明、算法的性能分析、算法的性能評價等諸多技能。設定本章的目的就是要詳細論述這些內容。此外，遞歸程式設計方法同樣至關重要，讀者也必須熟練掌握，因此也是本章討論的內容，但論述得較為簡明而且篇幅不很大。我們提請讀者注意，如果讀者以前對遞歸程式設計基礎未給予足夠重視，了解流於膚淺，那么必須仔細研讀這方面內容，以後一定會深感大有益處。然而，在討論各種工具與各項技術之前，我們必須強凋，編程可不僅僅是寫程式代碼，即寫完一條條程式語句就萬事大吉了。與之截然相反，優秀的程式設計師有完全不同的觀點。程式設計的首要問題，應該是首先把大規模程式系統分解成許許多多自成體系且相對獨立的組成部件，然後再為各部分之間存在的相互調用，定義嚴格的調用格式。
