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

前言

“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)程序設(shè)計(jì)的重要基礎(chǔ)，也是計(jì)算機(jī)科學(xué)與技術(shù)等電子信息類相關(guān)專業(yè)的一門重要基礎(chǔ)課程。它對(duì)程序設(shè)計(jì)思想的建立和提升有著重要的作用，既為后續(xù)的計(jì)算機(jī)課程奠定了一個(gè)較為扎實(shí)的基礎(chǔ)，又可提高學(xué)生分析問題和解決問題的能力。本書作為2005年版《數(shù)據(jù)結(jié)構(gòu)》的第二版，保持了前一版的基本框架，概念清楚、論述充分、面向應(yīng)用，進(jìn)一步完善了算法與數(shù)據(jù)結(jié)構(gòu)體系的內(nèi)容，每章都增加了“典型例題”一節(jié)，并對(duì)實(shí)驗(yàn)部分進(jìn)行調(diào)整和補(bǔ)充。教材主要面向高職高專院校計(jì)算機(jī)科學(xué)與技術(shù)等電子信息類專業(yè)的學(xué)生。教材內(nèi)容以“實(shí)踐應(yīng)用”為主體，理論以“夠用”為尺度。全書共分理論知識(shí)和實(shí)驗(yàn)指導(dǎo)兩個(gè)部分，理論知識(shí)部分又分為八章：第1章，緒論；第2章，線性表；第3章，棧和隊(duì)列；第4章，字符串、數(shù)組和廣義表；第5章，樹；第6章，圖；第7章，查找；第8章，排序。實(shí)驗(yàn)部分精選18個(gè)典型實(shí)例以幫助學(xué)生鞏固所學(xué)知識(shí)。本教材有如下特點(diǎn)：（1）所有例題都包括示意圖、分析、流程圖和程序代碼四個(gè)部分，思路清晰，層次鮮明，能逐步培養(yǎng)和提高學(xué)生分析問題和解決問題的能力。本書每章均配有適量習(xí)題和實(shí)驗(yàn)，具有很強(qiáng)的針對(duì)性和可操作性。（2）以全國計(jì)算機(jī)程序員考試大綱為基準(zhǔn)，涉及考試的章節(jié)選用部分歷年試題作為示例，加強(qiáng)學(xué)生對(duì)所學(xué)內(nèi)容的進(jìn)一步理解、鞏固和應(yīng)用。（3）各章都配有“典型例題”一節(jié)，列舉分析了很多實(shí)用的例子，有助于學(xué)生加深對(duì)基礎(chǔ)理論知識(shí)的理解和實(shí)際應(yīng)用能力的培養(yǎng)。（4）本書的算法和實(shí)驗(yàn)程序用標(biāo)準(zhǔn)C語言函數(shù)實(shí)現(xiàn)，可直接在turbo C或Visual C++6.0環(huán)境下運(yùn)行。（5）為配合本教材的教學(xué)，還編制了多媒體課件，以加深對(duì)基本概念的理解。課件和習(xí)題答案，可通過E-mail（1aobaomd@163.com）向包振宇索取。建議本教材的理論教學(xué)時(shí)數(shù)為40學(xué)時(shí)，實(shí)驗(yàn)教學(xué)時(shí)數(shù)為30學(xué)時(shí)。本教材由包振宇、孫干、陳勇編著。其中，理論部分的第1～5章和實(shí)驗(yàn)部分由包振宇編寫，理論部分的第6、7章和習(xí)題部分由孫干編寫，理論部分的第8章由陳勇編寫，最后由包振宇完成全書統(tǒng)稿。周永華、朱其俊參與了編寫大綱的討論并編寫了初稿的部分內(nèi)容，陳剛、張琴、劉呈真、楊健等參與了全書的校訂工作，劉愛華、吳亮等在使用本書的過程中提出了一些修改建議，使得本書更加完善。本書在編寫和修訂過程中，得到了許多專家和眾多院校數(shù)據(jù)結(jié)構(gòu)任課教師的大力支持和幫助，他們提出了許多中肯的意見和很好的建議，對(duì)本書的編寫及修訂起到了很大的指導(dǎo)作用。編者對(duì)此表示衷心的感謝。

內(nèi)容概要

