☆☆☆☆☆




點擊這裡下載

類似圖書 點擊查看全場最低價

---

內容介紹

內容介紹

數據結構是高等學校計算機及其相關專業的核心課程，是計算機程序設計的基礎。本書按照“像外行一樣思考，像專傢一樣實踐”的解決問題的思維方法，列舉大量實際或工程案例，從具體問題中引齣抽象概念，運用類比、圖形化描述等各種方式，對經典數據結構內容做深入淺齣的介紹。在介紹數據結構和算法的基本概念和算法分析方法的基礎之上，從軟件開發的角度，通過應用背景或知識背景介紹、數據分析、函數設計、算法設計、測試調試等環節，分彆對順序錶、鏈錶、棧、隊列、串、數組、樹、圖等基本類型的數據結構進行瞭分析和討論；介紹數據的典型操作方法，如數據排序方法和查找方法；介紹常見的如遞歸法、分治法、動態規劃、貪心法等經典算法。

 

目   錄

第1章  緒論    1

1.1  從編程說起    1

1.2  程序要處理的數據    5

1.3  數據結構的引入    11

1.4  數據結構的基本概念    13

1.4.1  數據結構基本術語    13

1.4.2  數據結構的三個要素    13

1.5  如何設計算法    16

1.5.1  算法的定義及錶示方法    16

1.5.2  算法設計與函數設計的關係    17

1.5.3  軟件設計描述方法    18

1.5.4  算法設計的一般步驟    19

1.6  如何評價算法的優劣    21

1.6.1  算法的設計要求    21

1.6.2  算法效率的度量方法    22

1.7  算法性能的事前分析方法    23

1.7.1  問題的規模與算法的策略    23

1.7.2  算法效率的上限與下限    25

1.7.3  漸進的上限——算法的時間

      復雜度    28

1.7.4  算法時間復雜度的綜閤討論    29

1.7.5  算法的空間效率分析方法    33

1.8  算法性能綜閤考量    37

1.9  本章小結    38

習題    38

第2章  結點邏輯關係為綫性的結構——綫性錶    41

2.1  從邏輯結構角度看綫性錶    41

2.1.1  實際問題中的綫性關係    41

2.1.2  綫性錶的邏輯結構    42

2.2  綫性錶的存儲結構方法之一——順序錶    43

2.2.1  順序錶的存儲結構設計    43

2.2.2  順序錶的運算    46

2.2.3  順序存儲結構的討論    53

2.3  綫性錶的存儲結構方法之二——鏈錶    53

2.3.1  單鏈錶的存儲    56

2.3.2  單鏈錶的運算    60

2.3.3  單鏈錶的討論    78

2.3.4  循環鏈錶    78

2.3.5  雙嚮鏈錶    81

2.3.6  鏈錶小結    86

2.4  綫性錶的應用舉例    87

2.4.1  逆序輸齣單鏈錶結點值    87

2.4.2  一元多項式的相加    88

2.5  順序錶和鏈錶的比較    95

2.6  本章小結    96

習題    97

第3章  運算受限的綫性錶——棧和隊列    100

3.1  棧——按照先入後齣的方式管理的綫性錶    100

3.1.1  棧處理模式的引入    100

3.1.2  棧的邏輯結構    104

3.1.3  棧的存儲結構設計    106

3.1.4  棧的操作    107

3.1.5  各種棧結構的比較    123

3.1.6  棧的應用舉例    123

3.2  隊列——按照先入先齣方式管理的綫性錶    132

3.2.1  隊列處理模式的引入    133

3.2.2  隊列的邏輯結構    136

3.2.3  隊列的順序存儲結構    137

3.2.4  順序隊列的基本操作    148

3.2.5  隊列的鏈式存儲結構    152

3.2.6  鏈隊列的基本操作    153

3.2.7  各種隊列結構的比較    160

3.2.8  隊列的應用舉例    161

3.3  本章小結    171

習題    172

第4章  內容特殊的綫性錶——多維數組與字符串    175

4.1  多維數組    175

4.1.1  數組的概念    175

4.1.2  數組的存儲結構    177

4.2  矩陣的壓縮存儲    181

4.2.1  對稱矩陣的壓縮存儲    182

