數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

內(nèi)容概要

本書第一章綜述了數(shù)據(jù)結(jié)構(gòu)的基本概念及算法分析初步；第二章至第七章分別討論了線性表、棧、隊(duì)列、數(shù)組、廣義表、樹(shù)、二叉樹(shù)、圖、串和集合等常用的數(shù)據(jù)結(jié)構(gòu)，包括數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及有關(guān)運(yùn)算；第八章和第九章討論了在數(shù)據(jù)處理中常用的查找和排序的各種方法和算法；第十章介紹了常用的文件組織方法；第十一章簡(jiǎn)單介紹了常用算法設(shè)計(jì)方法。全書的選材注重于實(shí)際應(yīng)用，略去一些理論推導(dǎo)和證明；采用通俗易懂的語(yǔ)言描述各種數(shù)據(jù)結(jié)構(gòu)的定義；采用類C語(yǔ)言來(lái)描述數(shù)據(jù)結(jié)構(gòu)和算法，盡量考慮C語(yǔ)言的特點(diǎn)。本書可作為計(jì)算機(jī)專業(yè)的教材或非計(jì)算機(jī)類各專業(yè)選修課的教材。

書籍目錄

第一章 緒論  1.1 基本概念和術(shù)語(yǔ)  1.2 算法的描述和分析  習(xí)題第二章 線性表  2.1 線性表的定義和運(yùn)算  2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)  2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)  2.4 棧  2.5 棧與遞歸  2.6 隊(duì)列  2.7 循環(huán)鏈表和雙向鏈表  2.8 一元多項(xiàng)式相加  習(xí)題第三章 數(shù)組和廣義表  3.1 數(shù)組  3.2 稀疏矩陣  3.3 廣義表  習(xí)題第四章 樹(shù)和二叉樹(shù)  4.1 樹(shù)的定義和術(shù)語(yǔ)  4.2 二叉樹(shù)  4.3 遍歷二叉樹(shù)  4.4 線索二叉樹(shù)  4.5 樹(shù)的存儲(chǔ)結(jié)構(gòu)和遍歷  4.6 哈夫曼樹(shù)  習(xí)題第五章 圖  5.1 圖的概念及術(shù)語(yǔ)  5.2 圖的存儲(chǔ)結(jié)構(gòu)  5.3 圖的遍歷  5.4 最小生成樹(shù)  5.5 最短路徑  5.6 拓?fù)渑判? 5.7 關(guān)鍵路徑  習(xí)題第六章 串  6.1 串的基本概念和存儲(chǔ)結(jié)構(gòu)  6.2 串的基本運(yùn)算  6.3 模式匹配  習(xí)題第七章 集合  7.1 集合的概念及主要運(yùn)算  7.2 集合的存儲(chǔ)表示  7.3 典型的集合結(jié)構(gòu)  習(xí)題第八章 查找  8.1 線性表查找  8.2 散列表和查找  8.3 二叉排序樹(shù)  習(xí)題第九章 排序  9.1 插入排序  9.2 選擇排序  9.3 交換排序  9.4 基數(shù)排序  9.5 歸并排序  9.6 內(nèi)部排序方法的選擇和使用  習(xí)題第十章 文件  10.1 順序文件  10.2 索引文件  10.3 散列文件  10.4 例排文件  習(xí)題第十一章 常用算法設(shè)計(jì)方法  11.1 遞推法  11.2 分治法  11.3 溯法  11.4 貪心法  11.5 動(dòng)態(tài)規(guī)劃法  習(xí)題參考文獻(xiàn)

章節(jié)摘錄

