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

前言

計(jì)算機(jī)科學(xué)已經(jīng)深入應(yīng)用到各個(gè)領(lǐng)域，不僅有效地解決了各種工程和科學(xué)計(jì)算中的數(shù)值計(jì)算問(wèn)題，而且也有效地解決了許多文本處理、信息檢索、數(shù)據(jù)庫(kù)管理、圖像識(shí)別、人工智能等非數(shù)值的數(shù)據(jù)處理問(wèn)題。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)學(xué)科的一個(gè)重要分支研究領(lǐng)域，它是算法分析與設(shè)計(jì)、操作系統(tǒng)、軟件工程、數(shù)據(jù)庫(kù)概論、編譯技術(shù)、計(jì)算機(jī)圖形學(xué)、人機(jī)交互等專業(yè)基礎(chǔ)課和專業(yè)課的先行課。其他計(jì)算機(jī)科學(xué)領(lǐng)域及有關(guān)的應(yīng)用軟件都要使用到各種數(shù)據(jù)結(jié)構(gòu)，例如：語(yǔ)言編譯要使用棧、散列表及語(yǔ)法樹(shù)；操作系統(tǒng)中用隊(duì)列、存儲(chǔ)管理表及目錄樹(shù)等；數(shù)據(jù)庫(kù)系統(tǒng)運(yùn)用線性表、多鏈表及索引樹(shù)等進(jìn)行數(shù)據(jù)管理；而在人工智能領(lǐng)域，依求解問(wèn)題性質(zhì)的差異將涉及到各種不同的數(shù)據(jù)結(jié)構(gòu)，如廣義表，集合、搜索樹(shù)及各種有向圖，等等。美國(guó)IEEE和ACM的教學(xué)計(jì)劃CC2001把“算法與數(shù)據(jù)結(jié)構(gòu)”列入計(jì)算機(jī)以及信息技術(shù)相關(guān)學(xué)科專業(yè)的本科必修基礎(chǔ)課程。在我國(guó)，“數(shù)據(jù)結(jié)構(gòu)與算法”已經(jīng)作為理工科非計(jì)算機(jī)專業(yè)必修的信息技術(shù)基礎(chǔ)課程之一。世界上許多科技人員對(duì)學(xué)習(xí)、研究數(shù)據(jù)結(jié)構(gòu)都非常重視，對(duì)于從事計(jì)算機(jī)科學(xué)及其應(yīng)用的科技工作者來(lái)說(shuō)，數(shù)據(jù)結(jié)構(gòu)更是必須透徹地掌握的重要基礎(chǔ)，有助于程序員更有效地組織數(shù)據(jù)、設(shè)計(jì)高效的算法、完成高質(zhì)量的程序，以滿足錯(cuò)綜復(fù)雜的實(shí)際需要。從字面上來(lái)看，數(shù)據(jù)結(jié)構(gòu)就是指數(shù)據(jù)間的相互關(guān)系。具體到計(jì)算機(jī)環(huán)境，談到任何一種結(jié)構(gòu)時(shí)，都自然地聯(lián)系著作用在這種類型的數(shù)據(jù)上的運(yùn)算（即函數(shù)），為了在計(jì)算機(jī)上執(zhí)行這些運(yùn)算，有必要把這些數(shù)據(jù)以某種方式存儲(chǔ)在計(jì)算機(jī)中。因此，可以認(rèn)為，所謂數(shù)據(jù)結(jié)構(gòu)，就是由某種邏輯關(guān)系組織起來(lái)的一批數(shù)據(jù)，按一定的存儲(chǔ)方法被存儲(chǔ)于計(jì)算機(jī)中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合。也就是說(shuō)，數(shù)據(jù)結(jié)構(gòu)具有3個(gè)方面：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。事實(shí)上，數(shù)據(jù)結(jié)構(gòu)的三個(gè)側(cè)面，以數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算定義更為重要。因?yàn)楹芏鄷r(shí)候人們并不關(guān)心數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和運(yùn)算的具體實(shí)現(xiàn)。1983年Aho等人把數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)與實(shí)現(xiàn)細(xì)節(jié)剝離，定義了抽象數(shù)據(jù)類型（簡(jiǎn)稱“ADT”）的概念。抽象數(shù)據(jù)類型是定義了一組運(yùn)算的數(shù)學(xué)模型。這種抽象的數(shù)據(jù)類型可以在較高級(jí)的算法中直接引用，而不用考慮其實(shí)現(xiàn)細(xì)節(jié)。這就使得設(shè)計(jì)者可以在不同的設(shè)計(jì)階段采用不同的抽象數(shù)據(jù)類型作為設(shè)計(jì)的基礎(chǔ)，在適當(dāng)?shù)某橄髮哟紊峡紤]程序的結(jié)構(gòu)和算法，從而很好地支持了邏輯設(shè)計(jì)和物理實(shí)現(xiàn)的分離，支持封裝和信息隱蔽。

