日韩美卡一卡二卡新区,国产精品不卡a∨在线观看,十七岁中国高清免费观看

　　本書(shū)在選材與編排上貼近當(dāng)前普通高等院校“數(shù)據(jù)結(jié)構(gòu)”課程的現(xiàn)狀和發(fā)展趨勢(shì)，內(nèi)容難度適中，突出實(shí)用性和應(yīng)用性。本書(shū)的具體內(nèi)容并未涉及各種數(shù)據(jù)結(jié)構(gòu)，而是通過(guò)分類和講解典型結(jié)構(gòu)使讀者形成對(duì)數(shù)據(jù)結(jié)構(gòu)的宏觀認(rèn)識(shí)。根據(jù)內(nèi)容的側(cè)重，本書(shū)共分8章，分別為緒論、線性表、棧和隊(duì)列、串和數(shù)組、樹(shù)形結(jié)構(gòu)、圖、排序和查找。　　本書(shū)可作為普通高校計(jì)算機(jī)相關(guān)專業(yè)“數(shù)據(jù)結(jié)構(gòu)”課程的教材，也可供學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的讀者自學(xué)使用（包括參加計(jì)算機(jī)等級(jí)考試或相關(guān)專業(yè)自學(xué)考試）、參考，還可供程序員、系統(tǒng)工程師等相關(guān)人員閱讀參考。　　本書(shū)是高等院校計(jì)算機(jī)科學(xué)、軟件工程及相關(guān)專業(yè)“數(shù)據(jù)結(jié)構(gòu)”課程的理想教材。

　　前言

　　隨著近年來(lái)計(jì)算概念的快速發(fā)展，計(jì)算學(xué)科已經(jīng)發(fā)展成為一個(gè)內(nèi)涵繁雜的綜合性學(xué)科，其至少可以劃分為計(jì)算機(jī)工程(CE)、計(jì)算機(jī)科學(xué)(CS)、信息系統(tǒng)(IS)、信息技術(shù)(IT)和軟件工程(SE)5個(gè)領(lǐng)域，而且不同領(lǐng)域的人才所應(yīng)具備的知識(shí)結(jié)構(gòu)與能力側(cè)重也不盡相同。盡管如此，從目前已經(jīng)完成的部分來(lái)看，數(shù)據(jù)結(jié)構(gòu)在各領(lǐng)域的知識(shí)體系中仍然占據(jù)著重要的位置。“數(shù)據(jù)結(jié)構(gòu)”是普通高等院校計(jì)算機(jī)和信息管理等專業(yè)的一門必修課程，主要討論數(shù)據(jù)的邏輯結(jié)構(gòu)、在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)以及對(duì)其進(jìn)行的各種處理運(yùn)算的方法和算法。

　　N.Wirth早在20世紀(jì)70年代就指出“程序=數(shù)據(jù)結(jié)構(gòu)+算法”。數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)在計(jì)算機(jī)中存儲(chǔ)、組織、傳遞和轉(zhuǎn)換的過(guò)程及方法，這些也是構(gòu)成與支撐算法的基礎(chǔ)。近年來(lái)，隨著面向?qū)ο蠹夹g(shù)的廣泛應(yīng)用，從數(shù)據(jù)結(jié)構(gòu)的定義、分類、組成到設(shè)計(jì)、實(shí)現(xiàn)與分析的模式和方法都有了長(zhǎng)足的發(fā)展，現(xiàn)代數(shù)據(jù)結(jié)構(gòu)更加注重和強(qiáng)調(diào)數(shù)據(jù)結(jié)構(gòu)的整體性、通用性、復(fù)用性、簡(jiǎn)潔性和安全性。

　　為遵循上述原則，本書(shū)選擇Java作為描述語(yǔ)言，因?yàn)橄鄬?duì)于其他語(yǔ)言，Java程序設(shè)計(jì)語(yǔ)言是應(yīng)用最廣泛、面向?qū)ο蟪潭然罡叩恼Z(yǔ)言，利用Java語(yǔ)言中的類和接口能夠準(zhǔn)確地描述任何一種數(shù)據(jù)結(jié)構(gòu)的邏輯定義和運(yùn)算，利用一種存儲(chǔ)結(jié)構(gòu)定義的派生類能夠高效地實(shí)現(xiàn)對(duì)數(shù)據(jù)的運(yùn)算。

　　在內(nèi)容的選取與結(jié)構(gòu)上，本書(shū)并未涉及各種數(shù)據(jù)結(jié)構(gòu)，而是通過(guò)分類和講解典型結(jié)構(gòu)使讀者形成對(duì)數(shù)據(jù)結(jié)構(gòu)的宏觀認(rèn)識(shí)。根據(jù)內(nèi)容的側(cè)重，本書(shū)共分8章，分別為緒論、線性表、棧和隊(duì)列、串和數(shù)組、樹(shù)形結(jié)構(gòu)、圖、排序和查找。

