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

內(nèi)容概要

　　本書全面系統(tǒng)地介紹了線性表、隊列、堆棧、樹、圖等基本數(shù)據(jù)結(jié)構(gòu)，以及這些數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的存儲及算法實現(xiàn)，系統(tǒng)地介紹了各種查找及排序算法的實現(xiàn)和效率分析，最后一章給出了數(shù)據(jù)結(jié)構(gòu)綜合應(yīng)用實例。書中各種算法采用C語言描述，注重程序設(shè)計風(fēng)格。
　　本書有配套教材《數(shù)據(jù)結(jié)構(gòu)（C語言版）例題詳解與課程設(shè)計指導(dǎo)》(ISBN:9787302246282)，書中包含各知識點(diǎn)的歸納與總結(jié)，也包含例題詳解、習(xí)題解答以及課程設(shè)計指導(dǎo)。
有關(guān)教學(xué)參考資料的電子文檔可通過下載。
　　本書語言流暢，內(nèi)容通俗易懂，算法描述力求簡練、易讀?？勺鳛橛嬎銠C(jī)類及信息類專業(yè)教材，也可供廣大計算機(jī)愛好者及軟件開發(fā)人員自學(xué)提高時使用。

書籍目錄

第1章　緒論
　1.1　什么是數(shù)據(jù)結(jié)構(gòu)
　　1.1.1　數(shù)據(jù)結(jié)構(gòu)的定義
　1.2　基本概念和術(shù)語
　　1.2.1　數(shù)據(jù)與數(shù)據(jù)元素
　　1.2.2　數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)
　　1.2.3　數(shù)據(jù)運(yùn)算
　　1.2.4　數(shù)據(jù)類型與抽象數(shù)據(jù)類型
　1.3　算法和算法描述語言
　1.4　算法分析
　　1.4.1　算法評價
　　1.4.2　算法性能分析與度量
　本章小結(jié)
　習(xí)題　
第2章　線性表
　2.1　線性表的邏輯結(jié)構(gòu)
　　2.1.1　線性表的定義
　　2.1.2　線性表的基本操作
　2.2　線性表的順序存儲及運(yùn)算實現(xiàn)
　　2.2.1　順序表
　　2.2.2　順序表上基本運(yùn)算的實現(xiàn)
　2.3　順序表應(yīng)用舉例
　2.4　線性表的鏈?zhǔn)酱鎯瓦\(yùn)算實現(xiàn)
　　2.4.1　單鏈表
　　2.4.2　單鏈表基本運(yùn)算的實現(xiàn)
　　2.4.3　循環(huán)鏈表
　　2.4.4　雙向鏈表
　　2.4.5　靜態(tài)鏈表
　　2.4.6　單鏈表應(yīng)用舉例
　2.5　順序表和鏈表的比較
　本章小結(jié)
　習(xí)題　
第3章　棧和隊列
　3.1　棧
　　3.1.1　棧的定義及基本操作
　　3.1.2　棧的順序存儲及操作實現(xiàn)
　　3.1.3　棧的鏈?zhǔn)酱鎯安僮鲗崿F(xiàn)
　3.2　棧的應(yīng)用舉例
　3.3　遞歸
　　3.3.1　遞歸定義
　　3.3.2　遞歸和棧的關(guān)系
　　3.3.3　遞歸算法實例
　3.4　隊列
　　3.4.1　隊列的定義及基本操作
　　3.4.2　隊列的順序存儲實現(xiàn)及操作實現(xiàn)
　　3.4.3　隊列的鏈?zhǔn)酱鎯崿F(xiàn)及操作實現(xiàn)
　3.5　隊列應(yīng)用舉例
　本章小結(jié)
　習(xí)題　
第4章　串
　4.1　串及其基本運(yùn)算
　　4.1.1　串的基本概念
　　4.1.2　串的基本運(yùn)算
　4.2　串的順序存儲及基本運(yùn)算
　　4.2.1　串的定長順序存儲
　　4.2.2　定長順序串的基本運(yùn)算
　4.3　模式匹配
　　4.3.1　簡單的模式匹配算法
　　4.3.2　KMP算法
　4.4　串的堆存儲結(jié)構(gòu)
　　4.4.1　動態(tài)堆存儲
　　4.4.2　靜態(tài)堆存儲
　4.5　串的鏈?zhǔn)酱鎯Y(jié)構(gòu)
　4.6　文本編輯——串操作應(yīng)用
　本章小結(jié)
　習(xí)題　
第5章　數(shù)組和廣義表
　5.1　數(shù)組
　　5.1.1　數(shù)組的定義
　　5.1.2　數(shù)組的內(nèi)存映像
　5.2　特殊矩陣的壓縮存儲
　　5.2.1　對稱矩陣
　　5.2.2　三角矩陣
　　5.2.3　稀疏矩陣
　5.3　廣義表
　　5.3.1　廣義表的定義
　　5.3.2　廣義表的存儲
　　5.3.3　廣義表基本操作的實現(xiàn)
　本章小結(jié)
　習(xí)題　
第6章　樹和二叉樹
　6.1　樹的基本概念
　　6.1.1　樹的定義及其表示
　　6.1.2　基本術(shù)語
　6.2　二叉樹
　　6.2.1　二叉樹的定義
　　6.2.2　二叉樹的性質(zhì)
　　6.2.3　二叉樹的存儲結(jié)構(gòu)
　6.3　遍歷二叉樹
　　6.3.1　先序遍歷
　　6.3.2　中序遍歷
　　6.3.3　后序遍歷
　　6.3.4　按層次遍歷二叉樹
　　6.3.5　遍歷算法的應(yīng)用舉例
　6.4　線索二叉樹
　　6.4.1　線索的概念
　　6.4.2　線索的算法實現(xiàn)
　　6.4.3　線索二叉樹上的運(yùn)算
　6.5　樹與森林
　　6.5.1　樹的存儲結(jié)構(gòu)
　　6.5.2　樹、森林和二叉樹的轉(zhuǎn)換
　　6.5.3　樹和森林的遍歷
　6.6　哈夫曼樹
　　6.6.1　基本術(shù)語
　　6.6.2　哈夫曼樹的建立
　本章小結(jié)
　習(xí)題　
第7章　圖
　7.1　圖的基本概念
　　7.1.1　圖的定義和術(shù)語
　　7.1.2　圖的基本操作
　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.3.3　應(yīng)用圖的遍歷判定圖的連通性
　　7.3.4　圖的遍歷的其他應(yīng)用
　7.4　最小生成樹
　　7.4.1　生成樹及生成森林
　　7.4.2　最小生成樹的概念
　　7.4.3　構(gòu)造最小生成樹的Prim算法
　　7.4.4　構(gòu)造最小生成樹的Kruskal算法
　7.5　最短路徑
　　7.5.1　從一個源點(diǎn)到其他各點(diǎn)的最短路徑
　　7.5.2　每一對頂點(diǎn)之間的最短路徑
　7.6　有向無環(huán)圖及其應(yīng)用
　　7.6.1　有向無環(huán)圖的概念
　　7.6.2　AOV網(wǎng)與拓?fù)渑判?br />　　7.6.3　AOE圖與關(guān)鍵路徑
　本章小結(jié)
　習(xí)題　
第8章　查找
　8.1　基本概念
　8.2　線性表的查找
　　8.2.1　順序查找
　　8.2.2　有序表的查找
　　8.2.3　分塊查找
　8.3　樹表查找
　　8.3.1　二叉排序樹
　　8.3.2　平衡二叉樹（AVL樹）
　　8.3.3　B-樹和B?+樹
　8.4　哈希表查找（雜湊法）
　　8.4.1　哈希表與哈希方法
　　8.4.2　常用的哈希方法
　　8.4.3　處理沖突的方法
　　8.4.4　哈希表的操作
　　8.4.5　哈希表查找及其分析
　本章小結(jié)
　習(xí)題　
第9章　排序
　9.1　基本概念
　9.2　插入排序
　　9.2.1　直接插入排序
　　9.2.2　折半插入排序
　　9.2.3　希爾排序
　9.3　交換排序
　　9.3.1　冒泡排序
　　9.3.2　快速排序
　9.4　選擇排序
　　9.4.1　簡單選擇排序
　　9.4.2　堆排序
　9.5　歸并排序
　9.6　基數(shù)排序
　　9.6.1　多關(guān)鍵碼排序
　　9.6.2　鏈?zhǔn)交鶖?shù)排序
　本章小結(jié)
　習(xí)題　
第10章　數(shù)據(jù)結(jié)構(gòu)綜合應(yīng)用
　10.1　各種結(jié)構(gòu)類型之間的關(guān)系概述
　10.2　二叉樹與分治策略
　10.3　圖的遍歷及其應(yīng)用
　本章小結(jié)
　習(xí)題
參考文獻(xiàn)　

