簡明易懂的算法及數(shù)據(jù)結(jié)構(gòu)

算法及數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)算法是對一系列數(shù)據(jù)進行處理，得到最終結(jié)果。一系列數(shù)據(jù)的組織形式，對算法的設(shè)計和實現(xiàn)有著很大的影響。數(shù)據(jù)結(jié)構(gòu)一系列數(shù)據(jù)的組織形式學(xué)習(xí)一些重要的、常見的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的分類線性結(jié)構(gòu)數(shù)據(jù)是一個接著一個，數(shù)據(jù)間只有0或1個前置和0或1個后續(xù)常見的數(shù)據(jù)結(jié)構(gòu)包括：數(shù)組、線性表、棧和隊列非線性結(jié)構(gòu)數(shù)據(jù)間的關(guān)系比較多樣，數(shù)據(jù)間可以有0或多個前置和0或多個后續(xù)常見的數(shù)據(jù)結(jié)構(gòu)包括：樹和圖數(shù)據(jù)結(jié)構(gòu)的操作數(shù)據(jù)結(jié)構(gòu)的操作對數(shù)據(jù)結(jié)構(gòu)中那一系列數(shù)據(jù)進行管理的行為根本的操作添加數(shù)據(jù)刪除數(shù)據(jù)修改數(shù)據(jù)遍歷所有數(shù)據(jù)查找指定數(shù)據(jù)的位置或節(jié)點對于不同的數(shù)據(jù)結(jié)構(gòu)，還有和它們自身相關(guān)的一些操作數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)形式數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)方法主要有兩種使用數(shù)組實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，稱為“順序?qū)崿F(xiàn)〞使用引用特性實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，稱為“鏈式實現(xiàn)〞“鏈式〞數(shù)據(jù)結(jié)構(gòu)的兩局部數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)一般分為兩局部數(shù)據(jù)節(jié)點〔Node〕：用來存放信息，包括：實際的數(shù)據(jù)引用相關(guān)數(shù)據(jù)節(jié)點〔Node〕的變量節(jié)點管理〔Manager〕：用來管理所有的數(shù)據(jù)節(jié)點，維護它們之間的引用關(guān)系數(shù)據(jù)結(jié)構(gòu)的操作在節(jié)點管理里面實現(xiàn)命名，假設(shè)數(shù)據(jù)結(jié)構(gòu)的名稱為XXX數(shù)據(jù)節(jié)點：XXXNode節(jié)點管理：XXX“鏈式〞數(shù)據(jù)結(jié)構(gòu)的圖示我們會采用圖示的方式來描述數(shù)據(jù)結(jié)構(gòu)直觀，便于討論溝通數(shù)據(jù)節(jié)點

