分塊查找基本思想是什么 冒泡法把一維數(shù)組從小到大排序

如何用C++描述分塊查找的算法？數(shù)據(jù)結(jié)構(gòu)和計算機相關(guān)的問題，數(shù)組的冒泡排序和分塊查找法，http://www.baidu .com/，分塊查找的基本思想是什么？什么是折半查找法？

本文導(dǎo)航

• c加加里面的算法
• 計算機的核心是算法和數(shù)據(jù)結(jié)構(gòu)
• 冒泡法把一維數(shù)組從小到大排序
• 百度賬號的頭像
• 分塊查找技巧口訣
• 折半查找算法經(jīng)典例題及答案

c加加里面的算法

template<class Type>

int BinarySearch(Type a[],const Type& x,int n)

{

int left=0;

int right=n-1;

while(left<=right){

int middle=(left+right)/2;

if (x==a[middle]) return middle;

if (x>a[middle]) left=middle+1;

else right=middle-1;

}

return -1;

}

模板函數(shù)BinarySearch在a[0]<=a[1]<=...<=a[n-1]共n個升序排列的元素中搜索x,找到x時返回其在數(shù)組中的位置，否則返回-1。容易看出，每執(zhí)行一次while循環(huán)，待搜索數(shù)組的大小減少一半,因此整個算法在最壞情況下的時間復(fù)雜度為O(log n)。在數(shù)據(jù)量很大的時候，它的線性查找在時間復(fù)雜度上的優(yōu)劣一目了然。

選擇排序

基本思想是：每次選出第i小的記錄，放在第i個位置（i的起點是0，按此說法，第0小的記錄實際上就是最小的，有點別扭，不管這么多了）。當i＝N－1時就排完了。

直接選擇排序

直選排序簡單的再現(xiàn)了選擇排序的基本思想，第一次尋找最小元素的代價是O(n)，如果不做某種特殊處理，每次都使用最簡單的尋找方法，自然的整個排序的時間復(fù)雜度就是O(n2)了。

冒泡法

為了在a[1]中得到最大值，我們將a[1]與它后面的元素a[2]，a[3]，...，a[10]進行比較。首先比較a[1]與a[2]，如果a[1]<a[2]，則將a[1]與a[2]交換，否則不交換。這樣在a[1]中得到的是a[1]與a[2]中的大數(shù)。然后將a[1]與a[3]比較，如果a[1]<a[3]，則將a[1]與a[3]交換，否則不交換。這樣在a[1]中得到的是a[1]，a[2]，a[3]中的最大值，...。如此繼續(xù)，最后a[1]與a[10]比較，如果a[1]<a[10]，則將a[1]與a[10]交換，否則不交換。這樣在a[1]中得到的數(shù)就是數(shù)組a的最大值（一共進行了9次比較）。

為了在a[2]中得到次大值，應(yīng)將a[2]與它后面的元素a[3]，a[4]，...，a[10]進行比較。這樣經(jīng)過8次比較，在a[2]是將得到次大值。

如此繼續(xù)，直到最后a[9]與a[10]比較，將大數(shù)放于a[9]，小數(shù)放于a[10]，全部排序到此結(jié)束。

從上面可以看出，對于10個數(shù)，需進行9趟比較，每一趟的比較次數(shù)是不一樣的。第一趟需比較9次，第二趟比較8次，...，最后一趟比較1次。

以上數(shù)組元素的排序，用二重循環(huán)實現(xiàn)，外循環(huán)變量設(shè)為i，內(nèi)循環(huán)變量設(shè)為j。外循環(huán)重復(fù)9次，內(nèi)循環(huán)依次重復(fù)9，8，...，1次。每次進行比較的兩個元素，第一個元素與外循環(huán)i有關(guān)的，用a[i]標識，第二個元素是與內(nèi)循環(huán)j有關(guān)的，用a[j]標識，i的值依次為1,2,...,9，對于每一個i, j的值依次為i+1,i+2,...。

計算機的核心是算法和數(shù)據(jù)結(jié)構(gòu)

