[数据结构与算法]AOE网的实现（十字链表存储结构）

起因是老师布置了一个作业，在网上看了下，大家都是用邻接表+栈写的。于是有了个想法，使用十字链表和数组来做，主要是想锻炼一下指针的使用，加强指针的学习。

先放输出结果图

AOE网的建立

?

任务的完成

鄙人还是学生，认为写的不好请不要喷，发这篇文章也是想养成写博客的习惯，欢迎大佬们在评论区指点一二。

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;


typedef char Vertextype;	//顶点信息类型
typedef int  Edgetype;		//孤的权重类型
typedef bool Status;		//状态值的类型
typedef int SElemType;		//栈的类型

//设定状态值
#define OK		1
#define ERROR	0

#define MAX_VERTEX 30			//设定最大顶点数目
#define STACK_INIT_SIZE 10		//栈存储空间初始分配量
#define STACKINCREMENT 2		//栈存储空间分配增量


//定义孤结点
//属性说明：tailvex存放孤尾顶点的序号，headvex存放弧头顶点的序号
//			headlink指向弧头相同的下一个孤结点，tailink指向弧尾相同的下一个弧结点
//			weight存放当前弧的权重
typedef struct EdgeNode {
	int tailvex, headvex;					
	struct EdgeNode *headlink, *taillink;	
	Edgetype weight;
}EdgeNode;


//定义顶点结点
//属性说明：data存放当前顶点的信息
//			firstin指向以当前顶点为弧头的第一个孤结点，firstout指向以当前顶点为弧尾的第一个弧结点
typedef struct VertexNode {
	Vertextype data;
	EdgeNode *firstin, *firstout;
}VextexNode;


//定义图
//属性说明：Otglist[]是一个顶点数组
//			numVextexes是总顶点数目，numEdges是总孤数
typedef struct GraphOtglist {
	VextexNode Otglist[MAX_VERTEX];
	int numVextexes, numEdges;
}GraphOtglist;

//定义栈
//属性说明：base是栈底指针，top是栈顶指针，stacksize是当前已分配的存储空间，以元素为单位

typedef struct SqStack {
   SElemType *base; 
   SElemType *top; 
   int stacksize; 
}SqStack;


//==========================================================================================


//函数声明
Status CreatGraph(GraphOtglist &G);				//构造带权有向图G
int LocateVex(GraphOtglist G, Vertextype n);	//查找data为n的顶点在顶点数组的下标
void FindInDegree(GraphOtglist G,int r[]);		//求出图G中各顶点的入度并存储在数组r中（一一对应）
void Display(GraphOtglist G);					//打印图G
void TopoSort(GraphOtglist G, int r[]);					//输出图G顶点的拓扑排序


//定义查找顶点元素下标函数
//函数说明：传入一个图和一个顶点信息，到图中找到相同顶点信息的顶点
//			若找到对应顶点，则返回该顶点的数组下标
//			若没有找到对应顶点，则提示错误，图中不存在该顶点，并返回-1
int LocateVex(GraphOtglist G, Vertextype n) {
	int i;
	for(i = 0; i < G.numVextexes; i++) {
		if(G.Otglist[i].data == n)
			return i;
	}
	printf("图G中不存在顶点%c\n", n);
	return -1;
}


