中北大学数据结构与算法课程设计说明书学院、系：软件学院专业：软件工程学生姓名：学号：设计题目：教学计划编制问题起迄日期: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 Graph2.栈的定义如下：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 Stack3.本程序有两个模块，调用关系简单：主程序模块→拓扑排序模块3系统完成功能及功能框图图3.1系统功能框图1图3.2 邻接表图3.3 拓扑排序流程图图3.4 课程先修关系图4 详细设计1.图的邻接表的存储表示，即结构体的定义：typedef struct ArcNode{i nt AdjOfV; // 该弧所指向的顶点的位置s truct ArcNode *next; //指向下一条弧的指针}ArcNode;typedef char VertexType[MAXOfNAME];typedef struct //链接表{V ertexType data; //顶点信息i nt grades; //存储学分信息A rcNode *first; //指向第一条依附该顶点的弧的指针}VNode, AdjList[MAX_VER]; // 头结点typedef struct{A djList ver; //vertices 存储课程名i nt vexnum, arcnum; // 图的当前顶点数和弧数}ALGraph;2. 建立图的邻接链表：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[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[]) {i nt i, k, j = 0, count, indegree[MAX_VER];S qStack S;A rcNode *p;F indInDegree(G, indegree); // 对各顶点求入度I nitStack(S); // 初始化栈f or (i = 0;i < G.vexnum;++i) //建零入度顶点栈Sif (!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"},{"C 10"},{"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));i f (!S.a)exit(-1);S.top =S.a;S.size =StackofNUM;r eturn 1;}int StackEmpty(SqStack S) /*判断栈是否为空*/{i f (S.top == S.a)return 1;e lse return 0;}int Push(SqStack &S, int x)/*入栈*/{i f (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;r eturn 1;}int Pop(SqStack &S, int &x) /*出栈*/{i f (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;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[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<stdio.h>#include<stdlib.h>#include<math.h>#include<string.h>#define N 12#define MAXOfNAME 3 //最多字符个数#define MAX_VER 100 //最大顶点数#define StackofNUM 20 //存储空间初始分配量#define StackforMore 5 // 存储空间分配增量int TotalOfTerms ; //学期总数int MaxScores;typedef struct SqStack{i nt *a;i nt *top;i nt size; //分配的存储空间}SqStack;typedef struct ArcNode{i nt AdjOfV; // 该弧所指向的顶点的位置s truct ArcNode *next; //指向下一条弧的指针}ArcNode;typedef char VertexType[MAXOfNAME];typedef struct //链接表{V ertexType data; //顶点信息i nt grades; //存储学分信息A rcNode *first; //指向第一条依附该顶点的弧的指针}VNode, AdjList[MAX_VER]; // 头结点typedef struct{A djList ver; //vertices 存储课程名i nt vexnum, arcnum; // 图的当前顶点数和弧数}ALGraph; //学分上限int InitStack(SqStack S) /*栈的初始化*/{S.a= (int *)malloc(StackofNUM * sizeof(int));i f (!S.a)exit(-1);S.top =S.a;S.size =StackofNUM;r eturn 1;}int StackEmpty(SqStack S) /*判断栈是否为空*/{i f (S.top == S.a)return 1;e lse return 0;}int Push(SqStack S, int x)/*入栈*/{i f (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;r eturn 1;}int Pop(SqStack S, int x) /*出栈*/{i f (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;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[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[]){i nt i, k, j = 0, count, indegree[MAX_VER];c har q=1,Z=0;S qStack S;A rcNode *p;F indInDegree(G, indegree); // 对各顶点求入度I nitStack(S); // 初始化栈f or (i = 0;i < G.vexnum;++i) //建零入度顶点栈Sif (!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");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;/**/}int main(){ALGraph G;AdjList R;struct Name name[N]={{"C1"},{"C2"},{"C3"},{"C4"},{"C5"},{"C6"},{"C7"},{"C8"},{"C9"},{"C10"} ,{"C11"},{"C12"}};printf(" ***************教学计划编制问题**************\n" );printf（" ************製作人张启尧董茁华 **************\n"）;printf( "请输入学期总数:");scanf("%d",&TotalOfTerms);getchar();printf("请输入学期的学分上限:");scanf("%d",&MaxScores);getchar();CreateGraph(G);Display(G);TopologicalOrder(G,R,name); return 0;}8 心得体会。