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