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

內(nèi)容概要

　　《算法與數(shù)據(jù)結(jié)構(gòu)：c語(yǔ)言描述（第3版）》以數(shù)據(jù)結(jié)構(gòu)為主線、算法為輔線組織教學(xué)內(nèi)容。全書共10章，內(nèi)容包括緒論、線性表、字符串、棧與隊(duì)列、二叉樹與樹、集合與字典、高級(jí)字典結(jié)構(gòu)、排序、圖、算法分析與設(shè)計(jì)。本書第1版為“面向21世紀(jì)課程教材”，2004年被評(píng)為“北京市高等教育精品教材，第2版為普通高等教育“十一五”國(guó)家級(jí)規(guī)劃教材，2007年獲“普通高等教育精品教材”獎(jiǎng)?！　　端惴ㄅc數(shù)據(jù)結(jié)構(gòu)：c語(yǔ)言描述（第3版）》體系完整、概念清楚、內(nèi)容充實(shí)、取材適當(dāng)，采用“數(shù)據(jù)結(jié)構(gòu)作為抽象數(shù)據(jù)類型的物理實(shí)現(xiàn)”觀點(diǎn)，既提高了抽象數(shù)據(jù)類型在本課程教學(xué)中的地位和作用，又突出了自身的教學(xué)重點(diǎn)。本書在講解知識(shí)的同時(shí)，重視能力的培養(yǎng)，以提高學(xué)生運(yùn)用知識(shí)解決實(shí)際問題的能力。新版對(duì)第2版教材中許多算法進(jìn)行了改進(jìn)，力求為讀者提供一套具有良好c語(yǔ)言風(fēng)格．更便于教學(xué)的程序代碼，以期幫助學(xué)生從中體會(huì)到算法的魅力和c語(yǔ)言編程的藝術(shù)，提高學(xué)生的學(xué)習(xí)興趣。同時(shí)，新版內(nèi)容也適當(dāng)?shù)靥岣吡酥R(shí)的深度和廣度，完全覆蓋了最新考研大綱的內(nèi)容要求。　　《算法與數(shù)據(jù)結(jié)構(gòu)：c語(yǔ)言描述（第3版）》許多知識(shí)模塊具有一定的獨(dú)立性和相關(guān)性，因此不同專業(yè)和不同水平的讀者可以根據(jù)需要組合使用。本書既可以作為計(jì)算機(jī)專業(yè)本科“數(shù)據(jù)結(jié)構(gòu)”課程教材，也可以作為理工科有關(guān)專業(yè)本科和計(jì)算機(jī)專業(yè)?？葡嚓P(guān)課程的教材或考研參考書。

作者簡(jiǎn)介

張乃孝，北京大學(xué)教授、博士生導(dǎo)師，曾任北京大學(xué)計(jì)算機(jī)系數(shù)據(jù)庫(kù)教研室主任、理論教研室主任和北京大學(xué)數(shù)學(xué)學(xué)院信怠系副主任；全國(guó)計(jì)算機(jī)學(xué)會(huì)“數(shù)據(jù)組織與結(jié)構(gòu)”學(xué)組副組長(zhǎng)和“軟件理論”學(xué)組副組長(zhǎng)。長(zhǎng)期從事“新語(yǔ)言”和“程序設(shè)計(jì)方法學(xué)”的研究，主持和參加了十多個(gè)國(guó)家級(jí)科研項(xiàng)目，提出“面向語(yǔ)言的方法學(xué)”。長(zhǎng)期從事基礎(chǔ)課教學(xué)，發(fā)表論文數(shù)十篇，出版教材十余本。曾獲“第一次全國(guó)科學(xué)大會(huì)獎(jiǎng)”、“全國(guó)優(yōu)秀教材獎(jiǎng)”、“北京市高等教育精品教材”獎(jiǎng)和“普通高等教育精品教材”獎(jiǎng)，并多次獲得北京大學(xué)教學(xué)優(yōu)秀獎(jiǎng)和科研成果獎(jiǎng)。個(gè)人簡(jiǎn)歷收入世界名人錄“Who Is Who in theWorld”等。

書籍目錄