內(nèi)容概要

　　《數(shù)據(jù)結(jié)構(gòu)與算法：學(xué)習(xí)指導(dǎo)與習(xí)題解析》配合我社出版的面向21世紀(jì)課程教材《數(shù)據(jù)結(jié)構(gòu)與算法》的使用，為讀者學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法課程給予指導(dǎo)。全書(shū)共14章，其中，第1～12章總結(jié)了本課程重要的內(nèi)容知識(shí)點(diǎn)、學(xué)習(xí)重點(diǎn)和難點(diǎn)，某些章節(jié)還對(duì)相關(guān)知識(shí)點(diǎn)進(jìn)行了擴(kuò)展；前13章從題意分析、典型錯(cuò)誤、數(shù)據(jù)結(jié)構(gòu)、算法代碼、算法分析等多個(gè)角度給出了主教材中212道習(xí)題和53道上機(jī)題的綜合分析和參考解答，并新收入了覆蓋各章知識(shí)點(diǎn)的170多道習(xí)題和40多道上機(jī)題供讀者練習(xí)；第13章內(nèi)容基本上選自ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽題，強(qiáng)化算法實(shí)現(xiàn)和上機(jī)實(shí)習(xí)能力；第14章以1999～2005年北京大學(xué)計(jì)算機(jī)系研究生入學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題及解答為主，輔助讀者自學(xué)與自測(cè)。教據(jù)結(jié)構(gòu)與算法課程的學(xué)習(xí)目的是，根據(jù)應(yīng)用問(wèn)題的性質(zhì)選擇合理的數(shù)據(jù)結(jié)構(gòu)，在合理的時(shí)間、空間復(fù)雜度限制下編程加以解決。認(rèn)真地完成習(xí)題和上機(jī)題，是學(xué)好本課程，提高程序設(shè)計(jì)質(zhì)量的重要環(huán)節(jié)?！　　稊?shù)據(jù)結(jié)構(gòu)與算法：學(xué)習(xí)指導(dǎo)與習(xí)題解析》可作為普通高等院校計(jì)算機(jī)及相關(guān)專業(yè)數(shù)據(jù)結(jié)構(gòu)與算法課程的教學(xué)參考書(shū)，也可供參加計(jì)算機(jī)碩士、計(jì)算機(jī)博士、軟件工程碩士入學(xué)考試的考生參考使用，還可供計(jì)算機(jī)應(yīng)用技術(shù)人員參考使用。

書(shū)籍目錄

