數(shù)據(jù)結構是計算機類專業(yè)*基礎，也是*重要的課程之一，它和程序設計一起為計算學科其他后繼課程的學習奠定了基礎。 上海交通大學的“數(shù)據(jù)結構”課程是精品課程和精品資源共享課程，《數(shù)據(jù)結構：思想與實現(xiàn)（第2版）》是該課程的教學成果之一，被列入“十二五”普通高等教育本科國家級規(guī)劃教材。 《數(shù)據(jù)結構：思想與實現(xiàn)（第2版）》條理清晰，嚴格按照線性結構、樹狀結構、集合結構和圖狀結構的次序來組織。除常規(guī)的數(shù)據(jù)結構內(nèi)容之外，還介紹了一些高級的數(shù)據(jù)結構，如紅黑樹、AA樹和跳表等，并提供了大量的數(shù)據(jù)結構應用實例，讓讀者在學習數(shù)據(jù)結構的同時，逐步了解為什么要學數(shù)據(jù)結構以及數(shù)據(jù)結構對計算機類專業(yè)的重要性。 《數(shù)據(jù)結構：思想與實現(xiàn)（第2版）》內(nèi)容詳實，既注重數(shù)據(jù)結構和算法的原理，又十分強調(diào)和程序設計課程的銜接。在講授數(shù)據(jù)結構的同時，不斷加強學生對程序設計的理解。書中的算法都有完整的C++實現(xiàn)，這些程序結構清晰，構思精巧，且所有程序都在VC 6.0環(huán)境下編譯通過，并能正確運行。它們既是學習數(shù)據(jù)結構和算法的示例，也是學習C++程序設計很好的示例。 為便于讀者學習與理解，《數(shù)據(jù)結構：思想與實現(xiàn)（第2版）》為重點、難點內(nèi)容提供了教學視頻，讀者可通過掃描二維碼觀看。 《數(shù)據(jù)結構：思想與實現(xiàn)（第2版）》可作為高等學校計算機類專業(yè)“數(shù)據(jù)結構”課程的教材，也可供相關技術人員參考。
數(shù)據(jù)結構是計算機類專業(yè)最基礎，也是最重要的課程之一，它和程序設計一起為計算學科其他后繼課程的學習奠定了基礎。
數(shù)據(jù)結構和程序設計是關系非常密切的課程。在教學安排中，通常程序設計課程后接著就是數(shù)據(jù)結構課程。在學習數(shù)據(jù)結構時，學生往往對程序設計還不是很熟練。通常學生的難點不在于對數(shù)據(jù)結構的理解，而在于如何用特定的程序設計語言來實現(xiàn)這些數(shù)據(jù)結構，特別是如何按照面向對象的思想將一個個數(shù)據(jù)結構設計成一個個類。本書十分強調(diào)和程序設計課程的銜接，在講授數(shù)據(jù)結構的同時，不斷加強學生對程序設計的理解。書中的算法都有完整的C++程序實現(xiàn)，這些程序結構清晰，構思精巧，且都在VC6.0環(huán)境下編譯通過，并能正確運行。它們既是學習數(shù)據(jù)結構和算法的示例，也是學習C++程序設計很好的示例。
本書既適用于過程化方法講授，也適用于面向對象方法講授。除第1章外，其余各章的結構基本一致。每章介紹一個數(shù)據(jù)結構，首先介紹該數(shù)據(jù)結構所處理的邏輯結構及其常用操作。其次介紹該數(shù)據(jù)結構的各種實現(xiàn)方法，以及如何將其封裝成類。接著介紹C++中對應于該數(shù)據(jù)結構的工具，告訴讀者如何應用現(xiàn)有的工具。最后介紹該數(shù)據(jù)結構的應用，讓讀者進一步了解數(shù)據(jù)結構的重要性。
本書共16章，第1章引言介紹什么是數(shù)據(jù)結構，什么是算法；回顧面向對象的程序設計方法；還介紹了本書的使用方法。第2~16章被分為五大部分：線性結構、樹狀結構、集合結構、圖狀結構和算法設計基礎。其中，第2～5章為第1部分，主要討論線性結構，包括線性表、棧、隊列與字符串。第6、7章為第2部分，討論樹狀結構，包括樹和基于樹實現(xiàn)的優(yōu)先級隊列。第8-12章為第3部分，討論集合結構，這一部分是根據(jù)集合的查找和排序兩個基本操作組織的，包括集合與靜態(tài)查找表、動態(tài)查找表、排序、外部查找與排序，以及基于集合操作的、用于處理等價類的工具——不相交集。第13-15章為第4部分，討論圖狀結構，主要包括圖的基本概念、基本操作、實現(xiàn)方法、常見應用，以及圖中的兩個重要的操作——最小生成樹和最短路徑問題。最后一部分由第16章組成，介紹基本的算法設計方法，主要包括枚舉法、貪婪法、分治法、動態(tài)規(guī)劃和隨機算法，使讀者在遇到一些沒有現(xiàn)成算法的問題時知道如何著手解決問題。
本書內(nèi)容豐富，除介紹常規(guī)的數(shù)據(jù)結構內(nèi)容之外，還介紹了一些高級的數(shù)據(jù)結構，如紅黑樹、AA樹、并查集和跳表等，并提供了大量的數(shù)據(jù)結構應用實例。讓讀者在學習數(shù)據(jù)結構的同時，逐步了解學習數(shù)據(jù)結構課程的目的，以及該課程對計算機類專業(yè)的重要性。
本書第1版于2009年出版。在使用過程中編者收到了許多任課教師和學生的反饋信息，對本書提出了一些意見和建議。第2版就以下幾點做了較大的修改。
（1）進一步理順框架。
（2）從初學者的角度出發(fā)，盡量講得通俗，突出基礎，突出重點。
�。�3）增加重點、難點的教學視頻。讀者可通過掃描二維碼的方式進行在線學習。
相信修改以后的第2版會更加符合讀者的需求。但因作者水平有限，書中肯定還會存在很多不足之處，敬請讀者批評指正。
翁惠玉，博士，上海交通大學計算機系教授，從事計算機網(wǎng)絡和信息系統(tǒng)的研究，并長期承擔“程序設計”和“數(shù)據(jù)結構”課程的教學工作。主講上海交通大學致遠學院計算機科學班和電子信息與電氣工程學院大平臺的“程序設計”和“數(shù)據(jù)結構”課程。其中，“數(shù)據(jù)結構”課程于2008年被評為國家精品課程，2012年評為國家精品資源共享課程。主編《C++程序設計思想與方法》《C++程序設計題解與拓展》《深入淺出數(shù)據(jù)結構》《數(shù)據(jù)結構題解與拓展》等多本教材。
俞勇，上海交通大學教授，博士生導師。國家精品課程“數(shù)據(jù)結構”及上海市“程序設計類基礎課程教學團隊”主持人，主編教材或著作8部。先后主持教育部教育教學改革項目2項，獲國家和上海市教學成果獎9項、上海市教材獎2項。曾帶領學生在ACM國際大學生程序設計競賽中3次獲得世界總冠軍，獲杰出教練獎。從事信息檢索、語義Web、機器學習等領域的研究，曾主持國家自然科學基金、863項目10余項，并在各種學術期刊、會議上發(fā)表學術論文近300篇，譯著3冊。
曾獲國務院特殊津貼、全國模范教師、全國師德標兵、寶鋼教師特等獎、上海市五一勞動獎章、上海市教學名師、上海市模范教師、上海交通大學校長獎和*受學生歡迎教師等榮譽。
第1章 引言
1．1 算法與數(shù)據(jù)結構
1．1．1 數(shù)據(jù)的邏輯結構
1．1．2 數(shù)據(jù)結構的運算
1．2 存儲實現(xiàn)
1．3 算法分析
1．3．1 時間復雜度的概念
1．3．2 算法運算量的計算
1．3．3 漸進時間復雜度
1．3．4 時間復雜度的計算
1．3．5 算法的優(yōu)化
13．6 空間復雜度
1．4 面向對象方法
本書的結構和特點
總結
練習1
第1部分 線性結構
第2章 線性表
2．1 線性表的定義
2．2 線性表的順序實現(xiàn)
2．2．1 順序表的存儲實現(xiàn)
2．2．2 順序表的運算實現(xiàn)
2．2．3 順序實現(xiàn)的性能分析
2．2．4 順序表的簡單示例
2．3 線性表的鏈接實現(xiàn)
2．3．1 單鏈表
2．3．2 雙鏈表
2．3．3 循環(huán)鏈表
2．3．4 鏈表的性能分析
2．4 標準模板庫（STL）中的線性表
2．4．1 容器和迭代器的概念
2．4．2 STL中的線性表類
2．5 線性表的應用
2．5．1 大整數(shù)處理
2．5．2 多項式求和
2．5．3 約瑟夫環(huán)
2．5．4 動態(tài)內(nèi)存管理
總結
練習2
第3章 棧
3．1 棧的定義
3．2 棧的順序實現(xiàn)
3．2．1 順序棧的存儲實現(xiàn)
3．2．2 順序棧的運算實現(xiàn)
3．2．3 順序棧性能分析
3．2．4 順序棧的簡單示例
3．3 棧的鏈接實現(xiàn)
3．3．1 鏈接棧的存儲實現(xiàn)
3．3．2 鏈接棧的運算實現(xiàn)
3．3．3 鏈接棧的簡單示例
3．4 STL中的棧
3．5 棧的應用
3．5．1 遞歸消除
3．5．2 括號配對
3．5．3 簡單的計算器
總結
……
第2部分 樹狀結構
第3部分 集合結構
第4部分 圖狀結構
第5部分 算法設計基礎
《數(shù)據(jù)結構：思想與實現(xiàn)（第2版）》：
提高外存儲器中查找表的查找效率，最直接的方法就是減少磁盤訪問的次數(shù)。在查找樹中，訪問的次數(shù)與查找樹的高度成正比。在外存儲器中，每次訪問對應了一次磁盤訪問。因此，要減少磁盤訪問的次數(shù)必須降低查找樹的高度。解決方法非常簡單，只要樹的分支多一些，高度就能降下來。比如，一棵31個結點的完全二叉樹有5層，而一棵31個結點5叉樹只有3層。一棵M叉樹允許有M路分支，隨著分支數(shù)量的增加，樹的高度就會降低。因為一棵完全二叉樹的高度大約為log2N，而一棵完全M叉樹的高度約為logMN。
構造M叉查找樹的方法和構造二叉查找樹的方法很相似。在二叉查找樹中，每個結點保存一個鍵值來決定到左子樹還是右子樹中繼續(xù)操作，在M叉查找樹中每個結點需要保存M-1個鍵來判斷到哪個分支中繼續(xù)操作。為了保證這個策略在最壞的情況下也很有效，必須采取一些手段保證M叉查找樹的平衡。否則，像二叉樹一樣，它也可能會退化成一個鏈表。
……
書單推薦
