| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2172 人关注过本帖, 1 人收藏
标题:这题的最短路线怎么求~
取消只看楼主 加入收藏
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
结帖率:99.25%
收藏(1)
已结贴  问题点数:50 回复次数:12 
这题的最短路线怎么求~
将若干城市信息存入一个带头结点的单链表,结点中的城市信息包括,城市名,城市的位置坐标,要求能够利用城市名和位置坐标进行有关添加,插入,删除,修改及查询成操作。要求:1给定一个城市名,返回其坐标 。2给定一个位置坐标P和一个距离d,返回所有与P的距离小于等于d的城市。 3城市之间奇数相通,所有质数与质数+1城市相通。求两城市的最短路线。

这题其它的问题九九可以自己解决,就是那个最短路线不是很会理解~感觉题目提示信息不是很明确~帮忙看看~

据说这是数据结构的问题,应该可以找到原题和答案的,就是那个求两个城市的最短路线那里卡壳了~帮忙看看~
搜索更多相关主题的帖子: 提示信息 
2017-02-12 14:42
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
PS:我把求最短路径理解成两种意思~
1:求所有任意连通城市之间的最短距离
2:求指定两个城市所有连通路径之间的最短路径~
那个出题给九九的竟然要两种可能都试试~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-02-12 15:29
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 2楼 九转星河
PS感觉相通之间的城市太多了~稍微逻辑推理就知道两个直接相通的城市之间直线距离最短~如果两个城市相通~最多不会超过3段~感觉出题的应该是以第一种理解为主~不过第二种情况是有算法值得学习的~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-02-12 16:14
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 4楼 kin3z
我看到的就是1楼的~别人转发来给我看的~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-02-12 18:12
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 6楼 kin3z
好的,那麻烦你了~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-02-12 19:12
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
自从电脑修好后,九九就要准备学习数据结构了,在学数据结构之前先要把链表基础打好~
最近在写链表操作的时候受了yangfrancis和x版主的启发,所以自己打算重新写写~

下面第一波已经完善了链表的创建~
有什么建议可以提出一下,好让九九去完善~
还是以拿最短距离为例~
程序代码:
/*
将若干城市信息存入一个带头结点的单链表,
结点中的城市信息包括,城市名,城市的位置坐标,要求能够利用城市名和位置坐标进行有关
添加,插入,删除,修改及查询成操作。
要求:
1给定一个城市名,返回其坐标 。
2给定一个位置坐标P和一个距离d,返回所有与P的距离小于等于d的城市。
3城市之间奇数相通,所有质数与质数+1城市相通。求两城市的最短路线。
*/
#include<stdio.h>
#include<stdlib.h>
#include<windows.h>
#include<conio.h>
#include<string.h>

#define LEN sizeof(Node)
#define S(a) sizeof(a)/sizeof(*a)
#define FIND(a,b)b-a

typedef struct Node
{
    int num;
    char name[20];
    double x;
    double y;
    struct Node* next;
}Node;

typedef void FUN(Node** head);
FUN fun_0,fun_1,fun_2,fun_3,fun_4,fun_5;

void cr_Node(Node **head);
void insert(Node** head,Node* ins,Node* p_ins);//插入节点----ins 插入节点的地址 p_ins被插入节点的地址

void menu();

void find_member(Node* head,int flag,int (*pfun1)(const void* p1,const void* p2));

void creat(Node** p);//创建节点
void date(Node* head);//输入数据
void my_scanf(const void *s,const void *p);
void print(Node* p);
void print_one(Node* p);
void del(Node* p);//删除节点
void my_free(Node* head);//释放节点
void change();

int my_continue(const void* p);
int my_strcmp(const void* p1,const void* p2);

int n=0;

void menu();

int main()
{
    
    Node* head=NULL;

    typedef void (*COM)();
    COM com[]={fun_0,fun_1,fun_2,fun_3,fun_4,fun_5};
    char c=0;

    while (c!=S(com))
    {
        menu();
        c=getch()-'0'-1;

        system("cls");

        if (c>-1&&c<S(com))
        {
            com[c](&head);
            fflush(stdin);
            printf("\n即将返回菜单\n");
            system("pause");
            system("cls");
        }
    }

    my_free(head);//清空链表要养成习惯(受x版主的影响)

    return 0;
}
void fun_0(Node** head)
{
    cr_Node(head);
}
void fun_1(Node** head)
{
    do
    {
        find_member(*head,0,my_strcmp);
    }while (my_continue("还需要继续查找吗(Y||N)?\n"));
}
void fun_2(Node** head)
{

}
void fun_3(Node** head)
{

}
void fun_4(Node** head)
{

}
void fun_5(Node** head)
{

}
void menu()
{
    system("cls");
    printf("**********<<城市管理系统>>**********\n");
    printf("1:创建(添加数据)\n");
    printf("2:查找数据\n");
    printf("3:插入数据\n");
    printf("4:删除数据\n");
    printf("5:修改数据\n");
    printf("6:退出\n");
}
void cr_Node(Node** head)
{
    Node* p=*head;

    while (*head&&p->next)
        p=p->next;

    do
    {
        Node* p2=p;

        system("cls");

        creat(&p);//创建节点
        date(p);//输入数据
        insert(head,p,p2);//插入节点到链表
    }while (my_continue("还需要继续创建城市数据吗(Y||N)?\n"));
}
void creat(Node **p)
{
     *p=(Node* )malloc(LEN);
     (*p)->next=NULL;

}
void insert(Node** head,Node* ins,Node* p_ins)
{
    if (p_ins==NULL)//当p_ins为NULL时属于头插(空链表属于头插)
    {
        ins->next=*head;
        *head=ins;
        return ;
    }

    ins->next=p_ins->next;
    p_ins->next=ins;
}
void print(Node* head)
{
    Node* p=head;

    printf("编号           名称          x坐标    y坐标\n");
    while (p)
    {
        print_one(p);
        p=p->next;
    }
}

