数据结构课程设计报告(完整版本)-

{

int data;//顶点的信息

ArcNode *firstarc;//指向第一条依附该顶点的弧的指针

}AdjList[MAX_V_NUM]; typedef struct {

AdjList vertices;

int vnum,arcnum;//图中当前顶点数和弧数 char kind,kind1;//图中的各类标志顶点和弧

}ALGraph; typedef struct {

int *base; int *top; int stacksize;

}Stack;

int ve[MAX_V_NUM];

Stack T;

//函数体描述部分

int InitStack(Stack &S); int Push(Stack &S,int &e); int Pop(Stack &S,int &e);

int CriticalPath(ALGraph &G);

int ToPoOrder(ALGraph &G,Stack &T);

int FindInDegree(ALGraph &G,int (&indegree)[MAX_V_NUM]); /*下面是函数的具体实现部分*/ //构造一个空栈

int InitStack(Stack &S) {

S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int)); if(!S.base) return 0; S.top=S.base;

S.stacksize=STACK_INIT_SIZE;//可以用于当栈的存储空间不够的情况下 进行扩充 return 1; };

//元素进栈

5 / 33

数据结构课程设计报告(完整版本)-

int Push (Stack &S, int &e) {

*S.top++=e; return 1; };

//元素出栈

int Pop(Stack &S, int &e) {

if(S.top==S.base) return 0; e=*--S.top; return 1; };

//判断栈是否为空

int StackEmpty(Stack &S) {

if(S.top==S.base) return 1; else return 0; };

//找出每个顶点的入度

int FindInDegree(ALGraph &G,int (&indegree)[MAX_V_NUM]) {

ArcNode *p; int i;

for(i=0;inextarc) indegree[p->adjvex]++; }

return 0; }

//拓扑排序同时求出各活动的最早发生时间

int ToPoOrder(ALGraph &G,Stack &T) {

int count=0;

6 / 33

数据结构课程设计报告(完整版本)-

int i,j,k; Stack S1; ArcNode *p;

int indegree[MAX_V_NUM]; InitStack(T); InitStack(S1);

FindInDegree(G,indegree); for(i=0;i

for(i=0;i

while(!StackEmpty(S1)) { Pop(S1,j); Push(T,j); count++; for(p=G.vertices[j].firstarc;p;p=p->nextarc) { k=p->adjvex; if(--indegree[k]==0) Push(S1,k); if(ve[j]+(p->info)>ve[k]) ve[k]=ve[j]+(p->info); } }

// for(i=0;i

//计算各顶点的最迟发生时间及进行输出 int CriticalPath(ALGraph &G) {

int vl[MAX_V_NUM]; int dut;

7 / 33

数据结构课程设计报告(完整版本)-

int i,j,k,ee,el; ArcNode *p; // char tag;

if(!ToPoOrder(G,T)) return 0;

cout<<\完成整项工程至少需要的时间是：\.vnum-1]<nextarc) { k=p->adjvex; dut=(p->info); if(vl[k]-dut

// for(i=0;i

cout<<\影响工程进度的关键活动是:\ for(j=0;jnextarc) { k=p->adjvex; dut=(p->info); ee=ve[j]; el=vl[k]-dut;

//cout<<\endl; if(ee==el) //tag=(ee=el)?'*':''; cout<name<

int main() {

ALGraph G; int i,j,Hnum;

8 / 33