出版時間:2008-3 作者:王震江 編
內容概要
本書可分為6個部分,分別為緒論、線性表、樹、圖、查找與排序、文件。 第1章概述數(shù)據結構可能涉及的內容和分析方法,講述了算法和程序的差異,算法的評價等問題。 第2、3、4、5章講述線性表結構、特殊線性表——棧和隊列、字符串和數(shù)組與廣義表。從順序存儲結構和鏈表結構兩個方面來闡述線性表的存儲結構和建立在存儲結構之上的算法設計,以及線性表的廣泛應用,如棧、隊列、字符串、數(shù)組、廣義表等,并進一步討論了這些數(shù)據結構的應用,如程序調用、中斷、皇后問題、火車編組問題等。 第6章討論樹。本書與其他教材不同的是,深入討論了一般樹的記數(shù)、層次、樹高等基本問題。在二叉樹的生成中講解了多種生成算法。在二叉樹的前序、中序和后序遍歷運算中討論了樹的遞歸和非遞歸算法遍歷算法,除此之外,還討論了歐拉遍歷和按層次遍歷,討論了線索二叉樹及其應用,二叉樹的典型應用——哈夫曼樹和哈夫曼編碼、排序樹、平衡樹、2—3樹、紅黑樹、表示樹、判定樹等問題。 第7章討論圖。內容包括圖、圖的遍歷、生成樹問題、最短路徑問題、拓撲排序和關鍵路徑等。 第8、9章討論目前常見的查找算法和排序算法。在查找算法中,從靜態(tài)表、動態(tài)表和哈希表三個方面來研究查找算法。靜態(tài)表的數(shù)據結構是線性表,動態(tài)表的查找主要有二叉樹查找、B樹查找和鍵樹查找等,哈希表的構造和查找則用哈希算法來實現(xiàn)。在排序中分為內排序和外排序兩個部分。內排序中主要討論了插入排序、交換排序、選擇排序、歸并排序、基數(shù)排序等8種經典的排序算法。外排序討論了磁盤排序、勝者樹和敗者樹、最佳歸并樹和磁帶排序等。 第10章討論了文件。從文件的存儲結構入手討論文件的管理,有順序文件、索引文件、索引順序文件、散列文件、多關鍵字文件等。 上述內容涵蓋了目前國內數(shù)據結構教材的幾乎所有內容,有的進行了深入的討論,有的比較初步,這與教材編寫的指導思想有關。 本書由王震江擔任主編,何英、吳紹兵任副主編。其中第1章、第2章(部分)、第3章、第4章、第6章由王震江編寫,第2章(部分)、第5章、第8章、第9章由吳紹兵編寫,第7章、第10章由何英編寫。王震江對全書進行了主審,統(tǒng)一了圖例。俞銳剛調試通過了全部算法,統(tǒng)編了全書的習題。邱莎審改了全文。
書籍目錄
第l章 緒論 1.1 數(shù)據結構概述 1.1.1 引言 1.1.2 數(shù)據結構有關概念及術語 1.1.3 數(shù)據類型和抽象數(shù)據類型 1.2 算法描述與實現(xiàn) 1.2.1 算法的概念與特性 1.2.2 算法的設計與實現(xiàn) 1.3 算法的評價與分析 1.3.1 評價標準 1.3.2 算法的時間復雜性 1.3.3 算法的空間復雜性 本章小結 習題第2章 線性表 2.1線性表的基本概念 2.1.1 定義 2.1.2 線性表的存儲結構 2.1.3 線性表的運算 2.2 順序表 2.2.1 順序存儲結構 2.2.2 順序表的運算 2.2.3 遍歷 2.2.4 順序存儲的物理位置 2.2.5 線性表的順序存儲的主要特點 2.3 鏈表 2.3.1 單鏈表定義與創(chuàng)建 2.3.2 單鏈表的基本運算算法 2.3.3 循環(huán)單鏈表 2.3.4 雙向鏈表 2.4 順序表和鏈表的比較 2.5 多項式相加問題 2.5.1 多項式的順序表表示 2.5.2 多項式相加的鏈表實現(xiàn) 本章小結 習題二第3章 棧和隊列 3.1 ?! ?.1.1 棧的定義及其運算 3.1.2 棧的順序存儲結構 3.1.3 棧的鏈表存儲結構 3.2 棧的應用 3.2.1 數(shù)制轉換 3.2.2 算術表達式轉換 3.2.3 子程序調用 3.2.4 中斷處理 3.2.5 遞歸調用 3.2.6 序列進出棧的排列問題 3.3 隊列 3.3.1 隊列的定義及運算 3.3.2 隊列的順序存儲結構 3.3.3 隊列的鏈式存儲結構 3.3.4 隊列的應用 本章小結 習題三第4章 串 4.1 串的基本概念 4.2 串的存儲結構 4.2.1 串的順序存儲 4.2.2 串的鏈表存儲 4.3 串的運算 4.3.1 串的基本運算 4.3.2 串的簡單模式匹配 4.3.3 Knuth—Morris—Pratt算法 本章小結 習題四第5章 數(shù)組和廣義表第6章 樹第7章 圖第8章 查找第9章 排序第10章 文件
圖書封面
評論、評分、閱讀與下載
院校計算機科學與技術專業(yè)規(guī)劃教材 PDF格式下載