章節(jié)摘錄

版權(quán)頁：插圖：4.時空效率時空效率（efficiency）要求算法的執(zhí)行時間盡可能地短，占用的存儲空間盡可能地少。但時空要求往往是相互矛盾的，節(jié)省了時間可能犧牲空間，反之亦然。設(shè)計者應(yīng)在時間與空間兩方面有所平衡。上述4個目標(biāo)，除“正確性”要求達(dá)到第三層次以上，其他目標(biāo)很難有具體要求，有時目標(biāo)之間還會互相抵觸，因此我們只能根據(jù)具體情況有所側(cè)重。例如，若算法需重復(fù)多次使用，則力求節(jié)省時間；若問題的數(shù)據(jù)量很大，計算機(jī)的存儲量又較小，則力求節(jié)省空間。本節(jié)的算法分析主要討論算法的時間性能以及空間性能。1.4.2算法性能分析與度量可以用一個算法的時間復(fù)雜度與空間復(fù)雜度來評價算法的優(yōu)劣。當(dāng)將一個算法轉(zhuǎn)換成程序并在計算機(jī)上執(zhí)行時，其運(yùn)行所需要的時間取決于下列因素。（1）硬件的速度。例如使用微機(jī)還是使用服務(wù)器。（2）書寫程序的語言。實現(xiàn)語言的級別越高，其執(zhí)行效率就越低。（3）編譯程序所生成目標(biāo)代碼的質(zhì)量。對于代碼優(yōu)化較好的編譯程序其所生成的程序質(zhì)量較高。（4）問題的規(guī)模。例如，求100以內(nèi)的素數(shù)與求1000以內(nèi)的素數(shù)的執(zhí)行時間肯定是不同的。顯然，在各種因素都不能確定的情況下，很難比較出算法的執(zhí)行時間。也就是說，使用執(zhí)行算法的絕對時間來衡量算法的效率是不合適的。為此，我們時間復(fù)雜度的定義如下所示。一個算法的時間復(fù)雜度（time complexity）是指，算法運(yùn)行從開始到結(jié)束所需要的時間。這個時間就是該算法中每條語句的執(zhí)行時間之和，而每條語句的執(zhí)行時間是該語句執(zhí)行次數(shù)（也稱為頻度）與執(zhí)行該語句所需時間的乘積。但是，當(dāng)算法轉(zhuǎn)換為程序之后，一條語句執(zhí)行一次所需的時間與計算機(jī)的性能及編譯程序生成目標(biāo)代碼的質(zhì)量有關(guān)，是很難確定的。為此，我們假設(shè)執(zhí)行每條語句所需的時間均為單位時間，在這一假設(shè)下，一個算法所花費(fèi)的時間就等于算法中所有語句的頻度之和。這樣，我們就可以脫離計算機(jī)的硬件、軟件環(huán)境而獨(dú)立地分析算法所消耗的時間。

