这个是我朋友提供的编程代码,虽然经过九九改了一点仍然感觉有点瑕疵~但参考一下是可以的,重点看看求最短距离的
迪杰特斯拉算法~~~~~
程序代码:
/*-------------------------------------------------程序思路--------------------------------------------------------*/
/*首先让用户单个的输入城市信息,然后开辟链表保存该城市信息,然后让用户选择是否再次输入,但用户结束输入时,进入功能选择
页面(1.添加城市,2.删除城市,3.修改城市信息,4.查询所有信息,5.查询一个坐标小于某个距离的城市,6.求最短距离)但完成选择的功
能后,再次返回该页面
/*--------------------------------------------------头文件---------------------------------------------------------*/
#include<stdio.h>
#include<string.h>
#include<conio.h>
#include<windows.h>
#include<stdlib.h>
#include<math.h>
#include<math.h>
#define MAX 999999
/*--------------------------------------------------宏定义---------------------------------------------------------*/
#define KOPENMEMORY (struct Struct *) malloc (sizeof(struct Struct))
/*--------------------------------------------------全局变量-------------------------------------------------------*/
double G[1031][1031];
double dis[1031];
int zy[1031];
int fla = 0;
int p11[1031];
int p111[1031]; //这个用来保存路劲
int f=0;
int i,j;
int zzz[1031]={0}; //用zzz数组来一次记录编号
int count=0;
char userChioce; //接收用户输入的选择
struct Struct
{
int num;
char name[20];
int positionX;
int positionY;
struct Struct * next;
};
struct Struct * head;
struct Struct *p1,*p2,*p3;
/*--------------------------------------------------函数声明-------------------------------------------------------*/
void input();
void addCry();
void delectCry();
void reviseCry();
void inquiryCry();
void inquiryRange();
void seeking(char cryName[20]);
void starting();
/*--------------------------------------------------功能函数-------------------------------------------------------*/
//实现按Enter,并进行清屏
void starting()
{
printf("按Enter键开始输入");
while(userChioce!=13 && userChioce!=10)
{
userChioce=_getch();
}
system("cls");
}
//根据输入的名字寻找到该城市所在的节点
void seeking(char cryName[20])
{
int result;
p2=head;
while(p1->next!=NULL)
{
result=strcmp(p1->name,cryName);
if(result==0)
break;
p2=p1;
p1=p1->next;
}
}
//给用户开始的输入
void input()
{
int i=1;
printf("请输入城市信息(每一次输入一个城市,信息之间用空格隔开)\n");
printf("提示信息包括城市编号,城市名字,x,y坐标\n");
starting(); //调用starting函数
p1=p2=KOPENMEMORY;
head=p1;
while(1)
{
printf("你正在输入第%d城市的信息\n",i++);
scanf("%d %s %d %d",&p1->num,p1->name,&p1->positionX,&p1->positionY);
printf("你是否要继续输入\n1.继续 2.结束\n");
userChioce=_getch();
p2=KOPENMEMORY;
p1->next=p2;
system("cls");
if(userChioce=='2')
{
break;
}
p1=p2;
}
p2=NULL;
p1->next=NULL;
}
//给用户添加城市
void addCry()
{
int i=1;
printf("欢迎进入添加城市的功能页面!!\n");
printf("城市信息包括 编号 名字 X坐标 Y坐标(输入格式: 编号 名字 X坐标 Y坐标)\n");
starting(); //调用starting函数
while(1)
{
system("cls");
printf("这是你的添加的第%d个城市\n",i++);
p3=KOPENMEMORY;
scanf("%d %s %d %d",&p3->num,p3->name,&p3->positionX,&p3->positionY);
system("cls");
p1=head;
while(p1->num < p3->num-1) //把添加内容跳转到编号指定的位置
{
if(p1->next==NULL)
break;
p1=p1->next;
}
if(p1->num < p3->num-1 && p1->next==NULL) //处理输入的编号比已存入的最大编号大2或以上
{
printf("你输入的编号过大\n是否再次输入\n1.重新输入 2.退出\n");
userChioce=_getch();
if(userChioce=='1')
continue;
else
break;
}
if(p3->num==1) //处理添加的城市是第一个城市
{
p3->next=head;
head=p3;
goto goto1;
}
p2=p1->next; //处理除了添加的城市是第一个的所有情况
p1->next=p3;
p3->next=p2;
if(p1->next==NULL)
{
p1->next=p3;
p3->next=NULL;
}
goto1:
p3=p3->next; //把添加的内容的后面的城市的编号加一
while(p3!=NULL)
{
p3->num+=1;
p3=p3->next;
}
printf("你是否要继续添加\n1.继续 2.退出");
userChioce=_getch();
if(userChioce=='2')
break;
}
}
//删除城市的信息
void delectCry()
{
int i=1;
char cryName[20];
system("cls");
printf("欢迎来到删除城市信息的页面\n");
starting(); //调用starting函数
while(1)
{
system("cls");
printf("请输入你第%d个要删除的城市\n",i++);
scanf("%s",cryName);
p1=head;
seeking(cryName); //调用函数seeking进行寻找城市
if(p1->next==NULL && 0==strcmp(p1->name,cryName)) //处理输入的名字是最后一个城市的名字
{
p2->next=NULL;
goto goto3;
}
else if(p1->next==NULL && 0!=strcmp(p1->name,cryName)) //处理输入的名字是已删除或不存在
{
printf("你输入的城市的名字错误\n1.重新输入 2.退出");
userChioce=_getch();
if(userChioce=='1')
continue;
else
break;
}
if(p1==head && 0==strcmp(p1->name,cryName)) //处理输入的名字是第一个城市的名字
{
head=p1->next;
goto goto4;
}
p2->next=p1->next; //处理除了是第一个和最后一个的所有情况
goto3:
goto4:
p2=p2->next;
while(p2!=NULL)
{
p2->num-=1;
p2=p2->next;
}
printf("你输入的城市已删除\n1.继续删除 2.退出");
userChioce=_getch();
if(userChioce=='2')
break;
}
}
//修改城市信息
void reviseCry()
{
char reviseChoice;
char cryName[20];
system("cls");
printf("欢迎来到修改城市信息的页面\n");
starting(); //调用starting函数
while(1)
{
printf("请输入你要修改信息所在的城市的名字\n");
scanf("%s",cryName);
seeking(cryName); //调用seeking函数
while(1)
{
printf("请选择修改的内容\n1.名字 2.X坐标 3.Y坐标\n");
reviseChoice=_getch();
system("cls");
switch(reviseChoice)
{
case '1':printf("请输入新的城市名字\n");scanf("%s",p1->name);break;
case '2':printf("请输入新的X坐标\n");scanf("%d",&p1->positionX);break;
case '3':printf("请输入新的Y坐标\n");scanf("%d",&p1->positionY);break;
default:printf("输入有误\n");break;
}
printf("是否继续修改该城市的信息\n 1.继续 2.退出\n");
Sleep(200);
userChioce=_getch();
if(userChioce=='2')
break;
}
printf("是否要修改别的城市的信息\n1.继续 2.退出\n");
userChioce=_getch();
system("cls");
if(userChioce=='2')
break;
system("cls");
}
}
//输入名字得到坐标
void inquiryCry()
{
int i=1;
char cryName[20];
system("cls");
printf("欢迎进入查询城市坐标的功能!!\n");
starting(); //调用starting函数
while(1)
{
system("cls");
printf("这是你查询的第%d个城市\n",i++);
printf("请输入城市的名字\n");
scanf("%s",cryName);
p1=head;
seeking(cryName); //调用函数seeking
if(p1->next==NULL && 0!=strcmp(p1->name,cryName)) /*避免用户输入已删除或不存在的城市名字*/
{
printf("你的输入有误\n1.重新输入 2.退出");
userChioce=_getch();
if(userChioce=='1')
continue;
else
break;
}
printf("%d %d\n",p1->positionX,p1->positionY);
printf("你是否要继续查询\n1.继续 2.结束");
userChioce=_getch();
if(userChioce=='2')
break;
}
}
//当用户输入一个坐标和时一个距离时,输出距离该坐标小于改距离的所有城市
void inquiryRange()
{
int i=1,cryCount=0;
int x,y,targetDistance;
float realityDistance;
system("cls");
printf("欢迎进入求一个范围内城市的功能\n");
starting(); //调用starting函数
while(1)
{
printf("这是你第%d次输入的坐标和距离(格式:X坐标 Y坐标 距离)\n",i);
scanf("%d %d %d",&x,&y,&targetDistance);
printf("距离(%d,%d)小于%d的城市有:\n",x,y,targetDistance);
p1=head;
while(p1!=NULL)
{
realityDistance=(float )sqrt( (p1->positionX-x) * (p1->positionX-x) + (p1->positionY-y) * (p1->positionY-y) ); //勾股定理算出城市和该坐标的距离
if(realityDistance <= targetDistance)
{
printf("%s\n",p1->name);
cryCount++;
}
p1=p1->next;
}
if(cryCount==0)
{
printf("没有距离(%d,%d)小于%d的城市\n",x,y,targetDistance);
}
printf("是否再次输入\n1.继续 2.退出\n");
userChioce=_getch();
if(userChioce=='2')
break;
system("cls");
}
}
/*--------------------------------------------------主函数---------------------------------------------------------*/
void shuchu();
void juli();
int fun(int s, int ys);
int main()
{
void (*pFunction)( );
input();
printf("你是否要退出\n1.选择服务 2.退出\n");
userChioce=_getch();
if(userChioce=='2')
{
exit(0);
}
while(1)
{
system("cls");
printf("欢迎你的进入!!\n请选择你需要的服务\n");
printf(" 1.添加城市\n 2.删除城市\n 3.修改城市信息\n 4.查询城市坐标\n 5.查询一个坐标小于某个距离的城市\n 6.求最短距离\n 7.显示所有信息");
userChioce=_getch();
switch(userChioce)
{
case '1':pFunction=addCry;break;
case '2':pFunction=delectCry;break;
case '3':pFunction=reviseCry;break;
case '4':pFunction=inquiryCry;break;
case '5':pFunction=inquiryRange;break;
case '6':pFunction=juli;break;
case '7':pFunction=shuchu; break;
}
(*pFunction)( );
}
return 0;
}
int jishu(int n) //判断奇数
{
if(n%2 == 0)
{
return 0;
}
return 1;
}
int zhishu(int n) //判断质数
{
int r=n;
r=r-1;
if(r==0)
{
return 0;
}
if(r==1)
{
return 0;
}
while(r!=1)
{
if(n%r==0)
{
return 0;
}
r--;
}
return 1;
}
void sss()
{
int i=0;
struct Struct *p;
p = head;
while(p != NULL)
{
zzz[i] = p->num;
i++;
p = p->next;
}
}
void juli()
{
int aa, bb, cc;
struct Struct *p;
count=0;
sss(); //将城市标号依次存入数组中
p = head;
while(p != NULL)
{
count++;
p=p->next;
}
for(i = 0; i < 1031; i++) //最多30个城市
{
for(j = 0; j < 1031; j++)
{
G[i][j]=MAX; //一开始2个城市之间的距离为MAX=999999
}
}
for(i = 0; i < count; i++) //穷举城市编号并计算两两之间的距离
{
struct Struct *h;
struct Struct *t;
struct Struct *tt;
int zz=i;
h=head;
//hh=hh->next;
t=h;
while(zz--) { //依次遍历
h=h->next;}
tt = t; //tt每次从第二个节点开始
for(j = 0; j < count; j++)
{
if( h->num==tt->num ) //标号相同,则距离为0
{
G[h->num][tt->num] = 0;
}
else if(jishu(h->num) && jishu(tt->num)) //都是奇数,计算距离
{
G[h->num][tt->num] = sqrt((double)(h->positionX-tt->positionX)*(h->positionX-tt->positionX) + (double)(h->positionY-tt->positionY)*(h->positionY-tt->positionY));
}
else if(zhishu(h->num) && h->num==tt->num-1)
{
G[h->num][tt->num] = sqrt((double)(h->positionX-tt->positionX)*(h->positionX-tt->positionX) + (double)(h->positionY-tt->positionY)*(h->positionY-tt->positionY));
}
else if(zhishu(tt->num) && tt->num==h->num-1)
{
G[h->num][tt->num] = sqrt((double)(h->positionX-tt->positionX)*(h->positionX-tt->positionX) + (double)(h->positionY-tt->positionY)*(h->positionY-tt->positionY));
}
else
{
G[h->num][tt->num] = MAX;
}
tt = tt->next;
}
}
printf("\n");
for(aa = 0; aa < count; aa++)
{
for(bb = 0; bb < count; bb++)
{
fun(zzz[aa],zzz[bb]); //zzz[aa] 表示第aa个城市的标号
printf("%d -> ",zzz[aa]); //dis[zzz[bb]表示zzz[bb]到 zzz[aa]的距离
if(dis[zzz[bb]] > 999990) //无法到达
{
printf(" %d = %lf\n",zzz[bb], dis[zzz[bb]]);
continue;
}
if(dis[zzz[bb]]==0) //自己到自己
{
printf(" %d = %lf\n",zzz[bb], dis[zzz[bb]]);
continue;
}
for(cc = 0; cc < f; cc++)
{
printf("%d -> ", p111[cc]);
}
printf(" %d = %lf",zzz[bb],dis[zzz[bb]]);
printf("\n");
}
printf("\n");
}
system("pause");
}
void shuchu() //输出所有信息函数
{
struct Struct *p;
printf("\n");
printf("%-10s%-10s%-8s%-8s\n","城市编号","城市名","X坐标","Y坐标");
p = head;
while(p!=NULL)
{
printf("%-10d%-10s%-10d%-10d\n", p->num, p->name, p->positionX, p->positionY );
p = p->next;
}
system("pause");
}
int fun(int s, int ys) //这里是迪杰特斯拉算法
{
int k;
int zs=0;
for(i = 0; i < 1031; i++)
{
p111[i] = 0;
}
f=0;
for(i = 0; i < 1031; i++)
{
p11[i] = 0; //每次开始前赋初始值,0表示没进入被找到距离起始点最短的队伍
}
//zy[1031]={0};
for(i = 0; i < 1031; i++)
{
dis[i] = G[s][i];
}
//dis[s] = 0;
p11[s] = 1;
for(i = 1; i < 1031; i++)
{
int min = MAX;
k = -1;
for(j = 0; j < 1031; j++)
{
if(!p11[j] && dis[j] < min)
{
fla = 1;
min = (int)dis[j];
k = j;
if(j==ys)
{
return 9;
}
}
}
if(k != -1)
{
p11[k] = 1;
for(j = 0; j < 1031; j++)
{
if(!p11[j] && (dis[j] > min + G[k][j]))
{
dis[j] = min + G[k][j];
p111[f] = k; //开始保存路劲
f++;
if(k == ys) //找到目标点结束
{
return 1;
}
if(k%2==0) //找到偶数城市点,没用,因为偶数不能出发与其他点相连
{
p111[--f]=0;
}
if(p111[f-1]==p111[f-2]) //这个if是因为在调试过程中会出现相同的城市编号如(3->5->5->5),故此有这个if判断
{
p111[f-1]=0;
f--;
}
}
}
}
else
{
break;
}
}
return 0;
}
[此贴子已经被作者于2017-2-14 09:51编辑过]