第1章 概論1.1 知識(shí)點(diǎn)總結(jié)1.2 教材習(xí)題解答1.3 增補(bǔ)習(xí)題1.4 增補(bǔ)上機(jī)題第2章 線性表、棧和隊(duì)列2.1 知識(shí)點(diǎn)總結(jié)2.2 教材習(xí)題解答2.3 增補(bǔ)習(xí)題2.4 增補(bǔ)上機(jī)題第3章 字符串3.1 知識(shí)點(diǎn)總結(jié) 3.2 教材習(xí)題解答3.3 教材上機(jī)題解答3.4 增補(bǔ)習(xí)題3.5 增補(bǔ)上機(jī)題第4章 二叉樹(shù)4.1 知識(shí)點(diǎn)總結(jié) 4.2 教材習(xí)題解答4.3 教材上機(jī)題解答4.4 增補(bǔ)習(xí)題4.5 增補(bǔ)上機(jī)題第5章 樹(shù)5.1 樹(shù)的概念和表示法5.2 樹(shù)的周游5.3 樹(shù)的存儲(chǔ)5.4 K叉樹(shù)5.5 教材習(xí)題解答5.6 教材上機(jī)題解答5.7 增補(bǔ)習(xí)題5.8 增補(bǔ)上機(jī)題第6章 圖6.1 知識(shí)點(diǎn)總結(jié)6.2 教材習(xí)題解答6.3 教材上機(jī)題解答6.4 增補(bǔ)習(xí)題6.5 增補(bǔ)上機(jī)題第7章 內(nèi)排序7.1 內(nèi)排序知識(shí)點(diǎn)總結(jié)7.1.1 內(nèi)排序概念7.1.2 內(nèi)排序的性質(zhì)(重點(diǎn))7.1.3 評(píng)價(jià)一個(gè)排序算法的好壞(重點(diǎn))7.1.4 基于比較的排序問(wèn)題的下限7.1.5 幾種重要的排序算法(重點(diǎn)，難點(diǎn))7.2 內(nèi)排序性能總結(jié)7.2.1 簡(jiǎn)單排序算法的時(shí)間代價(jià)比較7.2.2 排序算法的時(shí)間代價(jià)和空間代價(jià)7.2.3 排序算法的實(shí)驗(yàn)性能比較7.3 內(nèi)排序知識(shí)擴(kuò)充7.3.1 索引排序和地址排序7.3.2 海豚算法7.4 教材習(xí)題解答7.5 教材上機(jī)題解答7.6 增補(bǔ)習(xí)題7.7 增補(bǔ)上機(jī)題第8章 文件管理和外排序8.1 知識(shí)點(diǎn)總結(jié)8.1.1 文件管理和外排序的基本概念8.1.2 磁盤(pán)訪問(wèn)時(shí)間估算8.1.3 置換選擇排序8.1.4 二路外排序8.2 教材習(xí)題解答8.3 教材上機(jī)題解答8.4 增補(bǔ)習(xí)題8.5 增補(bǔ)上機(jī)題第9章 檢索9.1 知識(shí)點(diǎn)總結(jié)9.1.1 檢索概念9.1.2 檢索算法的基本分類9.1.3 衡量檢索算法的效率(重點(diǎn))9.1.4 基于線性表的檢索(重點(diǎn))9.1.5 基于散列表的檢索(重點(diǎn)、難點(diǎn))9.2 教材習(xí)題解答9.3 教材上機(jī)題解答9.4 增補(bǔ)習(xí)題9.5 增補(bǔ)上機(jī)題第10章 索引技術(shù)10.1 知識(shí)點(diǎn)總結(jié)10.1.1 索引概念10.1.2 索引技術(shù)的簡(jiǎn)單分類10.1.3 線性索引(重點(diǎn))10.1.4 動(dòng)態(tài)索引(重點(diǎn)、難點(diǎn))10.2 教材習(xí)題解答10.3 教材上機(jī)題解答10.4 增補(bǔ)習(xí)題10.5 增補(bǔ)上機(jī)題第11章 高級(jí)線性結(jié)構(gòu)11.1 知識(shí)點(diǎn)總結(jié)11.1.1 基本概念11.1.2 多維數(shù)組11.1.3 廣義表11.1.4 存儲(chǔ)管理技術(shù)11.2 教材習(xí)題解答11.3 教材上機(jī)題解答11.4 增補(bǔ)習(xí)題11.5 增補(bǔ)上機(jī)題第12章 高級(jí)樹(shù)結(jié)構(gòu)12.1 知識(shí)點(diǎn)總結(jié)12.1.1 適用于存儲(chǔ)、檢索字符串組的樹(shù)形結(jié)構(gòu)12.1.2 二叉搜索樹(shù)BsT的幾個(gè)變體(重點(diǎn))12.1.3 空間數(shù)據(jù)結(jié)構(gòu)12.1.4 樹(shù)形結(jié)構(gòu)的兩個(gè)應(yīng)用12.2 擴(kuò)充知識(shí)——紅黑樹(shù)12.2.1 紅黑樹(shù)的定義12.2.2 紅黑樹(shù)相關(guān)性質(zhì)12.2.3 插入結(jié)點(diǎn)算法12.2.4 刪除結(jié)點(diǎn)算法12.3 教材習(xí)題解答12.4 教材上機(jī)題解答12.5 增補(bǔ)習(xí)題12.6 增補(bǔ)上機(jī)題第13章 數(shù)據(jù)結(jié)構(gòu)與算法實(shí)習(xí)指導(dǎo)13.1 基本數(shù)據(jù)結(jié)構(gòu)的應(yīng)用13.2 窮舉法13.3 搜索和剪枝13.4 動(dòng)態(tài)規(guī)劃13.5 貪心法13.6 圖算法13.7 實(shí)習(xí)范例13.8 增補(bǔ)習(xí)題第14章 北京大學(xué)計(jì)算機(jī)系“數(shù)據(jù)結(jié)構(gòu)與算法”試題選14.1 北京大學(xué)信息學(xué)院2004年“數(shù)據(jù)結(jié)構(gòu)與算法”試題14.1.1 2004年期中考試試題14.1.2 2004年期末考試試題14.2 北京大學(xué)信息學(xué)院2004年“數(shù)據(jù)結(jié)構(gòu)與算法”試題參考答案14.2.1 2004年期中考試試題參考答案14.2.2 2004年期末考試試題參考答案14.3 北京大學(xué)碩士研究生入學(xué)考試“數(shù)據(jù)結(jié)構(gòu)”試題14.3.1 1999年試題14.3.2 2000年試題14.3.3 2001年試題14.3.4 2002年試題14.3.5 2003年試題14.3.6 2004年試題14.3.7 2005年試題14.4 北京大學(xué)碩士研究生入學(xué)考試“數(shù)據(jù)結(jié)構(gòu)”試題參考答案14.4.1 1999年試題參考答案14.4.2 2000年試題參考答案14.4.3 2001年試題參考答案14.4.4 2002年試題參考答案14.4.5 2003年試題參考答案14.4.6 2004年試題參考答案14.4.7 2005年試題參考答案參考文獻(xiàn)