　　算法是解決某一特定類型問(wèn)題的有具體步驟的方法。一個(gè)算法應(yīng)該具有下列特性：　?。?）有窮性。一個(gè)算法必須是在執(zhí)行有限步之后結(jié)束?！　。?）確定性。算法的每一步必須是確切地定義的，無(wú)二義性。對(duì)于每種情況，有待執(zhí)行的運(yùn)算必須被嚴(yán)格地和清楚地規(guī)定?！　。?）可行性。算法應(yīng)該是可行的，這意味著算法中描述的運(yùn)算都是相當(dāng)基本的，它們都是可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)的?！　。?）輸入。一個(gè)算法有0個(gè)或多個(gè)輸入。它們是在算法開(kāi)始前對(duì)算法給定的量。這些輸入取自于特定的對(duì)象的集合?！　。?）輸出。一個(gè)算法有一個(gè)或多個(gè)輸出。它們是同輸入有某種特定關(guān)系的量?！　∫粋€(gè)算法可以用自然語(yǔ)言、計(jì)算機(jī)程序語(yǔ)言來(lái)說(shuō)明，只是要求該說(shuō)明必須精確地描述計(jì)算過(guò)程。通常，描述算法采用介于自然語(yǔ)言和程序語(yǔ)言之間的偽語(yǔ)言，這樣既可以利用程序語(yǔ)言的主要語(yǔ)句描述算法的計(jì)算過(guò)程，又不至于陷于具體程序語(yǔ)言的某些細(xì)節(jié)。為了便于讀者上機(jī)驗(yàn)證算法和提高讀者的編程能力，本書采用C語(yǔ)言描述算法。　　求解同一個(gè)問(wèn)題可能有多種不同的算法，判斷一個(gè)算法的好壞，主要有以下幾個(gè)標(biāo)準(zhǔn)：　?。?）正確性。算法應(yīng)滿足具體問(wèn)題的需求，正確反映求解問(wèn)題對(duì)輸入、輸出和加工處理等方面的需求?！　。?）可讀性。算法應(yīng)當(dāng)便于閱讀，以利于理解與修改。如：算法的結(jié)構(gòu)清晰并加入注釋，簡(jiǎn)要說(shuō)明主要參數(shù)的使用規(guī)則，各程序段完成的功能等?！　。?）健壯性。要求算法具有查錯(cuò)和處理功能。如對(duì)非法數(shù)據(jù)或執(zhí)行過(guò)程中出現(xiàn)的異常狀態(tài)進(jìn)行檢測(cè)、報(bào)錯(cuò)和糾正錯(cuò)誤?！　。?）效率。算法的效率主要指算法運(yùn)行時(shí)所需要的計(jì)算機(jī)資源的多少，包括運(yùn)行時(shí)間和存儲(chǔ)空間的消耗。通常，求解同一個(gè)問(wèn)題若有多種算法，則執(zhí)行時(shí)間短的算法效率高，占用空間少的算法較好。但是算法的時(shí)間開(kāi)銷和空間開(kāi)銷經(jīng)常是相互制約的，對(duì)高時(shí)間效率和低存儲(chǔ)量的要求只能根據(jù)問(wèn)題的性質(zhì)折衷處理?！　≡谒惴ㄊ恰罢_的”前提下，對(duì)算法在計(jì)算機(jī)上執(zhí)行耗費(fèi)時(shí)間和所占空間的分析，常常是人們對(duì)算法進(jìn)行評(píng)估和選擇的重要依據(jù)?！　∷惴ǚ治鍪菍?duì)一種算法所消耗的計(jì)算機(jī)資源的估算，算法設(shè)計(jì)者可以據(jù)此對(duì)解決同一個(gè)問(wèn)題的多種算法的代價(jià)進(jìn)行比較，還可以判斷一種算法在實(shí)現(xiàn)時(shí)是否會(huì)遇到資源限制的問(wèn)題?！　　?/pre>








圖書封面



圖書標(biāo)簽Tags
無(wú)




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



還沒(méi)讀過(guò)(29)
勉強(qiáng)可看(213)
一般般(364)
內(nèi)容豐富(1510)
強(qiáng)力推薦(123)


 


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