Node實際數(shù)據(jù)引用變量節(jié)點間的引用關(guān)系已存在或新建準備刪除“鏈式〞數(shù)據(jù)結(jié)構(gòu)圖示的例如“你”Next“們”Next“好”Next“你”Next“們”Next“好”Next你們好你好“鏈式〞數(shù)據(jù)結(jié)構(gòu)圖示的例如“祖父”父親兒子“伯父”父親兒子“父親”父親兒子“叔叔”父親兒子“表兄”父親兒子“你”父親兒子族譜線性表線性結(jié)構(gòu)線性結(jié)構(gòu)是數(shù)據(jù)有次序集合的一類數(shù)據(jù)結(jié)構(gòu)特點：必然存在唯一的一個“第一元素〞必然存在唯一的一個“最后元素〞除最后元素外，均有唯一的后續(xù)除第一元素外，均有唯一的前驅(qū)線性結(jié)構(gòu)的分類根據(jù)實現(xiàn)手段區(qū)分使用數(shù)組實現(xiàn)——順序線性結(jié)構(gòu)使用引用實現(xiàn)——鏈式線性結(jié)構(gòu)根據(jù)線性結(jié)構(gòu)中元素的訪問限制無任何限制——線性表有訪問限制——棧和隊列線性表的操作——元素操作添加：Add在線性表最后添加元素插入：Insert在線性表中間指定的位置添加元素移除：RemoveAt把線性表中指定位置的元素從線性表中移去注意：被移除的元素只是在線性表中不存在，但并不沒有消失替換：Replace替換線性表中指定位置的元素清空線性表：Clear把線性表中所有元素清空線性表的操作——元素信息獲?。篏etByIndex獲取線性表中指定位置的元素從前查找：IndexOf從線性表中第一元素開始，獲取符合條件的元素所在的位置從后查找：LastIndexOf從線性表中最后元素開始，獲取符合條件的元素所在的位置獲取數(shù)量：Count獲取線性表中所有元素的數(shù)量數(shù)據(jù)結(jié)構(gòu)的元素遍歷獲取當(dāng)前元素：GetCurrent獲取當(dāng)前所指向的元素移動到下一個元素：MoveNext移動到下一個元素返回值為bool，如果有下一個元素，返回true，否那么，返回false。重置：Reset重新指向第一個元素單向鏈表LinkNodeLink雙向鏈表DoubleLinkNodeDoubleLink單向循環(huán)鏈表LinkNodeLink算法與窮舉法什么是算法算法對特定問題求解步驟的一種描述計算機算法使用計算機指令實現(xiàn)算法所描述的步驟，令到計算機解決特定的問題計算機算法的描述形式自然語言描述算法框圖描述偽代碼描述類似于編程代碼，但忽略編程語言中一些嚴格的語法規(guī)那么與細節(jié)目的在于描述算法計算機算法的特性輸入性有些算法好似沒有輸入量，實際上是輸入量已被嵌入到算法中輸出性有些算法好似沒有輸出結(jié)果，實際上是算法中已經(jīng)對外部產(chǎn)生影響確定性相同的輸入，得到的輸出也是相同的有窮性算法在有限步驟下結(jié)束，每個步驟在有限時間內(nèi)完成可行性算法能夠被現(xiàn)有的計算機技術(shù)實現(xiàn)算法的優(yōu)劣依據(jù)同一個問題，可能存在多種算法判斷算法優(yōu)劣標準正確性可讀性易于人的閱讀和理解健壯性具備檢查錯誤和對錯誤進行適當(dāng)處理的能力效率運行時間——時間復(fù)雜度內(nèi)存占用——空間復(fù)雜度什么是窮舉法逐一嘗試所有可能的解利用計算機的高速度和不知疲倦的特性通過判斷是否與條件矛盾來確定其是否為問題的解什么情況下適用窮舉法對問題求解毫無頭緒的情況下問題是可以必須預(yù)先確定可能解的個數(shù)，或可能解的取值范圍窮舉法較為費時窮舉法步驟確定可能解的取值范圍遍歷所有可能解根據(jù)條件，判斷該可能解是否符合題目要求窮舉法例子1問題：求整數(shù)數(shù)組A[0:N-1]中的最小值。窮舉法思路：解的范圍就是數(shù)組中的所有元素假設(shè)其中一個是最小值用其他所有元素與“最小值〞比較，如果更新小，那么更換最小值窮舉法例子2問題：有N個硬幣，其中一個是假幣。所有真幣的重量一樣，而假幣與真幣重量不一樣?，F(xiàn)有一個精確天平，但沒有砝碼。利用該天平找出假幣。用整型數(shù)組表示所有硬幣的重量，顯示假幣的位置，并說明假幣比真幣重還是輕。窮舉法思路：解的范圍就是數(shù)組中的所有硬幣進行兩兩比較如果硬幣重量一樣，那么都是真幣如果硬幣重量不一樣，那么其中一個是硬幣。此時需要和其他組別的硬幣比較，判斷哪個是真幣。注意N為奇數(shù)的情況窮舉法例子3問題：密碼組合。密碼由26個英文字母組成，大小寫不區(qū)分。長度可以是1-4個字符。顯示所有可能的密碼組合。提示：26個英文字母可以放在一個字符數(shù)組里面多個字符的情況可以使用多重循環(huán)窮舉法例子4問題：眾數(shù)查找。在一個由假設(shè)干元素組成的數(shù)組中，出現(xiàn)次數(shù)最多的元素稱為眾數(shù)。如果有多個元素的出現(xiàn)次數(shù)一樣，第一個出現(xiàn)的元素才是眾數(shù)。尋找元素是整數(shù)類型的數(shù)組中的眾數(shù)。窮舉法例子5問題：求滿足如下兩個性質(zhì)的最小自然數(shù)n：a) n的個位數(shù)是6；b)假設(shè)將n的個位數(shù)移到其余各位數(shù)字之前，所得的新數(shù)是n的4倍。提示：該數(shù)值為：153846窮舉法例子6問題：Ａ、Ｂ、Ｃ、Ｄ、Ｅ五名學(xué)生有可能參加計算機競賽，根據(jù)以下條件判斷哪些人參加了競賽：

