/*题目：GOOGLE手机搜索问题 *说明： *  GOOGLE有一项手机搜索业务，一般是在城市中寻找某一地点的业务； *当用户向GOOGLE发送关键词后，GOOGLE快速找到相关信息并返回给用户相关信息。 *内容： *  一个客户在一个陌生的城市里，想要找最近的一个咖啡馆。于是发送关健词 *给GOOGLE，GOOGLE经搜索返回给客户最近的一家咖啡馆的信息。 *分析： *  我用DATA.txt来记录地图上结点信息，用CLOSER.txt记录地图上各结点上的关系， *程序初使化时读入结点信息及结点间关系，在内存中建立地图信息。其中地图是用坐标 *来表示位置关系的。用二维指针数组按照结点坐标值与结点建立相当于十字链表的结构。 *搜索时，应得知用户当前位置坐标和关键词，以用户当前位置为中心，5个单位为边长的 *正方形区域内向外辐射搜索目标，找到目标后，相应的返回给用户路径。 */#include "stdio.h"#define MAX 2#define MAXLINK 8#define MAXSTHING 43#define MAXX 20#define MAXY 20typedef struct node{  int x,y ;       /*坐标*/  char name[MAX]; /*名称*/  int fa[MAXSTHING]; struct node *Link[MAXLINK];/*邻接元素*/}sign; sign *List[MAXSTHING];/*存储各元素信息*/sign *st[MAXX][MAXY];/*坐标指针*/ /* 用栈来表示路程信息*/typedef struct roa{sign *L[MAXSTHING];int length;int top;}road ;road *way; init(){ FILE *fp,*fp1; int i,j; int A; int B; int longth; char ch; /*读取结点信息*/ fp=fopen("data.txt","r"); if(fp==NULL) {    puts("无法打开文件data.txt!");     return (0);    } for(i=0;i<MAXSTHING;i++){ if(!feof(fp)) {   List[i]=(sign *)malloc(sizeof(sign));   fscanf(fp,"%d,%d,",&List[i]->x,&List[i]->y);/*读入坐标*/   fscanf(fp,"%c%c",&List[i]->name[0],&List[i]->name[1]); /*读入名称*/   st[List[i]->x][List[i]->y]=List[i];/*将结点和坐标指针一一对应*/   for(j=0;j<MAXLINK;j++)      List[i]->Link[j]=NULL;/*方向指针清空*/   } } fclose(fp); /*读取结点关系并创建关系*/fp1=fopen("CLOSER.txt","r");if(fp1==NULL){  printf("无法打开文件CLOSER.txt");  return(0);} while(1){  if(feof(fp1)){fclose(fp1);return;}  fscanf(fp1,"%d,%d,",&A,&B);  fscanf(fp1,"%d,",&longth);  for(i=0;i<MAXLINK;i++){  /*读入一个关系就建立起关系中两个结点的对应关系并写入两结点间距离*/      if (List[A-1]->Link[i]==NULL){          List[A-1]->Link[i]=List[B-1];          List[A-1]->fa[i]=longth;          break;      }  /*end if*/   }  /*end for*/   for(i=0;i<MAXLINK;i++){      if (List[B-1]->Link[i]==NULL){          List[B-1]->Link[i]=List[A-1];          List[B-1]->fa[i]=longth;          break;         }  /*end if*/  } /*end for*/} /*end while*/fclose(fp1);return;} /*查找初始化*/lookupinit(){  int x,y;  char cc;  clrscr();  printf("请输入您当前的位置坐标X,Y：");  scanf("%d,%d",&x,&y);  printf("\n\n请输入您要查询的关键字:");  /*象fscanf("i=%d j=%d",&i,&j)  *这样的输入方式比较特别，  *TC 2.0显然在第一次输入后没有象正常情况一样清楚输入缓冲区，  *这样第二次执行fscanf时，程序并没有让你输入而是直接读入上次输入的结果?  *如果你一定要这么做，应该在fscanf之前加上flush(stdin); */  fflush(stdin);  scanf("%c",&cc);  printf("%c",cc);  printf("\n\n程序正在处理，请稍等..........");  lookup(x,y,cc); } /*查找函数*/lookup(ux,uy,uch)int ux,uy;char uch;{ /*参数初始，(m,n),(r,s)为两搜索边缘顶点坐标，count是计数找到多少个*/  int m,n,r,s,i,j,k,l,count;  int a[MAXX][MAXY];  int len;  s=n=uy;  r=m=ux;  clrscr();  for(i=0;i<MAXX;i++)      for(j=0;j<MAXY;j++)          a[i][j]=0; /*标计数组初始化*/  count=0;  /*在搜索人当前位置为中心,10个单位边长的正方形内搜索，找不到的话正方形边长加5个单位再搜*/  while(!count){     /*范围扩张*/      m-=5;      n+=5;      s-=5;      r+=5;      /*范围不能超过边界*/      if(m<0)m=0;      if(n>19)n=19;      if(r>19)r=19;      if(s<0)s=0;      /*开始利用坐标指针快速搜索*/      for(i=m;i<=r;i++)         for(j=n;j>=s;j--){                 if(st[i][j]->name[0]==uch||st[i][j]->name[1]==uch){                    a[i][j]=1;/*用二维指针数组标记目标*/                    count++; /*计数*/                 }/*endif*/         }/*endfor*/     if(m==0&&n==19&&s==0&&r==19&&count==0){ /*到达边界且count为０就是没有找到目标*/        printf("没有找到您的目标，按任意键尝试其它关键字！");        getch();        return;     }  }/*end while*/   clrscr();   for(i=m;i<=r;i++)         for(j=n;j>=s;j--){           if(st[i][j]!=NULL) {              if((int)((i-ux)*(i-ux)+(j-uy)*(j-uy))<(int)((i-1-ux)*(i-1-ux)+(j+1-uy)*(j+1-uy)))                 {/*找到和用户最近的结点并记录下来该结点的做标*/                 k=i;                 l=j;                 }           }         }  len=(int)sqrt((ux-k)*(ux-k)+(uy-l)*(uy-l)) /*计算刚刚找到的结点和用户的距离*/;  printf("共有%d个结果，它们是：",count);  for(i=0;i<MAXX;i++)      for(j=0;j<MAXY;j++)         if(a[i][j]==1) {  /*找到标记后，标记结点进栈*/         printf("\n%c%c",st[i][j]->name[0],st[i][j]->name[1]);          way->top=0;          way->L[way->top]=st[i][j];          way->length=len;         Goto(i,j,k,l,m,n,r,s);/* 传递的参数有目标结点坐标i,j；距用户最近结点坐标k,l；横坐标范围m,r；纵坐标范围n,s*/         }         getch();}/*end function*/ Goto(int mx,int my,int cx,int cy,int m,int n,int r,int s){  int top,i,j,k;  road *p;  top=way->top;  p=way->L[top]; if(p->x==cx&&p->y==cy){  /*如果遍历到目标用top变量当做栈way的顶指针虚拟全部元素出栈输出已经过结点*/      printf("\n您现在的位置");      while(way->top>=0){         printf("-->%c%c",(way->L[way->top])->name[0],(way->L[way->top])->name[1]);             way->L[way->top]=NULL; /*栈顶元素出栈*/             way->top--; /*栈顶指针后退*/      }      printf("\n上面路程的长度是：%d\n",way->length);     return 1;   }  /*如果没找到就看是否已到边界，如果到了边界则此分支遍历结束*/  if(p->x<m||p->x>r||p->y>n||p->y<s){    top=way->top;        p=way->L[top-1];        for(k=0;k<MAXLINK;k++) /*从对应关系中找出上一结点到这一结点的距离*/            if(p->Link[k]==way->L[top]){               way->length-=p->fa[k];            }    way->L[top]=NULL; /*栈顶元素出栈*/    way->top--; /*栈顶指针后退*/    return 0;  }  for(i=0;i<MAXLINK;i++){      if((way->L[top])->Link[i]!=NULL&&(way->L[top])->Link[i]!=way->L[way->top-1]){/*如果一个结点上的指针不指向空，且没有回指向刚刚遍历过的结点，则让它指向的结点进栈*/                way->top++;   /*栈指针上移*/                top=way->top; /*用top带替way->top方便表达式的书写*/                p=way->L[top-1];                way->L[top]=p->Link[i];  /*p->Link[i]进栈*/                way->length+=p->fa[i]; /*路程长度增加相应长度*/                if(Goto(mx,my,cx,cy,m,n,r,s)==1)break;           }      else{/*如果为空，则说明该结点下再无结点，结点出栈，路程长度减少相应长度*/        top=way->top;        p=way->L[top-1];        for(k=0;k<MAXLINK;k++) /*从对应关系中找出上一结点到这一结点的距离*/            if(p->Link[k]==way->L[top]){               way->length-=p->fa[k];               break;            }         way->L[way->top] =NULL; /*栈顶退栈*/        way->top--;        return 0;       /* Goto(mx,my,cx,cy,m,n,r,s);*/       }   } } /*end founction*/main(){ sign *p;char ch;printf("程序正在初始化...................\n");init();/*初始化*/while(1){    clrscr();    printf("          ================GooGle手机搜索算法模拟=================\n\n\n\n\n");    printf("                          开始执搜索请输入B或b                 \n\n\n");    printf("                          退出请输入Q或q                 \n\n\n\n\n");    printf("                          　　　　　　　请输入您的命令：");    ch=getchar();    if(ch=='q'||ch=='Q') exit(0);    if(ch=='b'||ch=='B') lookupinit();} }/*题目：GOOGLE手机搜索问题 *说明： *  GOOGLE有一项手机搜索业务，一般是在城市中寻找某一地点的业务； *当用户向GOOGLE发送关键词后，GOOGLE快速找到相关信息并返回给用户相关信息。 *内容： *  一个客户在一个陌生的城市里，想要找最近的一个咖啡馆。于是发送关健词 *给GOOGLE，GOOGLE经搜索返回给客户最近的一家咖啡馆的信息。 *分析： *  我用DATA.txt来记录地图上结点信息，用CLOSER.txt记录地图上各结点上的关系， *程序初使化时读入结点信息及结点间关系，在内存中建立地图信息。其中地图是用坐标 *来表示位置关系的。用二维指针数组按照结点坐标值与结点建立相当于十字链表的结构。 *搜索时，应得知用户当前位置坐标和关键词，以用户当前位置为中心，5个单位为边长的 *正方形区域内向外辐射搜索目标，找到目标后，相应的返回给用户路径。 */#include "stdio.h"#define MAX 2#define MAXLINK 8#define MAXSTHING 43#define MAXX 20#define MAXY 20typedef struct node{  int x,y ;       /*坐标*/  char name[MAX]; /*名称*/  int fa[MAXSTHING]; struct node *Link[MAXLINK];/*邻接元素*/}sign; sign *List[MAXSTHING];/*存储各元素信息*/sign *st[MAXX][MAXY];/*坐标指针*/ /* 用栈来表示路程信息*/typedef struct roa{sign *L[MAXSTHING];int length;int top;}road ;road *way; init(){ FILE *fp,*fp1; int i,j; int A; int B; int longth; char ch; /*读取结点信息*/ fp=fopen("data.txt","r"); if(fp==NULL) {    puts("无法打开文件data.txt!");     return (0);    } for(i=0;i<MAXSTHING;i++){ if(!feof(fp)) {   List[i]=(sign *)malloc(sizeof(sign));   fscanf(fp,"%d,%d,",&List[i]->x,&List[i]->y);/*读入坐标*/   fscanf(fp,"%c%c",&List[i]->name[0],&List[i]->name[1]); /*读入名称*/   st[List[i]->x][List[i]->y]=List[i];/*将结点和坐标指针一一对应*/   for(j=0;j<MAXLINK;j++)      List[i]->Link[j]=NULL;/*方向指针清空*/   } } fclose(fp); /*读取结点关系并创建关系*/fp1=fopen("CLOSER.txt","r");if(fp1==NULL){  printf("无法打开文件CLOSER.txt");  return(0);} while(1){  if(feof(fp1)){fclose(fp1);return;}  fscanf(fp1,"%d,%d,",&A,&B);  fscanf(fp1,"%d,",&longth);  for(i=0;i<MAXLINK;i++){  /*读入一个关系就建立起关系中两个结点的对应关系并写入两结点间距离*/      if (List[A-1]->Link[i]==NULL){          List[A-1]->Link[i]=List[B-1];          List[A-1]->fa[i]=longth;          break;      }  /*end if*/   }  /*end for*/   for(i=0;i<MAXLINK;i++){      if (List[B-1]->Link[i]==NULL){          List[B-1]->Link[i]=List[A-1];          List[B-1]->fa[i]=longth;          break;         }  /*end if*/  } /*end for*/} /*end while*/fclose(fp1);return;} /*查找初始化*/lookupinit(){  int x,y;  char cc;  clrscr();  printf("请输入您当前的位置坐标X,Y：");  scanf("%d,%d",&x,&y);  printf("\n\n请输入您要查询的关键字:");  /*象fscanf("i=%d j=%d",&i,&j)  *这样的输入方式比较特别，  *TC 2.0显然在第一次输入后没有象正常情况一样清楚输入缓冲区，  *这样第二次执行fscanf时，程序并没有让你输入而是直接读入上次输入的结果?  *如果你一定要这么做，应该在fscanf之前加上flush(stdin); */  fflush(stdin);  scanf("%c",&cc);  printf("%c",cc);  printf("\n\n程序正在处理，请稍等..........");  lookup(x,y,cc); } /*查找函数*/lookup(ux,uy,uch)int ux,uy;char uch;{ /*参数初始，(m,n),(r,s)为两搜索边缘顶点坐标，count是计数找到多少个*/  int m,n,r,s,i,j,k,l,count;  int a[MAXX][MAXY];  int len;  s=n=uy;  r=m=ux;  clrscr();  for(i=0;i<MAXX;i++)      for(j=0;j<MAXY;j++)          a[i][j]=0; /*标计数组初始化*/  count=0;  /*在搜索人当前位置为中心,10个单位边长的正方形内搜索，找不到的话正方形边长加5个单位再搜*/  while(!count){     /*范围扩张*/      m-=5;      n+=5;      s-=5;      r+=5;      /*范围不能超过边界*/      if(m<0)m=0;      if(n>19)n=19;      if(r>19)r=19;      if(s<0)s=0;      /*开始利用坐标指针快速搜索*/      for(i=m;i<=r;i++)         for(j=n;j>=s;j--){                 if(st[i][j]->name[0]==uch||st[i][j]->name[1]==uch){                    a[i][j]=1;/*用二维指针数组标记目标*/                    count++; /*计数*/                 }/*endif*/         }/*endfor*/     if(m==0&&n==19&&s==0&&r==19&&count==0){ /*到达边界且count为０就是没有找到目标*/        printf("没有找到您的目标，按任意键尝试其它关键字！");        getch();        return;     }  }/*end while*/   clrscr();   for(i=m;i<=r;i++)         for(j=n;j>=s;j--){           if(st[i][j]!=NULL) {              if((int)((i-ux)*(i-ux)+(j-uy)*(j-uy))<(int)((i-1-ux)*(i-1-ux)+(j+1-uy)*(j+1-uy)))                 {/*找到和用户最近的结点并记录下来该结点的做标*/                 k=i;                 l=j;                 }           }         }  len=(int)sqrt((ux-k)*(ux-k)+(uy-l)*(uy-l)) /*计算刚刚找到的结点和用户的距离*/;  printf("共有%d个结果，它们是：",count);  for(i=0;i<MAXX;i++)      for(j=0;j<MAXY;j++)         if(a[i][j]==1) {  /*找到标记后，标记结点进栈*/         printf("\n%c%c",st[i][j]->name[0],st[i][j]->name[1]);          way->top=0;          way->L[way->top]=st[i][j];          way->length=len;         Goto(i,j,k,l,m,n,r,s);/* 传递的参数有目标结点坐标i,j；距用户最近结点坐标k,l；横坐标范围m,r；纵坐标范围n,s*/         }         getch();}/*end function*/ Goto(int mx,int my,int cx,int cy,int m,int n,int r,int s){  int top,i,j,k;  road *p;  top=way->top;  p=way->L[top]; if(p->x==cx&&p->y==cy){  /*如果遍历到目标用top变量当做栈way的顶指针虚拟全部元素出栈输出已经过结点*/      printf("\n您现在的位置");      while(way->top>=0){         printf("-->%c%c",(way->L[way->top])->name[0],(way->L[way->top])->name[1]);             way->L[way->top]=NULL; /*栈顶元素出栈*/             way->top--; /*栈顶指针后退*/      }      printf("\n上面路程的长度是：%d\n",way->length);     return 1;   }  /*如果没找到就看是否已到边界，如果到了边界则此分支遍历结束*/  if(p->x<m||p->x>r||p->y>n||p->y<s){    top=way->top;        p=way->L[top-1];        for(k=0;k<MAXLINK;k++) /*从对应关系中找出上一结点到这一结点的距离*/            if(p->Link[k]==way->L[top]){               way->length-=p->fa[k];            }    way->L[top]=NULL; /*栈顶元素出栈*/    way->top--; /*栈顶指针后退*/    return 0;  }  for(i=0;i<MAXLINK;i++){      if((way->L[top])->Link[i]!=NULL&&(way->L[top])->Link[i]!=way->L[way->top-1]){/*如果一个结点上的指针不指向空，且没有回指向刚刚遍历过的结点，则让它指向的结点进栈*/                way->top++;   /*栈指针上移*/                top=way->top; /*用top带替way->top方便表达式的书写*/                p=way->L[top-1];                way->L[top]=p->Link[i];  /*p->Link[i]进栈*/                way->length+=p->fa[i]; /*路程长度增加相应长度*/                if(Goto(mx,my,cx,cy,m,n,r,s)==1)break;           }      else{/*如果为空，则说明该结点下再无结点，结点出栈，路程长度减少相应长度*/        top=way->top;        p=way->L[top-1];        for(k=0;k<MAXLINK;k++) /*从对应关系中找出上一结点到这一结点的距离*/            if(p->Link[k]==way->L[top]){               way->length-=p->fa[k];               break;            }         way->L[way->top] =NULL; /*栈顶退栈*/        way->top--;        return 0;       /* Goto(mx,my,cx,cy,m,n,r,s);*/       }   } } /*end founction*/main(){ sign *p;char ch;printf("程序正在初始化...................\n");init();/*初始化*/while(1){    clrscr();    printf("          ================GooGle手机搜索算法模拟=================\n\n\n\n\n");    printf("                          开始执搜索请输入B或b                 \n\n\n");    printf("                          退出请输入Q或q                 \n\n\n\n\n");    printf("                          　　　　　　　请输入您的命令：");    ch=getchar();    if(ch=='q'||ch=='Q') exit(0);    if(ch=='b'||ch=='B') lookupinit();} }

评论