天堂国产午夜亚洲专区-少妇人妻综合久久蜜臀-国产成人户外露出视频在线-国产91传媒一区二区三区

當(dāng)前位置:主頁(yè) > 論文百科 > 大學(xué)課程 >

大話數(shù)據(jù)結(jié)構(gòu) 中文 PDF清晰掃描版 完整版 [36M] 下載

發(fā)布時(shí)間:2017-12-25 13:06

  本文關(guān)鍵詞:數(shù)據(jù)結(jié)構(gòu)  


  更多相關(guān)文章: 大話 數(shù)據(jù) 結(jié)構(gòu)


《大話數(shù)據(jù)結(jié)構(gòu)》以一個(gè)計(jì)算機(jī)教師教學(xué)為場(chǎng)景,講解數(shù)據(jù)結(jié)構(gòu)和相關(guān)算法的知識(shí)。通篇以一種趣味方式來(lái)敘述,大量引用了各種各樣的生活知識(shí)來(lái)類(lèi)比,并充分運(yùn)用圖形語(yǔ)言來(lái)體現(xiàn)抽象內(nèi)容,對(duì)數(shù)據(jù)結(jié)構(gòu)所涉及到的一些經(jīng)典算法做到逐行分析、多算法比較。與市場(chǎng)上的同類(lèi)數(shù)據(jù)結(jié)構(gòu)圖書(shū)相比,《大話數(shù)據(jù)結(jié)構(gòu)》內(nèi)容趣味易讀,算法講解細(xì)致深刻,是一本非常適合自學(xué)的讀物。
  《大話數(shù)據(jù)結(jié)構(gòu)》主要內(nèi)容包含:數(shù)據(jù)結(jié)構(gòu)介紹、算法推導(dǎo)大o階的方法;順序結(jié)構(gòu)與鏈?zhǔn)浇Y(jié)構(gòu)差異、棧與隊(duì)列的應(yīng)用;串的樸素模式匹配、kmp模式匹配算法;二叉樹(shù)前中后序遍歷、赫夫曼樹(shù)及應(yīng)用;圖的深度、廣度遍歷;最小生成樹(shù)兩種算法、最短路徑兩種算法;拓?fù)渑判蚺c關(guān)鍵路徑算法;折半查找、插值查找、斐波那契查找等靜態(tài)查找;稠密索引、分塊索引、倒排索引等索引技術(shù);二叉排序樹(shù)、平衡二叉樹(shù)等動(dòng)態(tài)查找;b樹(shù)、b+樹(shù)技術(shù),散列表技術(shù);冒泡、選擇、插入等簡(jiǎn)單排序;希爾、堆、歸并、快速等改進(jìn)排序……
  《大話數(shù)據(jù)結(jié)構(gòu)》適合學(xué)過(guò)一門(mén)編程語(yǔ)言的各類(lèi)讀者,包括在讀的大中專計(jì)算機(jī)專業(yè)學(xué)生、想轉(zhuǎn)行做開(kāi)發(fā)的非專業(yè)人員、欲考計(jì)算機(jī)研究生的應(yīng)屆或在職人員,以及工作后需要補(bǔ)學(xué)或溫習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的程序員等。
前言 本書(shū)起因
  大家好!我是《大話設(shè)計(jì)模式》(2008年初出版)的作者,三年來(lái),承蒙廣大讀者的厚愛(ài),《大話設(shè)計(jì)模式》取得了較大的成功。僅在當(dāng)當(dāng)網(wǎng),截止本文寫(xiě)作時(shí),就已經(jīng)有1073次評(píng)論,705次5星評(píng)價(jià),位居五星圖書(shū)榜計(jì)算機(jī)/網(wǎng)絡(luò)類(lèi)的累計(jì)總榜第二名。此書(shū)已經(jīng)成為國(guó)內(nèi)原創(chuàng)計(jì)算機(jī)類(lèi)圖書(shū)最暢銷(xiāo)的書(shū)籍之一。
  對(duì)于這樣一個(gè)自己喜歡做、可以做得好,而且已經(jīng)得到了市場(chǎng)廣泛認(rèn)可,為很多朋友提供幫助的事情,我沒(méi)有理由不去繼續(xù)做下去。這就是我準(zhǔn)備再寫(xiě)書(shū)的原因。
  我曾做過(guò)調(diào)查,數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)者大多都有這樣的感慨:數(shù)據(jù)結(jié)構(gòu)很重要,一定要學(xué)好,但數(shù)據(jù)結(jié)構(gòu)比較抽象,有些算法理解起來(lái)很困難,學(xué)得很累?晌腋M麄鬟_(dá)這樣的信息:數(shù)據(jù)結(jié)構(gòu)非常有趣,很多算法是智慧的結(jié)晶,學(xué)習(xí)它是去感受計(jì)算機(jī)編程技術(shù)的魅力,在理解掌握它的同時(shí),整個(gè)過(guò)程都是一種愉悅的精神感受,而非枯燥乏味的一門(mén)課程。因此我決定寫(xiě)作一本關(guān)于數(shù)據(jù)結(jié)構(gòu)有趣的書(shū)。
  不過(guò)現(xiàn)實(shí)總比理想來(lái)得更“現(xiàn)實(shí)”。要想把書(shū)寫(xiě)好,談何容易,我需要突破很多困難……嗐!不管如何,現(xiàn)在您看到了本書(shū),那就說(shuō)明我已經(jīng)克服了困難戰(zhàn)勝了自己。希望您可以喜歡上這本書(shū)。
  本書(shū)定位
  本書(shū)的定位就是一本適合讀者自學(xué)數(shù)據(jù)結(jié)構(gòu)的書(shū)籍,它有區(qū)別于教材,希望給大家另一種閱讀體驗(yàn)。
  通常講解數(shù)據(jù)結(jié)構(gòu)的圖書(shū)都是以教材的方式呈現(xiàn)。在寫(xiě)作前,我購(gòu)買(mǎi)或在圖書(shū)館借閱了十幾本非常好的數(shù)據(jù)結(jié)構(gòu)相關(guān)教材用來(lái)為寫(xiě)作本書(shū)做準(zhǔn)備。但經(jīng)過(guò)認(rèn)真閱讀后,我發(fā)現(xiàn),它們大多不是一本好的“自學(xué)讀物”。
  我沒(méi)有輕視這些好書(shū)的意思,不過(guò)教材和自學(xué)讀物,所面向的讀者是完全不同的。
  好的教材應(yīng)該是提綱挈領(lǐng)、重點(diǎn)突出,一定要留出思考的空間,否則就沒(méi)必要再聽(tīng)老師上課了。很多內(nèi)容的講解是由老師在課堂完成,教材中有練習(xí)、課后習(xí)題、思考題等,這些大多可以通過(guò)老師來(lái)解答。比如我們中學(xué)時(shí)的語(yǔ)文、數(shù)學(xué)課本,很薄的一本書(shū)通常要用一學(xué)期、甚至一年的時(shí)間來(lái)學(xué)習(xí),這就是因?yàn)樗鼈兪墙滩亩皇亲詫W(xué)讀物。如果是小說(shuō),可能一兩天就讀完了。
  好的自學(xué)讀物的目標(biāo)是讓初學(xué)者“獨(dú)自”全盤(pán)掌握知識(shí),需要強(qiáng)調(diào)“獨(dú)自”一詞,這就說(shuō)明讀者在閱讀時(shí),是完全依靠自己的力量來(lái)向未知發(fā)出挑戰(zhàn)。因此書(shū)中內(nèi)容,要么不寫(xiě),寫(xiě)了就應(yīng)該寫(xiě)透。如果讀者在閱讀時(shí)總是疑惑重重,那么這本書(shū)就有很大的問(wèn)題了。
  我也就是在基于這樣的認(rèn)識(shí),決心將《大話數(shù)據(jù)結(jié)構(gòu)》真正寫(xiě)成一本關(guān)于數(shù)據(jù)結(jié)構(gòu)和算法的自學(xué)讀物來(lái)展開(kāi)寫(xiě)作的。
  本書(shū)特色
  1.趣味引導(dǎo)
  大部分的編程類(lèi)圖書(shū),在內(nèi)容上基本都是直奔主題。但是尼采曾說(shuō)過(guò):“人們無(wú)法理解他沒(méi)有經(jīng)歷過(guò)的事情。”換句話說(shuō),我們只接受過(guò)去早已理解的事物相關(guān)的信息。這是一種比較學(xué)習(xí)過(guò)程,在這個(gè)過(guò)程中,大腦尋找每條信息之間的聯(lián)系。所以教育專家普遍認(rèn)為,吸引學(xué)生的注意力,比較好的辦法是用他們比較熟知的知識(shí)開(kāi)始。
  因此在本書(shū)中,我會(huì)用一個(gè)故事、一個(gè)趣味題目、一部電影的介紹等形式來(lái)作為每一章甚至很多小節(jié)的開(kāi)頭,選擇的內(nèi)容也多多少少與要講的主題內(nèi)容相關(guān)。這并不是多余,而是有意為之。事實(shí)上,這樣的形式在我的前一本書(shū)中已經(jīng)得到了普遍認(rèn)可。
  2.圖文并茂
  西方有句諺語(yǔ),“A picture is worth a thousand words.(一圖值千言)”。用上千個(gè)字描述不明白的東西,很可能一張圖就能解釋清楚。
  我非常認(rèn)可這個(gè)觀點(diǎn),所以本書(shū)雖沒(méi)有達(dá)到每一頁(yè)都有圖,但基本做到了絕大部分講解都有相關(guān)圖示,關(guān)鍵算法更是通過(guò)多圖逐步分解剖析。盡管這帶來(lái)了寫(xiě)作上的難度,但卻可以達(dá)到較好的效果。畢竟,讀者通過(guò)本書(shū)開(kāi)始學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時(shí),要從一無(wú)所知或略知一二到完全理解,甚至掌握應(yīng)用,是需要一個(gè)比較艱苦的過(guò)程,用大量的圖示可以減少這個(gè)過(guò)程的長(zhǎng)度。
  3.代碼詳解
