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

內(nèi)容概要

　　《數(shù)據(jù)結(jié)構(gòu)（C++版）》通過(guò)架構(gòu)清晰和易懂的表達(dá)方式將數(shù)據(jù)結(jié)構(gòu)中各種算法作最詳盡的詮釋與舉例，并利用完整的C++程序設(shè)計(jì)將各種理論加以實(shí)踐。　　全書共9章，包括數(shù)據(jù)結(jié)構(gòu)概述、數(shù)組和稀疏矩陣、鏈表、堆棧、隊(duì)列、樹、圖、排序、查找。為了將算法講解的清晰易懂，《數(shù)據(jù)結(jié)構(gòu)（C++版）》不盡以偽代碼來(lái)說(shuō)明，而是利用C++語(yǔ)言來(lái)展現(xiàn)，同時(shí)，書中的重要理論均輔以范例程序，從而透徹理解原理的精髓。為了驗(yàn)收各章的學(xué)習(xí)成果，章后附加重點(diǎn)整理和習(xí)題，提供更多實(shí)戰(zhàn)演練的機(jī)會(huì)?！　　稊?shù)據(jù)結(jié)構(gòu)（C++版）》適合作為計(jì)算機(jī)專業(yè)和信息專業(yè)本、?？粕臄?shù)據(jù)結(jié)構(gòu)教材，也可作為參加自學(xué)考試人員和計(jì)算機(jī)應(yīng)用技術(shù)人員的自學(xué)參考書。

書籍目錄