4.2.2  三角矩陣的壓縮存儲    183

4.2.3  對角矩陣的壓縮存儲    183

4.2.4  稀疏矩陣的壓縮存儲    185

4.3  字符串    189

4.3.1  字符串的定義    189

4.3.2  字符串的存儲結構    190

4.3.3  字符串的查找——模式匹配    195

4.4  本章小結    211

習題    213

第5章  結點邏輯關係分層次的非綫性結構——樹    216

5.1  實際問題中的樹    216

5.2  樹的邏輯結構    219

5.2.1  樹的定義和基本術語    219

5.2.2  樹的操作定義    222

5.3  樹的存儲結構    222

5.3.1  樹的連續存儲方式    223

5.3.2  樹的鏈式存儲方式    224

5.4  二叉樹的邏輯結構    226

5.4.1  二叉樹的概念    229

5.4.2  二叉樹的基本性質    230

5.4.3  二叉樹的操作定義    231

5.5  二叉樹的存儲結構及實現    231

5.5.1  二叉樹的順序結構    232

5.5.2  二叉樹的鏈式存儲

      結構——二叉鏈錶    235

5.5.3  建立動態二叉鏈錶    236

5.6  二叉樹結點的查找 問題——樹的遍曆    240

5.6.1  樹的廣度優先遍曆    242

5.6.2  樹的深度優先遍曆    244

5.6.3  樹的遍曆的應用    255

5.7  樹的應用    259

5.7.1  錶達式樹    259

5.7.2  綫索二叉樹    260

5.7.3  哈夫曼樹及哈夫曼編碼    265

5.8  廣義錶    278

5.8.1  廣義錶的定義    279

5.8.2  廣義錶的存儲    281

5.8.3  廣義錶的基本運算    287

5.9  本章小結    293

習題    295

第6章  結點邏輯關係任意的非綫性結構——圖    299

6.1  實際問題中的圖及抽象    299

6.2  圖的邏輯結構    304

6.2.1  圖的定義和基本術語    304

6.2.2  圖的操作定義    307

6.3  圖的存儲結構及實現    308

6.3.1  圖的數組錶示法1—— 鄰接矩陣    308

6.3.2  圖的數組錶示法2—— 邊集數組    310

6.3.3  圖的鏈錶錶示法1——鄰接錶    311

6.3.4  圖的鏈錶錶示法2—— 十字鏈錶    316

6.3.5  圖的鏈錶錶示法3——鄰接多重錶    317

6.3.6  圖各種存儲結構的歸結比較    319

6.4  圖的基本操作    320

6.4.1  鄰接矩陣的操作    320

6.4.2  鄰接錶的操作    322

6.5  圖的頂點查找問題——圖的遍曆    328

6.5.1  圖的廣度優先遍曆BFS    329

6.5.2  圖的深度優先遍曆DFS    334

6.5.3  圖的遍曆小結    340

6.6  圖的經典應用——圖中的樹問題    340

6.6.1  生成樹    342

6.6.2  最小生成樹MST    343

6.6.3  求最小生成樹算法1——Prim 算法    344

6.6.4  求最小生成樹算法2——Kruskal算法    349

6.6.5  生成樹算法小結    356

6.7  圖的經典應用——最短路徑問題    357

6.7.1  最短路徑問題的引入    357

6.7.2  單源最短路徑算法——Dijkstra算法    359

6.7.3  各頂點對間最短路徑算法——Floyd算法    364

6.7.4  最短路徑問題小結    369

6.8  圖的經典應用——活動頂點與活動邊的問題    370

6.8.1  圖的活動頂點排序問題的引入    370

6.8.2  AOV網與拓撲排序——活動頂點排序問題    373

6.8.3  AOE網與關鍵路徑——活動邊最長問題    378

6.8.4  活動頂點與活動邊問題小結    390

6.9  本章小結    390

習題    391

第7章  數據的處理方法——排序技術    397

7.1  概述    397

7.1.1  排序的基本概念    397

7.1.2  排序算法的分類    399

7.2  插入排序    399

7.2.1  直接插入排序    399

7.2.2  希爾排序    402

7.3  交換排序    404

7.3.1  冒泡排序    404

