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

前言

　　自20世紀(jì)70年代以來(lái)，數(shù)據(jù)結(jié)構(gòu)開(kāi)始成為計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的核心課程。最近十幾年來(lái)，數(shù)據(jù)結(jié)構(gòu)與算法在計(jì)算學(xué)科的4個(gè)主要分支：計(jì)算機(jī)科學(xué)（CS）、計(jì)算機(jī)工程（CE）、軟件工程（SE）和信息系統(tǒng)（IS）中的地位越來(lái)越重要了，這一點(diǎn)可以從ACM和IEEE／CS的“Computing Curricula 1991”和“Computing Curricula 2001”中體現(xiàn)出來(lái)。　　目前，計(jì)算機(jī)應(yīng)用已經(jīng)幾乎滲透到人們活動(dòng)的所有領(lǐng)域。由于高級(jí)程序設(shè)計(jì)語(yǔ)言和編程工具的推出和普遍使用，為各行各業(yè)的人員學(xué)習(xí)程序設(shè)計(jì)提供了可行的條件。現(xiàn)在為計(jì)算機(jī)編寫(xiě)程序已經(jīng)不僅僅是計(jì)算機(jī)專業(yè)人員的工作，各行各業(yè)的專家都在開(kāi)發(fā)本行業(yè)的應(yīng)用軟件。因此，數(shù)據(jù)結(jié)構(gòu)與算法課程早已不僅僅是計(jì)算機(jī)專業(yè)獨(dú)有的課程，本書(shū)是為所有需要學(xué)習(xí)計(jì)算機(jī)程序設(shè)計(jì)技術(shù)的計(jì)算機(jī)專業(yè)和與計(jì)算機(jī)相關(guān)專業(yè)的讀者編寫(xiě)的?！　?shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)是程序設(shè)計(jì)的核心，二者密不可分。事實(shí)上，過(guò)去所有的數(shù)據(jù)結(jié)構(gòu)教材都包含一定的算法方面的內(nèi)容，最常見(jiàn)的是查找與排序算法以及一些圖論問(wèn)題（如圖的連通性、最小生成樹(shù)、最短路徑等）。最近十年，情況有所變化，有關(guān)算法設(shè)計(jì)與分析的知識(shí)和技術(shù)受到更多的重視。國(guó)內(nèi)外出現(xiàn)了許多新的教材，例如“Data Structures andAlgorithmAnalysis”等，與一般的數(shù)據(jù)結(jié)構(gòu)教材相比，新教材增加了更多的算法方面的內(nèi)容，這種趨勢(shì)是很明顯的。本書(shū)的編寫(xiě)正是適應(yīng)了這種形勢(shì)，我們參閱了國(guó)內(nèi)外經(jīng)典著作和最新教材，結(jié)合編者多年講授算法、數(shù)據(jù)結(jié)構(gòu)和程序設(shè)計(jì)課程的經(jīng)驗(yàn)，力求在內(nèi)容方面深入淺出，既先進(jìn)、嚴(yán)謹(jǐn)，又通俗易懂，希望能受到我國(guó)相關(guān)專業(yè)的老師和同學(xué)的歡迎?！　　皵?shù)據(jù)結(jié)構(gòu)與算法”是為學(xué)習(xí)了一種程序設(shè)計(jì)語(yǔ)言的讀者編寫(xiě)的。掌握了初步的程序設(shè)計(jì)方法之后，面對(duì)實(shí)際的應(yīng)用問(wèn)題，最重要的就是學(xué)習(xí)如何選擇和設(shè)計(jì)有效的數(shù)據(jù)結(jié)構(gòu)和算法。編寫(xiě)程序的目的是解決問(wèn)題，而問(wèn)題的求解過(guò)程就是對(duì)于數(shù)據(jù)的組織和處理的過(guò)程，數(shù)據(jù)的組織方法是數(shù)據(jù)結(jié)構(gòu)部分的基本內(nèi)容，數(shù)據(jù)的處理方法是算法部分的基本內(nèi)容，二者是相輔相成的。本書(shū)全面地介紹了解決從簡(jiǎn)單到復(fù)雜的各種應(yīng)用問(wèn)題的數(shù)據(jù)結(jié)構(gòu)及其編程實(shí)現(xiàn)方法，包括較為簡(jiǎn)單的線性表、棧、隊(duì)列、數(shù)組和較為復(fù)雜的樹(shù)結(jié)構(gòu)與圖。對(duì)于算法的分析與設(shè)計(jì)技術(shù)，本書(shū)把重點(diǎn)放在介紹各種算法的設(shè)計(jì)方法，一方面介紹了與數(shù)據(jù)結(jié)構(gòu)相關(guān)的算法，例如查找算法、排序算法和圖論算法；另一方面則介紹了諸如分治、貪心、動(dòng)態(tài)規(guī)劃等常用的算法設(shè)計(jì)策略，這部分內(nèi)容，過(guò)去屬于研究生學(xué)習(xí)的范圍，特別是第9章，篇幅不大，但內(nèi)容較多、較深，本科生學(xué)習(xí)可能會(huì)有一定難度，教師在講授中可以適當(dāng)取舍。

