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

前言

我們生活在一個物質(zhì)世界中，同時又時刻面對著一個數(shù)字的世界。如果將物質(zhì)世界中的事與物數(shù)字化，那么它們在計算機中均表現(xiàn)為數(shù)據(jù)。這些數(shù)據(jù)來源于現(xiàn)實，具有具體的含義，而且在計算機中有著統(tǒng)一的表示方法，因而成為計算機程序處理的符號集合。研究數(shù)據(jù)在計算機中的表示方法、關(guān)聯(lián)方法、存儲方法以及典型處理方法，正是數(shù)據(jù)結(jié)構(gòu)課程的主要內(nèi)容。早在20ff紀80年代初，“數(shù)據(jù)結(jié)構(gòu)”就已成為國內(nèi)高校計算機專業(yè)教學(xué)計劃中的核心課程。目前，ACM／IEEE計算學(xué)科課程計劃（CC．2001）已將算法與數(shù)據(jù)結(jié)構(gòu)類課程列為核心課程之首，數(shù)據(jù)結(jié)構(gòu)愈益顯現(xiàn)出其在信息學(xué)科理論中的重要地位。在軟件系統(tǒng)的開發(fā)過程中，數(shù)據(jù)結(jié)構(gòu)的思維方法在本質(zhì)上不同于常規(guī)數(shù)學(xué)訓(xùn)練的公理系統(tǒng)思維方法，而是一種算法構(gòu)造性思維方法。所謂構(gòu)造性思維方法就是要讓學(xué)生理解、習(xí)慣并掌握算法的一種思維方法，也是本門課程教學(xué)的重要內(nèi)容和主要難點。要成為專業(yè)的軟件開發(fā)人員，僅僅知道開發(fā)工具的語言規(guī)則和簡單使用過程是遠遠不夠的，只有培養(yǎng)自身的數(shù)據(jù)抽象能力、算法設(shè)計能力，掌握創(chuàng)造性思維方法，舉一反三，觸類旁通，才能夠具備應(yīng)用知識解決復(fù)雜問題的能力。本書是作者根據(jù)多年的教學(xué)經(jīng)驗，結(jié)合當(dāng)前計算機科學(xué)技術(shù)的發(fā)展，并參考了眾多的數(shù)據(jù)結(jié)構(gòu)教材編著而成的。書中采用了能夠自然體現(xiàn)抽象數(shù)據(jù)類型概念的c++語言作為算法描述語言，內(nèi)容覆蓋了數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)大綱，從數(shù)據(jù)類型角度系統(tǒng)地介紹了各種數(shù)據(jù)結(jié)構(gòu)的邏輯特性、存儲表示方法及基本操作算法，并針對常用的數(shù)據(jù)結(jié)構(gòu)進一步討論了各種應(yīng)用算法及其實現(xiàn)方法。本書旨在培養(yǎng)學(xué)生分析計算機加工數(shù)據(jù)對象特征的能力，以便在實際操作中選擇合適的數(shù)據(jù)結(jié)構(gòu)和存儲結(jié)構(gòu)以及相應(yīng)的算法，同時幫助學(xué)生掌握估算算法時間復(fù)雜度和空間復(fù)雜度的基本技巧。本書將數(shù)據(jù)結(jié)構(gòu)的原理和算法分析技術(shù)有機地結(jié)合在一起，使用了參數(shù)化的模板，提高了算法中數(shù)據(jù)類型的通用性，支持高效的代碼重用。書中介紹和分析重點設(shè)計思想時，結(jié)合了大量圖解和具體示例，使讀者能夠聯(lián)系實際，掌握數(shù)據(jù)結(jié)構(gòu)的實質(zhì)內(nèi)容。此外，本書還介紹了一些比較高級的數(shù)據(jù)結(jié)構(gòu)及相關(guān)的算法分析技術(shù)。

內(nèi)容概要

本書采用能夠自然體現(xiàn)抽象數(shù)據(jù)類型概念的C++ 語言作為算法描述語言，把數(shù)據(jù)結(jié)構(gòu)的原理和算法分析技術(shù)有機地結(jié)合在一起。全書內(nèi)容包括線性表、棧、隊列、遞歸、廣義表、字符串、數(shù)組、樹、圖、查找以及各種排序算法，并給出了相關(guān)的實驗指導(dǎo)。書中還引入了一些比較高級的數(shù)據(jù)結(jié)構(gòu)和相關(guān)的算法分析技術(shù)。    本書可作為高等院校計算機或相關(guān)專業(yè)的教材，也可以作為其他程序類課程的輔導(dǎo)教材，同時也適用準備參加研究生入學(xué)考試、自學(xué)考試和各類程序設(shè)計競賽的人員閱讀。

