数据结构实验报告教学计划编制.doc
- 文档编号:1306444
- 上传时间:2023-04-30
- 格式:DOC
- 页数:17
- 大小:315.50KB
数据结构实验报告教学计划编制.doc
《数据结构实验报告教学计划编制.doc》由会员分享,可在线阅读,更多相关《数据结构实验报告教学计划编制.doc(17页珍藏版)》请在冰点文库上搜索。
数据结构与程序设计实验
实验报告
课程名称
数据结构与程序设计实验
课程编号
0906550
实验项目名称
教学计划编制
学号
年级
姓名
专业
计算机科学与技术
学生所在学院
计算机学院
指导教师
杨静
实验室名称地点
21B276
哈尔滨工程大学
实验报告五
实验课名称:
数据结构与程序设计实验
实验名称:
教学计划编制
班级:
学号:
姓名:
时间:
2016.05.03
一、问题描述
学历进修需要学生在一定的时间内完成一定的课程学习,每一门课有一定的
学分,修满学分,可获取相应的学历。
因为有些课程内容是另一些课程的学习基
础,所以课程学习之间存有一定的先后次序。
如:
某学历的计算机专业需要学习的课程及课程之间的关系如表1所示。
表1计算机专业进修课程
课程进修关系图
课程编号
课程名称
学分
C1
程序设计基础
2
C2
离散数学
3
C3
数据结构
4
C4
汇编语言
3
C5
程序设计与分析
2
C6
计算机原理
3
C7
编译原理
4
C8
操作系统
4
C9
高等数学
7
C10
线性代数
5
C11
普通物理
2
C12
数值分析
3
C13
软件工程
3
C14
数据库原理
3
本设计的主要任务是根据需要完成的课程的先修关系、每学期开设的课程总
数及总的学习时间,制定出教学计划。
需事先的基本功能如下。
a.课程进修目录的读入。
b.课程进修目录的编辑,如课程增加、删除、信息修改等。
c.满足一定条件的教学计划的输出。
二、数据结构设计
1.以邻接表存储课程名和学分
#defineMAX_VERTEX_NUM100
typedefstructArcNode{//弧结构
intadjvex;//该弧所指向的顶点的位置;
structArcNode*nextarc;//指向下一条弧的指针
InfoType*info;//弧的权值指针
}ArcNode;//表结点
typedefstruct{//头节点
VertexTypedata;//顶点信息
ArcNode*firstarc;//第一个表结点的地址,指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];
typedefstruct{
AdjListvertices,vertices2;//分别存课程名和学分
intvexnum,arcnum;//图的当前顶点数和弧数
intkind;//图的种类标志
}ALGraph;//图
2.拓扑排序时为了避免重复检测入度为0的顶点,用栈暂存所有入度为0的顶点
typedefstructSqStack{
SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
三、算法设计
1.利用邻接表作为存储结构,构造课程先后关系的AOV网
intLocateVex(ALGraphG,VertexTypeu){//返回顶点u在图G中的位置
inti;
for(i=0;i if(strcmp(u,G.vertices[i].data)==0) returni; return-1; } StatusCreateGraph(ALGraph&G){//构造图 inti,j,k; VertexTypev1,v2;//顶点信息,字符串类型 ArcNode*p;//指向第一条依附某顶点的弧的指针 printf("请输入教学计划的课程数: ");//课程数即为顶点数 scanf("%d",&G.vexnum); printf("请输入课程先修关系数(弧的数目): "); scanf("%d",&G.arcnum); printf("请输入%d个课程的名称(以字符代替): \n",G.vexnum); for(i=0;i scanf("%s",G.vertices[i].data);//存储课程名 G.vertices[i].firstarc=NULL; } printf("请输入%d个课程的学分值: \n",(G).vexnum); for(i=0;i scanf("%s",G.vertices2[i].data);//存储学分 } printf("请顺序输入每条弧的弧尾和弧头(以空格作为间隔): \n"); for(k=0;k scanf("%s%s",v1,v2); i=LocateVex(G,v1); j=LocateVex(G,v2); p=(ArcNode*)malloc(sizeof(ArcNode));//新建一个弧节点 p->adjvex=j;//指向下一个顶点的位置 p->info=NULL; p->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p; } returnOK; } 2.在拓扑排序时为了避免重复检测入度为0的顶点,需要用栈暂存所有入度为0的顶点,以下为栈的相关操作 StatusInitStack(SqStack*S){//构造一个空栈 (*S).base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(! (*S).base) exit(OVERFLOW); (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; returnOK; } voidClearStack(SqStack*S){//清空栈 S->top=S->base; } StatusStackEmpty(SqStackS){//判断栈是否为空 if(S.top==S.base) returnTRUE; else returnFALSE; } StatusPop(SqStack*S,SElemType*e){ if((*S).top==(*S).base) returnERROR; *e=*--(*S).top; returnOK; } StatusPush(SqStack*S,SElemTypee){ if((*S).top-(*S).base>=(*S).stacksize){ (*S).base=(SElemType*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType)); if(! (*S).base) exit(OVERFLOW); (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; } *((*S).top)++=e; returnOK; } 3.拓扑排序并输出课程设计 a.在有向图中选一个没有前驱的顶点且输出之 b.从图中删除该顶点和所有以它为尾的弧 重复a,b直至全部顶点均已输出,或者不存在无前驱的顶点(图中存在环) StatusTopologicalSort(ALGraphG){//输出G顶点的拓扑排序结果 inti,k,count; intindegree[MAX_VERTEX_NUM];//indegree数组存放顶点入度 boolhas=false; SqStackS; pathonea; pathtwob; ArcNode*p; FindInDegree(G,indegree);//对各顶点求入度indegree[0..vernum-1] InitStack(&S); for(i=0;i if(! indegree[i]) Push(&S,i);//入度为0者入栈 } count=0;//对输出顶点计数 while(! StackEmpty(S)){ Pop(&S,&i); a[i]=*G.vertices[i].data;//课程名; b[i]=*G.vertices2[i].data;//学分; printf("课程%s→学分%s",G.vertices[i].data,G.vertices2[i].data); ++count; for(p=G.vertices[i].firstarc;p;p=p->nextarc){ k=p->adjvex; if(! (--indegree[k]))//对i号顶点的每个邻接点的入度-1 Push(&S,k); } } if(count printf("此有向图有回路\n"); returnERROR; }else{ printf("为一个拓扑序列。 \n\n"); has=true; } printf("各学期中的学习负担尽量均匀(输入1)\n"); printf("用尽可能短的时间完成教学计划(输入2)? \n"); intpattern; printf("请选择(1or2): "); scanf("%d",&pattern); FindInDegree(G,indegree);//对各顶点求入度indegree[0..vernum-1] ClearStack(&S); printf("=====================================================\n"); printf("教学计划如下: \n"); intxq=1;//学期数; intxfh;//学分和; intnow=0; inttop=G.vexnum/term_num;//平均每学期课程数; intpjxf=sum(G)/term_num;//每学期平均学分; while(xq<=term_num+1){ intresult[20];//某个学期的课程; intm=0; xfh=0; now=0;//当前学期课程数; for(i=0;i if(0==indegree[i]) Push(&S,i); } if(xq==term_num+1&&! StackEmpty(S)){ printf("还有课程未安排! \n"); } while(! StackEmpty(S)&&xq<=term_num){ intxf; Pop(&S,&i);//弹出栈顶元素; xf=atoi(G.vertices2[i].data);//atoi: 字符串转换成整型数,xf: 学分; xfh=xfh+xf; now++; if(xfh>credit_lim){ ClearStack(&S); break; } if(pattern==1){ if(xq! =term_num/2&&now>top){ ClearStack(&S);//该操作使程序跳出此内层的while循环; now=0; break; } } if(pattern==2){ if(xq! =1&&xq! =term_num/2&&xq! =term_num/2-1&&now>top){ ClearStack(&S); now=0; break; } } indegree[i]--;//减为-1,避免被再次计入; for(p=G.vertices[i].firstarc;p;p=p->nextarc){ k=p->adjvex; indegree[k]--; if(indegree[k]==0) Push(&S,k); } result[m]=i; m++; } if(xq<=term_num){ printf("第%d个学期的课程为: ",xq); for(intj=0;j printf("课程%s",G.vertices[result[j]].data); } } printf("\n"); xq++; ClearStack(&S); } printf("=====================================================\n"); returnOK; } 4.其他辅助操作 voidDisplay(ALGraphG){//输出图的信息 inti; ArcNode*p; switch(G.kind){ caseDG: printf("有向图\n"); } printf("%d个顶点: \n",G.vexnum); for(i=0;i printf("%s",G.vertices[i].data); printf("\n%d条弧: \n",G.arcnum); for(i=0;i p=G.vertices[i].firstarc; while(p){ printf("%s→%s",G.vertices[i].data,G.vertices[p->adjvex].data); p=p->nextarc; } printf("\n"); } } voidFindInDegree(ALGraphG,intindegree[]){//求顶点的入度 inti; ArcNode*p; for(i=0;i indegree[i]=0; for(i=0;i p=G.vertices[i].firstarc; while(p){ indegree[p->adjvex]++; p=p->nextarc; } } } Statussum(ALGraphG){//求大学所有课程总学分; intz=0; for(inti=0;i z+=atoi(G.vertices2[i].data); } returnz; } 四、界面设计 输入参数包括: 学期总数,一学期的学分上限,课程数,弧的数目,每门课的课程号、学分和直接先修课的关系。 输出各门课程所对应的学分,以及每学期各门课程的安排。 所有输入输出均以提示给出。 五、运行测试与分析 1.输入学期总数,学分上限,课程数,弧的数目 2.输入每门课的课程号,学分,与直接先修课的关系(以弧的形式给出) 3.构造图并输出图的信息 4.按各学期中的学习负担尽量均匀地制定教学计划 5.按尽可能短的时间完成学习,制定教学计划 6.当存在回路时输出提示 六、实验收获与思考 通过实际的编程,巩固了图的邻接表存储。 拓扑排序等知识,同时在编程过程中发现了自己的不足,遇到了很多语法错误及逻辑错误,通过不断的调试解决问题,使我对编程有了更加深入的体会和认识。 七、附录(源代码) #include #include #include #include #include #defineTRUE1 #defineFALSE0 #defineOK1 #defineERROR0 #defineINFEASIBLE-1 typedefintStatus;//Status是函数的返回类型 typedefintBoolean; #defineMAX_NAME10//顶点字符串的最大长度 #defineMAX_CLASS_NUM100 intZ=0; intX=0; intterm_num,credit_lim,q=1; typedefintInfoType;//权值 typedefcharVertexType[MAX_NAME];//字符串类型 #defineMAX_VERTEX_NUM100 typedefenum{DG}GraphKind;//{有向图,有向网,无向图,无向网} typedefstructArcNode{//弧结构 intadjvex;//该弧所指向的顶点的位置; structArcNode*nextarc;//指向下一条弧的指针 InfoType*info;//弧的权值指针 }ArcNode;//表结点 typedefstruct{//头节点 VertexTypedata;//顶点信息 ArcNode*firstarc;//第一个表结点的地址,指向第一条依附该顶点的弧的指针 }VNode,AdjList[MAX_VERTEX_NUM]; typedefstruct{ AdjListvertices,vertices2;//分别存课程名和学分 intvexnum,arcnum;//图的当前顶点数和弧数 intkind;//图的种类标志 }ALGraph;//图 intLocateVex(ALGraphG,VertexTypeu){//返回顶点u在图G中的位置 inti; for(i=0;i if(strcmp(u,G.vertices[i].data)==0) returni; return-1; } StatusCreateGraph(ALGraph&G){//构造图 inti,j,k; VertexTypev1,v2;//顶点信息,字符串类型 ArcNode*p;//指向第一条依附某顶点的弧的指针 printf("请输入教学计划的课程数: ");//课程数即为顶点数 scanf("%d",&G.vexnum); printf("请输入课程先修关系数(弧的数目): "); scanf("%d",&G.arcnum); printf("请输入%d个课程的名称(以字符代替): \n",G.vexnum); for(i=0;i scanf("%s",G.vertices[i].data);//存储课程名 G.vertices[i].firstarc=NULL; } printf("请输入%d个课程的学分值: \n",(G).vexnum); for(i=0;i
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 报告 教学计划 编制