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

前言

　　本書(shū)是按照美國(guó)電氣電子工程師學(xué)會(huì)（Institute of Electrical and Electronic Engineers， IEEE）和計(jì)算機(jī)協(xié)會(huì)（Association for Computing Machinery， ACM）的《計(jì)算機(jī)學(xué)科教學(xué)計(jì)劃2001》的要求編寫(xiě)的?！　　皵?shù)據(jù)結(jié)構(gòu)”在計(jì)算機(jī)科學(xué)中是一門(mén)綜合性的專業(yè)基礎(chǔ)課。數(shù)據(jù)結(jié)構(gòu)的研究不僅涉及到計(jì)算機(jī)硬件（特別是編碼理論、存儲(chǔ)裝置和存取方法等）的研究范圍，而且和計(jì)算機(jī)軟件的研究有著更密切的關(guān)系，無(wú)論是編譯程序，還是操作系統(tǒng)，都涉及到數(shù)據(jù)元素在存儲(chǔ)器中的分配問(wèn)題。在研究信息檢索時(shí)也必須考慮如何組織數(shù)據(jù)，以便查找和存取數(shù)據(jù)元素更為方便?？梢哉J(rèn)為數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門(mén)核心課程，是從事計(jì)算機(jī)科學(xué)及其應(yīng)用的科技工作者必須掌握的重要課程?！　”窘滩淖鳛椤?1 世紀(jì)計(jì)算機(jī)專業(yè)大專系列教材》之一。教材在內(nèi)容組織和編排上力求體現(xiàn)“先理論，后應(yīng)用，理論與應(yīng)用相結(jié)合”的原則，強(qiáng)調(diào)對(duì)理論知識(shí)的理解和運(yùn)用。通過(guò)對(duì)本課程的學(xué)習(xí)，掌握各種數(shù)據(jù)結(jié)構(gòu)的基本概念、邏輯特性和物理表示法，以及相應(yīng)運(yùn)算的算法；靈活運(yùn)用各種數(shù)據(jù)結(jié)構(gòu)解決實(shí)際應(yīng)用問(wèn)題，并且為學(xué)習(xí)后繼專業(yè)課程打下良好的基礎(chǔ)。　　全書(shū)共分為9章?！　〉?章綜述數(shù)據(jù)、數(shù)據(jù)結(jié)構(gòu)、算法描述、算法分析，以及數(shù)據(jù)結(jié)構(gòu)與其他課程之間的關(guān)系等?！　〉?章至第7章介紹了基本的數(shù)據(jù)結(jié)構(gòu)，如線性表、棧、隊(duì)列、串、數(shù)組、廣義表、樹(shù)、二叉樹(shù)及圖等，分別討論了數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以及相應(yīng)運(yùn)算的算法?！　〉?章和第9章為查找和排序，介紹了常用的幾種查找方法和內(nèi)部排序方法?！　”窘滩挠幸韵轮饕攸c(diǎn)：　?。?）基礎(chǔ)理論知識(shí)的闡述由淺入深、通俗易懂、邏輯性強(qiáng)。在內(nèi)容的組織與編排上，略去了一些理論上的推導(dǎo)和繁瑣的數(shù)學(xué)證明?！　。?）為了有助于學(xué)生加深對(duì)基礎(chǔ)理論知識(shí)的理解，培養(yǎng)實(shí)際應(yīng)用的能力，各章（除第1章外）都配有與該章內(nèi)容相關(guān)的操作應(yīng)用舉例，且配有大量習(xí)題?！　。?）教材中使用類 C 語(yǔ)言作為算法描述語(yǔ)言，且所有算法都可以在任何一種 C 語(yǔ)言的開(kāi)發(fā)環(huán)境中實(shí)現(xiàn)。在隨書(shū)的配套光盤(pán)中可以看到這些算法的 C 語(yǔ)言程序?！　。?）附錄中匯總了本教材各章中介紹的各類數(shù)據(jù)結(jié)構(gòu)時(shí)用到的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)類型說(shuō)明，供學(xué)生上機(jī)實(shí)驗(yàn)時(shí)參考使用?！　”窘滩闹v課時(shí)數(shù)為 60 學(xué)時(shí)左右，上機(jī)實(shí)驗(yàn)時(shí)數(shù)在 20 學(xué)時(shí)以上。教師可以根據(jù)學(xué)時(shí)數(shù)和學(xué)生的實(shí)際情況選講操作應(yīng)用舉例中的例子。　　本書(shū)可作為高等院校計(jì)算機(jī)專業(yè)大專學(xué)生數(shù)據(jù)結(jié)構(gòu)課的教材，也可作為非計(jì)算機(jī)專業(yè)本科生的教材。　　由于作者水平有限，在教材中難免有錯(cuò)誤，懇請(qǐng)讀者諒解?！　”窘滩挠衫畲笥呀淌谥骶幒蛯彾?，彭波副教授編寫(xiě)。在上機(jī)實(shí)現(xiàn)教材中所有算法的過(guò)程中得到了曾立、許振文等同志的幫助，在此表示感謝。