第1章 數(shù)據(jù)結(jié)構(gòu)概述1.1 數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介1.1.1 數(shù)據(jù)與信息1.1.2 算法1.2 程序設(shè)計(jì)簡(jiǎn)介1.2.1 程序開發(fā)流程1.2.2 結(jié)構(gòu)化程序設(shè)計(jì)1.2.3 面向?qū)ο蟪绦蛟O(shè)計(jì)1.2.4 數(shù)據(jù)類型1.3 面向?qū)ο蟮母拍钆cC++語(yǔ)言1.3.1 C++語(yǔ)言1.3.2 類1.3.3 繼承1.3.4 多態(tài)1.4 算法效率的分析1.4.1 大O1.4.2 大Q1.4.3 大θ重點(diǎn)整理本章習(xí)題第2章 數(shù)組和稀疏矩陣2.1 線性表2.1.1 線性表的定義2.1.2 線性表的應(yīng)用2.2 數(shù)組簡(jiǎn)介2.2.1 一維數(shù)組2.2.2 二維數(shù)組2.2.3 三維數(shù)組2.2.4 n維數(shù)組2.3 矩陣簡(jiǎn)介與運(yùn)算2.3.1 矩陣相加2.3.2 矩陣相乘2.3.3 轉(zhuǎn)置矩陣2.3.4 稀疏矩陣2.3.5 上三角形矩陣2.3.6 下三角形矩陣2.3.7 帶狀矩陣2.4 數(shù)組與多項(xiàng)式2.4.1 多項(xiàng)式簡(jiǎn)介2.4.2 多項(xiàng)式的加法重點(diǎn)整理本章習(xí)題第3章 鏈表3.1 指針簡(jiǎn)介3.1.1 指針聲明3.1.2 動(dòng)態(tài)內(nèi)存分配3.1.3 C++語(yǔ)言中的動(dòng)態(tài)分配與釋放3.2 單鏈表3.2.1 單鏈表的建立3.2.2 單鏈表的結(jié)點(diǎn)刪除3.2.3 單鏈表的結(jié)點(diǎn)插入3.2.4 單鏈表的反轉(zhuǎn)3.2.5 單鏈表的連接3.2.6 多項(xiàng)式的表示法3.3 循環(huán)鏈表3.3.1 循環(huán)鏈表的定義3.3.2 循環(huán)鏈表的結(jié)點(diǎn)插入3.3.3 循環(huán)鏈表的結(jié)點(diǎn)刪除3.3.4 循環(huán)鏈表的連接3.3.5 循環(huán)鏈表與稀疏矩陣的表示法3.4 雙向鏈表3.4.1 雙向鏈表的定義3.4.2 雙向鏈表的結(jié)點(diǎn)插入3.4.3 雙向鏈表的結(jié)點(diǎn)刪除重點(diǎn)整理本章習(xí)題第4章 堆棧4.1 堆棧簡(jiǎn)介4.1.1 堆棧的工作原理4.1.2 堆棧的隊(duì)列實(shí)現(xiàn)4.1.3 堆棧的鏈表實(shí)現(xiàn)4.2 堆棧的應(yīng)用4.2.1 遞歸4.2.2 河內(nèi)塔問(wèn)題4.2.3 迷宮問(wèn)題4.2.4 八皇后問(wèn)題4.3 算術(shù)表達(dá)式的求值4.3.1 中序表示法求值4.3.2 前序表示法求值4.3.3 后序表示法求值4.4 中序表達(dá)式轉(zhuǎn)換成前序和后序表達(dá)式4.4.1 二叉樹法4.4.2 括號(hào)法4.4.3 堆棧法4.5 前序和后序表達(dá)式轉(zhuǎn)換成中序表達(dá)式4.5.1 括號(hào)法4.5.2 堆棧法重點(diǎn)整理本章習(xí)題第5章 隊(duì)列5.1 隊(duì)列簡(jiǎn)介5.1.1 隊(duì)列的基本操作5.1.2 隊(duì)列的數(shù)組實(shí)現(xiàn)5.1.3 隊(duì)列的鏈表實(shí)現(xiàn)5.2 隊(duì)列的應(yīng)用5.2.1 循環(huán)隊(duì)列5.2.2 優(yōu)先隊(duì)列5.2.3 雙向隊(duì)列重點(diǎn)整理本章習(xí)題第6章 樹6.1 樹簡(jiǎn)介6.2 二叉樹簡(jiǎn)介6.2.1 二叉樹的定義6.2.2 特殊二叉樹的介紹6.3 二叉樹的存儲(chǔ)方式6.3.1 二叉樹的數(shù)組表示法6.3.2 二叉樹的鏈表表示法6.4 二叉樹的遍歷6.4.1 中序遍歷6.4.2 前序遍歷6.4.3 后序遍歷6.4.4 二叉樹的遍歷實(shí)例6.4.5 二元運(yùn)算樹6.5 二叉樹的深入研究6.5.1 排序二叉樹6.5.2 線索二叉樹6.5.3 索引二叉樹6.6 樹的二叉樹表示法6.6.1 樹轉(zhuǎn)換成二叉樹6.6.2 二叉樹轉(zhuǎn)換成樹6.6.3 森林轉(zhuǎn)換成二叉樹6.6.4 二叉樹轉(zhuǎn)換成森林6.6.5 樹與森林的遍歷6.6.6 確定惟一二叉樹重點(diǎn)整理本章習(xí)題第7章 圖7.1 圖的簡(jiǎn)介7.1.1 圖的起源7.1.2 圖的名詞術(shù)語(yǔ)7.2 圖的表示法7.2.1 鄰接矩陣法7.2.2 鄰接表法7.2.3 多重鄰接鏈表法7.2.4 標(biāo)記法7.3 圖的遍歷7.3.1 深度優(yōu)先法7.3.2 廣度優(yōu)先法7.4 生成樹7.5 最小生成樹7.5.1 Prim算法7.5.2 Kruskal算法7.6 圖的最短路徑7.6.1 單點(diǎn)對(duì)全部頂點(diǎn)的最短路徑7.6.2 頂點(diǎn)之間的最短路徑7.7 AOV網(wǎng)絡(luò)與拓?fù)渑判?.7.1 拓?fù)渑判?.7.2 AOE網(wǎng)絡(luò)重點(diǎn)整理本章習(xí)題第8章 排序8.1 排序簡(jiǎn)介8.1.1 排序的分類8.1.2 排序算法的分析8.2 內(nèi)部排序法8.2.1 冒泡排序法8.2.2 選擇排序法8.2.3 插入排序法8.2.4 希爾排序法8.2.5 合并排序法8.2.6 快速排序法8.2.7 堆排序法8.2.8 基數(shù)排序法8.3 外部排序法8.3.1 直接合并排序法8.3.2 K-路合并法8.3.3 多相合并法重點(diǎn)整理本章習(xí)題第9章 查找9.1 查找簡(jiǎn)介9.2 常見的查找方法9.2.1 順序查找法9.2.2 二分查找法9.2.3 插值查找法9.2.4 斐波納契查找法9.2.5 哈希查找法重點(diǎn)整理本章習(xí)題

