數(shù)據(jù)結(jié)構(gòu)與算法實驗實踐教程

內(nèi)容概要

　　《高等院校計算機(jī)實驗與實踐系列示范教材：數(shù)據(jù)結(jié)構(gòu)與算法實驗實踐教程》共9章，內(nèi)容包括程序測試與運行時間度量、線性表和串的實現(xiàn)及其應(yīng)用、棧與隊列的實現(xiàn)和應(yīng)用、遞歸、二叉樹的實現(xiàn)和應(yīng)用、查找的實現(xiàn)與應(yīng)用、排序的實現(xiàn)與應(yīng)用、圖算法及其應(yīng)用和標(biāo)準(zhǔn)模板庫STL簡介。每章針對常用的數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計了例題和習(xí)題，部分習(xí)題在書后附有參考答案。

書籍目錄

第1章程序測試與運行時間度量 1.1程序的規(guī)格說明與測試 1.1.1程序的規(guī)格說明 1.1.2編程練習(xí)：排序函數(shù)的規(guī)格說明 1.1.3程序測試 1.1.4編程練習(xí)：排序的測試 1.1.5隨機(jī)數(shù)的生成 1.1.6自動化測試 1.1.7編程練習(xí)：排序的自動測試 1.2程序的運行時間度量 1.2.1 取得CPU時間 1.2.2統(tǒng)計排序函數(shù)的運行時間 1.2.3編程練習(xí)：排序的運行時間度量 1.2.4理解算法的時間復(fù)雜度 1.2.5編程練習(xí)：最大連續(xù)子序列和算法運算時間的比較 小結(jié) 第2章線性表和串的實現(xiàn)及其應(yīng)用 2.1標(biāo)準(zhǔn)庫數(shù)據(jù)結(jié)構(gòu)vector和list的使用 2.1.1標(biāo)準(zhǔn)庫數(shù)據(jù)結(jié)構(gòu)vector 2.1.2線性表vector的應(yīng)用 2.1.3編程練習(xí)：vector的應(yīng)用 2.1.4標(biāo)準(zhǔn)庫數(shù)據(jù)結(jié)構(gòu)list 2.1.5線性表的應(yīng)用 2.1.6編程練習(xí)：線性表的應(yīng)用 2.1.7編程練習(xí)：多項式的表示和運算 2.1.8編程練習(xí)：集合運算 2.2抽象數(shù)據(jù)類型線性表的實現(xiàn)及其測試 2.2.1線性表抽象數(shù)據(jù)類型定義 2.2.2編程練習(xí)：使用數(shù)組表示線性表 2.2.3使用單鏈表表示線性表 2.2.4編程練習(xí)：熟悉單鏈表 2.2.5編程練習(xí)：線性表的單鏈表實現(xiàn) 2.3串的應(yīng)用 2.3.1數(shù)據(jù)結(jié)構(gòu)串string 2.3.2編程練習(xí)：索引表的生成 2.3.3編程練習(xí)：一個行編輯器的實現(xiàn) 小結(jié) 第3章棧與隊列的實現(xiàn)和應(yīng)用 3.1標(biāo)準(zhǔn)庫棧的使用 3.1.1 STL模板類stack 3.1.2編程練習(xí)：熟悉棧的操作和棧的應(yīng)用 3.2棧的實現(xiàn) 3.2.1棧的定義 3.2.2編程練習(xí)：棧的實現(xiàn) 3.3隊列的應(yīng)用 3.3.1 STL模板隊列queue 3.3.2隊列應(yīng)用例子 3.4隊列的實現(xiàn) 3.4.1隊列的定義 3.4.2編程練習(xí)：隊列的實現(xiàn) 3.5棧和隊列的應(yīng)用 3.5.1車廂調(diào)度問題 3.5.2編程練習(xí)：車廂調(diào)度問題 3.5.3編程練習(xí)：服務(wù)隊列模擬問題 小結(jié) 第4章遞歸 4.1遞歸算法 4.1.1遞歸函數(shù)的例子 4.1.2一摞烙餅的排序 4.1.3編程練習(xí)：遞歸 4.2分治法 4.2.1漢諾塔 4.2.2歸并排序 4.2.3編程練習(xí)：歸并排序的實現(xiàn) 4.2.4遞歸算法的分析 4.3回溯 4.3.1八皇后問題 4.3.2迷宮問題 4.3.3編程練習(xí)：回溯 小結(jié) 第5章二叉樹的實現(xiàn)和應(yīng)用 5.1二叉樹的表示 5.1.1二叉鏈表 5.1.2二叉鏈表的構(gòu)造 5.1.3編程練習(xí)：二叉樹的二叉鏈表表示 5.1.4編程練習(xí)：二叉樹的輸出 5.1.5二叉樹的順序結(jié)構(gòu) 5.2二叉樹的遍歷 5.2.1二叉樹的深度優(yōu)先遍歷 5.2.2編程練習(xí)：二叉樹的遍歷和構(gòu)造 5.2.3編程練習(xí)：二叉樹的構(gòu)造 5.2.4二叉樹的廣度優(yōu)先遍歷 5.2.5編程練習(xí)：樹的層次遍歷 5.3 Huffman編碼的實現(xiàn)及其應(yīng)用 5.3.1 Huffman編碼及其無損壓縮 5.3.2實現(xiàn)基于Huffman編碼的壓縮和解壓縮 小結(jié) 第6章查找的實現(xiàn)與應(yīng)用 6.1順序查找 6.1.1簡單查找 6.1.2編程練習(xí)：順序查找的應(yīng)用和實現(xiàn) 6.1.3條件查找 6.1.4函數(shù)對象 6.1.5編程練習(xí)：條件查找的應(yīng)用 6.2二分查找的應(yīng)用 6.2.1返回存在性的二分查找 6.2.2編程練習(xí)：二分查找的應(yīng)用和實現(xiàn) 6.2.3返回位置的二分查找 6.2.4編程練習(xí)：查找中間數(shù) 6.3二叉查找樹 6.3.1二叉查找樹的插入 6.3.2編程練習(xí)：二叉查找樹的插入 6.3.3二叉查找樹的查找 6.3.4編程練習(xí)：二叉查找樹的查找 6.3.5二叉查找樹的刪除 6.3.6編程練習(xí)：二叉查找樹的刪除 …… 第7章排序的實現(xiàn)與應(yīng)用 第8章圖算法及其應(yīng)用 第9章標(biāo)準(zhǔn)模板庫STL簡介 參考文獻(xiàn) 索引

