算法設(shè)計(jì)基本方法及其基本思想(數(shù)據(jù)結(jié)構(gòu)的基本方法是怎樣的)

1.數(shù)據(jù)結(jié)構(gòu)的基本方法是怎樣的

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。

數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來(lái)更高的運(yùn)行或者存儲(chǔ)效率。

數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。算法的設(shè)計(jì)取決于數(shù)據(jù)（邏輯）結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于采用的存儲(chǔ)結(jié)構(gòu)。

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)實(shí)質(zhì)上是它的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的實(shí)現(xiàn)，為了全面的反映一個(gè)數(shù)據(jù)的邏輯結(jié)構(gòu)，它在存儲(chǔ)器中的映象包括兩方面內(nèi)容，即數(shù)據(jù)元素之間的信息和數(shù)據(jù)元素之間的關(guān)系。不同數(shù)據(jù)結(jié)構(gòu)有其相應(yīng)的若干運(yùn)算。

數(shù)據(jù)的運(yùn)算是在數(shù)據(jù)的邏輯結(jié)構(gòu)上定義的操作算法，如檢索、插入、刪除、更新和排序等。數(shù)據(jù)的運(yùn)算是數(shù)據(jù)結(jié)構(gòu)的一個(gè)重要方面，討論任一種數(shù)據(jù)結(jié)構(gòu)時(shí)都離不開(kāi)對(duì)該結(jié)構(gòu)上的數(shù)據(jù)運(yùn)算及其實(shí)現(xiàn)算法的討論。

數(shù)據(jù)結(jié)構(gòu)不同于數(shù)據(jù)類型，也不同于數(shù)據(jù)對(duì)象，它不僅要描述數(shù)據(jù)類型的數(shù)據(jù)對(duì)象，而且要描述數(shù)據(jù)對(duì)象各元素之間的相互關(guān)系。數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。

數(shù)據(jù)類型可分為兩類：原子類型、結(jié)構(gòu)類型。一方面，在程序設(shè)計(jì)語(yǔ)言中，每一個(gè)數(shù)據(jù)都屬于某種數(shù)據(jù)類型。

類型明顯或隱含地規(guī)定了數(shù)據(jù)的取值范圍、存儲(chǔ)方式以及允許進(jìn)行的運(yùn)算。可以認(rèn)為，數(shù)據(jù)類型是在程序設(shè)計(jì)中已經(jīng)實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)。

另一方面，在程序設(shè)計(jì)過(guò)程中，當(dāng)需要引入某種新的數(shù)據(jù)結(jié)構(gòu)時(shí)，總是借助編程語(yǔ)言所提供的數(shù)據(jù)類型來(lái)描述數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。計(jì)算機(jī)中表示數(shù)據(jù)的最小單位是二進(jìn)制數(shù)的一位，叫做位。

我們用一個(gè)由若干位組合起來(lái)形成的一個(gè)位串表示一個(gè)數(shù)據(jù)元素，通常稱這個(gè)位串為元素或結(jié)點(diǎn)。當(dāng)數(shù)據(jù)元素由若干數(shù)據(jù)項(xiàng)組成時(shí)，位串中對(duì)應(yīng)于各個(gè)數(shù)據(jù)項(xiàng)的子位串稱為數(shù)據(jù)域。

元素或結(jié)點(diǎn)可看成是數(shù)據(jù)元素在計(jì)算機(jī)中的映象。一個(gè)軟件系統(tǒng)框架應(yīng)建立在數(shù)據(jù)之上，而不是建立在操作之上。

一個(gè)含抽象數(shù)據(jù)類型的軟件模塊應(yīng)包含定義、表示、實(shí)現(xiàn)三個(gè)部分。對(duì)每一個(gè)數(shù)據(jù)結(jié)構(gòu)而言，必定存在與它密切相關(guān)的一組操作。

若操作的種類和數(shù)目不同，即使邏輯結(jié)構(gòu)相同，數(shù)據(jù)結(jié)構(gòu)能起的作用也不同。不同的數(shù)據(jù)結(jié)構(gòu)其操作集不同，但下列操作必不可缺：1，結(jié)構(gòu)的生成；2.結(jié)構(gòu)的銷毀；3，在結(jié)構(gòu)中查找滿足規(guī)定條件的數(shù)據(jù)元素；4，在結(jié)構(gòu)中插入新的數(shù)據(jù)元素；5，刪除結(jié)構(gòu)中已經(jīng)存在的數(shù)據(jù)元素；6，遍歷。

