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

前言

數(shù)據(jù)結(jié)構(gòu)與算法緊密相關(guān)。算法是求解問題的步驟，它必須是確定的（無歧義）、可行的、有限的。此外，它可以有零個或多個輸入，但必須有輸出。注意不要將算法和計算機程序等同起來，后者可作為描述前者的手段之一。除了使用算法描述語言描述算法之外，還可用流程圖、形式語言、程序設(shè)計語言，甚至自然語言等對算法進行描述。但不管怎么樣，“算法是貫穿在所有計算機程序設(shè)計中的一個基本概念”（D. E. Knuth，1997）、“算法是計算機科學(xué)的靈魂”（Umesh Vazirani，2008）等觀點，卻是計算機界眾多學(xué)者所認同的。算法學(xué)是系統(tǒng)研究算法的一門科學(xué)。通常，它主要包括算法設(shè)計、算法正確性證明及算法分析三個部分。算法設(shè)計是創(chuàng)建算法的過程，它研究良好的創(chuàng)建方法以及算法與數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系和作用；算法或其關(guān)鍵步驟正確性證明的基本途徑是數(shù)學(xué)歸納法；算法時間復(fù)雜性分析是算法分析的重要內(nèi)容之一。在算法的時間復(fù)雜性分析方面，有時只得到復(fù)雜性的階是不夠的，要給出更精確的分析結(jié)果，還要知道復(fù)雜性的階前面的系數(shù)。自20世紀(jì)60年代初開始，計算機越發(fā)頻繁地用于解決一些非數(shù)值分析問題。解決這些問題主要使用計算機的邏輯判斷能力而非其算術(shù)運算能力。當(dāng)然，“非數(shù)值分析”實際上是關(guān)于這一研究領(lǐng)域的一個極其負面的稱謂，最好應(yīng)有一個正面的名稱?！靶畔⑻幚怼碧^寬泛，而“程序設(shè)計技術(shù)”又顯得過窄，稱其為“計算機算法分析”似乎恰當(dāng)一些。

內(nèi)容概要

本書是國家精品課程“數(shù)據(jù)結(jié)構(gòu)”的研究成果之一，是面向21世紀(jì)課程教材和普通高等教育“十一五”國家級規(guī)劃教材。本書系統(tǒng)介紹了數(shù)據(jù)結(jié)構(gòu)的概念、原理與技術(shù)，主要內(nèi)容包括緒論，基本數(shù)據(jù)結(jié)構(gòu)，排序、查找與內(nèi)存管理，相關(guān)工具和文件等。其中，第一章緒論主要對算法描述語言（ADL）、算法書寫規(guī)范、數(shù)據(jù)結(jié)構(gòu)與算法基本概念、算法分析基礎(chǔ)和算法正確性證明等進行了介紹；第二至五章是基本數(shù)據(jù)結(jié)構(gòu)部分，主要涉及線性表、堆棧和隊列，數(shù)組和字符串，樹與二叉樹，圖結(jié)構(gòu)等內(nèi)容；第七至九章從算法的視角討論了排序、查找和內(nèi)存管理等方面的內(nèi)容，給出了若干典型算法的描述、時間復(fù)雜性分析和相關(guān)算法的比較等；第六章和十一章分別對遞歸和隨機數(shù)兩種主要工具進行了講解，其中隨機數(shù)是數(shù)據(jù)結(jié)構(gòu)的新內(nèi)容；文件這種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)則在第十章中闡明。
本書的附錄主要包括書中ADL算法的C++程序、一些基本數(shù)據(jù)結(jié)構(gòu)的C++
類實現(xiàn)以及習(xí)題答案或解題思路。本書配套教學(xué)資源中包括電子教案、ADL
算法的C++程序、較難習(xí)題答案的C++代碼以及相關(guān)的測試和運行支持程序，可供讀者自學(xué)和上機使用。
本書可作為高等學(xué)校計算機相關(guān)專業(yè)的教材和教學(xué)參考書，也可供相關(guān)專業(yè)的工程技術(shù)人員參考使用。

作者簡介

劉大有，吉林大學(xué)教授、博士生導(dǎo)師。國家基金委專家評審組成員，吉林省計算機學(xué)會理事長，中國人工智能學(xué)會常務(wù)理事，知識工程與分布智能專委會副主任，中國計算機學(xué)會人工智能與模式識別專委會副主任。1997-2008年曾任國務(wù)院學(xué)位委員會學(xué)科評議組成員。在知識工程.專家系統(tǒng)、分布智能.智能體，時空推理和數(shù)據(jù)挖掘等方面取得了系統(tǒng)的創(chuàng)造性成果.為提高我國智能推理與智能系統(tǒng)等方面的研究與應(yīng)用水平做出了突出貢獻承擔(dān)國家和省部級項目50余項，出版著作9部，發(fā)表論文390余篇，三大檢索270余篇；獲國家科技進步獎2項、省部級科技進步獎9項；獲國家教學(xué)成果二等獎1項、省教學(xué)成果一等獎2項、國家精品課程和國家級教學(xué)團隊稱號；并獲國務(wù)院特殊津貼，省突出貢獻專家，首批和二批省管優(yōu)秀專家.一、二批省高級專家等榮譽。