章節(jié)摘錄

　　第1章 數(shù)據(jù)結(jié)構(gòu)概述　　對(duì)于一個(gè)有志于從事IT專業(yè)技術(shù)的人士來(lái)說(shuō)，數(shù)據(jù)結(jié)構(gòu)（Data Structure）是一門與計(jì)算機(jī)軟件和硬件都密切相關(guān)的學(xué)科，其中包含了算法（Algorithm）、數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)、排序、搜索、哈希函數(shù)與程序設(shè)計(jì)等概念?！　?.1　數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介　　數(shù)據(jù)結(jié)構(gòu)可以看成是在數(shù)據(jù)處理過(guò)程中用于分析、組織數(shù)據(jù)的方法和操作邏輯，它主要關(guān)注數(shù)據(jù)間的特性與相互關(guān)系?！　≡诂F(xiàn)代社會(huì)中，計(jì)算機(jī)與信息緊密相關(guān)，由于計(jì)算機(jī)具有處理速度快與存儲(chǔ)容量大的兩大特點(diǎn)（如圖1.1所示），因此在數(shù)據(jù)處理的過(guò)程中具有舉足輕重的作用?！　?shù)據(jù)結(jié)構(gòu)是用計(jì)算機(jī)進(jìn)行數(shù)據(jù)處理的一套完整邏輯。程序設(shè)計(jì)者必須選擇一種數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行數(shù)據(jù)的增加、修改、刪除、保存等操作，如果在選擇數(shù)據(jù)結(jié)構(gòu)時(shí)作了錯(cuò)誤的決定，程序的執(zhí)行速度可能變得非常低，如果選錯(cuò)了數(shù)據(jù)類型，后果更是不堪設(shè)想?！　∫虼水?dāng)用計(jì)算機(jī)解決問(wèn)題時(shí)，必須以計(jì)算機(jī)所能接受的模式來(lái)認(rèn)識(shí)問(wèn)題，并設(shè)計(jì)適當(dāng)?shù)乃惴ㄈヌ幚頂?shù)據(jù)，這是數(shù)據(jù)結(jié)構(gòu)討論的重點(diǎn)。簡(jiǎn)單地說(shuō)，數(shù)據(jù)結(jié)構(gòu)就是對(duì)數(shù)據(jù)與算法結(jié)構(gòu)的研究。　　1.1.1　數(shù)據(jù)與信息　　談到數(shù)據(jù)結(jié)構(gòu)，首先必須了解什么是數(shù)據(jù)（Data）與信息（Information）。從字義上來(lái)看，數(shù)據(jù)是指未經(jīng)加工過(guò)的文字（Word）、數(shù)字（Number）、符號(hào)（Symbol）或圖形（Graph）等，它表達(dá)的是沒(méi)有什么利用價(jià)值的基本元素或?qū)ο螅缧彰?、課程表、通信錄等都可泛泛地稱為“數(shù)據(jù)”（Data）。　　當(dāng)數(shù)據(jù)經(jīng)過(guò)處理（Process），例如以特定的方式進(jìn)行系統(tǒng)地整理、歸納甚至統(tǒng)計(jì)分析后就成為信息（Information）。而這樣處理的過(guò)程就稱為“數(shù)據(jù)處理”（Data Processing）?！　膰?yán)謹(jǐn)?shù)慕嵌葋?lái)形容“數(shù)據(jù)處理”就是用人力或機(jī)器設(shè)備對(duì)數(shù)據(jù)進(jìn)行系統(tǒng)的整理，如記錄、排序、合并、整合、計(jì)算、統(tǒng)計(jì)等，以使原始的數(shù)據(jù)符合需求而成為有用的信息。數(shù)據(jù)處理過(guò)程如圖1.2所示?！　∮械淖x者可能會(huì)有疑問(wèn)：“數(shù)據(jù)和信息的角色是否絕對(duì)一成不變呢？”這也不一定，同一份文件可能在某種狀況下為數(shù)據(jù)，而在另一種狀況下則為信息。例如美伊戰(zhàn)爭(zhēng)的某戰(zhàn)役死傷人數(shù)報(bào)告，對(duì)你我這樣的平民百姓而言，可能只是一份“數(shù)據(jù)”，不過(guò)對(duì)于英美聯(lián)軍的指揮官而言可就是彌足珍貴的“信息”。　　1.1.2　算法　　數(shù)據(jù)結(jié)構(gòu)與算法是程序設(shè)計(jì)的核心。程序能否快速而有效地完成預(yù)定的任務(wù)取決于數(shù)據(jù)結(jié)構(gòu)，而程序是否能清楚而正確地把問(wèn)題解決則取決于算法，所以可以這么認(rèn)為：“數(shù)據(jù)結(jié)構(gòu)+算法=可執(zhí)行的程序”，如圖1.3所示?！　≡陧f氏辭典中算法被定義為：“在有限步驟內(nèi)解決數(shù)學(xué)問(wèn)題的程序?！比绻迷谟?jì)算機(jī)領(lǐng)域中，也可以把算法定義成：“為了解決某一個(gè)工作或問(wèn)題所需要有限數(shù)目的機(jī)械性或重復(fù)性指令與計(jì)算步驟”?！　≡谌粘Ｉ钪杏性S多工作都可以利用算法來(lái)描述，例如員工的工作報(bào)告、寵物的飼養(yǎng)過(guò)程、學(xué)生的功課表等。　　當(dāng)了解了算法的定義后，需要說(shuō)明計(jì)算機(jī)算法所必須符合的5個(gè)特性，如圖1.4所示。以上5個(gè)特性的說(shuō)明如表1.1所示?！　〗酉聛?lái)要考慮的是如何描述一個(gè)算法。其實(shí)算法描述的主要目的是讓人們了解算法的流程與步驟，只要能清楚地表現(xiàn)算法的5項(xiàng)特性即可。常用的算法描述如下?！　?.一般文字　　一般文字采用中文、英文、數(shù)字等進(jìn)行描述。文字?jǐn)⑹龇ǖ奶厣谟谑褂梦淖只蛘Z(yǔ)言敘述來(lái)說(shuō)明演算步驟。圖1.5就是一名學(xué)生小華早上上學(xué)并買早餐的簡(jiǎn)單文字算法。

編輯推薦

　　《數(shù)據(jù)結(jié)構(gòu)（C++版）》將各種數(shù)據(jù)結(jié)構(gòu)的重要理論、算法作最詳實(shí)的詮釋，大量的圖解說(shuō)明降低學(xué)習(xí)難度，完整的范例程序?qū)⒗碚摷右詫?shí)踐。書中所有的算法均以C++程序語(yǔ)言描述，藉此加深學(xué)習(xí)理解，促進(jìn)學(xué)用結(jié)合，提高軟件開發(fā)能力。全書共9章，內(nèi)容包括數(shù)據(jù)結(jié)構(gòu)概述、數(shù)組和稀疏矩陣、鏈表、堆棧、隊(duì)列、樹、圖、排序、查找。

圖書封面

圖書標(biāo)簽Tags

無(wú)

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

---

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

---