章節(jié)摘錄

插圖：1.1.4 算法及其特性算法是一個(gè)十分古老的研究課題。簡(jiǎn)單來(lái)說(shuō)，它是為求解問(wèn)題而給出的指令序列。一個(gè)算法可能有若干個(gè)輸入，這些輸入數(shù)據(jù)在算法開(kāi)始時(shí)提供一組量。對(duì)算法的描述應(yīng)該精確地說(shuō)明這些輸入的個(gè)數(shù)、類型以及它們應(yīng)滿足的初始條件，算法的每個(gè)步驟必須被明確描述，并且可行，不能有二義性。算法的一般性質(zhì)包括以下幾點(diǎn)：（1）通用性對(duì)于那些符合輸入類型的任意輸入數(shù)據(jù)，都能根據(jù)算法進(jìn)行問(wèn)題求解，并保證計(jì)算結(jié)果的正確性。（2）有效性組成算法的每一條指令都必須是能夠被人或機(jī)器確切執(zhí)行的。（3）確定性算法每執(zhí)行一步之后，對(duì)于它的下一步，應(yīng)該有明確的指示。即，保證每一步之后都有關(guān)于下一步動(dòng)作的指令，不能缺乏下一步指令或僅僅含有模糊不清的指令。（4）有窮性算法的執(zhí)行必須在有限步內(nèi)結(jié)束。在實(shí)際應(yīng)用中，算法的表現(xiàn)形式千變?nèi)f化，但許多算法的設(shè)計(jì)思想具有相似之處。歸納起來(lái)，常用的算法大致可分為以下幾類：（1）窮舉法基本思想是在一個(gè)可能存在可行狀態(tài)（可行解）的狀態(tài)全集中依次遍歷所有的元素，并判斷是否為可行狀態(tài)。（2）貪心法基本思想是試圖通過(guò)局部最優(yōu)解得到全局最優(yōu)解。（3）分治法基本思想是把一個(gè)規(guī)模較大的問(wèn)題劃分成相似的小問(wèn)題，各個(gè)求解，再得到整個(gè)問(wèn)題的解。（4）回溯法基本思想是一步一步向前試探，有多種選擇時(shí)任意選擇一種，只要可行就繼續(xù)向前，一旦失敗時(shí)就后退回來(lái)選擇其他可能性。（5）動(dòng)態(tài)規(guī)劃法基本思想是把大問(wèn)題分解為若干小問(wèn)題，通過(guò)求解子問(wèn)題來(lái)得到原問(wèn)題的解。由于這些子問(wèn)題相互包含，為了復(fù)用已計(jì)算的結(jié)果，常把計(jì)算的中間結(jié)果全部保存起來(lái)，自底向上多路徑地求解計(jì)算原問(wèn)題的解。（6）分支界限法基本思想是在表示問(wèn)題空間的樹(shù)上進(jìn)行系統(tǒng)搜索時(shí)采用廣度優(yōu)先策略，同時(shí)利用最優(yōu)解屬性的上下界來(lái)控制搜索的分支。1.1.5 算法的執(zhí)行效率及其度量解決同一個(gè)問(wèn)題一般存在多種算法。要想從這些算法中選擇一個(gè)適合的算法作為解決方案，則需對(duì)算法進(jìn)行度量和評(píng)價(jià)的方法。評(píng)價(jià)一個(gè)算法優(yōu)劣的重要依據(jù)是漸近分析實(shí)現(xiàn).該算法的程序在計(jì)算機(jī)中執(zhí)行時(shí)所需占用的機(jī)器資源的多少。兩個(gè)重要指標(biāo)為算法的空間代價(jià)（或稱空間復(fù)雜度）和算法的時(shí)間代價(jià)（或稱時(shí)間復(fù)雜度）。

