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

內(nèi)容概要

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

書籍目錄

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

章節(jié)摘錄

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

編輯推薦

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

圖書封面

評論、評分、閱讀與下載

---

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

---