搜索等于查找

搜索其实就等于查找

1.顺序查找

就是枚举，一个个的对比，发现了就是发现了，没有就是没有了，但是效率低下。前面的枚举里面的百鸡百钱和棋盘问题都是这类解决方案。

#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.二分法
如果查找表中的数据元素按关键字有序（假设递增有序），则在查找时，可不必逐个顺序比较，而采用跳跃的方式——先与“中间位置”的数据元素关键字比较，若相等，则查找成功；若给定值大于“中间位置”的关键字，则在查找表的后半部继续进行二分查找，否则在前半部进行二分查找。

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);  
}

深度优先搜索DFS 深度优先搜索和广度优先搜索是数据结构里面访问图的时候常用的，树其实是特殊的图，所以在二叉树的时候也会用到。DFS里面用到的是栈，在学习二叉树的里面的遍历问题，在实现非递归操作实现前序遍历二叉树的时候用到的算法就是DFS。数据结构----树（笔记）里最后那种非递归的实现就是DFS。
基本思想：从初始状态S开始，利用规则生成搜索树下一层任一个结点，检查是否出现目标状态G，若未出现，以此状态利用规则生成再下一层任一个结点，再检查是否为目标节点G，若未出现，继续以上操作过程，一直进行到叶节点（即不能再生成新状态节点），当它仍不是目标状态G时，回溯到上一层结果，取另一可能扩展搜索的分支。生成新状态节点。若仍不是目标状态，就按该分支一直扩展到叶节点，若仍不是目标，采用相同的回溯办法回退到上层节点，扩展可能的分支生成新状态，…，一直进行下去，直到找到目标状态G为止。
黑白图像，输入一个二维的黑白图像，1表示黑色，0表示白色，任务是统计其中8连块的个数，如果格子有公共定点或者公共边就是八连块。
1.使用递归，递归里面使用的是运行的时候的栈，函数运行在递归的过程自动压入栈，所以代码简洁点，但是程序递归次数过多的时候有栈溢出的危险。

#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];//标记已经访问的数据的位置
void dfs(int i,int j)
{
    if(a[i][j]==1&&visit[i][j]==0)//如果颜色为黑色并且没有被访问过。
    {
        visit[i][j]=1;//标记当前的位置为已经访问
        /**对周围的位置进行递归*/
        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);
}

广度优先搜索BFS 同样是在图的访问里用到的，在二叉数的层次遍历操作中用到的就是BFS。
BFS的思想是先访问节点周围的相邻的节点，然后在按照访问的顺序依次访问相邻的节点，这是和DFS的区别
迷宫问题
就是老鼠走迷宫的问题一样，用二维数组表示迷宫，0表示可以走的路，1表示墙壁表示不通，找出到达终点的路径
下面的这种办法和前面学过递归那里解决迷宫问题的思想不太一样，递归那里的思路是在递归中枚举。这里用的是BFS搜索路径，按层次依次向四周搜索路径，

#include#include#define M 1000
/**思想是如果迷宫出的位置的数是0，并且没有被访问过，就进入队列，否则不进入，在出队列的时候对该位置周围
的值进行判断是否满足进入队列的条件，结束条件是到达中点，或者队列为空。*/
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];//记录每次插入数据后rear的位置，根据这个判断是不是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");
    }
}