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

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

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

a) Ａ參加時(shí)，Ｂ也參加；

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

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

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

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