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

前言

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

內(nèi)容概要

本書(shū)結(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開(kāi)發(fā)環(huán)境中進(jìn)行了嚴(yán)格的測(cè)試，作者教學(xué)網(wǎng)站（http://cs.scu.edu.cn/~youhongyue）提供了大量的教學(xué)支持內(nèi)容。同時(shí)本書(shū)配有《數(shù)據(jù)結(jié)構(gòu)與算法（C++版）實(shí)驗(yàn)和課程設(shè)計(jì)教程》 (ISBN 978-7-302-17503-2）供讀者學(xué)習(xí)參考?！　”緯?shū)共分11章，第1章是基礎(chǔ)知識(shí)，介紹了基本概念及其術(shù)語(yǔ)，并討論了實(shí)用程序軟件包；第2章引入線性表；第3章介紹了棧和隊(duì)列，用棧實(shí)現(xiàn)了表達(dá)式求值；第4章介紹串，詳細(xì)討論了串的存儲(chǔ)結(jié)構(gòu)與模式匹配算法；第5章介紹數(shù)組和廣義表，首次提出了廣義表的使用空間表存儲(chǔ)結(jié)構(gòu)；第6章介紹了樹(shù)結(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ì)算問(wèn)題。　　通過(guò)本書(shū)的學(xué)習(xí)，不但能迅速提高數(shù)據(jù)結(jié)構(gòu)與算法的水平，同時(shí)還能提高C++程序設(shè)計(jì)的能力，經(jīng)過(guò)適當(dāng)?shù)倪x擇，本書(shū)能作為高等院校計(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ì)”等課程的教材，也可供其他從事軟件開(kāi)發(fā)工作的讀者參考。

書(shū)籍目錄

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

編輯推薦

通過(guò)《數(shù)據(jù)結(jié)構(gòu)與算法(C++版)》的學(xué)習(xí)，不但能迅速提高數(shù)據(jù)結(jié)構(gòu)與算法的水平，同時(shí)還能提高C++程序設(shè)計(jì)的能力，經(jīng)過(guò)適當(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ì)”等課程的教材，也可供其他從事軟件開(kāi)發(fā)工作的讀者參考。

圖書(shū)封面

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

---

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

---