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

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


徐孝凱
2006年8月


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

徐孝凱
1999年10月