數(shù)據(jù)結(jié)構(gòu)與算法

前言

數(shù)據(jù)結(jié)構(gòu)與算法內(nèi)容豐富，包含了計(jì)算機(jī)科學(xué)與技術(shù)的許多重要方面。分析和解決問題的思路和方法新穎，技巧性強(qiáng)，對(duì)學(xué)生的計(jì)算機(jī)軟件素質(zhì)的培養(yǎng)作用明顯。培養(yǎng)和訓(xùn)練學(xué)生選用合適的數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)方法編寫質(zhì)量高、風(fēng)格好的應(yīng)用程序，并具備評(píng)價(jià)算法優(yōu)劣的能力至關(guān)重要。本書采用C++面向?qū)ο蟮挠^點(diǎn)介紹數(shù)據(jù)結(jié)構(gòu)與算法，并使用模板程序設(shè)計(jì)技術(shù)，與采用面向過程的傳統(tǒng)觀點(diǎn)相比優(yōu)勢(shì)較大，使所設(shè)計(jì)的程序更容易實(shí)現(xiàn)代碼重用，在提供通用性和靈活性的同時(shí)，又保證了效率。本書已將面向?qū)ο蟪绦蛟O(shè)計(jì)的思想融合到數(shù)據(jù)結(jié)構(gòu)與算法中，讀者通過學(xué)習(xí)可進(jìn)一步提高面向?qū)ο蟪绦蛟O(shè)計(jì)的能力。全書共分為11章。第1章是基礎(chǔ)知識(shí)，介紹了基本概念及其術(shù)語，抽象數(shù)據(jù)類型的實(shí)現(xiàn)，還討論算法的概念和算法分析的簡(jiǎn)單方法。作為預(yù)備知識(shí)，讀者應(yīng)具有一定的C++程序設(shè)計(jì)的基礎(chǔ)。但是為了降低讀者的門檻，本章還介紹了要用的C++的主要知識(shí)點(diǎn)，并介紹了實(shí)用程序軟件包。第2章引入線性表，詳細(xì)討論線性表的順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在討論鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，首先仿照傳統(tǒng)方法實(shí)現(xiàn)線性表，然后在此基礎(chǔ)之上，在鏈表結(jié)構(gòu)中保存當(dāng)前位置和元素個(gè)數(shù)。這樣，在難度增加不大的情況下提高算法效率，使學(xué)生逐步體會(huì)改進(jìn)算法的途徑與方法。第3章介紹了棧和隊(duì)列，討論了棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，用棧實(shí)現(xiàn)了表達(dá)式求值。通過學(xué)習(xí)能掌握各種棧和隊(duì)列的實(shí)現(xiàn)與使用方法，對(duì)后繼課程（如操作系統(tǒng)原理和編譯原理）的學(xué)習(xí)打下良好的基礎(chǔ)。本章還討論了優(yōu)先隊(duì)列，使隊(duì)列應(yīng)用更加廣泛。第4章介紹串，詳細(xì)討論了串的存儲(chǔ)結(jié)構(gòu)與模式匹配算法，為開發(fā)串應(yīng)用（如實(shí)現(xiàn)文本編輯軟件）軟件打下堅(jiān)實(shí)的基礎(chǔ)。第5章介紹數(shù)組和廣義表，詳細(xì)討論了數(shù)組，特殊矩陣，稀疏矩陣和廣義表的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)方法，首次提出了廣義表的使用空間表存儲(chǔ)結(jié)構(gòu)，并使用廣義表實(shí)現(xiàn)了m元多項(xiàng)式的表示。第6章介紹了樹結(jié)構(gòu)，討論了二叉樹、線索二叉樹、樹、森林及其哈夫曼樹的結(jié)構(gòu)及其實(shí)現(xiàn)，還應(yīng)用哈夫曼編碼實(shí)現(xiàn)了壓縮軟件。第7章介紹圖結(jié)構(gòu)，實(shí)現(xiàn)了圖的常用存儲(chǔ)結(jié)構(gòu)，并討論了圖的相關(guān)應(yīng)用，實(shí)現(xiàn)了相應(yīng)算法（如求最小生成樹的Prim算法與Kruskal算法，求最短路徑的Dijkstra算法與Floyd算法）。第8章介紹查找，討論了靜態(tài)查找表、動(dòng)態(tài)查找表與散列表，還討論了二叉排序樹、二叉平衡樹與B樹，并實(shí)現(xiàn)了所有算法。第9章介紹排序，以簡(jiǎn)潔方式實(shí)現(xiàn)各種排序算法，還測(cè)試了各種排序算法的實(shí)際運(yùn)行時(shí)間。第10章介紹了文件，討論了主存儲(chǔ)器和輔助存儲(chǔ)器，以及各種常用文件結(jié)構(gòu)，還特別介紹了在數(shù)據(jù)庫中經(jīng)常采用的VSAM文件，對(duì)讀者研究與學(xué)習(xí)數(shù)據(jù)庫有一定的幫助。第11章介紹了算法設(shè)計(jì)技術(shù)、分析技術(shù)與可計(jì)算問題，詳細(xì)討論了各種算法設(shè)計(jì)技術(shù)（如貪心算法、分治算法、回溯算法）的使用方法并實(shí)現(xiàn)了各種算法，對(duì)算法分析技術(shù)和可計(jì)算問題也進(jìn)行了深入淺出的討論。對(duì)讀者的算法設(shè)計(jì)和分析的理論和實(shí)踐都有極大的幫助。對(duì)于初學(xué)者，要完全獨(dú)立編寫數(shù)據(jù)結(jié)構(gòu)與算法的代碼是相當(dāng)困難的。因此，本書討論的數(shù)據(jù)結(jié)構(gòu)與算法都加以實(shí)現(xiàn)并進(jìn)行了嚴(yán)格測(cè)試，提供了完整的測(cè)試程序，讀者可參考這些測(cè)試程序編寫相關(guān)算法。但是，如果只會(huì)使用已有的數(shù)據(jù)結(jié)構(gòu)編寫簡(jiǎn)單的程序也不利于讀者對(duì)數(shù)據(jù)結(jié)構(gòu)與算法的深入理解，以及研究新數(shù)據(jù)結(jié)構(gòu)與算法的能力。因此，本書的習(xí)題不但包括了基本練習(xí)題，還包括了仿照書中數(shù)據(jù)結(jié)構(gòu)構(gòu)造新數(shù)據(jù)結(jié)構(gòu)的題目，或改造已有算法的題目，這樣使讀者具有構(gòu)造新結(jié)構(gòu)及改造或改進(jìn)算法的能力。本書各章還提供了實(shí)例研究，主要提供給那些精力充沛的學(xué)生深入學(xué)習(xí)與研究，這些實(shí)例包括對(duì)正文內(nèi)容的補(bǔ)充（例如第9.9.3小節(jié)中的用堆實(shí)現(xiàn)優(yōu)先隊(duì)列），讀者可能感興趣但感到無從下手的算法（例如第1.6.2小節(jié)中的計(jì)算任意位數(shù)的π) 、離散數(shù)學(xué)中學(xué)習(xí)的著名算法的實(shí)現(xiàn)（例如第7.7.1小節(jié)中的周游世界問題——哈密爾頓圈與第7.7.2小節(jié)中的一筆畫問題——?dú)W拉問題）以及應(yīng)用所學(xué)知識(shí)解決實(shí)際問題（例如第6.8.2小節(jié)中的Huffman壓縮算法）。通過讀者對(duì)實(shí)例研究的學(xué)習(xí)，可提高實(shí)際應(yīng)用數(shù)據(jù)結(jié)構(gòu)與算法的能力。當(dāng)然，這可能有一定的難度，但應(yīng)比讀者想象的更易學(xué)習(xí)與掌握?，F(xiàn)在，各校在開設(shè)“數(shù)據(jù)結(jié)構(gòu)與算法”課時(shí)都安排有上機(jī)實(shí)驗(yàn)課時(shí)，因此本書每章都安排有上機(jī)實(shí)驗(yàn)題，這些實(shí)驗(yàn)題不但包括讀者感興趣的實(shí)驗(yàn)（例如紙牌游戲—— “21點(diǎn)”) ，數(shù)據(jù)結(jié)構(gòu)與算法基本應(yīng)用的實(shí)驗(yàn)（例如編寫一個(gè)程序讀入一個(gè)字符串，統(tǒng)計(jì)字符串中出現(xiàn)的字符及次數(shù)，然后輸出結(jié)果，要求用一個(gè)二叉排序樹來保存處理結(jié)果，結(jié)點(diǎn)的數(shù)據(jù)元素由字符與出現(xiàn)次數(shù)組成，關(guān)鍵字為字符），對(duì)課本數(shù)據(jù)結(jié)構(gòu)與算法改進(jìn)的實(shí)驗(yàn)（例如改進(jìn)本書實(shí)現(xiàn)的求最小生成樹的Kruskal算法，用最大優(yōu)先隊(duì)列來實(shí)現(xiàn)按照邊的權(quán)值順序處理，用等價(jià)關(guān)系判斷兩個(gè)結(jié)點(diǎn)是否屬于同一棵自由樹以及合并自由樹），還包括了解決實(shí)際問題的實(shí)驗(yàn)（例如采用散列文件實(shí)現(xiàn)電話號(hào)碼查找系統(tǒng)），通過實(shí)驗(yàn)?zāi)軜O大地提高讀者對(duì)數(shù)據(jù)結(jié)構(gòu)與算法的應(yīng)用能力。為了進(jìn)一步提高讀者運(yùn)用數(shù)據(jù)結(jié)構(gòu)與算法的水平，現(xiàn)在很多學(xué)校還開設(shè)了“數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)”。為此，本書的附錄提供了11個(gè)課程設(shè)計(jì)項(xiàng)目，這些項(xiàng)目包括了接近實(shí)際課題的題目（例如開發(fā)排課軟件與公園導(dǎo)游系統(tǒng)）、容易引起讀者興趣的項(xiàng)目（例如理論計(jì)算機(jī)科學(xué)家族譜的文檔／視圖模式）與需要通過查找資料進(jìn)一步提高的題目（例如采用自適應(yīng)形式的哈夫曼編碼方案開發(fā)壓縮軟件）。課程設(shè)計(jì)項(xiàng)目一般都提供功能的擴(kuò)展方法，基礎(chǔ)較差的讀者可只實(shí)現(xiàn)基礎(chǔ)功能，對(duì)數(shù)據(jù)結(jié)構(gòu)與算法有興趣的讀者可實(shí)現(xiàn)更強(qiáng)的功能，這樣使不同層次的讀者都會(huì)有所收獲，通過做這些項(xiàng)目能快速提高讀者解決實(shí)際問題的能力。為了盡快提高讀者的學(xué)習(xí)能力，本書各章還提供了深入學(xué)習(xí)導(dǎo)讀，包含了本書作者實(shí)現(xiàn)相關(guān)數(shù)據(jù)結(jié)構(gòu)與算法的最原始思想的資料來源，也包括了進(jìn)一步學(xué)習(xí)的參考資料，極大地方便讀者與教師查閱資料。本教材在內(nèi)容組織上特別考慮了讀者的可接受性；在算法實(shí)現(xiàn)時(shí)，重點(diǎn)考慮了程序的可讀性，為實(shí)現(xiàn)更強(qiáng)的功能，一般采用啟發(fā)的方式在習(xí)題、上機(jī)實(shí)驗(yàn)或課程設(shè)計(jì)中實(shí)現(xiàn)，這樣容易培養(yǎng)起讀者的學(xué)習(xí)興趣，使讀者感到自己具有發(fā)展或改進(jìn)已有算法的能力，也會(huì)使讀者感到自己已達(dá)到計(jì)算機(jī)高手的自信心。本書作者都活躍在教學(xué)研究第一線上，同時(shí)有的作者還具有深厚的數(shù)學(xué)功底。因此，本書不但完成了所有算法的測(cè)試程序，對(duì)算法分析的相關(guān)公式進(jìn)行了嚴(yán)格的數(shù)學(xué)推理，還獨(dú)立地從數(shù)學(xué)上嚴(yán)格推出了一種產(chǎn)生泊松隨機(jī)數(shù)的算法（見附錄B) 。事實(shí)上，用同樣的方法可產(chǎn)生任何離散隨機(jī)分布（例如二項(xiàng)分布），本書作者還首次對(duì)本書中關(guān)于計(jì)算任意位數(shù)π的算法作了嚴(yán)格的理論推導(dǎo)。本書采用了模板程序設(shè)計(jì)技術(shù)，現(xiàn)在模板技術(shù)已成為現(xiàn)代C++語言的風(fēng)格基礎(chǔ)，C++98(1998年標(biāo)準(zhǔn)化的C++)提供的標(biāo)準(zhǔn)程序庫中有80%的成分是使用模板機(jī)制實(shí)現(xiàn)的STL(Standard Template Library，標(biāo)準(zhǔn)模板庫)。而國(guó)內(nèi)現(xiàn)階段教學(xué)并未重視C++的模板程序設(shè)計(jì)，書籍資料也不是很多。作者認(rèn)為在C++中，只要模仿本書算法，讀者會(huì)在不知不覺中掌握模板程序設(shè)計(jì)技巧?，F(xiàn)在來討論一下在國(guó)外“數(shù)據(jù)結(jié)構(gòu)與算法”課程上機(jī)教學(xué)時(shí)喜歡采用的STL。實(shí)際上，STL是AT&T貝爾實(shí)驗(yàn)室和HP研究實(shí)驗(yàn)室的研究人員將模板程序設(shè)計(jì)和面向?qū)ο蟪绦蛟O(shè)計(jì)的原理結(jié)合起來，創(chuàng)造的一套研究數(shù)據(jù)結(jié)構(gòu)與算法的一種統(tǒng)一的方法，現(xiàn)在已成為C++標(biāo)準(zhǔn)庫的一部分。STL提供了實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的新途徑，它將(數(shù)據(jù))結(jié)構(gòu)(即組織數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu))抽象為容器，將之分為3類：序列容器、關(guān)聯(lián)容器和適配器容器。通過使用模板和迭代器，STL使得程序員能夠?qū)V泛的通用算法應(yīng)用到各種容器類上。通過本書作者的研究與了解，STL只覆蓋了數(shù)據(jù)結(jié)構(gòu)中的線性結(jié)構(gòu)和樹結(jié)構(gòu)，并沒有覆蓋圖部分。因此，對(duì)數(shù)據(jù)結(jié)構(gòu)來講，STL并不完備。同時(shí)，如果讀者上機(jī)編程都只使用STL解決數(shù)據(jù)結(jié)構(gòu)的相關(guān)算法，可能使讀者在數(shù)據(jù)結(jié)構(gòu)編程方面，只會(huì)使用STL，而不能獨(dú)自設(shè)計(jì)新數(shù)據(jù)結(jié)構(gòu)。本書采用模板方法實(shí)現(xiàn)了書中所有的數(shù)據(jù)結(jié)構(gòu)算法，應(yīng)比STL更完備。同時(shí)，STL中包含的源代碼可讀性差，不適合作為教學(xué)使用，本書的算法源程序首要強(qiáng)調(diào)可讀性，使讀者容易接受與模仿，并且讀者可進(jìn)行改進(jìn)或修改算法實(shí)現(xiàn)。因此，在某種意義上講，本書提供的關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法實(shí)現(xiàn)的類模板與函數(shù)模板是一種GTL (General Template Library）或OSGTL (Open Source General Template Library) 。讀者也可由作者個(gè)人主頁提供的軟件包（具體內(nèi)容請(qǐng)參看附錄C）來進(jìn)行實(shí)際數(shù)據(jù)結(jié)構(gòu)與算法方面的軟件開發(fā)。當(dāng)然，通過本書的學(xué)習(xí)，再返回來學(xué)習(xí)STL的應(yīng)用，將會(huì)達(dá)到事半功倍的效果。讀者只要找一本介紹STL的書籍或上網(wǎng)找一些介紹使用STL的文檔，并用STL試著編程即可完全掌握STL的使用。現(xiàn)在談?wù)動(dòng)嘘P(guān)C++編譯器的問題，在C++之外的任何編程語言中，編譯器都沒有受到過如此重視。這是因?yàn)镃++是一門非常復(fù)雜的語言，以至于編譯器也難于構(gòu)造。我們常用的編譯器都不能完全符合C++標(biāo)準(zhǔn)，以至于本書的部分測(cè)試不得不使用條件編譯技術(shù)來適應(yīng)不同C++編譯器，下面介紹一些常用的優(yōu)秀C++編譯器。(1)  Visual C++編譯器：由微軟開發(fā)，現(xiàn)在主要流行Visual C++ 6.0、Visual C++ 2005以及Visual C++ 2005 Express，特點(diǎn)是集成開發(fā)環(huán)境用戶界面友好，信息提示準(zhǔn)確，調(diào)試方便，對(duì)模板支持最完善。Visual C++ 6.0對(duì)硬件環(huán)境要求低，現(xiàn)在安裝的計(jì)算機(jī)最多，但對(duì)標(biāo)準(zhǔn)C++兼容只有83.43%. Visual C++ 2005與Visual C++ 2005 Express在軟件提示信息上做了進(jìn)一步的優(yōu)化與改進(jìn)，并且對(duì)標(biāo)準(zhǔn)C++兼容達(dá)到了98%以上的程度，但對(duì)硬件的要求較高。同時(shí)，Visual C++ 2005 Express是一種輕量級(jí)的Visual C++軟件，易于使用。對(duì)于編程愛好者、學(xué)生和初學(xué)者來說，Visual C++ 2005 Express是很好的編程工具，微軟在2006年4月22日正式宣布 Visual Studio 2005 Express版永久免費(fèi)。(2)  GCC編譯器：著名的開源C++編譯器。是類UNIX操作系統(tǒng)（例如Linux）下編寫C++程序的首選，有非常好的可移植性，可以在非常廣泛的平臺(tái)上使用，也是編寫跨平臺(tái)、嵌入式程序很好的選擇。GCC 3.3與標(biāo)準(zhǔn)C++兼容大概能夠達(dá)到96.15%。現(xiàn)已有一些移植在Windows環(huán)境下使用GCC編譯器的IDE（集成開發(fā)環(huán)境），例如Dev-C++與MinGW Developer Studio。其中，Dev-C++是能夠讓GCC在Windows下運(yùn)行的集成開發(fā)環(huán)境，提供了與專業(yè)IDE相媲美的語法高亮、代碼提示、調(diào)試等功能；MinGW Developer Studio是跨平臺(tái)下的GCC集成開發(fā)環(huán)境，目前支持 Windows、Linux和 FreeBSD。根據(jù)作者的實(shí)際使用，感覺使用GCC編譯器的IDE錯(cuò)誤信息提示的智能較低，錯(cuò)誤提示信息不太準(zhǔn)確，還有就是對(duì)模板支持較差，對(duì)語法檢查較嚴(yán)格，在Visual C++編譯器中編譯通過的程序可能在GCC編譯器的IDE還會(huì)顯示有錯(cuò)誤信息。本書所有算法都同時(shí)在Visual C++ 6.0、Visual C++ 2005、Visual C++ 2005 Express、Dev-C++和MinGW Developer Studio中通過測(cè)試。讀者可根據(jù)實(shí)際情況選擇適當(dāng)?shù)木幾g器，建議選擇Visual C++ 2005.教師可采取多種方式來使用本書講授數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)與算法分析，數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)，數(shù)據(jù)結(jié)構(gòu)與算法等課程，應(yīng)該根據(jù)學(xué)生的背景知識(shí)以及課程的學(xué)時(shí)數(shù)來進(jìn)行內(nèi)容的取舍。為滿足不同層次的教學(xué)需求，本教材使用了分層的思想，分層方法如下：沒有加星號(hào)（）及雙星號(hào)（）的部分是基本內(nèi)容，適合所有讀者學(xué)習(xí)；加星號(hào)的部分適合計(jì)算機(jī)專業(yè)的讀者深入學(xué)習(xí)；加有雙星號(hào)的部分適合于感興趣的同學(xué)研究，尤其適合于那些有志于ACM競(jìng)賽的讀者加以深入研究。下面給出了幾種可能的課程安排，建議習(xí)題及實(shí)驗(yàn)的主要形式是讓學(xué)生編寫并調(diào)試一些程序。開始時(shí)程序可以比較短，隨著課程的深入，程序?qū)⒅饾u變大。學(xué)生應(yīng)根據(jù)課堂上所講授的主題同步閱讀課本相關(guān)內(nèi)容。學(xué) 分大約課時(shí)數(shù)內(nèi)  容232選講第1章~~第9章中沒有打星號(hào)（）及雙星號(hào)（）的內(nèi)容348第1章~~第10章中沒有打星號(hào)（）及雙星號(hào)（）的內(nèi)容464第1章~~第11章中沒有打星號(hào)（）及雙星號(hào)（）的內(nèi)容580第1章~~第11章中沒有打星號(hào)（）及雙星號(hào)（）的內(nèi)容，選講部分打有星號(hào)（）的內(nèi)容696第1章~~第11章中沒有打雙星號(hào)（）的內(nèi)容，選講部分打有雙星號(hào)（）的內(nèi)容  作者為本書提供了全面的教學(xué)支持，如果在教學(xué)或?qū)W習(xí)過程中發(fā)現(xiàn)與本書有關(guān)的任何問題都可以與作者聯(lián)系作者將盡力滿足讀者的要求，并可能將解答公布在作者的教學(xué)網(wǎng)站上。另外，在作者的教學(xué)網(wǎng)站上還將提供如下內(nèi)容。(1)  提供書中所有算法在Visual C++ 6.0、Visual C++ 2005、Visual C++ 2005 Express、Dev-C++和MinGW Developer Studio開發(fā)環(huán)境中的測(cè)試程序，今后還會(huì)提供當(dāng)時(shí)流行的C++開發(fā)環(huán)境的測(cè)試程序，每種開發(fā)環(huán)境還將提供基本開發(fā)過程的文檔；還提供本書作者開發(fā)的軟件包（包含所有本書所講的數(shù)據(jù)結(jié)構(gòu)與算法的類模板與函數(shù)模板）。2)  提供教學(xué)用PowerPoint幻燈片PPT課件。(3)  向教師提供所有習(xí)題、上機(jī)實(shí)驗(yàn)題與課程設(shè)計(jì)項(xiàng)目的解答或參考程序，對(duì)學(xué)生來講，將在每學(xué)期期末（第15周~~第20周）公布解壓密碼。(4)  數(shù)據(jù)結(jié)構(gòu)與算法問答專欄。(5)  提供至少8套數(shù)據(jù)結(jié)構(gòu)與算法模擬試題及其解答，以供學(xué)生期末及其考研復(fù)習(xí)，也可供教師出考題時(shí)參考。(6)  提供數(shù)據(jù)結(jié)構(gòu)與算法相關(guān)的其他資料（例如作者收集的計(jì)算任何位數(shù)π的資料，Dev-C++與MinGW Developer Studio軟件，流行免費(fèi)C++編譯器的下載網(wǎng)址）。希望各位讀者能夠抽出寶貴的時(shí)間將建議或意見（當(dāng)然也可以發(fā)表對(duì)國(guó)內(nèi)外“數(shù)據(jù)結(jié)構(gòu)與算法”課程教學(xué)的任何意見）寄給作者，為我們修訂教材提供重要參考。孫界平、張衛(wèi)華、鄒昌文、王文昌、周焯華、胡開文、沈潔、周德華與歐陽等人對(duì)本書做了大量的工作，包括提供資料，調(diào)試算法，以及參與部分章節(jié)的編寫；作者還要感謝為本書提供直接或間接幫助的每一位朋友，由于他們熱情的幫助與鼓勵(lì)，激發(fā)了寫好本書的信心以及熱情。在此還要感謝清華大學(xué)出版社的編輯及評(píng)審專家，他們?yōu)楸緯某霭鎯A注了大量熱情。正是由于他們具有前瞻性的眼光才讓讀者有機(jī)會(huì)看到本書。盡管作者秉著負(fù)責(zé)任的態(tài)度編寫這本書，并盡了最大努力，但由于水平有限，書中難免有不妥之處，因此，敬請(qǐng)各位讀者不吝賜教，以便作者不斷提高，提高寫作水平。

