教学方案计划编制问答课程教学设计报告.doc

-! 中北大学 数据结构与算法课程设计 说 明 书 学 院、系： 软件学院 专 业： 软件工程 学 生 姓 名： 学 号： 设 计 题 目： 教学计划编制问题 起 迄 日 期: 2013年12月9日-2013年12月20日 指 导 教 师: 2013 年12月 20 日 1需求分析 1. 在大学的某个专业中选取几个课程作为顶点,通过各门课的先修关系来构建个图,该图用邻接表来存储,邻接表的头结点存储每门课的信息. 2. 本程序的目的是为用户编排课程,根据用户输入的信息来编排出每学期要学的课程. 3.测试数据： 学期总数：6；学分上限：9；本专业共开设12门课，课程号从C00到C11，学分顺序为2,3,4,3,2,3,4,4,7,5,2,3。 2概要设计 1.抽象数据类型图的定义如下： ADT Graph{ 数据对象V:V是具有相同特性的数据元素的集合,称为顶点集. 数据关系R: R={VR} VR={(v,w)|v,w∈V,(v,w)表示v和w之间存在直接先修关系} 基本操作P: void CreatGraph(ALGraph *); void FindInDegree(ALGraph , int * ); int TopologicalOrder(ALGraph G,AdjList R,struct Name name[]) int LocateVex(ALGraph G, VertexType u)/* 查找图中某个顶点位置 */ }ADT Graph 2.栈的定义如下： ADT Stack{ 数据对象:D={ai|ai∈ElemSet,i=1,2,…n,n>=0} 数据关系:R1={﹤ai-1 ai﹥|ai-1,ai∈D,i=2,…,n} 基本操作： void InitStack (SqStack *S); int StackEmpty(SqStack S); void Push(SqStack *S, int ); int Pop(SqStack *S, int *e); }ADT Stack 3.本程序有两个模块，调用关系简单：主程序模块→ 拓扑排序模块 3系统完成功能及功能框图 end 采用第二种策略：使课程尽可能地集中在前几个学期中 根据教学计划中的课程及其关系和学分定义图的顶点和边的结构体 创建图CreateGraph（）：结合先修关系的AOV网，采用邻接链表存储 菜单OUTPUT()：显示代号所对应课程及课程的先修课程 前插法 main 拓扑排序TopoSort(G)：将课程排序后并决定出每学期所学课程 输出图G的信息Display(G)：将图的顶点和弧边输出 图3.1系统功能框图 0 C1 1 ^ 5 ^ 11 ^ 11 10 6 7 ^ 6 ^ 4 ^ 7 2 ^ 11 3 4 ^ 9 ^ 1 C2 2 C3 3 C4 4 C5 5 C6 6 C7 ^ 7 C8 ^ 8 C9 9 C10 10 C11 11 C12 ^ 图3.2 邻接表 对每个顶点求入度，并存入数组InDegree[i]中（i=0…n） 初始化栈Stack,Counter=0 Return OK Return ERROR 依次将入度为0的顶点存入栈中 对以i号顶点为尾弧的每个邻接点的入度减1，并将入度减1后为零的顶点号压入栈中，输出i，计数器加1(Counter++) 推出栈顶的一个元素（入度为零的顶点号）至i，输出i，计数器加1（Counter++） 堆栈是否为空？ n个顶点全输出 Y Y N Y N Y 图3.3 拓扑排序流程图 C1 C4 C5 C7 C2 C3 C8 C9 C12 C10 C11 C6 图3.4 课程先修关系图 4 详细设计 1. 图的邻接表的存储表示，即结构体的定义： 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; 2. 建立图的邻接链表： printf("请输入下列课程的先修课程(无先修课程输入0 结束后也输入0)\n"); for (h=0;hAdjOfV = j; p->next = G.ver[i].first; // 插在表头 G.ver[i].first = p; scanf("%s",va); getchar(); } 3. 输出图的顶点和边： printf("%d个顶点", G.vexnum); for (i = 0;i < G.vexnum;++i)printf("%4s", G.ver[i].data); printf(" \n%d条弧边:\n",G.arcnum); for (i = 0;i < G.vexnum;i++) { p = G.ver[i].first; while (p) { printf("%s---->%s\n",G.ver[i].data,G.ver[p->AdjOfV].data); p = p->next; } } 4. 通过栈实现拓扑排序： 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[i]) Push(S, i); // 入度为0者进栈 count = 0; // 对输出顶点计数 while (!StackEmpty(S)) { Pop(S, i); printf("%s(%d学分),",G.ver[i].data,G.ver[i].grades); R[j++] = G.ver[i]; //将当前的拓扑序列保存起来 ++count; // 输出i号顶点并计数 for (p =G.ver[i].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;/**/ } 5.主程序和其他伪码算法： 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); } 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; } int LocateVex(ALGraph G, VertexType u)/* 查找图中某个顶点位置 */ { int i; for (i = 0;i < G.vexnum;++i) if (strcmp(u,G.ver[i].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[i].data); getchar(); G.ver[i].first = NULL; } printf("请输入%d个课程的学分值:",G.vexnum); for (i = 0;i < G.vexnum;++i) { scanf("%d",&G.ver[i].grades);getchar(); } printf("请输入下列课程的先修课程(无先修课程输入0 结束后也输入0)\n"); for (h=0;hAdjOfV = j; p->next = G.ver[i].first; // 插在表头 G.ver[i].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[i].data); printf(" \n%d条弧边:\n",G.arcnum); for (i = 0;i < G.vexnum;i++) { p = G.ver[i].first; while (p) { printf("%s---->%s\n",G.ver[i].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[i] = 0; for (i = 0;i < G.vexnum;i++) { p = G.ver[i].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(" C程序设计"); if(strcmp(str,name[1].c)==0)printf(" 模拟数字电路"); if(strcmp(str,name[2].c)==0)printf(" 数据结构"); if(strcmp(str,name[3].c)==0)printf(" C++面向对象 "); 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(" 电工技术"); } 4 界面设计 5 源代码 #include #include #include #include #define N 12 #define MAXOfNAME 3 //最多字符个数 #define MAX_VER 100 //最大顶点数 #define StackofNUM 20 //存储空间初始分配量 #define StackforMore 5 // 存储空间分配增量 int TotalOfTerms ; //学期总数 int MaxScores; typedef struct SqStack { int *a; int *top; int size; //分配的存储空间 }SqStack; 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 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; } int LocateVex(ALGraph G, VertexType u)/* 查找图中某个顶点位置 */ { int i; for (i = 0;i < G.vexnum;++i) if (strcmp(u,G.ver[i].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[i].data); getchar(); G.ver[i].first = NULL; } printf("请输入%d个课程的学分值:",G.vexnum); for (i = 0;i < G.vexnum;++i) { scanf("%d",&G.ver[i].grades);getchar(); } printf("请输入下列课程的先修课程(无先修课程输入0 结束后也输入0)\n"); for (h=0;hAdjOfV = j; p->next = G.ver[i].first; // 插在表头 G.ver[i].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[i].data); printf(" \n%d条弧边:\n",G.arcnum); for (i = 0;i < G.vexnum;i++) { p = G.ver[i].first; while (p) { printf("%s---->%s\n",G.ver[i].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[i] = 0; for (i = 0;i < G.vexnum;i++) { p = G.ver[i].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(" c程序设计"); if(strcmp(str,name[1].c)==0)printf(" 模拟数字电路"); if(strcmp(str,name[2].c)==0)printf(" 数据结构"); if(strcmp(str,name[3].c)==0)printf(" C++面向对象 "); 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(" 电工技术"); } int TopologicalOrder(ALGraph G,AdjList R,struct Name name[]) { int i, k, j = 0, count, indegree[MAX_VER]; char q=1,Z=0; SqStack S; ArcNode *p; FindInDegree(G, indegree); // 对各顶点求入度 InitStack(S); // 初始化栈 for (i = 0;i < G.vexnum;++i) //建零入度顶点栈S if (!indegree[i]) Push(S, i); // 入度为0者进栈 count = 0; // 对输出顶点计数 while (!StackEmpty(S)) { Pop(S, i); printf("%s(%d学分),",G.ver[i].data,G.ver[i].grades); R[j++] = G.ver[i]; //将当前的拓扑序列保存起来 ++count; // 输出i号顶点并计数 for (p =G.ver[i].first; p; p=p->next)// 对i号顶点的每个邻接点的入度减1 { k = p->AdjOfV; if (!(--indegree[k])) // 若入度减为0,则入栈 Push(S, k); } } if (count < G.vexnum) { printf("此有向图有回路无法完成拓扑排序");