//定义构造带权有向图函数（十字链表）
//函数说明：由用户输入顶点总数和弧总数，随后判断输入值是否
//			若不合理则提示错误并结束函数；
//			若合理则提示用户对图中各顶点和各弧进行信息输入
Status CreatGraph(GraphOtglist &G) {
	int i, j, k, w;
	Vertextype v1, v2;
	EdgeNode *e;
	
	//接受顶点数和弧数，并对其进行判断
	//若顶点数超出设定的顶点最大数目，提示错误并结束函数运行
	printf("请输入顶点数和孤数（以空格作为间隔）: ");
	scanf("%d",&G.numVextexes);
	scanf("%d",&G.numEdges);
	if(G.numVextexes > MAX_VERTEX) {
		printf("错误，顶点数超过最大设定数目%d\n", MAX_VERTEX);
		return ERROR;
	}

	//若弧数超过对应顶点最大值，提示错误并结束函数运行
	if(G.numEdges > G.numVextexes * (G.numVextexes - 1)) {
		printf("错误，%d个顶点最多可以拥有%d条弧\n", G.numVextexes, G.numVextexes * (G.numVextexes - 1));
		return ERROR;
	}

	//将顶点信息存入顶点数组元素的"data域"
	//并将"firstin域"和"firstout域"初始化为"NULL"
	for(i = 0; i < G.numVextexes; i++) {
		printf("请输入第%d个顶点的信息：", i + 1);
		cin >> G.Otglist[i].data;
		G.Otglist[i].firstin = NULL;
		G.Otglist[i].firstout = NULL;
	}

	//采用插入法将弧的地址插入到各顶点数组元素的"firstin域"和"firstout域"
	//若输入的弧头顶点或弧尾顶点不存在，则提示用户重新输入
	for(k = 0; k < G.numEdges; k++) {
		printf("请输入第%d条弧及其权重(使用空格分隔)：", k + 1);
		cin >> v1 >> v2 >> w;
		i = LocateVex(G,v1);
		j = LocateVex(G,v2);

		if(i == -1 || j == -1) {
			printf("请重新输入\n");
			k--;
			continue;
		}
		
		//先构建弧结点，确认构建完成后进行赋值，最后插入到弧链表
		e = NULL;
		e = (EdgeNode*)malloc(sizeof(EdgeNode));
		if(!e) {
			printf("第%d条弧空间分配不足\n",k + 1);
			return ERROR;
		}
		e->tailvex = i;
		e->headvex = j;
		e->weight = w;
		e->taillink = G.Otglist[i].firstout;
		G.Otglist[i].firstout = e;
		e->headlink = G.Otglist[j].firstin;
		G.Otglist[j].firstin = e;
	}
	printf("\n图G构建完成\n");
	return OK;
}

//定义输出图函数
//函数说明：输出有向图G
void Display(GraphOtglist G) { 
	printf("下列是图G：\n");
	int i;
	EdgeNode *p;
	printf("共%d个顶点,%d条弧:\n",G.numVextexes,G.numEdges);
	for(i=0;i<G.numVextexes;i++) {
		printf("顶点%c: 以%c为弧尾的弧头结点: ",G.Otglist[i].data, G.Otglist[i].data);
		p=G.Otglist[i].firstout;
		while(p) {
		printf("%c ",G.Otglist[p->headvex].data);
		if(p->weight)
			printf("弧信息: %d ",p->weight);
		p = p->taillink;
		}
	printf("以%c为弧头的弧尾结点: ", G.Otglist[i].data);
    p = G.Otglist[i].firstin;
    while(p) {
		printf("%c ",G.Otglist[p->tailvex].data);
		if(p->weight) 
			 printf("弧信息: %d ",p->weight);
		p = p->headlink;
     }
     printf("\n");
   }
 }

//定义各顶点的入度函数
//函数说明：传入一个有向图和一个数组，求出各顶点的入度并存入数组中
void FindInDegree(GraphOtglist G,int r[]) {
	int i;
	EdgeNode *p;
	for(i = 0; i < G.numVextexes; i++)
		r[i] = 0; // 赋初值
	for(i = 0; i < G.numVextexes; i++) {
		p = G.Otglist[i].firstin;
		while(p) {
			r[p->headvex]++;
			p=p->headlink;
		}
	}
}


//定义拓扑排序函数
//函数说明：传入一个图（十字链表），输出该图的拓扑排序
void TopoSort(GraphOtglist G,int r[]) {
		int k, count;
		EdgeNode *p;
		int indegree[MAX_VERTEX];	//用于记录各顶点的入度
		FindInDegree(G, indegree);	//调用FindInDegree函数，使indegree中有各顶点的入度了
		for(k = 0,count = 0; count != G.numVextexes; k++) {
			if(indegree[k] == 0) {
				r[count] = k;
				count++;						//存储一个顶点，count加1
				indegree[k] = -1;				//将当前顶点的入度改为-1，表示已经输出过了
				p = G.Otglist[k].firstout;		
				while(p) {
					indegree[p->headvex]--;
					p = p->taillink;
				}
				k = 0;
			}
		}
}


//定义顶点时间最早开发时间函数
//函数说明：传入一个最早开发时间数组，一个带权有向图
//			输出相应的顶点事件最早开发时间
void ETVERTEX(int etv[], GraphOtglist G) {
	int tp[MAX_VERTEX], indegree[MAX_VERTEX], compare[MAX_VERTEX] = {0};
	int i, j, x, m;
	EdgeNode *p;
	FindInDegree(G, indegree);
	TopoSort(G, tp);
	for( i = 0; i < G.numVextexes; i++) {
		//如果是源点，直接输出"0"
		if(indegree[i] == 0) {
			etv[tp[i]] = 0;
			continue;
		}

		//找当前的最长路径，即最早开发时间
		p = G.Otglist[tp[i]].firstin;
		j = 0;
		while(p) {
			compare[j]  = etv[p->tailvex] + p->weight;
			j++;
			p = p->headlink;
		}

		for(x = 0, m = 0; x < j; x++) {
			m = (m > compare[x]) ? m : compare[x];
			etv[tp[i]] = m;
		}
	}


}


