数据结构 C 代码 7.4: 关键路径

摘要: 关键路径算法有一定的难度, 先从左到右, 再从右到左.1. 代码将 Java 代码https://blog.csdn.net/minfanphd/article/details/116975772 稍作整理, 告诉 DeepSeek: 将如下 Java 代码翻译为 C 代码.#includestdio.h#includestdlib.h#includestring.h#includestdbool.h#defineMAX_DISTANCE10000typedefstructIntMatrix{int**data;introws;intcols;}IntMatrix;IntMatrix*IntMatrix_create(introws,intcols);IntMatrix*IntMatrix_copy(constIntMatrix*src);IntMatrix*IntMatrix_identity(introws);voidIntMatrix_free(IntMatrix*matrix);voidIntMatrix_print(IntMatrix*matrix);intIntMatrix_add(IntMatrix*self,constIntMatrix*other);IntMatrix*IntMatrix_multiply(constIntMatrix*a,constIntMatrix*b);typedefstructNet{intnumNodes;IntMatrix*weightMatrix;}Net;Net*Net_create(intnumNodes);Net*Net_create_from_matrix(int**matrix,introws,intcols);voidNet_free(Net*net);bool*criticalPath(Net*net);// IntMatrix 函数实现IntMatrix*IntMatrix_create(introws,intcols){IntMatrix*matrix(IntMatrix*)malloc(sizeof(IntMatrix));matrix-rowsrows;matrix-colscols;matrix-data(int**)malloc(rows*sizeof(int*));for(inti0;irows;i){matrix-data[i](int*)malloc(cols*sizeof(int));memset(matrix-data[i],0,cols*sizeof(int));}returnmatrix;}IntMatrix*IntMatrix_copy(constIntMatrix*src){IntMatrix*destIntMatrix_create(src-rows,src-cols);for(inti0;isrc-rows;i){memcpy(dest-data[i],src-data[i],src-cols*sizeof(int));}returndest;}IntMatrix*IntMatrix_identity(introws){IntMatrix*matrixIntMatrix_create(rows,rows);for(inti0;irows;i){matrix-data[i][i]1;}returnmatrix;}voidIntMatrix_free(IntMatrix*matrix){for(inti0;imatrix-rows;i){free(matrix-data[i]);}free(matrix-data);free(matrix);}voidIntMatrix_print(IntMatrix*matrix){printf([);for(inti0;imatrix-rows;i){if(i0)printf( );printf([);for(intj0;jmatrix-cols;j){printf(%d,matrix-data[i][j]);if(jmatrix-cols-1)printf(, );}printf(]);if(imatrix-rows-1)printf(,\n);}printf(]\n);}intIntMatrix_add(IntMatrix*self,constIntMatrix*other){if(self-rows!other-rows||self-cols!other-cols){fprintf(stderr,Matrix dimensions mismatch\n);return-1;}for(inti0;iself-rows;i){for(intj0;jself-cols;j){self-data[i][j]other-data[i][j];}}return0;}IntMatrix*IntMatrix_multiply(constIntMatrix*a,constIntMatrix*b){if(a-cols!b-rows){fprintf(stderr,Matrix multiplication dimensions mismatch\n);returnNULL;}IntMatrix*resultIntMatrix_create(a-rows,b-cols);for(inti0;ia-rows;i){for(intj0;jb-cols;j){for(intk0;ka-cols;k){result-data[i][j]a-data[i][k]*b-data[k][j];}}}returnresult;}// Net 函数实现Net*Net_create(intnumNodes){Net*net(Net*)malloc(sizeof(Net));net-numNodesnumNodes;net-weightMatrixIntMatrix_create(numNodes,numNodes);for(inti0;inumNodes;i){for(intj0;jnumNodes;j){net-weightMatrix-data[i][j]MAX_DISTANCE;}}returnnet;}Net*Net_create_from_matrix(int**matrix,introws,intcols){Net*net(Net*)malloc(sizeof(Net));net-weightMatrixIntMatrix_create(rows,cols);net-numNodesrows;for(inti0;irows;i){memcpy(net-weightMatrix-data[i],matrix[i],cols*sizeof(int));}returnnet;}voidNet_free(Net*net){IntMatrix_free(net-weightMatrix);free(net);}bool*criticalPath(Net*net){intnumNodesnet-numNodes;int*tempInDegrees(int*)calloc(numNodes,sizeof(int));int*tempEarliestTime(int*)calloc(numNodes,sizeof(int));int*tempOutDegrees(int*)calloc(numNodes,sizeof(int));int*tempLatestTime(int*)malloc(numNodes*sizeof(int));bool*result(bool*)calloc(numNodes,sizeof(bool));// 计算入度for(inti0;inumNodes;i){for(intj0;jnumNodes;j){if(net-weightMatrix-data[i][j]!-1){tempInDegrees[j];}}}// 拓扑排序计算最早时间int*inDegreesCopy(int*)malloc(numNodes*sizeof(int));memcpy(inDegreesCopy,tempInDegrees,numNodes*sizeof(int));for(inti0;inumNodes;i){if(inDegreesCopy[i]!0)continue;for(intj0;jnumNodes;j){if(net-weightMatrix-data[i][j]!-1){intnewTimetempEarliestTime[i]net-weightMatrix-data[i][j];if(newTimetempEarliestTime[j]){tempEarliestTime[j]newTime;}inDegreesCopy[j]--;}}}printf(Earliest time: );for(inti0;inumNodes;i){printf(%d, ,tempEarliestTime[i]);}printf(\n);// 计算出度for(inti0;inumNodes;i){for(intj0;jnumNodes;j){if(net-weightMatrix-data[i][j]!-1){tempOutDegrees[i];}}}// 初始化最晚时间intcriticalTimetempEarliestTime[numNodes-1];for(inti0;inumNodes;i){tempLatestTime[i]criticalTime;}// 反向拓扑排序计算最晚时间int*outDegreesCopy(int*)malloc(numNodes*sizeof(int));memcpy(outDegreesCopy,tempOutDegrees,numNodes*sizeof(int));for(intinumNodes-1;i0;i--){if(outDegreesCopy[i]!0)continue;for(intj0;jnumNodes;j){if(net-weightMatrix-data[j][i]!-1){intnewTimetempLatestTime[i]-net-weightMatrix-data[j][i];if(newTimetempLatestTime[j]){tempLatestTime[j]newTime;}outDegreesCopy[j]--;}}}printf(Latest time: );for(inti0;inumNodes;i){printf(%d, ,tempLatestTime[i]);}printf(\n);// 确定关键路径for(inti0;inumNodes;i){result[i](tempEarliestTime[i]tempLatestTime[i]);}free(tempInDegrees);free(tempEarliestTime);free(tempOutDegrees);free(tempLatestTime);free(inDegreesCopy);free(outDegreesCopy);returnresult;}// 测试代码intmain(){inttempMatrix3[6][6]{{-1,3,2,-1,-1,-1},{-1,-1,-1,2,3,-1},{-1,-1,-1,4,-1,3},{-1,-1,-1,-1,-1,2},{-1,-1,-1,-1,-1,1},{-1,-1,-1,-1,-1,-1}};// 转换为二维指针数组int**matrix(int**)malloc(6*sizeof(int*));for(inti0;i6;i){matrix[i](int*)malloc(6*sizeof(int));memcpy(matrix[i],tempMatrix3[i],6*sizeof(int));}Net*netNet_create_from_matrix(matrix,6,6);bool*criticalcriticalPath(net);printf(Critical nodes: );for(inti0;i6;i){if(critical[i])printf(%d ,i);}printf(\n);// 释放内存for(inti0;i6;i)free(matrix[i]);free(matrix);Net_free(net);free(critical);return0;}2. 运行结果Earliest time:0,3,2,6,6,8,Latest time:0,4,2,6,7,8,Critical nodes:02353. 小结主要看 criticalPath 函数.逻辑有一点难度, 当然, 也很有趣.注意: 当前代码有 bug, 我要找时间来重新弄一下.