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

吳永輝　　
2020年9月30日于上�！　�

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