《數據結構（C語言描述）（修訂版）》是2011年8月電子工業出版社出版的圖書，作者是王曉東。
基本介紹
- 書名：數據結構（C語言描述）（修訂版）
- 作者：王曉東
- ISBN：9787121142246
- 頁數：268頁
- 定價：32元
- 出版社：電子工業出版社
- 出版時間：2011年8月
- 開本：16開
內容簡介,圖書目錄,
內容簡介
本書是國家精品課程教材，以教育部計算機科學與技術教學指導委員會發布的“高等學校計算機科學與技術本科專業規範”為依據，以基本數據結構為知識單元而編寫。全書共分12章，包括引論、表、棧、佇列、排序與選擇、樹、圖、集合、符號表、字典、優先佇列、並查集等。
全書採用C語言作為描述語言，內容豐富，敘述簡明，理論與實踐並重，每章設有套用舉例和算法實驗題，並為任課教師免費提供電子課件和課程實驗用數據。
讀者對象：可作為高等學校計算機、電子信息、信息與計算科學、信息管理與信息系統等專業的數據結構課程教材，也適合工程技術人員和自學者學習參考。
圖書目錄
目 錄
第1章 引論 （1）
1.1 算法及其複雜性的概念 （1）
1.1.1 算法與程式 （1）
1.1.2 算法複雜性的概念 （1）
1.1.3 算法複雜性的漸近性態 （3）
1.2 算法的表達與數據表示 （5）
1.2.1 問題求解 （5）
1.2.2 表達算法的抽象機制 （5）
1.3 抽象數據類型 （8）
1.3.1 抽象數據類型的基本概念 （8）
1.3.2 使用抽象數據類型的好處 （9）
1.4 數據結構、數據類型和抽象數據類型 （10）
1.5 用C語言描述數據結構與算法 （11）
1.5.1 變數和指針 （11）
1.5.2 函式與參數傳遞 （12）
1.5.3 結構 （13）
1.5.4 動態存儲分配 （14）
1.6 遞歸 （15）
1.6.1 遞歸的基本概念 （15）
1.6.2 間接遞歸 （17）
本章小結 （17）
習題1 （18）
算法實驗1 （19）
算法實驗題1.1 哥德巴赫猜想問題 （19）
算法實驗題1.2 連續整數和問題 （19）
第2章 表 （20）
2.1 表的基本概念 （20）
2.2 用數組實現表 （21）
2.3 用指針實現表 （25）
2.4 用間接定址方法實現表 （29）
2.5 用游標實現表 （32）
2.6 循環鍊表 （38）
2.7 雙鍊表 （41）
2.8 表的搜尋游標 （45）
2.8.1 用數組實現表的搜尋游標 （45）
2.8.2 單循環鍊表的搜尋游標 （46）
2.9 套用舉例——Josephus排列問題 （48）
本章小結 （49）
習題2 （49）
算法實驗2 （51）
算法實驗題2.1 向量分類問題 （51）
算法實驗題2.2 條形圖輪廓問題 （51）
第3章 棧 （53）
3.1 棧的基本概念 （53）
3.2 用數組實現棧 （54）
3.3 用指針實現棧 （56）
3.4 套用舉例——等價類劃分問題 （59）
本章小結 （61）
習題3 （61）
算法實驗3 （63）
算法實驗題3.1 車皮編序問題 （63）
算法實驗題3.2 單柱Hanoi塔問題 （63）
算法實驗題3.3 多棧模擬問題 （64）
算法實驗題3.4 親兄弟問題 （64）
第4章 佇列 （66）
4.1 佇列的基本概念 （66）
4.2 用指針實現佇列 （67）
4.3 用循環數組實現佇列 （69）
4.4 套用舉例——電路布線問題 （73）
本章小結 （77）
習題4 （77）
算法實驗4 （78）
算法實驗題4.1 組佇列問題 （78）
算法實驗題4.2 雙棧佇列問題 （79）
算法實驗題4.3 猴子分桃問題 （79）
算法實驗題4.4 逆序表問題 （79）
第5章 排序與選擇 （81）
5.1 簡單排序算法 （81）
5.1.1 冒泡排序 （82）
5.1.2 插入排序 （82）
5.1.3 選擇排序 （83）
5.1.4 簡單排序算法的計算複雜性 （83）
5.2 快速排序算法 （84）
5.2.1 算法基本思想及實現 （84）
5.2.2 算法的性能 （86）
5.2.3 隨機快速排序算法 （86）
5.2.4 非遞歸快速排序算法 （87）
5.2.5 三數取中劃分算法 （88）
5.2.6 三劃分快速排序算法 （89）
5.3 合併排序算法 （90）
5.3.1 算法基本思想及實現 （90）
5.3.2 對基本算法的改進 （91）
5.3.3 自底向上的合併排序算法 （92）
5.3.4 自然合併排序 （92）
5.3.5 鍊表結構的合併排序算法 （93）
5.4 線性時間排序算法 （94）
5.4.1 計數排序 （94）
5.4.2 桶排序 （95）
5.5 中位數與第k小元素 （96）
5.5.1 平均情況下的線性時間選擇算法 （97）
5.5.2 最壞情況下的線性時間選擇算法 （98）
5.6 套用舉例——帶權中位數問題 （100）
本章小結 （101）
習題5 （102）
算法實驗5 （103）
算法實驗題5.1 交換排序問題 （103）
算法實驗題5.2 DNA排序問題 （103）
算法實驗題5.3 輸油管道問題 （104）
算法實驗題5.4 最優服務次序問題 （104）
第6章 樹 （105）
6.1 樹的定義 （105）
6.2 樹的遍歷 （107）
6.3 樹的表示法 （109）
6.3.1 父結點數組表示法 （109）
6.3.2 兒子鍊表表示法 （110）
6.3.3 左兒子右兄弟表示法 （110）
6.4 二叉樹的基本概念 （111）
6.5 二叉樹的運算 （113）
6.6 二叉樹的實現 （114）
6.6.1 二叉樹的順序存儲結構 （114）
6.6.2 二叉樹的結點度表示法 （115）
6.6.3 用指針實現二叉樹 （115）
6.7 線索二叉樹 （120）
6.8 套用舉例——信號增強裝置布局問題 （122）
本章小結 （126）
習題6 （126）
算法實驗6 （128）
算法實驗題6.1 層序列表問題 （128）
算法實驗題6.2 最近公共祖先問題 （128）
算法實驗題6.3 子樹問題 （129）
算法實驗題6.4 同構二叉樹問題 （129）
算法實驗題6.5 後序中序遍歷問題 （130）
第7章 圖 （131）
7.1 圖的基本概念 （131）
7.2 抽象數據類型ADT圖 （134）
7.3 圖的表示法 （134）
7.3.1 鄰接矩陣表示法 （135）
7.3.2 鄰接表表示法 （135）
7.3.3 緊縮鄰接表 （135）
7.4 用鄰接矩陣實現圖 （136）
7.4.1 用鄰接矩陣實現賦權有向圖 （136）
7.4.2 用鄰接矩陣實現賦權無向圖 （139）
7.4.3 用鄰接矩陣實現有向圖 （140）
7.4.4 用鄰接矩陣實現無向圖 （140）
7.5 用鄰接表實現圖 （141）
7.5.1 用鄰接表實現有向圖 （141）
7.5.2 用鄰接表實現無向圖 （144）
7.5.3 用鄰接表實現賦權有向圖 （145）
7.5.4 用鄰接表實現賦權無向圖 （148）
7.6 圖的遍歷 （149）
7.6.1 廣度優先搜尋 （149）
7.6.2 深度優先搜尋 （151）
7.7 最短路徑 （152）
7.7.1 單源最短路徑 （153）
7.7.2 Bellman-Ford最短路徑算法 （156）
7.7.3 所有頂點對之間的最短路徑 （158）
7.8 無圈有向圖DAG （160）
7.8.1 拓撲排序 （160）
7.8.2 DAG的最短路徑 （162）
7.8.3 DAG的最長路徑 （163）
7.8.4 DAG所有頂點對之間的最短路徑 （163）
7.9 最小支撐樹 （164）
7.9.1 最小支撐樹性質 （164）
7.9.2 Prim算法 （164）
7.9.3 Kruskal算法 （166）
7.10 圖匹配 （169）
7.11 套用舉例——差分約束系統 （170）
本章小結 （172）
習題7 （172）
算法實驗7 （174）
算法實驗題7.1 圖的二著色問題 （174）
算法實驗題7.2 賦權有向圖中心問題 （174）
算法實驗題7.3 最長簡單路徑問題 （175）
算法實驗題7.4 計算機網路問題 （175）
算法實驗題7.5 差分約束問題 （176）
算法實驗題7.6 有截止時間的工作排序問題 （176）
第8章 集合 （178）
8.1 以集合為基礎的抽象數據類型 （178）
8.1.1 集合的定義和記號 （178）
8.1.2 定義在集合上的基本運算 （179）
8.2 用位向量實現集合 （179）
8.3 用鍊表實現集合 （183）
8.4 套用舉例——Eratosthenes篩法 （186）
本章小結 （187）
習題8 （187）
算法實驗8 （188）
算法實驗題8.1 半數集問題 （188）
第9章 符號表 （190）
9.1 實現符號表的簡單方法 （190）
9.2 用散列表實現符號表 （191）
9.2.1 開散列 （192）
9.2.2 閉散列 （194）
9.2.3 散列函式及其效率 （198）
9.2.4 閉散列的重新散列技術 （199）
9.3 套用舉例——字元串頻率統計問題 （199）
本章小結 （201）
習題9 （201）
算法實驗9 （202）
算法實驗題9.1 偽隨機排列問題 （202）
算法實驗題9.2 字元串散列問題 （202）
算法實驗題9.3 英文文本分析問題 （202）
算法實驗題9.4 最長模式串問題 （203）
第10章 字典 （204）
10.1 字典的定義 （204）
10.2 用數組實現字典 （204）
10.3 用二叉搜尋樹實現字典 （205）
10.4 AVL樹 （213）
10.4.1 AVL樹的定義和性質 （213）
10.4.2 旋轉變換 （214）
10.4.3 AVL樹的插入運算 （217）
10.4.4 AVL樹的刪除運算 （220）
10.5 套用舉例——條形圖統計問題 （223）
本章小結 （225）
習題10 （225）
算法實驗10 （226）
算法實驗題10.1 裝箱問題 （226）
算法實驗題10.2 電路板連線問題 （227）
算法實驗題10.3 辭典問題 （227）
第11章 優先佇列 （229）
11.1 優先佇列的定義 （229）
11.2 用字典實現優先佇列 （230）
11.3 優先權樹和堆 （230）
11.4 用數組實現堆 （232）
11.5 可並優先佇列 （235）
11.5.1 左偏樹的定義 （235）
11.5.2 用左偏樹實現可並優先佇列 （236）
11.6 套用舉例——哈夫曼編碼 （239）
本章小結 （243）
習題11 （243）
算法實驗11 （244）
算法實驗題11.1 多機調度問題 （244）
算法實驗題11.2 整數字典問題 （244）
算法實驗題11.3 最小權語言問題 （245）
算法實驗題11.4 二叉搜尋堆問題 （245）
第12章 並查集 （247）
12.1 並查集的定義及其簡單實現 （247）
12.2 用父結點數組實現並查集 （248）
12.3 套用舉例——離線最小值問題 （251）
本章小結 （253）
習題12 （253）
算法實驗12 （254）
算法實驗題12.1 二進制方程問題 （254）
算法實驗題12.2 網路連通問題 （255）
算法實驗題12.3 朋友問題 （255）
算法實驗題12.4 無向圖的連通分支問題 （255）
參考文獻 （257）
