chaoshixuanzhi.txt

学校超市选址问题,数据结构课程设计 【问题描述】对于某一学校超市

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#define alloc(type) (type*)malloc(sizeof(type)) 
#define MAX_NUM 3.14E38 
#define TRUE 1 
#define FALSE 0 
#define NODE_NUM 8 

struct adj_list{ 
int index; 
char name[10]; 
float len; 
struct adj_list *next; 
}; 
typedef struct adj_list Node; 

//node[]为起始节点数组 
int dijkstra(Node node[],int size,int first,float distance[],int previous[]){ 
//初始化数组 
int *isused=new int[size]; 
for(int i=0;i<size;i++){ 
distance[i]=MAX_NUM; 
isused[i]=FALSE; 
previous[i]=-1; 
} 
//初始起始节点和邻接节点间的距离 
Node *pos=node[first].next; 
if(pos==NULL) 
return 0; 
while(pos!=NULL){ 
distance[pos->index]=pos->len; 
previous[pos->index]=first; 
pos=pos->next; 
} 
//初始化开头节点 
distance[first]=0; 
isused[first]=TRUE; 
int current=first; 
//这里不是对所有的起始节点进行遍历 
for(i=1;i<size;i++){ 
//寻找一个最近开头节点的节点 
float temp=MAX_NUM; 
for(int j=0;j<size;j++){ 
if(isused[j]==FALSE&&distance[j]<temp){ 
current=j; 
temp=distance[j]; 
} 
} 
if(current==first) break; 
isused[current]=TRUE; 
//更新distance[]列表 
pos=node[current].next; 
while(pos!=NULL){ 
if(isused[pos->index]==FALSE&&distance[pos->index]>distance[current]+pos->len){ 
distance[pos->index]=distance[current]+pos->len; 
previous[pos->index]=current; 
} 
pos=pos->next; 
} 
} 
return current; 
} 

//追踪线路 
void printTrace(int lastindex,Node node[],int previous[]){ 
printf("最短路径为:"); 
if(lastindex==0) 
printf("%s",node[0].name); 
else{ 

int pos=lastindex; 
while(true){ 
printf("%s ",node[pos].name); 
if(pos==0) break; 
pos=previous[pos]; 
} 
printf("\n"); 
} 
} 

void generate(Node node[],int size){ 
//先输入顶点名字，然后按格式输入后面的链表节点 
//格式为:name index len 
//输入#结束链表节点的输入,转入其他顶点 
for(int i=0;i<size;i++){ 
printf("%d\n",i); 
scanf("%s",node[i].name); 
node[i].len=0.0; 
node[i].index=i; 
node[i].next=NULL; 
Node *pos=&node[i]; 
char name[10]; 
int index=0; 
float len=0.0; 
while(true){ 
scanf("%s",name); 
if(strcmp(name,"#")==0) break; 
scanf("%d %f",&index,&len); 
Node *no=alloc(Node); 
strcpy(no->name,name); 
no->index=index; 
no->len=len; 
no->next=NULL; 
pos->next=no; 
pos=pos->next; 
} 
} 
} 

void printnode(Node *node){ 
printf("(%d,%s,%g)",node->index,node->name,node->len); 
} 

void showtable(Node node[],int size){ 
for(int i=0;i<size;i++){ 
printnode(node+i); 
Node *pos=node[i].next; 
while(pos!=NULL){ 
printf("->"); 
printnode(pos); 
pos=pos->next; 
} 
printf("\n"); 
} 
} 

int main(){ 
Node node[NODE_NUM]; 
generate(node,NODE_NUM); 
float distance[NODE_NUM]; 
int previous[NODE_NUM]; 
int lastindex=dijkstra(node,NODE_NUM,0,distance,previous); 
printTrace(lastindex,node,previous); 
return 0; 
}