7.3.2  快速排序    406

7.4  選擇排序    409

7.4.1  簡單選擇排序    410

7.4.2  堆排序    411

7.5  歸並排序    415

7.6  分配排序    418

7.6.1  桶排序    418

7.6.2  基數排序    421

7.7  各種排序算法的比較    424

7.8  本章小結    427

習題    428

第8章  數據的處理——索引與查找技術    431

8.1  索引的基本概念    433

8.1.1  索引的定義    433

8.1.2  索引的邏輯特徵    434

8.1.3  索引的主要操作    435

8.2  綫性索引技術    435

8.2.1  稠密索引    435

8.2.2  分塊索引    436

8.2.3  多重錶    437

8.2.4  倒排錶    439

8.3  樹形索引    441

8.3.1  二叉排序樹    441

8.3.2  B樹    448

8.4  查找概述    452

8.4.1  查找的基本概念    452

8.4.2  查找算法的性能    453

8.5  綫性錶的查找技術    453

8.5.1  順序查找    453

8.5.2  有序錶查找    454

8.5.3  索引查找    459

8.6  樹錶的查找技術    461

8.6.1  二叉排序樹    461

8.6.2  B樹    462

8.6.3  在非數值有序錶上的查找——字典樹    462

8.7  散列錶的查找技術    464

8.7.1  散列概述    465

8.7.2  散列函數的設計    467

8.7.3  處理衝突的方法    469

8.7.4  散列查找的性能分析    473

8.8  本章小結    474

習題    476

第9章  經典算法    479

9.1  遞歸算法    479

9.1.1  遞歸的概念及要素    479

9.1.2  遞歸的應用場景    481

9.1.3  遞歸的計算機實現    482

9.1.4  遞歸方法特點分析    483

9.1.5  遞歸算法實例    485

9.1.6  遞歸小結    487

9.2  分治算法    487

9.2.1  分治是什麼    487

9.2.2  分治法的適用條件    488

9.2.3  分治問題的類型    488

9.2.4  分治法小結    490

9.3  動態規劃    491

9.3.1  什麼是動態規劃    491

9.3.2  動態規劃的解題方法    493

9.3.3  動態規劃解題實例    495

9.3.4  動態規劃小結    500

9.4  貪心算法    501

9.4.1  貪心算法是什麼    501

9.

 

 

作者介紹

周幸妮，西安電子科技大學副教授，長期從事“數據結構”、“C程序設計語言”等課程的教學工作，著有《C程序設計》等教材。

 

 

前    言

從新視角來看待舊問題，則需要創造性的思維——愛因斯坦

數據結構的教與學經曆

六七年前上數據結構課時，駕輕就熟地依然按照一貫的講法上課。上瞭幾次課後，收到班上一位同學的E-mail，信中說：“我自己是特彆熱愛寫程序的。一方麵我很熟悉電腦，軟硬件都有涉獵，所以學起來就不缺基礎的相關知識（像內存、寄存器、電子電路等等這些都很熟悉）；另一方麵我好像很能適應，也很喜歡這種思維方式……但好像班上不少的同學對數據結構的學習理解和接受起來還是比較睏難的……”

教授數據結構的課程也有十餘年瞭，一直以來，學生們總是認為數據結構不是一門容易學的課程，“在眾多的專業課中，數據結構被很多學生認為是一門很難學習的課程。”[1]雖然我在學校讀書時沒有學過數據結構的課程，隻是因為後來要教書，纔自學的數據結構。在自學的過程中，也並沒有覺著內容怎麼難啊，這是怎麼迴事呢？

仔細迴想一下自己學習與工作的經曆過程，或許就是來信的這位同學說的，是因為在學習數據結構書本知識之前，已經有瞭較強的編程的技能、一些數據結構實際應用的先驗知識吧。比如，在研究所工作時首次參加的軟件開發項目中，就有多進程、鏈錶、隊列、散列等的實際應用，雖然在學校並沒有學過這些概念，而是先接觸到實際項目中要處理的問題，再看到其他程序員的具體算法處理和程序實現方法，從實際的問題切入，就比較容易理解相應的數據組織形式和對應的算法，等到後來再接觸到書本的理論知識，就有一種一通百通，豁然開朗的感覺。還有一個原因是在軟件開發過程中逐漸熟悉並掌握瞭程序調試方法，對例程通過跟蹤的方法，很容易弄清執行的路徑和結果，對算法的設計和實現的理解也起到瞭事半功倍的效果。

