5.cpp

求解网络中的最短路径。假设某个计算机网络有n个站点

#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>


struct ElementType				        // 邻接链表结点类型
{
	int num;					        // 站点编号
	unsigned dist;				        // 从参考站点到该站点的距离
	ElementType *next;			        // 指向下一个站点
	ElementType(int n=0,unsigned d=0)
	{
		num=n,dist=d,next=NULL;
	}
};

// 模块声明
ElementType *load(int &number);			   // 从文件读取站点连结信息，得到站点数目number
unsigned plus(unsigned m,unsigned n);	   // 加法模块
void search(ElementType *link,int number); // 搜索功能模块

void main()
{
	int number;								
	ElementType *link;
	link=load(number);					   // 从文件中读取站点连结信息，并写入link中
	search(link,number);				   // 调用搜索模块
}

ElementType *load(int &number)			   // 从文件读取站点连结信息			
{	FILE *fp;
	char filename[10]={"data5.txt"};		   
	int i,num;
	unsigned dist;
	char ch1[40];
	char *ch=ch1;
	ElementType *link,*p1,*p2;
	if((fp=fopen(filename,"r"))==NULL)     // 打开文件data5.txt
	{	cout<<"cannot open this file\n"<<endl;
		exit(0);
	}                                      // 将从文件读入的字符串存入ch数组
	number=fgetc(fp)-48;
	link=new ElementType[number];		   // 获得动态空间，存放站点连结信息
	fscanf(fp,"%s",ch);
	while((i=ch[0]-48)!=0)				   // 将站点间信息写入link[number]							 
	{
		p2=p1=link+i-1;
		ch=strchr(ch,'-')+1;			 
		while(ch[0]!=0)
		{
			num=dist=0;
			while(ch[0]!='*')
			{	num=ch[0]+10*num-48,ch++;
			}
			ch++;
			while(ch[0]!='-'&&ch[0]!=0)
			{	dist=ch[0]+10*dist-48,ch++;
			}
			if(ch[0]!=0)	ch++;
			p1->num=num,p1->dist=dist;
			if(ch[0]==0) 
			{	p1->next=0;
				break;
			}
			p1=new ElementType;
			p2->next=p1,p2=p1;
		}
		ch=ch1;
		fscanf(fp,"%s",ch);
	}
	return link;
}

unsigned plus(unsigned m,unsigned n)		// 加法模块,实现m,n的求和
{	if(m==-1||n==-1) return -1;				// 当m,n中有∞存在，或者
	else if((m/2+n/2)<-1) return m+n;		// 二者的和超过∞时，返回∞	
		 else return -1;					// 否则按照正常运算进行
}

int check(int *t,int number)				// 检查最短路径是否已经找到了
{	int i;									// 是则返回1，否则0
	for(i=0;i<number;i++)
		if(*(t+i)==0) 
			return 0;
	return 1;
}


void search(ElementType *link,int number)	// 查询功能模块
{
	int i,j,source,aim,MinDistSite,flag;			
	unsigned MinDist;						
	unsigned *dist=new unsigned[number];	// 分配动态空间存放最短连通距离
	int *flag1=new int[number],*flag2=new int[number],*PreSite=new int[number];
	ElementType *p=link,*pi;
	cout<<"please input SourceSite and AimSite:";
	cin>>source>>aim;						// 输入源、目的站点
	if(source>number||source<1||aim>number||aim<1)	
	{	cout<<"input error!";				// 检查输入合理性
		exit(0);	
	}
	for(i=0;i<number;i++)					// 初始化判别数组flag1,flag2 
   	{	if(i==aim-1)  
			flag1[i]=1,dist[i]=0;			
        else	
			flag1[i]=0,dist[i]=-1;
		flag2[i]=0;
	}
	do
	{	for(i=0;i<number;i++)				// 遍历已经找到最短路径,且邻接站
		{	if(flag1[i]==0||flag2[i]==1)    // 点中尚有未找到最短路径的站点
				continue;
			flag=0,pi=link+i,MinDist=-1;	// flag记录有无未找到最短距离的邻接站点
											// MinDist存放当前最短距离
			while(pi!=NULL)					// 遍历该站点所有邻接站点
			{	j=pi->num-1;			
				if(flag1[j]==1)				// 避开已经找到最短路径的邻接站点
				{	pi=pi->next;
					continue;
				}
				else flag=1;				
				if(dist[j]>plus(dist[i],pi->dist))
				{	PreSite[j]=i;			// 发现更短路径则更新其PreSite 
					dist[j]=plus(dist[i],pi->dist);
				}		
				if(dist[j]<MinDist)		    // 记录当前最短距离的站点
				{	MinDist=dist[j];
					MinDistSite=j;
				}			
				pi=pi->next;								
			}
			if(flag==0) flag2[i]=1;			// 在判别数组中记录新找到的站点
		}
		flag1[MinDistSite]=1;
	}while(check(flag2,number)==0);			// 当所需最短路径找到时退出查找
	i=source-1;
	cout<<"the shortest path: ";			// 输出最短路径及其距离
	while(i!=aim-1)
	{	cout<<i+1<<"->";
		i=PreSite[i];
	}
	cout<<aim<<", with distance "<<dist[source-1]<<"."<<endl;
}