//定义各顶点的出度函数
//函数说明：传入一个有向图和一个数组，求出各顶点的出度并存入数组中
void FindOutDegree(GraphOtglist G,int r[]) {
	int i;
	EdgeNode *p;
	for(i = 0; i < G.numVextexes; i++)
		r[i] = 0; // 赋初值
	for(i = 0; i < G.numVextexes; i++) {
		p = G.Otglist[i].firstout;
		while(p) {
			r[p->tailvex]++;
			p=p->taillink;
		}
	}
}


//定义顶点时间最晚开发时间函数
//函数说明：传入一个最晚开发时间数组，终点的最早开发时间，一个带权有向图
//			输出相应的顶点事件最晚开发时间
void LTVERTEX(int ltv[], int last, GraphOtglist G) {
	int tp[MAX_VERTEX], outdegree[MAX_VERTEX], compare[MAX_VERTEX] = {0};
	int i, j, x, m;
	EdgeNode *p;
	FindOutDegree(G, outdegree);	
	TopoSort(G, tp);
	for( i = G.numVextexes - 1; i >= 0; i--) {
		//如果是终点,最晚开发时间和最早开发时间相同
		if(outdegree[i] == 0) {
			ltv[tp[i]] = last;
			continue;
		}
	
		//从compare数组中找最小的值作为当前顶点的最迟开发时间
		p = G.Otglist[tp[i]].firstout;
		j = 0;
		while(p) {
			compare[j]  = ltv[p->headvex] - p->weight;
			j++;
			p = p->taillink;
		}

		for(x = 0, m = 9999; x < j; x++) {
			m = (m < compare[x]) ? m : compare[x];
			ltv[tp[i]] = m;
		}
	}
}


//定义活动（弧）的最早开发时间函数
//函数说明：传入事件最早开发时间数组etv和带权有向图G
//			输出各活动的最早开发时间，即弧尾顶点的最早开发时间
void ETEDGE(int etv[], GraphOtglist G) {
	int i;
	EdgeNode *p;
	printf("各活动的最早开发时间:\n");
	for(i = 0; i < G.numVextexes; i++) {
		p = G.Otglist[i].firstout;
		while(p) {
			printf("  %c-%c: %d", G.Otglist[p->tailvex].data, G.Otglist[p->headvex].data, etv[p->tailvex]);
			p = p->taillink;
		}
	}	
	printf("\n\n");
}


//定义活动（弧）的最迟开发时间函数
//函数说明：传入事件最迟开发时间数组ltv和带权有向图G
//			输出各活动的最迟开发时间，即弧头顶点的最迟开发时间减去权值
void LTEDGE(int ltv[], GraphOtglist G) {
	int i;
	EdgeNode *p;
	printf("各活动的最迟开发时间:\n");
	for(i = 0; i < G.numVextexes; i++) {
		p = G.Otglist[i].firstout;
		while(p) {
			printf("  %c-%c: %d", G.Otglist[p->tailvex].data, G.Otglist[p->headvex].data, ltv[p->headvex] - p->weight);
			p = p->taillink;
		}
	}
	printf("\n\n");
}

//定义活动的时间余量函数
//函数说明：传入事件最早开发时间数组etv、事件最迟开发时间数组ltv以及带权有向图G
//			输出各活动的时间余量
void LEISURE(int etv[], int ltv[], GraphOtglist G) {
	int i;
	EdgeNode *p;
	printf("各活动的时间余量:\n");
	for(i = 0; i < G.numVextexes; i++) {
		p = G.Otglist[i].firstout;
		while(p) {
		   printf("  %c-%c: %d",G.Otglist[p->tailvex].data, G.Otglist[p->headvex].data, ltv[p->headvex] - p->weight - etv[p->tailvex]);
			p = p->taillink;
		}
	}
}


//定义关键路径比较函数
//函数说明：传入关键路径数组ch1和关键路径数组ch2，若相同则返回-1，若不同则返回1
int COMPARE(char ch1[], char ch2[]) {
	int i,j;
	for(i = 0; ch1[i] != '#'; i++);
	for(j = 0; j < i; ) {
		if(ch1[j] == ch2[j]) {
			j++;
			continue;
		}
		return -1;
	}
	return 1;
}