書籍目錄

第一章 緒論
  1.1 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)
  1.2 數(shù)據(jù)結(jié)構(gòu)概念
    1.2.1 數(shù)據(jù)的邏輯結(jié)構(gòu)
    1.2.2 數(shù)據(jù)的存儲結(jié)構(gòu)
    1.2.3 對數(shù)據(jù)結(jié)構(gòu)的操作
    1.2.4 數(shù)據(jù)結(jié)構(gòu)示例
  1.3 算法
    1.3.1 算法及其特性
    1.3.2 算法的描述
    1.3.3 算法的評價準(zhǔn)則
  1.4 算法的正確性證明
  1.5 算法分析基礎(chǔ)
    1.5.1 算法時間復(fù)雜性的分析方法
    1.5.2 復(fù)雜性函數(shù)的漸近表示
    1.5.3 算法時間與空間分析
    1.5.4 計算復(fù)雜性和算法的效率
  小結(jié)
  參考文獻與推薦讀物
  習(xí)題
第二章 線性表、堆棧和隊列
  2.1 線性表的定義和基本操作
  2.2 線性表的順序存儲結(jié)構(gòu)
  2.3 線性表的鏈接存儲結(jié)構(gòu)
    2.3.1 單鏈表
    2.3.2 循環(huán)鏈表
    2.3.3 雙向鏈表
  2.4 復(fù)雜性分析
  2.5 堆棧
    2.5.1 堆棧的定義和基本操作
    2.5.2 順序棧
    2.5.3 鏈?zhǔn)綏?br />    2.5.4 順序棧與鏈?zhǔn)綏５谋容^
    2.5.5 堆棧應(yīng)用——括號匹配
  2.6 隊列
    2.6.1 隊列的定義和基本操作
    2.6.2 順序隊列
    2.6.3 鏈?zhǔn)疥犃?br />    2.6.4 順序隊列與鏈?zhǔn)疥犃械谋容^
    2.6.5 隊列與堆棧的擴展
  小結(jié)
  參考文獻與推薦讀物
  習(xí)題
第三章 數(shù)組和字符串
  3.1 數(shù)組
    3.1.1 數(shù)組的存儲和尋址
    3.1.2 一維數(shù)組類
  3.2 矩陣
    3.2.1 矩陣類
    3.2.2 特殊矩陣
    3.2.3 三元組表
    3.2.4 十字鏈表
  3.3 字符串
    3.3.1 字符串的定義與字符串類
    3.3.2 模式匹配算法
  小結(jié)
  參考文獻與推薦讀物
  習(xí)題
第四章 樹
  4.1 樹的基本概念
    4.1.1 樹的定義
    4.1.2 樹的相關(guān)術(shù)語
  4.2 二叉樹
    4.2.1 二叉樹定義和主要性質(zhì)
    4.2.2 二叉樹順序存儲
    4.2.3 二叉樹鏈接存儲
    4.2.4 二叉樹遍歷
    4.2.5 創(chuàng)建二叉樹
    4.2.6 復(fù)制二叉樹
  4.3 線索二叉樹
    4.3.1 線索二叉樹定義
    4.3.2 線索二叉樹存儲
    4.3.3 線索二叉樹基本算法
  4.4 樹和森林
    4.4.1 樹與二叉樹的轉(zhuǎn)換
    4.4.2 樹的順序存儲
    4.4.3 樹的鏈接存儲
    4.4.4 樹和森林的遍歷
  4.5 壓縮與哈夫曼樹
    4.5.1 文件編碼
    4.5.2 擴充二叉樹
    4.5.3 哈夫曼樹和哈夫曼編碼
  4.6 應(yīng)用
    4.6.1 表達式求值
    4.6.2 分類與決策樹
  小結(jié)
  參考文獻與推薦讀物
  習(xí)題
第五章 圖
  5.1 圖的基本概念
  5.2 圖的存儲結(jié)構(gòu)與類定義
    5.2.1 存儲結(jié)構(gòu)
    5.2.2 Graph類
  5.3 圖的遍歷算法
    5.3.1 深度優(yōu)先遍歷
    5.3.2 廣度優(yōu)先遍歷
  5.4 拓撲排序
  5.5 關(guān)鍵路徑
  5.6 最短路徑問題
    5.6.1 無權(quán)最短路徑問題
    5.6.2 正權(quán)最短路徑問題
    5.6.3 每對頂點之間的最短路徑
  5.7 最小支撐樹
    5.7.1 普里姆算法
    5.7.2 克魯斯卡爾算法
  5.8 圖的應(yīng)用
    5.8.1 可及性與Wahall算法
    5.8.2 連通分量
    5.8.3 圖在網(wǎng)絡(luò)分析和信息檢索中的應(yīng)用
  小結(jié)
  參考文獻與推薦讀物
  習(xí)題
