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

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

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

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

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

數(shù)據(jù)的存儲結(jié)構(gòu)實質(zhì)上是它的邏輯結(jié)構(gòu)在計算機(jī)存儲器中的實現(xiàn)，為了全面的反映一個數(shù)據(jù)的邏輯結(jié)構(gòu)，它在存儲器中的映象包括兩方面內(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)的一個重要方面，討論任一種數(shù)據(jù)結(jié)構(gòu)時都離不開對該結(jié)構(gòu)上的數(shù)據(jù)運(yùn)算及其實現(xiàn)算法的討論。

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

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

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

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

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

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

一個含抽象數(shù)據(jù)類型的軟件模塊應(yīng)包含定義、表示、實現(xiàn)三個部分。對每一個數(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ù)類型：一個數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型實際上就是對該數(shù)據(jù)結(jié)構(gòu)的定義。

因為它定義了一個數(shù)據(jù)的邏輯結(jié)構(gòu)以及在此結(jié)構(gòu)上的一組算法。抽象數(shù)據(jù)類型可用以下三元組表示：（D,S,P）。

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

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

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

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

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

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

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

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

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

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

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

但是可以分類。

以下是我查到的資料

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

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

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

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

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

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

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

3.窮舉搜索法

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

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

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

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

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

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

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

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

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

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

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

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

4.算法有幾種

但是可以分類。

以下是我查到的資料

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

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

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

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

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

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

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

3.窮舉搜索法

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

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

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

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

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

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