void print_one(Node* p)
{
    printf("%-10d%-20s%-8.2f%-8.2f\n",p->num,p->name,p->x,p->y);
}
void my_free(Node* head)
{
    Node* p=head;
    
    if (head==NULL)
        return ;

    while (p->next)
    {
        p=p->next;
        free(head);
        head=p;
    }

    free(head);
}
void date(Node* p)
{
    void *pr[][3]=
    {
        "请输入第城市的编号:\n","%d",&p->num,
        "请输入城市的名称:\n","%20[^\n]%*c",p->name,
        "请输入城市的x坐标:\n","%lf",&p->x,
        "请输入城市的y坐标:\n","%lf",&p->y,
    };

    int i=0;

    ++n;
    printf("正在创建第%d个城市的数据\n",n);

    for (i=0;i<S(pr);++i)
    {
        printf(pr[i][0]);
        my_scanf(pr[i][1],pr[i][2]);
    }
}

void my_scanf(const void* s,const void* p)
{
    while (scanf(s,p)!=1)
    {
        printf("输入数据有误,请重新输入数据\n");
        fflush(stdin);
    }

    fflush(stdin);
}
int my_continue(const void* p)
{
    char c=0;
    printf(p);

    while (1)
    {
        int k=0;
        c=getch();
        k=((c=='y'||c=='Y'||c=='n'||c=='N'));
        if (k)
            return (c=='Y'||c=='y');

        printf("输入只能在Y或N之间选择,请重新输入:\n");
    }
}

void find_member(Node* head,int flag,int (*pfun1)(const void* p1,const void* p2))
{
    Node* p=head;
    char name[20]={0};
    int k=(int* )head->name-(int* )head;
    system("cls");
    printf("请输入查找城市的名称:\n");
    my_scanf("%20[^\n]%*c",name);

    while (p)
    {
        if ((*pfun1)(name,(int* )p+k)==flag)
        {
            printf("编号           名称          x坐标    y坐标\n");
            print_one(p);
            return ;
        }
        p=p->next;
    }

    printf("没有找到城市的数据\n");

}
void del(Node* p)//删除节点
{

}
int my_strcmp(const void* p1,const void* p2)
{
    return strcmp(p1,p2);

}
void change()
{}


九九会做多少就做多少~代更~

其实九九原意是想强化链表操作的~感觉前期菜单功能没有处理好~后期制作才补上~看来要大改一下主体结构了~这次就当积累一下经验~下次更时间也许较长~九九还要养成功能系统化和尽量增强功能通用性的习惯~下次更的时间也许较长了~

[此贴子已经被作者于2017-2-14 20:01编辑过]

收到的鲜花
  • azzbcc2017-02-13 09:23 送鲜花  5朵   附言:void creat(Node** p)或者 Node *create().
  • 炎天2017-02-14 01:23 送鲜花  6朵   附言:好文章

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-02-12 23:37
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
9楼第二更~
有点像我曾经写那个大型学生信息管理系统的味道了~

[此贴子已经被作者于2017-2-13 10:34编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-02-13 10:19
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
第三更~是时候要建立字库与完善菜单了~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-02-13 20:51
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
这个是我朋友提供的编程代码,虽然经过九九改了一点仍然感觉有点瑕疵~但参考一下是可以的,重点看看求最短距离的迪杰特斯拉算法~~~~~

程序代码:
/*-------------------------------------------------程序思路--------------------------------------------------------*/
/*首先让用户单个的输入城市信息,然后开辟链表保存该城市信息,然后让用户选择是否再次输入,但用户结束输入时,进入功能选择
页面(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编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-02-14 09:26
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 12楼 kin3z
哦,九九是经过测试才把代码贴出来的,那个printf(p)p是const void* 型指针,这个叫可变输出格式~~~~~是为了增强程序的通用性用的,随着p指针的不同指向输出内容不同,但都是在my_continue函数里面完成的,这样能在一个my_conitnue调用函数实现不同内容的输出,从而增加了程序的通用性~~~~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-02-14 09:58
快速回复:这题的最短路线怎么求~
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.030271 second(s), 10 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved