西南交通大学 数据结构实验期末课程设计.zip

#include <stdio.h> #include <stdlib.h> #include <iostream> #include <fstream> using namespace std; #define MAX_VERTEX_NUM 20 //最大顶点数 #define Stack_Add_Size 10 #define Stack_Init_Size 100 //图的邻接表存储结构 typedef struct ArcNode //弧结构 { int w; //权值 int adjverx; //该弧指向的顶点的位置 struct ArcNode *nextarc; //指向下一条弧 } ArcNode; typedef struct VNode //顶点 { int i; ArcNode *firstarc; } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vexs; //顶点数组集合 int vexnum, arcnum; //图的当前顶点数和弧数 } ALGraph; //栈的存储结构 typedef struct { int *base; int *top; int stacksize; } Stack; void InitStack(Stack &a)//初始化栈 { a.base = (int *)malloc(Stack_Init_Size * sizeof(int)); //给a.base分配内存 if (!a.base) exit(0); //内存分配失败则退出 a.top = a.base; //置栈为空 a.stacksize = Stack_Init_Size; } void Push(Stack &a, int c) //入栈算法 { if (a.stacksize <= a.top - a.base) //若栈满 { a.base = (int *)realloc(a.base, (a.stacksize + Stack_Add_Size) * sizeof(int)); //重新分配 if (!a.base) exit(0); a.top = a.base + a.stacksize; //更新top指针 a.stacksize += Stack_Add_Size; } *a.top++ = c; //先赋值后+1 } bool EmptyStack(Stack &S)//判断栈是否为空 { if (S.base == S.top) { return true; } return false; } int Pop(Stack &a)//弹出栈顶数据 { if (a.base == a.top) //若栈空，则退出 { printf("it's empty"); exit(0); } else { a.top--; return *a.top; //否则弹出栈顶值 } } void CreatAlGraph(ALGraph &G)//建立图的邻接表存储结构 { ifstream f("data.txt");//使用相对路径 if (!f.is_open()) { cout << "can not open data.txt" << endl; return; } f >> G.vexnum >> G.arcnum; for (int i = 0; i < G.vexnum; i++) //初始化 { G.vexs[i].i = i; G.vexs[i].firstarc = NULL; } for (int k = 0; k < G.arcnum; k++) { ArcNode *pr, *p, *q = (ArcNode *)malloc(sizeof(ArcNode)); //q为待指向弧 int i, j, w; f >> i >> j >> w; //读取两点以及权值 q->adjverx = j; //建立第i行表结点 q->nextarc = NULL; q->w = w; pr = NULL; p = G.vexs[i].firstarc; //如果不为空表明i结点已有指向的结点 while (p && p->adjverx < j) { pr = p; p = p->nextarc; } if (pr == NULL) { q->nextarc = p; G.vexs[i].firstarc = q; } else { pr->nextarc = q; q->nextarc = p; } } f.close(); } int CalVex(ALGraph &G, int ve[], int vl[]) //求所有活动的最早与最晚开始时间 { //首先创建并初始化indegree数组 int *indegree = new int[G.vexnum]; int i, j, k, count; ArcNode *p; Stack S, T; for (i = 0; i < G.vexnum; i++) indegree[i] = 0; for (i = 0; i < G.vexnum; i++) for (p = G.vexs[i].firstarc; p != NULL; p = p->nextarc) indegree[p->adjverx]++; InitStack(S); InitStack(T); for (i = 0; i < G.vexnum; i++) //所有顶点的最早开始时间初始化为0 ve[i] = 0; for (i = 0; i < G.vexnum; i++) //源点入栈S(这里假定源点仅1个) if (!indegree[i]) { Push(S, i); k = i; //k保存源点下标 break; } count = 0;//存储已入栈的个数 //前向递推(拓扑排序) while (!EmptyStack(S)) { i = Pop(S); Push(T, i); count++; for (p = G.vexs[i].firstarc; p; p = p->nextarc) { if (!(--indegree[p->adjverx])) Push(S, p->adjverx); int w = ve[i] + p->w; if (ve[p->adjverx] < w)//取最大值 ve[p->adjverx] = w; } } delete[] indegree; if (count < G.vexnum) return -1;//表示有环结构 //反向递推 if (!EmptyStack(T)) j = Pop(T); //汇点出栈 //所有顶点最晚开始时间初始化为汇点最早开始时间 for (i = 0; i < G.vexnum; i++) vl[i] = ve[j]; while (!EmptyStack(T)) { i = Pop(T); for (p = G.vexs[i].firstarc; p; p = p->nextarc) { int w = vl[p->adjverx] - p->w; if (vl[i] > w)//取最小值 vl[i] = w; } } return k; //返回源点下标 } void PrintG(ALGraph &G, int ve[], int vl[])//输出最短路径上的结点 { cout<<"关键路径上顶点的的拓扑有序序列："; int i; for ( i = 0; i < G.vexnum; i=i+1){ for ( ArcNode* p = G.vexs[i].firstarc; p; p = p->nextarc) { int ee = ve[i];//活动的最早开始时间 int ll = vl[p->adjverx] - p->w;//活动的最晚开始时间 if (ee == ll){ cout<<G.vexs[i].i<<" "; i=p->adjverx-1;//只输出一条关键路径 break; } } } cout<<G.vexs[i-1].i<<"\n工程最短完成时间："<<vl[i-1]<<endl; } int main() { ALGraph G; int *ve = new int[G.vexnum], *vl = new int[G.vexnum]; CreatAlGraph(G); CalVex(G, ve, vl); PrintG(G,ve,vl); system("pause"); return 0; }