搜索其實就等于查找
1.順序查找
就是枚舉，一個個的對比，發(fā)現(xiàn)了就是發(fā)現(xiàn)了，沒有就是沒有了，但是效率低下。前面的枚舉里面的百雞百錢和棋盤問題都是這類解決方案。
#include int?search?(int?a[],?int?n,?int?k)
?/*a查找表,?n表長,?k關鍵字*/
{?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ù)元素按關鍵字有序（假設遞增有序），則在查找時，可不必逐個順序比較，而采用跳躍的方式——先與“中間位置”的數(shù)據(jù)元素關鍵字比較，若相等，則查找成功；若給定值大于“中間位置”的關鍵字，則在查找表的后半部繼續(xù)進行二分查找，否則在前半部進行二分查找。
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ù)結構里面訪問圖的時候常用的，樹其實是特殊的圖，所以在二叉樹的時候也會用到。DFS里面用到的是棧，在學習二叉樹的里面的遍歷問題，在實現(xiàn)非遞歸操作實現(xiàn)前序遍歷二叉樹的時候用到的算法就是DFS。數(shù)據(jù)結構----樹（筆記）里最后那種非遞歸的實現(xiàn)就是DFS。
基本思想：從初始狀態(tài)S開始，利用規(guī)則生成搜索樹下一層任一個結點，檢查是否出現(xiàn)目標狀態(tài)G，若未出現(xiàn)，以此狀態(tài)利用規(guī)則生成再下一層任一個結點，再檢查是否為目標節(jié)點G，若未出現(xiàn)，繼續(xù)以上操作過程，一直進行到葉節(jié)點（即不能再生成新狀態(tài)節(jié)點），當它仍不是目標狀態(tài)G時，回溯到上一層結果，取另一可能擴展搜索的分支。生成新狀態(tài)節(jié)點。若仍不是目標狀態(tài)，就按該分支一直擴展到葉節(jié)點，若仍不是目標，采用相同的回溯辦法回退到上層節(jié)點，擴展可能的分支生成新狀態(tài)，…，一直進行下去，直到找到目標狀態(tài)G為止。
黑白圖像，輸入一個二維的黑白圖像，1表示黑色，0表示白色，任務是統(tǒng)計其中8連塊的個數(shù)，如果格子有公共定點或者公共邊就是八連塊。
1.使用遞歸，遞歸里面使用的是運行的時候的棧，函數(shù)運行在遞歸的過程自動壓入棧，所以代碼簡潔點，但是程序遞歸次數(shù)過多的時候有棧溢出的危險。
#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];//標記已經(jīng)訪問的數(shù)據(jù)的位置
void?dfs(int?i,int?j)
{
????if(a[i][j]==1&&visit[i][j]==0)//如果顏色為黑色并且沒有被訪問過。
????{
????????visit[i][j]=1;//標記當前的位置為已經(jīng)訪問
????????/**對周圍的位置進行遞歸*/
????????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.也可以自己顯示的利用棧進行操作，代碼如下。
#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é)點周圍的相鄰的節(jié)點，然后在按照訪問的順序依次訪問相鄰的節(jié)點，這是和DFS的區(qū)別
迷宮問題
就是老鼠走迷宮的問題一樣，用二維數(shù)組表示迷宮，0表示可以走的路，1表示墻壁表示不通，找出到達終點的路徑
下面的這種辦法和前面學過遞歸那里解決迷宮問題的思想不太一樣，遞歸那里的思路是在遞歸中枚舉。這里用的是BFS搜索路徑，按層次依次向四周搜索路徑，
#include#include#define?M?1000
/**思想是如果迷宮出的位置的數(shù)是0，并且沒有被訪問過，就進入隊列，否則不進入，在出隊列的時候?qū)υ撐恢弥車?的值進行判斷是否滿足進入隊列的條件，結束條件是到達中點，或者隊列為空。*/
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表示的是道路，開始坐標是(1,1)終止坐標是(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ù)這個判斷是不是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步.n",visit[end_i][end_j]);
????}
????else
????{
????????printf("不可到達.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");
????}
} 
下載文檔
