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

內(nèi)容概要

《高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)核心課程系列規(guī)劃教材:數(shù)據(jù)結(jié)構(gòu)與算法(C語(yǔ)言版)》為高等院校計(jì)算機(jī)及相關(guān)專業(yè)“數(shù)據(jù)結(jié)構(gòu)”課程的教學(xué)用書(shū)，系統(tǒng)地介紹了各種典型的數(shù)據(jù)結(jié)構(gòu)，內(nèi)容包括：數(shù)據(jù)結(jié)構(gòu)概論、線性表、棧與隊(duì)列、串、數(shù)組、樹(shù)、圖、查找、排序、遞歸、文件等：為了加強(qiáng)對(duì)算法的理解，還介紹了算法分析方面的內(nèi)容。

書(shū)籍目錄

第1章數(shù)據(jù)結(jié)構(gòu)概論 1.1 問(wèn)題的提出 1.2基本概念與術(shù)語(yǔ) 1.3數(shù)據(jù)結(jié)構(gòu)的概念 1.4數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及運(yùn)算 1.4.1數(shù)據(jù)的邏輯結(jié)構(gòu) 1.4.2數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 1.4.3數(shù)據(jù)的運(yùn)算 1.4.4邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及運(yùn)算的關(guān)系 1.5算法與算法特性 1.5.1算法及其特性 1.5.2算法的描述方法 1.5.3算法與程序及數(shù)據(jù)結(jié)構(gòu) 1.6算法性能分析及算法度量 1.6.1 算法性能分析 1.6.2算法度量 小結(jié) 習(xí)題 拓展實(shí)驗(yàn)：電話號(hào)碼的查詢 第2章線?陛表 2.1線性表的定義與運(yùn)算 2.1.1線性表的定義 2.1.2線性表的抽象數(shù)據(jù)類型 2.2線性表的順序存儲(chǔ) 2.2.1順序存儲(chǔ) 2.2.2順序表的運(yùn)算 2.3線性表的鏈?zhǔn)酱鎯?chǔ) 2.3.1線性鏈表及運(yùn)算 2.3.2靜態(tài)鏈表及運(yùn)算 2.3.3 循環(huán)鏈表及運(yùn)算 2.3.4雙向鏈表及運(yùn)算 2.4線性表的應(yīng)用 2.4.1 約瑟夫問(wèn)題 2.4.2一元多項(xiàng)式求和問(wèn)題 2.4.3 集合應(yīng)用問(wèn)題 小結(jié) 習(xí)題 拓展實(shí)驗(yàn)：線性表的合并 第3章棧與隊(duì)列 3.1 棧 3.1.1 棧的定義 3.1.2棧的順序存儲(chǔ)結(jié)構(gòu) 3.1.3棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 3.2棧的應(yīng)用 3.2.1 子程序的調(diào)用和返回問(wèn)題 3.2.2數(shù)制轉(zhuǎn)換問(wèn)題 3.3 隊(duì)列 3.3.1 隊(duì)列的定義 3.3.2 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu) 3.3.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 3.4隊(duì)列的應(yīng)用 3.4.1 設(shè)備速度不匹配問(wèn)題 3.4.2舞伴問(wèn)題 小結(jié) 習(xí)題 拓展實(shí)驗(yàn)：算術(shù)表達(dá)式求值 第4章 串 4.1 串的基本概念 4.2串的存儲(chǔ)結(jié)構(gòu) 4.2.1 串的靜態(tài)存儲(chǔ)結(jié)構(gòu) 4.2.2 串的動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu) 4.3 串的基本運(yùn)算 4.3.1 串的抽象數(shù)據(jù)類型定義 4.3.2 串的基本運(yùn)算實(shí)現(xiàn) 4.4模式匹配 4.4.1 BF算法 4.4.2 KMP算法 4.5 串的應(yīng)用 小結(jié) 習(xí)題 拓展實(shí)驗(yàn)：設(shè)計(jì)簡(jiǎn)單的文本編輯器 第5章數(shù)組 5.1 數(shù)組及其基本操作 5.1.1數(shù)組的概念 5.1.2抽象數(shù)據(jù)類型數(shù)組的定義 5.2數(shù)組的存儲(chǔ)結(jié)構(gòu) 5.3 數(shù)組在矩陣運(yùn)算中的應(yīng)用 5.3.1 特殊矩陣的壓縮存儲(chǔ) 5.3.2稀疏矩陣的壓縮存儲(chǔ) 小結(jié) 習(xí)題 拓展實(shí)驗(yàn)：一元多項(xiàng)式的值計(jì)算 第6章樹(shù) 6.1樹(shù)的概念 6.1.1樹(shù)的定義 6.1.2樹(shù)的表示方法 6.1.3樹(shù)的基本術(shù)語(yǔ) 6.1.4樹(shù)的ADT定義 6.2 二叉樹(shù) 6.2.1 二叉樹(shù)的定義及基本結(jié)構(gòu) 6.2.2二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 6.2.3二叉樹(shù)的遍歷 6.3線索二叉樹(shù) 6.3.1二叉樹(shù)的線索化 6.3.2利用線索遍歷 6.4樹(shù)、森林、二叉樹(shù)之間的關(guān)系 6.4.1樹(shù)的存儲(chǔ)結(jié)構(gòu) 6.4.2森林與二叉樹(shù)的轉(zhuǎn)換 6.4.3樹(shù)和森林的遍歷 6.5 哈夫曼算法及其應(yīng)用 6.5.1 哈夫曼樹(shù)的定義 6.5.2哈夫曼二叉樹(shù)的構(gòu)造 6.5.3 哈夫曼樹(shù)在編碼問(wèn)題中的應(yīng)用 小結(jié) 習(xí)題 拓展實(shí)驗(yàn)：創(chuàng)建二叉樹(shù) 第7章 圖 7.1 圖的概念與ADT定義 7.1.1 圖的概念 7.1.2 圖的抽象數(shù)據(jù)類型定義 7.2 圖的存儲(chǔ)結(jié)構(gòu) 7.2.1 鄰接矩陣 7.2.2鄰接表 7.2.3十字鏈表 7.2.4鄰接多重表 7.3圖的遍歷 7.3.1深度優(yōu)先搜索 7.3.2廣度優(yōu)先搜索 7.4圖的應(yīng)用 7.4.1 生成樹(shù) 7.4.2最短路徑 7.4.3 拓?fù)渑判?7.4.4關(guān)鍵路徑 小結(jié) 習(xí)題 拓展實(shí)驗(yàn)：圖的深度優(yōu)先搜索 第8章 查找 8.1 查找的基本概念 8.2靜態(tài)查找問(wèn)題 8.2.1順序查找 8.2.2二分查找 8.3線性表的查找方法 8.3.1線性查找 8.3.2折半查找 8.3.3 分塊查找 8.4樹(shù)表的查找方法 8.4.1 二叉查找樹(shù) 8.4.2平衡二叉樹(shù) 8.4.3 B-樹(shù) 8.5 哈希表的查找方法 8.5.1 哈希表 8.5.2 構(gòu)造哈希表的基本方法 8.5.3解決沖突的方法 8.5.4 哈希表的查找方法 8.6各種查找方法的比較 小結(jié) 習(xí)題 拓展實(shí)驗(yàn)：折半查找 第9章 排序 9.1排序的基本概念 9.2內(nèi)部排序 9.2.1 插入排序 9.2.2 冒泡排序 9.2.3快速排序 9.2.4選擇排序 9.2.5 歸并排序 9.2.6 基數(shù)排序 9.3 內(nèi)部排序方法比較 9.4 內(nèi)部排序方法的選擇 9.5外部排序簡(jiǎn)介 小結(jié) 習(xí)題 拓展實(shí)驗(yàn)：希爾排序 第10章遞歸 10.1 遞歸的定義與類型 10.1.1遞歸的定義 10.1.2遞歸的類型 10.2遞歸應(yīng)用舉例 10.2.1漢諾塔問(wèn)題 10.2.2八皇后問(wèn)題 10.3遞歸的實(shí)現(xiàn) 10.4遞歸到非遞歸的轉(zhuǎn)換過(guò)程 10.5 遞歸的時(shí)間和空問(wèn)復(fù)雜度 小結(jié) 習(xí)題 拓展實(shí)驗(yàn)：漢諾塔問(wèn)題研究 第11章 文件 11.1外存儲(chǔ)器簡(jiǎn)介 11.2有關(guān)文件的概念 11.2.1 文件及其類別 11.2.2文件的操作 11.3 文件的組織 11.3.1 順序文件 11.3.2索引文件 11.3.3散列文件 11.3.4多關(guān)鍵字文件 小結(jié) 習(xí)題 拓展實(shí)驗(yàn)：索引文件 參考文獻(xiàn)

