第一题.cpp

几个常用的数据结构算法：堆栈、链表、二叉树、图等。

#include<stdio.h>
#include<stdlib.h>
#define NUM 10
#define add 5
typedef struct ArcNode{
	int  adjvex;
	struct ArcNode *nextarc;
	int weight;
}ArcNode;

typedef struct VNode{
	int data;
	ArcNode *firstarc;
}VNode,AdjList[NUM];

typedef struct{
	VNode *vertices;
	int vexnum,arcnum;
	int kind;
}ALGraph;
 
typedef struct{
	int *base;
	int *top;
	int stacksize;
}SqStack;

typedef struct Path{
	int i;
	int j;
	struct Path *next;
}Path,*PathList;


int AdjListSize=NUM;
int *ve;
int *vl;

PathList Head;
int *PathShow;



          //栈操作函数
int InitStack(SqStack &S)    //建立栈
{
	S.base=(int*)malloc(NUM*sizeof(int));
	if(!S.base) exit(-2);
	S.top=S.base;S.stacksize=NUM;
	return 1;
}

int Push(SqStack &S,int e)  //数据进栈
{
	if(S.top-S.base>=S.stacksize){
		S.base=(int*)realloc(S.base,(S.stacksize+add)*sizeof(int));
		if(!S.base) exit(-2);
		S.top=S.base+S.stacksize;
		S.stacksize+=add;
	}
	*S.top++=e;
	return 1;
}

int Pop(SqStack &S,int &e)  //数据出栈
{
	if(S.top==S.base) return -2;
	e=*--S.top;
	return 1;
}

int StackEmpty(SqStack&S)  //判断栈为空
{
	if(S.top==S.base) return 1;
	else return 0;
}


void CreateGraphic(ALGraph&G)  //创建图的邻接表存储结构
{
	
	void InsertVex(ALGraph &G,int flag);
	void InsertArc(ALGraph &G,int flag);
	void ShowVexs(ALGraph &);
    system("cls");
	int quit=0;

	while(!quit)         //菜单显示
	{
		char ch;
		printf("\t\t\t\t创建邻接表存储结构\n");
		printf("1.批量插入图顶点\n");
		printf("2.单个插入图顶点\n");
		printf("3.批量插入弧\n");
		printf("4.单个插入弧\n");
		printf("5.察看顶点信息\n");
		printf("6.退出\n");
		ch=getchar();
		getchar();
		switch(ch)
		{
		case '1': InsertVex(G,1);break;
		case '2': InsertVex(G,0);break;
		case '3': InsertArc(G,1);break;
		case '4': InsertArc(G,0);break;
		case '5': ShowVexs(G);break;
		case '6': quit=1;break;
		default: printf("What you choose is wrong! Please choose again!\n");
		}
	}
}

void InsertVex(ALGraph &G,int flag)
{
	int ch;
	system("cls");
	if(flag)
	{
		printf("请输入要插入顶点编号 (int 类型),以-1结束:\n");
		printf("如：1 2 3 -1回车表示：输入了三个顶点，编号依次是1 2 3\n"); 
	}
	else
		printf("请输入要插入顶点编号 (int 类型):");
	
		scanf("%d",&ch);
		while(ch!=-1){
			if(G.vexnum>=AdjListSize){
				G.vertices=(VNode*)realloc(G.vertices,(G.vexnum+add)*sizeof(VNode));
				AdjListSize+=add;
			}
		G.vertices[G.vexnum++].data=ch;//为该节点数据域赋值
		G.vertices[G.vexnum-1].firstarc=NULL;//指针域赋值
        if(!flag) {
			printf("\n插入成功\n"); getchar();return;
		}
		else
			scanf("%d",&ch);
		}
		getchar();
}

