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

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

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

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

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

數(shù)據(jù)的運算是在數(shù)據(jù)的邏輯結(jié)構(gòu)上定義的操作算法，如檢索、插入、刪除、更新和排序等。數(shù)據(jù)的運算是數(shù)據(jù)結(jié)構(gòu)的一個重要方面，討論任一種數(shù)據(jù)結(jié)構(gòu)時都離不開對該結(jié)構(gòu)上的數(shù)據(jù)運算及其實現(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ù)的取值范圍、存儲方式以及允許進行的運算。可以認為，數(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)。計算機中表示數(shù)據(jù)的最小單位是二進制數(shù)的一位，叫做位。

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

元素或結(jié)點可看成是數(shù)據(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描述程序處理的實體時，強調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）。

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

它是計算機程序加工的原料，應(yīng)用程序處理各種各樣的數(shù)據(jù)。計算機科學(xué)中，所謂數(shù)據(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é)點、頂點、記錄等。例如，學(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)作一個基本單位進行訪問和處理的。

數(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)中，所有的頂點是一個數(shù)據(jù)元素類，頂點A和頂點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ù)值分析、加密算法、排序算法、檢索算法、隨機化算法、并行算法。

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

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

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

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

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

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

3.窮舉搜索法

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

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

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

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

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

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

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

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

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

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

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

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

4.算法有幾種

但是可以分類。

以下是我查到的資料

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

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

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

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

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

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

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

3.窮舉搜索法

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

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

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

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

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

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