第1章緒論 1.1從問題到程序 1.1.1問題分析與抽象 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.1Josephus問題 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ì)列 4.1棧及其抽象數(shù)據(jù)類型 4.1.1基本概念 4.1.2抽象數(shù)據(jù)類型 4.2棧的實(shí)現(xiàn) 4.2.1順序表示 4.2.2鏈接表示 4.3棧的應(yīng)用 4.3.1棧與遞歸 4.3.2迷宮問題 4.3.3表達(dá)式計(jì)算 4.4隊(duì)列及其抽象數(shù)據(jù)類型 4.4.1基本概念 4.4.2抽象數(shù)據(jù)類型 4.5隊(duì)列的實(shí)現(xiàn) 4.5.1順序表示 4.5.2鏈接表示 4.6隊(duì)列的應(yīng)用 小結(jié) 習(xí)題 第5章二叉樹與樹 5.1二叉樹及其抽象數(shù)據(jù)類型 5.1.1基本概念 5.1.2主要性質(zhì) 5.1.3抽象數(shù)據(jù)類型 5.2二叉樹的周游 5.2.1什么是周游 5.2.2周游的分類 5.2.3一個(gè)例子 5.2.4周游的抽象算法 5.3二叉樹的實(shí)現(xiàn) 5.3.1順序表示 5.3.2鏈接表示 5.3.3線索二叉樹 5.4二叉樹的應(yīng)用 5.4.1堆與優(yōu)先隊(duì)列 5.4.2哈夫曼樹及其應(yīng)用 5.5樹及其抽象數(shù)據(jù)類型 5.5.1基本概念 5.5.2抽象數(shù)據(jù)類型 5.5.3樹的周游 5.6樹的實(shí)現(xiàn) 5.6.1父指針表示法 5.6.2子表表示法 5.6.3長(zhǎng)子一兄弟表示法 5.6.4樹的其他表示法 5.7樹林 5.7.1樹林的周游 5.7.2樹林的存儲(chǔ)表示 5.7.3樹林與二叉樹的轉(zhuǎn)換 小結(jié) 習(xí)題 第6章集合與字典 6.1集合及其抽象數(shù)據(jù)類型 6.1.1基本概念 6.1.2主要運(yùn)算 6.1.3抽象數(shù)據(jù)類型 6.2集合的實(shí)現(xiàn) 6.2.1集合的位向量表示 6.2.2集合的單鏈表表示 6.3字典及其抽象數(shù)據(jù)類型 6.3.1基本概念 6.3.2抽象數(shù)據(jù)類型 6.4字典的順序表示 6.4.1存儲(chǔ)結(jié)構(gòu) 6.4.2算法的實(shí)現(xiàn) 6.4.3 有序順序表與二分法檢索 6.5字典的散列表示 6.5.1基本概念 6.5.2散列函數(shù) 6.5.3碰撞的處理 6.5.4散列文件 小結(jié) 習(xí)題 第7章高級(jí)字典結(jié)構(gòu) 7.1字典與索引 7.1.1字典的索引 7.1.2索引的抽象 7.2字符樹 7.2.1雙鏈樹表示 7.2.2多鏈表示 7.3二叉排序樹 7.3.1二叉排序樹 7.3.2二叉排序樹的檢索 7.3.3二叉排序樹的插入和構(gòu)造 7.3.4二叉排序樹的刪除 7.4最佳二叉排序樹 7.4.1基本概念 7.4.2等概率的檢索 7.4.3不等概的情況 7.5平衡二叉排序樹 7.5.1基本概念 7.5.2調(diào)整平衡的模式 7.5.3實(shí)現(xiàn) 7.6索引文件 7.6.1多分樹 7.6.2B樹 7.6.3B+樹 小結(jié) 習(xí)題 第8章排序 8.1基本概念 8.2插入排序 8.2.1直接插入排序 8.2.2二分法插入排序 8.2.3表插入排序 8.2.4Shell排序 8.3選擇排序 8.3.1直接選擇排序 8.3.2堆排序 8.4交換排序 8.4.1起泡排序 8.4.2快速排序 8.5分配排序 8.5.1概述 8.5.2基數(shù)排序 8.6歸并排序 8.6.1內(nèi)排序 8.6.2外排序 小結(jié) 習(xí)題 第9章圖 9.1基本概念及其抽象數(shù)據(jù)類型 9.1.1基本概念 9.1.2抽象數(shù)據(jù)類型 9.2圖的周游 9.2.1深度優(yōu)先周游 9.2.2廣度優(yōu)先周游 9.3存儲(chǔ)表示 9.3.1鄰接矩陣表示法 9.3.2鄰接表表示法 9.3.3兩種表示的比較 9.4最小生成樹 9.4.I最小生成樹及其性質(zhì) 9.4.2最小生成樹的構(gòu)造 9.5最短路徑 9.5.1Dijkstra算法 9.5.2Floyd算法 9.6拓?fù)渑判?9.6.1AOV網(wǎng) 9.6.2拓?fù)渑判?9.7關(guān)鍵路徑 9.7.1AOE網(wǎng) 9.7.2關(guān)鍵路徑 小結(jié) 習(xí)題 第10章算法分析與設(shè)計(jì) 10.1算法分析技術(shù) 10.1.1空間代價(jià)分析 10.1.2時(shí)間代價(jià)分析 10.2算法設(shè)計(jì)技術(shù) 10.2.1分治法 10.2.2貪心法 10.2.3動(dòng)態(tài)規(guī)劃法 10.2.4回溯法 10.2.5分枝界限法與0／1背包問題 小結(jié) 習(xí)題 索引 算法清單 參考文獻(xiàn)

