//C::::::::::::::::::教学计划编制问题.Cpp #include<stdio.h> #include<stdlib.h> #include<math.h> #include<string.h> #include "SeqStack.h"//为什么有错误？？？？？？？ #include "ALGraph.h"//为什么有错误？？？？？？？ #define N 12 // A:::::::::SeqStack.h #define StackofNUM 20 //存储空间初始分配量 #define StackforMore 5 // 存储空间分配增量 typedef struct SqStack { int *a; int *top; int size; //分配的存储空间 }SqStack; int InitStack(SqStack &S) /*栈的初始化*/ { S.a= (int *)malloc(StackofNUM * sizeof(int)); if (!S.a)exit(-1); S.top =S.a; S.size =StackofNUM; return 1; } int StackEmpty(SqStack S) /*判断栈是否为空*/ { if (S.top == S.a)return 1; else return 0; } int Push(SqStack &S, int x)/*入栈*/ { if (S.top - S.a >= S.size) {S.a = (int *) realloc ( S.a, (S.size + StackforMore) * sizeof(int)); if ( !S.a ) exit(-1); S.top =S.a +S.size; S.size +=StackforMore; } *S.top++ = x; return 1; } int Pop(SqStack &S, int &x) /*出栈*/ { if (S.top == S.a)return 0; x = *--S.top; return 1; } //B:::::::::ALGraph.h #define MAXOfNAME 3 //最多字符个数 #define MAX_VER 100 //最大顶点数 typedef struct ArcNode { int AdjOfV; // 该弧所指向的顶点的位置 struct ArcNode *next; //指向下一条弧的指针 }ArcNode; typedef char VertexType[MAXOfNAME]; typedef struct //链接表 { VertexType data; //顶点信息 int grades; //存储学分信息 ArcNode *first; //指向第一条依附该顶点的弧的指针 }VNode, AdjList[MAX_VER]; // 头结点 typedef struct { AdjList ver; //vertices 存储课程名 int vexnum, arcnum; // 图的当前顶点数和弧数 }ALGraph; int TotalOfTerms //学期总数 int MaxScores; //学分上限 int LocateVex(ALGraph G, VertexType u)/* 查找图中某个顶点位置 */ { int i; for (i = 0;i < G.vexnum;++i) if (strcmp(u,G.ver.data)==0)return i; return -1; } int CreateGraph(ALGraph &G) /*采用邻接表存储结构*/ { int i, j, h; VertexType va; ArcNode *p; printf("请输入教学计划的课程数: " ); scanf("%d",&G.vexnum); getchar(); printf( "请输入各个课程的先修课程的总和(弧总数): "); scanf("%d",&G.arcnum); getchar(); printf( "请输入%d个课程的课程号(最多%d个字符,字母+数字如C10):", G.vexnum,MAXOfNAME); for (i = 0;i < G.vexnum;++i) { scanf("%s",&G.ver.data); getchar(); G.ver.first = NULL; } printf("请输入%d个课程的学分值:",G.vexnum); for (i = 0;i < G.vexnum;++i) { scanf("%d",&G.ver.grades);getchar(); } printf("请输入下列课程的先修课程(无先修课程输入0 结束后也输入0)\n"); for (h=0;h<G.vexnum;++h) // 构造表结点链表,利用前插法 { printf("%s的先修课程:",G.ver[h].data); scanf("%s",va);getchar(); while (va[0]!='0') { i = LocateVex(G, va); //弧头 j = h; //弧尾 p = (ArcNode*)malloc(sizeof(ArcNode)); p->AdjOfV = j; p->next = G.ver.first; // 插在表头 G.ver.first = p; scanf("%s",va); getchar(); } } return 1; } void Display(ALGraph G) /* 输出图G的信息*/ { int i; ArcNode *p; printf("有向图\n"); printf("%d个顶点", G.vexnum); for (i = 0;i < G.vexnum;++i)printf("%4s", G.ver.data); printf(" \n%d条弧边:\n",G.arcnum); for (i = 0;i < G.vexnum;i++) { p = G.ver.first; while (p) { printf("%s---->%s\n",G.ver.data,G.ver[p->AdjOfV].data); p = p->next; } } } void FindInDegree(ALGraph G, int indegree[]) /*求顶点的入度*/ { int i; ArcNode *p; for (i = 0;i < G.vexnum;i++) indegree = 0; for (i = 0;i < G.vexnum;i++) { p = G.ver.first; while (p) { indegree[p->AdjOfV]++; p = p->next; } } } struct Name { char c[20]; }name; void CmpOfStr(VertexType str,struct Name name[],int n) /*让C1~C12分别与12门课程对应起来*/ { if(strcmp(str,name[0].c)==0)printf(" 程序设计基础"); if(strcmp(str,name[1].c)==0) printf(" 离散数学"); if(strcmp(str,name[2].c)==0) printf(" 数据结构"); if(strcmp(str,name[3].c)==0)printf(" 汇编语言 "); if(strcmp(str,name[4].c)==0) printf(" 语言的设计和分析 "); if(strcmp(str,name[5].c)==0)printf(" 计算机原理"); if(strcmp(str,name[6].c)==0)printf(" 编译原理"); if(strcmp(str,name[7].c)==0)printf(" 操作系统 "); if(strcmp(str,name[8].c)==0)printf(" 高等数学"); if(strcmp(str,name[9].c)==0)printf(" 线性代数"); if(strcmp(str,name[10].c)==0)printf(" 普通物理"); if(strcmp(str,name[11].c)==0)printf(" 数值分析"); //C::::::::::::::::::教学计划编制问题.Cpp #include<stdio.h> #include<stdlib.h> #include<math.h> #include<string.h> #include "SeqStack.h" #include "ALGraph.h" #define N 12 int TopologicalOrder(ALGraph G,AdjList R,struct Name name[]) { int i, k, j = 0, count, indegree[MAX_VER]; SqStack S; ArcNode *p; FindInDegree(G, indegree); // 对各顶点求入度 InitStack(S); // 初始化栈 for (i = 0;i < G.vexnum;++i) //建零入度顶点栈S if (!indegree) Push(S, i); // 入度为0者进栈 count = 0; // 对输出顶点计数 while (!StackEmpty(S)) { Pop(S, i); printf("%s(%d学分),",G.ver.data,G.ver.grades); R[j++] = G.ver; //将当前的拓扑序列保存起来 ++count; // 输出i号顶点并计数 for (p =G.ver.first; p; p=p->next)// 对i号顶点的每个邻接点的入度减1 { k = p->AdjOfV; if (!(--indegree[k])) // 若入度减为0,则入栈 Push(S, k); } } if (count < G.vexnum) {printf("此有向图有回路无法完成拓扑排序"); return 0; } else printf( " 为一个拓扑序列"); printf("\n"); int q=1,Z=0; while (q <= TotalOfTerms) { int C = R[Z].grades ; printf("\n第%d个学期应学课程:",q); while (C <= MaxScores) { C = C + R[Z+1].grades; if (Z < G.vexnum) { CmpOfStr(R[Z].data,name,N);/*让C1~C12分别与12门课程对应起来*/ ++Z; } } printf("\n"); if (q == TotalOfTerms) printf( "\nOK Over!"); q++; } return 1;} void main() { ALGraph G; AdjList R; struct Name name[N]={{"C1"},{"C2"},{"C3"},{"C4"},{"C5"},{"C6"},{"C7"},{"C8"},{"C9"},{"C10"},{"C11"},{"C12"}}; printf(" ***************教学计划编制问题**************\n" ); printf( "请以课件9-2上课程先序图为例输入学期总数:"); scanf("%d",&TotalOfTerms); getchar(); printf("请输入学期的学分上限（8或9）:"); scanf("%d",&MaxScores); getchar(); CreateGraph(G); Display(G); TopologicalOrder(G,R,name); }
| 
发表于 2015-1-9 17:34:24
收藏
转播
分享
