shortest.cpp

GPS地图邻接表结构,可编译,北京大学的

#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 10000

typedef struct {
   float Latitude;     //纬度
   char  Dir_Of_Lat;   //纬度方向
   float Longitude;    //经度
   char  Dir_Of_Lon;   //经度方向
} VexType;  
     
struct EdgeNode;
typedef struct EdgeNode *PEdgeNode;
typedef struct EdgeNode *EdgeList;         

struct EdgeNode {
   int adjvex;               //相邻点在图中位置
   PEdgeNode nextarc;       //指向下一个表节点
   float weight;             //权值，表示路程
};

typedef struct {
   VexType vertex;           //顶点信息
   EdgeList edgelist;        //指向表节点的头指针
} VexNode;

typedef struct {
   int n;                    //顶点个数
   VexNode vexs[MAXVEX];     //顶点数组
} GraphList;


/*************************************
加入顶点算法
**************************************/
void addvex(GraphList *p, float la, float lo, char dla, char dlo){
   VexNode * temp;
   VexNode * pvexs;
   temp = (VexNode *)malloc(sizeof(VexNode)); 
   temp->vertex.Latitude = la;
   temp->vertex.Longitude = lo;
   temp->vertex.Dir_Of_Lat = dla;
   temp->vertex.Dir_Of_Lon = dlo;
   temp->edgelist = NULL;  
   pvexs = p->vexs;
   
   if(pvexs)
      pvexs ++; 
   *pvexs = *temp;     
}


/*************************************
 边的插入算法
*************************************/
void insert(GraphList *p, int a, int b, float w){ 
   EdgeList pp;
   PEdgeNode temp;
   temp = (PEdgeNode)malloc(sizeof(EdgeNode));
   temp->adjvex = b;
   temp->nextarc = NULL;
   temp->weight = w;
   pp = p->vexs[a].edgelist;
   
   if(pp ==NULL)
      p->vexs[a].edgelist = temp;
   else{
      while(pp->nextarc != NULL)
         pp = pp->nextarc;
      pp->nextarc = temp;
   }
}


/***************************************
邻接表的构造
****************************************/
GraphList* makeList(GraphList *p,int num){
   
   p = (GraphList *)malloc(sizeof(GraphList));
   p->n = num;  
   while(num--){
      printf("Please enter vertex's Latitude, Longitude,direct of Latitude and direct of Longitude:");
      float la, lo;
      char dla, dlo;
      scanf("%f, %f, %c, %c", &la, &lo, &dla, &dlo);
      
      printf("The variable you enter are %f, %f, %c, %c", la, lo, dla, dlo);
      addvex(p, la, lo, dla, dlo);
   }
      printf("Please enter the two vertex's number in the array, and the weight:");
      int a, b, w;
      scanf("%d, %d, %f", &a, &b, &w);   
      insert(p, a, b, w);
          
   return p;
}

int main(){
   GraphList *p;
   int num = 1;
  
   p = makeList(p, num);
   for(int m = 0; m < num; m++){
      printf("%d, %f, %f, %c, %c", p->n, p->vexs[m].vertex.Latitude,
      p->vexs[m].vertex.Longitude, p->vexs[m].vertex.Dir_Of_Lon, p->vexs[m].vertex.Dir_Of_Lat); 
   }
   getchar();getchar();getchar();
   getchar();getchar();getchar();
   return 0;
}