-
.
.
《算法与数据结构》课程设计报告
题目：
教学计划编制问题
专业：
计算机科学与技术
班级：
1002
学号：
1030030242
姓名：
巫爱萍
指导教师：
许文庆
完成日期：
2012
年
6
月
14
日
.
一、课程设计目的
本课程设计的目标就是要达到理论与实际应用相结合，
提高学生组织数据及<
/p>
编写大型程序的能力，并培养基本的、良好的程序设计技能以及合作能力。
设计中要求综合运用所学知识，
上机解决一些与实际
应用结合紧密的、
规模
较大的问题，通过分析、设计、编码、调
试等各环节的训练，使学生深刻理解、
牢固掌握数据结构和算法设计技术，掌握分析、解
决实际问题的能力。
通过这次设计，
要求在数据结构的逻辑特性和物理表示、
数据结构的选择和
应用
、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序
设计方法以及
上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
二、课程设计内容
针对计算机系本科
课程，依据其相互依赖关系制定课程安排计划，其相互依
赖关系如下图所示，并要求各学
期课程数目大致相同且搭配适当。
.
.
三、课程设计过程
1
．需求分析
以无歧
义的陈述说明程序设计的任务，强调的是程序要做什么？并明确规定：
(1)
输入的形式和输入值的范围；
创建邻接表时需要输入顶点数、
边
数、
顶点及其入度
和确定弧的两个顶点
的下标。
(2)
输出的形式；在主函数中输出拓扑排序序列。
(3)
程序所能达到的功能；
A
、求解上图的拓扑排序结果。
B
、上述课程在
4
学期
上完，
要求每学期上课的门数大致一样。
(4)
测试数据：
创建邻接表时输入的顶点数：
7
创建邻接表时输入的顶点数：
8
创建
邻接表时输入的顶点及其入度分别为：
（
1,0
）
、
（
2,0
）
、
（
3,1
）
、
（
4,2
）
、
（
5,2
）
、
（
6,2
）
、
（
7,1
）
创建邻接表时输入的确定弧的两个顶点
的下标为：
<1,3>
、
<3,4>
、
<2,4
>
、
<2,7>
、
<2,5>
、
<7,6>
、
<4,6>
、
<4,5>
2
．概要设计
1
）本程序包含
7
个函数：
①
主函数
main()
②
创建邻接表函数
creatgraph(algraph&
g)
③
拓扑排序函数
toposort(algraph&
g,int n)
各函数间关系如下
:
.
.
creatgraph
mai
toposort
3
．详细设计
实现概
要设计中定义的所有数据类型，
对每个操作只需要写出伪码算法；
对主程序和其
他模块也都需要写出伪码算法
(
伪码算法达到的详细程度建议为：按照伪码算法可以在计算
机键盘直接输入高级
程序设计语言程序
)
；画出函数和过程的调用关系图。
1
）
typedef struct arcnode
{
int adjvex;
//int info;
struct arcnode *nextarc;
}arcnode;
2
）
typedef struct vnode
{
int data;
int id;
struct arcnode *firstarc;
}vnode,adjlist[MAX_VERTEX_NUM
3
）
typedef struct
{
adjlist vertices;
int vexnum,arcnum;
//int kind;
}algraph;
4
）图的基本操作
.
.
为了方便用邻接表来存储有向图。
algraph creatgraph(algraph& g)
{
int i,j,k;
arcnode *p;
algraph ag;
printf(
< br>printf(
请输入顶点数
:n
scanf(
printf(<
/p>
请输入边数
:n
scanf(
printf(
printf(
请输入顶点：
for(i=1;i<=;++i)
{
scanf(
es[i].firstarc=NULL;
}
printf(
请输入确定
弧的两个顶点
的下标
:
n
for(k=1;k<=;++k)
{
scanf(
p=(arcnode*)malloc(sizeof(arcnode));
p->adjvex=j;
p->nextarc=es[i].firstarc;
es[i].firstarc=p;
}
return ag;
}
5)
拓扑排序的基本操作
int toposort(algraph& g,int n)
{
int i,j,k,m=0;
int top=0;
arcnode *p;
//p=(arcnode*)malloc(sizeof(arcnode));
for(i=1;i<=n;i++)
if(es[i].id==0)
{
es[i].id=top;
top=i;
}
while(top!=0)
{
j=top;
top=es[top].id;
.
-
-
-
-
-
-
-
-
-
上一篇：苦累面前莫低头(部队苦累关教育)
下一篇：在领导面前的自我介绍范文