序 言
時(shí)光更迭、歷史嬗遞。中國(guó)經(jīng)濟(jì)以她足以令世人驚嘆的持續(xù)高速發(fā)展駛?cè)肓艘粋�(gè)新的世紀(jì)，一個(gè)新的千年。世紀(jì)之初，以微電子、計(jì)算機(jī)、軟件和通信技術(shù)為主導(dǎo)的信息技術(shù)革命給我們生存的社會(huì)所帶來(lái)的變化令人目不暇接。軟件是優(yōu)化我國(guó)產(chǎn)業(yè)結(jié)構(gòu)、加速傳統(tǒng)產(chǎn)業(yè)改造和用信息化帶動(dòng)工業(yè)化的基礎(chǔ)產(chǎn)業(yè)，是體現(xiàn)國(guó)家競(jìng)爭(zhēng)力的戰(zhàn)略性產(chǎn)業(yè)，是從事知識(shí)的提煉、總結(jié)、深化和應(yīng)用的高智型產(chǎn)業(yè)；軟件關(guān)系到國(guó)家的安全，是保證我國(guó)政治獨(dú)立、文化不受侵蝕的重要因素；軟件也是促進(jìn)其他學(xué)科發(fā)展和提升的基礎(chǔ)學(xué)科；軟件作為20世紀(jì)人類(lèi)文明進(jìn)步的最偉大成果之一，代表了先進(jìn)文化的前進(jìn)方向。美國(guó)政府早在1992年“國(guó)家關(guān)鍵技術(shù)”一文中提出“美國(guó)在軟件開(kāi)發(fā)和應(yīng)用上所處的傳統(tǒng)領(lǐng)先地位是信息技術(shù)及其他重要領(lǐng)域競(jìng)爭(zhēng)能力的一個(gè)關(guān)鍵因素”，“一個(gè)成熟的軟件制造工業(yè)的發(fā)展是滿足商業(yè)與國(guó)防對(duì)復(fù)雜程序日益增長(zhǎng)的要求所必需的”，“在很多國(guó)家關(guān)鍵技術(shù)中，軟件是關(guān)鍵的、起推動(dòng)作用（或阻礙作用）的因素”。在1999年1月美國(guó)總統(tǒng)信息技術(shù)顧問(wèn)委員會(huì)的報(bào)告“21世紀(jì)的信息技術(shù)”中指出“從臺(tái)式計(jì)算機(jī)、電話系統(tǒng)到股市，我們的經(jīng)濟(jì)與社會(huì)越來(lái)越依賴于軟件”，“軟件研究為基礎(chǔ)研究方面最優(yōu)先發(fā)展的領(lǐng)域�！倍�軟件人才的缺乏和激烈競(jìng)爭(zhēng)是當(dāng)前國(guó)際的共性問(wèn)題。各國(guó)、各企業(yè)都對(duì)培養(yǎng)、引進(jìn)軟件人才采取了特殊政策與措施。
為了滿足社會(huì)對(duì)軟件人才的需要，為了讓更多的人可以更快地學(xué)到實(shí)用的軟件理論、技術(shù)與方法，我們編著了《普通高等院校計(jì)算機(jī)專(zhuān)業(yè)（本科）實(shí)用教程系列》。本套叢書(shū)面向普通高等院校學(xué)生，以培養(yǎng)面向21世紀(jì)計(jì)算機(jī)專(zhuān)業(yè)應(yīng)用人才（以軟件工程師為主）為 目標(biāo)，以簡(jiǎn)明實(shí)用、便于自學(xué)、反映計(jì)算機(jī)技術(shù)最新發(fā)展和應(yīng)用為特色，具體歸納為以下幾點(diǎn)：
1．進(jìn)透基本理論、基本原理、方法和技術(shù)，在寫(xiě)法上力求敘述詳細(xì)，算法具體，通俗易懂，便于自學(xué)。
2．理論結(jié)合實(shí)際。計(jì)算機(jī)是一門(mén)實(shí)踐性很強(qiáng)的科學(xué)，叢書(shū)貫徹從實(shí)踐中來(lái)到實(shí)踐中去的原則，許多技術(shù)理論結(jié)合實(shí)例講解，以便于學(xué)習(xí)理解。
3．本叢書(shū)形成完整的體系，每本教材既有相對(duì)獨(dú)立性，又有相互銜接和呼應(yīng)，為總的培養(yǎng)目標(biāo)服務(wù)。
4．每本教材都配以習(xí)題和實(shí)驗(yàn)，在各教學(xué)階段安排課程設(shè)計(jì)或大作業(yè)，培養(yǎng)學(xué)生的實(shí)戰(zhàn)能力與創(chuàng)新精神。習(xí)題和實(shí)驗(yàn)可以制作成光盤(pán)。
為了適應(yīng)計(jì)算機(jī)科學(xué)技術(shù)的發(fā)展，本系列教材將本著與時(shí)俱進(jìn)的精神不斷修訂更新，及時(shí)推出第二版、第三版……
新世紀(jì)曙光激人向上，催人奮進(jìn)。江澤民同志在十五屆五中全會(huì)上的講話：“大力推進(jìn)國(guó)民經(jīng)濟(jì)和社會(huì)信息化，是覆蓋現(xiàn)代化建設(shè)全局的戰(zhàn)略舉措。以信息化帶動(dòng)工業(yè)化，發(fā)揮后發(fā)優(yōu)勢(shì)，實(shí)現(xiàn)社會(huì)生產(chǎn)力的跨越式發(fā)展”，指明了我國(guó)信息界前進(jìn)的方向。21世紀(jì)日趨開(kāi)放的國(guó)策與更加迅速發(fā)展的科技會(huì)托起祖國(guó)更加輝煌燦爛的明天。

