#include <stdio.h>#include <stdlib.h>#include <string.h>#include <conio.h>#include<windows.h>#define MAXV 10typedef char VerType;//顶点值类型struct ArcNode{ int adjvex; //邻接点域，存储该顶点对应的下标struct ArcNode* next;//指向下一个临界点的指针点}ArcNode;typedef struct VNode{ int in; //入度VerType data; //值char name[MAXV];struct ArcNode* firstedge; //邻接表头指针}VNode;typedef struct adjGraph{ //邻接表储存结构struct VNode vers[MAXV]; //顶点和邻接点的数组int vexnum, arcnum; //顶点数和边数}adjGraph;//拓扑排序int TopSort(adjGraph* G){ struct ArcNode* e;int i, k, gettop;int top = 0;//栈指针int count = 0;//统计输出顶点个数int* stack; //定义栈存储入度为0的顶点stack = (int *)malloc(G->vexnum * sizeof(int)); //开辟栈空间for(i=0;i<G->vexnum;i++) //遍历所有结点if(G->vers[i].in == 0)stack[++top] = i; //将入度为0的顶点入栈while(top !=0){ //栈不空gettop = stack[top--]; //出栈一个顶点printf("%c %c ",G->vers[gettop].data,G->vers[gettop].name);//输出顶点count++; //统计输出顶点数for(e=G->vers[gettop].firstedge; e; e = e->next){ //弧表遍历k = e->adjvex;if(!(--G->vers[k].in))//将k号顶点邻接点的入度减1stack[++top] = k;//若为0则入栈，以便下次循环输出}}if(count < G->vexnum)//如果count小于顶点数，说明存在环return 0;elsereturn 1;}/* 数边数File *fp;int a,b,c;fscanf(fp,"%d",&b);for(i=0;i<G->vexnum;i++){fscanf(fp,"%d",&G->vers[i].data); getc(fp); while(fgetc(fp)!=0){ a++;c=fgetc(fp);}*//*File *fp; 文件读取int i,m;if((fp=fopen("date.txt","r"))==NULL){return;}fscanf(fp,"%d",&G->vexnum);for(i=0;i<G->vexnum;i++){fscanf(fp,"%d",&G->vers[i].data);G->vers[i].name=getc(fp); n=G->vers[i].data; while(fgetc(fp)!=0){m=fgetc(fp);}}*///创建图void CreateGraph(adjGraph * G){int i, m, n;FILE *fp;if((fp=fopen("date.txt","r"))==NULL){return;}int a=0,b=0,c=0; fscanf(fp,"%d",&b); for(i=0;i<G->vexnum;i++){fscanf(fp,"%d",&b); fgetc(fp); while(fgetc(fp)!=0){ a++;c=fgetc(fp);}G->arcnum=a; //边数 fscanf(fp,"%d",&G->vers[i].data); /*顶点数*/ for(i=0;i<G->vexnum;i++){ fscanf(fp,"%d",G->vexnum); fscanf(fp,"%s",G->vers[i].name);n=G->vers[i].data; while(fgetc(fp)!=0){m=fgetc(fp);//初始化图头结点指针和入度值G->vers[i].firstedge = NULL;//头结点指针为空G->vers[i].in = 0; //入度为0 for(i=0;i<G->arcnum;i++){ //边关系struct ArcNode *newNode = (struct ArcNode*)malloc(sizeof(struct ArcNode));newNode->next = G->vers[m].firstedge == NULL ? NULL : G->vers[m].firstedge; //三目运算符newNode->adjvex = n;G->vers[m].firstedge = newNode; //G->vers[n].in++;//入度+1}}}}} //完成函数int sGraph(){ struct adjGraph *G=(struct adjGraph*)malloc(sizeof(struct adjGraph)) ;CreateGraph(G);if(TopSort(G)){printf("\n课程排序完成！\n");}else{printf("\n课程图存在环,无法排课！\n");}return 0;}//菜单模块void menu(){printf("-------------------------欢迎进入拓扑课程排序系统-------------------------------");printf("\n");printf("-------------------------------1、排课------------------------------------------");printf("\n");printf("-------------------------------0、退出系统--------------------------------------");printf("\n");printf("--------------------------------------------------------------------------------\n");printf("\n");printf("\t\t请输入指令(0-1): ");} int main(){int num; system("color 0B"); while(1) { menu(); scanf("%d",&num); system("cls"); switch(num) { case 1: sGraph();break; case 0: printf("谢谢使用！\n\n"); return 0; default :printf("\n无效的指令!\n\n\n"); } system("pause"); system("cls");}}
