成都信息工程学院计算机系课程实验报告一【上机实验目的】对有向图的拓扑排序和关键路径更加了解以及更好的应用它二【实验环境】PC机每人1台在Visual C++环境下测试三【上机实验内容】.给定一图，在其拓朴排序的基础上，求关键路径，要求以图形界面呈现关键路径。
四【上机调试程序流程图】（注：可打印）五【上机调试中出现的错误信息、错误原因及解决办法】犯的错误1.在写构建图这个子函数时，初始数据的时候有点问题，本来想用文件的，但是对于文件用的不是很熟悉，然后就利用了二维数组来存放数据。
2.就是在画图形界面的时候，让关键路径以另外的颜色出现时候出现了问题。
解决方法是找到个最早时间和最迟时间相等就把顶点和终点赋值给相应的顶点，再进行颜色的改变。
六【上机调试后的源程序及还存在的问题】（注：源程序可打印）#include <graphics.h>#include<iostream>using namespace std;#define MAX_VEXTEX_NUM 20#define M 20#define MaxLen 1000 //最大长度#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OK 1#define ERROR 0#define OVERFLOW -1typedef int SElemType;typedef int VertexType;typedef int VRType;typedef int InfoType;typedef struct ArcNode{int adjvex; // 该弧所指向的顶点的位置struct ArcNode *nextarc;// 指向下一条弧的指针InfoType info; // 该弧相关信息的指针}ArcNode;typedef struct VNode{VertexType data;// 顶点信息ArcNode *firstarc;// 指向第一条依附该顶点的弧}VNode,AdjList[MAX_VEXTEX_NUM];typedef struct{AdjList vertices;int vexnum, arcnum;}ALGraph;typedef struct SqStack{SElemType *base;SElemType *top;int stacksize;}SqStack;class point //画界面{public:point(int x,int y):m_x(x),m_y(y){}point(){}int x(){return m_x;}int y(){return m_y;}point operator+(point p){return point(m_x+p.x(),m_y+p.y());}point operator/(int i){return point(m_x/i,m_y/i);}private:int m_x;int m_y;};int g_r=25;int g_height=400;int g_width=500;point g_pos[9];void paintmain(ALGraph &G);void line(point a,point b){line(a.x(),a.y(),b.x(),b.y());}void fillcircle(point p,int r){fillellipse(p.x(),p.y(),r,r);}void outtext(point p,char* str){outtextxy(p.x(),p.y(),str);} //界面void InitStack(SqStack &S)//初始化栈{S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base)exit (OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;}int Pop(SqStack &S,SElemType &e)//出栈操作{if(S.top==S.base)return ERROR;e=*--S.top;return OK;}int Push(SqStack &S,SElemType e)//人栈操作{if(S.top-S.base>=S.stacksize){S.base = (SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top = S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;return OK;}int StackEmpty(SqStack S)//判栈是否为空{if(S.top==S.base)return OK;elsereturn ERROR;}int CreatALGraph(ALGraph &G)//构建图{ArcNode *p;int i,j, k,info1;int a[11][3]={{1,2,6},{1,3,4},{1,4,5},{2,5,1},{3,5,1},{4,6,2},{5,7,9},{5,8,7},{6,8,4},{7,9,2},{8,9,4}};G.vexnum=9;G.arcnum=11;for (i=1;i<=G.vexnum;i++)G.vertices[i].data=i;G.vertices[i].firstarc=NULL;}for(k=0;k<G.arcnum;k++){i=a[k][0];j=a[k][1];info1=a[k][2];p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->info=info1;p->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p;}return OK;}void FindInDegree(ALGraph G,int indegree[])//求入度操作{int i;for(i=1;i<=G.vexnum;i++){indegree[i]=0;}for(i=1;i<=G.vexnum;i++){while(G.vertices[i].firstarc){indegree[G.vertices[i].firstarc->adjvex]++;G.vertices[i].firstarc=G.vertices[i].firstarc->nextarc;}}}int ve[100];int TopologicalSort(ALGraph G,SqStack &T) //进行拓扑排序{int indegree[M];FindInDegree(G, indegree);//求各顶点的入度SqStack S;int i,x,k;InitStack(S);ArcNode *p;InitStack(S);for (i=1;i<=G.vexnum;i++){if (!indegree[i])Push(S,i);//入度为0者入栈}InitStack(T);int count=0;for(x=1;x<=G.vexnum;x++)// ve[0..G.vexnum-1]=0; {ve[x]=0;}while(!StackEmpty(S)){Pop(S,i);Push(T,i);++count;//输出i号顶点并计数for (p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;if (--indegree[k]==0)//若入度减为0，则入栈{Push(S,k);}if((ve[i]+p->info)>ve[k]){ve[k]= ve[i]+p->info;}}}printf("\n");if (count<G.vexnum)//该图有回路{printf("出现错误\n");}else{printf("排序成功\n");}return OK;}int CriticalPath(ALGraph G)//输出G的关键活动{int dut;int j=G.vexnum;int i,k;int ee,el;int vl[100];ArcNode *p;SqStack T;if(!TopologicalSort(G,T)){printf("该图存在环，无法找到关键路径！");return ERROR;}for(i=1;i<=G.vexnum;i++)// vl[0.. G.vexnum-1] =ve[0..G.vexnum-1];//用ve初始化vl {vl[i]=ve[G.vexnum];}while(!StackEmpty(T))for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;dut=p->info;if((vl[k]-dut)<vl[j]){vl[j]=vl[k]-dut;}}//end of forfor(i=1;i<=G.vexnum;++i){for (p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;dut=p->info;ee=ve[i];el=vl[k]-dut;if(ve[i]==(vl[k]-dut)){setcolor(BLUE);line(g_pos[i],g_pos[k]);}}//end of for(p)}return 1;}//end of CriticalPathvoid paintmain(ALGraph &G){setbkcolor(WHITE);setcolor(BLACK);setfont(-15,0,"微软雅黑");ArcNode *p;int i,j, k,info1;int a[11][3]={{1,2,6},{1,3,4},{1,4,5},{2,5,1},{3,5,1},{4,6,2}, {5,7,9},{5,8,7},{6,8,4},{7,9,2},{8,9,4}};G.vexnum=9;G.arcnum=11;for(k=0;k<G.arcnum;k++){i=a[k][0];j=a[k][1];info1=a[k][2];char str[10]; //画线point p1=g_pos[i];point p2=g_pos[j];int w=info1;itoa(w,str,10);line(p1,p2);outtext((p1+p2)/2,str);p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->info=info1;p->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p;}setcolor(RED);for ( i=1; i<=9; ++i) // paint circle{char str[10]="v";itoa(i,str+1,10);fillcircle(g_pos[i],g_r);setbkmode(TRANSPARENT);outtext(g_pos[i]+point(-8,-8),str);}}int main(){ALGraph G;CreatALGraph(G);setinitmode(NULL);initgraph(g_width,g_height);// setcaption("AOE-网演示程序");g_pos[1]=point(35,120);g_pos[2]=point(140,70);g_pos[3]=point(140,180);g_pos[4]=point(140,260);g_pos[5]=point(250,120);g_pos[6]=point(260,260);g_pos[7]=point(360,70);g_pos[8]=point(360,180);g_pos[9]=point(450,120);paintmain(G);setfont(-20,0,"微软雅黑");outtextxy(160,10,"按任意键开始演示...");getch();CriticalPath(G);getch();return 0;}七【上机实验中的其他它问题及心得】经过半学期学习数据结构然后做了这个关键路径的小项目，要写出这个小项目必需要平时努力的学好前面的知识，为后面打下基础才能写好这个程序。
