C语言数据结构--相对路径设计

概述本文章向大家介绍C语言数据结构--相对路径设计，主要包括C语言数据结构--相对路径设计使用实例、应用技巧、基本知识点总结和需要注意事项，具有一定的参考价值，需要的朋友可以参考一下。

#include

#include

#include

#include

typedef struct node//边表结点

{

int adjvex; //邻接点编号

int dut; //弧的信息

struct node *next; //下一条弧指针

}edgenode;

typedef struct //顶点表结点

{

int projectname;//顶点域

int ID;//顶点的入度信息

edgenode *link; //边表头指针

}vexnode;

voID CreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber)//创建图

{

int begin,end,duttem; //分别代表弧的前节点，尾节点，活动时间

edgenode *p;// 边表头指针

for(int i=0;i

{

Graphicmap[i].projectname=i;//顶点的命名按0，1，2，3......

Graphicmap[i].ID =0;//顶点的信息的度数均赋为零

Graphicmap[i].link =NulL;

}

printf("n");

printf("请输入某项目的信息，并请用整形数字表示（格式：弧头，弧尾，权值）：n");

printf("例如:输入1,2,4 即代表结点1与4之间的活动需要4个时间单位。n");

printf("n");

for(int k=0;k

{

scanf("%d,%d,%d",&begin,&end,&duttem); //请输入第%d条的起点、终点和权值

p=(edgenode*)malloc(sizeof(edgenode));//临时分配存储空间

p->adjvex =end-1;//因为是从零开始记的，姑要减一，就是让终点插入到邻接表内

p->dut =duttem; //该弧的活动时间为duttem

Graphicmap[end-1].ID ++; //入度加一

p->next =Graphicmap[begin-1].link ;

Graphicmap[begin-1].link =p;//让下一个节点作为下一插入节点的前驱节点

}

}

int SearchMapPath(vexnode* Graphicmap,int activenumber

,int& totaltime) //求出最大路径，并打印出关键路径

{

int i,j,k,m=0;

int front=-1,rear=-1;

int* topologystack=(int*)malloc(projectnumber*sizeof(int));//用来保存拓扑排列

int* vl=(int*)malloc(projectnumber*sizeof(int));//用来表示在不推迟整个工程的前提下，VJ允许最迟发生的时间

int* ve=(int*)malloc(projectnumber*sizeof(int));//用来表示Vj最早发生时间

int* l=(int*)malloc(activenumber*sizeof(int));//用来表示活动Ai最迟完成开始时间

int* e=(int*)malloc(activenumber*sizeof(int));//表示活动最早开始时间

edgenode *p; //边表头的指针

totaltime=0; //存放整个工程的最短时间

for(i=0;i

for(i=0;i

{

if(Graphicmap[i].ID==0)

{

topologystack[++rear]=i;//让所有的头节点入队列

m++; //记录入队列的顶点个数

}

}

while(front!=rear)

{

front++; //出队列

j=topologystack[front]; //拓扑排序的节点依次出队列

m++; //记录入队列的节点个数

p=Graphicmap[j].link ; //指向顶点指向的下一个顶点

while(p)

{

k=p->adjvex ; // 邻接点编号

Graphicmap[k].ID --;//让入度减一，相当于删除一个入度为零的前驱节点，和相关的弧

if(ve[j]+p->dut >ve[k])//将最长的路径赋给VE[K]

ve[k]=ve[j]+p->dut ;

if(Graphicmap[k].ID ==0)//如果入度为零，则入队列

topologystack[++rear]=k;

p=p->next ; //指向下一个节点

}

}

if(m

{

printf("n本程序所建立的图有回路不可计算出关键路径!n");

printf("将退出本程序！n");

return 0;

}

totaltime=ve[projectnumber-1];//最短完成时间即为最后一个节点所累加的时间之和

for(i=0;i

vl[i]=totaltime;

for(i=projectnumber-2;i>=0;i--)// 用逆拓扑排序来求活动Ai最迟完成开始时间，即从最后一个节点减去最短的时间

{

j=topologystack[i];

p=Graphicmap[j].link ;

while(p)

{

k=p->adjvex ;

if((vl[k]-p->dut )

vl[j]=vl[k]-p->dut ;

p=p->next ;

}

}

i=0;

printf("n");

printf("| 起点 | 终点 | 最早开始时间 | 最迟完成时间 | 差值 | 备注 n");

for(j=0;j

{

p=Graphicmap[j].link;

while(p)

{

k=p->adjvex ;

e[++i]=ve[j];

l[i]=vl[k]-p->dut;

printf("| %4d | %4d | %11d | %11d | %3d |",Graphicmap[j].projectname +1,Graphicmap[k].projectname +1,e[i],l[i],l[i]-e[i]);

if(l[i]==e[i]) //当差值为零时，则为关键路径

printf(" 关键活动 <%2d,%4d>",

Graphicmap[j].projectname +1,Graphicmap[k].projectname +1);

printf("n");

p=p->next ;

}

}

return 1;

}

voID seekkeyroot()//求关键路径的主函数

{

int projectnumber,activenumber,totaltime=0;

printf("n");

printf("输入符合标准，欢迎进入求关键路径的系统!n");

printf("n");

printf("请输入这个项目的AOE-网的节点数: ");

scanf("%d",&projectnumber);

printf("请输入这个项目的AOE-网的活动个数: ");

scanf("%d",&activenumber);

vexnode* Graphicmap=(vexnode*)malloc(projectnumber*sizeof(vexnode));

CreateGraphic(Graphicmap,projectnumber,activenumber);//创建邻接图

SearchMapPath(Graphicmap,totaltime);//求出最大路径，并打印出关键路径

printf("n");

printf("整个工程所用的最短时间为：%d个单位时间n",totaltime);

system("pause");

}

int main()

{

char ch;

for(;;)

{

do

{

system("cls");

printf("☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★ n");

printf(" 欢迎进入求关键路径算法程序 n");

printf("☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★ n");

printf("%s","ns(start)开始输入工程的节点数据并求出关键路径n");

printf("n");

printf("%s","e(exit)退出n");

printf("n");

printf("%s","请输入选择:");

scanf("%c",&ch);

ch=toupper(ch);

}while(ch!='S'&&ch!='E');

switch(ch)

{

case'S':

seekkeyroot();

break;

case'E':

return 1;

}

}

}

总结

以上是内存溢出为你收集整理的C语言数据结构--相对路径设计全部内容，希望文章能够帮你解决C语言数据结构--相对路径设计所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。