內(nèi)容概要

　　《數(shù)據(jù)結(jié)構(gòu)與算法》是數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)的教材，其宗旨是將數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)有機(jī)地結(jié)合起來(lái)，向讀者系統(tǒng)介紹了數(shù)據(jù)結(jié)構(gòu)的基本概念及主要的算法設(shè)計(jì)方法。全書(shū)共分9章，第1章介紹了數(shù)據(jù)結(jié)構(gòu)的基本概念，第3～8章分別介紹了線性表、串、棧、隊(duì)列和數(shù)組、樹(shù)結(jié)構(gòu)和圖結(jié)構(gòu)以及查找和排序等數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識(shí)，在第2章簡(jiǎn)單介紹算法概念的基礎(chǔ)上，第9章詳細(xì)介紹了幾種算法的設(shè)計(jì)方法，并給出實(shí)例具體說(shuō)明設(shè)計(jì)過(guò)程。書(shū)中主要算法都用C++語(yǔ)言寫(xiě)出，并給出了詳細(xì)的注解?！稊?shù)據(jù)結(jié)構(gòu)與算法》概念清楚，選材精練，敘述深入淺出，用了大量的例子和圖表來(lái)說(shuō)明基本概念和方法，直觀易懂。每章后面都附有習(xí)題，讀者可以通過(guò)習(xí)題復(fù)習(xí)和檢驗(yàn)所學(xué)知識(shí)?！稊?shù)據(jù)結(jié)構(gòu)與算法》可以作為高等院校理工科學(xué)生的教材，也可以作為廣大計(jì)算機(jī)科學(xué)與工程領(lǐng)域從業(yè)人員的參考書(shū)。

作者簡(jiǎn)介

