aoe.cpp

aoe 算法实现以及具体程序框架

#include<stdio.h>
#include<conio.h>
#include<process.h>
#include<malloc.h>//包含头文件
#define MAXSIZE 40//预设最大顶点数为30
typedef struct bian//邻顶点的结构体
{
	int top;//传说中的顶点信息
	int value;//权值
	struct bian *next;//下一个指针
} ledge;
typedef struct aoe//aoe顶点结构体
{
	int in;//传说中的入度
	bian *next;//链表指针
} node;
node top[MAXSIZE];//定义顶点数组

int datain[10][3]={{1,2,3},{1,3,2},{2,4,4},{3,4,3},{2,5,8},{3,6,7},{4,5,4},{4,6,2},{5,7,9,},{6,7,6}};//一组已输入的数据
int initlink(int number)//顶点数组初始化函数
{
	int temp;
	if(number>MAXSIZE)//如果输入顶点数大于预定数报错
	{
		printf("大兄弟,我是电脑不是神,况且神也判断不了那么大的东西啊\n");
		return 0;
	}
	for(temp=0;temp<number;temp++)
	{
		top[temp].in=0;//初始化入度
		top[temp].next=NULL;//初始化邻接链表
	}
	return 1;
}
int createlink(int start,int end,int value,int max)//创建邻接链表关系函数
{
	ledge *l;
	if((start>max)||(end>max)||(start==end)||(value==0))//如果输入的数据有误则报错
	{
		printf("小朋友，我不是神我是电脑，况且神也不能拿错误数据算对\n %d %d %d",start,end,value);
		return 0;
	}
	l=(ledge *)malloc(sizeof(ledge));//分配空间
	l->top=--end;
	l->value=value;
	l->next=top[--start].next;
	top[start].next=l;
	top[end].in++;//将链表挂入顶点表后
	return 1;
}
int findlongway(int maxnumber)//搜索最长路径函数
{
	int tempa,tempb,tempc,pd;//tempa,tempb,tempc为常用多功能变量
  int hi,lo,lway[MAXSIZE],sway[MAXSIZE];//hi为队顶 lo为底 lway数组为储存最长路径 sway数组储存最短路径
  int topsave[MAXSIZE];//队列
  ledge *temp;//多动能变量
  hi=lo=-1;//初始化队列
  for(tempa=0;tempa<maxnumber;tempa++)//初始化最长路径
	  lway[tempa]=0;
  for(tempa=0;tempa<maxnumber;tempa++)//找出入度为0的点入队
	  if(!top[tempa].in)
	  {
		  topsave[++hi]=tempa;
	  }
	  pd=0;//判断条件初始化
	  while(hi!=lo)//如果队列有数据
	  {
		  tempb=topsave[++lo];
		  temp=top[tempb].next;
		  pd++;
		  while(temp)
		  {
			  tempc=temp->top;
			  top[tempc].in--;
			  if(lway[tempb]+temp->value>lway[tempc])
				  lway[tempc]=lway[tempb]+temp->value;//将节点按照逻辑先后关系储存到队列中并求最长时间
			  if(!top[tempc].in)
			  {
				  topsave[++hi]=tempc;
			  }
			  temp=temp->next;
		  }
	  }
	  if(pd<maxnumber)//根据入队的顶点数判断有无存在回路
	  {
		  printf("地图网络中出现回路,请检查清楚重新输入");
		  return 0;
	  }
	  for(tempa=0;tempa<maxnumber;tempa++)
	  {
		  sway[tempa]=lway[maxnumber-1];
	  }
	  for(tempa=maxnumber-2;tempa>=0;tempa--)//判断并求最短时间
	  {
		  tempb=topsave[tempa];//反向运用刚生成的队列
		  temp=top[tempb].next;
		  while(temp)
		  {
			  tempc=temp->top;
			  if(sway[tempc]-temp->value<sway[tempb])
				  sway[tempb]=sway[tempc]-temp->value;
			  temp=temp->next;
		  }
	  }
	  printf("最佳攻击顺序是:");
	for(tempb=0;tempb<maxnumber;tempb++)
	{
		tempa=topsave[tempb];//从队列中得出先后顺序并打印
		if(sway[tempa]==lway[tempa])
		printf("%d(关键)在%d操作--->",tempa+1,lway[tempa]);
	  else printf("%d最早在%d操作,最迟在%d--->",tempa+1,lway[tempa],sway[tempa]);
	}
	printf("end\n完成战役需要的总时间是%d",lway[tempa]);
	return 1;
}

	  void main()
{
	int datamax;//顶点个数
	int tempa,a,b,c;//tempa循环变量 a,b,c传说中最经典的多功能变量
	char key;//按键值
	ledge *first,*second;//first，second在释放内存时用到
	printf("魔兽辅助分析器\n");
	printf("选择数据输入方式 :\n a.读取程序内地图数组\n b.重新输入\n");//选择输入方式
	key=getch();//判断输入
	while((key!='a')&&(key!='b'))
	{
		key=getch();
	}
	if(key=='a') 
	{
		datamax=7;
		initlink(datamax);
		for(tempa=0;tempa<10;tempa++)//自动输入内定数组
		{
			createlink(datain[tempa][0],datain[tempa][1],datain[tempa][2],datamax);
		}
	}
	else
	{
		printf("请输入您的地图规模（整数）：");
		scanf("%d",&datamax);
		if(!initlink(datamax))exit(0);
		printf("请输入您的地图信息（格式请参照说明书）:");
		scanf("%d %d %d",&a,&b,&c);
		while((a*b)!=0)//手工输入如果输入0则结束
		{
			createlink(a,b,c,datamax);
			printf("请继续输入：");
			scanf("%d %d %d",&a,&b,&c);
		}
	}
	findlongway(datamax);//调用aoe函数
	for(tempa=0;tempa<datamax;tempa++)//释放程序分配空间
	{
		first=top[tempa].next;
		while(first)
		{
			second=first->next;
			if(!second)
			{
				free(first);
				first=second;
			}
			else
			{
				free(first);
				first=0;
			}
		}
	}
	getchar();//让屏幕停下来
}