了得網計算機/網絡_數據結構編程實驗：大學程序設計課程與競賽訓練教材第3版

內容簡介

本書針對大學程序設計競賽和課程教學，基於數據結構的知識體繫結構和循序漸進的原則組織內容，包括基本編程能力訓練、線性數據結構的編程、樹的編程、圖的編程。在每一章中，先介紹了相關的數據結構知識後，然後給出相應的範例；在每章的結尾給出相關題庫。

前言
篇訓練基本編程能力的實驗
第1章簡單計算的編程實驗 2
1.1改進程序書寫風格 2
1.2正確處理多個測試用例 4
1.3在實數和整數之間轉換 10
1.4二分法、實數精度 13
1.5相關題庫 20
第2章簡單模擬的編程實驗 30
2.1直敘式模擬 30
2.2篩選法模擬 33
2.3構造法模擬 35
2.4相關題庫 37
第3章遞歸與回溯法的編程實驗 44前言
篇訓練基本編程能力的實驗
第1章簡單計算的編程實驗 2
1.1改進程序書寫風格 2
1.2正確處理多個測試用例 4
1.3在實數和整數之間轉換 10
1.4二分法、實數精度 13
1.5相關題庫 20
第2章簡單模擬的編程實驗 30
2.1直敘式模擬 30
2.2篩選法模擬 33
2.3構造法模擬 35
2.4相關題庫 37
第3章遞歸與回溯法的編程實驗 44
3.1計算遞歸函數 45
3.2求解遞歸數據 47
3.3用遞歸算法求解問題 49
3.4回溯法 55
3.5相關題庫 63
本篇小結 69
第二篇線性表的編程實驗
第4章應用直接存取類線性表編程 72
4.1數組應用的四個典型範例 72
4.1.1日期計算 72
4.1.2高精度運算 78
4.1.3多項式的表示與處理 86
4.1.4數值矩陣運算 91
4.2字符串處理 96
4.2.1使用字符串作為存儲結構 96
4.2.2字符串的模式匹配 97
4.2.3使用Manacher算法求長回文子串 103
4.3在數組中快速查素 107
4.4通過數組分塊技術優化算法 109
4.5相關題庫 113
第5章應用順序存取類線性表編程 149
5.1順序表的應用 149
5.2棧應用 158
5.3隊列應用 166
5.3.1順序隊列 166
5.3.2優先隊列 176
5.3.3雙端隊列 180
5.4相關題庫 183
第6章應用廣義索引類線性表編程 192
6.1使用詞典解題 192
6.2應用散列技術處理字符串 197
6.3使用散列表與散列技術解題 202
6.4相關題庫 210
第7章線性表排序的編程實驗 217
7.1利用STL中自帶的排序功能編程 217
7.2應用排序算法編程 222
7.3相關題庫 226
本篇小結 247
第三篇樹的編程實驗
第8章采用樹結構的非線性表編程 250
8.1用樹的遍歷求解層次性問題 250
8.2用樹結構支持並查集 258
8.3用樹狀數組統計子樹權和 266
8.4用四叉樹求解二維空間問題 272
8.5用Trie樹查詢字符串 280
8.6用AC自動機進行多模式匹配 284
8.7相關題庫 292
第9章應用二叉樹的基本概念編程 324
9.1普通有序樹轉化為二叉樹 324
9.2應用典型二叉樹 327
9.3計算二叉樹路徑 333
9.4通過遍歷確定二叉樹結構 339
9.5相關題庫 344
第10章應用經典二叉樹編程 348
10.1二叉搜索樹 348
10.2二叉堆 355
10.3樹堆 363
10.3.1樹堆的概念和操作 363
10.3.2非旋轉樹堆 370
10.4赫夫曼樹 379
10.4.1赫夫曼樹 379
10.4.2多叉赫夫曼樹 381
10.5AVL樹 384
10.6伸展樹 389
10.7相關題庫 397
本篇小結 411
第四篇圖的編程實驗
第11章應用圖的遍歷算法編程 414
11.1BFS算法 414
11.2DFS算法 425
11.3拓撲排序 433
11.3.1刪邊法 433
11.3.2采用DFS計算拓撲排序 436
11.3.3反向拓撲排序 440
11.4計算圖的連通性 443
11.5Tarjan算法 450
11.6相關題庫 468
第12 章應用小生成樹算法編程 489
12.1Kruskal算法 489
12.2Prim算法 491
12.3生成樹 496
12.4相關題庫 500
第13章應用路算法編程 507
13.1Warshall算法和Floyd-Warshall算法 507
13.2Dijkstra算法 514
13.3Bellman-Ford算法 519
13.4SPFA算法 523
13.5相關題庫 527
第14章二分圖、網絡流算法編程 535
14.1二分圖匹配 535
14.1.1匈牙利算法 535
14.1.2Hall婚姻定理 541
14.1.3KM算法 544
14.2計算網絡流 551
14.2.1網絡流 551
14.2.2小費用流 560
14.3相關題庫 570
第15 章應用狀態空間搜索編程 583
15.1構建狀態空間樹 583
15.2優化狀態空間搜索 590
15.2.1剪枝 591
15.2.2定界 595
15.2.3A*算法? 603
15.2.4IDA*算法 612
15.3在博弈問題中使用遊戲樹 623
15.4相關題庫 638
本篇小結 658

