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

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


徐孝凱
2006年8月


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

徐孝凱
1999年10月