內(nèi)容概要

本教材是《21世紀(jì)計(jì)算機(jī)專業(yè)大專系列教材》之一。全書(shū)共分9章，第1章綜述數(shù)據(jù)、數(shù)據(jù)結(jié)構(gòu)、算法描述、算法分析，以及數(shù)據(jù)結(jié)構(gòu)與其他課程之間的關(guān)系等。第2章至第7章介紹了基本的數(shù)據(jù)結(jié)構(gòu)，如線性表、棧、隊(duì)列、串、數(shù)組、廣義表、材、二叉樹(shù)及圖等，分別討論了數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以及相應(yīng)運(yùn)算的算法。第8章和第9章為查找和排序，介紹了常用的幾種查找方法和內(nèi)部排序方法。教材中使用類C語(yǔ)言作為算法描述語(yǔ)言，且所有算法都可以在任何一種C語(yǔ)言的開(kāi)發(fā)環(huán)境中實(shí)現(xiàn)。在隨書(shū)的配套光盤(pán)中可以看到這些算法的C語(yǔ)言程序?！稊?shù)據(jù)結(jié)構(gòu)》中所介紹的數(shù)據(jù)結(jié)構(gòu)概念清楚，內(nèi)容豐富。為了有助于學(xué)生加深對(duì)基礎(chǔ)理論知識(shí)的理解，培養(yǎng)實(shí)際應(yīng)用的能力，各章（除第1章外）都配有與該章內(nèi)容相關(guān)的操作應(yīng)用舉例，且配有大量習(xí)題?！稊?shù)據(jù)結(jié)構(gòu)》可作為高等院校計(jì)算機(jī)專業(yè)大專數(shù)據(jù)結(jié)構(gòu)課程的教材，也可作為非計(jì)算機(jī)專業(yè)本科生的教材。

書(shū)籍目錄