　　第1章介紹數(shù)據(jù)結(jié)構(gòu)的基本概念，算法的描述和算法時(shí)間復(fù)雜度、空間復(fù)雜度等內(nèi)容，是全書(shū)的基礎(chǔ)。

　　第2章主要介紹線性表的基本概念和抽象數(shù)據(jù)類型定義、線性表順序和鏈?zhǔn)絻煞N存儲(chǔ)方式的表示、基本操作的實(shí)現(xiàn)和相應(yīng)的應(yīng)用。

　　第3章簡(jiǎn)要介紹棧和隊(duì)列的基本概念和抽象數(shù)據(jù)類型定義、棧和隊(duì)列在順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的基本操作和應(yīng)用。

　　第4章主要介紹串的基本概念和數(shù)據(jù)類型定義、串的存儲(chǔ)結(jié)構(gòu)、基本操作實(shí)現(xiàn)和應(yīng)用等內(nèi)容。

　　第5章主要介紹樹(shù)和二叉樹(shù)的基本概念，詳細(xì)介紹二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)、遍歷方法的實(shí)現(xiàn)及應(yīng)用、哈夫曼樹(shù)的概念和構(gòu)造方法。

　　第6章主要介紹圖的基本概念、抽象數(shù)據(jù)類型定義、存儲(chǔ)結(jié)構(gòu)和遍歷方法，還介紹最小生成樹(shù)的基本概念和算法、最短路徑的相關(guān)算法、拓?fù)渑判虻母拍詈蛯?shí)現(xiàn)方法。

　　第7章介紹排序的基本概念，插入排序、交換排序、選擇排序、歸并排序等多種排序的原理、實(shí)現(xiàn)方法及性能分析。

　　第8章主要介紹查找的基本概念，順序查找、二分查找等查找的原理、實(shí)現(xiàn)方法和性能分析，平衡二叉樹(shù)、哈希表的概念、結(jié)構(gòu)定義和實(shí)現(xiàn)方法。

　　本書(shū)的理論知識(shí)的教學(xué)安排建議如下：

　　章節(jié)內(nèi)容學(xué)時(shí)數(shù)

　　第1章緒論2

　　第2章線性表4~6

　　第3章棧和隊(duì)列6~8

　　第4章串和數(shù)組2~4

　　第5章樹(shù)形結(jié)構(gòu)6~8

　　第6章圖4~8

　　第7章排序4~6

　　第8章查找4~6

　　建議先修課程：Java語(yǔ)言

　　建議理論教學(xué)時(shí)數(shù)：32~48學(xué)時(shí)

　　建議實(shí)驗(yàn)(實(shí)踐)教學(xué)時(shí)數(shù)：16~32學(xué)時(shí)

　　本書(shū)中的所有算法都已經(jīng)通過(guò)上機(jī)調(diào)試，盡量確保算法的正確性。在每章內(nèi)容后都有小結(jié)，便于讀者復(fù)習(xí)總結(jié)，并配有豐富的習(xí)題，包括選擇題、填空題、算法設(shè)計(jì)題等，給讀者更多思考的空間。

　　本書(shū)在以下幾個(gè)方面具有突出特色：

　�。�1）內(nèi)容精練，強(qiáng)化基礎(chǔ)，合理安排內(nèi)容結(jié)構(gòu)，做到由淺入深、循序漸進(jìn)。

　　本書(shū)各章節(jié)都從基本概念入手，逐步介紹其特點(diǎn)和基本操作的實(shí)現(xiàn)，把重點(diǎn)放在基礎(chǔ)知識(shí)的介紹上，縮減難度較大的內(nèi)容，使理論敘述簡(jiǎn)潔明了、重點(diǎn)突出、詳略得當(dāng)。

　�。�2）應(yīng)用實(shí)例豐富、完整。

　　本書(shū)通過(guò)豐富的應(yīng)用實(shí)例和源代碼使理論和應(yīng)用緊密結(jié)合，增強(qiáng)學(xué)生的理解能力，鍛煉程序設(shè)計(jì)思維，并且代碼有詳細(xì)明了的注釋，易于閱讀。

　　（3）每章后面附有小結(jié)和習(xí)題，便于學(xué)習(xí)、總結(jié)和提高。