1.數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，它在計算機處理和程序設(shè)計中通常作為一個整體進行考慮和處理。一個數(shù)據(jù)元素可由若干數(shù)據(jù)項組成。

2.棧（stack）在計算機科學(xué)中是限定僅在表尾進行插入或刪除操作的線形表。

棧是一種數(shù)據(jù)結(jié)構(gòu)，它按照后進先出的原則存儲數(shù)據(jù)，先進入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時候從棧頂開始彈出數(shù)據(jù)（最后一個數(shù)據(jù)被第一個讀出來）。

棧是只能在某一端插入和刪除的特殊線性表。用桶堆積物品，先堆進來的壓在底下，隨后一件一件往堆。取走時，只能從上面一件一件取。堆和取都在頂部進行，底部一般是不動的。

棧就是一種類似桶堆積物品的數(shù)據(jù)結(jié)構(gòu)，進行刪除和插入的一端稱棧頂，另一堆稱棧底。插入一般稱為進棧（PUSH），刪除則稱為退棧（POP）。 棧也稱為后進先出表（LIFO表）。

3.線性表是由n（n≥0）個數(shù)據(jù)元素（結(jié)點）a[0]，a[1]，a[2]…，a[n-1]組成的有限序列。

4.隊列的操作原則是先進先出

5.并發(fā)進程間的關(guān)系：并發(fā)進程相互之間可能是 無關(guān)的 ，也可能是 交往的 .如果一個進程的執(zhí)行不影響其他進程的執(zhí)行，且與其他進程的進展情況無關(guān)，即它們是各自獨立的，則這些并發(fā)進程相互之間是無關(guān)的。如果一個進程的執(zhí)行依賴其他進程的執(zhí)行，則這些并發(fā)進程之間是有交往的。

6.算法設(shè)計的基本方法:列舉法 枚舉歸納法 遞推法 遞歸法 減半遞推技術(shù) 回溯法 數(shù)值法

7.數(shù)據(jù)結(jié)構(gòu)分為哪幾大類:通常有下列四類基本的結(jié)構(gòu)：

⑴集合結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素間的關(guān)系是“屬于同一個集合”。

⑵線性結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對一的關(guān)系。

⑶樹型結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對多的關(guān)系。

⑷圖形結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對多的關(guān)系，也稱網(wǎng)狀結(jié)構(gòu)。

8.對于一個順尋戰(zhàn)來說,戰(zhàn)空 戰(zhàn)滿的條件:?？盏臈l件是st->top=0,棧滿的條件是st->top==maxlen

9.N/2

10.進程死鎖的4個表要條件

（1） 互斥條件：一個資源每次只能被一個進程使用。

（2） 請求與保持條件：一個進程因請求資源而阻塞時，對已獲得的資源保持不放。

（3） 不剝奪條件:進程已獲得的資源，在末使用完之前，不能強行剝奪。

（4） 循環(huán)等待條件:若干進程之間形成一種頭尾相接的循環(huán)等待資源關(guān)系。

11.操作系統(tǒng)的典型類型 3個:

批處理操作系統(tǒng)

分時操作系統(tǒng)

實時操作系統(tǒng)

12.進程的3中基本:就緒，阻塞，運行

13.算法的概念和特征:

算法（Algorithm）是一系列解決問題的清晰指令，也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時間內(nèi)獲得所要求的輸出。如果一個算法有缺陷，或不適合于某個問題，執(zhí)行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務(wù)。一個算法的優(yōu)劣可以用空間復(fù)雜度與時間復(fù)雜度來衡量。

算法可以理解為有基本運算及規(guī)定的運算順序所構(gòu)成的完整的解題步驟?；蛘呖闯砂凑找笤O(shè)計好的有限的確切的計算序列，并且這樣的步驟和序列可以解決一類問題。

一個算法應(yīng)該具有以下五個重要的特征：

1、有窮性2、確切性3、輸入：一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身定除了初始條件；

4、輸出：一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的；

5、可行性

14.數(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)。

15.什么是數(shù)據(jù)的存儲結(jié)構(gòu):存儲結(jié)構(gòu)是指一個數(shù)據(jù)集合在計算機內(nèi)存里是怎么樣存儲的.或者說在內(nèi)存里怎么給一群數(shù)據(jù)分配內(nèi)存.

