text1.c

数据结构168个实验程序,很全面

#include <stdio.h>
#define MAX 20    //最大顶点个数
#define up 10000  //定义一个无穷大的值
int cost[MAX][MAX];//
int dist[MAX],n;
struct
{
	int num;
	int pnode[MAX];
}path[MAX];    
void creatgraph()    //创建带权无向图
{
	int i,j,s,e,len,contin=1;
	printf("顶点个数：");
	scanf("%d",&n);
	for (i=0;i<n;i++)
	{
		for (j=0;j<n;j++)
			cost[i][j]=cost[j][i]=up;
		cost[i][i]=0;
	}
	printf("输入顶点，顶点，各边，以0，0，0表示结束：\n");
	i=1;
	while (contin==1)
	{
		printf("\t第",i,"条边——顶点，顶点，边长：");
		scanf("%d %d %d",&s,&e,&len);
		if (s==0 && e==0 && len==0)
			contin=0;
		else if (s>=0 && s<n && e>=0 && e<n && len>0)
		{
			cost[s][e]=len;
			i++;
		}
		else
			printf("\t\t边值错误，重新输入：\n");
	}
}
void shortdjs()  //求最短路径
{
	int s[MAX];
	int mindis,dis,i,j,v0=0,u;
	for (i=0;i<n;i++)
	{
		dist[i]=cost[v0][i];
		path[i].pnode[0]=v0;
		path[i].num=0;
        s[i]=0;
	}
	s[v0]=1;
	for (i=1;i<n;i++)
	{
		mindis=up;
		for (j=1;j<n;j++)
			if (s[j]==0 && dist[j]<mindis)
			{
				u=j;
				mindis=dist[j];
			}
			s[u]=1;
			for (j=1;j<n;j++)
				if (s[j]==0)
				{
					dis = dist[u]+cost[u][j];
					if (dist[j]>dis)
					{
						dist[j]=dis;
						path[j].num++;
						path[j].pnode[path[j].num]=u;
					}
				}
				path[i].num++;    //将终点i添加到路径中
				path[i].pnode[path[i].num]=i;
				}
}
void dispath()//输出最短路径 
{
	int i,j;
	printf("\n 从V0到各顶点的最短路径长度如下：\n");
	printf("\t    起点—终点        最短长度        最短路径\n");
	printf("\t★★★★★★★★★☆☆☆☆☆☆☆★★★★★★★★★\n");
	for (i=1;i<n;i++)
	{
		printf("\t (V0-V%d)",i);
		if (dist[i]<up)
			printf("                %d                 (",dist[i]);
		else
			printf("∞     (");
		for (j=0;j<path[i].num;j++)
			printf("V%d ,",path[i].pnode[j]);
		printf("V%d )\n",path[i].pnode[path[i].num]);
	}
}
main()
{
	creatgraph();
	shortdjs();
	dispath();
}