迴頭來看學生們學習的教科書，概念的介紹是傳統意義上的敘述方式，抽象度很高，但從實際到抽象、從抽象到實際的過程介紹不足，即感性認識不足，抽象就難以理解接受。“現在有一個不好的傾嚮，就是教材或課堂過於重視抽象化的知識，忽視應用背景。數據結構的教材是這一傾嚮的代錶。這對入門階段的學生來講是不適宜的，因為學生難以走進所涉及的抽象世界，最終錶現為不知道在講什麼。”[2]

再看我的學生，既沒有實際軟件開發的經驗也沒有熟練的編程調試基礎，對數據結構結構沒有感性認識，先接觸的是那些抽象的概念，感到理解和接受睏難也就可以理解瞭。鄒恒明在《數據結構：炫動的0、1之弦》一書中指齣，對於很多人來說，數據結構的概念並不難，真正的難點是：

（1）如何實現從數據結構概念到程序實現的跨越（即如何實現一個數據結構）；

（2）如何實現從實際應用到數據結構抽象的跨越（即如何利用數據結構解決實際問題）。

對於我來說，僅僅在學校學瞭一點點程序設計語言（記得所有上機時間加起來不超過20小時），沒有任何數據結構的知識，剛齣校門就參與瞭曆時三年多後來獲得國傢科技進步三等奬的大型軟件開發工作，以及後續多個電信用戶單位的實際軟件安裝、應用調試和維護工作，親曆瞭實現瞭上述兩個“跨越”的最實際生動的案例。雖然項目的開發過程非常艱苦，有在用戶單位調試現場連續大半年的天天加班到深夜、第二天依然要正點到機房的超負荷工作，有通宵的跟蹤調試，有24小時在綫係統內存泄漏的巨大壓力，有上綫後雙機備份係統同時崩潰爭分奪秒找bug的驚心動魄，等等。應該說自己是很幸運的，雖然在學校僅僅學習瞭一點點編程的概念，但在工作中根據需要自學和嚮同事學習瞭很多新知識、經驗和技巧，這樣的實踐磨練，對後來的程序設計類課程的理解和教授，是非常有益的。

學習數據結構睏難的癥結所在

迴想與總結起來，之所以要有上述兩個鴻溝要“跨越”，也是由於學校的傳統教科書教法和實際的應用要求脫節造成的。

弗裏德裏希?威廉?尼采曾寫道：“人們無法理解他沒有經曆過的事情。”[3]換句話來說，我們隻接受與過去早已理解的事物相關的信息。這是一種比較學習的過程，在這個過程中，大腦要尋找每條信息之間的聯係，藉助以往經驗來理解新事物[4]。

“歐拉認為，如果不能把解決數學問題背後的思維過程教給學生的話，數學教學就是沒有意義的。現代計算機實質上的發明者萊布尼茲也說過：在我看來，沒有什麼能比探索發明的源頭還要重要，它遠比發明本身更重要。從小到大，我們看過的數學書幾乎無一不是歐幾裏德式的：從定義到定理，再到推論。這樣的書完全而徹底地扭麯瞭數學發現的真實過程。目前幾乎所有的算法書的講解方式也都是歐幾裏德式的，每一個推導步驟都是精準製導直接麵嚮數據結構目標的，實際上，這完全把人類大腦創造發明的步驟給反過來瞭。對讀者來說，這就等於直接告訴你答案和做法瞭，然後讓你去驗證這個答案和做法是可行或成立的，而關於答案和做法到底是怎麼來的，從問題到答案之間經曆瞭怎樣的思維過程，卻鮮有書能夠很好地闡釋。對於這類知識講述（歐幾裏德方式）方式的批判，西方（尤其是在數學領域）早就有瞭。”[5]

傳統數據結構教科 數據結構與算法分析新視角 下載 mobi epub pdf txt 電子書

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

類似圖書 點擊查看全場最低價

查看全網最低價