　　辛運(yùn)幃，1965年生。1986年畢業(yè)于南開(kāi)大學(xué)計(jì)算機(jī)與系統(tǒng)科學(xué)系，并留校任教。曾先后從師于陳有祺教授、盧桂章教授，并獲得工學(xué)碩士、博士學(xué)位，現(xiàn)為南開(kāi)大學(xué)信息技術(shù)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系教授。多年來(lái)主講“數(shù)據(jù)結(jié)構(gòu)”、“形式語(yǔ)言與自動(dòng)機(jī)”、“計(jì)算方法”等課程。主要研究領(lǐng)域?yàn)槿斯ぶ悄?、電子商?wù)、加密技術(shù)等，曾承擔(dān)科技部、天津市重點(diǎn)基金等多項(xiàng)科研項(xiàng)目，出版教材《數(shù)據(jù)結(jié)構(gòu)導(dǎo)論》、《Java程序設(shè)計(jì)》等，發(fā)表論文十余篇?！　Z，1942年生。1981年于南開(kāi)大學(xué)數(shù)學(xué)系研究生畢業(yè)。南開(kāi)大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系教授，博士生導(dǎo)師，教育部計(jì)算機(jī)科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會(huì)委員，基礎(chǔ)分會(huì)副主任，天津市高等學(xué)校計(jì)算機(jī)基礎(chǔ)教學(xué)指導(dǎo)委員會(huì)副主任，中國(guó)計(jì)算機(jī)學(xué)會(huì)理論計(jì)算機(jī)科學(xué)分會(huì)理事，天津市學(xué)位委員會(huì)學(xué)科評(píng)議組成員。長(zhǎng)期講授“高級(jí)語(yǔ)言程序設(shè)計(jì)”、“算法設(shè)計(jì)與分析”等課程。主要研究領(lǐng)域?yàn)椴⑿信c分布式系統(tǒng)、算法設(shè)計(jì)與分析、網(wǎng)絡(luò)存儲(chǔ)系統(tǒng)、面向?qū)ο蟪绦蛟O(shè)計(jì)等。曾主持國(guó)家863、自然科學(xué)基金、博士點(diǎn)基金項(xiàng)目等十余項(xiàng)，在國(guó)內(nèi)外發(fā)表論文60篇，出版教材“計(jì)算機(jī)算法引論”、“高級(jí)語(yǔ)言C++程序設(shè)計(jì)”等。　　陳有祺，1936年生。1960年畢業(yè)于北京大學(xué)數(shù)學(xué)力學(xué)系，同年在南開(kāi)大學(xué)任教。1980-1982年在美國(guó)西密西根大學(xué)作訪問(wèn)學(xué)者，研修人工智能和形式語(yǔ)言，現(xiàn)為南開(kāi)大學(xué)教授。曾任南開(kāi)大學(xué)計(jì)算機(jī)與系統(tǒng)科學(xué)系主任，現(xiàn)兼任中國(guó)計(jì)算機(jī)學(xué)會(huì)理論計(jì)算機(jī)科學(xué)分會(huì)理事，全國(guó)高等學(xué)校計(jì)算機(jī)教育研究會(huì)理事，《理論計(jì)算機(jī)科學(xué)》常務(wù)編委等職。多年來(lái)從事編譯理論、形式語(yǔ)言與自動(dòng)機(jī)、人工智能和自然語(yǔ)言理解等領(lǐng)域的教學(xué)與研究工作，共發(fā)表論著二十余篇（部）。1991年被評(píng)為天津市優(yōu)秀教師。

書(shū)籍目錄

