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

前言

　　“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程、信息與計(jì)算科學(xué)、信息管理與信息系統(tǒng)等相關(guān)專業(yè)最重要的專業(yè)基礎(chǔ)課之一，主要研究分析計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式和相關(guān)操作運(yùn)算算法。通過本課程學(xué)習(xí)，要求學(xué)生掌握數(shù)據(jù)結(jié)構(gòu)和算法的基本概念和技術(shù)，掌握數(shù)組、線性表、棧、隊(duì)列、串、廣義表、樹、二叉樹、圖等常用數(shù)據(jù)結(jié)構(gòu)及相關(guān)算法，以及排序、查找等重要技術(shù)，能針對應(yīng)用問題選擇合適的數(shù)據(jù)結(jié)構(gòu)，并設(shè)計(jì)相應(yīng)的操作運(yùn)算算法?！　∧暇煼洞髮W(xué)“數(shù)據(jù)結(jié)構(gòu)”課程經(jīng)過多年建設(shè)與探索，進(jìn)行了教學(xué)內(nèi)容與教學(xué)方法的改革與實(shí)踐，提高了教學(xué)質(zhì)量，被評(píng)為江蘇省精品課程。我們在教學(xué)中貫徹了下列指導(dǎo)思想：　　（1）基礎(chǔ)性。數(shù)據(jù)結(jié)構(gòu)、算法和程序設(shè)計(jì)是計(jì)算機(jī)科學(xué)的核心，本課程應(yīng)為學(xué)生的軟件開發(fā)能力的培養(yǎng)打下扎實(shí)的基礎(chǔ)?！　。?）系統(tǒng)性。本課程以系統(tǒng)的觀點(diǎn)研究數(shù)據(jù)組織和操作算法，必須在抽象思維、算法設(shè)計(jì)等方面加強(qiáng)學(xué)生的能力培養(yǎng)。　?。?）先進(jìn)性。本課程的新思想和新方法不斷產(chǎn)生，必須不斷更新教學(xué)內(nèi)容以拓寬學(xué)生的知識(shí)面，適應(yīng)計(jì)算機(jī)應(yīng)用和發(fā)展的需要?！　。?）實(shí)踐性。本課程是一門實(shí)踐性很強(qiáng)的課程，在“數(shù)據(jù)結(jié)構(gòu)”的課程實(shí)驗(yàn)中不僅要訓(xùn)練學(xué)生的計(jì)算機(jī)實(shí)驗(yàn)技能和操作能力，更應(yīng)包括設(shè)計(jì)算法的創(chuàng)造性實(shí)驗(yàn)?zāi)芰?。　　本教材在編寫過程中集作者多年“數(shù)據(jù)結(jié)構(gòu)”精品課程的教學(xué)經(jīng)驗(yàn)，體現(xiàn)科學(xué)性、先進(jìn)性和實(shí)用性原則，既注重基本原理，又重視算法實(shí)現(xiàn)；力求內(nèi)容豐富，重點(diǎn)突出，條理清晰，由淺入深，語言流暢，具有特色。全書使用C++類定義各種數(shù)據(jù)結(jié)構(gòu)，利用C++偽代碼描述算法；給出許多經(jīng)典算法和典型題例；每章均附有小結(jié)、習(xí)題和上機(jī)實(shí)驗(yàn)題；附錄給出了5套課程考試樣卷和5道課程設(shè)計(jì)題，以供教學(xué)參考?！　”窘滩墓卜?0章?！　〉?章簡要介紹數(shù)據(jù)結(jié)構(gòu)和算法的基本概念；　　第2-5章介紹線性結(jié)構(gòu)及其算法，包括線性表、棧、隊(duì)列、串、數(shù)組和特殊矩陣；　　第6-8章介紹非線性結(jié)構(gòu)及其算法，包括廣義表、樹、二叉樹、圖；　　第9章介紹各種常用的查找算法；　　第10章介紹各種常用的排序算法?！　”窘滩挠赡暇煼洞髮W(xué)“數(shù)據(jù)結(jié)構(gòu)”課程組共同編寫。其中，第1章和第10章由吉根林教授編寫；第2章和第3章由陳波副教授編寫；第6章和第7章由王瓊副教授編寫；第5章和第8章由周俊生副教授編寫；第4章和第9章由于泠副教授編寫。全書由吉根林和陳波擔(dān)任主編，并最后統(tǒng)稿、修改和定稿。本書出版過程中得到了電子工業(yè)出版社的大力支持，在此表示衷心的感謝！　　由于作者水平有限，書中難免存在不妥之處，敬請讀者批評(píng)指正。

內(nèi)容概要