前言

《數據結構編程實驗》是“大學程序設計課程與競賽訓練教材”繫列的部著作。在出版本書第1版的時候，我們的初心是基於程序設計競賽的試題，以全面、繫統地磨煉和提高學生通過編程解決問題的能力為目標，出版既能用於大學程序設計類課程的教學和實驗，又能用於程序設計競賽選手訓練的繫列著作。
經過多年的努力，“大學程序設計課程與競賽訓練教材”繫列不斷完善。這套教材基於以下指導思想：
1）程序設計競賽是“通過編程解決問題”的競賽。國際大學生程序設計競賽（International Collegiate Programming Contest，ICPC）和中學生國際信息學奧賽（International Olympiad in Informatics，IOI）在20世紀80年代中後期走向成熟之後， 30多年來積累了海量的試題。這些來自全球各地、凝聚了無數命題者心血和智慧的試題，不僅可以用於程序設計競賽選手的訓練，而且可以用於程序設計類課程的教學和實驗，能夠繫統、全面地提高學生通過編程解決問題的能力。《數據結構編程實驗》是“大學程序設計課程與競賽訓練教材”繫列的部著作。在出版本書第1版的時候，我們的初心是基於程序設計競賽的試題，以全面、繫統地磨煉和提高學生通過編程解決問題的能力為目標，出版既能用於大學程序設計類課程的教學和實驗，又能用於程序設計競賽選手訓練的繫列著作。
經過多年的努力，“大學程序設計課程與競賽訓練教材”繫列不斷完善。這套教材基於以下指導思想：
1）程序設計競賽是“通過編程解決問題”的競賽。國際大學生程序設計競賽（International Collegiate Programming Contest，ICPC）和中學生國際信息學奧賽（International Olympiad in Informatics，IOI）在20世紀80年代中後期走向成熟之後， 30多年來積累了海量的試題。這些來自全球各地、凝聚了無數命題者心血和智慧的試題，不僅可以用於程序設計競賽選手的訓練，而且可以用於程序設計類課程的教學和實驗，能夠繫統、全面地提高學生通過編程解決問題的能力。
2）我們認為，評價一個人的專業能力要看兩個方面：①知識體繫，他能用哪些知識去解決問題，或者說，哪些是他真正掌握並能應用的知識，而不僅僅是他學過什麼知識；②思維方式，當他面對問題，特別是不太標準化的問題的時候，解決問題的策略是什麼。對於程序設計競賽選手，要求的知識體繫可以概括為1984年圖靈獎得主Nicklaus Wirth提出的著名公式“算法數據結構=程序”，這也是計算機學科知識體繫的核心部分。因此，本繫列的前兩部著作分別是《數據結構編程實驗》和《算法設計編程實驗》。對於需要采用某些策略進行求解的程序設計試題，比如，不采用常用的數據結構或者解題的算法要進行優化等，我們對相關試題進行分析、整理，編寫了本繫列的第三部著作《程序設計解題策略》。
3）從本質上說，程序設計是技術。所以，首先牢記學習編程要不斷“實踐，實踐，再實踐”。本繫列選用大量程序設計競賽的試題，以案例教學的方式進行教學實驗並安排學生進行解題訓練。其次，“以繫統的方法實踐”。本繫列基於高校通常采用的教學大綱，以繫統、全面提高學生通過編程解決問題的能力為目標，以程序設計競賽的試題以及詳細的解析、帶注解的程序作為實驗，在每一章的結束部分給出相關題庫以及解題提示，並對大部分試題給出官方的測試數據。
基於上述指導思想，我們在中國大陸出版了本繫列的簡體中文版，在中國臺灣地區出版了繁體中文版，在美國由CRC Press出版了英文版。
對於本書，我們在機械工業出版社出版了第1版和第2版，在中國臺灣地區出版了繁體版的第1版和第2版。2016年，我們在CRC Press出版了本書的英文版Data Structure Practice: for Collegiate Programming Contest and Education。在本書的中、英文版廣泛使用的基礎上，我們對第2版進行了脫胎換骨的改進，編寫了本書的第3版。
本書基於數據結構課程的知識體繫，采用循序漸進的原則編寫而成。全書分四篇（共15章），即訓練基本編程能力的實驗、線性表的編程實驗、樹的編程實驗和圖的編程實驗。在每一章中，首先介紹相關的數據結構知識，然後給出相應的實驗範例，並在章末給出相關題庫。
篇“訓練基本編程能力的實驗”適合剛學會程序設計語言的讀者。這部分包括3章：第1章“簡單計算的編程實驗”、第2章“簡單模擬的編程實驗”和第3章“遞歸與回溯法的編程實驗”。與本書第2版相比，這一篇對正確處理多個測試用例、在實數和整數之間轉換、二分法、實數精度、遞歸、回溯的實驗做了較大改進。
數據結構分為3類，即線性表、樹和圖，分別在本書的第二篇“線性表的編程實驗”、第三篇“樹的編程實驗”和第四篇“圖的編程實驗”中按知識體繫展開實驗，而排序和搜索的實驗則是和具體的數據結構結合，在相應的章節裡加以介紹。
第二篇“線性表的編程實驗”包括4章：第4章“應用直接存取類線性表編程”給出數組和字符串的實驗；第5章“應用順序存取類線性表編程”介紹鏈接存儲結構（指針）、棧、隊列的實驗；第6章“應用廣義索引類線性表編程”包含詞典解題和散列技術的實驗；第7章“線性表排序的編程實驗”從使用STL完成排序以及編程實現排序算法兩方面給出線性表排序的實驗。與本書第2版相比，本篇對高精度運算、棧、隊列等的實驗做了較大改進，並增加了Manacher算法和應用散列技術處理字符串的實驗。
第三篇“樹的編程實驗”包括3章：第8章“采用樹結構的非線性表編程”、第9章“應用二叉樹的基本概念編程”和第10章“應用經典二叉樹編程”。相比於本書第2版，本篇對並查集、樹狀數組、二叉樹路徑和遍歷、二叉搜索樹、樹堆、赫夫曼樹的實驗做了較大改進，並增加了用Trie樹查詢字符串、用AC自動機進行多模式匹配、應用典型二叉樹、AVL樹、伸展樹的實驗。
第四篇“圖的編程實驗”包括5章：第11章“應用圖的遍歷算法編程”、第12章“應用小生成樹算法編程”、第13章“應用路算法編程”、第14章“二分圖、網絡流算法編程”和第15章“應用狀態空間搜索編程”。相比於本書第2版，本篇對BFS、DFS、拓撲排序、路、二分圖、網絡流、優化狀態空間搜索、遊戲樹的實驗做了較大改進，並增加了計算圖的連通性、Tarjan算法、生成樹的實驗。
本書可用作高校數據結構、程序設計語言以及離散數學等課程的實驗教材，也可用作程序設計競賽選手的繫統訓練參考書籍。對於本書，我們的使用建議是：書中各章的實驗範例可以用於數據結構、程序設計語言以及離散數學相關課程的教學、實驗和上機作業，以及程序設計競賽選手掌握相關知識點的入門訓練；每章後給出的相關題庫中的試題可以作為程序設計競賽選手的專項訓練試題，以及學生進一步提高編程能力的練習題。
我們對浩如煙海的ACM-ICPC程序設計競賽區預賽和總決賽、各種大學生程序設計競賽、在線程序設計競賽以及中學生信息學奧林匹克競賽的試題進行了分析和整理，從中精選出306道試題作為本書的試題。其中，160道試題為實驗範例試題，每道試題不僅有詳盡的解析，還給出標有詳細注釋的參考程序；另外的146道試題為題庫試題，所有試題都有清晰的提示。
在華章網站（www.hzbook.com）上提供了本書所有試題的英文原版描述以及大部分試題的官方測試數據和解答程序。限於篇幅，書中部分實驗範例試題的參考程序未放在書中，而是以PDF文件的形式和試題的英文原版描述一起作為本書附加資源，讀者可從華章網站下載這些資源。
這些年來，我們秉承“不忘初心，方得始終”的思想，不斷地完善和改進繫列著作。我們也得到了海內外各位同人的鼎力相助。感謝石溪大學的Steven Skiena教授和Rezaul Chowdhury教授，得克薩斯州立大學的C. Jinshong Hwang教授、Ziliang Zong教授和Hongchi Shi教授，德國科技大學阿曼分校的Rudolf Fleischer教授，他們為本書英文版書稿的試用和改進做了大量工作。
感謝組織程序設計訓練營集訓並邀請我使用本書書稿講學的香港理工大學曹建農教授、臺北商業大學彭勝龍教授、西北工業大學姜學峰教授和劉君瑞教授、寧夏理工學院副校長俞經善教授、中國礦業大學畢方明教授，以及中國礦業大學徐海學院劉昆教授等。感謝盧森堡大學博士生張一博、香港中文大學博士生王禹對於本書第3版的編寫提出的建設性意見。
特別感謝中國大陸及中國臺灣、中國香港、中國澳門的同人和我一起創建ACM-ICPC亞洲訓練聯盟，聯盟的創建不僅為本書書稿，也為繫列著作及其課程建設提供了一個實踐的平臺。
由於時間和水平所限，書中難免存在缺點和錯誤，表述不當和筆誤也在所難免，歡迎學術界同人和讀者不吝指正。如果你在閱讀中發現了問題，懇請通過電子郵件告訴我們，以便我們在課程建設和中、英文版再版時改進。聯繫方式如下：
通信地址：上海市邯鄲路220號復旦大學計算機科學技術學院吳永輝（郵編：200433）
電子郵件：yhwu@fudan.edu.cn

吳永輝
2020年9月30日於上海

注：本書試題的在線測試地址如下。
在線評測繫統簡稱網址
北京大學在線評測繫統POJhttp://poj.org/
浙江大學在線評測繫統ZOJhttps://zoj.pintia.cn/home
UVA在線評測繫統UVAhttp://uva.onlinejudge.org/http://livearchive.onlinejudge.org/
Ural在線評測繫統Uralhttp://acm.timus.ru/
HDOJ在線評測繫統HDOJhttp://acm.hdu.edu.cn/

商品搜索

商品分类

【醫學】

【各大出版社】