第1章  緒論  1.1  數(shù)據(jù)結(jié)構(gòu)概述  1.2  數(shù)據(jù)結(jié)構(gòu)的發(fā)展概況  1.3  數(shù)據(jù)結(jié)構(gòu)與其他課程的關(guān)系  1.4  基本概念　1.5  算法描述及分析　　1.5.1  算法的重要特性　　1.5.2  算法的描述方法　　1.5.3  算法的設(shè)計(jì)要求　　1.5.4  算法效率的度量　　1.5.5  算法的空間需求　習(xí)題第2章  線性表　2.1  線性表的邏輯結(jié)構(gòu)　　2.1.1  線性表的定義　　2.1.2  線性表的基本操作　2.2  線性表的順序存儲(chǔ)結(jié)構(gòu)　　2.2.1  線性表的順序存儲(chǔ)表示　　2.2.2  基本操作在順序表上的實(shí)現(xiàn)　　2.2.3  線性表順序存儲(chǔ)結(jié)構(gòu)小結(jié)　2.3  線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)　　2.3.1  線性表的鏈?zhǔn)酱鎯?chǔ)表示　　2.3.2  基本操作在單鏈表上的實(shí)現(xiàn)　　2.3.3  循環(huán)鏈表　　2.3.4  雙向鏈表　　2.3.5  線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)小結(jié)　2.4  線性表的兩種存儲(chǔ)結(jié)構(gòu)比較　2.5  線性表操作應(yīng)用舉例　習(xí)題第3章  棧和隊(duì)列　3.1  棧　　3.1.1  棧的邏輯結(jié)構(gòu)　　3.1.2  棧的順序存儲(chǔ)結(jié)構(gòu)　　3.1.3  棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)　3.2  隊(duì)列　　3.2.1  隊(duì)列的邏輯結(jié)構(gòu)　　3.2.2  隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)　　3.2.3  隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)　3.3  棧和隊(duì)列操作應(yīng)用舉例　習(xí)題第4章  串　4.1  串的邏輯結(jié)構(gòu)　　4.1.1  串的定義　　4.1.2  串的基本操作　4.2  串的存儲(chǔ)結(jié)構(gòu)　　4.2.1  定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)　　4.2.2  堆分配存儲(chǔ)結(jié)構(gòu)　　4.2.3  塊鏈存儲(chǔ)結(jié)構(gòu)　4.3  串操作應(yīng)用舉例　習(xí)題第5章  數(shù)組與廣義表　5.1  數(shù)組的邏輯結(jié)構(gòu)　　5.1.1  數(shù)組的定義　　5.1.2  數(shù)組的基本操作　5.2  數(shù)組的順序存儲(chǔ)結(jié)構(gòu)　5.3  矩陣的壓縮存儲(chǔ)　　5.3.1  特殊矩陣的壓縮存儲(chǔ)　　5.3.2  稀疏矩陣的邏輯結(jié)構(gòu)　　5.3.3  稀疏矩陣的存儲(chǔ)結(jié)構(gòu)　5.4　 廣義表　　5.4.1  廣義表的邏輯結(jié)構(gòu)　　5.4.2  廣義表的存儲(chǔ)結(jié)構(gòu)　5.5  數(shù)組與廣義表操作應(yīng)用舉例　習(xí)題第6章  樹(shù)與二叉樹(shù)　6.1  樹(shù)　　6.1.1  樹(shù)的邏輯結(jié)構(gòu)　　6.1.2  樹(shù)的存儲(chǔ)結(jié)構(gòu)　6.2  二叉樹(shù)　　6.2.1  二叉樹(shù)的邏輯結(jié)構(gòu)　　6.2.2  二叉樹(shù)的基本性質(zhì)　　6.2.3  二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)　6.3  遍歷二叉樹(shù)　　6.3.1  遍歷二叉樹(shù)的操作定義　　6.3.2  遍歷二叉樹(shù)的遞歸算法　　6.3.3  遍歷二叉樹(shù)的非遞歸算法　　6.3.4  建立二叉樹(shù)的算法　6.4  二叉線索樹(shù)　　6.4.1  二叉線索樹(shù)的引出　　6.4.2  二叉線索樹(shù)的定義　　6.4.3  二叉線索樹(shù)的存儲(chǔ)結(jié)構(gòu)　　6.4.4  二叉線索樹(shù)的操作　6.5  樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換　　6.5.1  樹(shù)與二叉樹(shù)的轉(zhuǎn)換　　6.5.2  森林與二叉樹(shù)的轉(zhuǎn)換　　6.5.3  樹(shù)和森林的遍歷　6.6  赫夫曼樹(shù)及其應(yīng)用　　6.6.1  基本概念　　6.6.2  赫夫曼算法　　6.6.3  赫夫曼編碼　　6.6.4  赫夫曼樹(shù)和赫夫曼編碼的存儲(chǔ)表示　　6.6.5  赫夫曼編碼的算法　　6.6.6  示例　6.7  樹(shù)與二叉樹(shù)操作應(yīng)用舉例　習(xí)題第7章  圖　7.1  圖的邏輯結(jié)構(gòu)　　7.1.1圖的定義　　7.1.2  圖的基本操作　　7.1.3  圖的基本概念　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  最小生成樹(shù)　　7.4.1  生成樹(shù)　　7.4.2  最小生成樹(shù)　7.5  最短路徑　　7.5.1  求某個(gè)源點(diǎn)到其他頂點(diǎn)的最短路徑　　7.5.2  求每一對(duì)頂點(diǎn)之間的最短路徑　7.6  拓?fù)渑判颉　?.6.1  AOV網(wǎng)　　7.6.2  拓?fù)渑判颉?.7  關(guān)鍵路徑　　7.7.1  AOE網(wǎng)　　7.7.2  關(guān)鍵路徑的概念　　7.7.3  關(guān)鍵路徑的算法　7.8  圖操作應(yīng)用舉例　習(xí)題第8章  查找　8.1  基本概念　8.2  靜態(tài)查找　　8.2.1  靜態(tài)查找的基本操作　　8.2.2  靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)　　8.2.3  順序查找　　8.2.4  折半查找　　8.2.5  分塊查找　8.3  動(dòng)態(tài)查找　　8.3.1  動(dòng)態(tài)查找的基本操作　　8.3.2  動(dòng)態(tài)查找表的二叉鏈表存儲(chǔ)結(jié)構(gòu)　　8.3.3  二叉排序樹(shù)　　8.3.4  二叉平衡樹(shù)　　8.3.5  B樹(shù)　8.4  散列表　　8.4.1  散列表的概念　　8.4.2  散列函數(shù)的構(gòu)造方法　　8.4.3  處理沖突的方法　　8.4.4  散列表的查找和分析　8.5  查找操作應(yīng)用舉例　習(xí)題第9章  排序　9.1  基本概念　9.2  插入排序法　　9.2.1  直接插入排序　　9.2.2  希爾排序　9.3  交換排序法　　9.3.1  冒泡排序　　9.3.2  快速排序　9.4  選擇排序法　　9.4.1  直接選擇排序　　9.4.2  堆排序　9.5  歸并排序法　　9.5.1  兩個(gè)有序序列的歸并　　9.5.2  一趟歸并排序　9.6  基數(shù)排序法　　9.6.1  多關(guān)鍵字排序　　9.6.2  鏈?zhǔn)交鶖?shù)排序　9.7  各種內(nèi)部排序法的比較　9.8  排序操作應(yīng)用舉例　習(xí)題附錄  數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)綜合參考文獻(xiàn)