章節(jié)摘錄

版權(quán)頁(yè)：   插圖：   算法中用到了對(duì)隊(duì)列操作的幾個(gè)函數(shù)，可參看隊(duì)列一章中的相關(guān)內(nèi)容。遍歷函數(shù)BFS（）與深度優(yōu)先搜索中給出的相同，這里不再給出。 分析算法的實(shí)質(zhì)，每個(gè)頂點(diǎn)至多只能有一次機(jī)會(huì)進(jìn)入隊(duì)列。遍歷圖的過(guò)程實(shí)際上就是以邊或弧為線索，尋找鄰接點(diǎn)的過(guò)程。圖的廣度優(yōu)先遍歷算法的時(shí)間復(fù)雜度和深度優(yōu)先搜索相同，采用鄰接矩陣存儲(chǔ)結(jié)構(gòu)時(shí)，其時(shí)間復(fù)雜度為O（n2），而采用鄰接表存儲(chǔ)結(jié)構(gòu)時(shí)，其時(shí)間復(fù)雜度為O（n+e），e為圖中邊的個(gè)數(shù)。 值得注意的一點(diǎn)是，無(wú)論采用深度優(yōu)先搜索法，還是廣度優(yōu)先搜索法進(jìn)行圖的遍歷，如果選定的出發(fā)點(diǎn)不同或者是所建立的存儲(chǔ)結(jié)構(gòu)不一致，則可能得到不同的遍歷結(jié)果。只有當(dāng)選取的出發(fā)點(diǎn)、采用的存儲(chǔ)結(jié)構(gòu)以及遍歷圖的方式都是確定的，遍歷的結(jié)果才是唯一的。 7.4 圖的應(yīng)用 本節(jié)從生成樹(shù)、最短路徑、拓?fù)渑判蚝完P(guān)鍵路徑方面介紹圖的應(yīng)用。 7.4.1 生成樹(shù) 7.1節(jié)中介紹了生成樹(shù)的概念。設(shè)G（V，E）是一個(gè)連通的無(wú)向圖，從圖中任意一個(gè)頂點(diǎn)出發(fā)，可以訪問(wèn)到全部頂點(diǎn)。在遍歷的過(guò)程中，所經(jīng)過(guò)的邊集設(shè)為T（G），沒(méi)有經(jīng)過(guò)的邊集設(shè)為B（G）。顯然，T∪B=E，且T∩B=?？紤]一個(gè)新圖G’=（V，T），由于V（G’）=V（G），E（G’）E（G），則G’是G的連通子圖，且G’中含有G的全部頂點(diǎn)。把圖中的頂點(diǎn)加上遍歷時(shí)經(jīng)過(guò)的所有邊所構(gòu)成的子圖稱為生成樹(shù)。如G’是G的生成樹(shù)。顯然，n個(gè)頂點(diǎn)的連通圖至少有n-1條邊。由于生成樹(shù)有n-1條邊，所以生成樹(shù)是連通圖的極小連通子圖。對(duì)于一個(gè)非連通圖和不是強(qiáng)連通的有向圖，從任意一點(diǎn)出發(fā)，不能訪問(wèn)到圖中所有頂點(diǎn)，只能得到連通分量的生成樹(shù)，所有連通分量的生成樹(shù)組成生成森林。 一個(gè)連通圖的生成樹(shù)并不是唯一的，這是因?yàn)楸闅v圖時(shí)選擇的起始點(diǎn)不同，遍歷的策略不同，因此遍歷所經(jīng)過(guò)的邊也就不同，故而產(chǎn)生不同的生成樹(shù)。如圖7-20所示就是幾種不同的生成樹(shù)。 因?yàn)榫W(wǎng)的邊帶權(quán)，而生成樹(shù)不唯一，于是就產(chǎn)生了這樣一個(gè)問(wèn)題：如何找到一個(gè)各邊的權(quán)數(shù)總和最小的生成樹(shù)，這對(duì)于實(shí)際生活有很大的意義。例如，如果想在幾個(gè)城市之間進(jìn)行通信聯(lián)絡(luò)，首先需要建設(shè)一個(gè)基礎(chǔ)通信網(wǎng)絡(luò)，如果城市數(shù)量是n個(gè)，要想實(shí)現(xiàn)各個(gè)城市間的通信則至少需要n-1條線路。當(dāng)選擇具體的通信線路時(shí)，首先應(yīng)該考慮通信經(jīng)費(fèi)問(wèn)題。任意兩個(gè)城市之間的通信線路都相應(yīng)地存在通信代價(jià)權(quán)值。n個(gè)城市，如果任意兩個(gè)城市之間均有線路，則最多可設(shè)置n（n-1）／2條線路，如何在這n（n-1）／2條線路中選擇行-1條，使得總的耗費(fèi)最低，這是一個(gè)需考慮的問(wèn)題。 對(duì)于n個(gè)城市之問(wèn)的基礎(chǔ)通信網(wǎng)絡(luò)可以用連通網(wǎng)來(lái)表示，其中網(wǎng)的頂點(diǎn)表示城市，邊表示兩城市之間的線路，邊的權(quán)值表示相應(yīng)線路上的通信代價(jià)。依據(jù)這個(gè)連通網(wǎng)可以建立多棵生成樹(shù)，每一棵生成樹(shù)都可以形成一個(gè)通信網(wǎng)方案。生成樹(shù)的代價(jià)是各個(gè)邊的代價(jià)之和，如果選擇生成樹(shù)的目標(biāo)是使總體的通信費(fèi)用最小，這個(gè)問(wèn)題就是構(gòu)造連通網(wǎng)的最小代價(jià)生成樹(shù)，簡(jiǎn)稱為最小生成樹(shù)的問(wèn)題。

編輯推薦

《高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)核心課程系列規(guī)劃教材:數(shù)據(jù)結(jié)構(gòu)與算法(C語(yǔ)言版)》語(yǔ)言與選材精練、概念清晰、注重實(shí)用、邏輯性強(qiáng)，對(duì)于各章節(jié)中所涉及的數(shù)據(jù)結(jié)構(gòu)與算法都給出了C語(yǔ)言描述，并都附有大量的習(xí)題，便于學(xué)生理解與掌握。《高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)核心課程系列規(guī)劃教材:數(shù)據(jù)結(jié)構(gòu)與算法(C語(yǔ)言版)》適合作為高等院校計(jì)算機(jī)及相關(guān)專業(yè)的教材，也可作為計(jì)算機(jī)應(yīng)用技術(shù)人員的參考書(shū)。

圖書(shū)封面

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

---

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

---