数据库关键路径实验报告.doc

成都信息工程学院计算机系课程实验报告实验课程：数据结构实验项目：关键路径指导教师： 李莉丽学生姓名:刘英 学生学号：2012051021班 级：计科应用1班实验地点： 6308实验时间：20 13 年 11月 3 日 点 点实验成绩：评阅老师：一【上机实验目的】对有向图的拓扑排序和关键路径更加了解以及更好的应用它二【实验环境】PC机每人1台在Visual C+环境下测试三【上机实验内容】.给定一图，在其拓朴排序的基础上，求关键路径，要求以图形界面呈现关键路径。四【上机调试程序流程图】（注：可打印）开始构建图求图的入度对图进行拓扑排序找到图G的关键活动画出图形界面实现关键路径的显示结束开始给顶点数和边数赋值分别为9、11给顶点信息赋值，用了一个for循环创建了一个二维数组，里面存放的数据是顶点、终点、弧度值构建图的邻接表结束结束开始将入度为零的压入栈判断栈是否为空弹出栈顶元素，并将其结点的邻接点入度减一，入度为0者入栈算出结点的最早发生时间结束拓扑排序开始逆序求出最迟时间判断最早时间与最迟时间是否相等如果相等输出这个关键路径的顶点和终点，并在界面上以绿色线条呈现结束关键路径的呈现五【上机调试中出现的错误信息、错误原因及解决办法】犯的错误1.在写构建图这个子函数时，初始数据的时候有点问题，本来想用文件的，但是对于文件用的不是很熟悉，然后就利用了二维数组来存放数据。2.就是在画图形界面的时候，让关键路径以另外的颜色出现时候出现了问题。解决方法是找到个最早时间和最迟时间相等就把顶点和终点赋值给相应的顶点，再进行颜色的改变。六【上机调试后的源程序及还存在的问题】（注：源程序可打印）#include #includeusing 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 ArcNodeint adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc;/ 指向下一条弧的指针InfoType info; / 该弧相关信息的指针ArcNode;typedef struct VNodeVertexType data;/ 顶点信息 ArcNode *firstarc;/ 指向第一条依附该顶点的弧VNode,AdjListMAX_VEXTEX_NUM;typedef structAdjList vertices; int vexnum, arcnum;ALGraph;typedef struct SqStackSElemType *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_pos9;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;else return ERROR;int CreatALGraph(ALGraph &G)/构建图ArcNode *p;int i,j, k,info1;int a113=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.verticesi.data=i; G.verticesi.firstarc=NULL;for(k=0;kadjvex=j; p-info=info1; p-nextarc=G.verticesi.firstarc; G.verticesi.firstarc=p;return OK;void FindInDegree(ALGraph G,int indegree)/求入度操作int i;for(i=1;i=G.vexnum;i+) indegreei=0;for(i=1;iadjvex+; G.verticesi.firstarc=G.verticesi.firstarc-nextarc; int ve100;int TopologicalSort(ALGraph G,SqStack &T) /进行拓扑排序int indegreeM; FindInDegree(G, indegree);/求各顶点的入度 SqStack S;int i,x,k;InitStack(S);ArcNode *p;InitStack(S);for (i=1;i=G.vexnum;i+) if (!indegreei)Push(S,i);/入度为0者入栈InitStack(T);int count=0; for(x=1;xnextarc) k=p-adjvex; if (-indegreek=0)/若入度减为0，则入栈 Push(S,k); if(vei+p-info)vek) vek= vei+p-info; printf(n);if (countG.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 vl100;ArcNode *p;SqStack T;if(!TopologicalSort(G,T) printf(该图存在环，无法找到关键路径！); return ERROR; for(i=1;inextarc) k=p-adjvex; dut=p-info; if(vlk-dut)vlj) vlj=vlk-dut; /end of for for(i=1;inextarc) k=p-adjvex; dut=p-info; ee=vei; el=vlk-dut; if(vei=(vlk-dut) setcolor(BLUE); line(g_posi,g_posk); /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 a113=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;kadjvex=j; p-info=info1; p-nextarc=G.verticesi.firstarc; G.verticesi.firstarc=p; setcolor(RED); for ( i=1; i=9; +i) / paint circle char str10=v; itoa(i,str+1,10); fillcircle(g_posi,g_r); setbkmode(TRANSPARENT); outtext(g_posi+point(-8,-8),str); int main()ALGraph G;CreatALGraph(G); setinitmode(NULL); initgraph(g_width,g_height);/ setcaption(AOE-网演示程序); g_pos1=point(35,120); g_pos2=point(140,70); g_pos3=point(140,180); g_pos4=point(140,260); g_pos5=point(250,120); g_pos6=point(260,260); g_pos7=point(360,70); g_pos8=point(360,180); g_pos9=point(450,120); paintmain(G); setfont(-20,0,微软雅黑); outtextxy(160,10,按任意键开始演示.); getch(); CriticalPath(G); getch(); return 0;七【上机实验中的其他它问题及心得】经过半学期学习数据结构然后做了这个关键路径的小项目，要写出这个小项目必需要平时努力的学好前面的知识，为后面打下基础才能写好这个程序。我感觉自己在上数据结构这门课的时候是每节课都到了的，只是有一次起晚了迟到了几分钟，每次上课李老师都要抽人回答上节课上的知识点，让我们回顾以前学的知识，这是一个很好的方法让我们记得数据结构主要学了什么，而且在上课期间也是慢慢的给我们分析程序，用画图的方式让我们很容易理解程序中每个语句是什么含义，通过你的引导让我们知道应该怎么分析程序，实参到形参的关系等等，这次写这个关键路径也是用了你的方法，先把书上的程序用画图的方式慢慢理解之后，然后有了自己的思路，才写出的这个关键路径的程序。对于在写这个关键路径的过程中也遇到很多问题，但最要的有两个就是怎么存放数据和图形界面应该怎么画这两个问题。存放数据时本来用的是文件，但是学习文件时对于文件的操作不是很熟悉，然后无论怎样改都有错误，然后就选择了用二维数组来存放数据。而对于图形界面，以前都