作者簡介

余臘生，中南大學(xué)副教授。主講計算機專業(yè)本科“數(shù)據(jù)結(jié)構(gòu)”和“計算機系統(tǒng)結(jié)構(gòu)”課程以及研究生“軟件構(gòu)件技術(shù)”課程多年，其中“數(shù)據(jù)結(jié)構(gòu)”課程被評為“中南大學(xué)精品課程”。主持和參加了包括國家863應(yīng)用示范工程和湖南省自然科學(xué)基金項目在內(nèi)的10多個科研項目，在國內(nèi)外專業(yè)核心刊物發(fā)表論文30多篇，EI檢索多篇。主要研究方向為Agent理論及其計算技術(shù)、結(jié)構(gòu)與算法、網(wǎng)絡(luò)數(shù)據(jù)庫技術(shù)等。

書籍目錄

第1章　緒論   　1.1　數(shù)據(jù)結(jié)構(gòu)的概念   　　1.1.1　為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)   　　1.1.2　相關(guān)概念和術(shù)語   　1.2　抽象數(shù)據(jù)類型   　　1.2.1　數(shù)據(jù)類型   　　1.2.2　抽象數(shù)據(jù)類型   　1.3　算法和算法分析  　　1.3.1　問題求解概述  　　1.3.2　算法特性  　　1.3.3　常見的算法類型  　　1.3.4　算法描述  　　1.3.5　算法性能分析與度量  　習(xí)題  　實習(xí)題  第2章　線性表  　2.1　線性表的邏輯結(jié)構(gòu)  　　2.1.1　線性表的定義  　　2.1.2　線性表的基本操作  　2.2　線性表的順序存儲及操作實現(xiàn)  　　2.2.1　順序表  　　2.2.2　順序表上基本操作的實現(xiàn)  　　2.2.3　順序表應(yīng)用舉例  　　2.2.4　小結(jié)  　2.3　線性表的鏈式存儲及操作實現(xiàn)  　　2.3.1　單向鏈表  　　2.3.2　單向鏈表上基本操作的實現(xiàn)  　　2.3.3　循環(huán)鏈表  　　2.3.4　雙向鏈表  　　2.3.5　靜態(tài)鏈表  　　2.3.6　單向鏈表應(yīng)用舉例  　2.4　順序表和鏈表的選取  　習(xí)題  　實習(xí)題  第3章　棧和隊列  　3.1　棧  　　3.1.1　棧的定義及基本操作  　　3.1.2　棧的存儲及操作實現(xiàn)  　　3.1.3　棧應(yīng)用舉例  　3.2　隊列  　　3.2.1　隊列的定義及基本操作  　　3.2.2　隊列的存儲及操作實現(xiàn)  　　3.2.3　優(yōu)先隊列  　　3.2.4　雙端隊列  　　3.2.5　隊列應(yīng)用舉例  　習(xí)題  　實習(xí)題  第4章　遞歸和廣義表  　4.1　何謂遞歸  　4.2　遞歸的執(zhí)行過程  　4.3　尾部遞歸函數(shù)  　4.4　遞歸的應(yīng)用  　　4.4.1　漢諾塔問題  　　4.4.2　迷宮問題  　　4.4.3　n皇后問題  　4.5　遞歸程序到非遞歸程序的轉(zhuǎn)換  　　4.5.1　簡單轉(zhuǎn)換  　　4.5.2　復(fù)雜轉(zhuǎn)換  　　4.5.3　轉(zhuǎn)化的形式化步驟  　4.6　廣義表 　　4.6.1　廣義表的定義及基本操作 　　4.6.2　廣義表的存儲 　　4.6.3　廣義表有關(guān)操作的實現(xiàn) 　習(xí)題 　實習(xí)題 第5章　字符串 　5.1　字符串及其基本操作 　　5.1.1　字符串的基本概念 　　5.1.2　字符串的基本操作 　5.2　字符串的定長順序存儲及基本操作 　　5.2.1　字符串的定長順序存儲 　　5.2.2　定長順序串的基本操作 　　5.2.3　模式匹配 　5.3　字符串的堆存儲 　　5.3.1　字符串名的存儲映像 　　5.3.2　堆存儲結(jié)構(gòu) 　　5.3.3　基于堆存儲結(jié)構(gòu)的基本操作 　5.4　字符串的鏈式存儲 　5.5　字符串的應(yīng)用 　　5.5.1　中文分詞 　　5.5.2　遺傳算法 　習(xí)題 　實習(xí)題 第6章　數(shù)組與矩陣 　6.1　數(shù)組 　　6.1.1　數(shù)組的邏輯結(jié)構(gòu) 　　6.1.2　數(shù)組的內(nèi)存映像 　6.2　特殊矩陣的壓縮存儲 　　6.2.1　對角矩陣 　　6.2.2　三對角矩陣 　　6.2.3　三角矩陣 　　6.2.4　對稱矩陣 　6.3　稀疏矩陣 　　6.3.1　稀疏矩陣的三元組表存儲 　　6.3.2　稀疏矩陣的鏈式存儲 　　6.3.3　稀疏矩陣的十字鏈表存儲 　習(xí)題 　實習(xí)題 第7章　樹與二叉樹 　7.1　樹的定義及表示 　　7.1.1　樹的定義 　　7.1.2　樹的表示 　　7.1.3　樹的特點 　　7.1.4　與樹相關(guān)的基本術(shù)語 　　7.1.5　樹形結(jié)構(gòu)的邏輯特征 　　7.1.6　樹的存儲 　7.2　二叉樹 　　7.2.1　二叉樹的定義及相關(guān)概念 　　7.2.2　二叉樹的主要性質(zhì) 　　7.2.3　二叉樹的存儲 　　7.2.4　二叉樹的基本操作及實現(xiàn) 　7.3　二叉樹的遍歷 　　7.3.1　二叉樹的遍歷方法及遞歸實現(xiàn) 　　7.3.2　二叉樹遍歷的非遞歸實現(xiàn) 　　7.3.3　遍歷算法應(yīng)用舉例 　　7.3.4　由遍歷序列恢復(fù)二叉樹 　　7.3.5　不用棧的二叉樹遍歷非遞歸方法 　7.4　線索二叉樹 　　7.4.1　線索二叉樹的定義及結(jié)構(gòu) 　　7.4.2　線索二叉樹的基本操作及實現(xiàn) 　7.5　最優(yōu)二叉樹——赫夫曼樹 　　7.5.1　赫夫曼樹的基本概念 　　7.5.2　赫夫曼樹的構(gòu)造算法 　　7.5.3　赫夫曼樹的應(yīng)用 　7.6　樹、森林與二叉樹的轉(zhuǎn)換 　　7.6.1　樹、森林到二叉樹的轉(zhuǎn)換 　　7.6.2　二叉樹到樹和森林的轉(zhuǎn)換 　7.7　樹和森林的遍歷 　　7.7.1　樹的遍歷 　　7.7.2　森林的遍歷 　　7.7.3　樹和森林的層次次序遍歷 　7.8　樹的應(yīng)用 　　7.8.1　判定樹 　　7.8.2　集合的表示 　習(xí)題 　實習(xí)題 第8章　圖 　8.1　基本概念 　　8.1.1　圖的定義和術(shù)語 　　8.1.2　圖的抽象數(shù)據(jù)類型 　8.2　圖的存儲結(jié)構(gòu) 　　8.2.1　鄰接矩陣 　　8.2.2　鄰接表 　　8.2.3　鄰接矩陣和鄰接表的比較 　　8.2.4　十字鏈表 　　8.2.5　鄰接多重表 　　8.2.6　索引表 　8.3　圖的遍歷 　　8.3.1　深度優(yōu)先搜索 　　8.3.2　廣度優(yōu)先搜索 　8.4　圖的連通性 　　8.4.1　無向圖的連通性 　　8.4.2　有向圖的連通性 　　8.4.3　生成樹和生成森林 　　8.4.4　關(guān)節(jié)點和雙連通分量 　8.5　最小生成樹 　　8.5.1　最小生成樹的基本概念 　　8.5.2　Prim算法 　　8.5.3　Kruskal算法 　8.6　最短路徑 　　8.6.1　無權(quán)最短路徑問題 　　8.6.2　從一個源點到其他各頂點的最短路徑 　　8.6.3　邊上權(quán)值為任意值的單源最短路徑問題 　　8.6.4　負權(quán)最短路徑問題 　　8.6.5　每對頂點之間的最短路徑 　8.7　DAG及其應(yīng)用 　　8.7.1　DAG的概念 　　8.7.2　AOV網(wǎng)與拓撲排序 　　8.7.3　AOE圖與關(guān)鍵路徑 　習(xí)題 　實習(xí)題 第9章　查找 　9.1　基本概念 　9.2　靜態(tài)查找表 　　9.2.1　靜態(tài)查找表結(jié)構(gòu) 　　9.2.2　順序查找 　　9.2.3　有序表的二分查找 　　9.2.4　有序表的斐波那契查找和插值查找 　　9.2.5　分塊查找 　9.3　動態(tài)查找表 　　9.3.1　二叉排序樹 　　9.3.2　平衡二叉樹 　　9.3.3　紅黑樹 　　9.3.4　B樹 　　9.3.5　B+樹   9.4　散列表查找 　　9.4.1　散列表與散列方法 　　9.4.2　常用的散列函數(shù) 　　9.4.3　處理沖突的方法 　　9.4.4　散列表的查找分析 　　9.4.5　散列表的操作 　習(xí)題 　實習(xí)題 第10章　排序 　10.1　基本概念 　10.2　插入排序 　　10.2.1　直接插入排序 　　10.2.2　二分插入排序 　　10.2.3　表插入排序 　　10.2.4　謝爾排序 　10.3　交換排序  　　10.3.1　冒泡排序  　　10.3.2　快速排序 　10.4　選擇排序 　　10.4.1　線性選擇排序 　　10.4.2　交換線性選擇排序 　　10.4.3　樹形選擇排序 　　10.4.4　堆排序 　　10.4.5　用堆實現(xiàn)的優(yōu)先隊列 　10.5　兩路歸并排序 　10.6　分配排序 　　10.6.1　多鍵排序 　　10.6.2　桶排序 　　10.6.3　鏈式基數(shù)排序 　10.7　其他排序方法 　　10.7.1　二叉樹排序法 　　10.7.2　計數(shù)排序法 　10.8　各種內(nèi)排序方法的比較 　10.9　外排序 　　10.9.1　外排序的方法 　　10.9.2　自然歸并排序法 　　10.9.3　k路歸并法 　　10.9.4　多段歸并法 　習(xí)題 　實習(xí)題 參考文獻 附錄　實驗指導(dǎo)（圖靈網(wǎng)站下載）