編輯推薦

《數(shù)據(jù)結(jié)構(gòu)(C語言版)》在省級精品課程建設(shè)的基礎(chǔ)上編寫的，為高質(zhì)量教學(xué)提供配套資源。定位鮮明。本教材立足一般本科院校，難度適中，包括對基本算法的引申和拓展，兼顧對基本算法清晰細(xì)致的分析和對復(fù)雜問題的適當(dāng)引導(dǎo)，在厚基礎(chǔ)和注重能力上實現(xiàn)最佳平衡。內(nèi)容全面，算法設(shè)計簡明，敘述精練。系統(tǒng)地介紹線性表、隊列、堆棧、樹、圖等基本數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的存儲及算法實現(xiàn)，以及各種查找及排序算法的實現(xiàn)和效率分析，最后給出了一個數(shù)據(jù)結(jié)構(gòu)的綜合應(yīng)用實例，運(yùn)用數(shù)據(jù)結(jié)構(gòu)三大邏輯結(jié)構(gòu)解決實際問題。書中各個算法描述思路清晰，編程風(fēng)格統(tǒng)一，書中代碼都調(diào)試通過，保證算法的正確性。配套齊全。包括《數(shù)據(jù)結(jié)構(gòu)（C語言版）例題詳解與課程設(shè)計指導(dǎo)》、教學(xué)課件（PPT）、按章節(jié)和學(xué)時備課教案（Word）、配套源代碼、課程設(shè)計案例指導(dǎo)書、省級精品課程教學(xué)網(wǎng)站等。

圖書封面

評論、評分、閱讀與下載

---

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

---