第l章 緒論1.1 數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介1.1.1 數(shù)據(jù)結(jié)構(gòu)的發(fā)展歷史1.1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)1.2 有關(guān)的預(yù)備知識(shí)1.2.1 集合1.2.2 遞歸1.2.3 數(shù)學(xué)證明方法習(xí)題第2章 算法的基本概念與算法分析2.1 算法的基本概念2.1.1 一個(gè)簡(jiǎn)單的算法2.1.2 什么是算法2.1.3 算法與問(wèn)題2.1.4 算法與程序2.2 算法的評(píng)估2.2.1 算法的正確性2.2.2 時(shí)間代價(jià)2.2.3 空間代價(jià)2.2.4 最優(yōu)性2.3 算法的復(fù)雜度度量2.3.1 基本操作2.3.2 問(wèn)題實(shí)例長(zhǎng)度2.3.3 復(fù)雜度函數(shù)及其漸進(jìn)性質(zhì)2.3.4 最壞情形和最優(yōu)情形2.3.5 平均情形和算法的期望復(fù)雜度2.3.6 復(fù)雜度函數(shù)的表示2.4 算法設(shè)計(jì)與分析的重要性2.4.1 一個(gè)實(shí)例2.4.2 計(jì)算機(jī)應(yīng)用領(lǐng)域的變化2.4.3 計(jì)算機(jī)技術(shù)的發(fā)展需要設(shè)計(jì)有效算法2.5 MAXMIN問(wèn)題2.5.1 MAxMIN問(wèn)題的平凡算法2.5.2 第一次改進(jìn)算法2.5.3 第二次改進(jìn)算法2.5.4 采用分治策略的改進(jìn)算法2.5.5 算法MAxMIN的討論習(xí)題第3章 線性表3.1 線性表的定義和基本運(yùn)算3.2 線性表的實(shí)現(xiàn)3.2.1 順序存儲(chǔ)結(jié)構(gòu)3.2.2 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)3.2.3 兩種基本實(shí)現(xiàn)方法的比較3.2.4 循環(huán)鏈表3.2.5 雙向鏈表3.3 線性表的應(yīng)用習(xí)題第4章 棧、隊(duì)列和數(shù)組4.1 棧4.1.1 順序棧4.1.2 鏈?zhǔn)綏?.1.3 順序棧與鏈?zhǔn)綏５谋容^4.1.4 棧的應(yīng)用4.2 隊(duì)列4.2.1 隊(duì)列的定義及基本運(yùn)算4.2.2 順序隊(duì)列4.2.3 鏈?zhǔn)疥?duì)列4.2.4 隊(duì)列的應(yīng)用4.3 數(shù)組4.3.1 數(shù)組的抽象數(shù)據(jù)類型4.3.2 數(shù)組的存儲(chǔ)方式4.3.3 特殊數(shù)組4.3.4 數(shù)組的應(yīng)用習(xí)題第5章 樹(shù)形結(jié)構(gòu)5.1 樹(shù)5.1.1 樹(shù)的基本概念5.1.2 樹(shù)的抽象數(shù)據(jù)類型5.2 二叉樹(shù)5.2.1 二叉樹(shù)的定義及其主要特性5.2.2 二叉樹(shù)的實(shí)現(xiàn)5.2.3 二叉樹(shù)的遍歷5.3 樹(shù)、森林與二叉樹(shù)的關(guān)系5.3.1 樹(shù)的存儲(chǔ)結(jié)構(gòu)5.3.2 森林與二叉樹(shù)的轉(zhuǎn)換5.3.3 樹(shù)和森林的遍歷5.4 樹(shù)形結(jié)構(gòu)的應(yīng)用5.4.1 等價(jià)類問(wèn)題5.4.2 哈夫曼樹(shù)和哈夫曼編碼習(xí)題第6章 圖6.1 圖的基本概念6.1.1 圖的基本概念6.1.2 圖的抽象數(shù)據(jù)類型6.2 圖的存儲(chǔ)結(jié)構(gòu)6.2.1 鄰接矩陣6.2.2 鄰接表6.2.3 逆鄰接表6.2.4 鄰接多重表6.2.5 圖的實(shí)現(xiàn)6.3 圖的遍歷及求圖的連通分量6.3.1 深度優(yōu)先搜索6.3.2 廣度優(yōu)先搜索6.3.3 無(wú)向圖的連通分量6.4 生成樹(shù)和最小代價(jià)生成樹(shù)6.4.1 生成樹(shù)6.4.2 最小代價(jià)生成樹(shù)6.5 最短路徑6.5.1 從某個(gè)源點(diǎn)到其他各頂點(diǎn)的最短路徑6.5.2 每一對(duì)頂點(diǎn)間的最短路徑6.6 有向無(wú)環(huán)圖及其應(yīng)用6.6.1 有向無(wú)環(huán)圖6.6.2 拓?fù)渑判?.6.3 關(guān)鍵路徑習(xí)題第7章 查找7.1 查找的基本概念7.2 順序表的查找7.2.1 順序查找7.2.2 折半查找7.2.3 索引順貢序表的查找7.3 樹(shù)表的查找7.3.1 二叉排序樹(shù)7.3.2 平衡二叉樹(shù)7.3.3 B-樹(shù)7.4 P臺(tái)希表及其查找7.4.1 什么是哈希7.4.2 哈希函數(shù)的構(gòu)造方法7.4.3 處理沖突的幾種方法7.4.4 哈希表的查找及其效率分析習(xí)題第8章 內(nèi)部排序8.1 排序的一般概念8.2 插入排序8.2.1 直接插入排序8.2.2 折半插入排序8.2.3 希爾排序8.3 交換排序8.3.1 起泡排序8.3.2 快速排序8.4 選擇排序8.4.1 簡(jiǎn)單選擇排序8.4.2 堆排序8.5 歸并排序8.5.1 兩個(gè)有序序列的歸并操作8.5.2 歸并排序8.6 分配排序和基數(shù)排序8.7 有關(guān)內(nèi)部排序算法的比較習(xí)題第9章 算法設(shè)計(jì)技術(shù)9.1 求解問(wèn)題的基本思路9.2 分治技術(shù)9.2.1 分治策略的思想9.2.2 大整數(shù)乘法9.2.3 矩陣相乘的Strassen算法9.2.4 選擇問(wèn)題的分治算法9.3 貪心技術(shù)9.3.1 貪心算法的思想9.3.2 活動(dòng)安排問(wèn)題9.3.3 背包問(wèn)題9.3.4 多機(jī)調(diào)度問(wèn)題的近似算法9.3.5 單源最短路徑問(wèn)題的Dijkstra算法9.4 回溯與分枝限界技術(shù)9.4.1 兩個(gè)適合回溯技術(shù)的問(wèn)題9.4.2 八后問(wèn)題9.4.3 0-1背包問(wèn)題的回溯算法9.4.4 分枝限界算法9.5 動(dòng)態(tài)規(guī)劃技術(shù)9.5.1 Fibonacci數(shù)的計(jì)算9.5.2 矩陣連乘的順序問(wèn)題9.5.3 適合動(dòng)態(tài)規(guī)劃算法的兩個(gè)條件綜合練習(xí)題一綜合練習(xí)題二綜合練習(xí)題三綜合練習(xí)題四綜合練習(xí)題五綜合模擬題一綜合模擬題二參考文獻(xiàn)

