2007429028周跃华实验四

班级 数学1班 姓名 周跃华 学号 2007429028 日期 2008-12-15

一、需求分析

1． 程序的功能：

大学中的每个专业都有几十门基础课程、专业课程及选修课程，学生必须分几个学期完成这些课程才能毕业。教学计划的制定就是合理的编排这些课程，使得学生能够顺利的进行学习。这些课程中，有些课程是独立于其它课程的基础课，有些课程却需要其它先行课程；一般四年制本科教学前7个学期（三年半）进行理论课程的学习，第8个学期实习；教学计划的编排必须充分考虑这些因素。 2． 输入输出的要求：

假定学习年限是固定的，每学年包含两个学期，各专业开设的课程是确定的，每门课程是否有先修课、有几门先修课也是确定的。要求制定教学计划，合理的安排各学期开授的课程。要求各学期课程门数、学分的分布较均匀。

二、概要设计

1． 本程序所用的抽象数据类型的定义； typedef struct node{ int adjevx; struct node *next; }EdgeNode;

typedef struct vnode{ int num; char name[25]; float chour; int indegree; char quality; char flag; int flag1; int flag2; }Information;

typedef struct vnode1{ Information point; EdgeNode *firstedge; }VNode; typedef struct { VNode Adjlist[MAX]; int n,e; float sum; }AOVgraph;

2． 主模块的流程及各子模块的主要功能；

void input():输依次输入课程的总数，AOV网中边的条数；输入AOV网中各个顶点的信息；输入该课程的课程名；输入该课程的学分；输入该课程的课序号；输入该

课程的入度；如果此课程需要多个学期修完，请输入【Y】；如果不是请输入【N】； void lesson(int i)： float Seq_Sort(int p):

void main():：主模块，通过对各个模块的调用实现教学计划的安排。 3． 模块之间的层次关系。 主 模 块

input lesson Seq Sort

三、详细设计

1． 采用c语言定义相关的数据类型； typedef struct node{ int adjevx; struct node *next; }EdgeNode;

typedef struct vnode{ int num; char name[25]; float chour; int indegree; char quality; char flag; int flag1; int flag2; }Information;

typedef struct vnode1{ Information point; EdgeNode *firstedge; }VNode;

typedef struct { VNode Adjlist[MAX]; int n,e; float sum; }AOVgraph;

AOVgraph *AOV; ；

2． 写出各模块的伪码算法；