　　本書(shū)結(jié)合學(xué)生的學(xué)習(xí)實(shí)際選擇難度適中、邏輯合理，適于初學(xué)者和進(jìn)階者開(kāi)拓思路、深入了解數(shù)據(jù)結(jié)構(gòu)使用方法和技巧的習(xí)題，并附有詳細(xì)的解答過(guò)程和注意要點(diǎn)，達(dá)到通俗易懂、由淺入深的效果，培養(yǎng)讀者遷移知識(shí)的能力。

　　（4）采用Java的泛型方法來(lái)體現(xiàn)方法的通用性。

　　本書(shū)采用面向?qū)ο蟮挠^點(diǎn)討論數(shù)據(jù)結(jié)構(gòu)技術(shù)，先將抽象數(shù)據(jù)類型定義成接口，再結(jié)合具體的存儲(chǔ)結(jié)構(gòu)加以實(shí)現(xiàn)，并以各實(shí)現(xiàn)類為線索對(duì)類中各種操作的實(shí)現(xiàn)方法加以說(shuō)明。

　　（5）圖文并茂，便于學(xué)生直觀地理解數(shù)據(jù)結(jié)構(gòu)與算法。

　　本書(shū)通過(guò)圖表的方式對(duì)數(shù)據(jù)結(jié)構(gòu)及相應(yīng)操作進(jìn)行簡(jiǎn)單直接的描述，使內(nèi)容更加淺顯易懂。

　　教師可以按照自己對(duì)數(shù)據(jù)結(jié)構(gòu)的理解適當(dāng)?shù)靥^(guò)一些章節(jié)，也可以根據(jù)教學(xué)目標(biāo)靈活地調(diào)整章節(jié)的順序，增減各章的學(xué)時(shí)數(shù)。

　　由于數(shù)據(jù)結(jié)構(gòu)本身還在探索之中，加上我們的水平和能力有限，本書(shū)難免有疏漏之處，懇請(qǐng)各位同仁和廣大讀者給予批評(píng)指正，也希望各位能將實(shí)踐過(guò)程中的經(jīng)驗(yàn)和心得與我們交流(yunxianglu@hotmail.com)。

　　作者

　　2017年6月

　　第5章

　　樹(shù)形結(jié)構(gòu)

　　5.1樹(shù)

　　5.1.1樹(shù)的基本概念

　　樹(shù)是數(shù)據(jù)元素之間具有層次關(guān)系的非線性結(jié)構(gòu)，是由n個(gè)結(jié)點(diǎn)構(gòu)成的有限集合，結(jié)點(diǎn)數(shù)為0的樹(shù)叫空樹(shù)。樹(shù)必須滿足以下條件。

　　(1)有且僅有一個(gè)被稱為根的結(jié)點(diǎn)。

　　(2)其余結(jié)點(diǎn)可分為m個(gè)互不相交的有限集合，每個(gè)集合又構(gòu)成一棵樹(shù)，叫根結(jié)點(diǎn)的子樹(shù)。

　　與線性結(jié)構(gòu)不同，樹(shù)中的數(shù)據(jù)元素具有一對(duì)多的邏輯關(guān)系，除根結(jié)點(diǎn)以外，每個(gè)數(shù)據(jù)元素可以有多個(gè)后繼但有且僅有一個(gè)前驅(qū)，反映了數(shù)據(jù)元素之間的層次關(guān)系。

　　樹(shù)是遞歸定義的。結(jié)點(diǎn)是樹(shù)的基本單位，若干個(gè)結(jié)點(diǎn)組成一棵子樹(shù)，若干棵互不相交的子樹(shù)組成一棵樹(shù)。

　　圖5.1樹(shù)的邏輯結(jié)構(gòu)示意圖

　　人們?cè)谏钪兴?jiàn)的家譜、Windows的文件系統(tǒng)等，雖然表現(xiàn)形式各異，在本質(zhì)上是樹(shù)結(jié)構(gòu)。圖5.1給出了樹(shù)的邏輯結(jié)構(gòu)示意圖。

　　樹(shù)的表示方法有多種，如樹(shù)形表示法、文氏圖表示法、凹入圖表示法和廣義表表示法。圖5.1所示為樹(shù)形表示法，圖5.2給出了用其他3種表示法對(duì)樹(shù)的表示。

　　圖5.2樹(shù)的3種表示方法

　　5.1.2樹(shù)的術(shù)語(yǔ)

　　1.結(jié)點(diǎn)

　　樹(shù)的結(jié)點(diǎn)就是構(gòu)成樹(shù)的數(shù)據(jù)元素，就是其他數(shù)據(jù)結(jié)構(gòu)中存儲(chǔ)的數(shù)據(jù)項(xiàng)，在樹(shù)形表示法中用圓圈表示。

　　2.結(jié)點(diǎn)的路徑

