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

前言

《算法與數(shù)據(jù)結(jié)構(gòu)——C語(yǔ)言描述》（高等教育出版社，2002）是著者在二十多年從事“數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)實(shí)踐和教材建設(shè)的基礎(chǔ)上，為北京大學(xué)理科院系開(kāi)設(shè)的同名主干基礎(chǔ)課而編寫(xiě)的一本通用教材，在校內(nèi)外廣泛使用并受到讀者的好評(píng)。該書(shū)于2004年獲得“北京市高等教育精品教材獎(jiǎng)”。為了精益求精，經(jīng)過(guò)著者認(rèn)真修訂，2006年出版了第2版，2007年該書(shū)又榮獲教育部頒發(fā)的“普通高等教育精品教材獎(jiǎng)”。數(shù)據(jù)結(jié)構(gòu)與算法在計(jì)算機(jī)專(zhuān)業(yè)教育中的核心地位與重要作用是公認(rèn)的，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的困難也是廣大師生所共知的。多年來(lái)，許多老師和同學(xué)都曾向著者反映：十分需要數(shù)據(jù)結(jié)構(gòu)與算法的教學(xué)指導(dǎo)、實(shí)習(xí)指導(dǎo)、學(xué)習(xí)輔導(dǎo)和習(xí)題解答之類(lèi)的書(shū)。本書(shū)是原書(shū)著者應(yīng)廣大讀者需要編寫(xiě)的與該書(shū)配套的一本教學(xué)參考書(shū)。根據(jù)著者多年的教學(xué)經(jīng)驗(yàn)，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的難點(diǎn)在于解題。學(xué)生在解題中經(jīng)常出現(xiàn)的錯(cuò)誤，通常也是教材中沒(méi)有重點(diǎn)解釋的問(wèn)題。提高學(xué)生的知識(shí)水平光靠聽(tīng)課和看書(shū)是不夠的，在學(xué)生解題的過(guò)程中，可能會(huì)發(fā)現(xiàn)許多教學(xué)中忽視的問(wèn)題。如果挑選一批對(duì)于理解數(shù)據(jù)結(jié)構(gòu)的概念和思想有益的題目讓學(xué)生練習(xí)，可以有助于學(xué)生學(xué)得更活、理解得更深；在習(xí)題解答中標(biāo)明學(xué)生經(jīng)常出現(xiàn)的錯(cuò)誤，并且適當(dāng)加以解釋?zhuān)W(xué)生在自己獨(dú)立思考后參考，更能達(dá)到事半功倍的效果。算法是人類(lèi)智慧的結(jié)晶。在數(shù)據(jù)結(jié)構(gòu)的習(xí)題中，最難的無(wú)疑是算法題。算法題的答案不是唯一的，所以無(wú)法給出一個(gè)標(biāo)準(zhǔn)答案。編寫(xiě)習(xí)題解答的重點(diǎn)和難點(diǎn)是算法。設(shè)計(jì)算法的關(guān)鍵在于設(shè)計(jì)的思路，不同的思路產(chǎn)生出不同的算法。面對(duì)一個(gè)算法題，學(xué)生最需要的是如何開(kāi)始分析這個(gè)問(wèn)題和逐步解決這個(gè)問(wèn)題。所以對(duì)于每道復(fù)雜的算法題，不應(yīng)該僅僅給出一個(gè)程序，而需要首先給出問(wèn)題的分析、算法的思路，再給出程序和算法分析。對(duì)存在多個(gè)解法的題目，在給出一個(gè)算法的同時(shí)，還可以指出各種解法的缺點(diǎn)和改進(jìn)之處。這樣，學(xué)生可以從中體會(huì)到算法的真諦，從而真正有利于提高學(xué)生的算法設(shè)計(jì)與分析能力。應(yīng)用數(shù)據(jù)結(jié)構(gòu)與算法的知識(shí)解決實(shí)際問(wèn)題，并上機(jī)實(shí)現(xiàn)，是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的過(guò)程中不可缺少的環(huán)節(jié)。為了使上機(jī)實(shí)習(xí)取得事半功倍的效果，老師不但要選擇適當(dāng)?shù)膯?wèn)題，提出實(shí)習(xí)的具體要求和規(guī)定上機(jī)報(bào)告的內(nèi)容和形式；同時(shí)更需要給學(xué)生以具體幫助。實(shí)習(xí)題與算法題有類(lèi)似之處，但通常更加復(fù)雜。我們搜集了常見(jiàn)教材上的各種應(yīng)用問(wèn)題，并給出求解的樣例，其目的就是有助于組織好這一教學(xué)環(huán)節(jié)。

內(nèi)容概要