第六章 遞歸
  6.1 遞歸的定義
  6.2 基本遞歸過程
  6.3 遞歸過程實現(xiàn)與堆棧
  6.4 遞歸法求解問題
    6.4.1 委員會問題
    6.4.2 回溯
  6.5 遞歸的效率
  小結(jié)
  參考文獻與推薦讀物
  習(xí)題
第七章 排序
  7.1 排序問題的基本概念
  7.2 插入排序
    7.2.1 直接插入排序
    7.2.2 Shell排序
  7.3 交換排序
    7.3.1 冒泡排序
    7.3.2 快速排序
  7.4 選擇排序
    7.4.1 直接選擇排序
    7.4.2 堆排序
  7.5 合并排序
  7.6 基于關(guān)鍵詞比較的排序算法分析
    7.6.1 平方階排序算法及改進算法
    7.6.2 線性對數(shù)階排序算法
    7.6.3 分治排序的一般方法
    7.6.4 基于關(guān)鍵詞比較的排序算法下界
  7.7 分布排序
    7.7.1 基數(shù)分布
    7.7.2 值分布
  7.8 外排序
    7.8.1 外存儲器
    7.8.2 磁帶排序
    7.8.3 磁盤排序
  小結(jié)
  參考文獻與推薦讀物
  習(xí)題
第八章 查找
  8.1 順序查找
    8.1.1 無序表的順序查找
    8.1.2 有序表的順序查找
  8.2 基于關(guān)鍵詞比較的查找
    8.2.1 對半查找
    8.2.2 一致對半查找
    8.2.3 斐波那契查找
    8.2.4 插值查找
  8.3 二叉查找樹
    8.3.1 基本概念和性質(zhì)
    8.3.2 查找、插入和刪除
    8.3.3 平均情況時間分析
  8.4 最優(yōu)二叉查找樹
    8.4.1 訪問頻率
    8.4.2 最優(yōu)二叉查找樹
    8.4.3 近似最優(yōu)樹的構(gòu)造
  8.5 平衡樹
    8.5.1 高度平衡樹
    8.5.2 重量平衡樹
  8.6 紅黑樹
    8.6.1 紅黑樹的性質(zhì)
    8.6.2 旋轉(zhuǎn)
    8.6.3 插入
    8.6.4 刪除
  8.7 B樹及其變形樹
    8.7.1 多又樹
    8.7.2 B樹
    8.7.3 B樹變形樹
  8.8 數(shù)字查找
    8.8.1 檢索結(jié)構(gòu)查找
    8.8.2 數(shù)字樹查找
  8.9 散列
    8.9.1 散列函數(shù)
    8.9.2 沖突調(diào)節(jié)
    8.9.3 刪除
    8.9.4 重量平衡樹的應(yīng)用——按位置查找
  小結(jié)
  參考文獻與推薦讀物
  習(xí)題
第九章 內(nèi)存管理
  9.1 概述
  9.2 均勻大小記錄的分配和回收算法
    9.2.1 記錄分配算法
    9.2.2 訪問計數(shù)器法
    9.2.3 廢料收集方法
  9.3 不同大小記錄的分配和回收算法
    9.3.1 查找分配策略
    9.3.2 邊界標(biāo)識法
    9.3.3 壓縮分配
  9.4 伙伴系統(tǒng)
    9.4.1 伙伴系統(tǒng)概述
    9.4.2 分配記錄和釋放記錄算法
  小結(jié)
  參考文獻與推薦讀物
  習(xí)題
第10章 文件
  10.1 文件的基本概念
    10.1.1 文件及其分類
    10.1.2 文件的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)
  10.2 順序文件
    10.2.1 順序無序文件
    10.2.2 順序有序文件
    10.2.3 增補文件
  10.3 散列文件
    10.3.1 散列文件
    10.3.2 可擴充的散列文件
  10.4 索引文件
    10.4.1 動態(tài)索引結(jié)構(gòu)和靜態(tài)索引結(jié)構(gòu)
    10.4.2 ISAM文件
    10.4.3 VSAM文件
  10.5 多關(guān)鍵字文件
    10.5.1 多重鏈表文件
    10.5.2 倒排文件
  小結(jié)
  參考文獻與推薦讀物
  習(xí)題
