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

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

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