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

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

本文導(dǎo)航

• c加加里面的算法
• 計(jì)算機(jī)的核心是算法和數(shù)據(jù)結(jié)構(gòu)
• 冒泡法把一維數(shù)組從小到大排序
• 百度賬號(hào)的頭像
• 分塊查找技巧口訣
• 折半查找算法經(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個(gè)升序排列的元素中搜索x,找到x時(shí)返回其在數(shù)組中的位置，否則返回-1。容易看出，每執(zhí)行一次while循環(huán)，待搜索數(shù)組的大小減少一半,因此整個(gè)算法在最壞情況下的時(shí)間復(fù)雜度為O(log n)。在數(shù)據(jù)量很大的時(shí)候，它的線性查找在時(shí)間復(fù)雜度上的優(yōu)劣一目了然。

選擇排序

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

直接選擇排序

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

冒泡法

為了在a[1]中得到最大值，我們將a[1]與它后面的元素a[2]，a[3]，...，a[10]進(jìn)行比較。首先比較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的最大值（一共進(jìn)行了9次比較）。

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

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

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

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

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

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

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

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

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

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

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

4.隊(duì)列的操作原則是先進(jìn)先出

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

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

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

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

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

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

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

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

9.N/2

10.進(jìn)程死鎖的4個(gè)表要條件

（1） 互斥條件：一個(gè)資源每次只能被一個(gè)進(jìn)程使用。

（2） 請(qǐng)求與保持條件：一個(gè)進(jìn)程因請(qǐng)求資源而阻塞時(shí)，對(duì)已獲得的資源保持不放。

（3） 不剝奪條件:進(jìn)程已獲得的資源，在末使用完之前，不能強(qiáng)行剝奪。

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

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

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

分時(shí)操作系統(tǒng)

實(shí)時(shí)操作系統(tǒng)

12.進(jìn)程的3中基本:就緒，阻塞，運(yùn)行

13.算法的概念和特征:

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

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

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

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

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

5、可行性

14.數(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)可以帶來更高的運(yùn)行或者存儲(chǔ)效率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。

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

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

分塊查找 哈希表查找

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

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

進(jìn)程管理(Process Management)

存儲(chǔ)管理(Memory Management)

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

文件管理(File Management)

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

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

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

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

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

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

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

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

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

#include<iostream.h>

const int N=12,M=3;

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

{

cout<<"請(qǐng)輸入"<<N<<"個(gè)元素"<<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<<"請(qǐng)輸入要查找的元素"<<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;

}

}

}

百度賬號(hào)的頭像

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

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

1． 基本要求：

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

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

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

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

1． 問題描述：

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

2． 問題的解決方案：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

即： 4 0

8 4

12 8

分塊查找技巧口訣

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

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

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

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

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

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

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

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

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

擴(kuò)展資料

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

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

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

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

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

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