16.查找的概念以及典型的算法:給定一個值K，在含有n個結(jié)點的表中找出關(guān)鍵字等于給定值K的結(jié)點。若找到，則查找成功，返回該結(jié)點的信息或該結(jié)點在表中的位置;否則查找失敗，返回相關(guān)的指示信息。順序查找 二分查找

分塊查找 哈希表查找

17.操作系統(tǒng)的功能:

作業(yè)管理(Job Management)

進程管理(Process Management)

存儲管理(Memory Management)

設(shè)備管理(Device Management)

文件管理(File Management)

18.遞歸算法思路:一個過程或函數(shù)在其定義或說明中又直接或間接調(diào)用自身的一種方法，它通常把一個大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復(fù)計算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合。用遞歸思想寫出的程序往往十分簡潔易懂。

19.數(shù)據(jù)的邏輯結(jié)構(gòu):簡單說,數(shù)據(jù)的邏輯結(jié)構(gòu)就是數(shù)據(jù)之間關(guān)系,如順序關(guān)系,隸屬關(guān)系等.

20.隊列的概念:隊列（Queue）是只允許在一端進行插入，而在另一端進行刪除的運算受限的線性表

21.進程的概念:進程是一個具有獨立功能的程序關(guān)于某個數(shù)據(jù)集合的一次運行活動。它可以申請和擁有系統(tǒng)資源，是一個動態(tài)的概念，是一個活動的實體。它不只是程序的代碼，還包括當前的活動，通過程序計數(shù)器的值和處理寄存器的內(nèi)容來表示。

22.二叉樹的先序、中序和后續(xù):NLR：前序遍歷(PreorderTraversal亦稱(先序遍歷))訪問結(jié)點的操作發(fā)生在遍歷其左右子樹之前。

② LNR：中序遍歷(InorderTraversal)訪問結(jié)點的操作發(fā)生在遍歷其左右子樹之中(間)。

③ LRN：后序遍歷(PostorderTraversal)訪問結(jié)點的操作發(fā)生在遍歷其左右子樹之后。

23.快速排序:快速排序?qū)γ芭菖判虻囊环N改進。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。

冒泡法把一維數(shù)組從小到大排序

#include<iostream.h>

const int N=12,M=3;

void numbers (int a[]) //輸入數(shù)組元素

{

cout<<"請輸入"<<N<<"個元素"<<endl;

for(int i=0;i<N;i++)

cin>>a;

}

void sort(int a[],int n) //冒泡法排序

{

int t;

for(int i=0;i<n-1;i++)

for(int j=0;j<n-1-i;j++)

if(a[j]>a[j+1])

{

t=a[j];

a[j]=a[j+1];

a[j+1]=t;

}

}

void search(int a[]) //分塊查找法

{

int x,j,i;

cout<<"請輸入要查找的元素"<<endl;

cin>>x;

int b[N][2];

for(j=0,i=3;j<3,i<12;j++,i+=4)

b[j][0]=a;

for(j=0,i=0;j<3,i<12;j++,i+=4)

b[j][1]=i;

for(j=0;j<3;j++)

{

if(x<=b[j][0])

break;

}

if(x>a[N-1])

{

cout<<x<<" "<<"不在您要查找的數(shù)組中"<<endl;

return;

}

{

int top=b[j][1],bottom=b[j][1]+N/M-1,middle=(top+bottom)/2; //折半查找法

while(top<=bottom)

{

if(x==a[middle])

break;

else if(x>a[middle])

top=middle+1;

else

bottom=middle-1;

middle=(top+bottom)/2;

}

if(x==a[middle])

{

cout<<x<<" "<<"在您要查找的數(shù)組中"<<endl;

}

else

{

cout<<x<<" "<<"不在您要查找的數(shù)組中"<<endl;

}

}

}

百度賬號的頭像

們我現(xiàn)在有一個C++作業(yè)題不會做，特向你們求助，懇請你們能給我些幫助！??！下面是問題的題目及要求，謝謝你的幫助！