孫家廣
2004年1月
第二版前言
本書(shū)第一版出版至今已近7年，隨著計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)學(xué)科的不斷發(fā)展和教學(xué)的改革需要，在第一版的基礎(chǔ)上，整理和加工形成了第二版。
第一版教材深受讀者的喜愛(ài)，連續(xù)14次印刷，發(fā)行7萬(wàn)余冊(cè)，被許多高校選定為教材和考研參考書(shū)。有許多讀者在網(wǎng)站上發(fā)表評(píng)論，贊揚(yáng)本書(shū)的風(fēng)格和特色。
第二版對(duì)第一版的內(nèi)容進(jìn)行了優(yōu)化和適當(dāng)增刪，并對(duì)一些章節(jié)進(jìn)行了調(diào)整，由第1版中的8章修訂為10章。原來(lái)的第5章“樹(shù)”，改為第5章的“樹(shù)和二叉樹(shù)”和第6章的“特殊二叉樹(shù)”兩章，原來(lái)的第6章“圖”，改為第7章“圖”和第8章“圖的應(yīng)用”兩章。
在第二版教材中，增加了“堆”結(jié)構(gòu)的內(nèi)容、集合結(jié)構(gòu)的內(nèi)容、線性表應(yīng)用的內(nèi)容、棧與隊(duì)列應(yīng)用的內(nèi)容等；擴(kuò)充了棧與遞歸應(yīng)用的實(shí)例、二叉樹(shù)和樹(shù)查找運(yùn)算的算法、生成哈夫曼樹(shù)的算法、對(duì)B_樹(shù)的插入算法等；修改了從二叉搜索樹(shù)中刪除結(jié)點(diǎn)的算法、對(duì)外存文件進(jìn)行排序的算法等。當(dāng)然還對(duì)許多內(nèi)容進(jìn)行了修改，力爭(zhēng)反映該學(xué)科的先進(jìn)性和科學(xué)性，反映作為教材的系統(tǒng)性、實(shí)用性和可讀性。
第2版的內(nèi)容較豐富，在目錄、例題或習(xí)題中帶星號(hào)“*”的內(nèi)容可以不作為講授內(nèi)容和教學(xué)要求，留給學(xué)生自學(xué)。
書(shū)中所有算法和程序都在Visual C++ 6.0開(kāi)發(fā)環(huán)境下調(diào)試運(yùn)行通過(guò)，使得其正確性和有效性得到了進(jìn)一步驗(yàn)證。
數(shù)據(jù)結(jié)構(gòu)教材的內(nèi)容包括兩個(gè)層面：邏輯層面和實(shí)現(xiàn)層面。在邏輯層面上，介紹的是各種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，在每種數(shù)據(jù)結(jié)構(gòu)上進(jìn)行插入、刪除、查找、遍歷等相應(yīng)運(yùn)算的方 法，不涉及在計(jì)算機(jī)上實(shí)現(xiàn)運(yùn)算的算法；在實(shí)現(xiàn)層面上，討論的是如何把對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行運(yùn)算的方法和步驟轉(zhuǎn)換為用一種計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言描述的算法，并能夠?qū)嶋H運(yùn)行和得到驗(yàn)證。邏輯層面的學(xué)習(xí)是基本的和必需的，實(shí)現(xiàn)層面的學(xué)習(xí)是進(jìn)一步的，對(duì)于計(jì)算機(jī)及信息類(lèi)專(zhuān)業(yè)的學(xué)生，這兩步都要學(xué)，而且都要學(xué)好，對(duì)于經(jīng)管農(nóng)林等類(lèi)的學(xué)生，則應(yīng)側(cè)重 第1步。
數(shù)據(jù)結(jié)構(gòu)課程是一門(mén)理論性和實(shí)踐性都很強(qiáng)的課程，只有通過(guò)親自編寫(xiě)算法、上機(jī)運(yùn)行和調(diào)試程序，才能夠加深理解和掌握所學(xué)的知識(shí)，提高程序設(shè)計(jì)和軟件研發(fā)能力。
使用此教材，最好具有C++語(yǔ)言的基礎(chǔ)，因?yàn)闀?shū)中描述的數(shù)據(jù)類(lèi)型和算法都是按照C++語(yǔ)言的規(guī)則編寫(xiě)的。當(dāng)然，若是只具有其他計(jì)算機(jī)語(yǔ)言的基礎(chǔ)，則使用該書(shū)時(shí)應(yīng)同時(shí)自學(xué)C++語(yǔ)言。對(duì)于一般讀者來(lái)說(shuō)，只要有任一種計(jì)算機(jī)語(yǔ)言的基礎(chǔ)，再自學(xué)任何其他計(jì)算機(jī)語(yǔ)言都是不困難的。
與本書(shū)配套的《數(shù)據(jù)結(jié)構(gòu)實(shí)用教程習(xí)題參考解答》也同時(shí)改版，將同此主教材一并出版發(fā)行。與本書(shū)配套的《數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)》一書(shū)暫時(shí)不需改版，仍可繼續(xù)與這本第二版主教材配套使用。
在由清華大學(xué)出版社組織的此套系列教材中，本人還編著了《C++語(yǔ)言基礎(chǔ)教程》一書(shū)，該書(shū)已重印十多次，便于自學(xué)，讀者反映較好，并被列選為國(guó)家“十一五”規(guī)劃教材，不妨推薦給讀者參考。
衷心希望通過(guò)這次改版，使《數(shù)據(jù)結(jié)構(gòu)實(shí)用教程》一書(shū)更加受到讀者的愛(ài)戴和好評(píng)，也同時(shí)希望讀者繼續(xù)給予批評(píng)指正，本人深表謝意！
作者電子郵箱：xuxk@crtvu.edu.cn，聯(lián)系電話：010-64910302。


