图的遍历课程设计.docx
- 文档编号:10462602
- 上传时间:2023-05-25
- 格式:DOCX
- 页数:44
- 大小:245.43KB
图的遍历课程设计.docx
《图的遍历课程设计.docx》由会员分享,可在线阅读,更多相关《图的遍历课程设计.docx(44页珍藏版)》请在冰点文库上搜索。
图的遍历课程设计
学号:
图的遍历
课程设计
题目
图的遍历
教学院
计算机
专业
班级
姓名
指导教师
2011
年
12
月
31
日
课程设计任务书
2010~2011学年第1学期
学生姓名:
专业班级:
指导教师:
工作部门:
一、课程设计题目
图的遍历
二、课程设计内容(含技术指标)
1.显示图的邻接矩阵,图的邻接表,深度优先遍历,广度优先遍历,最小生成树PRIM算法,最小生成树KRUSCAL算法,图的连通分量。
2.当用户选择的功能错误时,系统会输出相应的提示。
3.通过图操作的实现,把一些实际生活中的具体的事物抽象出来
三、进度安排
1.初步完成总体设计,搭好框架;
2.完成最低要求:
两种必须都要实现,写出画图的思路;
3.进一步要求:
画出图的结构,有兴趣的同学可以进一步改进图的效果。
四、基本要求
1.界面友好,函数功能要划分好
2.程序要加必要的注释
3.要提供程序测试方案
目录
一概述.............................................1
1.问题描述………………………………………………………………………………………..1
2.系统分析………………………………………………………………………………………..1
3.课程设计(论文)进程安排…………………………………………………………………..1
二.总体设计方案......................................2
1.整体设计思路...............................................................................................................................2
2.算法的整体思路……………………………………………………………………………….3
3.工作内容……………………………………………………………………………………….3
三详细设计………………………………………………………4
1.详细设计思路及算法…………………………………………………………………………..4
2.程序流程图……………………………………………………………………………………11
四程序的调试与运行结果说明………………………………12
1.运行结果………………………………………………………………………………………12
五.课程设计总结………………………………………………15
参考文献…………………………………………………………16
附录A原程序清单………………………………………………16
数据结构课程设计成绩评定表…………………………………30
一概述
1.问题描述
1)函数功能要划分好
2)总体设计应画流程图
3)程序要加必要的注释
4)要提供程序测试方案
2.系统分析
1)掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力
2)初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能
3)提高综合运用所学的理论知识和方法独立分析和解决问题的能力
4)训练用系统的观点和软件开发一般规范进行软件开发,培养软件工作者所应具备的科学的工作方法和作风
3.课程设计(论文)进程安排
序号
设计(论文)各阶段内容
地点
起止日期
1
设计动员,布置任务
K4-208
2011年12月20日
2
查阅资料,分析、讨论与设计
K4-208
12月21日~12月22日
3
编写程序,进行调试
K4-208
12月23日~12月27日
4
完成模块联调,进行测试
K4-208
12月29日~12月30日
5
成果验收,完成设计报告、答辩
K4-208
2010年12月31日
二.总体设计方案
1.整体设计思路
图的邻接矩阵:
对于一个具有n个顶点的图,可以使用n*n的矩阵(二维数组)来表示它们间的邻接关系。
图的邻接表:
邻接表由表头结点和表结点两部分组成,其中图中每个顶点均对应一个存储在数组中的表头结点。
如这个表头结点所对应的顶点存在相邻顶点,则把相邻顶点依次存放于表头结点所指向的单向链表中。
深度优先遍历的递归算法思想:
假定以图中某个顶点Vi为出发点,首先访问出发点,然后选择一个Vi的未访问过的邻接点Vj,以Vj为新的出发点继续进行深度优先搜索,直至图中所有顶点都被访问过。
1)访问结点V并标记结点V为已访问;
2)查找结点V的第一个邻接结点W;
3)若结点W的临界结点W存在,则继续执行,否则算法结束;
4)若结点W尚未被访问,则递归访问结点W;
5)查找结点V的W临界结点的下一个临界结点W,转到步骤(3)。
广度优先遍历算法:
从图的某一顶点Vi出发,访问此顶点后,依次访问Vi的各个未曾访问过的邻接点,然后分别从这些邻接点出发,直至图中所有已有已被访问的顶点的邻接点都被访问到。
1)访问初始结点V并标记结点V为已访问;
2)结点V入队列;
3)当队列非空时则继续执行,否则算法结束;
4)出队列取得队头结点U;
5)查找结点U的第一个邻接结点W;
6)若结点U的邻接结点W不存在,则转到步骤(3),否则循环执行下列步骤:
a)(6.1)若结点W尚未被访问,则访问结点W并标记结点W为已访问;
b)(6.2)结点W入队;
c)(6.3)查找结点U的W邻接结点的下一个邻接结点W,转到步骤(6)。
普利姆算法思想:
令集合U的初值为U={u0},集合T的初值为T={}。
从所有结点u属于U和结点v属于V\U的带权边中选出具有最小权值的边(u,v),将结点v加入集合U中,将边(u,v)加入集合T中。
如此不断反复,当U=V时,最小生成树便构造完毕。
克鲁斯卡尔算法思想:
设无向连通带权图G=(V,E),其中V为结点的集合,E为边的集合。
设带权图G的最小生成树T由结点集合和边的集合构成,其初值为T=(v,{}),即初始时最小生成树T只由带权图G中的结点集合组成,各结点之间没有一条边。
这样,最小生成树T中的各个结点各自构成一个连通分量。
然后,按照边的权值递增的顺序考察带权图G中边集合E的各条边,若被考察的边的两个结点属于T的两个不同的连通分量,则将此边加入懂啊最小生成树T中,同时,把两个连通分量连接为一个连通分量;若被考察的边的两个结点属于T的同一个连通分量,则将此边舍去。
如此下去,当T中的连通分量个数为1时,T中的该连通分量即为带权图G的一棵最小生成树。
连通分量:
非连通图的每一个连通部分。
2.算法的整体思路
本系统能分别用邻接矩阵存储结构和邻接表存储结构构造无向图,然后在此无向图中能实现深度优先遍历,广度优先遍历,最小生成树和连通分量的算法。
3.工作内容
1.显示图的邻接矩阵,图的邻接表,深度优先遍历,广度优先遍历,最小生成树PRIM算法,最小生成树KRUSCAL算法,图的连通分量。
2.当用户选择的功能错误时,系统会输出相应的提示。
3.通过图操作的实现,把一些实际生活中的具体的事物抽象出来。
三详细设计
1.详细设计思路及算法
图1-1无向图
1.程序中所用变量的定义:
#include
#include
usingnamespacestd;
#defineint_max10000
#defineinf9999
#definemax20
2.邻接矩阵的定义:
typedefstructArcCell
{
intadj;
char*info;
}ArcCell,AdjMatrix[20][20];
typedefstruct
{
charvexs[20];
AdjMatrixarcs;
intvexnum,arcnum;
}MGraph_L;
A050600000
B5000654000
C6000520045
D06552050300
E0400500700
F0003070080
G004500800
图1-2邻接矩阵
3.邻接表:
A
0
B
1
C
2
D
3
E
4
F
5
G
6
2
1
/\
0
3
4
/\
6
/\
4
5
/\
6
/\
0
2
1
4
2
3
1
3
3
5
/\
5
/\
表1-1邻接表
4.深度优先遍历:
voidadjprint(algraphgra)
5.广度优先遍历:
voidbfstra(algraphgra)
6.最小生成树PRIM算法:
7.最小生成树KRUSCAL算法:
2.程序流程图
四程序的调试与运行结果说明
1.运行结果
图2-1输入顶点数
图2-2输入权值
无向图创建成功
图2-3菜单
图2-4邻接矩阵
图2-5邻接表
图2-6深广度优先遍历
图2-7最小生成树
图2-8连通分量
五.课程设计总结
课程设计是把我们所学的理论知识进行系统的总结并应用于实践的良好机会,有利于加强我们用知识理论来分析实际问题的能力,进而加强了我们对知识认识的实践度,巩固了我们的理论知识,深化了对知识的认识,并为走向社会打下一个良好的基础。
对于我们学生来讲,此次课程设计是为了让我们训练自己的实际设计能力,通过设计实践,去真正获得此项目管理和团队协作等方面的基本训练和工作经验。
通过课程设计的一系列训练,我们能提高如何综合运用所学知识解决实际问题的能力,以及获得此项目管理和团队协作等等众多方面的具体经验,增强对相关课程具体内容的理解和掌握能力,培养对整体课程知识综合运用和融会贯通能力。
通过这近一个星期的数据结构课程设计实践,我学到了很多东西。
本次课程设计对我来说正是一个提高自己能力的机会,我好好的抓住机会,努力做好每一步,完善每一步。
自己的C语言知识和数据结构知识得到了巩固,编程能力也有了一定的提高。
同时也学会了解决问题的方法。
此次课程设计也让我认识到必须培养严谨的态度。
自己在编程时经常因为一些类似于“少了分号”的小错误而导致错误,不够认真细致,这给自己带来了许多麻烦。
编程是一件十分严谨的事情,容不得马虎。
所以在今后自己一定要培养严谨的态度。
我想这不仅是对于程序设计,做任何事都应如此。
在实践过程中,我和组员分工合作,勇于提出问题,解决难题,在实践中,我遇到了许多困难,但都一一克服了。
最终我圆满的完成此次课程设计,学到了很多东西。
同时,程序还存在着一些缺陷,就是不能输出原图,存在一些局限性,不过我会继续努力思考,完善程序,做到最好。
此次试验,老师对我的指导是至关重要的,在此我非常感谢老师,从她那我学到了很多有关c语言的知识,为以后的学习打下了一定的基础。
总的来说,本次课程设计,不仅我的知识面有所提高,另外我的综合素质也有所提高,,比如说:
团队精神、提问能力、思考能力等等。
这次课程设计为我以后更好的学习和使用c语言打下了基础。
参考文献
[1]数据结构—使用C语言(第3版)朱战立编,西安交通大学出版社。
[2]VisualC++程序设计──基础与实例分析.北京:
清华大学出版社,2004
附录A原程序清单
#include
#include
usingnamespacestd;
#defineint_max10000
#defineinf9999
#definemax20
//…………………………………………邻接矩阵定义……………………
typedefstructArcCell
{
intadj;
char*info;
}ArcCell,AdjMatrix[20][20];
typedefstruct
{
charvexs[20];
AdjMatrixarcs;
intvexnum,arcnum;
}MGraph_L;
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
intlocalvex(MGraph_LG,charv)//返回V的位置
{
inti=0;
while(G.vexs[i]!
=v)
{
++i;
}
returni;
}
intcreatMGraph_L(MGraph_L&G)//创建图用邻接矩阵表示
{
charv1,v2;
inti,j,w;
cout<<"…………创建无向图…………"< (46)不包括“()”"< cin>>G.vexnum>>G.arcnum; for(i=0;i! =G.vexnum;++i) { cout<<"输入顶点"< cin>>G.vexs[i]; } for(i=0;i! =G.vexnum;++i) for(j=0;j! =G.vexnum;++j) { G.arcs[i][j].adj=int_max; G.arcs[i][j].info=NULL; } for(intk=0;k! =G.arcnum;++k) { cout<<"输入一条边依附的顶点和权: (ab3)不包括()"< cin>>v1>>v2>>w;//输入一条边依附的两点及权值 i=localvex(G,v1);//确定顶点V1和V2在图中的位置 j=localvex(G,v2); G.arcs[i][j].adj=w; G.arcs[j][i].adj=w; } cout<<"图G邻接矩阵创建成功! "< returnG.vexnum; } voidljjzprint(MGraph_LG) { inti,j; for(i=0;i! =G.vexnum;++i) { for(j=0;j! =G.vexnum;++j) cout< cout< } } intvisited[max];//访问标记 intwe; typedefstructarcnode//弧结点 { intadjvex;//该弧指向的顶点的位置 structarcnode*nextarc;//弧尾相同的下一条弧 char*info;//该弧信息 }arcnode; typedefstructvnode//邻接链表顶点头接点 { chardata;//结点信息 arcnode*firstarc;//指向第一条依附该结点的弧的指针 }vnode,adjlist; typedefstruct//图的定义 { adjlistvertices[max]; intvexnum,arcnum; intkind; }algraph; //…………………………………………队列定义…………………… typedefstructqnode { intdata; structqnode*next; }qnode,*queueptr; typedefstruct { queueptrfront; queueptrrear; }linkqueue; //……………………………………………………………………… typedefstructacr { intpre;//弧的一结点 intbak;//弧另一结点 intweight;//弧的权 }edg; intcreatadj(algraph&gra,MGraph_LG)//用邻接表存储图 { inti=0,j=0; arcnode*arc,*tem,*p; for(i=0;i! =G.vexnum;++i) { gra.vertices[i].data=G.vexs[i]; gra.vertices[i].firstarc=NULL; } for(i=0;i! =G.vexnum;++i) { for(j=0;j! =G.vexnum;++j) { if(gra.vertices[i].firstarc==NULL) { if(G.arcs[i][j].adj! =int_max&&j! =G.vexnum) { arc=(arcnode*)malloc(sizeof(arcnode)); arc->adjvex=j; gra.vertices[i].firstarc=arc; arc->nextarc=NULL; p=arc; ++j; while(G.arcs[i][j].adj! =int_max&&j! =G.vexnum) { tem=(arcnode*)malloc(sizeof(arcnode)); tem->adjvex=j; gra.vertices[i].firstarc=tem; tem->nextarc=arc; arc=tem; ++j; } --j; } } else { if(G.arcs[i][j].adj! =int_max&&j! =G.vexnum) { arc=(arcnode*)malloc(sizeof(arcnode)); arc->adjvex=j; p->nextarc=arc; arc->nextarc=NULL; p=arc; } } } } gra.vexnum=G.vexnum; gra.arcnum=G.arcnum; /*for(i=0;i! =gra.vexnum;++i) { arcnode*p; cout< p=gra.vertices[i].firstarc; while(p! =NULL) { cout< p=p->nextarc; } cout< }*/ cout<<"图G邻接表创建成功! "< return1; } voidadjprint(algraphgra) { inti; for(i=0;i! =gra.vexnum;++i) { arcnode*p; cout< p=gra.vertices[i].firstarc; while(p! =NULL) { cout< p=p->nextarc; } cout< } } intfirstadjvex(algraphgra,vnodev)//返回依附顶点V的第一个点 //即以V为尾的第一个结点 { if(v.firstarc! =NULL) returnv.firstarc->adjvex; } intnextadjvex(algraphgra,vnodev,intw)//返回依附顶点V的相对于W的下一个顶点 { arcnode*p; p=v.firstarc; while(p! =NULL&&p->adjvex! =w) { p=p->nextarc; } if(p->adjvex==w&&p->nextarc! =NULL) { p=p->nextarc; returnp->adjvex; } if(p->adjvex==w&&p->nextarc==NULL) return-10; } intinitqueue(linkqueue&q)//初始化队列 { q.rear=(queueptr)malloc(sizeof(qnode)); q.front=q.rear; if(! q.front) return0; q.front->next=NULL; return1; } intenqueue(linkqueue&q,inte)//入队 { queueptrp; p=(queueptr)malloc(sizeof(qnode)); if(! p) return0; p->data=e; p->next=NULL; q.rear->next=p; q.rear=p; return1; } intdequeue(linkqueue&q,int&e)//出队 { queueptrp; if(q.front==q.rear) return0; p=q.front->next; e=p->data; q.front->next=p->next; if(q.rear==p) q.rear=q.front; free(p); return1; } intqueueempty(linkqueueq)//判断队为空 { if(q.front==q.rear) return1; return0; } voidbfstra(algraphgra)//广度优先遍历 { inti,e; linkqueueq; for(i=0;i! =gra.vexnum;++i) visited[i]=0; initqueue(q); for(i=0;i! =gra.vexnum;++i) if(! visited[i]) {visited[i]=1; cout< enqueue(q,i); while(! queueempty(q)) { dequeue(q,e); //cout<<""< for(we=firstadjvex(gra,gra.vertices[e]);we>=0;we=nextadjvex(gra,gra.vertices[e],we)) { if(! visited[we]) { visited[we]=1; cout<
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 遍历 课程设计