本書是省精品課程的教學(xué)成果，全書共分10章，介紹各種常用的數(shù)據(jù)結(jié)構(gòu)，包括線性表、棧、隊(duì)列、串、數(shù)組、特殊矩陣、廣義表、樹、二叉樹、圖等；闡述各種數(shù)據(jù)結(jié)構(gòu)的基本概念、邏輯關(guān)系、存儲(chǔ)結(jié)構(gòu)、操作運(yùn)算及其實(shí)現(xiàn)算法；介紹各種常用的查找算法和排序算法，并對各種算法的性能進(jìn)行分析。書中使用C++類定義各種數(shù)據(jù)結(jié)構(gòu)，利用C++偽代碼描述算法；給出了許多經(jīng)典算法和典型題例；每章均附有小結(jié)、習(xí)題和上機(jī)實(shí)驗(yàn)題；附錄給出了5套課程考試樣卷和5道課程設(shè)計(jì)題。    本書既注重基本原理，又重視算法實(shí)現(xiàn)；既體現(xiàn)先進(jìn)性，又強(qiáng)調(diào)實(shí)用性；內(nèi)容豐富，重點(diǎn)突出，條理清晰，由淺入深。本書的PPT課件和相關(guān)教學(xué)資源可從江蘇省精品課程和南京師范大學(xué)精品課程“數(shù)據(jù)結(jié)構(gòu)”網(wǎng)站http://mcs.njnu.edu.cn/datastructure/index.asp下載。    本書可作為高等學(xué)校計(jì)算機(jī)、軟件工程、信息與計(jì)算科學(xué)、信息管理與信息系統(tǒng)等專業(yè)教材，也可供計(jì)算機(jī)軟件開發(fā)人員參考。

書籍目錄