章節(jié)摘錄

　　1.1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)　　為了對(duì)數(shù)據(jù)結(jié)構(gòu)有一個(gè)全面正確的了解，在本節(jié)給出有關(guān)的基本概念和術(shù)語(yǔ)?！　?shù)據(jù)：能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)處理的一切對(duì)象。這里必須強(qiáng)調(diào)指出，所謂數(shù)據(jù)絕不能僅僅理解為整數(shù)或?qū)崝?shù)這種狹義的“數(shù)”，必須做廣義的理解。例如，一個(gè)用某種程序語(yǔ)言編寫(xiě)的源程序、一篇文稿、一張地圖、一幅照片、一首歌曲等，都可以視為“數(shù)據(jù)”。今后隨著計(jì)算機(jī)的發(fā)展，數(shù)據(jù)的范圍還將不斷擴(kuò)大。　　數(shù)據(jù)元素：數(shù)據(jù)的基本單位。由于數(shù)據(jù)的范圍非常廣泛，因此其基本單位也是可大可小的。大到可以是一個(gè)國(guó)家的地圖、一　　、一部電影；小到可以是一個(gè)字符，甚至是計(jì)算機(jī)中的一位。對(duì)于較大的單位，還可以由稱為“數(shù)據(jù)項(xiàng)”的較小單位組成。如圖書(shū)館中一本書(shū)的目錄卡片就可以包含書(shū)名、作者名、出版社名、書(shū)號(hào)和出版日期等數(shù)據(jù)項(xiàng)?！　?shù)據(jù)對(duì)象：具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。因?yàn)樵趯?shí)際應(yīng)用中不會(huì)同時(shí)處理一切類型的數(shù)據(jù)，總是針對(duì)特定的問(wèn)題處理一種或幾種對(duì)象。例如，用計(jì)算機(jī)求素?cái)?shù)這個(gè)問(wèn)題只涉及“整數(shù)”這種數(shù)據(jù)對(duì)象?！　?shù)據(jù)結(jié)構(gòu)：彼此具有一定關(guān)系的數(shù)據(jù)元素的集合。事實(shí)上，這些關(guān)系反映了客觀世界事物之間的聯(lián)系。由于客觀事物存在著各種不同的聯(lián)系形式，所以反映在數(shù)據(jù)關(guān)系上也就各不相同。一般來(lái)說(shuō)，數(shù)據(jù)有四類基本結(jié)構(gòu)：（1）集合。這個(gè)結(jié)構(gòu)中數(shù)據(jù)元素之間除了?！巴瑢儆谝粋€(gè)集合”這一關(guān)系外，沒(méi)有其他關(guān)系。（2）線性結(jié)構(gòu)。這個(gè)結(jié)構(gòu)中數(shù)據(jù)元素之間存在著依次排列的先后次序關(guān)系。（3）樹(shù)形結(jié)構(gòu)。這個(gè)結(jié)構(gòu)中數(shù)據(jù)元素之間存在著層次關(guān)系或分支關(guān)系。（4）圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。這個(gè)結(jié)構(gòu)中數(shù)據(jù)元素之間相互連接成網(wǎng)狀。

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

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

---

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

---