章節(jié)摘錄

　　第1章 緒論　　自從世界上第一臺(tái)電子計(jì)算機(jī)問(wèn)世以來(lái)，計(jì)算機(jī)科學(xué)和計(jì)算機(jī)軟件、硬件技術(shù)得到飛速地發(fā)展；計(jì)算機(jī)的應(yīng)用領(lǐng)域也從最初的科學(xué)計(jì)算逐步發(fā)展到人類社會(huì)的各個(gè)領(lǐng)域。計(jì)算機(jī)加工處理的對(duì)象由簡(jiǎn)單的數(shù)值、字符發(fā)展到文字、圖像、聲音等各種復(fù)雜的帶有不同類型及相互有不同關(guān)系的數(shù)據(jù)。為了編制“好”的程序，必須要分析程序處理的數(shù)據(jù)的特性及數(shù)據(jù)之間的關(guān)系，這就是“數(shù)據(jù)結(jié)構(gòu)”這門(mén)學(xué)科形成和發(fā)展的背景?！　?.1　數(shù)據(jù)結(jié)構(gòu)概述　　眾所周知，計(jì)算機(jī)的程序是對(duì)數(shù)據(jù)進(jìn)行加工處理。在大多數(shù)情況下，這些數(shù)據(jù)并不是無(wú)組織的，數(shù)據(jù)之間往往具有重要的結(jié)構(gòu)關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)的重要內(nèi)容。那么，什么是數(shù)據(jù)結(jié)構(gòu)呢？先不妨舉例說(shuō)明，然后給出明確定義?！　±?.1　一個(gè)大學(xué)的學(xué)生健康情況管理?！　”?.1　中的學(xué)生健康情況登記表就是一個(gè)數(shù)據(jù)結(jié)構(gòu)。表中每個(gè)學(xué)生的情況為一個(gè)記錄，它由姓名、學(xué)號(hào)、性別、年齡、班級(jí)和健康狀況等6個(gè)數(shù)據(jù)項(xiàng)組成。計(jì)算機(jī)學(xué)生健康情況管理的主要功能包括：查詢、瀏覽、插入、修改、刪除和統(tǒng)計(jì)等。

圖書(shū)封面

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

---

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

---