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

內(nèi)容概要

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

作者簡介

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

書籍目錄

第1章緒論 1.1從問題到程序 1.1.1問題分析與抽象 1.1.2程序的設計與實現(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é)點與結(jié)構(gòu) 1.3.4外存數(shù)據(jù)的組織 1.4算法 1.4.1什么是算法 1.4.2算法的設計 1.4.3算法的精化 1.4.4算法的分析 小結(jié) 習題 第2章線性表 2.1基本概念與抽象數(shù)據(jù)類型 2.1.1基本概念 2.1.2抽象數(shù)據(jù)類型 2.2順序表示 2.2.1存儲結(jié)構(gòu) 2.2.2運算的實現(xiàn) 2.2.3分析與評價 2.2.4順序表空間的擴展 2.3鏈接表示 2.3.1單鏈表表示 2.3.2單鏈表上運算的實現(xiàn) 2.3.3分析與比較 2.3.4單鏈表的改進和擴充 2.4應用舉例 2.4.1Josephus問題 2.4.2采用順序表模擬 2.4.3采用循環(huán)鏈表模擬 2.5矩陣 2.5.1矩陣的順序表示 2.5.2稀疏矩陣的表示方法 2.6廣義表與動態(tài)存儲管理 2.6.1廣義表 2.6.2結(jié)點的動態(tài)分配與回收 2.6.3廢料收集與存儲壓縮 小結(jié) 習題 第3章字符串 3.1字符串及其抽象數(shù)據(jù)類型 3.1.1基本概念 3.1.2抽象數(shù)據(jù)類型 3.2字符串的實現(xiàn) 3.2.1順序表示 3.2.2鏈接表示 3.3模式匹配 3.3.1樸素的模式匹配 3.3.2無回溯的模式匹配 小結(jié) 習題 第4章棧與隊列 4.1棧及其抽象數(shù)據(jù)類型 4.1.1基本概念 4.1.2抽象數(shù)據(jù)類型 4.2棧的實現(xiàn) 4.2.1順序表示 4.2.2鏈接表示 4.3棧的應用 4.3.1棧與遞歸 4.3.2迷宮問題 4.3.3表達式計算 4.4隊列及其抽象數(shù)據(jù)類型 4.4.1基本概念 4.4.2抽象數(shù)據(jù)類型 4.5隊列的實現(xiàn) 4.5.1順序表示 4.5.2鏈接表示 4.6隊列的應用 小結(jié) 習題 第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一個例子 5.2.4周游的抽象算法 5.3二叉樹的實現(xiàn) 5.3.1順序表示 5.3.2鏈接表示 5.3.3線索二叉樹 5.4二叉樹的應用 5.4.1堆與優(yōu)先隊列 5.4.2哈夫曼樹及其應用 5.5樹及其抽象數(shù)據(jù)類型 5.5.1基本概念 5.5.2抽象數(shù)據(jù)類型 5.5.3樹的周游 5.6樹的實現(xiàn) 5.6.1父指針表示法 5.6.2子表表示法 5.6.3長子一兄弟表示法 5.6.4樹的其他表示法 5.7樹林 5.7.1樹林的周游 5.7.2樹林的存儲表示 5.7.3樹林與二叉樹的轉(zhuǎn)換 小結(jié) 習題 第6章集合與字典 6.1集合及其抽象數(shù)據(jù)類型 6.1.1基本概念 6.1.2主要運算 6.1.3抽象數(shù)據(jù)類型 6.2集合的實現(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存儲結(jié)構(gòu) 6.4.2算法的實現(xiàn) 6.4.3 有序順序表與二分法檢索 6.5字典的散列表示 6.5.1基本概念 6.5.2散列函數(shù) 6.5.3碰撞的處理 6.5.4散列文件 小結(jié) 習題 第7章高級字典結(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實現(xiàn) 7.6索引文件 7.6.1多分樹 7.6.2B樹 7.6.3B+樹 小結(jié) 習題 第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é) 習題 第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存儲表示 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拓撲排序 9.6.1AOV網(wǎng) 9.6.2拓撲排序 9.7關(guān)鍵路徑 9.7.1AOE網(wǎng) 9.7.2關(guān)鍵路徑 小結(jié) 習題 第10章算法分析與設計 10.1算法分析技術(shù) 10.1.1空間代價分析 10.1.2時間代價分析 10.2算法設計技術(shù) 10.2.1分治法 10.2.2貪心法 10.2.3動態(tài)規(guī)劃法 10.2.4回溯法 10.2.5分枝界限法與0／1背包問題 小結(jié) 習題 索引 算法清單 參考文獻

章節(jié)摘錄

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

編輯推薦

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

圖書封面

評論、評分、閱讀與下載

---

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

---