《數(shù)據(jù)結(jié)構(gòu)(第2版)》內(nèi)容以“實(shí)踐應(yīng)用”為主體，理論以“夠用”為尺度，理論與實(shí)驗(yàn)相結(jié)合。其內(nèi)容分為兩部分，包括理論知識(shí)部分與實(shí)驗(yàn)部分。本教材有如下特點(diǎn)：（1）所有例題都包括示意圖、分析、流程圖和程序代碼四個(gè)部分，思路清晰，層次鮮明，能逐步培養(yǎng)和提高學(xué)生分析問題和解決問題的能力。每章均配有適量習(xí)題和實(shí)驗(yàn)，具有很強(qiáng)的針對(duì)性和可操作性。（2）以全國計(jì)算機(jī)程序員考試大綱為基準(zhǔn)，涉及考試的章節(jié)選用部分歷年試題作為示例，以加強(qiáng)學(xué)生對(duì)所學(xué)內(nèi)容的進(jìn)一步理解、鞏固和應(yīng)用。（3）書中的算法和實(shí)驗(yàn)程序用標(biāo)準(zhǔn)C語言函數(shù)實(shí)現(xiàn)，可直接在Turbo C或Visual C抖6.0環(huán)境下運(yùn)行?！稊?shù)據(jù)結(jié)構(gòu)(第2版)》適合于高職高專院校計(jì)算機(jī)類專業(yè)的學(xué)生。

書籍目錄

第一部分 理論知識(shí)第1章 緒論1.1 數(shù)據(jù)結(jié)構(gòu)與算法1.1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念1.1.2 算法的概念和特性1.2 算法的描述和分析1.2.1 算法的描述1.2.2 算法的分析1.3 典型例題習(xí)題1第2章 線性表2.1 線性表的邏輯結(jié)構(gòu)2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)2.2.1 順序分配2.2.2 線性表的操作2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.3.1 線性鏈表的實(shí)現(xiàn)2.3.2 線性鏈表的運(yùn)算2.3.3 循環(huán)鏈表2.4 典型例題習(xí)題2第3章 棧和隊(duì)列3.1 堆棧3.1.1 堆棧的定義和基本操作3.1.2 順序存儲(chǔ)棧3.1.3 鏈?zhǔn)酱鎯?chǔ)棧3.2 隊(duì)列3.2.1 順序存儲(chǔ)隊(duì)列3.2.2 鏈?zhǔn)酱鎯?chǔ)隊(duì)列3.3 典型例題習(xí)題3第4章 字符串、數(shù)組和廣義表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 模式匹配的BF算法4.3.2 模式匹配的KMP算法4.4 數(shù)組的基本概念4.5 矩陣的壓縮存儲(chǔ)4.5.1 特殊矩陣的壓縮4.5.2 稀疏矩陣4.6 廣義表4.6.1 廣義表的存儲(chǔ)結(jié)構(gòu)4.6.2 綜合舉例4.7 典型例題習(xí)題4第5章 樹5.1 樹的定義和術(shù)語5.1.1 樹的定義5.1.2 樹的基本術(shù)語5.2 二叉樹5.2.1 二叉樹的定義和性質(zhì)5.2.2 二叉樹的存儲(chǔ)結(jié)構(gòu)5.3 遍歷二叉樹5.3.1 遍歷二叉樹的方法5.3.2 遍歷二叉樹的函數(shù)5.4 線索二叉樹5.5 樹和森林5.5.1 樹的存儲(chǔ)結(jié)構(gòu)5.5.2 樹與二叉樹的轉(zhuǎn)換（通過二叉鏈表存儲(chǔ)聯(lián)系）5.6 樹的應(yīng)用5.6.1 二叉排序樹5.6.2 哈夫曼樹5.7 典型例題習(xí)題5第6章 圖6.1 圖的基本概念6.1.1 圖的定義6.1.2 圖的相關(guān)術(shù)語6.2 圖的存儲(chǔ)結(jié)構(gòu)6.2.1 鄰接矩陣6.2.2 鄰接表6.3 圖的遍歷6.3.1 深度優(yōu)先搜索(DFS)6.3.2 廣度優(yōu)先搜索(BFS)6.4 最小代價(jià)生成樹6.4.1 最小代價(jià)生成樹的概念6.4.2 構(gòu)造最小生成樹的PRIM算法6.5 最短路徑6.5.1 從某個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑6.5.2 每一對(duì)頂點(diǎn)間的最短路徑6.6 拓?fù)渑判?.7 典型例題習(xí)題6第7章 查找7.1 線性表的查找7.1.1 順序存儲(chǔ)線性表的查找7.1.2 分塊查找7.1.3 鏈?zhǔn)酱鎯?chǔ)線性表查找7.2 樹的查找7.2.1 二叉樹查找7.2.2 平衡二叉樹7.2.3 B樹7.3 哈希表及其查找7.3.1 哈希表7.3.2 常見的散列函數(shù)7.3.3 解決沖突的方法7.4 典型例題習(xí)題7第8章 排序8.1 選擇排序8.2 直接插入排序8.2.1 順序存儲(chǔ)線性表的直接插入排序8.2.2 鏈?zhǔn)酱鎯?chǔ)線性表的直接插入排序8.3 冒泡排序8.3.1 順序存儲(chǔ)線性表的冒泡排序8.3.2 鏈?zhǔn)酱鎯?chǔ)線性表的冒泡排序8.4 希爾排序8.5 堆排序8.6 快速排序8.7 合并排序8.8 典型例題習(xí)題8第二部分 實(shí)驗(yàn)部分實(shí)驗(yàn)一 時(shí)間復(fù)雜度的計(jì)算實(shí)驗(yàn)二 順序存儲(chǔ)線性表的操作(1)實(shí)驗(yàn)三 順序存儲(chǔ)線性表的操作(2)實(shí)驗(yàn)四 鏈?zhǔn)酱鎯?chǔ)線性表的操作(1)實(shí)驗(yàn)五 鏈?zhǔn)酱鎯?chǔ)線性表的操作(2)實(shí)驗(yàn)六 鏈?zhǔn)酱鎯?chǔ)線性表的操作(3)實(shí)驗(yàn)七 順序棧的操作實(shí)驗(yàn)八 順序存儲(chǔ)隊(duì)列的進(jìn)隊(duì)列和出隊(duì)列操作實(shí)驗(yàn)九 字符串的操作實(shí)驗(yàn)十 數(shù)組的操作實(shí)驗(yàn)十一 廣義表的操作實(shí)驗(yàn)十二 樹的操作實(shí)驗(yàn)十三 圖的操作實(shí)驗(yàn)十四 二分法查找的操作實(shí)驗(yàn)十五 插入排序的操作實(shí)驗(yàn)十六 選擇排序的操作實(shí)驗(yàn)十七 快速排序的操作實(shí)驗(yàn)十八 冒泡排序和希爾排序的操作參考文獻(xiàn)