內(nèi)容概要

本書結(jié)合C++面向?qū)ο蟪绦蛟O(shè)計(jì)的特點(diǎn)，構(gòu)建了數(shù)據(jù)結(jié)構(gòu)與算法，對(duì)所有算法都在Visual C++ 6.0、Visual C++ 2005、Visual C++ 2005 Express、Dev-C++和MinGW Developer Studio開發(fā)環(huán)境中進(jìn)行了嚴(yán)格的測(cè)試，作者教學(xué)網(wǎng)站（http://cs.scu.edu.cn/~youhongyue）提供了大量的教學(xué)支持內(nèi)容。同時(shí)本書配有《數(shù)據(jù)結(jié)構(gòu)與算法（C++版）實(shí)驗(yàn)和課程設(shè)計(jì)教程》 (ISBN 978-7-302-17503-2）供讀者學(xué)習(xí)參考?！　”緯卜?1章，第1章是基礎(chǔ)知識(shí)，介紹了基本概念及其術(shù)語，并討論了實(shí)用程序軟件包；第2章引入線性表；第3章介紹了棧和隊(duì)列，用棧實(shí)現(xiàn)了表達(dá)式求值；第4章介紹串，詳細(xì)討論了串的存儲(chǔ)結(jié)構(gòu)與模式匹配算法；第5章介紹數(shù)組和廣義表，首次提出了廣義表的使用空間表存儲(chǔ)結(jié)構(gòu)；第6章介紹了樹結(jié)構(gòu)，應(yīng)用哈夫曼編碼實(shí)現(xiàn)了壓縮軟件；第7章介紹圖結(jié)構(gòu)，實(shí)現(xiàn)了圖的常用存結(jié)構(gòu)，討論了圖的相關(guān)應(yīng)用，并實(shí)現(xiàn)了相應(yīng)算法；第8章介紹查找，討論了靜態(tài)查找表、動(dòng)態(tài)查找表與散列表，實(shí)現(xiàn)了所有算法；第9章介紹排序，以簡(jiǎn)潔方式實(shí)現(xiàn)各種排序算法；第10章介紹了文件，討論了各種常用文件結(jié)構(gòu)；第11章介紹了算法設(shè)計(jì)技術(shù)、分析技術(shù)與可計(jì)算問題?！　⊥ㄟ^本書的學(xué)習(xí)，不但能迅速提高數(shù)據(jù)結(jié)構(gòu)與算法的水平，同時(shí)還能提高C++程序設(shè)計(jì)的能力，經(jīng)過適當(dāng)?shù)倪x擇，本書能作為高等院校計(jì)算機(jī)及相關(guān)專業(yè)“數(shù)據(jù)結(jié)構(gòu)”、“數(shù)據(jù)結(jié)構(gòu)與算法”、“數(shù)據(jù)結(jié)構(gòu)與算法分析”和“數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)”等課程的教材，也可供其他從事軟件開發(fā)工作的讀者參考。