抽象數(shù)據(jù)類型：一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型實(shí)際上就是對(duì)該數(shù)據(jù)結(jié)構(gòu)的定義。

因?yàn)樗x了一個(gè)數(shù)據(jù)的邏輯結(jié)構(gòu)以及在此結(jié)構(gòu)上的一組算法。抽象數(shù)據(jù)類型可用以下三元組表示：（D,S,P）。

D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的基本操作集。ADT的定義為：ADT 抽象數(shù)據(jù)類型名：{數(shù)據(jù)對(duì)象：（數(shù)據(jù)元素集合），數(shù)據(jù)關(guān)系：（數(shù)據(jù)關(guān)系二元組結(jié)合），基本操作：（操作函數(shù)的羅列）}； ADT抽象數(shù)據(jù)類型名；抽象數(shù)據(jù)類型有兩個(gè)重要特性：數(shù)據(jù)抽象 用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）。

數(shù)據(jù)封裝 將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。數(shù)據(jù)（Data）是信息的載體，它能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。

它是計(jì)算機(jī)程序加工的原料，應(yīng)用程序處理各種各樣的數(shù)據(jù)。計(jì)算機(jī)科學(xué)中，所謂數(shù)據(jù)就是計(jì)算機(jī)加工處理的對(duì)象，它可以是數(shù)值數(shù)據(jù)，也可以是非數(shù)值數(shù)據(jù)。

數(shù)值數(shù)據(jù)是一些整數(shù)、實(shí)數(shù)或復(fù)數(shù)，主要用于工程計(jì)算、科學(xué)計(jì)算和商務(wù)處理等；非數(shù)值數(shù)據(jù)包括字符、文字、圖形、圖像、語(yǔ)音等。數(shù)據(jù)元素（Data Element）是數(shù)據(jù)的基本單位。

在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等。例如，學(xué)生信息檢索系統(tǒng)中學(xué)生信息表中的一個(gè)記錄等，都被稱為一個(gè)數(shù)據(jù)元素。

有時(shí)，一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)（Data Item）組成，例如，學(xué)籍管理系統(tǒng)中學(xué)生信息表的每一個(gè)數(shù)據(jù)元素就是一個(gè)學(xué)生記錄。它包括學(xué)生的學(xué)號(hào)、姓名、性別、籍貫、出生年月、成績(jī)等數(shù)據(jù)項(xiàng)。

這些數(shù)據(jù)項(xiàng)可以分為兩種：一種叫做初等項(xiàng)，如學(xué)生的性別、籍貫等，這些數(shù)據(jù)項(xiàng)是在數(shù)據(jù)處理時(shí)不能再分割的最小單位；另一種叫做組合項(xiàng)，如學(xué)生的成績(jī)，它可以再劃分為數(shù)學(xué)、物理、化學(xué)等更小的項(xiàng)。通常，在解決實(shí)際應(yīng)用問(wèn)題時(shí)是把每個(gè)學(xué)生記錄當(dāng)作一個(gè)基本單位進(jìn)行訪問(wèn)和處理的。

數(shù)據(jù)對(duì)象（Data Object）或數(shù)據(jù)元素類（Data Element Class）是具有相同性質(zhì)的數(shù)據(jù)元素的集合。在某個(gè)具體問(wèn)題中，數(shù)據(jù)元素都具有相同的性質(zhì)（元素值不一定相等），屬于同一數(shù)據(jù)對(duì)象（數(shù)據(jù)元素類），數(shù)據(jù)元素是數(shù)據(jù)元素類的一個(gè)實(shí)例。

例如，在交通咨詢系統(tǒng)的交通網(wǎng)中，所有的頂點(diǎn)是一個(gè)數(shù)據(jù)元素類，頂點(diǎn)A和頂點(diǎn)B各自代表一個(gè)城市，是該數(shù)據(jù)元素類中的兩個(gè)實(shí)例，其數(shù)據(jù)元素的值分別為A和B。 數(shù)據(jù)結(jié)構(gòu)（Data Structure）是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。

在任何問(wèn)題中，數(shù)據(jù)元素之間都不會(huì)是孤立的，在它們之間都存在著這樣或那樣的關(guān)系，這種數(shù)據(jù)元素之間的關(guān)系稱為結(jié)構(gòu)。

2.算法的實(shí)現(xiàn)方法有幾種

但是可以分類。

以下是我查到的資料

