chengxu.cpp

城市之间路径查询 自行输入数据

/*
若干城市的信息存入一个带头结点的单链表，结点中的城市信息包括城市名，城市的位置坐标。要求：
   1，给定一个城市名，返回其位置坐标；
   2，给定一个位置坐标p和一个距离d，返回所有距p的距离小于d的城市。
*/

//分析
// (1) *********用city写一个struct其中包括城市名和城市坐标************
// (2) 单链表的运用，存入城市的信息（包括城市名，城市坐标）。
// (3) 给定城市名，找到其坐标Node *Locate(LinkList l,char k),值得探讨的是对于结构是否需要查找
// (4) 给定位置和坐标需要查找城市时，可以单独用一个程序
// void findlastest(LinkList l,int a1,int b1,int d1)直接找到和打印，不需要返回值



//主程序

#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>

# define C 10
# define Null 0


typedef struct city
{
	char name[C];                                //城市名用数组表示,怎么样配对---先用一个字符表示
	int  x,y;
}City;                                           //l->a.name表示城市名，l->a.x或者l->a.y表示城市坐标

typedef struct Node                              //结构类型定义
{
	City   a;
	struct Node *next;
}Node ,*LinkList;                                //LinkList为结构指针类型

void initlist(LinkList l);
void CreateFromHead(LinkList  l);
Node *Locate(LinkList l,char k[]);
void findlastest(LinkList l,int a1,int b1,int d1);

void main()
{
	LinkList m;
	Node     *r;
	int      n,i,j,z;                            //准备随便输入的坐标i和j，z用于写固定的距离
	char     d[C];                               //d[C]是准备输入城市名的
	m=(Node *)malloc(sizeof(Node));           
	initlist(m);
	CreateFromHead(m);                           //在建立单链表之后，单链表中所有的值都有了城市名和位置坐标
	printf("1.输入一个城市名以用于匹配");
    scanf("%s",&d); 
	printf("\n");                                //输入准备与之匹配的城市名
	n=strlen(d);
    r=Locate(m,d);
	if(r==NULL)  printf("找不到匹配的城市");
        else     printf("%d,%d",r->a.x,r->a.y);
	printf("\n\n\n");
	printf("2.给定一个坐标找与之距离小于d1的城市");
	scanf("%d%d",&i,&j);
	printf("给定一个固定的距离d1=");
	scanf("%d",&z);                              //在输入完后可以直接用一个类似于找key的程序代替查找与之最近的城市
	printf("找到的城市有");
	printf("\n");
	findlastest(m,i,j,z);
}



//1,初始化单链表
void initlist(LinkList l)
{
	l=(LinkList)malloc(sizeof(Node));            //建立头结点
	l->next=Null;                                //建立空的单链表l
}


//2,建立单链表
void CreateFromHead(LinkList  l)
{ 
	Node    *s;
	char 	h[C];                                //输入城市名
	int     x1,y1,i=0,j;                         //在后面输入的时候也是要注意输入的
	l->next=NULL;	
	printf("请输入你要存储的城市信息的城市个数n=");
	scanf("%d",&j);
 	while(i<j)                                
	{   
		printf("请分别任意输入不同的字符");
        scanf("%s",&h);
		printf("请输入两个数字");
		scanf("%d%d",&x1,&y1);                   //想用程序代替的时候怎么输出返回值??
		printf("\n");
		s=(Node *)malloc(sizeof(Node));          //建立新结点s
		strcpy(s->a.name,h);                     //把一个字符串附给另一个字符串（数组）
		s->a.x=x1;
		s->a.y=y1;
		s->next=l->next;                         //将s结点插入表头
		l->next=s;
		i++;
	}

}


//查找关键字相同的数组k
Node *Locate(LinkList l,char k[])
//在带头结点的单链表L中查找其结点值等于key的结点，若找到则返回该结点的位置p，否则返回NULL
{ 
	Node *p;
	p=(Node *)malloc(sizeof(Node));
	p=l->next;                                   //从表中第一个结点开始
	while (p!=NULL)
	{
		if (strcmp(p->a.name,k))                 //比较两个城市名
			p=p->next; 
		else  
			break;                               //找到结点值=k时退出循环
	}
	return p;
} 


//查找距离小于d1的城市
void findlastest(LinkList l,int a1,int b1,int d1)
{
	Node   *p;  
	p=(Node *)malloc(sizeof(Node));
	int    k,w;
	p=l->next;
	while(p!=NULL)
	{			
    	k=(p->a.x-a1)*(p->a.x-a1);               //直接在查找的时候就进行比较，然后记下
    	w=(p->a.y-b1)*(p->a.y-b1);
		if((k+w)<(d1*d1))
		{
			printf("%s",p->a.name);
			printf("\n");
		}
    	p=p->next; 		
	}    
}


/*
探讨：
  
   在查找距离的过程中，程序可改为找最小的距离的城市，则最后一个findlastest子程序要改为
   
void findlastest(LinkList l,int a1,int b1)
{
	Node   *p;
	int    d[C];
	int    g,v,q; char abc[C];                  //用于记下在查找的过程中比较时的城市坐标或者用字符数组记下城市名
	int    k,w,t=0;
	p=l->next;
	while(p!=Null)
	{			
    	k=(p->a.x-a1)*(p->a.x-a1);              //直接在查找的时候就进行比较，然后记下
    	w=(p->a.y-b1)*(p->a.y-b1);
		d[t]=k+w;
		if(!t)  q=d[t];
		if(d[t]<q&&t!=0)
		{
			q=d[t];
			strcpy(abc,p->a.name);
		}
    	p=p->next; 
    	t++;		
	} 
	printf("距离所给位置坐标最小距离的是")；
	printf("%s",abc);
}
*/