徐孝凱
2006年8月


第一版前言
數(shù)據(jù)結(jié)構(gòu)是普通高校計(jì)算機(jī)專(zhuān)業(yè)和信息管理專(zhuān)業(yè)一門(mén)必修的核心課程。它的主要任務(wù)是討論現(xiàn)實(shí)世界中數(shù)據(jù)（即事物的抽象描述）的各種邏輯結(jié)構(gòu)、在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)以及進(jìn)行各種非數(shù)值運(yùn)算的算法，目的是使學(xué)生掌握數(shù)據(jù)組織、存儲(chǔ)和處理的常用方法，為以后進(jìn)行軟件開(kāi)發(fā)和學(xué)習(xí)后續(xù)專(zhuān)業(yè)課程打下基礎(chǔ)。
數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹(shù)結(jié)構(gòu)和圖結(jié)構(gòu)4種。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)分為順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)和散列結(jié)構(gòu)4種。對(duì)數(shù)據(jù)進(jìn)行的非數(shù)值運(yùn)算主要包括插
入、刪除、查找、排序、輸入和輸出等。需要特別指出：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)既適用于內(nèi)存，
也適用于外存，不僅要學(xué)會(huì)對(duì)內(nèi)存數(shù)據(jù)操作的算法，而且要學(xué)會(huì)對(duì)外存數(shù)據(jù)（文件）操作的算法，這樣才能夠解決實(shí)際軟件開(kāi)發(fā)的問(wèn)題，達(dá)到學(xué)以致用的目的。
在已經(jīng)出版的眾多數(shù)據(jù)結(jié)構(gòu)教材中，對(duì)每一種數(shù)據(jù)結(jié)構(gòu)類(lèi)型進(jìn)行相應(yīng)運(yùn)算的算法描述通常是粗略的，離真正用一種計(jì)算機(jī)語(yǔ)言上機(jī)實(shí)現(xiàn)還有相當(dāng)?shù)木嚯x，特別在外存文件的操作上更是如此。本套教材在這方面做了徹底的改變，所給出的每一算法都利用C/C++語(yǔ)言給出了具體的實(shí)現(xiàn)，算法的正確性和有效性得到了實(shí)際的檢驗(yàn)，這樣就突出了實(shí)用性，使教材更便于教學(xué)，特別是自學(xué)，克服了以往同類(lèi)教材只重視理論而輕視算法具體實(shí)現(xiàn)的 缺陷。
本套教材包含3本，第一本為主教材《數(shù)據(jù)結(jié)構(gòu)實(shí)用教程》，第二本為實(shí)驗(yàn)教材《數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)》，第三本為輔助教材《數(shù)據(jù)結(jié)構(gòu)實(shí)用教程習(xí)題參考解答》。主教材共分為8章，依次為緒論、線性表、稀疏矩陣和廣義表、棧和隊(duì)列、樹(shù)、圖、查找和排序。在第1章的緒論中，1.2節(jié)為算法描述，對(duì)于C++語(yǔ)言比較熟悉的教學(xué)班和讀者，此內(nèi)容可作為自學(xué)閱讀內(nèi)容。主教材沒(méi)有專(zhuān)門(mén)給出文件一章，這是因?yàn)�，可把文件（這里只討論磁盤(pán)文件）看作存儲(chǔ)在外存上的數(shù)組，通過(guò)文件流操作函數(shù)既可順序存取文件內(nèi)容，也可隨機(jī)存取文件中任何位置上的信息塊，如何使用文件已經(jīng)在C/C++語(yǔ)言中學(xué)習(xí)過(guò)，在數(shù)據(jù)結(jié)構(gòu)課程中只是應(yīng)用問(wèn)題，所以不必單列一章介紹。實(shí)驗(yàn)教材給出了10個(gè)數(shù)據(jù)結(jié)構(gòu)應(yīng)用的典型例題，并給出了相應(yīng)的參考程序。輔助教材給出了主教材中每章習(xí)題的大部分參考解答，最后附加了兩個(gè)綜合題，它們是針對(duì)不同文件的插入、刪除和查找操作的，目的是培養(yǎng)學(xué)生對(duì)所學(xué)知識(shí)的實(shí)際應(yīng)用能力。
本人一直從事數(shù)據(jù)結(jié)構(gòu)的教學(xué)和研究工作，編著過(guò)多本教材，清華大學(xué)出版社已經(jīng)出版的《數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)明教程》一書(shū)就是其代表作�，F(xiàn)在這套教材是本人多年教學(xué)經(jīng)驗(yàn)的結(jié)晶，是對(duì)以往教材的繼承、豐富和發(fā)展，希望能夠?qū)��?shù)據(jù)結(jié)構(gòu)課程的教學(xué)起到良好的作用，使讀者能夠得到滿意的收獲。
本套教材是根據(jù)計(jì)算機(jī)專(zhuān)業(yè)和信息管理專(zhuān)業(yè)本科培養(yǎng)目標(biāo)，對(duì)數(shù)據(jù)結(jié)構(gòu)課程教學(xué)的要求編寫(xiě)的。由于內(nèi)容敘述細(xì)致，算法描述具體，便于自學(xué)，所以刪除部分內(nèi)容后可作為相應(yīng)專(zhuān)科學(xué)生的教材。具體如何刪減，應(yīng)由辦學(xué)單位和任課教師定奪。
學(xué)習(xí)本套教材應(yīng)具有C語(yǔ)言或C++語(yǔ)言的基礎(chǔ)。若只學(xué)習(xí)過(guò)C語(yǔ)言，則應(yīng)在學(xué)習(xí)本課程的過(guò)程中補(bǔ)充C++語(yǔ)言的輸入/輸出操作、文件流操作、運(yùn)算符重載等有關(guān)內(nèi)容。
本課程總學(xué)時(shí)應(yīng)安排在80～100學(xué)時(shí)之間，其中講授與上機(jī)學(xué)時(shí)之比應(yīng)為2∶1左右，有條件的學(xué)生要盡量多上機(jī)。
承蒙北京大學(xué)計(jì)算機(jī)系許卓群教授和北京石油大學(xué)計(jì)算機(jī)系陳明教授認(rèn)真審閱了本套教材的全部書(shū)稿，提出了寶貴的意見(jiàn)，在此謹(jǐn)向他們表示衷心感謝。
盡管本人做了很大的努力，但由于水平有限，加之時(shí)間倉(cāng)促，錯(cuò)誤和不足之處在所難免，敬請(qǐng)授課教師和廣大讀者批評(píng)指正。
電子郵箱地址：xuxk@crtvu.edu.cn，聯(lián)系電話：010-64910302。

徐孝凱
1999年10月