《数据结构实验报告-教学计划编制.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告-教学计划编制.docx（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、敕据构造与程本殁计实龄实验报告课程名称数据构造与程序设计实验课程编号0906550实验工程名称教学方案编制学号年级姓名专业计算机科学与技术学生所在学院计算机学院指导教师杨静实验室名称地点21B276哈尔滨工程大学实验报告五一、问题描述实验课名称：数据构造与程序设计实验实验名称：教学方案编制班级：学号：姓名：时间:学历进修需要学生在一定的时间内完成一定的课程学习，每一门课有一定的 学分，修满学分，可获取相应的学历。因为有些课程内容是另一些课程的学习基 础，所以课程学习之间存有一定的先后次序。如：某学历的计算机专业需要学习的课程及六、实验收获与思考通过实际的编程，稳固了图的邻接表存储。拓扑排序等知
2、识，同时在编程过程中发现了 自己的缺乏，遇到了很多语法错误及逻辑错误，通过不断的调试解决问题，使我对编程有了 更加深入的体会和认识。七、附录（源代码）#include ttinclude #include ttinclude #include ttdefineTRUE 1ttdefine FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE-1typedef int Status; / Status 是函数的返回类型typedef int Boolean;#define MAX_NAME 10 顶点字符串的最大长度#define MAX_CL
3、ASS_NUM 100int Z=0;int X=0;int term_num, creditjim, q=l;typedef int InfoType; 权值typedef char VertexTypeMAX_NAME; 字符串类型#define MAX_VERTEX_NUM 100typedef enumDGGraphKind;有向图，有向网,无向图，无向网typedef struct ArcNode 弧构造int adjvex;该弧所指向的顶点的位置；struct ArcNode * next arc;指向下一条弧的指针InfoType *info; 弧的权值指针ArcNode;表结点
4、typedef struct 头节点VertexType data; 顶点信息ArcNode *firstarc; 第一个表结点的地址,指向第一条依附该顶点的弧的指针 VNode, Adj Li st M AX_V E RTEX_N U M ;typedef structAdj List vertices,vertices2;分别存课程名和学分int vexnum,arcnum; 图的当前顶点数和弧数int kind; 图的种类标志ALGraph; 图int LocateVex(ALGraph G, VertexType u)返回顶点 u 在图 G 中的位置 int i;for(i=0; iG
5、.vexnum; +i)if(strcmp(u, G.verticesi.data)=O)return i;return -1;)Status CreateGraph(ALGraph &G)构造图int ijk;VertexType vl,v2;顶点信息,字符串类型ArcNode *p;指向第一条依附某顶点的弧的指针printf(“请输入教学方案的课程数: 个课程数即为顶点数scanf(%d,& G.vexnum);printf(“请输入课程先修关系数(弧的数目):);scanf(%dz& G.arcnum);printf(请输入d个课程的名称(以字符代替):nG.vexnum);for(i=
6、0; iG.vexnum; +i) scanf(%s，G.verticesi.data); 存储课程名 G.verticesi.firstarc=NULL;printf(请输入d个课程的学分值:n,(G).vexnum);for(i=0; iG.vexnum; +i) scanfCsG.verticesZIiJ.data);/)printf(“请顺序输入每条弧的弧尾和弧头(以空格作为间隔):n“)；for(k=0; kadjvex = j; 指向下一个顶点的位置 p-info = NULL;p-nextarc = G.verticesi.firstarc;G.verticesi.firstar
7、c = p;return OK;void Display(ALGraph G)输出图的信息int i;ArcNode * p;switch(G.kind)case DG: printf(有向图n”)；)printf(%d 个顶点：n,G.vexnum);for(i=0;iG.vexnum;+i)printf(%s z G.verticesi.data);printf(n%d 条弧:n”,G.arcnum);for(i=0;i%s, G.verticesi.data, G.verticesp-adjvex.data); p=p-nextarc;)printf(n);)void FindlnDeg
8、ree(ALGraph G,int indegree) 求顶点的入度int i;ArcNode *p;for(i=0;iG.vexnum;i+)indegreei=O;for(i=0;iadjvex+;p=p-nextarc;)typedef int SEIemType;#define STACK_INIT_SIZE 10#define STACKINCREMENT 2typedef struct SqStack为了防止重复检测入度为0的顶点，暂存所有入度为0的顶点 SEIemType *base;SEIemType *top;int stacksize;SqStack;Status lnit
9、Stack(SqStack *S)构造一个空栈(*S).base=(SEIemType *)malloc(STACK_INIT_SIZE*sizeof(SEIemType);if(!(*S).base)exit(OVERFLOW);(*S).top=(*S).base;(*S).stacksize=STACK INIT SIZE;return OK;)void ClearStack(SqStack *S) 清空栈 S-top=S-base;)Status StackEmpty(SqStack S) / 判断栈是否为空if(S.top=S.base)return TRUE;elsereturn
10、FALSE;Status Pop(SqStack *S,S日emType *e)if(*S).top=(*S).base)return ERROR;*e=*-(*S).top;return OK;)Status Push(SqStack *S,S日emType e)if(*S).top-(*S).base=(*S).stacksize)(*S).base=(SEIemType*)realloc(*S).base,(*S).stacksize+STACKINCREMENT)*sizeof(SEIemType);if(!(*S).base)exit(OVERFLOW);(*S).top=(*S).
11、base+(*S).stacksize;(*S).stacksize+= STACKINCREMENT;*(*S).top)+=e;return OK;)Status sum(ALGraph G)求大学所有课程总学分；int z=0;for(int i=0; i G.vexnum; i+)z += atoi(G.vertices2i.data);return z;)typedef int pathoneMAX_CLASS_NUM;typedef int pathtwoMAX CLASS NUM;Status TopologicalSortfALGraph G)输出 G 顶点的拓扑排序结果 in
12、t i,k,count;int indegreeMAX_VERTEX_NUM; /indegree 数组存放顶点入度 Boolean has = FALSE;SqStack S;pathone a;pathtwo b;ArcNode * p;FindlnDegree(G,indegree); /对各顶点求入度 indegreeO.vernum-1 lnitStack(&S);for(i=0;i 学分 s zG.verticesi.data,G.vertices2i.data); +count;for(p=G.verticesi.firstarc; p; p=p-nextarc)k=p-adjv
13、ex;if(!(-indegreek) 对i号顶点的每个邻接点的入度 Push(&S,k);)if(count G.vexnum)图中有不存在前驱的顶点printf(此有向图有回路n“)；return ERROR;elseprintf(为一个拓扑序列。nn);has=TRUE;printf(各学期中的学习负担尽量均匀(输入1) n);printf(“用尽可能短的时间完成教学方案(输入2)n“)；int pattern;printf(请选择(1 or 2):);scanf(”d”,&pattern);FindlnDegree(G,indegree); /对各顶点求入度 indegree0.ver
14、num-1 ClearStack(&S);printf(=n);printf(教学方案如下：nH);int xq = 1;学期数；int xfh; 学分和；int now=0;int top = G.vexnum / term_num ; 平均每学期课程数；int pjxf = sum(G) / term_num ; 每学期平均学分；while(xq = term_num + 1)int result20;某个学期的课程;int m = 0;xfh = 0;now=0;当前学期课程数；for(i=0;iG.vexnum;+i)if(0 = indegreei) Push(&S,i);)if(x
15、q = term_num+l & !StackEmpty(S) printf(还有课程未安排！ n);)while(!StackEmpty(S) & xq creditjim) ClearStack(&S); break;)if(pattern = 1)if(xq!=term_num/2 & nowtop)ClearStack(&S); 该操作使程序跳出此内层的while循环； now = 0;break;)if(pattern = 2)if(xq!=l & xq!=term_num/2 & xq!=term_num/2-l & nowtop) ClearStack(&S);now = 0;
16、break;)indegreei-; 减为-1,防止被再次计入；for(p=G.verticesi.firstarc; p; p=p-nextarc) k=p-adjvex; indegreek-;if(indegreek=O) Push(&S,k);) resultm=i; m+;)if(xq = term_num)printf(“第d个学期的课程为：，xq);for(int j=0; jm; j+)printf(课程5，G.verticesresultj.data); ) printf(Hnn); xq+; ClearStack(&S);printf(=n); return OK;)int
17、 main()printf(教学方案编制问题n“)；printf(拓扑排序 AOV-网)nn“)；/AOV(activity on vertex)-网:顶点表示活动，弧表示活动间优先关系的有向图; int CONTINUE = 1;printf(n);ALGraph f;图的邻接表存储；printf(”请输入学期总数:)； scanf(”d”,&term_num);printf(“请输入每学期的学分上限:)； scanf(%d,&creditjim);CreateGraph(f);Display(f);while(CONTINUE != 0) TopologicalSort(f);printf
18、(“n按1继续，按。完毕:)； scanf(”d，&CONTINUE);return OK;)教师评分:教师签字:课程之间的关系如表1所示。表1计算机专业进修课程课程进修关系图课程编号课程名称学分o*Cl程序设计根基2C2离散数学3C3数据构造4C4汇编语言3C5程序设计与分析2C6计算机原理3C7编译原理4C8操作系统4C9高等数学7CIO线性代数5Cll普通物理2C12数值分析3C13软件工程3C14数据库原理3本设计的主要任务是根据需要完成的课程的先修关系、每学期开设的课程总 数及总的学习时间，制定出教学方案。需事先的 基本功能如下。a.课程进修目录的读入。b.课程进修目录的编辑，如课程
19、增加、删除、信息修改等。c.满足一定条件的教学方案的输出。二、数据构造设计1 .以邻接表存储课程名和学分#define MAX_VERTEX_NUM 100typedef struct ArcNode 弧构造int adjvex;该弧所指向的顶点的位置；struct ArcNode *nextarc;指向下一条弧的指针InfoType *info; 弧的权值指针ArcNode;表结点typedef struct 头节点VertexType data; 顶点信息ArcNode *firstarc; 第一个表结点的地址，指向第一条依附该顶点的弧的指针 VNode, Adj List M AX_VE
20、 RTEX_N UM;typedef structAdj List vertices,vertices2;分别存课程名和学分int vexnum,arcnum; 图的当前顶点数和弧数int kind; 图的种类标志ALGraph; 图2 .拓扑排序时为了防止重复检测入度为0的顶点，用栈暂存所有入度为0的顶点 typedef struct SqStackSEIemType *base;SEIemType *top;int stacksize;SqStack;三、算法设计1 .利用邻接表作为存储构造，构造课程先后关系的AOV网int LocateVex(ALGraph G, VertexType
21、u)返回顶点 u 在图 G 中的位置 int i;for(i=0; iG.vexnum; +i)if(strcmp(u, G.verticesi.data)=O) return i;return -1;)Status CreateGraph(ALGraph &G)构造图 int i jk;VertexType vl/v2;顶点信息，字符串类型ArcNode *p;指向第一条依附某顶点的弧的指针printf(“请输入教学方案的课程数:);课程数即为顶点数scanf(%d,& G.vexnum);printf(“请输入课程先修关系数(弧的数目):);scanf(%d,& G.arcnum);pri
22、ntf(请输入d个课程的名称(以字符代替):n，G.vexnum);for(i=0; iG.vexnum; +i) scanf(”%s，G.verticesi.data); /存储课程名 G.verticesi.firstarc=NULL;printf(请输入d个课程的学分值:n, (G).vexnum);for(i=0; iG.vexnum; +i) scanf(%s,G.vertices2i.data);/#fi#printf(请顺序输入每条弧的弧尾和弧头(以空格作为间隔):n“)；for(k=0; kadjvex = j; 指向下一个顶点的位置 p-info = NULL;p-nexta
23、rc = G.verticesi.firstarc;G.verticesi.firstarc = p;return OK;)2 .在拓扑排序时为了防止重复检测入度为0的顶点，需要用栈暂存所有入度为0的顶点，以 下为栈的相关操作Status lnitStack(SqStack *S)构造一个空栈(*S).base=(SEIemType *)malloc(STACK_INIT_SIZE*sizeof(SEIemType);if(!(*S).base)exit(OVERFLOW);(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;return OK;
24、)void ClearStack(SqStack *S) 清空栈 S-top=S-base;)Status StackEmptyfSqStack S) / 判断栈是否为空if(S.top=S.base)return TRUE;elsereturn FALSE;)Status Pop(SqStack *S/SEIemType *e)if(*S).top=(*S).base)return ERROR;*e=*-(*S).top;return OK;)Status Push(SqStack *S,S日emType e)if(*S).top-(*S).base=(*S).stacksize)(*S).
25、base=(SEIemType*)realloc(*S).base,(*S).stacksize+STACKINCREMENT)*sizeof(SEIemType);if(!(*S).base)exit(OVERFLOW);(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+二 STACKINCREMENT;*(*S).top)+=e;return OK;)3 .拓扑排序并输出课程设计a.在有向图中选一个没有前驱的顶点且输出之b.从图中删除该顶点和所有以它为尾的弧重复a,b直至全部顶点均已输出，或者不存在无前驱的顶点(图中存在环)Status To
26、pologicalSort(ALGraph G)输出 G 顶点的拓扑排序结果int i,k?count;int indegreeMAX_VERTEX_NUM; /indegree 数组存放顶点入度bool has = false;SqStack S;pathone a;pathtwo b;ArcNode * p;FindlnDegree(G,indegree); /对各顶点求入度 indegreeO.vernum-1 lnitStack(&S);for(i=0;inextarc) k=p-adjvex;if(!(-indegreek) 对i号顶点的每个邻接点的入度-1 Push(&S,k);)
27、if(count G.vexnum)图中有不存在前驱的顶点print,此有向图有回路n“)；return ERROR;elseprint为一个拓扑序列。nn);has=true;printf(“各学期中的学习负担尽量均匀(输入)n);printf(“用尽可能短的时间完成教学方案(输入2) n);int pattern;printf(请选择(1 or 2):);scanf(%d,&pattern);FindlnDegree(Gjndegree); /对各顶点求入度 indegree0.vernum-1ClearStack(&S);printf(=n); printf(教学方案如下：nH);int
28、 xq = 1;学期数；int xfh; 学分和；int now=0;int top = G.vexnum / term_num ;平均每学期课程数；int pjxf = sum(G) / term num ; 每学期平均学分；while(xq = term_num + 1)int result20; 某个学期的课程；int m = 0;xfh = 0;now=0; 当前学期课程数；for(i=0;iG.vexnum;+i)if(0 = indegreei) Push(&S,i);)if(xq = term_num+l & !StackEmpty(S) printf(“还有课程未安排！ n);
29、)while(!StackEmpty(S) & xq credit_lim) ClearStack(&S); break;)if(pattern = 1)if(xq!=term_num/2 & nowtop)ClearStack(&S); 该操作使程序跳出此内层的while循环； now = 0;break;)if(pattern = 2)if(xq!=l & xq!=term_num/5 & xq!=term_num/2-l & nowtop) ClearStack(&S);now = 0; break;)indegree-; 减为-1,防止被再次计入;for(p=G.verticesi.f
30、irstarc; p; p=p-nextarc)k=p-adjvex;indegreek-;if(indegreek=O) Push(&S,k);)resultm=i;m+;)if(xq = term_num)printfC第1个学期的课程为：、xq);for(int j=0; jm; j+)printf(课程5，G.verticesresultj.data);) ) printf(nH); xq+; ClearStack(&S);printf(=n); return OK;)4 .其他辅助操作void Display(ALGraph G)输出图的信息 int i;ArcNode * p;sw
31、itch(G.kind)case DG: printf(有向图n”)； printf(%d 个顶点：n，G.vexnum); for(i=0;iG.vexnum;+i)printf(%s, G.verticesi.data); printf(“n%d 条弧:n”,G.arcnum); for(i=0;i%s, G.verticesi.data, G.verticesp-adjvex.data); p=p-nextarc;) printf(n);)void FindlnDegree(ALGraph G,int indegree) 求顶点的入度 int i;ArcNode *p;for(i=0;i
32、G.vexnum;i+) indegreei=O;for(i=0;iadjvex+;p=p-nextarc;)Status sum(ALGraph G) 求大学所有课程总学分；int z=0;for(int i=0; i G.vexnum; i+)z += atoi(G.vertices2i.data);return z;)四、界面设计输入参数包括：学期总数，一学期的学分上限，课程数，弧的数目，每门课的课程号、 学分和直接先修课的关系。输出各门课程所对应的学分，以及每学期各门课程的安排。所 有输入输出均以提示给出。五、运行测试与分析1.输入学期总数，学分上限，课程数，弧的数目驾学刹编制问题 学的公 的短。 中能1 期可择 学只选 各课程1课程2课程3 课程4课程5爵爵 mKrnrnlrmr. 讲课讲讲 tr JTT-TTT .rTr ,ITT Rq1234按1继续，按。结束：0.当存在回路时输出提示请顺序输入每条弧的弧尾和强头（以空格作为间隔）： 211(Iin顶3弧5 4个2条一 3 5 17 13比有向图有回路核1继续，按0结束: