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

前言

　　關(guān)于算法的研究已經(jīng)有數(shù)千年的歷史。計(jì)算機(jī)的出現(xiàn)，使得用機(jī)器自動(dòng)解題的夢(mèng)想成為現(xiàn)實(shí)，人們可以將算法編寫(xiě)成程序交給計(jì)算機(jī)執(zhí)行，使許多原來(lái)認(rèn)為不可能完成的算法變得實(shí)際可行。數(shù)據(jù)結(jié)構(gòu)的概念最早由C.A.R.Hoare和N.Wirth在1966年提出。大量關(guān)于程序設(shè)計(jì)理論的研究表明：對(duì)大型復(fù)雜程序的構(gòu)造進(jìn)行系統(tǒng)而科學(xué)的研究，必須對(duì)這些程序中所包含的數(shù)據(jù)結(jié)構(gòu)進(jìn)行深入的研究。事實(shí)上，程序就是在數(shù)據(jù)的某些特定的結(jié)構(gòu)和表示的基礎(chǔ)上對(duì)于算法的描述。不清楚解決問(wèn)題的算法就無(wú)法決定如何組織數(shù)據(jù)，反之算法的實(shí)現(xiàn)又在很大程度上依賴于數(shù)據(jù)的具體組織。簡(jiǎn)言之，算法與數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計(jì)中相輔相成、不可分割的兩個(gè)方面。因此，1976年N.Wirth用“算法+數(shù)據(jù)結(jié)構(gòu)=程序”這個(gè)公式表達(dá)了算法與數(shù)據(jù)結(jié)構(gòu)的聯(lián)系和它們?cè)诔绦蛑械牡匚?。　　抽象?shù)據(jù)類型起源于20世紀(jì)70年代，可以定義成：有一定行為（操作）的抽象（數(shù)學(xué)）類型。它抽象出數(shù)據(jù)類型的使用要求，而把它的具體表示方式和運(yùn)算的實(shí)現(xiàn)細(xì)節(jié)都隱藏起來(lái)。它支持?jǐn)?shù)據(jù)類型的實(shí)現(xiàn)與使用分離的原則，是一種十分有效的對(duì)問(wèn)題進(jìn)行抽象與分解的思維工具，后來(lái)發(fā)展成為面向?qū)ο蠹夹g(shù)與方法的主要理論基礎(chǔ)。?　　從抽象數(shù)據(jù)類型的觀點(diǎn)出發(fā)，數(shù)據(jù)結(jié)構(gòu)可以理解成為“抽象數(shù)據(jù)類型的物理實(shí)現(xiàn)”。對(duì)于數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)和研究，主要圍繞兩個(gè)問(wèn)題：一個(gè)是如何具體表示抽象數(shù)據(jù)類型中的數(shù)學(xué)模型；另一個(gè)是如何給出抽象數(shù)據(jù)類型中需要的操作的具體實(shí)現(xiàn)。用上述觀點(diǎn)，可以從更加抽象的角度理解數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系，也容易解釋數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)與運(yùn)算的三者關(guān)系。?　　目的與動(dòng)機(jī)?　　“數(shù)據(jù)結(jié)構(gòu)”（或稱“數(shù)據(jù)結(jié)構(gòu)與算法”或“算法與數(shù)據(jù)結(jié)構(gòu)”）是計(jì)算機(jī)科學(xué)的基礎(chǔ)課程，它被獨(dú)立列入大學(xué)本科的教學(xué)計(jì)劃有30多年的歷史。其主要目的是使讀者全面地理解數(shù)據(jù)結(jié)構(gòu)和算法的概念、掌握設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)與算法的主要原理和方法、比較不同數(shù)據(jù)結(jié)構(gòu)和算法的特點(diǎn)。通過(guò)學(xué)習(xí)和實(shí)踐，提高學(xué)生使用計(jì)算機(jī)解決問(wèn)題的能力。?　　1998年，北京大學(xué)把“算法與數(shù)據(jù)結(jié)構(gòu)”作為第一批理科各系主干基礎(chǔ)課列入學(xué)校的教學(xué)計(jì)劃。經(jīng)北大信息學(xué)院和數(shù)學(xué)學(xué)院共同推薦，著者連續(xù)六年被校長(zhǎng)聘任為該課程的全校主持人，負(fù)責(zé)組織理科各院系的主講老師制定教學(xué)大綱、編寫(xiě)教材和教學(xué)輔導(dǎo)用書(shū)、交流教學(xué)經(jīng)驗(yàn)等工作?！　”緯?shū)的第一版就是在這個(gè)背景下，邀請(qǐng)了北大物理學(xué)院、化學(xué)學(xué)院和計(jì)算中心的幾位主講老師與著者共同編寫(xiě)的。從2000年開(kāi)始，本書(shū)作為北京大學(xué)主干課“算法與數(shù)據(jù)結(jié)構(gòu)”的教材在校內(nèi)試用，2002年得以在高等教育出版社正式出版，并得到廣大校內(nèi)外老師和學(xué)生的支持和鼓勵(lì)，被評(píng)為“2004年北京市高等教育精品教材”。為了回報(bào)廣大讀者，使得這本書(shū)能夠更上一個(gè)臺(tái)階，成為過(guò)得硬的“精品”教材，在高等教育出版社的大力支持下，著者決定認(rèn)真修改后出此新版。?

內(nèi)容概要

