数据结构课程设计 - 关键路径

由天下分享时间：2025/3/10 22:03:19 加入收藏我要投稿点赞

2、栈的顺序存储结构如下： #define SIZEMAX 20 #define ADD 10 typedef int Elemtype; typedef struct {

Elemtype * base; Elemtype * top; int maxsize; }Stack;

3、图的构建函数设计如下：

int ID[MAX]={0}; //存放每个顶点的入度的数组ID

int ve[MAX]={0}; //用来存放每个顶点的最早发生时间的数组ve char str3[MAX][10]; //存放活动的字符串数组

void InitGraph(ALGraph &G) //初始化图时将图的顶点数、弧数都赋为MAX {

G.vexnum=MAX; G.arcnum=MAX;

for(int i=0;i

void CreateGraphic(ALGraph &G) {

int i,j,s,n;

ArcNode *p,*pp; //定义两个指向ArcNode表结点的指针p,pp char str1[10],str2[10]; //定义两个字符串str1,str2,最大长度为10 scanf(\,&G.vexnum); //输入图的顶点数vexnum

for(i=0;i

{

scanf(\,G.vertices[i].data); //输入各顶点的信息,顶点名称 G.vertices[i].first=NULL; //第i个头结点的first域指向空

}

scanf(\,&G.arcnum); //输入图的弧数arcnum for(i=0;i

scanf(\,str1,str2,str3[i],&n); //输入每条弧的其它相关信息,str1是弧的弧尾，str2是弧的弧头，str3指的是活动，n指的是权值

for(j=0;j

if(strcmp(str1,G.vertices[j].data)==0) 则停止查找，并保存弧尾

break; 所示的顶点在头结点中的序号j

for(s=0;s

if(strcmp(str2,G.vertices[s].data)==0) 则停止查找，并保存弧头

break; 所示的顶点在头结点中的序号s

pp=(ArcNode *)malloc(sizeof(ArcNode)); //给pp申请一个内存空间 pp->adjvex=s; //将弧头所指向的顶点的位置下标存放在pp的adjvex域中 pp->info1=str3[i]; //将该弧的活动信息存放在pp的info1域中 pp->info2=n; //将该弧的权值大小存放在pp的info2域中 pp->next=NULL; //pp的next指向空 ID[s]++; //s的入度加1

if(G.vertices[j].first!=NULL) //如果序号为j的头结点的first所指向的不为 { 空，则表示该顶点已经连好了一条弧，需要找下一个可存放的位置

p=G.vertices[j].first; //用一个临时指针保存该头结点的first指针 if(p->next!=NULL) //如果first所指向的表结点的next指向不为空， { //则需要找下一个可存放位置

while(p->next->next!=NULL) //如果p所指向的表结点的next { 所指向另一表结点的next不为空，就把p指针往后移一位 } p=p->next;

p=p->next;

}

p->next=pp; //直到p的next指向为空，再把p的next指向pp

else G.vertices[j].first=pp; //如果序号为j的头结点的first所指向的为空，直接把它的first指向pp

} }

4、堆栈的功能函数设计如下：

Status InitStack(Stack &S) //栈的初始化操作 {

S.base=(Elemtype *)malloc(SIZEMAX*sizeof(Elemtype)); //给栈分配内存空间 if(!S.base) exit (OVERFLOW); //若分配不成功，则返回OVERFLOW； S.top=S.base; //让栈的栈顶指针和栈底指针相等 S.maxsize=SIZEMAX; //栈的当前容量为SIZEMAX return OK; }

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

if(S.top==S.base) //如果栈的栈顶指针等于栈底指针，则表示当前栈为空

return ERROR; //栈顶元素不存在，所以返回ERROR

e=*(--S.top); //如果栈不为空，就取出S的栈顶指针所指向的数据，

return OK; //并把top指针往下移一个位置 }

Status Push(Stack &S,int e) {

if(S.top-S.base>=S.maxsize) //如果当前栈内存的元素超过了它的最大存放量 { //则必须追加空间 }

*(S.top++)=e; //top指针往上移一位后，让top指针指向元素e

S.base=(Elemtype *)realloc(S.base,(S.maxsize+ADD)*sizeof(Elemtype)); if(!S.base)

exit (OVERFLOW);

S.top=S.base+S.maxsize; S.maxsize=S.maxsize+ADD;

return OK; }

Status Empty(Stack S) {

if(S.top==S.base) return OK;

//如果栈的栈顶指针等于栈底指针，则表示当前栈为空,返回OK

else return ERROR; //否则返回ERROR }

5、求关键路径的函数设计如下：

Status Topo(ALGraph G,Stack &T) //拓扑排序函数 {

int i,j,k;

ArcNode *p; //定义一个指向ArcNode表结点的指针p

Stack S; //定义一个存放入度为0的顶点所在的下标值的栈 InitStack(S); //初始化栈S

for(j=0;j

if(ID[j]==0) //若为0，就让该顶点所在位置的下标值入栈

Push(S,j);

int count=0; //记录进入拓扑排序栈T的元素个数 while(!Empty(S)) {

Pop(S,j); //从零入度顶点栈S中取出栈顶元素，存放在j中 Push(T,j); //元素j入栈T，表示序号为j的顶点入栈 count++;

for(p=G.vertices[j].first;p;p=p->next)

{ //找以第j个顶点为弧尾的弧的弧头

k=p->adjvex; //保存弧头所示的顶点的位置下标 ID[k]--; //删除该弧后，弧头所示的顶点入度减1 if(ID[k]==0) Push(S,k); //如果该顶点入度为0，就入栈S if( ( ve[j] + (p->info2) ) > ve[k] ) ve[k]=ve[j]+(p->info2); //如果j号顶点的最早发生时间与该弧的权值之和大于k号定点的

}//最早发生时间，就改变k号顶点的最早发生时间

}

if(count

}

else return OK;

Status Critial(ALGraph G) //求关键路径函数 {

int i,j,k,ee,el;

int vl[MAX]; //存放各顶点最迟发生时间的数组vl

Stack T; //定义一个存放拓扑序列元素的栈T InitStack(T); //初始化该栈 ArcNode * p;

if(!Topo(G,T)) return ERROR;

//如果拓扑排序不成功，也无法找到关键路径，就返回ERROR

for(i=0;i