章節(jié)摘錄

插圖：

編輯推薦

《數(shù)據(jù)結(jié)構(gòu)基于C++模板類的實現(xiàn)》是作者在多年教學(xué)實踐的基礎(chǔ)上編寫而成的，寫作中注意借鑒近年出版的多種數(shù)據(jù)結(jié)構(gòu)領(lǐng)域優(yōu)秀著作的長處?！稊?shù)據(jù)結(jié)構(gòu)基于C++模板類的實現(xiàn)》采用C++模板類描述算法，強調(diào)實踐性，深入地闡述了數(shù)據(jù)結(jié)構(gòu)的基本知識和各種數(shù)據(jù)結(jié)構(gòu)的具體應(yīng)用，并比較、分析了每一種數(shù)據(jù)結(jié)構(gòu)的不同存儲方法及其有關(guān)算法。內(nèi)容包括線性表、棧和隊列、遞歸與廣義表、串、數(shù)組和矩陣、樹和二叉樹、圖、排序和查找等?！ご蠖鄶?shù)算法使用了參數(shù)化的模板，支持高效的代碼重用?！ご罅康膱D解和具體的實例分析使抽象的內(nèi)容變得具體而且淺顯易懂?！τ谥攸c算法給出了富于啟發(fā)性的問題及討論。·設(shè)計了許多有典型性的習(xí)題和實驗指導(dǎo)，幫助讀者能夠?qū)W會正確地選擇數(shù)據(jù)結(jié)構(gòu)，編寫符合程序規(guī)范的代碼，為應(yīng)用程序的開發(fā)打下基礎(chǔ)。

圖書封面

評論、評分、閱讀與下載

---

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

---