本書(shū)以數(shù)據(jù)結(jié)構(gòu)為主線，算法為輔線組織教學(xué)內(nèi)容。全書(shū)共分10章：緒論、線性表、字符串、棧與隊(duì)列、二叉樹(shù)與樹(shù)、集合與字典、高級(jí)字典結(jié)構(gòu)、排序、圖和算法分析與設(shè)計(jì)。本書(shū)體系完整，概念清楚，內(nèi)容充實(shí)，取材適當(dāng)。第一版在2004年被評(píng)為“北京市高等教育精品教材”。 　　這次再版，采用“數(shù)據(jù)結(jié)構(gòu)作為抽象數(shù)據(jù)類型的物理實(shí)現(xiàn)”觀點(diǎn)，在內(nèi)容和形式上都進(jìn)行了許多改進(jìn)和擴(kuò)充。提高了抽象數(shù)據(jù)類型在教學(xué)中的地位和作用；更加突出了重點(diǎn)，提高了全書(shū)的可讀性，還補(bǔ)充了習(xí)題，增加了索引?！　∮捎谠诰帉?xiě)中注意到知識(shí)模塊的獨(dú)立性和相關(guān)性，不同專業(yè)和不同水平的學(xué)生可以根據(jù)需要組合使用。本書(shū)既可以作為信息與計(jì)算機(jī)專業(yè)大學(xué)本科的“數(shù)據(jù)結(jié)構(gòu)”教材，也可以作為一般理工科專業(yè)本科和計(jì)算機(jī)專業(yè)?？茖W(xué)生學(xué)習(xí)相關(guān)課程的教材或教學(xué)參考書(shū)。

書(shū)籍目錄

1　緒論　1.1　從問(wèn)題到程序  　1.1.1　問(wèn)題分析與抽象　  1.1.2　程序的設(shè)計(jì)與實(shí)現(xiàn)　1.2　抽象數(shù)據(jù)類型  　1.2.1　什么是抽象數(shù)據(jù)類型　  1.2.2　意義與作用  　1.2.3　舉例  1.3  數(shù)據(jù)結(jié)構(gòu)　  1.3.1　什么是數(shù)據(jù)結(jié)構(gòu)  　1.3.2　數(shù)據(jù)結(jié)構(gòu)的分類　  1.3.3　結(jié)點(diǎn)與結(jié)構(gòu)  　1.3.4　外存數(shù)據(jù)的組織  1.4　算法　　1.4.1　什么是算法　　1.4.2　算法的設(shè)計(jì)　　1.4.3　算法的精化　　1.4.4　算法的分析　小結(jié)　習(xí)題2　線性表　2.1　基本概念與抽象數(shù)據(jù)類型    2.1.1　基本概念    2.1.2　抽象數(shù)據(jù)類型  2.2　順序表示    2.2.1　存儲(chǔ)結(jié)構(gòu)    2.2.2　運(yùn)算的實(shí)現(xiàn)    2.2.3　分析與評(píng)價(jià)    2.2.4　順序表空間的擴(kuò)展　2.3　鏈接表示　　2.3.1　單鏈表表示　　2.3.2　單鏈表上運(yùn)算的實(shí)現(xiàn)　　2.3.3　分析與比較　　2.3.4　單鏈表的改進(jìn)和擴(kuò)充　2.4　應(yīng)用舉例　  2.4.1　Josephus問(wèn)題　  2.4.2　采用順序表模擬  　2.4.3　采用循環(huán)鏈表模擬　2.5　矩陣　  2.5.1　矩陣的順序表示　  2.5.2　稀疏矩陣的表示方法　2.6　廣義表與動(dòng)態(tài)存儲(chǔ)管理  　2.6.1　廣義表　  2.6.2　結(jié)點(diǎn)的動(dòng)態(tài)分配與回收　  2.6.3　廢料收集與存儲(chǔ)壓縮　小結(jié)　習(xí)題3　字符串  3.1　字符串及其抽象數(shù)據(jù)類型    3.1.1　基本概念    3.1.2　抽象數(shù)據(jù)類型  3.2　字符串的實(shí)現(xiàn)    3.2.1  順序表示    3.2.2　鏈接表示  3.3　模式匹配    3.3.1　樸素的模式匹配    3.3.2　無(wú)回溯的模式匹配  小結(jié)  習(xí)題4  線與隊(duì)列5  二叉樹(shù)與樹(shù)6  集合與字典7  高級(jí)字典結(jié)構(gòu)8  排序9  圖10  算法分析與設(shè)計(jì)參考文獻(xiàn)索引算法清單后記

編輯推薦

　　《算法與數(shù)據(jù)結(jié)構(gòu)：C語(yǔ)言描述（第2版）》以數(shù)據(jù)結(jié)構(gòu)為主線，算法為輔線組織教學(xué)內(nèi)容。全書(shū)共分10章：緒論、線性表、字符串、棧與隊(duì)列、二叉樹(shù)與樹(shù)、集合與字典、高級(jí)字典結(jié)構(gòu)、排序、圖和算法分析與設(shè)計(jì)?！端惴ㄅc數(shù)據(jù)結(jié)構(gòu)：C語(yǔ)言描述（第2版）》體系完整，概念清楚，內(nèi)容充實(shí)，取材適當(dāng)。第一版在2004年被評(píng)為“北京市高等教育精品教材”。

圖書(shū)封面

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

無(wú)

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

---

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

---