書籍目錄

第1章 緒論　1.1 數(shù)據(jù)結(jié)構(gòu)的概念和學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的必要性　1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念　1.3 抽象數(shù)據(jù)類型及其實(shí)現(xiàn)　1.4 算法和算法分析?1.5 實(shí)用程序軟件包　1.6 實(shí)例研究　1.7 深入學(xué)習(xí)導(dǎo)讀　習(xí)題1　上機(jī)實(shí)驗(yàn)題1第2章 線性表　2.1 線性表的邏輯結(jié)構(gòu)　2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)　2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)　2.4 實(shí)例研究　2.5 深入學(xué)習(xí)導(dǎo)讀　習(xí)題2　上機(jī)實(shí)驗(yàn)題2第3章 棧和隊(duì)列　3.1 棧　3.2 隊(duì)列?3.3 優(yōu)先隊(duì)列　3.4 實(shí)例研究　3.5 深入學(xué)習(xí)導(dǎo)讀　習(xí)題3　上機(jī)實(shí)驗(yàn)題3第4章 串　4.1 串類型的定義　4.2 字符串的實(shí)現(xiàn)　4.3 字符串模式匹配算法?4.4 實(shí)例研究　4.5 深入學(xué)習(xí)導(dǎo)讀　習(xí)題4　上機(jī)實(shí)驗(yàn)題4第5章 數(shù)組和廣義表第6章 樹和二叉樹第7章 圖第8章 查找第9章 排序第10章 文件第11章 算法設(shè)計(jì)與分析附錄A 調(diào)和級(jí)數(shù)附錄B 泊松分布附錄C 配套的軟件包附錄D 課程設(shè)計(jì)項(xiàng)目附錄E 實(shí)驗(yàn)報(bào)告格式附錄F 課程設(shè)計(jì)報(bào)告格式參考文獻(xiàn)