章節(jié)摘錄

版權(quán)頁：   插圖：   模板機(jī)制的使用，使得可以實現(xiàn)容器與數(shù)據(jù)類型的無關(guān)性（同樣的容器可以管理不同數(shù)據(jù)類型的元素，用類模板實現(xiàn)），以及算法與數(shù)據(jù)類型的無關(guān)性（同樣的算法可以操作不同類型的數(shù)據(jù)，用函數(shù)模板實現(xiàn)）。但是，僅有模板機(jī)制，卻無法實現(xiàn)算法與容器的無關(guān)性。也就是說，無法用同樣的算法來操縱不同種類的容器。為了解決這一問題，C++標(biāo)準(zhǔn)庫設(shè)計中使用了迭代器這一概念，通用算法使用迭代器在容器上進(jìn)行操作。 所謂迭代器，就是一種抽象的指針，是面向?qū)ο蟮膹V義指針，用來指向容器（或流）中的對象，使得可以按順序訪問容器（即數(shù)據(jù)結(jié)構(gòu)）中的對象，而不必暴露容器的內(nèi)部結(jié)構(gòu)，從而實現(xiàn)算法與容器的無關(guān)性。借助于迭代器，同一算法可以對不同種類容器中的數(shù)據(jù)進(jìn)行操作。C++標(biāo)準(zhǔn)庫中的迭代器以類模板的方式定義，使得可以在不同的數(shù)據(jù)結(jié)構(gòu)上體現(xiàn)統(tǒng)一的行為方式。也就是說，可以使用迭代器以基本相同的方式遍歷容器中的元素，而無須關(guān)注底層的數(shù)據(jù)結(jié)構(gòu)到底是順序存儲的vector還是鏈?zhǔn)酱鎯Φ腎ist。 9.2.1 C++標(biāo)準(zhǔn)庫迭代器簡介 C++標(biāo)準(zhǔn)庫中迭代器的實現(xiàn)機(jī)制非常復(fù)雜，下面僅從使用的角度對迭代器進(jìn)行介紹。“迭代器”一詞一般有兩種含義：一是指“迭代器類型”；二是指“迭代器類型的對象”，就像有時將一個“指針類型的變量”也叫做一個“指針”一樣。 迭代器類型有許多具體的不同類別，就像指針類型有基類型不同的許多指針類型一樣（如指向int型對象的指針與指向string型對象的指針就屬于基類型不同的指針類型）。標(biāo)準(zhǔn)庫中定義的迭代器類型有5種類別，不同類別的迭代器類型提供不同的操作，實現(xiàn)不同的功能，具體如表9—7所示。 注9.1 表9—7中所列的每個迭代器類別稱為一個概念（concept），如果一種迭代器支持一個概念所要求的運算，也稱該迭代器是相應(yīng)概念的模型。例如，vector關(guān)聯(lián)的迭代器是輸入迭代器的模型，是雙向迭代器的模型，也是隨機(jī)迭代器的模型。 標(biāo)準(zhǔn)庫中的每種容器都以嵌入類的形式定義了自己的迭代器類型，這些迭代器類型對基類型為容器元素類型的指針進(jìn)行封裝，并重載相應(yīng)運算符。

編輯推薦

《高等院校計算機(jī)實驗與實踐系列示范教材:數(shù)據(jù)結(jié)構(gòu)與算法實驗實踐教程》是獨立于其他數(shù)據(jù)結(jié)構(gòu)和算法教材的輔導(dǎo)書，可作為高等院校數(shù)據(jù)結(jié)構(gòu)與算法實驗課的教材和參考書，也適用于計算機(jī)編程愛好者。

圖書封面

評論、評分、閱讀與下載

---

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

---