void input() { int k=0,i=0,j; EdgeNode *s,*r; char ch; b=0;AOV->sum=0; printf(\"请依次输入课程的总数，AOV网中边的条数。(格式为: 课程的总数:边的条数):\\n\\n\");

scanf(\"%d:%d\ ch=getchar(); do { printf(\"\\n请输入AOV网中第%d个顶点的信息,还有%d个顶点没有输入：\\n\

printf(\"\\n请输入该课程的课程名:\\n\\n\"); scanf(\"%s\ ch=getchar(); AOV->Adjlist[i].point.quality='M'; b++;

printf(\"\\n请输入该课程的学分:\\n\\n\"); scanf(\"%f\ AOV->sum+=AOV->Adjlist[i].point.chour; printf(\"\\n请输入该课程的课序号:\\n\\n\"); scanf(\"%d\ printf(\"\\n请输入该课程的入度:\\n\\n\"); scanf(\"%d\ AOV->Adjlist[i].firstedge=NULL; ch=getchar(); printf(\"\\n如果此课程需要多个学期修完，请输入【Y】；如果不是请输入【N】:\\n\\n\");

scanf(\"%c\ AOV->Adjlist[i].point.flag2=0; if(AOV->Adjlist[i].point.indegree==0) AOV->Adjlist[i].point.flag1=0; else AOV->Adjlist[i].point.flag1=1; i++; ch=getchar(); if(AOV->n==i) { printf(\"\\n所有课程已输入完毕！\\n\"); break; } }while(1); printf(\"\\n以下为输入AOV网中各条边的信息:\\n\\n\");

do{ k++; printf(\"\\n请输入边的信息(输入格式为: i:j。i，j分别表示AOV网中的顶点对应的序号。):\\n\\n\");

scanf(\"%d:%d\ ch=getchar(); s=(EdgeNode *)malloc(sizeof(EdgeNode)); s->adjevx=j-1; if(AOV->Adjlist[i-1].firstedge==NULL) AOV->Adjlist[i-1].firstedge=s; else { r=AOV->Adjlist[i-1].firstedge; while(r->next!=NULL) r=r->next; r->next=s; } s->next=NULL; if(AOV->e==k) { printf(\"\\n边的信息输入结束。\\n\\n\"); break; } else printf(\"\\n还有%d条边没有输入。\\n\\n\ }while(1); }

void lesson(int i) { int k; EdgeNode *ptr;

sum2+=AOV->Adjlist[i].point.chour; if(sum2-AOV->sum/sAdjlist[i].point.chour) { fprintf(fp,\"%d %s %1.1f %c\\n\AOV->Adjlist[i].point.quality);

AOV->Adjlist[i].point.flag2=1; b--; q++; ptr=AOV->Adjlist[i].firstedge; while(ptr!=NULL) {

k=ptr->adjevx;

AOV->Adjlist[k].point.indegree--; ptr=ptr->next; } } else

sum2-=AOV->Adjlist[i].point.chour; }

float Seq_Sort(int p) { int i; float j; Information point1; char ch; for(i=0;in;i++) if(AOV->Adjlist[i].point.indegree==0&&AOV->Adjlist[i].point.quality=='M'&&AOV->Adjlist[i].point.flag1==0&&AOV->Adjlist[i].point.flag2==0)

lesson(i); j=sum2; printf(\"\\n第%d学年第%d学期所修学分为：%1.2f，课程数为：%d。如果想修选修课，请输入 Y ,否则输入 N: \\n\\n\

ch=getchar(); if(ch=='y'||ch=='Y') do { ch=getchar(); printf(\"\\n请输入选修课的信息:\\n\\n\"); printf(\"\\n请输入该课程的课程名:\\n\\n\"); scanf(\"%s\ ch=getchar(); printf(\"\\n请输入该课程的学分:\\n\\n\"); scanf(\"%f\ j+=point1.chour; q++; printf(\"\\n请输入该课程的课序号:\\n\\n\"); scanf(\"%d\ point1.quality='X'; fprintf(fp,\"%d %s %1.1f %c\\n\

printf(\"\\n现在所修学分为：%1.2f，课程数为：%d，继续输入选修课，请输入 Y ，否则输入 N:\\n\\n\

ch=getchar(); ch=getchar();

}while(ch=='Y'||ch=='y'); ch=getchar(); return j; }

void main() { int i,j,a; char *name1,ch; float sum4; AOV=(AOVgraph *)malloc(sizeof(AOVgraph)); printf(\" 由AOV网生成课表\\n\\n\"); printf(\"使用说明：\\n1.使用者自己画出AOV网且AOV网中只包含必修课程，选修课由本人填写，并且标明AOV网中顶点的序号，根据序号的顺序来输入顶点的信息和边的信息。\\n\\n2.课表中 X 表示选修，M 表示必须。\\n\");

printf(\"\\n请输入修完课程总的学期数:\\n\\n\"); scanf(\"%d\ s=a; printf(\"\\n本程序将各个学期的课表依次存放到文件中(*.txt格式),请输入各个文件的名字\\n\\n\");

name1=(char*) malloc(sizeof(char)); scanf(\"%s\ printf(\"\\n请输入AOV网中课程的信息:\\n\\n\"); input(); if((fp=fopen(name1,\"a+\"))==NULL) { printf(\"不能打开该文件!\\n\"); exit(0); } for(i=0;ifor(j=0;jn;j++)

if(AOV->Adjlist[j].point.indegree==0&&(AOV->Adjlist[j].point.flag=='y'||AOV->Adjlist[j].point.flag=='Y')&&AOV->Adjlist[j].point.flag1==0&&AOV->Adjlist[j].point.flag2==0)

lesson(j); sum4=Seq_Sort(i); fprintf(fp,\"\\n本学期总的学分为%1.2f，总的课程为%d\\n\ for(j=0;jn;j++) if(AOV->Adjlist[j].point.indegree==0) AOV->Adjlist[j].point.flag1=0;

AOV->sum=AOV->sum-sum2; sum2=0; s--; q=0; } fclose(fp); if(b>0) { printf(\"\\n还有必修课有必修课不能选上，排课时应该增加学期数！\\n\\n没修完的课程为：\\n\\n\");

printf(\"number name credit quality\\n\"); for(i=0;in;i++) if(AOV->Adjlist[i].point.flag2==0) printf(\"%d %s %1.1f %c\\n\AOV->Adjlist[i].point.quality);

printf(\" \\n请输入回车键退出程序后，请在调整学期数。\\n\"); ch=getchar(); } else { printf(\"\\n课表已经生成，输入回车键退出程序后，查看存放课表的文件。\\n\");

ch=getchar(); } }；

3． 画出函数的调用关系图。

四、调试分析

1．调试中遇到的问题及对问题的解决方法； 2．算法的时间复杂度和空间复杂度。

五、使用说明及测试结果

六、源程序

#include #include #include #define MAX 100 typedef struct node{ int adjevx; struct node *next;

}EdgeNode;

typedef struct vnode{ int num; char name[25]; float chour; int indegree; char quality; char flag; int flag1; int flag2; }Information;

typedef struct vnode1{ Information point; EdgeNode *firstedge; }VNode; typedef struct { VNode Adjlist[MAX]; int n,e; float sum; }AOVgraph;

AOVgraph *AOV; FILE *fp; int s,m,b,q=0; float sum2=0;

void input() { int k=0,i=0,j; EdgeNode *s,*r; char ch; b=0;AOV->sum=0; printf(\"请依次输入课程的总数，AOV网中边的条数。(格式为: 课程的总数:边的条数):\\n\\n\");

scanf(\"%d:%d\ ch=getchar(); do { printf(\"\\n请输入AOV网中第%d个顶点的信息,还有%d个顶点没有输入：\\n\

printf(\"\\n请输入该课程的课程名:\\n\\n\"); scanf(\"%s\ ch=getchar(); AOV->Adjlist[i].point.quality='M';

b++;

printf(\"\\n请输入该课程的学分:\\n\\n\"); scanf(\"%f\ AOV->sum+=AOV->Adjlist[i].point.chour; printf(\"\\n请输入该课程的课序号:\\n\\n\"); scanf(\"%d\ printf(\"\\n请输入该课程的入度:\\n\\n\"); scanf(\"%d\ AOV->Adjlist[i].firstedge=NULL; ch=getchar(); printf(\"\\n如果此课程需要多个学期修完，请输入【Y】；如果不是请输入【N】:\\n\\n\");

scanf(\"%c\ AOV->Adjlist[i].point.flag2=0; if(AOV->Adjlist[i].point.indegree==0) AOV->Adjlist[i].point.flag1=0; else AOV->Adjlist[i].point.flag1=1; i++; ch=getchar(); if(AOV->n==i) { printf(\"\\n所有课程已输入完毕！\\n\"); break; } }while(1); printf(\"\\n以下为输入AOV网中各条边的信息:\\n\\n\"); do{ k++; printf(\"\\n请输入边的信息(输入格式为: i:j。i，j分别表示AOV网中的顶点对应的序号。):\\n\\n\");

scanf(\"%d:%d\ ch=getchar(); s=(EdgeNode *)malloc(sizeof(EdgeNode)); s->adjevx=j-1; if(AOV->Adjlist[i-1].firstedge==NULL) AOV->Adjlist[i-1].firstedge=s; else { r=AOV->Adjlist[i-1].firstedge; while(r->next!=NULL) r=r->next; r->next=s; } s->next=NULL;

if(AOV->e==k) { printf(\"\\n边的信息输入结束。\\n\\n\"); break; } else printf(\"\\n还有%d条边没有输入。\\n\\n\ }while(1); }

void lesson(int i) { int k; EdgeNode *ptr;

sum2+=AOV->Adjlist[i].point.chour; if(sum2-AOV->sum/sAdjlist[i].point.chour) { fprintf(fp,\"%d %s %1.1f %c\\n\AOV->Adjlist[i].point.quality);

AOV->Adjlist[i].point.flag2=1; b--; q++; ptr=AOV->Adjlist[i].firstedge; while(ptr!=NULL) {

k=ptr->adjevx; AOV->Adjlist[k].point.indegree--; ptr=ptr->next; } } else

sum2-=AOV->Adjlist[i].point.chour; }

float Seq_Sort(int p) { int i; float j; Information point1; char ch; for(i=0;in;i++) if(AOV->Adjlist[i].point.indegree==0&&AOV->Adjlist[i].point.quality=='M'&&AOV->Adjlist[i].point.flag1==0&&AOV->Adjlist[i].point.flag2==0)

lesson(i); j=sum2; printf(\"\\n第%d学年第%d学期所修学分为：%1.2f，课程数为：%d。如果想修选修课，请输入 Y ,否则输入 N: \\n\\n\

ch=getchar(); if(ch=='y'||ch=='Y') do { ch=getchar(); printf(\"\\n请输入选修课的信息:\\n\\n\"); printf(\"\\n请输入该课程的课程名:\\n\\n\"); scanf(\"%s\ ch=getchar(); printf(\"\\n请输入该课程的学分:\\n\\n\"); scanf(\"%f\ j+=point1.chour; q++; printf(\"\\n请输入该课程的课序号:\\n\\n\"); scanf(\"%d\ point1.quality='X'; fprintf(fp,\"%d %s %1.1f %c\\n\

printf(\"\\n现在所修学分为：%1.2f，课程数为：%d，继续输入选修课，请输入 Y ，否则输入 N:\\n\\n\

ch=getchar(); ch=getchar(); }while(ch=='Y'||ch=='y'); ch=getchar(); return j; }

void main() { int i,j,a; char *name1,ch; float sum4; AOV=(AOVgraph *)malloc(sizeof(AOVgraph)); printf(\" 由AOV网生成课表\\n\\n\"); printf(\"使用说明：\\n1.使用者自己画出AOV网且AOV网中只包含必修课程，选修课由本人填写，并且标明AOV网中顶点的序号，根据序号的顺序来输入顶点的信息和边的信息。\\n\\n2.课表中 X 表示选修，M 表示必须。\\n\");

printf(\"\\n请输入修完课程总的学期数:\\n\\n\"); scanf(\"%d\ s=a;

printf(\"\\n本程序将各个学期的课表依次存放到文件中(*.txt格式),请输入各个文件的名字\\n\\n\");

name1=(char*) malloc(sizeof(char)); scanf(\"%s\ printf(\"\\n请输入AOV网中课程的信息:\\n\\n\"); input(); if((fp=fopen(name1,\"a+\"))==NULL) { printf(\"不能打开该文件!\\n\"); exit(0); } for(i=0;ifor(j=0;jn;j++)

if(AOV->Adjlist[j].point.indegree==0&&(AOV->Adjlist[j].point.flag=='y'||AOV->Adjlist[j].point.flag=='Y')&&AOV->Adjlist[j].point.flag1==0&&AOV->Adjlist[j].point.flag2==0)

lesson(j); sum4=Seq_Sort(i); fprintf(fp,\"\\n本学期总的学分为%1.2f，总的课程为%d\\n\ for(j=0;jn;j++) if(AOV->Adjlist[j].point.indegree==0) AOV->Adjlist[j].point.flag1=0; AOV->sum=AOV->sum-sum2; sum2=0; s--; q=0; } fclose(fp); if(b>0) { printf(\"\\n还有必修课有必修课不能选上，排课时应该增加学期数！\\n\\n没修完的课程为：\\n\\n\");

printf(\"number name credit quality\\n\"); for(i=0;in;i++) if(AOV->Adjlist[i].point.flag2==0) printf(\"%d %s %1.1f %c\\n\AOV->Adjlist[i].point.quality);

printf(\" \\n请输入回车键退出程序后，请在调整学期数。\\n\"); ch=getchar();

} else { printf(\"\\n课表已经生成，输入回车键退出程序后，查看存放课表的文件。\\n\");

ch=getchar(); } }