章節(jié)摘錄

版權(quán)頁(yè)：   插圖：   1.1.2 程序的設(shè)計(jì)與實(shí)現(xiàn) 一般來(lái)說(shuō)，一個(gè)問題的解決可以有許多辦法，由于使用的工具是計(jì)算機(jī)，所以在選擇方法時(shí)必須充分考慮到計(jì)算機(jī)的特點(diǎn)和條件，才能找到比較巧妙的辦法，比較快而且準(zhǔn)確地計(jì)算出需要的結(jié)果。 對(duì)于前面抽象出來(lái)的著色問題，下面介紹一種簡(jiǎn)單的求解方法，目的在于使讀者從中體會(huì)從問題抽象的模型到實(shí)現(xiàn)模型的設(shè)計(jì)過程。 選擇算法 窮舉琺 求一般著色問題的最優(yōu)解，可以采用窮舉法，具體做法是：從分為1，2，3……組開始考察，逐個(gè)列舉出所有可能的著色方案，檢查這樣的分組方案是否滿足要求。首先滿足要求的分組，自然是問題的最優(yōu)解。 具體來(lái)講，假設(shè)求解的圖中有n個(gè)結(jié)點(diǎn)，首先考察如果放在一個(gè)組里（這時(shí)顯然只有一種著色方式）是否可行，即考察組里的結(jié)點(diǎn)是否有線相連。如果沒有，最優(yōu)解已經(jīng)找到；否則考察如果放在兩個(gè)組里是否可行，這時(shí)需要逐個(gè)窮舉出所有可能的分成兩個(gè)組的方案，這個(gè)數(shù)可能很大。例如，兩個(gè)組按1：n—1分配，就有C1n=n種方案，按2：n—2分配，就有C2n=n（n—1）／2種方案等。當(dāng)考察了所有放在兩個(gè)組里可能的方案后，如果都不行的話，接著考慮分為三組、四組的各種組合。以此類推，最多到分成n組，最終總能成功。 但是，對(duì)于規(guī)模大的問題，由于求解時(shí)間會(huì)隨著實(shí)際問題規(guī)模的增長(zhǎng)而呈指數(shù)級(jí)上升，這類窮舉法可能使計(jì)算機(jī)無(wú)法承受（有耐心的讀者，不妨對(duì)上述信號(hào)燈問題親自動(dòng)手模擬一下這個(gè)窮舉法的求解過程）。 當(dāng)然，對(duì)于一般（任意規(guī)模）的著色問題，存在一些比窮舉法更快的求最優(yōu)解的算法，因?yàn)槌霰菊n教學(xué)范圍，不在此展開討論。實(shí)際上，對(duì)于一個(gè)具體的著色問題（例如本節(jié)開頭提出的信號(hào)燈問題），并沒有必要一定找到其最優(yōu)解。下面給出的是一個(gè)比窮舉法快得多的，但是通常能夠求出次優(yōu)解的算法。 貪心法 求著色問題的次優(yōu)解，一種簡(jiǎn)單的方法稱為貪心法：先用一種顏色給盡可能多的結(jié)點(diǎn)上色，只要這些結(jié)點(diǎn)之間沒有邊相連；然后再用另一種顏色在未著色結(jié)點(diǎn)中給盡可能多的結(jié)點(diǎn)上色，如此反復(fù)，直到所有結(jié)點(diǎn)都著色為止。

編輯推薦

《面向21世紀(jì)課程教材:算法與數(shù)據(jù)結(jié)構(gòu):C語(yǔ)言描述(第3版)》編輯推薦：許多知識(shí)模塊具有一定的獨(dú)立性和相關(guān)性，因此不同專業(yè)和不同水平的讀者可以根據(jù)需要組合使用。《面向21世紀(jì)課程教材:算法與數(shù)據(jù)結(jié)構(gòu):C語(yǔ)言描述(第3版)》既可以作為計(jì)算機(jī)專業(yè)本科“數(shù)據(jù)結(jié)構(gòu)”課程教材，也可以作為理工科有關(guān)專業(yè)本科和計(jì)算機(jī)專業(yè)?？葡嚓P(guān)課程的教材或考研參考書。

圖書封面

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

---

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

---