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