本書系統(tǒng)地介紹了數(shù)據(jù)結構與算法的基本知識。第1章介紹了數(shù)據(jù)結構和算法相關的概念,并介紹了本書配套的考試軟件的使用方法。第2章~第7章按照邏輯結構對數(shù)據(jù)結構進行了分類,具體分為線性表、棧和隊列、字符串、數(shù)組和廣義表、樹和二叉樹、圖;在介紹每種數(shù)據(jù)結構的時候又按照不同的存儲結構分別進行了介紹,同時介紹了各種運算在具體存儲結構中的實現(xiàn)方法,并給出了用C語言實現(xiàn)的算法描述,這樣就形成了邏輯結構、存儲結構及運算一致的數(shù)據(jù)結構的學習思路,極其有利于初學者學習。第8章和第9章分別介紹了常用的查找和排序算法。本書可以作為高等院校計算機相關專業(yè)的教材,也可以作為從事計算機應用開發(fā)人員的參考用書。
本書按照邏輯結構對數(shù)據(jù)結構進行了分類,具體分為線性表、棧和隊列、字符串、數(shù)組和廣義表、樹和二叉樹、圖。內容講解通俗易懂,全部源程序均已調試通過。本書包含配套學習及考試系統(tǒng),對課程的考試形式進行了較大的改革,把期末考試改變?yōu)榘凑鹿?jié)考試,即學完一章后就可進行考試。本書除了包含配套考試系統(tǒng)外,還配有算法演示軟件,該軟件能夠演示本課程中的常用算法?呻S機生成一個數(shù)據(jù)系列,并單步演示算法的執(zhí)行過程。教師能夠在演示的過程中講解算法的執(zhí)行流程,學生也能夠通過算法演示過程理解算法。
唐名華,廣東金融學院計算機學院副教授。先后承擔了《數(shù)據(jù)結構》、《操作系統(tǒng)原理》、《高級語言程序設計》和《多媒體技術》等課程。主要致力于計算智能、數(shù)據(jù)挖掘理論與應用、智能機器人技術等方向的研究。主持多項廣東省科技計劃項目、廣東省教育廳科技創(chuàng)新項目等。獲得市科技進步獎3項,申請發(fā)明專利2項,軟件著作版權2項。指導學生參加全國機器人大賽,累計獲得冠軍1項、季軍1項、一等獎6項、二等獎6項、三等獎8項;指導學生參加廣東省軟件作品大賽獲得一等獎。指導學生參加全國大學生數(shù)據(jù)挖掘競賽獲得二等獎。
目 錄第1章 緒論11.1 數(shù)據(jù)結構的基本概念11.1.1 數(shù)據(jù)結構的研究對象11.1.2 數(shù)據(jù)結構的研究內容21.1.3 數(shù)據(jù)結構的表示方法51.2 算法與算法分析61.2.1 算法的概念61.2.2 算法的描述方法61.2.3 算法分析71.2.4 常用算法設計方法81.3 數(shù)據(jù)結構和算法的學習與考試軟件91.3.1 教師端91.3.2 學生端12習題13第2章 線性表152.1 線性表的邏輯結構152.1.1 線性表的引出152.1.2 線性表的邏輯結構162.1.3 線性表的運算162.2 線性表的順序存儲結構—順序表172.2.1 順序表的概念172.2.2 順序表的運算182.2.3 順序表的特點222.3 線性表的鏈式存儲結構—鏈表222.3.1 鏈表的概念222.3.2 鏈表的運算232.4 循環(huán)鏈表和雙向鏈表302.4.1 循環(huán)鏈表302.4.2 雙向鏈表31習題33第3章 棧和隊列353.1 棧353.1.1 棧的基本概念353.1.2 棧的順序存儲結構—順序棧363.1.3 棧的鏈式存儲結構—鏈棧383.2 棧的應用403.2.1 表達式求值413.2.2 棧與遞歸433.3 隊列453.3.1 隊列的基本概念453.3.2 隊列的順序存儲結構—順序隊列453.3.3 隊列的鏈式存儲結構—鏈式隊列483.3.4 循環(huán)隊列503.4 隊列的應用52習題53第4章 字符串554.1 字符串概述554.2 字符串的存儲結構564.2.1 字符串的順序存儲結構564.2.2 字符串的鏈式存儲結構564.3 字符串的運算57習題63第5章 數(shù)組和廣義表645.1 數(shù)組645.1.1 多維數(shù)組的順序存儲645.1.2 特殊矩陣的壓縮存儲655.2 廣義表725.2.1 廣義表的概念725.2.2 廣義表的存儲735.2.3 廣義表的運算75習題76第6章 樹和二叉樹786.1 樹786.1.1 樹的基本概念786.1.2 樹的運算806.2 二叉樹806.2.1 二叉樹的基本概念806.2.2 二叉樹的性質826.2.3 二叉樹的存儲結構836.2.4 二叉樹的運算856.3 特殊的二叉樹896.3.1 線索二叉樹896.3.2 二叉排序樹926.3.3 最優(yōu)二叉樹1006.3.4 堆1046.4 樹的存儲結構與運算1096.4.1 樹的存儲結構1096.4.2 樹的運算1116.5 森林1146.5.1 森林與二叉樹的轉換1146.5.2 森林的遍歷115習題115第7章 圖1167.1 概述1167.1.1 圖的相關概念1167.1.2 圖的連通性1177.1.3 圖的基本操作1187.2 圖的存儲結構1197.2.1 圖的鄰接矩陣表示1197.2.2 圖的鄰接表表示1227.2.3 圖的邊集數(shù)組表示1297.2.4 圖的十字鏈表表示1297.3 圖的遍歷1307.3.1 圖的深度優(yōu)先遍歷1317.3.2 圖的廣度優(yōu)先遍歷1327.4 最小生成樹1347.4.1 圖的生成樹1347.4.2 普里姆算法1347.4.3 克魯斯卡爾算法1377.5 最短路徑問題1407.5.1 單源最短路徑1407.5.2 全源最短路徑1427.6 有向無環(huán)圖1457.6.1 拓撲排序1457.6.2 關鍵路徑147習題150第8章 查找1528.1 線性查找表1528.1.1 順序查找1528.1.2 折半查找1538.1.3 斐波那契查找1548.1.4 分塊查找1568.2 二叉排序樹1578.2.1 二叉排序樹的查找性能1578.2.2 平衡二叉樹1588.3 B-樹1618.3.1 B-樹的概念1618.3.2 B-樹的查找1628.3.3 B-樹的插入1628.3.4 B-樹的刪除1638.4 哈希查找1658.4.1 哈希表查找1658.4.2 哈希函數(shù)1668.4.3 沖突處理1688.4.4 哈希查找的性能170習題171第9章 排序1729.1 基本概念1729.2 簡單排序方法1739.2.1 選擇排序1739.2.2 插入排序1749.2.3 冒泡排序1779.3 快速排序1799.4 堆排序1819.5 歸并排序1839.5.1 歸并1839.5.2 歸并排序過程1849.6 基數(shù)排序1859.7 內部排序算法性能比較1879.8 外部排序188習題188附錄A 習題參考答案189