章節(jié)摘錄

可能有人認(rèn)為，隨著計(jì)算機(jī)的功能越來越強(qiáng)大和運(yùn)行速度越來越快，程序運(yùn)行效率已變得越來越不重要了。然而，計(jì)算機(jī)功能越強(qiáng)大，人們就越要嘗試解決更加復(fù)雜的問題，而更復(fù)雜的問題需要更大的計(jì)算量，這使得對(duì)程序的運(yùn)行效率有更高的要求，工作越復(fù)雜越偏離人們的日常經(jīng)驗(yàn)，使得從事軟件開發(fā)的人必須學(xué)習(xí)和具備徹底理解隱藏在程序設(shè)計(jì)后面的一般原理——數(shù)據(jù)結(jié)構(gòu)和算法。從本質(zhì)上講，數(shù)據(jù)結(jié)構(gòu)與算法的原理和方法獨(dú)立于具體描述語言，然而只能使用具體的某種計(jì)算機(jī)語言才能在計(jì)算機(jī)上實(shí)現(xiàn)。本書采用目前普遍使用的C++程序設(shè)計(jì)語言來描述各種數(shù)據(jù)結(jié)構(gòu)與算法，假設(shè)讀者具有程序設(shè)計(jì)基礎(chǔ)，了解C++的基本結(jié)構(gòu)和語法。為了、使讀者更好理解，本章將對(duì)C++的基本結(jié)構(gòu)和語法進(jìn)行介紹。1.1 數(shù)據(jù)結(jié)構(gòu)的概念和學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的必要性對(duì)于數(shù)值計(jì)算問題的解決方法，主要是用數(shù)學(xué)方程建立數(shù)學(xué)模型，例如天氣預(yù)報(bào)的數(shù)學(xué)模型為二階橢圓偏微分方程；預(yù)測(cè)人口增長(zhǎng)的數(shù)學(xué)模型為常微分方程。求解這些數(shù)學(xué)模型的方法是計(jì)算數(shù)學(xué)研究的范疇，例如采用差分算法、有限元算法和無限元算法等。對(duì)于非數(shù)值計(jì)算問題，主要采用數(shù)據(jù)結(jié)構(gòu)的方法建立數(shù)學(xué)模型，下面通過實(shí)例加以說明。

編輯推薦

通過《數(shù)據(jù)結(jié)構(gòu)與算法(C++版)》的學(xué)習(xí)，不但能迅速提高數(shù)據(jù)結(jié)構(gòu)與算法的水平，同時(shí)還能提高C++程序設(shè)計(jì)的能力，經(jīng)過適當(dāng)?shù)倪x擇，《數(shù)據(jù)結(jié)構(gòu)與算法(C++版)》能作為高等院校計(jì)算機(jī)及相關(guān)專業(yè)“數(shù)據(jù)結(jié)構(gòu)”、“數(shù)據(jù)結(jié)構(gòu)與算法”、“數(shù)據(jù)結(jié)構(gòu)與算法分析”和“數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)”等課程的教材，也可供其他從事軟件開發(fā)工作的讀者參考。

圖書封面

評(píng)論、評(píng)分、閱讀與下載

---

    數(shù)據(jù)結(jié)構(gòu)與算法 PDF格式下載

---