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

printf(\);

printf(\关键路径为：\); for(j=0;j

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

ee=ve[j];

el=vl[k]-(p->info2);

if(el==ee) printf(\,p->info1);

四、 调试分析

1、本次课程设计题目思路特别清晰，算法特别简单，但是在编程过程中遇到了一系列的问题都值得思考与分析。

2、首先是在图的创建过程中，用邻接表创建图的时候，指针使用没有正确到位而引发了一系列问题，后来通过与老师同学一起分析才找到了问题的症结所在。之前用临时指针p保存头结点的first指针，然后让p指向已经存好信息的表结点pp，这样操作并没有真正把它连起来，下次循环时，又覆盖了原来的信息。

3、在成功创建了图后，把主函数中生成的图作为参数传给Critial()时，又发现原来图中的活动这一信息又改变了，全变成乱码了，原来是由于存放活动的字符串str3，由于不断的输入，导致最后字符串什么也没有了，而图中每个弧的活动指针都指向它，所以就全乱了，后来就把它改为字符串数组，并且把它设为全局变量。

4、在调试Critial()这一函数中，也遇到了一些问题，在观察零入度栈S的栈顶元素和拓扑序列栈T的时候，在watch窗口中输入*(S.top--)，发现一直乱变，根

11

本不知道它的栈内元素，甚至怀疑栈的初始化函数有没有写对，后来通过查找以前堆栈类型问题以及与同学题目作对比才发现就是由于窗口输入内容写错了，应该改为*(S.top-1)。

五、 用户使用说明

第一行输入顶点个数vexnum。 第二行输入各个顶点的名称。 第三行输入弧的边数arcnum。

接下来的arcnum行输入每一条弧的弧尾顶点、弧头顶点、活动以及权值大小。

六、 测试结果

七、 附录

以下是该程序设计的完整代码： #include

12

#include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0

#define OVERFLOW -2 #define MAX 20

#define SIZEMAX 20 #define ADD 10 typedef int Status; typedef int Infotype; typedef char Vertextype; typedef int Elemtype;

int ID[MAX]={0}; int ve[MAX]={0}; char str3[MAX][10];

typedef struct ArcNode {

int adjvex; struct ArcNode * next; char * info1; int info2; }ArcNode;

typedef struct VNode {

Vertextype data[3]; ArcNode * first;

}VNode,AdjList[MAX]; typedef struct {

AdjList vertices; int vexnum; int arcnum; }ALGraph;

typedef struct {

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

void Init(ALGraph &G) {

G.vexnum=MAX;

13

G.arcnum=MAX;

for(int i=0;i

void CreateGraphic(ALGraph &G) {

int i,j,s,n;

ArcNode *p,*pp;

char str1[10],str2[10];

scanf(\,&G.vexnum); for(i=0;i

scanf(\,&G.arcnum); for(i=0;iadjvex=s; pp->info1=str3[i]; pp->info2=n; pp->next=NULL; ID[s]++; if(G.vertices[j].first!=NULL) { p=G.vertices[j].first; if(p->next!=NULL) { while(p->next->next!=NULL) { p=p->next; } p=p->next; } p->next=pp; }

14

else G.vertices[j].first=pp; } }

Status InitStack(Stack &S) {

S.base=(Elemtype *)malloc(SIZEMAX*sizeof(Elemtype)); if(!S.base) exit (OVERFLOW); S.top=S.base;

S.maxsize=SIZEMAX; return OK; }

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

if(S.top==S.base) return ERROR; e=*(--S.top); return OK; }

Status Push(Stack &S,int e) {

if(S.top-S.base>=S.maxsize) { 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; }

*(S.top++)=e; //*(S.top)=e,S.top++; return OK; }

Status Empty(Stack S) {

if(S.top==S.base) return OK; else return ERROR; }

Status Topo(ALGraph G,Stack &T) {

int i,j,k;

ArcNode *p;

Stack S; InitStack(S);

for(j=0;j

15