第1章  緒論  1.1  數(shù)據(jù)結(jié)構(gòu)課程的研究內(nèi)容  1.2  基本概念及術(shù)語  1.3  算法與算法分析    1.3.1  算法    1.3.2  算法分析  本章小結(jié)  習(xí)題1  上機(jī)實(shí)驗(yàn)題1第2章  線性表  2.1  線性表的基本概念  2.2  線性表的存儲(chǔ)結(jié)構(gòu)    2.2.1  順序存儲(chǔ)結(jié)構(gòu)    2.2.2  鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)  2.3  線性表的操作算法    2.3.1  順序表的操作算法    2.3.2  鏈表的操作算法  2.4  線性表的應(yīng)用  2.5  順序表和鏈表的綜合比較  本章小結(jié)  習(xí)題2  上機(jī)實(shí)驗(yàn)題2第3章  棧和隊(duì)列  3.1  棧    3.1.1  棧的基本概念    3.1.2  棧的存儲(chǔ)結(jié)構(gòu)    3.1.3  棧的操作算法    3.1.4  棧的應(yīng)用  3.2  隊(duì)列    3.2.1  隊(duì)列的基本概念    3.2.2  隊(duì)列的存儲(chǔ)結(jié)構(gòu)    3.2.3  隊(duì)列的操作算法    3.2.4  隊(duì)列的應(yīng)用  本章小結(jié)  習(xí)題3  上機(jī)實(shí)驗(yàn)題3第4章  串  4.1  串的基本概念  4.2  串的存儲(chǔ)結(jié)構(gòu)    4.2.1  串的順序存儲(chǔ)結(jié)構(gòu)    4.2.2  串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)  4.3  串的操作算法    4.3.1  串的基本操作算法    4.3.2  串的模式匹配    4.3.3  串的應(yīng)用——文本編輯軟件  本章小結(jié)  習(xí)題4  上機(jī)實(shí)驗(yàn)題4第5章  數(shù)組和特殊矩陣  5.1  數(shù)組    5.1.1  數(shù)組的基本概念    5.1.2  數(shù)組的存儲(chǔ)結(jié)構(gòu)  5.2  特殊矩陣的壓縮存儲(chǔ)    5.2.1  對稱矩陣的壓縮存儲(chǔ)    5.2.2  三角矩陣的壓縮存儲(chǔ)    5.2.3  對角矩陣的壓縮存儲(chǔ)    5.2.4  稀疏矩陣的壓縮存儲(chǔ)  本章小結(jié)  習(xí)題5  上機(jī)實(shí)驗(yàn)題5第6章  廣義表  6.1  廣義表的基本概念  6.2  廣義表的存儲(chǔ)結(jié)構(gòu)    6.2.1  廣義表中結(jié)點(diǎn)的結(jié)構(gòu)    6.2.2  廣義表的存儲(chǔ)結(jié)構(gòu)舉例  6.3  廣義表的操作算法    6.3.1  構(gòu)造算法    6.3.2  遍歷廣義表    6.3.3  廣義表算法舉例  本章小結(jié)  習(xí)題6  上機(jī)實(shí)驗(yàn)題6第7章  樹和二叉樹  7.1  樹的概念和性質(zhì)    7.1.1  樹的定義    7.1.2  樹的基本術(shù)語    7.1.3  樹的基本性質(zhì)  7.2  二叉樹的概念和性質(zhì)    7.2.1  二叉樹的定義    7.2.2  二叉樹的基本性質(zhì)  7.3  二叉樹的存儲(chǔ)結(jié)構(gòu)    7.3.1  二叉樹的順序存儲(chǔ)結(jié)構(gòu)    7.3.2  二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)  7.4  二叉樹的遍歷    7.4.1  二叉樹遍歷的概念    7.4.2  二叉樹遍歷算法    7.4.3  二叉樹的構(gòu)造和析構(gòu)算法  7.5  二叉樹的其他操作算法  7.6  線索二叉樹    7.6.1  線索二叉樹的概念    7.6.2  線索二叉樹的存儲(chǔ)結(jié)構(gòu)    7.6.3  線索二叉樹的操作算法  7.7  樹的存儲(chǔ)結(jié)構(gòu)與算法    7.7.1  樹的存儲(chǔ)結(jié)構(gòu)    7.7.2  樹的操作算法  7.8  HUFFMAN樹與HUFFMAN編碼    7.8.1  Huffman樹的定義    7.8.2  Huffman樹的構(gòu)造    7.8.3  Huffman編碼與譯碼    7.8.4  Huffman樹的其他應(yīng)用——程序設(shè)計(jì)流程優(yōu)化  7.9  樹與等價(jià)類    7.9.1  等價(jià)類問題    7.9.2  等價(jià)類的實(shí)現(xiàn)    7.9.3  性能分析與改進(jìn)  本章小結(jié)  習(xí)題7  上機(jī)實(shí)驗(yàn)題7第8章  圖  8.1  圖的基本概念    8.1.1  圖的定義    8.1.2  圖的基本術(shù)語  8.2  圖的存儲(chǔ)結(jié)構(gòu)    8.2.1  鄰接矩陣表示法    8.2.2  鄰接表表示法  8.3  圖的遍歷    8.3.1  圖的遍歷的概念    8.3.2  深度優(yōu)先搜索    8.3.3  廣度優(yōu)先搜索    8.3.4  圖的遍歷算法的應(yīng)用  8.4  最小生成樹    8.4.1  最小生成樹的概念及其性質(zhì)    8.4.2  Prim算法    8.4.3  Kruskal算法  8.5  最短路徑    8.5.1  最短路徑的概念    8.5.2  單源最短路徑    8.5.3  每對頂點(diǎn)之間的最短路徑  8.6  AOV網(wǎng)與拓?fù)渑判?   8.6.1  有向無環(huán)圖與AOV網(wǎng)的概念    8.6.2  拓?fù)渑判? 8.7  AOE網(wǎng)與關(guān)鍵路徑    8.7.1  AOE網(wǎng)的概念    8.7.2  關(guān)鍵路徑  本章小結(jié)  習(xí)題8  上機(jī)實(shí)驗(yàn)題8第9章  查找  9.1  查找的基本概念  9.2  順序表的查找    9.2.1  順序查找    9.2.2  折半查找    9.2.3  分塊查找  9.3  樹表的查找    9.3.1  二叉排序樹    9.3.2  平衡二叉樹    9.3.3  B樹    9.3.4  B+樹  9.4  HASH查找    9.4.1  Hash查找的基本概念    9.4.2  Hash表的構(gòu)造    9.4.3  Hash查找算法及分析  本章小結(jié)  習(xí)題9  上機(jī)實(shí)驗(yàn)題9第10章  排序  10.1  排序的基本概念  10.2  冒泡排序  10.3  選擇排序  10.4  插入排序    10.4.1  直接插入排序    10.4.2  折半插入排序  10.5  希爾排序  10.6  快速排序  10.7  堆排序  10.8  歸并排序    10.8.1  二路歸并排序的非遞歸實(shí)現(xiàn)    10.8.2  二路歸并排序的遞歸實(shí)現(xiàn)  10.9  基數(shù)排序    10.9.1  多關(guān)鍵字排序    10.9.2  鏈?zhǔn)交鶖?shù)排序  本章小結(jié)  習(xí)題10  上機(jī)實(shí)驗(yàn)題10附錄A  數(shù)據(jù)結(jié)構(gòu)試題附錄B  數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題參考文獻(xiàn)

章節(jié)摘錄

