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

前言

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

內(nèi)容概要

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

作者簡介

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

書籍目錄

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

章節(jié)摘錄

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

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

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

---