算法可大致分為基本算法、數(shù)據(jù)結(jié)構(gòu)的算法、數(shù)論與代數(shù)算法、計(jì)算幾何的算法、圖論的算法、動(dòng)態(tài)規(guī)劃以及數(shù)值分析、加密算法、排序算法、檢索算法、隨機(jī)化算法、并行算法。

算法可以宏泛的分為三類：

有限的，確定性算法 這類算法在有限的一段時(shí)間內(nèi)終止。他們可能要花很長(zhǎng)時(shí)間來(lái)執(zhí)行指定的任務(wù)，但仍將在一定的時(shí)間內(nèi)終止。這類算法得出的結(jié)果常取決于輸入值。

有限的，非確定算法 這類算法在有限的時(shí)間內(nèi)終止。然而，對(duì)于一個(gè)（或一些）給定的數(shù)值，算法的結(jié)果并不是唯一的或確定的。

無(wú)限的算法 是那些由于沒(méi)有定義終止定義條件，或定義的條件無(wú)法由輸入的數(shù)據(jù)滿足而不終止運(yùn)行的算法。通常，無(wú)限算法的產(chǎn)生是由于未能確定的定義終止條件。

算法設(shè)計(jì)與分析的基本方法 1.遞推法

2.遞歸遞歸指的是一個(gè)過(guò)程：函數(shù)不斷引用自身，直到引用的對(duì)象已知

3.窮舉搜索法

窮舉搜索法是對(duì)可能是解的眾多候選解按某種順序進(jìn)行逐一枚舉和檢驗(yàn)，并從眾找出那些符合要求的候選解作為問(wèn)題的解。

4.貪婪法貪婪法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因?yàn)樗∪チ藶檎易顑?yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間。貪婪法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。

5.分治法把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的相同或相似的子問(wèn)題，再把子問(wèn)題分成更小的子問(wèn)題……直到最后子問(wèn)題可以簡(jiǎn)單的直接求解，原問(wèn)題的解即子問(wèn)題的解的合并。

6.動(dòng)態(tài)規(guī)劃法

動(dòng)態(tài)規(guī)劃是一種在數(shù)學(xué)和計(jì)算機(jī)科學(xué)中使用的，用于求解包含重疊子問(wèn)題的最優(yōu)化問(wèn)題的方法。其基本思想是，將原問(wèn)題分解為相似的子問(wèn)題，在求解的過(guò)程中通過(guò)子問(wèn)題的解求出原問(wèn)題的解。動(dòng)態(tài)規(guī)劃的思想是多種算法的基礎(chǔ)，被廣泛應(yīng)用于計(jì)算機(jī)科學(xué)和工程領(lǐng)域。

7.迭代法迭代是數(shù)值分析中通過(guò)從一個(gè)初始估計(jì)出發(fā)尋找一系列近似解來(lái)解決問(wèn)題（一般是解方程或者方程組）的過(guò)程，為實(shí)現(xiàn)這一過(guò)程所使用的方法統(tǒng)稱為迭代法。

3.各算法策略中包含了哪些計(jì)算思維的思想方法

算法策略就是在問(wèn)題空間中隨機(jī)搜索所有可能的解決問(wèn)題的方法，直至選擇一種有效的方法解決問(wèn)題。

算法策略間的關(guān)系編輯 1、對(duì)問(wèn)題進(jìn)行分解的算法策略——分治法與動(dòng)態(tài)規(guī)劃法 共同點(diǎn)：（1）分治法與動(dòng)態(tài)規(guī)劃法實(shí)際上都是遞歸思想的運(yùn)用 （2）二者的根本策略都是對(duì)問(wèn)題進(jìn)行分解，找到大規(guī)模與小規(guī)模的關(guān)系，然后通過(guò)解小規(guī)模的解，得出大規(guī)模的解 不同點(diǎn)： 適用于分治法的問(wèn)題分解成子問(wèn)題后，各子問(wèn)題間無(wú)公共子子問(wèn)題，而動(dòng)態(tài)規(guī)劃法相反。 動(dòng)態(tài)規(guī)劃法 = 分治算法思想 + 解決子問(wèn)題間的冗余情況 2、多階段逐步解決問(wèn)題的策略——貪心算法和動(dòng)態(tài)規(guī)劃法 貪心算法：每一步都根據(jù)策略得到一個(gè)結(jié)果，并傳遞到下一步，自頂向下，一步一步地做出貪心決策。