按照教育部計(jì)算機(jī)專(zhuān)業(yè)本科《數(shù)據(jù)結(jié)構(gòu)》教學(xué)大綱和新頒布的計(jì)算機(jī)專(zhuān)業(yè)碩士研究生入學(xué)考試《數(shù)據(jù)結(jié)構(gòu)》考試大綱的要求，本書(shū)精心挑選了覆蓋大綱全部要求的500多道習(xí)題，并且提供了所有題目的參考答案。    為了便于閱讀，在每章的開(kāi)頭概述了本章的主要內(nèi)容，指出了本章的學(xué)習(xí)的重點(diǎn)和難點(diǎn)；為了便于理解，對(duì)于較難的算法題和上機(jī)題，書(shū)中給出了比較詳細(xì)的分析；對(duì)于不同教材可能對(duì)答案造成的差異還給出了適當(dāng)?shù)恼f(shuō)明；對(duì)于學(xué)生易犯的錯(cuò)誤和題目的難易度、重要性等書(shū)中均明確給出提示。本書(shū)集多功能于一身，具有突出的系統(tǒng)性、完整性和針對(duì)性。    本書(shū)作者具有近30年從事數(shù)據(jù)結(jié)構(gòu)課程教學(xué)的經(jīng)驗(yàn)，編寫(xiě)了多本不同對(duì)象和不同語(yǔ)言描述的數(shù)據(jù)結(jié)構(gòu)教材。本書(shū)的目的是為各類(lèi)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的讀者，特別是希望考研的學(xué)生編寫(xiě)的一本通用教學(xué)參考書(shū)。全書(shū)采用作者最新出版的《算法與數(shù)據(jù)結(jié)構(gòu)-c語(yǔ)言描述（第2版）》統(tǒng)一的框架和同樣的語(yǔ)言表示，也包含了該書(shū)中全部習(xí)題的答案。該書(shū)在2007年榮獲教育部頒發(fā)的“十一五”國(guó)家級(jí)規(guī)劃教材“普通高等教育精品教材”獎(jiǎng)。

書(shū)籍目錄

第1章  緒論  1.1 主要內(nèi)容與方法    1.1.1 從問(wèn)題到程序    1.1.2 抽象數(shù)據(jù)類(lèi)型    1.1.3 數(shù)據(jù)結(jié)構(gòu)    1.1.4 算法  1.2 簡(jiǎn)單題  1.3 問(wèn)答題  1.4 算法分析題  1.5  應(yīng)用與上機(jī)題第2章  線性表  2.1 主要內(nèi)容與方法    2.1.1 基本概念與抽象數(shù)據(jù)類(lèi)型    2.1.2 順序表示    2.1.3 鏈接表示    2.1.4 矩陣與廣義表  2.2 簡(jiǎn)單題  2.3 問(wèn)答題    2.4 算法題  2.5 應(yīng)用與上機(jī)題第3章  字符串  3.1 主要內(nèi)容與方法    3.1.1 字符串及其抽象數(shù)據(jù)類(lèi)型    3.1.2 字符串的表示    3.1.3 模式匹配  3.2 簡(jiǎn)單題  3.3 問(wèn)答題  3.4 算法題  3.5 應(yīng)用與上機(jī)題第4章棧與隊(duì)列  4.1 主要內(nèi)容與方法    4.1.1 棧及其抽象數(shù)據(jù)類(lèi)型    4.1.2 棧的實(shí)現(xiàn)    4.1.3 棧與遞歸    4.1.4 隊(duì)列及其抽象數(shù)據(jù)類(lèi)型    4.1.5 隊(duì)列的實(shí)現(xiàn)  4.2 簡(jiǎn)單題  4.3 問(wèn)答題  4.4 算法題  4.5 應(yīng)用與上機(jī)題第5章  二叉樹(shù)、樹(shù)與樹(shù)林  5.1  主要內(nèi)容與方法    5.1.1 二叉樹(shù)及其抽象數(shù)據(jù)類(lèi)型    5.1.2 二叉樹(shù)的周游    5.1.3 二叉樹(shù)的實(shí)現(xiàn)    5.1.4 二叉樹(shù)的應(yīng)用    5.1.5 樹(shù)與樹(shù)林  5.2 簡(jiǎn)單題    5.2.1 是非題    5.2.2 選擇題    5.2.3 填空題  5.3 問(wèn)答題    5.3.1 基本概念    5.3.2 周游    5.3.3 存儲(chǔ)表示    5.3.4 轉(zhuǎn)換    5.3.5 堆與優(yōu)先隊(duì)列    5.3.6 哈夫曼樹(shù)    5.3.7 表達(dá)式樹(shù)  5.4 算法題  5.5 應(yīng)用與上機(jī)題第6章  集合與字典  6.1 主要內(nèi)容與方法    6.1.1 集合及其抽象數(shù)據(jù)類(lèi)型    6.1.2 集合的買(mǎi)現(xiàn)    6.1.3 字典及其抽象數(shù)據(jù)類(lèi)型    6.1.4 字典的順序表示    6.1.5 字典的散列表示  6.2 簡(jiǎn)單題  6.3 問(wèn)答題  6.4 算法題  6.5 應(yīng)用與上機(jī)題第7章  高級(jí)字典結(jié)構(gòu)  7.1 主要內(nèi)容與方法    7.1.1 字典與索引    7.1.2 字符樹(shù)    7.1.3 二叉排序樹(shù)    7.1.4 最佳二叉排序樹(shù)    7.1.5 平衡二叉排序樹(shù)    7.1.6 索引文件  7.2 簡(jiǎn)單題  7.3 問(wèn)答題    7.3.1 二叉排序樹(shù)    7.3.2 最佳二叉排序樹(shù)    7.3.3 平衡二叉排序樹(shù)    7.3.4 索引文件  7.4 算法題  7.5 應(yīng)用與上機(jī)題第8章  排序  8.1 主要內(nèi)容與方法  8.2 簡(jiǎn)單題  8.3 問(wèn)答題  8.4 算法題  8.5 應(yīng)用與上機(jī)題第9章  圖  9.1 主要內(nèi)容與方法    9.1.1 基本概念及其抽象數(shù)據(jù)類(lèi)型    9.1.2 圖的周游    9.1.3 存儲(chǔ)表示    9.1.4 最小生成樹(shù)    9.1.5 最短路徑    9.1.6 拓?fù)渑判蚺c關(guān)鍵路徑  9.2 簡(jiǎn)單題  9.3 問(wèn)答是亟    9.3.1 基本概念    9.3.2 存儲(chǔ)表示    9.3.3 周游與生成樹(shù)    9.3.4 最小生成樹(shù)    9.3.5 最短路徑    9.3.6 拓?fù)渑判蚺c關(guān)鍵路徑  9.4 算法題  9.5 應(yīng)用與上機(jī)題第10章  算法分析與設(shè)計(jì)  10.1 主要內(nèi)容與方法    10.1.1 算法分析技術(shù)    10.1.2 算法設(shè)計(jì)技術(shù)  10.2 簡(jiǎn)單題  10.3 算法分析題  10.4 算法設(shè)計(jì)題  10.5 應(yīng)用與上機(jī)題參考文獻(xiàn)

