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

前言

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

內(nèi)容概要

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

書籍目錄

第一部分 理論知識第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 線性表的順序存儲結(jié)構(gòu)2.2.1 順序分配2.2.2 線性表的操作2.3 線性表的鏈式存儲結(jié)構(gòu)2.3.1 線性鏈表的實現(xiàn)2.3.2 線性鏈表的運算2.3.3 循環(huán)鏈表2.4 典型例題習(xí)題2第3章 棧和隊列3.1 堆棧3.1.1 堆棧的定義和基本操作3.1.2 順序存儲棧3.1.3 鏈式存儲棧3.2 隊列3.2.1 順序存儲隊列3.2.2 鏈式存儲隊列3.3 典型例題習(xí)題3第4章 字符串、數(shù)組和廣義表4.1 字符串基本概念4.2 字符串的存儲結(jié)構(gòu)4.2.1 串的順序存儲結(jié)構(gòu)4.2.2 串的鏈式存儲結(jié)構(gòu)4.3 字符串的模式匹配4.3.1 模式匹配的BF算法4.3.2 模式匹配的KMP算法4.4 數(shù)組的基本概念4.5 矩陣的壓縮存儲4.5.1 特殊矩陣的壓縮4.5.2 稀疏矩陣4.6 廣義表4.6.1 廣義表的存儲結(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 二叉樹的存儲結(jié)構(gòu)5.3 遍歷二叉樹5.3.1 遍歷二叉樹的方法5.3.2 遍歷二叉樹的函數(shù)5.4 線索二叉樹5.5 樹和森林5.5.1 樹的存儲結(jié)構(gòu)5.5.2 樹與二叉樹的轉(zhuǎn)換（通過二叉鏈表存儲聯(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 圖的存儲結(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 最小代價生成樹6.4.1 最小代價生成樹的概念6.4.2 構(gòu)造最小生成樹的PRIM算法6.5 最短路徑6.5.1 從某個頂點到其他頂點的最短路徑6.5.2 每一對頂點間的最短路徑6.6 拓撲排序6.7 典型例題習(xí)題6第7章 查找7.1 線性表的查找7.1.1 順序存儲線性表的查找7.1.2 分塊查找7.1.3 鏈式存儲線性表查找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 順序存儲線性表的直接插入排序8.2.2 鏈式存儲線性表的直接插入排序8.3 冒泡排序8.3.1 順序存儲線性表的冒泡排序8.3.2 鏈式存儲線性表的冒泡排序8.4 希爾排序8.5 堆排序8.6 快速排序8.7 合并排序8.8 典型例題習(xí)題8第二部分 實驗部分實驗一 時間復(fù)雜度的計算實驗二 順序存儲線性表的操作(1)實驗三 順序存儲線性表的操作(2)實驗四 鏈式存儲線性表的操作(1)實驗五 鏈式存儲線性表的操作(2)實驗六 鏈式存儲線性表的操作(3)實驗七 順序棧的操作實驗八 順序存儲隊列的進隊列和出隊列操作實驗九 字符串的操作實驗十 數(shù)組的操作實驗十一 廣義表的操作實驗十二 樹的操作實驗十三 圖的操作實驗十四 二分法查找的操作實驗十五 插入排序的操作實驗十六 選擇排序的操作實驗十七 快速排序的操作實驗十八 冒泡排序和希爾排序的操作參考文獻

章節(jié)摘錄

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

圖書封面

評論、評分、閱讀與下載

---

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

---