動(dòng)態(tài)規(guī)劃算法：每一步?jīng)Q策得到的不是一個(gè)唯一結(jié)果，而是一組中間結(jié)果（且這些結(jié)果在以后各步可能得到多次引用），只是每一步都使問(wèn)題的規(guī)模逐步縮小，最終得到問(wèn)題的一個(gè)結(jié)果。 計(jì)算機(jī)能夠快速、準(zhǔn)確地“計(jì)算”的最基本的原因，就是硬件與軟件的分離、程序與數(shù)據(jù)的分離。

這實(shí)際上也就是將我們?nèi)祟愖匀徽Z(yǔ)言中的思想與方法、方法與對(duì)象、思想與對(duì)象實(shí)行了分離。由于這些分離，使得計(jì)算機(jī)的程序語(yǔ)言中的命令與數(shù)據(jù)，都能非常精確地指稱計(jì)算機(jī)內(nèi)存里面的確定區(qū)域。

這樣，計(jì)算機(jī)“計(jì)算”的時(shí)候，就不會(huì)象人類大腦那樣，左半腦中的一個(gè)語(yǔ)詞指稱的是一個(gè)幾乎難以確切地劃分出“邊界”的右半腦中的圖景，而是一塊有著確定“地址”的內(nèi)存區(qū)域。這樣，計(jì)算機(jī)就能夠達(dá)到快速準(zhǔn)確地“計(jì)算”了。

4.算法有幾種

但是可以分類。

以下是我查到的資料

算法可大致分為基本算法、數(shù)據(jù)結(jié)構(gòu)的算法、數(shù)論與代數(shù)算法、計(jì)算幾何的算法、圖論的算法、動(dòng)態(tài)規(guī)劃以及數(shù)值分析、加密算法、排序算法、檢索算法、隨機(jī)化算法、并行算法。

算法可以宏泛的分為三類：

有限的，確定性算法 這類算法在有限的一段時(shí)間內(nèi)終止。他們可能要花很長(zhǎng)時(shí)間來(lái)執(zhí)行指定的任務(wù)，但仍將在一定的時(shí)間內(nèi)終止。這類算法得出的結(jié)果常取決于輸入值。

有限的，非確定算法 這類算法在有限的時(shí)間內(nèi)終止。然而，對(duì)于一個(gè)（或一些）給定的數(shù)值，算法的結(jié)果并不是唯一的或確定的。

無(wú)限的算法 是那些由于沒(méi)有定義終止定義條件，或定義的條件無(wú)法由輸入的數(shù)據(jù)滿足而不終止運(yùn)行的算法。通常，無(wú)限算法的產(chǎn)生是由于未能確定的定義終止條件。

算法設(shè)計(jì)與分析的基本方法 1.遞推法

2.遞歸遞歸指的是一個(gè)過(guò)程：函數(shù)不斷引用自身，直到引用的對(duì)象已知

3.窮舉搜索法

窮舉搜索法是對(duì)可能是解的眾多候選解按某種順序進(jìn)行逐一枚舉和檢驗(yàn)，并從眾找出那些符合要求的候選解作為問(wèn)題的解。

4.貪婪法貪婪法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因?yàn)樗∪チ藶檎易顑?yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間。貪婪法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。

5.分治法把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的相同或相似的子問(wèn)題，再把子問(wèn)題分成更小的子問(wèn)題……直到最后子問(wèn)題可以簡(jiǎn)單的直接求解，原問(wèn)題的解即子問(wèn)題的解的合并。

6.動(dòng)態(tài)規(guī)劃法

動(dòng)態(tài)規(guī)劃是一種在數(shù)學(xué)和計(jì)算機(jī)科學(xué)中使用的，用于求解包含重疊子問(wèn)題的最優(yōu)化問(wèn)題的方法。其基本思想是，將原問(wèn)題分解為相似的子問(wèn)題，在求解的過(guò)程中通過(guò)子問(wèn)題的解求出原問(wèn)題的解。動(dòng)態(tài)規(guī)劃的思想是多種算法的基礎(chǔ)，被廣泛應(yīng)用于計(jì)算機(jī)科學(xué)和工程領(lǐng)域。

7.迭代法迭代是數(shù)值分析中通過(guò)從一個(gè)初始估計(jì)出發(fā)尋找一系列近似解來(lái)解決問(wèn)題（一般是解方程或者方程組）的過(guò)程，為實(shí)現(xiàn)這一過(guò)程所使用的方法統(tǒng)稱為迭代法。