章節(jié)摘錄

插圖：11.什么是存儲(chǔ)密度？【答】存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)時(shí)，實(shí)際數(shù)據(jù)所占的空間與結(jié)構(gòu)所占總空間之比叫做存儲(chǔ)密度。12.解釋下列與文件相關(guān)的概念。（1）文件（2）記錄（3）關(guān)鍵碼（4）頁(yè)塊【答】文件是一種線性結(jié)構(gòu)，它一般放在外存儲(chǔ)器（簡(jiǎn)稱(chēng)外存）上，由許多記錄組成。記錄是數(shù)據(jù)項(xiàng)的集合，是文件中可以存取的邏輯單位。能夠唯一地標(biāo)識(shí)記錄的一個(gè)（或一組）字段叫做關(guān)鍵碼。一個(gè)頁(yè)塊（簡(jiǎn)稱(chēng)塊）是磁帶或磁盤(pán)上的一條物理記錄，通?？梢源娣哦鄺l邏輯記錄。內(nèi)存中設(shè)置的緩沖區(qū)應(yīng)該是頁(yè)塊大小的倍數(shù)。每次訪問(wèn)外存儲(chǔ)器，就是把一個(gè)頁(yè)塊讀入緩沖區(qū)或者把部分緩沖區(qū)內(nèi)容寫(xiě)到一個(gè)頁(yè)塊。分頁(yè)塊存儲(chǔ)的方法是一種有利于減少訪問(wèn)外存儲(chǔ)器的次數(shù)而又便于管理的方法。13.什么是順序文件？它有什么特點(diǎn)？【答】如果文件記錄的邏輯次序是按關(guān)鍵碼遞增（或遞減）次序定義的，并且在外存儲(chǔ)器上是按同樣的次序排列的，則這種文件叫做順序文件。由于順序文件中記錄的物理次序與邏輯次序是一致的，所以適宜順序存取（即存取一條記錄之后，接著將存取其后繼記錄）和成批處理。川頁(yè)序文件特別適用于磁帶存儲(chǔ)器，也適用于磁盤(pán)存儲(chǔ)器。順序文件的隨機(jī)存?。窗措S機(jī)給出的關(guān)鍵碼存取一條記錄）效率很低。14.什么是索引（順序）文件？它有什么特點(diǎn)？【答】索引表是由索引組成的表，每個(gè)索引項(xiàng)是一條記錄的關(guān)鍵碼和指向該記錄的指針組成的二元組。如果文件中每條記錄對(duì)應(yīng)一個(gè)索引項(xiàng)，則將這樣的索引稱(chēng)為密集索引；如果不是每條記錄都對(duì)應(yīng)一個(gè)索引項(xiàng)，例如，讓文件中每個(gè)頁(yè)塊對(duì)應(yīng)一個(gè)索引項(xiàng)，則這樣的索引稱(chēng)為稀疏索引。

編輯推薦

《算法與數(shù)據(jù)結(jié)構(gòu):學(xué)習(xí)指導(dǎo)與習(xí)題解析(第2版)》：普通高等教育“十一五”國(guó)家級(jí)規(guī)劃教材配套參考書(shū)

圖書(shū)封面

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

無(wú)

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

---

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

---