　　結(jié)點(diǎn)的路徑是指從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)過(guò)結(jié)點(diǎn)的順序排列。

　　3.路徑的長(zhǎng)度

　　路徑的長(zhǎng)度指的是路徑中包含的分支數(shù)。

　　4.結(jié)點(diǎn)的度

　　結(jié)點(diǎn)的度指的是結(jié)點(diǎn)擁有的子樹(shù)的數(shù)目。

　　5.樹(shù)的度

　　樹(shù)的度指的是樹(shù)中所有結(jié)點(diǎn)的度的最大值。

　　6.葉結(jié)點(diǎn)

　　葉結(jié)點(diǎn)是樹(shù)中度為0的結(jié)點(diǎn)，也叫終端結(jié)點(diǎn)。

　　7.分支結(jié)點(diǎn)

　　分支結(jié)點(diǎn)是樹(shù)中度不為0的結(jié)點(diǎn)，也叫非終端結(jié)點(diǎn)。

　　8.子結(jié)點(diǎn)

　　子結(jié)點(diǎn)是指結(jié)點(diǎn)的子樹(shù)的根結(jié)點(diǎn)，也叫孩子結(jié)點(diǎn)。

　　9.父結(jié)點(diǎn)

　　具有子結(jié)點(diǎn)的結(jié)點(diǎn)叫該子結(jié)點(diǎn)的父結(jié)點(diǎn)，也叫雙親結(jié)點(diǎn)。

　　10.子孫結(jié)點(diǎn)

　　子孫結(jié)點(diǎn)是指結(jié)點(diǎn)的子樹(shù)中的任意結(jié)點(diǎn)。

　　11.祖先結(jié)點(diǎn)

　　祖先結(jié)點(diǎn)是指結(jié)點(diǎn)的路徑中除自身之外的所有結(jié)點(diǎn)。

　　12.兄弟結(jié)點(diǎn)

　　兄弟結(jié)點(diǎn)是指和結(jié)點(diǎn)具有同一父結(jié)點(diǎn)的結(jié)點(diǎn)。

　　13.結(jié)點(diǎn)的層次

　　樹(shù)中根結(jié)點(diǎn)的層次為0，其他結(jié)點(diǎn)的層次是父結(jié)點(diǎn)的層次加1。

　　14.樹(shù)的深度

　　樹(shù)的深度是指樹(shù)中所有結(jié)點(diǎn)的層次數(shù)的最大值加1。

　　15.有序樹(shù)

　　有序樹(shù)是指樹(shù)的各結(jié)點(diǎn)的所有子樹(shù)具有次序關(guān)系，不可以改變位置。

　　16.無(wú)序樹(shù)

　　無(wú)序樹(shù)是指樹(shù)的各結(jié)點(diǎn)的所有子樹(shù)之間無(wú)次序關(guān)系，可以改變位置。

　　17.森林

　　森林是由多個(gè)互不相交的樹(shù)構(gòu)成的集合。給森林加上一個(gè)根結(jié)點(diǎn)就變成一棵樹(shù)，將樹(shù)的根結(jié)點(diǎn)刪除就變成森林。

　　5.2二叉樹(shù)

　　5.2.1二叉樹(shù)的基本概念

　　1.普通二叉樹(shù)

　　二叉樹(shù)是特殊的有序樹(shù)，它也是由n個(gè)結(jié)點(diǎn)構(gòu)成的有限集合。當(dāng)n=0時(shí)稱為空二叉樹(shù)。二叉樹(shù)的每個(gè)結(jié)點(diǎn)最多只有兩棵子樹(shù)，子樹(shù)也為二叉樹(shù)，互不相交且有左右之分，分別稱為左二叉樹(shù)和右二叉樹(shù)。

　　二叉樹(shù)也是遞歸定義的，在樹(shù)中定義的度、層次等術(shù)語(yǔ)同樣也適用于二叉樹(shù)。

　　2.滿二叉樹(shù)

　　滿二叉樹(shù)是特殊的二叉樹(shù)，它要求除葉結(jié)點(diǎn)外的其他結(jié)點(diǎn)都具有兩棵子樹(shù)，并且所有的葉結(jié)點(diǎn)都在同一層上，如圖5.3所示。

　　3.完全二叉樹(shù)

　　完全二叉樹(shù)是特殊的二叉樹(shù)，若完全二叉樹(shù)具有n個(gè)結(jié)點(diǎn)，它要求n個(gè)結(jié)點(diǎn)與滿二叉樹(shù)的前n個(gè)結(jié)點(diǎn)具有完全相同的邏輯結(jié)構(gòu)，如圖5.4所示。

你還可能感興趣

我要評(píng)論