//定义关键路径函数
//函数说明：传入事件最早开发时间数组etv、事件最迟开发时间数组ltv、保存关键路径数组th和带权有向图G
void CRITICALPATH(int etv[], int ltv[], char th[], GraphOtglist G) {
	int tp[MAX_VERTEX];
	int i,k;
	TopoSort(G, tp);
	for(i = 0, k = 0; i < G.numVextexes; i++) {
		if(etv[tp[i]] != ltv[tp[i]]) {
			continue;
		}
		th[k] = G.Otglist[tp[i]].data;
		k++;
	}
}


//定义二次关键路径函数
//函数说明：传入事件最早开发时间数组etv、事件最迟开发时间数组ltv、保存关键路径的数组th和带权有向图G
//			求出当前关键路径上的某弧（此处选择a11，即E-I）的权值减小到何值时，关键路径发生改变
//			即去掉当前弧，重新找一条关键路径，将两关键路径权值相减，差值即为该狐需要减少的权值
void TWOCRITICALPATH(char th[], GraphOtglist G) {
	char v1,v2;
	char *q;
	int i;
	int *etv, *ltv;
	EdgeNode *p;
	etv = (int*)malloc(sizeof(int) * G.numVextexes);
	ltv = (int*)malloc(sizeof(int) * G.numVextexes);
	q = (char*)malloc(sizeof(char) * G.numVextexes);
	for(i = 0; i < G.numVextexes; i++) {
		*(q + i) = *(th + i);
	}
	printf("请输入目标弧:");
	cin >> v1 >> v2;
	//查找目标弧
	for(i = 0; i < G.numVextexes; i++) {
		if(G.Otglist[i].data != v1)
			continue;
		p = G.Otglist[i].firstout;
		while(p) {
			if(G.Otglist[p->headvex].data == v2)
				break;
			p = p->taillink;
		}
		break;
	}
	
	//找到目标弧后，减少其权值，迭代求关键路径，直到关键路径发生改变
	while(1) {
		p->weight--;
		ETVERTEX(etv, G);
		LTVERTEX(ltv, etv[G.numVextexes - 1], G);
		CRITICALPATH(etv, ltv, th, G);
		if(COMPARE(q,th))
			break;
	}
	printf("\n活动a11完成时间缩短到%d时将导致AOE网的关键路径发生改变\n", p->weight);
	printf("AOE网新的关键路径有两条:\n");
	for(i = 0; *(q + i) != '#'; i++) {
		printf(" %c ", *(q + i));
	}
	printf("\n");
	for(i = 0; *(th + i) != '#'; i++) {
		printf(" %c ", *(th + i));
	}
	printf("\n");
}


void main()
{	
	int i;
	int *etv, *ltv;
	char *th, *p;
	GraphOtglist graph;				//建立一个图
	CreatGraph(graph);				//调用构造函数	
	Display(graph);					//调用输出函数，查看有向图是否正确	
	system("pause");
	system("cls");
	etv = (int*)malloc(sizeof(int) * graph.numVextexes);
	ltv = (int*)malloc(sizeof(int) * graph.numVextexes);
	th = (char*)malloc(sizeof(char) * graph.numVextexes);
	//初始化用于保存关键路径的数组th
	for(i = 0; i < graph.numVextexes; i++) {
		*(th + i) = '#';
	}
	ETVERTEX(etv, graph);
	//打印各顶点的最早开发时间
	printf("下面是各顶点事件的最早开发时间:\n");
	for(i = 0; i < graph.numVextexes; i++) {
		printf("  %c: %d", graph.Otglist[i].data, etv[i]);
	}
	printf("\n");


	LTVERTEX(ltv, etv[graph.numVextexes - 1], graph);
	//打印各顶点的最晚开发时间
	printf("下面是各顶点事件的最晚开发时间:\n");
	for(i = 0; i < graph.numVextexes; i++) {
		printf("  %c: %d", graph.Otglist[i].data, ltv[i]);
	}
	printf("\n\n");

	ETEDGE(etv, graph);
	LTEDGE(ltv, graph);
	LEISURE(etv,ltv, graph);
	CRITICALPATH(etv, ltv, th, graph);	
	printf("\n带权有向图G的关键路径:");
	p = th;
	while(*p != '#') {
		printf(" %c ", *p);
		p++;
	}
	TWOCRITICALPATH(th, graph);
	system("pause");
}

??????