.  我在寫(xiě)作中盡量摒棄了傳統(tǒng)數(shù)據(jù)結(jié)構(gòu)教材的“重理論思想而輕代碼講解”的作法。在準(zhǔn)備數(shù)據(jù)結(jié)構(gòu)寫(xiě)作時(shí)我發(fā)現(xiàn),很多教材對(duì)數(shù)據(jù)結(jié)構(gòu)理論和算法設(shè)計(jì)思想講得比較好,可一到實(shí)際代碼時(shí),有的把代碼貼出來(lái)加少量注釋,有的直接用偽代碼形式。這對(duì)于上課的學(xué)生還好,畢竟有老師在課堂中去詳解代碼編寫(xiě)原理,可是對(duì)于初學(xué)數(shù)據(jù)結(jié)構(gòu)和算法的自學(xué)者而言,如果書(shū)中不去解釋代碼某些細(xì)節(jié)為什么那樣編寫(xiě)的原因,甚至代碼根本不可能在某個(gè)編譯器中運(yùn)行通過(guò),其挫折感是很強(qiáng)烈的。比如即使理解了圖結(jié)構(gòu)中的最短路徑求解原理,也可能無(wú)法寫(xiě)出最短路徑的算法。
  我把代碼在運(yùn)行過(guò)程中變量的變化融入到整個(gè)算法設(shè)計(jì)思想的講解中,配合相應(yīng)的示意圖,會(huì)幫助大家更加容易理解算法的實(shí)質(zhì)。這種講解模式在本書(shū)的第6、7、8、9章的很多復(fù)雜算法中有具體體現(xiàn),越是復(fù)雜的代碼越是講解細(xì)致。這算是本書(shū)的一個(gè)特色,希望對(duì)讀者有幫助。
  4.形式新穎
  我把本書(shū)的內(nèi)容虛構(gòu)成了一個(gè)老師上課的場(chǎng)景,所有內(nèi)容都通過(guò)這位老師表達(dá)出來(lái),書(shū)中的文字非?谡Z(yǔ)化,這樣做的目的是為了更加直觀地讓讀者感覺(jué),自己是在學(xué)習(xí),是在上課。有人可能會(huì)說(shuō),現(xiàn)在的課堂大都是讓人昏昏欲睡,把讀者帶入上課場(chǎng)景,不是更加讓讀者犯困嗎?我覺(jué)得如果你的學(xué)習(xí)經(jīng)歷中聽(tīng)過(guò)一些優(yōu)秀老師的課,你就不會(huì)下這樣的結(jié)論。好的老師講課,是可以做到引人入勝的。
  有人可能會(huì)問(wèn),我為什么不用《大話設(shè)計(jì)模式》中的對(duì)話形式,而采用講課形式呢?這是對(duì)數(shù)據(jù)結(jié)構(gòu)這門(mén)學(xué)問(wèn)的特點(diǎn)考慮的。設(shè)計(jì)模式主要都是思想體現(xiàn),通常會(huì)仁者見(jiàn)仁、智者見(jiàn)智,用對(duì)話展開(kāi)比較容易;而數(shù)據(jù)結(jié)構(gòu)中更多的是定義、術(shù)語(yǔ)、經(jīng)典算法等,這些公認(rèn)的知識(shí),可討論的地方并不多,更多的是需要把它講清楚。讓兩個(gè)人在一起討論某個(gè)設(shè)計(jì)模式的優(yōu)缺點(diǎn),會(huì)非常合適,而討論數(shù)據(jù)結(jié)構(gòu)定義的好壞,就沒(méi)有太大意義了,不如讓一個(gè)老師告訴學(xué)生數(shù)據(jù)結(jié)構(gòu)的定義好在哪里更符合實(shí)際。因此用傳統(tǒng)的講課形式會(huì)好一些。
  另外,本書(shū)沒(méi)有習(xí)題,有思考的題目也一定會(huì)給出某種答案。但本書(shū)每個(gè)復(fù)雜知識(shí)點(diǎn)的末尾,都會(huì)提供另一本書(shū)的進(jìn)一步閱讀建議。這也是基于它是一本自學(xué)讀物的原則。讀者閱讀本書(shū)可能是任何時(shí)間任何地方,如果書(shū)中存在沒(méi)有解答的習(xí)題,碰到了困難是沒(méi)法及時(shí)找到老師來(lái)幫助的,因此本書(shū)盡量避免讓讀者有這樣的困惑存在。如果需要練習(xí)的同學(xué),我覺(jué)得還是應(yīng)該考慮再去買(mǎi)本習(xí)題集來(lái)學(xué)習(xí)。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法,做題和上機(jī)寫(xiě)代碼非常有必要,從這個(gè)角度也說(shuō)明,閱讀完本書(shū)其實(shí)也只是完成入門(mén)而已。
  本書(shū)既然是以老師上課的形式來(lái)進(jìn)行,那就免不了要融入一名教師除了授業(yè)解惑以外,還要傳達(dá)一些個(gè)人價(jià)值觀的體現(xiàn)。書(shū)中很多細(xì)微處,如對(duì)某位科學(xué)家的尊敬、對(duì)某個(gè)算法的推崇、對(duì)勤奮勵(lì)志故事的講述等都在表達(dá)著一個(gè)老師向?qū)W生傳遞真、善、美的意愿。我始終認(rèn)為,讀者拿到的雖然只是一本沒(méi)有表情、不會(huì)說(shuō)話的書(shū),但其實(shí)也是在隔空與另一個(gè)朋友交流。人與人的交流不可能只是就事論事,一定會(huì)有情感的溝通,這種情感如果能產(chǎn)生共鳴、達(dá)成互信,就會(huì)讓事情(比如學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法這件事)本身更容易理解和接受。
  本書(shū)內(nèi)容
  本書(shū)主要是按照教育部關(guān)于計(jì)算機(jī)專業(yè)數(shù)據(jù)結(jié)構(gòu)課程大綱的要求略微增減來(lái)組織內(nèi)容的。
  主要包括:數(shù)據(jù)結(jié)構(gòu)介紹,算法推導(dǎo)大O階的方法,線性表結(jié)構(gòu)的介紹,順序結(jié)構(gòu)與鏈?zhǔn)浇Y(jié)構(gòu)差異,棧與隊(duì)列的應(yīng)用,串的樸素模式匹配、KMP模式匹配算法,樹(shù)結(jié)構(gòu)的介紹,二叉樹(shù)前中后序遍歷,線索二叉樹(shù),赫夫曼樹(shù)及應(yīng)用,圖結(jié)構(gòu)的介紹,圖的深度、廣度遍歷,最小生成樹(shù)兩種算法,最短路徑兩種算法,拓?fù)渑判蚺c關(guān)鍵路徑算法,查找應(yīng)用的相關(guān)介紹,折半查找、插值查找、斐波那契查找等靜態(tài)查找,稠密索引、分塊索引、倒排索引等索引技術(shù),二叉排序樹(shù)、平衡二叉樹(shù)等動(dòng)態(tài)查找,B樹(shù)、B+樹(shù)技術(shù),散列表技術(shù),排序應(yīng)用的相關(guān)介紹,冒泡、選擇、插入等簡(jiǎn)單排序,希爾、堆、歸并、快速等改進(jìn)排序,各位排序算法的對(duì)比等。
  本書(shū)讀者
  數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)軟件相關(guān)專業(yè)的基礎(chǔ)課程,幾乎可以說(shuō),要想從事編程工作,無(wú)論你是否是科班出身,都不可以繞過(guò)這部分知識(shí)。因此,適合閱讀本書(shū)的讀者非常廣泛,包括在讀的本?、中專職高技校等計(jì)算機(jī)專業(yè)學(xué)生、想轉(zhuǎn)行做開(kāi)發(fā)的非專業(yè)人員、欲考計(jì)算機(jī)研究生的應(yīng)屆或在職人員,以及工作后需要補(bǔ)學(xué)或溫習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的程序員等各類(lèi)讀者。
  本書(shū)對(duì)讀者的技術(shù)背影要求比較低,只要是學(xué)過(guò)一門(mén)高級(jí)編程語(yǔ)言,例如C、C++、Java、C#、VB等就可以開(kāi)始閱讀本書(shū)。不過(guò)由于當(dāng)中涉及到比較復(fù)雜的算法知識(shí),需要讀者有一定的數(shù)學(xué)修養(yǎng)和邏輯思維能力,否則可能書(shū)籍的后半部分閱讀起來(lái)會(huì)比較吃力。
  本書(shū)研讀方法
  事實(shí)上,任何有難度的知識(shí)和技巧,都不是那么容易被掌握的。我盡管已經(jīng)朝著通俗易懂的方向努力,可有些數(shù)據(jù)結(jié)構(gòu),特別是經(jīng)典算法,是幾代科學(xué)家的智慧結(jié)晶,因此要掌握它們還是需要讀者的全力投入。
  美國(guó)暢銷(xiāo)書(shū)《如何閱讀一本書(shū)》中提到“閱讀可以是一件主動(dòng)的事,閱讀越主動(dòng),效果越好。拿同樣的書(shū)給背景相近的兩個(gè)人閱讀,一個(gè)人卻比另一個(gè)人從書(shū)中得到了更多,這是因?yàn),首先在于這人的主動(dòng),其次,在于他在閱讀中的每一種活動(dòng)都參與了更多的技巧。這兩件事是息息相關(guān)的。閱讀是一個(gè)復(fù)雜的活動(dòng),就跟寫(xiě)作一樣,包含了大量不同的活動(dòng)。要達(dá)成良好的閱讀,這些活動(dòng)都是不可或缺的。一個(gè)人越能良好運(yùn)作這些活動(dòng),閱讀的效果也就越好。”
  我當(dāng)然希望讀者在閱讀本書(shū)后收獲巨大,但這顯然是一廂情愿。要想獲得更多,您可能也需要付出類(lèi)似我寫(xiě)作一樣的力氣來(lái)閱讀,例如摘抄文字、眉批心得、稿紙演算、代碼輸入電腦,以及您自己在編程工作中的運(yùn)用等。這些相應(yīng)活動(dòng)的執(zhí)行,將會(huì)使您得到巨大的收獲。
  作為作者,建議本書(shū)的研讀方法為:
  1.復(fù)習(xí)C語(yǔ)言的基礎(chǔ)知識(shí)。如果你掌握的是別的語(yǔ)言也不要緊,適當(dāng)了解一些C語(yǔ)言和你掌握的編程語(yǔ)言的語(yǔ)法差異還是有必要的。甚至將本書(shū)代碼改造成另一種語(yǔ)言本身就是一種非常好的學(xué)習(xí)方法。
  2.閱讀第一遍時(shí),建議從頭至尾進(jìn)行。如果你對(duì)前面的知識(shí)有足夠了解,當(dāng)然可以跳過(guò)直接閱讀后面的章節(jié)。不過(guò)若要學(xué)習(xí)一門(mén)完整的知識(shí)并形成體系。通讀本書(shū),還是最好的學(xué)習(xí)方法。
  3.閱讀時(shí),摘抄是非常好的習(xí)慣。“最淡的墨水也勝于最強(qiáng)的記憶!”有不少讀者會(huì)認(rèn)為摘抄了將來(lái)也不會(huì)再去看,有什么必要,但其實(shí)在寫(xiě)字的過(guò)程就是大腦學(xué)習(xí)的過(guò)程,寫(xiě)字在減緩你閱讀的速度,從而讓你更好地消化閱讀的內(nèi)容。相信大家都能理解,“囫圇吞棗”和“慢慢品味”的差異,學(xué)習(xí)同樣如此。
  4.閱讀每一章時(shí),特別是在閱讀算法的推導(dǎo)過(guò)程時(shí),一定要在電腦中運(yùn)行代碼(本書(shū)源碼的下載地址可以到中的《大話數(shù)據(jù)結(jié)構(gòu)相關(guān)主題》中找到),了解代碼的運(yùn)行過(guò)程。本書(shū)的很多算法都做到了逐行講解,但單純閱讀可能真的很難達(dá)到理解的程度(這是紙質(zhì)書(shū)無(wú)法克服的缺陷),需要你通過(guò)開(kāi)發(fā)工具調(diào)試,并設(shè)置斷點(diǎn)和逐行執(zhí)行,并參照書(shū)中的講解,觀察變量的變化情況來(lái)理解算法的編寫(xiě)原理。
  5.閱讀完每一章時(shí),一定要在理解基礎(chǔ)上記憶一些關(guān)鍵東西。最佳的效果就是你可以不看書(shū)也做到一點(diǎn)不錯(cuò)地默寫(xiě)出相關(guān)算法。
  6.閱讀完每一章時(shí),一定要適當(dāng)練習(xí)。本書(shū)沒(méi)有提供練習(xí)題,但市場(chǎng)上相關(guān)的數(shù)據(jù)結(jié)構(gòu)習(xí)題集比比皆是,可以選擇嘗試。另外互聯(lián)網(wǎng)上也可以獲得足夠的習(xí)題來(lái)給你練習(xí)。練習(xí)的目的是為了檢測(cè)自己是否真的完全理解了書(shū)中的內(nèi)容。事實(shí)上很多時(shí)候,閱讀中的人們只是自我感覺(jué)理解,而并非真正的明白。
  7.學(xué)習(xí)不可能一蹴而就,數(shù)據(jù)結(jié)構(gòu)和算法如果通過(guò)一本書(shū)就可以掌握,那本身就是笑話。本書(shū)附錄提供了本書(shū)寫(xiě)作時(shí)的參考書(shū)目,基本都是最優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)或相關(guān)的中文書(shū)籍各有側(cè)重,建議大家可以適當(dāng)?shù)亻喿x。
  8.在之后的編程學(xué)習(xí)和工作中,盡量把已經(jīng)學(xué)到的數(shù)據(jù)結(jié)構(gòu)和算法知識(shí)運(yùn)用到現(xiàn)實(shí)開(kāi)發(fā)中。遺忘時(shí)翻閱本書(shū)回顧相關(guān)內(nèi)容,最終達(dá)到精通數(shù)據(jù)結(jié)構(gòu)和相關(guān)算法的境界。
  編程語(yǔ)言說(shuō)明
  本書(shū)是用C語(yǔ)言編寫(xiě),基于C90(ISO C)的標(biāo)準(zhǔn)。讀者可以選擇任何一款基于C90標(biāo)準(zhǔn)的C語(yǔ)言開(kāi)發(fā)工具或更高版本的開(kāi)發(fā)工具來(lái)學(xué)習(xí)本書(shū)中的代碼。
  本人一直習(xí)慣于用Visual Studio 2008作為開(kāi)發(fā)工具,因此在寫(xiě)作此書(shū)時(shí),也是用此工具的Visual C++來(lái)編譯調(diào)試代碼,一切都相安無(wú)事,但寫(xiě)作完成后,考慮到不同讀者應(yīng)用開(kāi)發(fā)工具的習(xí)慣不同,最終在編輯的建議下,決定提供一份可在C90標(biāo)準(zhǔn)的C語(yǔ)言開(kāi)發(fā)環(huán)境中編譯通過(guò)的代碼,結(jié)果發(fā)現(xiàn)錯(cuò)誤百出。
  例如C90標(biāo)準(zhǔn)的注釋要求是“/* 注釋文字 */”而不允許是“//注釋文字”:要求變量聲明必須要在函數(shù)的最前面,只能是“int i; for(i=0;i[n;i++)……”,而不允許如“for (int i=0;i[n;i++)”這樣的方式:再比如C++中函數(shù)的參數(shù)可以傳遞如“void CreateBiTree(BiTree &T)”的地址變量,但在C語(yǔ)言中,只能傳遞如“void CreateBiTree(BiTree *T)”的指針變量。因此當(dāng)你看到書(shū)中的有些代碼到處都是“*”時(shí),就用不著奇怪了。
  出于為了讓代碼可以在低端編譯環(huán)境通過(guò)的考慮,犧牲一些代碼的簡(jiǎn)捷性和優(yōu)雅性也是無(wú)可奈何和必要的。最終我將書(shū)中全部代碼都改成C90標(biāo)準(zhǔn)的代碼。
  C語(yǔ)言初學(xué)者可能會(huì)因?yàn)閯偨佑|編程語(yǔ)言,特別是對(duì)指針的理解不深,而擔(dān)心閱讀困難。我個(gè)人感覺(jué),單純學(xué)習(xí)指針是很難理解它的真正用途和好處,而通過(guò)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu),特別是像鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在各種結(jié)構(gòu)算法中的運(yùn)用,反而可以讓讀者進(jìn)一步的理解指針的優(yōu)越之處。從這個(gè)角度說(shuō),數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)可以反過(guò)來(lái)加強(qiáng)讀者對(duì)C語(yǔ)言,特別是指針概念的理解。
  編程語(yǔ)言差異
  C語(yǔ)言是一門(mén)古老的高級(jí)語(yǔ)言,它的應(yīng)用范圍非常廣泛,因此我選擇它作為本書(shū)的算法展示語(yǔ)言。如果讀者之前學(xué)過(guò)它,那么閱讀本書(shū)就不存在語(yǔ)言障礙。懂得C++語(yǔ)言的讀者,同樣也不會(huì)有任何語(yǔ)言上的問(wèn)題。
  像掌握J(rèn)ava、C#、VB等面向?qū)ο笳Z(yǔ)言的讀者,當(dāng)面對(duì)書(shū)中大量的C語(yǔ)言式的結(jié)構(gòu)(struct)聲明和針對(duì)結(jié)構(gòu)的參數(shù)傳遞的代碼時(shí),都可以理解為是類(lèi)的定義和由類(lèi)生成對(duì)象的傳遞。盡管的確存在差異,但是并不影響整體對(duì)數(shù)據(jù)結(jié)構(gòu)知識(shí)和算法原理的理解。
  我個(gè)人感覺(jué),哪怕是對(duì)C語(yǔ)言不熟悉,也不妨利用學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的機(jī)會(huì),學(xué)習(xí)一下C語(yǔ)言的編程方法,這對(duì)于將來(lái)應(yīng)用其他高級(jí)語(yǔ)言也是有很大幫助的。
  不是一個(gè)人在戰(zhàn)斗
  首先要感謝我的妻子李秀芳對(duì)我寫(xiě)作本書(shū)期間的全力支持,我辭職寫(xiě)作,沒(méi)有她精神上的理解鼓勵(lì)和生活上的悉心照顧,是不可能走出這一步并順利完成書(shū)稿的。我們的兒子程晟涵如今已經(jīng)三周歲,我是在他每日的歡聲笑語(yǔ)和哭哭啼啼中進(jìn)行每一章節(jié)的構(gòu)思和寫(xiě)作,希望他可以茁壯成長(zhǎng)。我的父母已經(jīng)年邁,他們?yōu)槲业娜殑?chuàng)作也甚為擔(dān)心和憂慮,這里也要說(shuō)一聲抱歉。
  本人數(shù)據(jù)結(jié)構(gòu)的知識(shí),是源自清華大學(xué)出版社出版的《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)》(嚴(yán)蔚敏、吳偉民編著)一書(shū),嚴(yán)老師和吳老師算是我在數(shù)據(jù)結(jié)構(gòu)方面的啟蒙老師,本書(shū)的不少內(nèi)容和代碼也是參考了此書(shū)。機(jī)械工業(yè)出版社的《算法導(dǎo)論》對(duì)于本人的算法知識(shí)提高幫助很大,寫(xiě)作中也大量吸收了書(shū)中的精華。寫(xiě)作過(guò)程中,本人購(gòu)買(mǎi)和借閱了與數(shù)據(jù)結(jié)構(gòu)相關(guān)的大量書(shū)籍,詳細(xì)書(shū)目見(jiàn)附錄。沒(méi)有前輩的貢獻(xiàn),就沒(méi)有本書(shū)的出版,也希望本書(shū)能成為這些書(shū)籍的前期讀物。在此向這些圖書(shū)作者表示衷心的感謝。
  僅有作者是不可能完成圖書(shū)的出版的,本人要非常感謝清華大學(xué)出版社的朋友們,他們是本書(shū)的最初讀者,也是協(xié)助本人將此書(shū)由毛糙變精良的最有力幫手。
  本書(shū)的封面設(shè)計(jì)程瑜、插圖設(shè)計(jì)周翔,都是在反反復(fù)復(fù)的修改中完成創(chuàng)作的。
  寫(xiě)作中,還得到了周筠、盧鶇翔、張伸、胡文佳、Milo、陳鋼、劉超、劉唯一、楊繡國(guó)、戚嫵婷、雷順、楊詩(shī)盈、高宇翔、林健的友情幫助,他們都在本人的書(shū)稿創(chuàng)作中提出了寶貴建議。
  在此向所有幫助與支持我的朋友道一聲:謝謝!
  程 杰
  
