搜索其實(shí)就等于查找
1.順序查找
就是枚舉，一個(gè)個(gè)的對(duì)比，發(fā)現(xiàn)了就是發(fā)現(xiàn)了，沒有就是沒有了，但是效率低下。前面的枚舉里面的百雞百錢和棋盤問題都是這類解決方案。
#include int?search?(int?a[],?int?n,?int?k)
?/*a查找表,?n表長,?k關(guān)鍵字*/
{?int?i;
?????for?(i=0;?i<n;?i++)
????????if?(k==a[i])?return?(i+1);
?????return??0;
}
int?main()
{ int?x,t,a[9]={10,31,12,42,35,76,16,18,29};
?????????scanf("%d",&x);
t=search(a,9,x);
if?(t==0)??printf("Not?found!n");
else?printf("%dn",t);
}2.二分法
如果查找表中的數(shù)據(jù)元素按關(guān)鍵字有序（假設(shè)遞增有序），則在查找時(shí)，可不必逐個(gè)順序比較，而采用跳躍的方式——先與“中間位置”的數(shù)據(jù)元素關(guān)鍵字比較，若相等，則查找成功；若給定值大于“中間位置”的關(guān)鍵字，則在查找表的后半部繼續(xù)進(jìn)行二分查找，否則在前半部進(jìn)行二分查找。
int?bin_search?(int?a[?],?int?n,?int?k)
{
???int?low,?high,?mid;
???low=0;?high=n-1;
???while?(low?<=?high)
????{
??????? mid=(low?+?high)/2;
??????? if?(k?<?a[mid])?
??????? high?=?mid?-?1;?
????????else??if??(k?>?a[mid])??
????????low?=?mid?+?1;
????????else??
?????????return??mid?;?
????}
?return??-1;
}int?bin_search?(int?a[?],?int?low,int?high?,int?k)
{
int?mid=(low?+?high)/2;
if?(low>high)?
return?-1;
else??if?(k?==?a[mid])??
????????return?mid;
????else??if??(k?>?a[mid]?)??
????????bin_search(a,mid+1,high,k);
????else??
????????bin_search(a,low,mid-1,k);??
}
深度優(yōu)先搜索DFS
深度優(yōu)先搜索和廣度優(yōu)先搜索是數(shù)據(jù)結(jié)構(gòu)里面訪問圖的時(shí)候常用的，樹其實(shí)是特殊的圖，所以在二叉樹的時(shí)候也會(huì)用到。DFS里面用到的是棧，在學(xué)習(xí)二叉樹的里面的遍歷問題，在實(shí)現(xiàn)非遞歸操作實(shí)現(xiàn)前序遍歷二叉樹的時(shí)候用到的算法就是DFS。數(shù)據(jù)結(jié)構(gòu)----樹（筆記）里最后那種非遞歸的實(shí)現(xiàn)就是DFS。
基本思想：從初始狀態(tài)S開始，利用規(guī)則生成搜索樹下一層任一個(gè)結(jié)點(diǎn)，檢查是否出現(xiàn)目標(biāo)狀態(tài)G，若未出現(xiàn)，以此狀態(tài)利用規(guī)則生成再下一層任一個(gè)結(jié)點(diǎn)，再檢查是否為目標(biāo)節(jié)點(diǎn)G，若未出現(xiàn)，繼續(xù)以上操作過程，一直進(jìn)行到葉節(jié)點(diǎn)（即不能再生成新狀態(tài)節(jié)點(diǎn)），當(dāng)它仍不是目標(biāo)狀態(tài)G時(shí)，回溯到上一層結(jié)果，取另一可能擴(kuò)展搜索的分支。生成新狀態(tài)節(jié)點(diǎn)。若仍不是目標(biāo)狀態(tài)，就按該分支一直擴(kuò)展到葉節(jié)點(diǎn)，若仍不是目標(biāo)，采用相同的回溯辦法回退到上層節(jié)點(diǎn)，擴(kuò)展可能的分支生成新狀態(tài)，…，一直進(jìn)行下去，直到找到目標(biāo)狀態(tài)G為止。
黑白圖像，輸入一個(gè)二維的黑白圖像，1表示黑色，0表示白色，任務(wù)是統(tǒng)計(jì)其中8連塊的個(gè)數(shù)，如果格子有公共定點(diǎn)或者公共邊就是八連塊。
1.使用遞歸，遞歸里面使用的是運(yùn)行的時(shí)候的棧，函數(shù)運(yùn)行在遞歸的過程自動(dòng)壓入棧，所以代碼簡潔點(diǎn)，但是程序遞歸次數(shù)過多的時(shí)候有棧溢出的危險(xiǎn)。
#include#includeint?a[6][8]=
{
????{0,0,0,0,0,0,0,0},?//6行8列，最外面一層是防止越界的,中心表示的是圖像
????{0,1,1,0,0,0,1,0},
????{0,1,0,0,1,0,0,0},
????{0,0,0,0,0,0,0,0},
????{0,0,1,0,0,1,1,0},
????{0,1,0,0,0,0,0,0},
};
int?visit[6][8];//標(biāo)記已經(jīng)訪問的數(shù)據(jù)的位置
void?dfs(int?i,int?j)
{
????if(a[i][j]==1&&visit[i][j]==0)//如果顏色為黑色并且沒有被訪問過。
????{
????????visit[i][j]=1;//標(biāo)記當(dāng)前的位置為已經(jīng)訪問
????????/**對(duì)周圍的位置進(jìn)行遞歸*/
????????dfs(i-1,j-1);dfs(i,j-1);dfs(i+1,j-1);
????????dfs(i-1,j);?????????????dfs(i,j+1);
????????dfs(i-1,j+1);dfs(i,j+1);dfs(i+1,j+1);
????}
????return?;
}
int?main()
{
????int?i,j,count=0;
????memset(visit,0,sizeof(visit)/sizeof(int));
????for(i=1;i<5;i++)
????{
????????for(j=1;j<7;j++)
????????{
????????????if(visit[i][j]==0&&a[i][j]==1)
????????????{
????????????????dfs(i,j);
????????????????count++;
????????????}
????????}
????}
????printf("%d",count);
}2.也可以自己顯示的利用棧進(jìn)行操作，代碼如下。
#include#include#define?M?100
typedef?struct
{
????int?sk[M];
????int?top;
}S;
S?my_stack;
int?a[6][8]=
{
????{0,0,0,0,0,0,0,0},?//6行8列，最外面一層是防止越界的,中心表示的是圖像
????{0,1,1,0,0,0,1,0},
????{0,1,0,0,1,0,0,0},
????{0,0,0,0,0,0,0,0},
????{0,0,1,0,0,1,1,0},
????{0,1,0,0,0,0,0,0},
};
int?visit[6][8]={0};//表示沒有被訪問
void?find(int?i,int?j)
{
????if(visit[i][j]==0&&a[i][j]==1)
????{
????????visit[i][j]=1;
????????my_stack.sk[++my_stack.top]=i*8+j;
????}
}
int?main()
{
????int?i,j,count=0;
????int?u,t_i,t_j;
????my_stack.top=-1;//初始化棧
????memset(visit,0,sizeof(visit)/sizeof(int));
????for(i=1;i<5;i++)
????{
????????for(j=1;j<7;j++)
????????{
????????????if(visit[i][j]==0&&a[i][j]==1)
????????????{
????????????????my_stack.sk[++my_stack.top]=i*8+j;//入棧
????????????????visit[i][j]=1;
????????????????while(my_stack.top!=-1)
????????????????{
????????????????????u=my_stack.sk[my_stack.top--];
????????????????????t_i=u/8;t_j=u%8;
????????????????????find(t_i-1,t_j-1);//出棧尋找周圍的元素，如果符合條件就把周圍的元素入棧
????????????????????find(t_i-1,t_j);
????????????????????find(t_i-1,t_j+1);
????????????????????find(t_i,t_j-1);
????????????????????find(t_i,t_j+1);
????????????????????find(t_i+1,t_j-1);
????????????????????find(t_i+1,t_j);
????????????????????find(t_i+1,t_j+1);
????????????????}
????????????????count++;
????????????}
????????}
????}
????printf("%d",count);
}廣度優(yōu)先搜索BFS
同樣是在圖的訪問里用到的，在二叉數(shù)的層次遍歷操作中用到的就是BFS。
BFS的思想是先訪問節(jié)點(diǎn)周圍的相鄰的節(jié)點(diǎn)，然后在按照訪問的順序依次訪問相鄰的節(jié)點(diǎn)，這是和DFS的區(qū)別
迷宮問題
就是老鼠走迷宮的問題一樣，用二維數(shù)組表示迷宮，0表示可以走的路，1表示墻壁表示不通，找出到達(dá)終點(diǎn)的路徑
下面的這種辦法和前面學(xué)過遞歸那里解決迷宮問題的思想不太一樣，遞歸那里的思路是在遞歸中枚舉。這里用的是BFS搜索路徑，按層次依次向四周搜索路徑，
#include#include#define?M?1000
/**思想是如果迷宮出的位置的數(shù)是0，并且沒有被訪問過，就進(jìn)入隊(duì)列，否則不進(jìn)入，在出隊(duì)列的時(shí)候?qū)υ撐恢弥車?的值進(jìn)行判斷是否滿足進(jìn)入隊(duì)列的條件，結(jié)束條件是到達(dá)中點(diǎn)，或者隊(duì)列為空。*/
int?count=1;
int?t_i,t_j,u,i=0;
typedef?struct
{
????int?queue[M];
????int?rear;
????int?head;
}S_queue;
S_queue?my_queue;
char?a[6][8]=//0表示的是障礙，1表示的是道路，開始坐標(biāo)是(1,1)終止坐標(biāo)是(4,6)
{
????{0,0,0,0,0,0,0,0},
????{0,1,1,1,1,1,1,0},
????{0,1,0,0,1,0,0,0},
????{0,1,0,0,1,1,1,0},
????{0,1,1,1,1,1,1,0},
????{0,0,0,0,0,0,0,0},
};
int?visit[6][8]={0};//表示沒有被訪問
int?pos[M];//記錄每次插入數(shù)據(jù)后rear的位置，根據(jù)這個(gè)判斷是不是count要加1
void?find(int?i,int?j)
{
????if(a[i][j]==1&&visit[i][j]==0)
????{
????????visit[i][j]=visit[t_i][t_j]+1;
????????my_queue.queue[my_queue.rear++]=i*8+j;
????}
}
int?main()
{
????int?start_i=1,j=1,start_j=1;//開始位置
????int?end_i=4,end_j=6;
????int?flag=0;
????memset(visit,0,sizeof(visit)/sizeof(int));
????my_queue.rear=0;
????my_queue.head=0;
????my_queue.queue[my_queue.rear++]=start_i*8+start_j;
????visit[start_i][start_j]=count;
????while(my_queue.head<my_queue.rear)
????{
????????u=my_queue.queue[my_queue.head++];
????????if(visit[end_i][end_j]!=0)
????????{
????????????flag=1;
????????????break;
????????}
????????t_i=u/8;
????????t_j=u%8;
????????find(t_i-1,t_j);/**先上下找，后左右找*/
????????find(t_i+1,t_j);
????????find(t_i,t_j-1);
????????find(t_i,t_j+1);
????}
????if(flag==1)
????{
????????printf("可以到達(dá),需要%d步.n",visit[end_i][end_j]);
????}
????else
????{
????????printf("不可到達(dá).n");
????}
????for(start_i=0;start_i<=5;start_i++)
????{
????????for(start_j=0;start_j<=7;start_j++)
????????{
????????????printf("%-4d",visit[start_i][start_j]);
????????}
????????printf("%n");
????}
} 
下載文檔