a) Ａ參加時，Ｂ也參加；

b) Ｂ和Ｃ只有一個人參加；

c) Ｃ和Ｄ或者都參加，或者都不參加；

d) Ｄ和Ｅ中至少有一個人參加；

e) 如果Ｅ參加，那么Ａ和Ｄ也都參加。提示：參加的情況是：A=False,B=False,C=True,D=True,E=False滾雪球法什么是滾雪球法也稱為迭代法——數(shù)學(xué)求解對一個的根底解，經(jīng)過有限次的加工處理，令根底解變?yōu)樽罱K解。什么情況下適用滾雪球法可以從問題中，確定一個根底解令根底解轉(zhuǎn)變?yōu)樽罱K解的一系列加工處理方法，可以重復(fù)進行加工處理方式是確定的加工處理的次數(shù)是確定的滾雪球法步驟確定一個根底解重復(fù)進行加工處理根據(jù)情況，選擇適宜的加工處理的方法把〔加工后〕根底解作為加工處理方法的輸入加工處理方法輸出新的加工后根底解加工完成加工后的根底解就是最終解加工次數(shù)到達界限滾雪球例子1問題：猴子第一天摘下假設(shè)干桃子，當(dāng)即吃下一半多一個。以后每天都吃前一天剩下的一半多一個。經(jīng)過N天，只剩下1個桃子。問猴子第一天所摘桃子的數(shù)量。滾雪球法思路：根底解是怎樣的加工的步驟如何滾雪球例子2問題：如果一對兔子每月里能生出一對小兔〔一雌一雄〕，而每對小兔在它們出生后的第三個月里，又能生出一對小兔。假定不發(fā)生死亡的情況下，由一對初生的小兔開始，n個月后會有多少對兔子？滾雪球法思路：根底解是怎樣的加工的步驟如何遞歸法什么是遞歸法遞歸方法直接或間接調(diào)用自身相似問題結(jié)構(gòu)相同但規(guī)模不一樣的問題什么情況下適用遞歸法可以從題目中，把原問題轉(zhuǎn)化為對相似問題的調(diào)用可以從題目中，找出能獲取根底解的相似問題的規(guī)模遞歸法的兩個過程遞推：問題分解，直至能獲取根底解回歸：根底解構(gòu)成最終解遞歸法步驟確定根底解獲取的條件構(gòu)造相似問題的算法輸入——不同規(guī)模問題的輸入量不一樣對輸入做相似的處理調(diào)用自身，設(shè)置新的輸入對自身調(diào)用后的輸出，做進一步加工輸出調(diào)用算法，使用最大規(guī)模的輸入量遞歸例子1問題：如果一對兔子每月里能生出一對小兔〔一雌一雄〕，而每對小兔在它們出生后的第三個月里，又能生出一對小兔。假定不發(fā)生死亡的情況下，由一對初生的小兔開始，n個月后會有多少對兔子？遞歸法思路：根底解是怎樣的相似問題的處理：本月的數(shù)量=上月的數(shù)量+新出生的數(shù)量=上月的數(shù)量+上月三月大的數(shù)量+上月二月大的數(shù)量=上月的數(shù)量+(上上月三月大+上上月二月大〕的數(shù)量+上上月初生的數(shù)量=上月的數(shù)量+上上月的數(shù)量遞歸例子2問題：有三個柱子，柱A上有m個大小不一的盤子，并且小盤子在大盤子上面，現(xiàn)要求將盤子從A柱上，利用B柱，全部移到C柱。要求：小盤子在任何時候都必須在大盤子上面?！矟h諾塔問題〕遞歸法思路：根底解是怎樣的相似問題的處理步驟分治法什么是分治法相似問題結(jié)構(gòu)相同但規(guī)模不一樣的問題對原問題分解為多個小規(guī)模問題小規(guī)模問題的解合并后得出最終解小規(guī)模問題可以遞歸求解什么情況下適用分治法可以從題目中，把原問題分解為多個相似問題的求解可以從題目中，找出能獲取根底解的相似問題的規(guī)模分治法是對遞歸法的擴展遞歸法：原問題縮小為一個小規(guī)模問題分治法：原問題分解為多個小規(guī)模問題分治法步驟確定根底解獲取的條件分解問題為多個小問題解決每個小問題，如果不能直接解決，那么進行遞歸求解合并所有小問題的解分治法例子1