章節(jié)摘錄

插圖：第1章 緒論“數(shù)據(jù)結(jié)構(gòu)”形成和發(fā)展的背景：自1946年第一臺(tái)計(jì)算機(jī)問世以來，計(jì)算機(jī)已深入到人類社會(huì)的各個(gè)領(lǐng)域，計(jì)算機(jī)的應(yīng)用已不再局限于科學(xué)計(jì)算，而更多地用于控制、管理及信息處理等非數(shù)值計(jì)算的工作。計(jì)算機(jī)加工處理的對(duì)象由純粹的數(shù)值發(fā)展到字符、表格、圖像、聲音等各種具有一定結(jié)構(gòu)的數(shù)據(jù)，這就給程序設(shè)計(jì)帶來一些新的問題。為編寫出一個(gè)“好”的程序，必須分析待處理的對(duì)象的特性以及各處理對(duì)象之間存在的關(guān)系。這就是“數(shù)據(jù)結(jié)構(gòu)”這門學(xué)科形成和發(fā)展的背景。1.1 數(shù)據(jù)結(jié)構(gòu)與算法1.1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念1.數(shù)據(jù)對(duì)現(xiàn)實(shí)世界的事物采用計(jì)算機(jī)能識(shí)別、存儲(chǔ)和處理的形式所進(jìn)行的描述。簡言之，數(shù)據(jù)是計(jì)算機(jī)程序能加工和處理的對(duì)象，也就是計(jì)算機(jī)化的信息。2.數(shù)據(jù)元素?cái)?shù)據(jù)的基本單位，又稱為結(jié)點(diǎn)。在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。有時(shí)一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。如一的書目信息為一個(gè)數(shù)據(jù)元素，而書目信息中的每一項(xiàng)（如書名、作者名等）為一個(gè)數(shù)據(jù)項(xiàng)。數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單元。3.數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。4.數(shù)據(jù)結(jié)構(gòu)（1）相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)對(duì)象及其相互關(guān)系和構(gòu)造方法。一個(gè)數(shù)據(jù)結(jié)構(gòu)Ds可以被形象地用一個(gè)二元組表示為：DS=（D，R）。其中，D是數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)（稱為結(jié)點(diǎn)）的非空集，R是定義在D上的關(guān)系的非空有限集合。結(jié)構(gòu)是指結(jié)點(diǎn)之間的關(guān)系，數(shù)據(jù)結(jié)構(gòu)就是結(jié)點(diǎn)的有限集合和關(guān)系的有限集合。（2）數(shù)據(jù)結(jié)構(gòu)中，結(jié)點(diǎn)及結(jié)點(diǎn)間的相互關(guān)系是數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)內(nèi)容，一般包括結(jié)點(diǎn)的值和結(jié)點(diǎn)間的關(guān)系，數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)形式是數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（或物理結(jié)構(gòu)）。（3）數(shù)據(jù)結(jié)構(gòu)按邏輯關(guān)系的不同分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類，其中非線性結(jié)構(gòu)又分為樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)，而樹形結(jié)構(gòu)又可分為樹結(jié)構(gòu)和二叉樹結(jié)構(gòu)。

編輯推薦

《數(shù)據(jù)結(jié)構(gòu)(第2版)》為中國鐵道出版社出版。

圖書封面

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

---

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

---