第11章 隨機數(shù)
  11.1 生成隨機數(shù)
    11.1.1 均勻分布隨機數(shù)
    11.1.2 其他分布隨機數(shù)
  11.2 隨機數(shù)檢驗
    11.2.1 一般檢驗方法
    11.2.2 經(jīng)驗檢驗方法
  11.3 隨機排列與隨機組合
    11.3.1 隨機排列
    11.3.2 隨機組合
  11.4 應(yīng)用
    11.4.1 隨機算法
    11.4.2 使用隨機數(shù)的快速排序算法
  小結(jié)
  參考文獻與推薦讀物
  習(xí)題
附錄
  附錄1 各章算法的C++實現(xiàn)
  附錄2 習(xí)題參考答案或解題思路

章節(jié)摘錄

插圖：本章的補充讀物建議如下：文獻[8]把數(shù)據(jù)結(jié)構(gòu)原理和算法分析技術(shù)有機結(jié)合在一起，系統(tǒng)介紹了基本的數(shù)據(jù)結(jié)構(gòu)、算法分析技術(shù)以及排序和檢索的各種方法，并簡要介紹了較高級的數(shù)據(jù)結(jié)構(gòu)和可計算性理論的一般知識。文獻[9]對算法分析所涉及的、幾乎取自每一數(shù)學(xué)分支的數(shù)學(xué)計算（或技術(shù)）進行了全面、深入的討論；精辟介紹了各種經(jīng)典算法，對算法復(fù)雜性進行了嚴格分析，透徹闡明了算法正確性證明的方法；給出了數(shù)據(jù)結(jié)構(gòu)概念的嚴密定義；徹底厘清了數(shù)據(jù)結(jié)構(gòu)的歷史、文獻和發(fā)展脈絡(luò)。文獻[9]無疑是數(shù)據(jù)結(jié)構(gòu)和算法方面的一部最權(quán)威、內(nèi)容最豐富的經(jīng)典著作。文獻[10]提出了一種對算法進行分類的新方法，基于該方法介紹了一些經(jīng)典的算法設(shè)計技術(shù)，給出了算法效率分析的框架和分析方法。文獻[11]系統(tǒng)地介紹了基本數(shù)據(jù)結(jié)構(gòu)以及算法設(shè)計的方法、技術(shù)和應(yīng)用實例。文獻[12]從算法設(shè)計與算法分析的基本概念和方法入手，介紹了常用、經(jīng)典的算法設(shè)計技術(shù)，給出每種技術(shù)的特征、應(yīng)用背景和應(yīng)用實例，并詳細分析了每個算法的復(fù)雜性。文獻[13]介紹了基本數(shù)據(jù)結(jié)構(gòu)，將算法設(shè)計與分析結(jié)合在一起，重點討論了算法的設(shè)計策略、下界理論、NP難題和NP完全問題、近似算法和并行算法等。文獻[14]對計算機算法、算法設(shè)計策略進行了全面、深入的介紹，采用大量的插圖說明算法的工作過程，每一個算法都給出了其運行時間的詳細分析，分析過程既保持了數(shù)學(xué)的嚴謹性，又易于理解。

編輯推薦

《數(shù)據(jù)結(jié)構(gòu)(第2版)》特色：·采用兩種語言描述算法《數(shù)據(jù)結(jié)構(gòu)(第2版)》正文采用算法描述語言ADL描述算法。附錄提供算法的C++實現(xiàn)。這樣做有利于讀者將注意力聚焦于數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)鍵部分．彌補了用C++語言描述算法既占用較多篇幅，又涉及較多程序設(shè)計細節(jié)的不足。·強調(diào)“數(shù)據(jù)結(jié)構(gòu)的嚴格性”《數(shù)據(jù)結(jié)構(gòu)(第2版)》對典型算法或給出時間復(fù)雜性分析或分析結(jié)果，特別對時間復(fù)雜性階相同的相關(guān)算法，既給出算法復(fù)雜性的階，又給出階前面的系數(shù)；對某些算法，給出其關(guān)鍵問題(或步驟)的正確性證明。注重分析與證明的嚴格性。·突出啟發(fā)式教學(xué)與因材施教《數(shù)據(jù)結(jié)構(gòu)(第2版)》對一些較難的知識點設(shè)計了啟發(fā)式教學(xué)案例。在相關(guān)算法的銜接處，闡明后續(xù)算法形成的思想及其主要特點；在展開算法描述之前，給出算法關(guān)鍵思想的刻畫；在每章結(jié)尾處。給出相關(guān)算法的比較。此外，對習(xí)題給出了難度級別，對較難習(xí)題給出了分級提示?！づ涮捉虒W(xué)資源豐富《數(shù)據(jù)結(jié)構(gòu)(第2版)》提供配套的電子講稿、全書ADL算法的C++程序、較難習(xí)題答案的C++代碼及相關(guān)的測試和運行支持程序(可從中國高校計算機課程網(wǎng)上下載)，可供讀者自學(xué)和上機使用。

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

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

---