　　第1章　緒論　　“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程、信息安全、信息管理與信息系統(tǒng)、信息與計(jì)算科學(xué)等專業(yè)的一門十分重要的專業(yè)核心基礎(chǔ)課程，主要學(xué)習(xí)計(jì)算機(jī)中數(shù)據(jù)的組織方式、存儲(chǔ)結(jié)構(gòu)和處理方法。數(shù)據(jù)結(jié)構(gòu)課程的學(xué)習(xí)將為計(jì)算機(jī)及相關(guān)專業(yè)的后續(xù)課程（如操作系統(tǒng)、編譯原理、數(shù)據(jù)庫原理、軟件工程等）的學(xué)習(xí)打下基礎(chǔ)。實(shí)際上，要編寫一個(gè)“好”的程序，無非是要選擇一個(gè)合理的數(shù)據(jù)結(jié)構(gòu)和好的算法，而“好”算法的選擇很大程度上取決于描述實(shí)際問題所采用的數(shù)據(jù)結(jié)構(gòu)，因此要編寫出“好”的程序，僅僅學(xué)習(xí)程序設(shè)計(jì)語言是不夠的，必須很好地掌握數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)和基本技能。本章將概要地介紹數(shù)據(jù)結(jié)構(gòu)課程的研究內(nèi)容、基本概念和基本思想?！　?.1　數(shù)據(jù)結(jié)構(gòu)課程的研究內(nèi)容。　　數(shù)據(jù)結(jié)構(gòu)起源于程序設(shè)計(jì)，隨著計(jì)算機(jī)科學(xué)技術(shù)的發(fā)展，計(jì)算機(jī)應(yīng)用領(lǐng)域不再局限于科學(xué)計(jì)算，而更多地應(yīng)用于信息處理、智能控制、辦公自動(dòng)化等領(lǐng)域。計(jì)算機(jī)處理的對象由數(shù)值發(fā)展到字符串、表格、圖形、圖像、聲音等數(shù)據(jù)，而且處理的數(shù)據(jù)量也越來越大。在程序設(shè)計(jì)中面對這樣的數(shù)據(jù)，我們應(yīng)如何來組織和處理它們呢?這就是“數(shù)據(jù)結(jié)構(gòu)”課程需要研究的問題?！　∮?jì)算機(jī)解決問題時(shí)，一般要經(jīng)過幾個(gè)步驟：首先，要將實(shí)際問題抽象出數(shù)學(xué)模型，然后針對數(shù)學(xué)模型設(shè)計(jì)出求解算法，最后編寫程序上機(jī)調(diào)試，直到求出最終結(jié)果。數(shù)值計(jì)算問題的數(shù)學(xué)模型一般可由數(shù)學(xué)方程或數(shù)學(xué)公式來描述。然而，對于非數(shù)值計(jì)算問題，例如圖書資料的檢索、人一機(jī)博弈、課程表編排、最短路徑求解等問題，它們的數(shù)學(xué)模型無法用數(shù)學(xué)方程或數(shù)學(xué)公式來描述，而是要用線性表、樹、圖等數(shù)據(jù)結(jié)構(gòu)來描述，并且要對這些模型設(shè)計(jì)相應(yīng)算法來求解。數(shù)據(jù)結(jié)構(gòu)就是研究計(jì)算機(jī)非數(shù)值計(jì)算問題中的數(shù)據(jù)對象以及它們之間的關(guān)系和操作算法的學(xué)科，具體主要包含三個(gè)方面的內(nèi)容：①數(shù)據(jù)的邏輯結(jié)構(gòu)；②數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；③數(shù)據(jù)的操作算法。

編輯推薦

　　本教材在編寫過程中集作者多年“數(shù)據(jù)結(jié)構(gòu)”精品課程的教學(xué)經(jīng)驗(yàn)，體現(xiàn)科學(xué)性、先進(jìn)性和實(shí)用性原則，既注重基本原理，又重視算法實(shí)現(xiàn)；力求內(nèi)容豐富，重點(diǎn)突出，條理清晰，由淺入深，語言流暢，具有特色。全書使用C++類定義各種數(shù)據(jù)結(jié)構(gòu)，利用C++偽代碼描述算法；給出許多經(jīng)典算法和典型題例；每章均附有小結(jié)、習(xí)題和上機(jī)實(shí)驗(yàn)題；附錄給出了5套課程考試樣卷和5道課程設(shè)計(jì)題，以供教學(xué)參考?！　”窘滩墓卜?0章。第1章簡要介紹數(shù)據(jù)結(jié)構(gòu)和算法的基本概念；第2～5章介紹線性結(jié)構(gòu)及其算法，包括線性表、棧、隊(duì)列、串、數(shù)組和特殊矩陣；第6～8章介紹非線性結(jié)構(gòu)及其算法，包括廣義表、樹、二叉樹、圖；第9章介紹各種常用的查找算法；第10章介紹各種常用的排序算法?！　”咎捉滩脑趪乙?guī)劃教材的基礎(chǔ)上，進(jìn)行全面更新，以適應(yīng)高校課程與教學(xué)改革的需要，并特別注意教材的可讀性和可用性，為任課教師提供各種教學(xué)服務(wù)。

圖書封面

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

---

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

---