編輯推薦

《數(shù)據(jù)結(jié)構(gòu)與算法:學(xué)習(xí)指導(dǎo)與習(xí)題解析》為普通高等教育“十五”國(guó)家級(jí)規(guī)劃教材配套參考書(shū)。全書(shū)共14章，前13章從題意分析、典型錯(cuò)誤、數(shù)據(jù)結(jié)構(gòu)、算法代碼、算法分析等多個(gè)角度給出了主教材中212道習(xí)題和53道上機(jī)題的綜合分析和參考解答，并新收入了覆蓋各章知識(shí)點(diǎn)的170多道習(xí)題和40多道上機(jī)題供讀者練習(xí)；第14章以1999～2005年北京大學(xué)計(jì)算機(jī)系研究生入學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題及解答為主，輔助讀者自學(xué)與自測(cè)。 《數(shù)據(jù)結(jié)構(gòu)與算法:學(xué)習(xí)指導(dǎo)與習(xí)題解析》可作為普通高等院校計(jì)算機(jī)及相關(guān)專業(yè)數(shù)據(jù)結(jié)構(gòu)與算法課程的教學(xué)參考書(shū)，也可供參加計(jì)算機(jī)碩士、計(jì)算機(jī)博士、軟件工程碩士入學(xué)考試的考生參考使用，還可供計(jì)算機(jī)應(yīng)用技術(shù)人員參考使用。

圖書(shū)封面

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

無(wú)

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

---

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

---