前言
要成為的程序員，必須學(xué)習(xí)“數(shù)據(jù)結(jié)構(gòu)與算法”課程。雖然同類課程或教材有些只是名為“數(shù)據(jù)結(jié)構(gòu)”，沒有提到“算法”，但實(shí)際上，數(shù)據(jù)結(jié)構(gòu)和算法，沒有必要也無法嚴(yán)格區(qū)分，兩者是“你中有我、我中有你”的關(guān)系。或者，將數(shù)據(jù)結(jié)構(gòu)算作算法的一個(gè)分支也未嘗不可，如著名教材《算法導(dǎo)論》，其中就包含大量數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。本書中涉及的問題，如果需要將數(shù)據(jù)以復(fù)雜的方式組織起來，就歸類為數(shù)據(jù)結(jié)構(gòu)；否則，就歸類為算法。
大多數(shù)課程或教材，用C語言實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)和算法。然而，相比C++語言，甚至Java和Python語言，用C語言實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)和算法有明顯的劣勢。C語言沒有對面向?qū)ο蟪绦蛟O(shè)計(jì)方法的支持，實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)無法做到“封裝”和“隱藏”。不支持“封裝”，導(dǎo)致代碼缺乏局部性，難以理解，難以維護(hù)。不支持“隱藏”，導(dǎo)致無法防止數(shù)據(jù)結(jié)構(gòu)從外部被不慎破壞，缺乏安全性。C語言不支持泛型程序設(shè)計(jì)，導(dǎo)致實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)和算法缺乏通用性或可重用性。例如，編寫一個(gè)可以對任何數(shù)據(jù)類型的數(shù)組排序的函數(shù)、編寫一個(gè)可以存放任何數(shù)據(jù)類型的二叉查找樹數(shù)據(jù)結(jié)構(gòu)是比較困難的，即便實(shí)現(xiàn)了，這樣的函數(shù)和數(shù)據(jù)結(jié)構(gòu)的使用方式也較為麻煩和不自然。C語言無可變長數(shù)組，這導(dǎo)致在實(shí)現(xiàn)圖的鄰接表、樹等數(shù)據(jù)結(jié)構(gòu)時(shí)不得不采用鏈表、兒子�残值軜涞染幊绦�率或運(yùn)行效率不佳的方案�？傊�，“數(shù)據(jù)結(jié)構(gòu)與算法”是理論結(jié)合實(shí)踐的課程，對數(shù)據(jù)結(jié)構(gòu)和算法的編程實(shí)現(xiàn)，不但應(yīng)該正確，還應(yīng)在工程上是優(yōu)美的，即安全、簡潔、好用、可重用，這用C語言很難做到。目前，程序設(shè)計(jì)方法的潮流是面向?qū)ο蟆⒎盒秃秃瘮?shù)式編程，C語言對這三大特性均無支持，故作者認(rèn)為，當(dāng)前的數(shù)據(jù)結(jié)構(gòu)和算法教學(xué)，亟須改革，將用C語言描述數(shù)據(jù)結(jié)構(gòu)和算法，轉(zhuǎn)變?yōu)橛弥С置嫦驅(qū)ο�、支持泛型和函�?shù)式編程的C++語言描述。
然而，系統(tǒng)掌握C++語言有較高的學(xué)習(xí)成本，即便對已經(jīng)掌握C語言的編程者也是如此，這是阻礙C++語言在數(shù)據(jù)結(jié)構(gòu)和算法教學(xué)中得以推廣的主要原因。實(shí)際上，C++語言的大量特性，如異常處理、繼承、多態(tài)等，是為了編寫大型程序而設(shè)計(jì)的，數(shù)十行或一百多行代碼即可實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)和算法不需要使用這些特性，因而用C++語言進(jìn)行數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)，其實(shí)無須學(xué)員系統(tǒng)地掌握C++語言，只須學(xué)會(huì)C++語言中一小部分最核心的面向?qū)ο蟆⒎盒秃秃瘮?shù)式編程特性即可。為此，作者抽取了這部分核心特性，精心編寫了“C++語言快速入門和溫故知新”一章，依此章進(jìn)行4個(gè)課時(shí)的教學(xué)，可使學(xué)過C語言的學(xué)生掌握C++語言的精髓，從而可以充分理解本書的所有程序，并用C++語言編寫小型程序。本書完全適用于只學(xué)過C語言的讀者，故雖然所有程序均用C++語言實(shí)現(xiàn)，卻依然命名為《數(shù)據(jù)結(jié)構(gòu)與算法(C/C++語言實(shí)現(xiàn))》。
作者在北京大學(xué)講授“數(shù)據(jù)結(jié)構(gòu)與算法”和“數(shù)據(jù)結(jié)構(gòu)與算法實(shí)習(xí)”課程多年,并曾擔(dān)任北京大學(xué)ACM國際大學(xué)生程序設(shè)計(jì)競賽隊(duì)教練9年。作者講授的這些課程，既有面向非計(jì)算機(jī)專業(yè)的，也有面向計(jì)算機(jī)專業(yè)的。本書即是對這些課程教學(xué)經(jīng)驗(yàn)的歸納與整合。
本書數(shù)據(jù)結(jié)構(gòu)部分包括線性表、棧、隊(duì)列、二叉樹、堆、哈夫曼樹、樹和森林、并查集、散列表、二叉查找樹、AVL樹、紅黑樹、B�矘洹�B+樹、圖、矩陣等內(nèi)容。算法部分包括枚舉、二分、遞歸、深度優(yōu)先搜索、廣度優(yōu)先搜索、貪心、動(dòng)態(tài)規(guī)劃、內(nèi)排序、外排序、最短路、最小生成樹、拓?fù)渑判�、關(guān)鍵路徑等內(nèi)容。數(shù)據(jù)結(jié)構(gòu)部分和算法部分交替講述。本書內(nèi)容覆蓋計(jì)算機(jī)專業(yè)408考研大綱。
相比大部分同類教材，本書的知識(shí)覆蓋面更廣，尤其是算法部分。
閱讀本書需要讀者已經(jīng)掌握C語言程序設(shè)計(jì)的基礎(chǔ)知識(shí)。對于學(xué)過C語言程序設(shè)計(jì)的讀者，本書非常適合作為第二門編程課的教材。
本書內(nèi)容和習(xí)題按難度明確分級(jí)，不論是高校計(jì)算機(jī)專業(yè)還是非計(jì)算機(jī)專業(yè)的師生，都可以從中各取所需。不帶“★”標(biāo)記的是基本內(nèi)容，適用于所有讀者；計(jì)算機(jī)專業(yè)的讀者應(yīng)掌握帶“★”標(biāo)記的章節(jié)；標(biāo)記為“★★”的內(nèi)容，則適用于高水平院校計(jì)算機(jī)專業(yè)的教學(xué)；少數(shù)標(biāo)記為“★★★”的例題和習(xí)題，難度與大學(xué)生程序設(shè)計(jì)競賽的中等題相當(dāng)。有些例題習(xí)題來自早年的程序設(shè)計(jì)競賽，或在競賽中本就是簡單題，難度不高，因而沒有“★★★”標(biāo)記，甚至沒有“★”標(biāo)記。
作者考察了許多國內(nèi)外流行的數(shù)據(jù)結(jié)構(gòu)與算法教材，發(fā)現(xiàn)許多教材中多用偽代碼，或不完整的代碼來描述數(shù)據(jù)結(jié)構(gòu)和算法，很少給出能直接運(yùn)行的完整程序。不但需要實(shí)打?qū)嵕幊探鉀Q的例題很少，而且配套的習(xí)題，基本都是考查概念，或只要求描述解決問題的過程，幾乎不會(huì)要求寫出完整的、完全正確的程序。即便一些教材中有編程習(xí)題，讀者也無法評判自己編寫的解題程序是否完全正確無隱錯(cuò)。用這樣的教材教學(xué)，雖然可以應(yīng)付考研等筆試考試，但是難免有紙上談兵之嫌。一旦碰到企業(yè)招聘要求現(xiàn)場寫代碼，或者考研復(fù)試要求上機(jī)寫代碼，往往力不從心。
相比大多數(shù)數(shù)據(jù)結(jié)構(gòu)和算法教材，本書的最大特點(diǎn)就是高標(biāo)準(zhǔn)的實(shí)踐性。除了少數(shù)幾個(gè)特別復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，95%的數(shù)據(jù)結(jié)構(gòu)和算法都給出了完整可運(yùn)行的代碼，并且這些代碼大部分都出現(xiàn)在具體的例題中。
本書的例題和編程習(xí)題，都可以在北京大學(xué)在線程序評測平臺(tái)OpenJudge上提交解題程序。平臺(tái)廣泛用于北京大學(xué)“計(jì)算概論”“程序設(shè)計(jì)實(shí)習(xí)”“數(shù)據(jù)結(jié)構(gòu)與算法”等編程類課程的教學(xué)。要在OpenJudge上完成本書的編程習(xí)題，必須對相應(yīng)的數(shù)據(jù)結(jié)構(gòu)和算法知識(shí)的每個(gè)實(shí)現(xiàn)細(xì)節(jié)都清楚地掌握，且編寫的程序不能有隱錯(cuò)，這樣的要求,比自己寫個(gè)程序隨意測試一下沒發(fā)現(xiàn)問題就算對了要高得多，更遠(yuǎn)非在紙上寫寫畫畫的筆試型習(xí)題可比。OpenJudge的具體使用方法見附錄。
本書配套電子資料齊全，包括課程講義以及130多個(gè)風(fēng)格簡潔優(yōu)美的程序源碼。
本書還另有Python語言版和Java語言版，均已經(jīng)由清華大學(xué)出版社出版。
作者水平有限，書中難免存在一些不足及疏漏之處，懇請讀者批評指正。讀者可以通過guo_wei@pku.edu.cn與作者溝通、交流。
作者的女兒兼校友郭小美審閱并校對了全部書稿。一部分程序由她從作者編寫的其他語言的程序改寫為C++程序，特此感謝。

郭煒
于北京大學(xué)信息科學(xué)技術(shù)學(xué)院
2025年4月