《大話數(shù)據(jù)結(jié)構(gòu)
第1章數(shù)據(jù)結(jié)構(gòu)緒論 1
1.1開(kāi)場(chǎng)白 2
如果你交給某人一個(gè)程序,你將折磨他一整天;如果你教某人如何編寫(xiě)程序,你將折磨他一輩子。
1.2你數(shù)據(jù)結(jié)構(gòu)怎么學(xué)的? 3
他完成開(kāi)發(fā)并測(cè)試通過(guò)后,得意地提交了代碼。項(xiàng)目經(jīng)理看完代碼后拍著桌子對(duì)他說(shuō):“你數(shù)據(jù)結(jié)構(gòu)是怎么學(xué)的?”
1.3數(shù)據(jù)結(jié)構(gòu)起源 4
1.4基本概念和術(shù)語(yǔ) 5
正所謂“巧婦難為無(wú)米之炊”,再?gòu)?qiáng)大的計(jì)算機(jī),也要有“米”下鍋才可以干活,否則就是一堆破銅爛鐵。這個(gè)“米”就是數(shù)據(jù)。
1.4.1數(shù)據(jù) 5
1.4.2數(shù)據(jù)元素 5
1.4.3數(shù)據(jù)項(xiàng) 6
1.4.4數(shù)據(jù)對(duì)象 6
1.4.5數(shù)據(jù)結(jié)構(gòu) 6
1.5邏輯結(jié)構(gòu)與物理結(jié)構(gòu) 7
1.5.1邏輯結(jié)構(gòu) 7
1.5.2物理結(jié)構(gòu) 9
1.6抽象數(shù)據(jù)類(lèi)型 11
大家都需要房子住,但顯然沒(méi)錢(qián)考慮大房子是沒(méi)有意義的。于是商品房就出現(xiàn)了各種各樣的戶型,有幾百平米的別墅,也有僅兩平米的膠囊公寓……
1.6.1數(shù)據(jù)類(lèi)型 11
.1.6.2抽象數(shù)據(jù)類(lèi)型 12
1.7總結(jié)回顧 14
1.8結(jié)尾語(yǔ) 15
最終的結(jié)果一定是,你對(duì)著別人很牛的說(shuō)“數(shù)據(jù)結(jié)構(gòu)——就那么回事。”
第2章算法 17
2.1開(kāi)場(chǎng)白 18
2.2數(shù)據(jù)結(jié)構(gòu)與算法關(guān)系 18
計(jì)算機(jī)界的前輩們,是一幫很牛很牛的人,他們使得很多看似沒(méi)法解決或者很難解決的問(wèn)題,變得如此美妙和神奇。
2.3兩種算法的比較 19
高斯在上小學(xué)的一天,老師要求每個(gè)學(xué)生都計(jì)算1+2+…+100的結(jié)果,誰(shuí)先算出來(lái)誰(shuí)先回家……
2.4算法定義 20
現(xiàn)實(shí)世界中的算法千變?nèi)f化,沒(méi)有通用算法可以解決所有問(wèn)題。甚至一個(gè)小問(wèn)題,某個(gè)解決此類(lèi)問(wèn)題很優(yōu)秀的算法卻未必就適合它。
2.5算法的特性 21
2.5.1輸入輸出 21
2.5.2有窮性 21
2.5.3確定性 21
2.5.4可行性 21
2.6算法設(shè)計(jì)的要求 22
求100個(gè)人的高考成績(jī)平均分與求全省所有考生的成績(jī)平均分在占用時(shí)間和內(nèi)存存儲(chǔ)上有非常大的差異,我們自然追求高效率和低存儲(chǔ)的算法來(lái)解決問(wèn)題。
2.6.1正確性 22
2.6.2可讀性 23
2.6.3健壯性 23
2.6.4時(shí)間效率高和存儲(chǔ)量低 23
2.7算法效率的度量方法 24
隨著n值越來(lái)越大,它們?cè)跁r(shí)間效率上的差異也就越來(lái)越大。好比有些人每天都在學(xué)習(xí),而另一些人,打打游戲、睡睡大覺(jué),畢業(yè)后前者名企爭(zhēng)著要,后者求職處處無(wú)門(mén)。
2.7.1事后統(tǒng)計(jì)方法 24
2.7.2事前分析估算方法 25
2.8函數(shù)的漸近增長(zhǎng) 27
2.9算法時(shí)間復(fù)雜度 29
理解大o推導(dǎo)不算難,難的其實(shí)是對(duì)數(shù)列的一些相關(guān)運(yùn)算,這考察的更多的是數(shù)學(xué)知識(shí)和能力。
2.9.1算法時(shí)間復(fù)雜度定義 29
2.9.2推導(dǎo)大o階方法 30
2.9.3常數(shù)階 30
2.9.4線性階 31
2.9.5對(duì)數(shù)階 32
2.9.6平方階 32
2.10常見(jiàn)的時(shí)間復(fù)雜度 35
有些時(shí)候,告訴你某些東西不可以去嘗試,也是一種知識(shí)的傳遞?偛荒芊且ケ欢旧咭б豢诓胖郎卟豢梢匀フ腥前伞
2.11最壞情況與平均情況 35
2.12算法空間復(fù)雜度 36
事先建立一個(gè)有2050大的數(shù)組,然后把所有年份按下標(biāo)數(shù)字對(duì)應(yīng),如果是閏年,此數(shù)組項(xiàng)的值就是1,如果不是就是0。這樣,所謂的判斷某一年是否是閏年就變成了查找這個(gè)數(shù)組的某一項(xiàng)的值是多少的問(wèn)題。
2.13總結(jié)回顧 37
2.14結(jié)尾語(yǔ) 38
愚公移山固然可敬,但發(fā)明炸藥和推土機(jī),可能更加實(shí)在和聰明。
第3章線性表 41
3.1開(kāi)場(chǎng)白 42
門(mén)外家長(zhǎng)都擠在大門(mén)口與門(mén)里的小孩子的井然有序,形成了鮮明對(duì)比。哎,有時(shí)大人的所作所為,其實(shí)還不如孩子。
3.2線性表的定義 42
3.3線性表的抽象數(shù)據(jù)類(lèi)型 45
有時(shí)我們想知道某個(gè)小朋友(比如麥兜)是否是班級(jí)的同學(xué),老師會(huì)告訴我說(shuō),沒(méi)有,麥兜是在春田花花幼兒園里。這種查找某個(gè)元素是否存在的操作很常用。
3.4線性表的順序存儲(chǔ)結(jié)構(gòu) 47
他每次一吃完早飯就沖著去了圖書(shū)館,挑一個(gè)好地兒,把他書(shū)包里的書(shū),一本一本的按座位放好,長(zhǎng)長(zhǎng)一排,九個(gè)座硬是被他占了。
3.4.1順序存儲(chǔ)定義 47
3.4.2順序存儲(chǔ)方式 47
3.4.3數(shù)據(jù)長(zhǎng)度與線性表長(zhǎng)度區(qū)別 48
3.4.4地址計(jì)算方法 49
3.5順序存儲(chǔ)結(jié)構(gòu)的插入與刪除 50
春運(yùn)時(shí)去買(mǎi)火車(chē)票,大家都排隊(duì)排著好好的,這時(shí)來(lái)了一個(gè)美女:“可否讓我排在你前面?”這可不得了,后面的人像蠕蟲(chóng)一樣,全部都得退后一步。
3.5.1獲得元素操作 50
3.5.2插入操作 51
3.5.3刪除操作 52
3.5.4線性表順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn) 54
3.6線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 55
反正也是要讓相鄰元素間留有足夠余地,那干脆所有元素都不要考慮相鄰位置了,哪有空位就到哪里。而只是讓每個(gè)元素知道它下一個(gè)元素的位置在哪里。
3.6.1順序存儲(chǔ)結(jié)構(gòu)不足的解決
辦法 55
3.6.2線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)定義 56
3.6.3頭指針與頭結(jié)點(diǎn)的異同 58
3.6.4線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)代碼描述 58
3.7單鏈表的讀取 60
3.8單鏈表的插入與刪除 61
本來(lái)是爸爸左牽著媽媽的手、右牽著寶寶的手在馬路邊散步。突然迎面走來(lái)一美女,爸爸失神般地望著,此情景被媽媽逮個(gè)正著,于是扯開(kāi)父子倆,拉起寶寶的左手就快步朝前走去。
3.8.1單鏈表的插入 61
3.8.2單鏈表的刪除 64
3.9單鏈表的整表創(chuàng)建 66
3.10單鏈表的整表刪除 69
3.11單鏈表結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)優(yōu)缺點(diǎn) 70
3.12靜態(tài)鏈表 71
對(duì)于一些語(yǔ)言,如basic、fortran等早期的編程高級(jí)語(yǔ)言,由于沒(méi)有指針,這鏈表結(jié)構(gòu),按照前面我們的講法,它就沒(méi)法實(shí)現(xiàn)了。怎么辦呢?
3.12.1靜態(tài)鏈表的插入操作 73
3.12.2靜態(tài)鏈表的刪除操作 75
3.12.3靜態(tài)鏈表優(yōu)缺點(diǎn) 77
3.13循環(huán)鏈表 78
這個(gè)輪回的思想很有意思。它強(qiáng)調(diào)了不管你今生是窮是富,如果持續(xù)行善積德,下輩子就會(huì)好過(guò),反之就會(huì)遭到報(bào)應(yīng)。
3.14雙向鏈表 81
就像每個(gè)人的人生一樣,欲收獲就得付代價(jià)。雙向鏈表既然是比單鏈表多了如可以反向遍歷查找等的數(shù)據(jù)結(jié)構(gòu),那么也就需要付出一些小的代價(jià)。
3.15總結(jié)回顧 84
3.16結(jié)尾語(yǔ) 85
如果你覺(jué)得上學(xué)讀書(shū)是受罪,假設(shè)你可以活到80歲,其實(shí)你最多也就吃了20年苦。用人生四分之一的時(shí)間來(lái)?yè)Q取其余時(shí)間的幸福生活,這點(diǎn)苦不算啥。
第4章棧與隊(duì)列 87
4.1開(kāi)場(chǎng)白 88
想想看,在你準(zhǔn)備用槍的時(shí)候,突然這手槍明明有子彈卻打不出來(lái),這不是要命嗎。
4.2棧的定義 89
類(lèi)似的很多軟件,比如word、photoshop等,都有撤消(undo)的操作,也是用棧這種思想方式來(lái)實(shí)現(xiàn)的。
4.2.1棧的定義 89
4.2.2進(jìn)棧出棧變化形式 90
4.3棧的抽象數(shù)據(jù)類(lèi)型 91
4.4棧的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 92
4.4.1棧的順序存儲(chǔ)結(jié)構(gòu) 92
4.4.2棧的順序存儲(chǔ)結(jié)構(gòu)進(jìn)棧操作 93
4.4.3棧的順序存儲(chǔ)結(jié)構(gòu)出棧操作 94
4.5兩棧共享空間 94
兩個(gè)大學(xué)室友畢業(yè)同時(shí)到北京工作,他們都希望租房時(shí)能找到獨(dú)自住的一室戶或一室一廳,可找來(lái)找去發(fā)現(xiàn),實(shí)在是承受不起。
4.6棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 97
4.6.1棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 97
4.6.2棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)進(jìn)棧操作 98
4.6.3棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)出棧操作 99
4.7棧的作用 100
4.8棧的應(yīng)用——遞歸 100
當(dāng)你往鏡子前面一站,鏡子里面就有一個(gè)你的像。但你試過(guò)兩面鏡子一起照嗎?如果a、b兩面鏡子相互面對(duì)面放著,你往中間一站,嘿,兩面鏡子里都有你的千百個(gè)“化身”。
4.8.1斐波那契數(shù)列實(shí)現(xiàn) 101
4.8.2遞歸定義 103
4.9棧的應(yīng)用——四則運(yùn)算表達(dá)式求值 104
4.9.1后綴(逆波蘭)表示法定義 104
4.9.2后綴表達(dá)式計(jì)算結(jié)果 106
4.9.3中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式 108
4.10隊(duì)列的定義 111
電腦有時(shí)會(huì)處于疑似死機(jī)的狀態(tài)。就當(dāng)你失去耐心,打算了reset時(shí)。突然它像酒醒了一樣,把你剛才點(diǎn)擊的所有操作全部都按順序執(zhí)行了一遍。
4.11隊(duì)列的抽象數(shù)據(jù)類(lèi)型 112
4.12循環(huán)隊(duì)列 113
你上了公交車(chē)發(fā)現(xiàn)前排有兩個(gè)空座位,而后排所有座位都已經(jīng)坐滿,你會(huì)怎么做?立馬下車(chē),并對(duì)自己說(shuō),后面沒(méi)座了,我等下一輛?沒(méi)這么笨的人,前面有座位,當(dāng)然也是可以坐的。
4.12.1隊(duì)列順序存儲(chǔ)的不足 112
4.12.2循環(huán)隊(duì)列定義 114
4.13隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 117
4.13.1隊(duì)列鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)入隊(duì)操作118
4.13.2隊(duì)列鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)出隊(duì)操作 119
4.14總結(jié)回顧 120
4.15結(jié)尾語(yǔ) 121
人生,需要有隊(duì)列精神的體現(xiàn)。南極到北極,不過(guò)是南緯90度到北緯90度的隊(duì)列,如果你中途猶豫,臨時(shí)轉(zhuǎn)向,也許你就只能和企鵝相伴永遠(yuǎn)?墒聦(shí)上,無(wú)論哪個(gè)方向,只要你堅(jiān)持到底,你都可以到達(dá)終點(diǎn)。
第5章串 123
5.1開(kāi)場(chǎng)白 124
“枯眼望遙山隔水,往來(lái)曾見(jiàn)幾心知?壺空怕酌一杯酒,筆下難成和韻詩(shī)。途路阻人離別久,訊音無(wú)雁寄回遲。孤燈夜守長(zhǎng)寥寂,夫憶妻兮父憶兒。”……可再仔細(xì)一讀發(fā)現(xiàn),這首詩(shī)竟然可以倒過(guò)來(lái)讀。
5.2串的定義 124
我所提到的“over”、“end”、“lie”其實(shí)就是“lover”、“friend”、“believe”這些單詞字符串的子串。
5.3串的比較 126
5.4串的抽象數(shù)據(jù)類(lèi)型 127
5.5串的存儲(chǔ)結(jié)構(gòu) 128
感情上發(fā)生了問(wèn)題,為了向女友解釋一下,我準(zhǔn)備發(fā)一條短信,一共打了75個(gè)字。最后八個(gè)字是“我恨你是不可能的”,點(diǎn)發(fā)送。后來(lái)得知對(duì)方收到的,只有70個(gè)字,短信結(jié)尾是“……我恨你”。
5.5.1串的順序存儲(chǔ)結(jié)構(gòu) 129
5.5.2串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 131
5.6樸素的模式匹配算法 131
主串為s=”00000000000000000000000000000000000000000000000001”,而要匹配的子串為t=”0000000001”,……在匹配時(shí),每次都得將t中字符循環(huán)到最后一位才發(fā)現(xiàn),哦,原來(lái)它們是不匹配的。
5.7kmp模式匹配算法 135
很多年前我們的科學(xué)家覺(jué)得像這種有多個(gè)0和1重復(fù)字符的字符串,卻需要挨個(gè)遍歷的算法,是非常糟糕的事情。
5.7.1kmp模式匹配算法原理 135
5.7.2next數(shù)組值推導(dǎo) 139
5.7.3kmp模式匹配算法實(shí)現(xiàn) 141
5.7.4kmp模式匹配算法改進(jìn) 142
5.7.5nextval數(shù)組值推導(dǎo) 144
5.8總結(jié)回顧 146
5.9結(jié)尾語(yǔ) 146
《璇璣圖》共八百四十字,縱橫各二十九字,縱、橫、斜、交互、正、反讀或退一字、迭一字讀均可成詩(shī),詩(shī)有三、四、五、六、七言不等,目前有人統(tǒng)計(jì)可組成七千九百五十八首詩(shī)。聽(tīng)清楚哦,是7958首。
第6章樹(shù) 149
6.1開(kāi)場(chǎng)白 150
無(wú)論多高多大的樹(shù),那也是從小到大的,由根到葉,一點(diǎn)點(diǎn)成長(zhǎng)起來(lái)的。俗話說(shuō)十年樹(shù)木,百年樹(shù)人,可一棵大樹(shù)又何止是十年這樣容易。
6.2樹(shù)的定義 150
樹(shù)的定義其實(shí)就是我們?cè)谥v解棧時(shí)提到的遞歸的方法。也就是在樹(shù)的定義之中還用到了樹(shù)的概念,這是比較新的一種定義方法。
6.2.1結(jié)點(diǎn)分類(lèi) 152
6.2.2結(jié)點(diǎn)間關(guān)系 152
6.2.3樹(shù)的其他相關(guān)概念 153
6.3樹(shù)的抽象數(shù)據(jù)類(lèi)型 154
6.4樹(shù)的存儲(chǔ)結(jié)構(gòu) 155
6.4.1雙親表示法 155
6.4.2孩子表示法 158
6.4.3孩子兄弟表示法 162
6.5二叉樹(shù)的定義 163
蘇東坡曾說(shuō):“人有悲歡離合,月有陰晴圓缺,此事古難全”。意思就是完美是理想,不完美才是人生。我們通常舉的例子也都是左高右低、參差不齊的二叉樹(shù)。那是否存在完美的二叉樹(shù)呢?
6.5.1二叉樹(shù)特點(diǎn) 164
6.5.2特殊二叉樹(shù) 166
6.6二叉樹(shù)的性質(zhì) 169
6.6.1二叉樹(shù)性質(zhì)1 169
6.6.2二叉樹(shù)性質(zhì)2 169
6.6.3二叉樹(shù)性質(zhì)3 169
6.6.4二叉樹(shù)性質(zhì)4 170
6.6.5二叉樹(shù)性質(zhì)5 171
6.7二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 172
6.7.1二叉樹(shù)順序存儲(chǔ)結(jié)構(gòu) 172
6.7.2二叉鏈表 173
6.8遍歷二叉樹(shù) 174
你人生的道路上,高考填志愿要面臨哪個(gè)城市、哪所大學(xué)、具體專業(yè)等選擇,由于選擇方式的不同,遍歷的次序就完全不同。
6.8.1二叉樹(shù)遍歷原理 174
6.8.2二叉樹(shù)遍歷方法 175
6.8.3前序遍歷算法 178
6.8.4中序遍歷算法 181
6.8.5后序遍歷算法 184
6.8.6推導(dǎo)遍歷結(jié)果 184
6.9二叉樹(shù)的建立 187
6.10線索二叉樹(shù) 188
我們現(xiàn)在提倡節(jié)約型社會(huì),一切都應(yīng)該節(jié)約為本。對(duì)待我們的程序當(dāng)然也不例外,能不浪費(fèi)的時(shí)間或空間,都應(yīng)該考慮節(jié)省。
6.10.1線索二叉樹(shù)原理 188
6.10.2線索二叉樹(shù)結(jié)構(gòu)實(shí)現(xiàn) 191
6.11樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換 195
有個(gè)鄉(xiāng)鎮(zhèn)企業(yè)也買(mǎi)了同樣的生產(chǎn)線,老板發(fā)現(xiàn)這個(gè)問(wèn)題后找了個(gè)小工來(lái)說(shuō):你必須搞定,不然炒你魷魚(yú)。小工很快想出了辦法:他在生產(chǎn)線旁邊放了臺(tái)風(fēng)扇猛吹,空皂盒自然會(huì)被吹走。
6.11.1樹(shù)轉(zhuǎn)換為二叉樹(shù) 196
6.11.2森林轉(zhuǎn)換為二叉樹(shù) 197
6.11.3二叉樹(shù)轉(zhuǎn)換為樹(shù) 197
6.11.4二叉樹(shù)轉(zhuǎn)換為森林 199
6.11.5樹(shù)與森林的遍歷 199
6.12赫夫曼樹(shù)及其應(yīng)用 200
壓縮而不出錯(cuò)是如何做到的呢?簡(jiǎn)單的說(shuō),就是把我們要壓縮的文本進(jìn)行重新編碼,以達(dá)到減少不必要的空間的技術(shù)。壓縮和解壓縮技術(shù)就是基于赫夫曼的研究之上發(fā)展而來(lái),我們應(yīng)該記住他。
6.12.1赫夫曼樹(shù) 200
6.12.2赫夫曼樹(shù)定義與原理 203
6.12.3赫夫曼編碼 205
6.13總結(jié)回顧 208
6.14結(jié)尾語(yǔ) 209
人受傷時(shí)會(huì)流下淚水。樹(shù)受傷時(shí),天將再不會(huì)哭。希望我們的未來(lái)不要僅僅是鋼筋水泥建造的高樓,也要有那郁郁蔥蔥的森林和草地,我們?nèi)祟?lèi)才可能與自然和諧共處。
第7章圖 211
7.1開(kāi)場(chǎng)白 212
如果你不善于規(guī)劃,很有可能就會(huì)出現(xiàn)如玩好新疆后到海南,然后再?zèng)_向黑龍江這樣的荒唐決策。
7.2圖的定義 213
現(xiàn)實(shí)中,人與人之間關(guān)系就非常復(fù)雜,比如我的認(rèn)識(shí)的朋友,可能他們之間也互相認(rèn)識(shí),這就不是簡(jiǎn)單的一對(duì)一、一對(duì)多的關(guān)系了,那就是我們今天要研究的主題——圖。
7.2.1各種圖定義 214
7.2.2圖的頂點(diǎn)與邊間關(guān)系 217
7.2.3連通圖相關(guān)術(shù)語(yǔ) 219
7.2.4圖的定義與術(shù)語(yǔ)總結(jié) 222
7.3圖的抽象數(shù)據(jù)類(lèi)型 222
7.4圖的存儲(chǔ)結(jié)構(gòu) 223
因?yàn)槊绹?guó)的黑夜就是中國(guó)的白天,利用互聯(lián)網(wǎng),他的員工白天上班就可以監(jiān)控到美國(guó)倉(cāng)庫(kù)夜間的實(shí)際情況,如果發(fā)生了像火災(zāi)、偷盜這樣的突發(fā)事件,及時(shí)電話到美國(guó)當(dāng)?shù)叵嚓P(guān)人員處理
7.4.1鄰接矩陣 224
7.4.2鄰接表 228
7.4.3十字鏈表 232
7.4.4鄰接多重表 234
7.4.5邊集數(shù)組 236
7.5圖的遍歷 237
我有一天早晨準(zhǔn)備出門(mén),發(fā)現(xiàn)鑰匙不見(jiàn)了。一定是我兒子拿著玩,不知道丟到哪個(gè)犄角旮旯去了,你們說(shuō),我應(yīng)該如何找?
7.5.1深度優(yōu)先遍歷 238
7.5.2廣度優(yōu)先遍歷 242
7.6最小生成樹(shù) 245
如果你加班加點(diǎn),沒(méi)日沒(méi)夜設(shè)計(jì)出的結(jié)果是方案一,我想你離被炒魷魚(yú)應(yīng)該是不遠(yuǎn)了(同學(xué)微笑)。因?yàn)檫@個(gè)方案比后兩個(gè)方案一半還多的成本會(huì)讓老板氣暈過(guò)去的。
7.6.1普里姆(prim)算法 247
7.6.2克魯斯卡爾(kruskal)算法 251
7.7最短路徑 257
有人為了省錢(qián),需路程最短,但換乘站間距離長(zhǎng)等原因并不省時(shí)間;另一些人,他為趕時(shí)間,最大的需求是總時(shí)間要短;還有一類(lèi)人,他們都不想多走路,關(guān)鍵是換乘要少,這樣可以在車(chē)上好好休息一下。
7.7.1迪杰斯特拉(dijkstra)算法 259
7.7.3弗洛伊德(floyd)算法 265
7.8拓?fù)渑判?270
電影制作不可能在人員到位進(jìn)駐場(chǎng)地時(shí),導(dǎo)演還沒(méi)有找到,也不可能在拍攝過(guò)程中,場(chǎng)地都沒(méi)有。這都會(huì)導(dǎo)致荒謬的結(jié)果。
7.8.1拓?fù)渑判蚪榻B 271
7.8.2拓?fù)渑判蛩惴?272
7.9關(guān)鍵路徑 277
假如造一個(gè)輪子要0.5天、造一個(gè)發(fā)動(dòng)機(jī)要3天、造一個(gè)車(chē)底盤(pán)要2天、造一個(gè)外殼要2天,其它零部件2天,全部零部件集中到一處要0.5天,組裝成車(chē)要2天,請(qǐng)問(wèn),在汽車(chē)廠造一輛車(chē),最短需要多少天呢?
7.9.1關(guān)鍵路徑算法原理 279
7.9.2關(guān)鍵路徑算法 280
7.10總結(jié)回顧 287
7.11結(jié)尾語(yǔ) 289
世界上最遙遠(yuǎn)的距離,不是牛a與牛c之間狹小空隙,而是你們當(dāng)中,有人在通往牛逼的路上一路狂奔,而有人步入大學(xué)校園就學(xué)會(huì)放棄。
第8章查找 291
8.1開(kāi)場(chǎng)白 292
當(dāng)你精心寫(xiě)了一篇博文或者上傳一組照片到互聯(lián)網(wǎng)上,來(lái)自世界各地的無(wú)數(shù)“蜘蛛”便會(huì)蜂擁而至。所謂蜘蛛就是搜索引擎公司服務(wù)器上軟件,它把互聯(lián)網(wǎng)當(dāng)成了蜘蛛網(wǎng),沒(méi)日沒(méi)夜的訪問(wèn)上面的各種信息。
8.2查找概論 293
比如網(wǎng)絡(luò)時(shí)代的新名詞,如“蝸居”、“蟻?zhàn)?rdquo;等,如果需要將它們收錄到漢語(yǔ)詞典中,顯然收錄時(shí)就需要查找它們是否存在,以及找到如果不存在時(shí)應(yīng)該收錄的位置。
8.3順序表查找 295
8.3.1順序表查找算法 296
8.3.2順序表查找優(yōu)化 297
8.4有序表查找 298
我在紙上已經(jīng)寫(xiě)好了一個(gè)100以內(nèi)的正整數(shù)請(qǐng)你猜,問(wèn)幾次可以猜出來(lái)。當(dāng)時(shí)已經(jīng)介紹了如何才可以最快的猜出這個(gè)數(shù)字。我們把這種每次取中間記錄查找的方法叫做折半查找。
8.4.1折半查找 298
8.4.2插值查找 301
8.4.3斐波那契查找 302
8.5線性索引查找 306
我母親年紀(jì)大了,經(jīng)常在家里找不到東西,,于是她用一小本子,記錄了家里所有小東西放置的位置,比如戶口本放在右手床頭柜下面抽屜中,鈔票放在衣……咳,這個(gè)就不提了。
8.5.1稠密索引 307
8.5.2分塊索引 308
8.5.3倒排索引 311
8.6二叉排序樹(shù) 313
后來(lái)老虎來(lái)了,一人拼命地跑,另一人則急中生智,爬到了樹(shù)上。而老虎是不會(huì)爬樹(shù)的,結(jié)果……。爬樹(shù)者改變了跑的思想,這一改變何等重要,撿回了自己的一條命。
8.6.1二叉排序樹(shù)查找操作 316
8.6.2二叉排序樹(shù)插入操作 318
8.6.3二叉排序樹(shù)刪除操作 320
8.6.4二叉排序樹(shù)總結(jié) 327
8.7平衡二叉樹(shù)(avl樹(shù)) 328
平板就是一個(gè)世界,當(dāng)誘惑降臨,人心中的平衡被打破,世界就會(huì)混亂,最后留下的只有孤獨(dú)寂寞失敗。這種單調(diào)的機(jī)械化的社會(huì),禁不住誘惑的侵蝕,最容易被侵蝕的,恰恰是最空虛的心靈。
8.7.1平衡二叉樹(shù)實(shí)現(xiàn)原理 330
8.7.2平衡二叉樹(shù)實(shí)現(xiàn)算法 334
8.8多路查找樹(shù)(b樹(shù)) 341
要觀察一個(gè)公司是否嚴(yán)謹(jǐn),看他們?nèi)绾伍_(kāi)會(huì)就知道了。如果開(kāi)會(huì)時(shí)每一個(gè)人都只是帶一張嘴,即興發(fā)言,這肯定是一家不嚴(yán)謹(jǐn)?shù)墓尽?
8.8.12-3樹(shù) 343
8.8.22-3-4樹(shù) 348
8.8.3b樹(shù) 349
8.8.4b+樹(shù) 351
8.9散列表查找(哈希表)概述 353
你很想學(xué)太極拳,聽(tīng)說(shuō)學(xué)校有個(gè)叫張三豐的人打得特別好,于是到學(xué)校學(xué)生處找人,工作人員拿出學(xué)生名單,最終告訴你,學(xué)校沒(méi)這個(gè)人,并說(shuō)張三豐幾百年前就已經(jīng)在武當(dāng)山作古了。
8.9.1散列表查找定義 354
8.9.2散列表查找步驟 355
8.10散列函數(shù)的構(gòu)造方法 356
8.10.1直接定址法 357
8.10.2數(shù)字分析法 358
8.10.3平方取中法 359
8.10.4折疊法 359
8.10.5除留余數(shù)法 359
8.10.6隨機(jī)數(shù)法 360
8.11處理散列沖突的方法 360
我們每個(gè)人都希望身體健康,雖然疾病可以預(yù)防,但不可避免,沒(méi)有任何人可以說(shuō),生下來(lái)到現(xiàn)在沒(méi)有生過(guò)一次病。
8.11.1開(kāi)放定址法 361
8.11.2再散列函數(shù)法 363
8.11.3鏈地址法 363
8.11.4公共溢出區(qū)法 364
8.12散列表查找實(shí)現(xiàn) 365
8.12.1散列表查找算法實(shí)現(xiàn) 365
8.12.2散列表查找性能分析 367
8.13總結(jié)回顧 368
8.14結(jié)尾語(yǔ) 369
如果我是個(gè)喜歡汽車(chē)的人,時(shí)常搜汽車(chē)信息。那么當(dāng)我在搜索框中輸入“甲殼蟲(chóng)”、“美洲虎”等關(guān)鍵詞時(shí),不要讓動(dòng)物和人物成為搜索的頭條。
第9章排序 373
9.1開(kāi)場(chǎng)白 374
假如我想買(mǎi)一臺(tái)iphone4的手機(jī),于是上了某電子商務(wù)網(wǎng)站去搜索。可搜索后發(fā)現(xiàn),有8863個(gè)相關(guān)的物品,如此之多,這叫我如何選擇。我其實(shí)是想買(mǎi)便宜一點(diǎn)的,但是又怕遇到騙子,想找信譽(yù)好的商家,如何做?
9.2排序的基本概念與分類(lèi) 375
比如我們某些大學(xué)為了選拔在主科上更優(yōu)秀的學(xué)生,要求對(duì)所有學(xué)生的所有科目總分倒序排名,并且在同樣總分的情況下將語(yǔ)數(shù)外總分做倒序排名。這就是對(duì)總分和語(yǔ)數(shù)外總分兩個(gè)次關(guān)鍵字的組合排序。
9.2.1排序的穩(wěn)定性 376
9.2.2內(nèi)排序與外排序 377
9.2.3排序用到的結(jié)構(gòu)與函數(shù) 378
9.3冒泡排序 378
無(wú)論你學(xué)習(xí)哪種編程語(yǔ)言,在學(xué)到循環(huán)和數(shù)組時(shí),通常都會(huì)介紹一種排序算法,而這個(gè)算法一般就是冒泡排序。并不是它的名稱很好聽(tīng),而是說(shuō)這個(gè)算法的思路最簡(jiǎn)單,最容易理解。
9.3.1最簡(jiǎn)單排序?qū)崿F(xiàn) 379
9.3.2冒泡排序算法 380
9.3.3冒泡排序優(yōu)化 382
9.3.4冒泡排序復(fù)雜度分析 383
9.4簡(jiǎn)單選擇排序 384
還有一種做股票的人,他們很少出手,只是在不斷觀察和判斷,等時(shí)機(jī)一到,果斷買(mǎi)進(jìn)或賣(mài)出。他們因?yàn)槔潇o和沉著,以及交易的次數(shù)少,而最終收益頗豐。
9.4.1簡(jiǎn)單選擇排序算法 384
9.4.2簡(jiǎn)單選擇排序復(fù)雜度分析 385
9.5直接插入排序 386
哪怕你是第一次玩撲克牌,只要認(rèn)識(shí)這些數(shù)字,理牌的方法都是不用教的。將3和4移動(dòng)到5的左側(cè),再將2移動(dòng)到最左側(cè),順序就算是理好了。這里,我們的理牌方法,就是直接插入排序法。
9.5.1直接插入排序算法 386
9.5.2直接插入排序復(fù)雜度分析 388
9.6希爾排序 389
不管怎么說(shuō),希爾排序算法的發(fā)明,使得我們終于突破了慢速排序的時(shí)代(超越了時(shí)間復(fù)雜度為o(n2)),之后,更為高效的排序算法也就相繼出現(xiàn)了。
9.6.1希爾排序原理 391
9.6.2希爾排序算法 391
9.6.3希爾排序復(fù)雜度分析 395
9.7堆排序 396
什么叫堆結(jié)構(gòu)呢?回憶一下我們小時(shí)候,特別是男同學(xué),基本都玩過(guò)疊羅漢的惡作劇。通常都是先把某個(gè)要整的人按倒在地,然后大家就一擁而上撲了上去……后果?后果當(dāng)然就是一笑了之。
9.7.1堆排序算法 398
9.7.2堆排序復(fù)雜度分析 405
9.8歸并排序 406
即使你是你們班級(jí)第一、甚至年級(jí)第一名,如果你沒(méi)有上分?jǐn)?shù)線,則說(shuō)明你的成績(jī)排不到全省前1萬(wàn)名,你也就基本失去了當(dāng)年上本科的機(jī)會(huì)了。
9.8.1歸并排序算法 407
9.8.2歸并排序復(fù)雜度分析 413
9.8.3非遞歸實(shí)現(xiàn)歸并排序 413
9.9快速排序 417
終于我們的高手要登場(chǎng)了,將來(lái)你工作后,你的老板讓你寫(xiě)個(gè)排序算法,而你會(huì)的算法中竟然沒(méi)有快速排序,我想你還是不要聲張,偷偷去把快速排序算法找來(lái)敲進(jìn)電腦,這樣至少你不至于被大伙兒取笑。
9.9.1快速排序算法 417
9.9.2快速排序復(fù)雜度分析 421
9.9.3快速排序優(yōu)化 422
9.10總結(jié)回顧 428
目前還沒(méi)有十全十美的排序算法,有優(yōu)點(diǎn)就會(huì)有缺點(diǎn),即使是快速排序法,也只是在整體性能上優(yōu)越,它也存在排序不穩(wěn)定、需要大量輔助空間、對(duì)少量數(shù)據(jù)排序無(wú)優(yōu)勢(shì)等不足。
9.11結(jié)尾語(yǔ) 430
如果你有夢(mèng)想的話,就要去捍衛(wèi)它。當(dāng)別人做不到的時(shí)候,他們就想要告訴你,你也不能。如果你想要些什么,就得去努力爭(zhēng)取。就這樣!
附錄參考文獻(xiàn) 435



本文編號(hào):1332938

資料下載
論文發(fā)表

本文鏈接:http://sikaile.net/wenshubaike/dxkc/1332938.html


Copyright(c)文論論文網(wǎng)All Rights Reserved | 網(wǎng)站地圖 |

版權(quán)申明:資料由用戶b7d5e***提供,本站僅收錄摘要或目錄,作者需要?jiǎng)h除請(qǐng)E-mail郵箱bigeng88@qq.com