课程设计实例.docx
- 文档编号:14963872
- 上传时间:2023-06-28
- 格式:DOCX
- 页数:19
- 大小:103.09KB
课程设计实例.docx
《课程设计实例.docx》由会员分享,可在线阅读,更多相关《课程设计实例.docx(19页珍藏版)》请在冰点文库上搜索。
课程设计实例
设计性综合性实验
实验课题名称:
院系:
计算机科学与技术学院专业:
网络工程
课程:
数据结构教师:
学号:
姓名:
(组长)
学号:
姓名:
学号:
姓名:
学号:
姓名:
学号:
姓名:
学号:
姓名:
至学年度学期
实验名称:
教学计划编制问题
实验性质:
设计性(*) 综合性(*)
实验器材:
PC机并装有VC++6.0环境
实验目的:
解决教学计划编制问题
实验任务:
通过解决教学计划编制问题了解拓扑排序问题并得到深入理解
实验内容、过程及结果:
一.问题描述
我们知道教学计划在编制的过程中,有一个层次的关系。
比如说:
数值分析必须在高等数学学完之后才可以学习,数据结构必须要在学习了一两门程序设计语言之后才可以学习。
也就是说有的课程必须要在学习完了某些课程之后才可以学习。
二.设计思路
编制教学计划,当然涉及到的课程都要给学完。
所以我们可以将所以的课程编制成一张图,然后遍历图。
由于课程有前续后继的关系,所以用AOV网是最合适。
对AOV网进行拓扑排序即可以得出结果。
对AOV网进行拓扑排序有两种情况:
广度优先和深度优先。
在进行深度优先周游时,我们要考虑到一种情况。
例如:
高等数学和C语言编程是并列的两门学科,他们之间没有前续后继的关系,可以同时进行学习。
高等数学是数值分析和电子电路的基础课程,电子电路又是模拟电子电路的基础课程。
C语言编程是数据结构的基础课程,数据结构是算法设计与分析的基础课程。
如果按照深度优先周游的话就有可能将上面几门课程排成:
C语言程序设计,数据结构,算法设计与分析,高等数学,电子电路,模拟电子电路。
这样的教学计划很明显不符合实际教学的需要。
因此我们应该进行广度优先周游,将高等数学和C语言程序设计先学,再学其他后继课程。
三.解决问题
计算机系的课程如下:
(只罗列出具有前续后继关系的课程,像马列等课程由于和其他课程没有关联,所以在课程排序好后考虑每个学期的课程量时随机加入)
1,高等数学17,JAVA程序设计
2,概率论和数理统计18,编译原理
3,线形代数19,现代通信技术
4,C语言程序设计20,计算机网络
5,电路理论21,软件工程
6,模拟电子技术22,算法设计与分析
7,数字逻辑23,人工智能
8,面向对象编程技术24,Matlab编程技术
9,数据结构25,电子商务
10,汇编语言26,分布式数据库
11,计算机组成原理27,网络数据库编程
12,微机原理与接口技术28,计算机图形学
13,操作系统29,图象处理
14,数据库概论30,嵌入式系统
15,数值分析31,多媒体技术
16,计算机控制基础
下面是课程之间先后关系的AOV网:
将上面的AOV网用邻接表表示如下:
入度
顶点
边表
30
∧
0
1
15
28
∧
0
2
15
28
∧
28
0
3
15
28
∧
0
4
8
9
10
24
0
5
6
∧
1
6
7
∧
1
7
11
∧
1
8
14
17
19
21
∧
1
9
14
21
22
∧
1
10
11
∧
2
11
12
∧
1
12
13
16
18
30
∧
1
13
∧
2
14
26
∧
3
15
∧
1
16
23
∧
1
17
∧
1
18
∧
1
19
20
∧
1
20
25
31
∧
2
21
∧
1
22
23
∧
2
23
∧
1
24
∧
1
25
∧
1
26
27
∧
1
27
∧
4
28
29
∧
1
29
∧
2
30
∧
1
31
∧
四.实现
1.功能函数设计
pGraphListinitGraph(void);
此函数的作用是初始化一个AOV网,入度都初始化为零,边表都初始化为NULL。
课程代号从1按次序到31。
pLinkQueuecreatEmptyQueue(void);
创建一个空队列
intisEmptyQueue(pLinkQueuepQueue);
判断队列是否问空,如果为空返回1,否则返回0
voidenQueue(pLinkQueuepQueue,intx);
入对操作
voiddeQueue(pLinkQueuepQueue);
出队操作
intgetQueueHead(pLinkQueuepQueue);
得到队列头部的数据
voidfindIndegree(pGraphListpList);
得到每个顶点的入度
voidtopoSort(pGraphListpList);
拓扑排序
pGraphListinitEdgeList(pGraphListpList,intx,intindex);
初始化边表。
即在主函数中调用一次此函数就要一个结点存入指定的地方
下面是源代码:
#include
#include
intpTopo[31];//存放拓扑排序的结果
//为什么使用全局变量,在运行与测试中进行说明
structedgeNode;
typedefstructedgeNode*pEdgeNode;
typedefstructedgeNode*pEdgeList;
//邻接表中边表的结点
structedgeNode
{
intindex;
pEdgeNodenext;
};
//存放顶点信息的结构体
structvertexNode
{
intvertexInfo;
intinDegree;
pEdgeListnext;
};
typedefstructvertexNode*pVertexNode;
//对AOV网进行封装
structgraphList
{
intn;
pVertexNodevertex[31];
};
typedefstructgraphList*pGraphList;
structnode;
typedefstructnode*pNode;
//链接表队列中的结点
structnode
{
intinfo;
pNodelink;
};
//队列的封装
structlinkQueue
{
pNodehead;
pNoderear;
};
typedefstructlinkQueue*pLinkQueue;
//初始化图
pGraphListinitGraph(void);
//创建空队列
pLinkQueuecreatEmptyQueue(void);
//判断队列是否为空
intisEmptyQueue(pLinkQueuepQueue);
//入队操作
voidenQueue(pLinkQueuepQueue,intx);
//出队操作
voiddeQueue(pLinkQueuepQueue);
//取队列头部的元素
intgetQueueHead(pLinkQueuepQueue);
//得到每个结点的入度
voidfindIndegree(pGraphListpList);
//拓扑排序
voidtopoSort(pGraphListpList);
//输入每个边表
pGraphListinitEdgeList(pGraphListpList,intx,intindex);
intmain()
{
char*array[31];//存放课程名称
pGraphListpList;
pList=initGraph();
pList=initEdgeList(pList,15,0);
pList=initEdgeList(pList,28,0);
pList=initEdgeList(pList,15,1);
pList=initEdgeList(pList,28,1);
pList=initEdgeList(pList,15,2);
pList=initEdgeList(pList,28,2);
pList=initEdgeList(pList,8,3);
pList=initEdgeList(pList,9,3);
pList=initEdgeList(pList,10,3);
pList=initEdgeList(pList,24,3);
pList=initEdgeList(pList,28,3);
pList=initEdgeList(pList,30,3);
pList=initEdgeList(pList,6,4);
pList=initEdgeList(pList,7,5);
pList=initEdgeList(pList,11,6);
pList=initEdgeList(pList,14,7);
pList=initEdgeList(pList,17,7);
pList=initEdgeList(pList,19,7);
pList=initEdgeList(pList,21,7);
pList=initEdgeList(pList,14,8);
pList=initEdgeList(pList,21,8);
pList=initEdgeList(pList,22,8);
pList=initEdgeList(pList,11,9);
pList=initEdgeList(pList,12,10);
pList=initEdgeList(pList,13,11);
pList=initEdgeList(pList,16,11);
pList=initEdgeList(pList,18,11);
pList=initEdgeList(pList,30,11);
pList=initEdgeList(pList,26,13);
pList=initEdgeList(pList,23,15);
pList=initEdgeList(pList,20,18);
pList=initEdgeList(pList,25,19);
pList=initEdgeList(pList,31,19);
pList=initEdgeList(pList,23,21);
pList=initEdgeList(pList,27,25);
pList=initEdgeList(pList,29,27);
array[0]="1.高等数学";
array[1]="2.概率论与数理统计";
array[2]="3.线形代数";
array[3]="4.C语言程序设计";
array[4]="5.电路理论";
array[5]="6.模拟电子技术";
array[6]="7.数字逻辑";
array[7]="8.面向对象编程技术";
array[8]="9.数据结构";
array[9]="10.汇编语言";
array[10]="11.计算机组成原理";
array[11]="12.微机原理与接口技术";
array[12]="13.操作系统";
array[13]="14.数据库概论";
array[14]="15.数值分析";
array[15]="16.计算机控制基础";
array[16]="17.JAVA程序设计";
array[17]="18.编译原理";
array[18]="19.现代通信技术";
array[19]="20.计算机网络";
array[20]="21.软件工程";
array[21]="22.算法设计与分析";
array[22]="23.人工智能";
array[23]="24.Matlab编程技术";
array[24]="25.电子商务";
array[25]="26.分布式数据库";
array[26]="27.网络数据库编程";
array[27]="28.计算机图形学";
array[28]="29.图象处理";
array[29]="30.嵌入式系统";
array[30]="31.多媒体技术";
topoSort(pList);
for(inti=0;i<31;i++)
printf("%s\n",array[pTopo[i]-1]);
return0;
}
pGraphListinitGraph(void)//初始化图,边表都赋值为NULL
{
inti;
pGraphListpList;
pList=(pGraphList)malloc(sizeof(structgraphList));
for(i=0;i<31;i++)
pList->vertex[i]=(pVertexNode)malloc(sizeof(structvertexNode));
pList->n=31;
for(i=0;i<31;i++)
pList->vertex[i]->vertexInfo=i+1;
for(i=0;i<31;i++)
pList->vertex[i]->next=NULL;
returnpList;
}
pLinkQueuecreatEmptyQueue(void)//创建空对列
{
pLinkQueuepQueue;
pQueue=(pLinkQueue)malloc(sizeof(structlinkQueue));
if(pQueue!
=NULL)
{
pQueue->head=NULL;
pQueue->rear=NULL;
}
else
printf("Outofspace!
\n");
returnpQueue;
}
intisEmptyQueue(pLinkQueuepQueue)
{
returnpQueue->head==NULL;
}
voidenQueue(pLinkQueuepQueue,intx)//判断队列是否为空
{
pNodep;
p=(pNode)malloc(sizeof(structnode));
if(p==NULL)
printf("Outofspace!
\n");
else
{
p->info=x;
p->link=NULL;
if(pQueue->head==NULL)
pQueue->head=p;
else
pQueue->rear->link=p;
pQueue->rear=p;
}
}
voiddeQueue(pLinkQueuepQueue)//出队
{
pNodep;
if(pQueue->head==NULL)
printf("Emptyqueue.\n");
else
{
p=pQueue->head;
pQueue->head=p->link;
free(p);
}
}
intgetQueueHead(pLinkQueuepQueue)//取队列头部的数据
{
if(pQueue->head==NULL)
printf("Emptyqueue.\n");
else
returnpQueue->head->info;
}
voidfindIndegree(pGraphListpList)//计算出每个顶点的入度
{
inti;
pEdgeNodep;
for(i=0;i
pList->vertex[i]->inDegree=0;
for(i=0;i
{
p=pList->vertex[i]->next;
while(p!
=NULL)
{
pList->vertex[p->index-1]->inDegree++;
p=p->next;
}
}
}
voidtopoSort(pGraphListpList)//拓扑排序
{
intelement;
inti;
intn=0;
intk;
pLinkQueuepQueue;
pEdgeListp;
findIndegree(pList);
pQueue=creatEmptyQueue();
for(i=0;i
if(pList->vertex[i]->inDegree==0)
{
enQueue(pQueue,pList->vertex[i]->vertexIn
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 课程设计 实例