一、題目：用分塊查找方法解決在數(shù)據(jù)庫中查找與關(guān)鍵字相同記錄的問題

1． 基本要求：

（1）要求用C++模塊化設(shè)計的思想來完成程序的設(shè)計；

（2）要求各個功能分別使用函數(shù)來完成，主函數(shù)和各個函數(shù)分別存放在不同的.cpp文件中，要求使用頭文件；

（3）程序調(diào)試通過后，完成程序文檔的處理，加必要的注釋。

三、設(shè)計方法和基本原理

1． 問題描述：

在一組無序數(shù)列中查找某個數(shù)據(jù)，找到則輸出該數(shù)據(jù)，否則輸出未找到信息。

2． 問題的解決方案：

根據(jù)問題的描述，可以按照要求的功能采用結(jié)構(gòu)化的設(shè)計思想。

（1） 數(shù)列的賦值要求編寫?yīng)毩⒑瘮?shù)實現(xiàn)；

（2） 將無序數(shù)列排序為有序數(shù)列可以用“拉鋸法”排序法也可以用其他方法實現(xiàn)，并編寫?yīng)毩⒑瘮?shù)；

（3） 分塊查找的算法用獨立函數(shù)實現(xiàn)

四、主要技術(shù)問題的描述

根據(jù)三的分析，主要問題在于：

1、排序算法的實現(xiàn)（不限方法）

2、分塊查找方法的實現(xiàn)

分塊查找又索引查找，它主要用于“分塊有序”表的查找。所謂“分塊有序”是指將線性表L（一維數(shù)組）分成m個子表（要求每個子表的長度相等），且第i+1個子表中的每一個項目均大于第i個子表中的所有項目?！胺謮K有序”表應(yīng)該包括線性表L本身和分塊的索引表A。因此，分塊查找的關(guān)鍵在于建立索引表A。

（1）建立索引表A（二維數(shù)組）

索引表包括兩部分：關(guān)鍵字項（子表中的最大值）和指針項（子表的第一項在線性表L中位置）

索引表按關(guān)鍵字有序的。

例如：線性表L（有序）為：1 2 3 4 5 6 7 8 9 10 11 12

分成m=3個子表：{1 2 3 4} {5 6 7 8} {9 10 11 12}

索引表A：二維數(shù)組：第一列為每個子表的最大值 ，第二列為每個子表的起始地址

即： 4 0

8 4

12 8

分塊查找技巧口訣

前提條件 塊內(nèi)無序塊間有序

方法二分查找塊間 順序查找塊內(nèi)

折半查找算法經(jīng)典例題及答案

折半查找法是效率較高的一種查找方法，假設(shè)有已經(jīng)按照從小到大的順序排列好的五個整數(shù)a0~a4，要查找的數(shù)是X，其基本思想是：

設(shè)查找數(shù)據(jù)的范圍下限為l=0，上限為h=4，求中點m=（l+h）/2，用X與中點元素am比較，若X等于am，即找到，停止查找。

否則，若X大于am，替換下限l=m+1，到下半段繼續(xù)查找。

若X小于am，換上限h=m-1，到上半段繼續(xù)查找，如此重復(fù)前面的過程直到找到或者l>h為止。

如果l>h，說明沒有此數(shù)，打印找不到信息，程序結(jié)束。

該方法是查找的范圍不斷縮小一半，所以查找效率較高。

擴展資料

折半查找法優(yōu)缺點

Bentley在自己的著作《Writing Correct Programs》中寫道，90%的計算機專家不能在2小時內(nèi)寫出完全正確的二分搜索算法。

問題的關(guān)鍵在于準確地制定各次查找范圍的邊界以及終止條件的確定，正確地歸納奇偶數(shù)的各種情況，其實整理后可以發(fā)現(xiàn)它的具體算法是很直觀的。

折半查找法的優(yōu)點是比較次數(shù)少，查找速度快，平均性能好。

其缺點是要求待查表為有序表，且插入刪除困難，因此折半查找方法適用于不經(jīng)常變動而查找頻繁的有序列表。

參考資料來源：百度百科-折半查找法