void InsertArc(ALGraph &G,int flag)
{
	int head,tail,weight;
	ArcNode *p1,*p2;
	system("cls");
	printf("请输入各边信息：\n");
	printf("某项目的开始到结束在图中的节点输入规则为<弧头,弧尾，权值>:\n"); 
	printf("如：3 4 9 回车表示：第三节点到第四节点之间的活动用了9个单位时间\n"); 
	if(flag)
		printf("当输入的(弧头)为-1时，各边信息输入结束!!\n");

	scanf("%d",&head); 
	while(head!=-1){
		scanf("%d%d",&tail,&weight); 
		for(int i=0;i<G.vexnum;i++)                    //找到第一个输入节点的位置
			if(head==G.vertices[i].data) break;
		if(i==G.vexnum){
			printf("你输入弧的弧头顶点不存在! 请先输入顶点再进行输入\n");
			getchar();
			return;
		}
		for(int j=0;j<G.vexnum;j++){
			if(tail==G.vertices[j].data) break;}      //找到第二个输入节点的位置
		if(j==G.vexnum){
			printf("你输入弧的弧尾顶点不存在! 请先输入顶点再进行输入\n");
			getchar();
			return;
		}
		p2=(struct ArcNode *)malloc(sizeof(struct ArcNode)); 
		p1=G.vertices[i].firstarc;                    //先让p1指向该节点的第一个弧
	
		p2->nextarc=p1;                               //把p2插在p1前面
		p2->adjvex=tail;
		G.vertices[i].firstarc=p2; 

		p2->weight=weight;   //权值
		G.arcnum+=1;
		if(!flag) {
			printf("\n插入成功\n");getchar();return;
		}
		else
			scanf("%d",&head); 
	}
	getchar();

}
void ShowVexs(ALGraph &G)
{
	ArcNode *p;
	system("cls");
	for(int i=0;i<G.vexnum;i++)
	{
		printf("第%d个节点：%d\n",i+1,G.vertices[i].data);
		p=G.vertices[i].firstarc;
		if(!p) printf("该节点无邻接表!!\n");
		else
			printf("该节点的邻接表:\n");
		while(p)
		{
			printf("\t\t指向节点:%d 权值:%d\n",p->adjvex,p->weight);
			p=p->nextarc;
		} 
	}
	printf("\nPress any !!Enter!! to continue ");
	getchar();
	

}

void FindInDegree(ALGraph &G,int *indegree)
{
	int i,j;
	struct ArcNode *p;
	
	
	for(i=0;i<G.vexnum;i++)
	{
		for(j=0;j<G.vexnum;j++)       //查找所有邻接表，计算该顶点的入度
		{
			p=G.vertices[j].firstarc;
			
			while(p)
			{
				if(p->adjvex==G.vertices[i].data)
					indegree[i]++;
				p=p->nextarc;
			}
		}
	}
}

int TopologicalOrder(ALGraph G, SqStack &T) 
{  // 有向网G采用邻接表存储结构，求各顶点事件的最早发生时间ve(全局变量)。
  // T为拓扑序列定点栈，S为零入度顶点栈。
  // 若G无回路，则用栈T返回G的一个拓扑序列，且函数值为1，否则为0。
  SqStack S;
  
  int count=0,k;
  int *indegree;
  int t;
	indegree=(int*)malloc(G.vexnum*sizeof(int));
	for(int i=0;i<G.vexnum;i++)
		indegree[i]=0;
	FindInDegree(G,indegree);  // 对各顶点求入度indegree[0..vernum-1]
   
	ve=(int*)malloc(G.vexnum*sizeof(int));
    for( i=0;i<G.vexnum;i++)    // 初始化
		   ve[i]=0;
  ArcNode *p;
  InitStack(S);
 
  for (int j=0; j<G.vexnum; ++j)     // 建零入度顶点栈S
	  if (indegree[j]==0)
		  Push(S, j);// 入度为0者进栈
	  InitStack(T);//建拓扑序列顶点栈T
	  count = 0;  
	 while (!StackEmpty(S)) {
    Pop(S, j);  
	Push(T, j);  
	++count;       // j号顶点入T栈并计数
    for (p=G.vertices[j].firstarc;p;  p=p->nextarc) {
      t = p->adjvex;            // 对j号顶点的每个邻接点的入度减1
	  for(i=0;i<G.vexnum;i++)
		  if(G.vertices[i].data==t) k=i;

      if (--indegree[k] == 0)
		  Push(S, k);   // 若入度减为0，则入栈
      if (ve[j]+p->weight > ve[k])  ve[k] = ve[j]+p->weight;
    }
 }
  if (count<G.vexnum) 
	  return 0;  // 有回路
  else 
	  return 1;
} 

int CriticalPath(ALGraph G,int projectnum)
 {  
  // 输出G的各项关键活动。
	int a,j,k,el,ee,dut,t;
	int n=0;
	void ShowMaxPath(ALGraph G,int);

	vl=(int*)malloc(G.vexnum*sizeof(int));
    Head=(PathList)malloc(sizeof(Path));
	Head->next=NULL;
	PathList q;
  SqStack T;
  
  char tag;
  ArcNode *p;
  if (!TopologicalOrder(G, T)) 
	  return 0;
  for(int i=0;i<G.vexnum;i++)
	  if(G.vertices[i].data==projectnum)
		  break;
  printf("此工程至少需要的单位时间为：%d\n\n",ve[i]);
  for(a=0; a<G.vexnum; a++)
	  vl[a] = ve[i];
  while (!StackEmpty(T))       // 按拓扑逆序求各顶点的vl值
    for (Pop(T, j), p=G.vertices[j].firstarc;  p;  p=p->nextarc) {
      t=p->adjvex;  dut=p->weight;  
	  for(i=0;i<G.vexnum;i++)
		  if(G.vertices[i].data==t) k=i;

		  if (vl[k]-dut < vl[j]) vl[j] = vl[k]-dut;
    }
	printf("起点\t终点\t最早开始时间\t最迟完成时间\t差值 \t是否为关键活动\n"); 
	for (j=0; j<G.vexnum; ++j)            // 求ee,el和关键活动
		for (p=G.vertices[j].firstarc;  p;  p=p->nextarc) {
			t=p->adjvex;dut=p->weight; 
			for(i=0;i<G.vexnum;i++)
				if(G.vertices[i].data==t) k=i;
			ee = ve[j];  el = vl[k]-dut;
			tag = (ee==el) ? '*' : ' ';
			if(ee==el){
            q=(PathList)malloc(sizeof(Path));
			q->i=G.vertices[j].data;
		
			q->j=G.vertices[k].data;
			q->next=Head->next;
			Head->next=q;}
			printf("%d\t%d\t%d\t\t%d\t\t%d\t%c\n",G.vertices[j].data, G.vertices[k].data, dut, ee, el, tag);   // 输出关键活动
			n++;
		}
	 PathShow=(int*)malloc(n*sizeof(int));   
	 ShowMaxPath(G,projectnum);
	 return 1;
} 


void SearchMaxPath(ALGraph &G)
{ 
	int projectnum;
	int flag;
	int quit=0;
	printf("请输入工程的结束顶点的编号：\n");
	do{
		quit=0;
		scanf("%d",&projectnum);
		getchar();
		for(int i=0;i<G.vexnum;i++){
			if(G.vertices[i].data==projectnum)
				break;}
		if(i==G.vexnum){
			printf("输入顶点不存在，请重新输入!!\n");
			printf("请输入工程的结束顶点的编号：\n");
			quit=1;}

	}while(quit);
	
	flag=CriticalPath(G,projectnum);
	if(!flag)
		printf("图中有回路，不能求得所要数据\n");
	printf("\nPress any !!Enter!! to continue ");
	getchar();
}


void ShowMaxPath(ALGraph G,int projectnum)
{
	void Print(int i,int n,int projectnum);

	int *indegree;
	indegree=(int*)malloc(G.vexnum*sizeof(int));
	for(int i=0;i<G.vexnum;i++)
		indegree[i]=0;
	FindInDegree(G,indegree);  // 对各顶点求入度indegree[0..vernum-1]

		printf("\n关键路径(用各顶点表示)为：\n");
        for(int j=0;j<G.vexnum;j++)
			if(indegree[j]==0){
				PathShow[0]=G.vertices[j].data;
				Print(G.vertices[j].data,1,projectnum);
				
			}
}

void Show(int projectnum)
{
	int i=0; 
	do{
		printf("%d\t",PathShow[i]);
	}while(PathShow[i++]!=projectnum);
	printf("\n");

}


void Print(int i,int n,int projectnum)
{
	if(i==projectnum){
		Show(projectnum);
		return;
	}
	for(PathList p=Head->next;p;p=p->next){
		if(p->i==i){
			PathShow[n]=p->j;
			Print(p->j,n+1,projectnum);
		}
		
	}
}

void main()
{

	int i;
    ALGraph G;
	G.vertices=(VNode*)malloc(AdjListSize*sizeof(VNode));
	int quit=0;//初始化图G
	G.arcnum=0;
	G.vexnum=0;
    G.kind=1;//1表示有带权值的有向图
	for(i=0;i<AdjListSize;i++)
		G.vertices[i].firstarc=NULL;
	
	while(!quit)
	{
		char ch;
		system("cls");
		printf("\t\t\t\t关键路径算法\n");
		printf("C 创建邻接表存储结构\n");
		printf("S 求最大路径\n");
		printf("E 退出\n");
		printf("请输入你的选择：");
		ch=getchar();
		getchar();
		switch(ch)
		{
		case 'C': case 'c': CreateGraphic(G);break;
		case 'S': case 's': SearchMaxPath(G);break;
		case 'E': case 'e': quit=1;break;
		default: printf("What you choose is wrong! Please press !!Enter!! to choose again!\n");
			getchar();
		}
	}
}