下载
加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 图的基本操作及应用数据结构课程设计报告

图的基本操作及应用数据结构课程设计报告.doc

图的基本操作及应用数据结构课程设计报告

陌上丹青ll
2017-12-21 0人阅读 举报 0 0 暂无简介

简介:本文档为《图的基本操作及应用数据结构课程设计报告doc》,可适用于综合领域

图的基本操作及应用数据结构课程设计报告系(院):计算机科学学院专业班级:教育技术学班姓名:宋佳学号:指导教师:詹泽梅设计时间:设计地点:号楼号机房《算法与数据结构》课程设计任务书班级:教育技术课程设计题目:图的基本操作及应用数据结构课程设计是在学完数据结构课程之后的实践教学环节。本实践教学是培养学生数据抽象能力进行复杂程序设计的训练过程。要求学生能对所涉及问题选择合适的数据结构、存储结构及算法并编写出结构清楚且正确易读的程序提高程序设计基本技能和技巧。一(设计目的(提高数据抽象能力。根据实际问题能利用数据结构理论课中所学到的知识选择合适的逻辑结构以及存储结构并设计出有效解决问题的算法。(提高程序设计和调试能力。学生通过上机实习验证自己设计的算法的正确性。学会有效利用基本调试方法迅速找出程序代码中的错误并且修改。(初步了解开发过程中问题分析、整体设计、程序编码、测试等基本方法和技能。二(设计任务设计一个基于DOS菜单的应用程序。要利用多级菜单实现各种功能。内容如下:(无向图的基本操作及应用创建无向图的邻接矩阵创建无向图的邻接表无向图的深度优先遍历无向图的广度优先遍历(有向图的基本操作及应用创建有向图的邻接矩阵创建有向图的邻接表拓扑排序(无向网的基本操作及应用创建无向网的邻接矩阵创建无向网的邻接表求最小生成树(有向网的基本操作及应用创建有向网的邻接矩阵创建有向网的邻接表关键路径单源最短路径三(设计指导第一步:根据设计任务设计DOS菜单。第二步:设计菜单(c语言)#include<stdioh>voidShowMainMenu(){printf("n")printf("**************图的基本操作及应用***************n")*n")printf("*无向图的基本操作及应用n")printf("*有向图的基本操作及应用*printf("*无向网的基本操作及应用*n")printf("*有向网的基本操作及应用*n")n")printf("*退出printf("***********************************************n")}voidUDG(){intndo{printf("n")printf("**************无向图的基本操作及应用***************n")printf("*创建无向图的邻接矩阵*n")printf("*创建无向图的邻接表*n")printf("*无向图的深度优先遍历*n")printf("*无向图的广度优先遍历*n")printf("*退出n")printf("***********************************n")printf("请选择:")scanf("d",n)switch(n){case:printf("wait")breakcase:printf("wait")breakcase:printf("wait")breakcase:printf("wait")breakcase:breakdefault:printf("ERROR!")}}while(n!=)}voidDG(){intndo{printf("n")printf("**************有向图的基本操作及应用***************n")printf("*创建有向图的邻接矩阵*n")printf("*创建有向图的邻接表*n")printf("*拓扑排序*n")*n")printf("*退出printf("*******************************n")printf("请选择:")scanf("d",n)switch(n){case:printf("wait")breakcase:printf("wait")breakcase:printf("wait")breakcase:breakdefault:printf("ERROR!")}}while(n!=)}voidUDN(){intndo{printf("n")printf("**************无向网的基本操作及***n")printf("*创建无向网的邻接矩阵*n")printf("*创建无向网的邻接表*n")printf("*Prim算法求最小生成树*n")printf("*kraskal算法求最小生成树*n")printf("*退出n")printf("*************************************n")printf("请选择:")scanf("d",n)switch(n){case:printf("wait")breakcase:wait")breakprintf("case:printf("wait")breakcase:printf("wait")breakcase:breakdefault:printf("ERROR!")}}while(n!=)}voidDN(){intndo{printf("n")printf("**************有向网的基本操作****n")printf("*创建有向网的邻接矩阵*n")printf("*创建有向网的邻接表*n")printf("*关键路径*n")printf("*单源顶点最短路径问题*n")printf("*退出n")printf("***********************************n")printf("请选择:")scanf("d",n)switch(n){case:printf("wait")breakcase:printf("wait")breakcase:printf("wait")breakcase:printf("wait")breakcase:breakdefault:printf("ERROR!")}}while(n!=)}voidmain(){intndo{ShowMainMenu()printf("请选择:")scanf("d",n)switch(n){case:UDG()breakcase:DG()breakcase:UDN()breakcase:DN()breakcase:breakdefault:printf("ERROR!")break}}while(n!=)}第三步:添加功能函数。在主程序的合适位置添加相应的函数实现各功能(提示:语句printf(“wait”)所在位置)。四(成绩评定,实习报告(文字不得少于字)一、设计方案二、实现过程三、实现代码四、测试五、结论六、难点与收获。,程序实现程序运行正确无编译错误无逻辑错误在第一条的基础上任务完成的越多成绩等级越高。,成绩由三部分组成:平时考核()、程序实现()、实习报告()一、设计方案由课程设计任务书按照要求需要设计有向图、有向网、无向图、无向网四种图邻接矩阵、邻接表两种数据存储结构共十六种基本操作及应用三层以上的显示菜单。图的操作中又包含有有关线性表、栈和队列的基本操作。由于显示菜单已给出剩下的只是把函数写入其中而线性表、栈和队列的基本操作并不复杂很容易实现我们只有完成图的相关操作即可。图的操作都是以两种存储结构为基础的邻接矩阵存储结构和邻接表存储结构如四种图(有向图有向网无向图无向网)的创建其他的操作都是在四种图创建后才开始进行的。所以首先必须理解两种存储结构的定义。图的邻接矩阵存储结构即图的数组表示法。用两个数组分别存储数据元素(顶点)的信息和数据元素之间的关系(边或弧)的信息。用邻接矩阵存储结构的图具有以下几点特征:(一):顶点数:vexnum边(弧)数:arcnum图的种类:kind(二):邻接矩阵:arcs(顶点关系类型:adj相关信息:*info)(三):顶点向量(顶点名):vexs其优点是以二维数组表示有n个顶点的图时需存放n顶点的信息和n*n个弧的信息存储量。借助于邻接矩阵容易判定任意两个顶点之间是否有边或弧相连并容易求各个顶点的度。缺点其时间复杂度是O(n*n),例如构造一个具有n个顶点和e条边的无向网的时间复杂度为O(n*ne*n)。图的邻接表存储结构是图的一种链式存储结构。对图中的每个顶点建立一个单链表每个结点有三个域组成邻接点域adjvex(弧尾在邻接表链表中的位序)链域nextarc(下一条弧)数据域info(权值)。还要建立一个邻接表链表用以存放顶点名data和后继指针firstarc,表头结点以顺序结构的形式存储便于随机访问任一顶点的单链表。邻接表存储结构的优点在于其时间复杂度小。除此之外还有十字链表存储结构和多重链表存储结构。由于没有用到他们故不再详细描述。树的深度优先搜索遍历类似于树的先根遍历是树的先根遍历的推广。从图中的某个顶点出发访问此顶点然后依次从该顶点出发深度优先搜索遍历图直至图中所有与该顶点有关的路径都被访问到此时图中若还有顶点未被访问到则另选图中的一个未被访问的顶点作为起始点重述上述过程直至所有顶点都被访问到。广度优先搜索遍历类似于树的按层次遍历的过程。以某个顶点为起始顶点由近至远依次访问和该顶点有路径相通的且路径长度为的顶点。当图中所有顶点都被访问到后就完成了图的广度优先搜索遍历。求无向网的最小生成树问题有两种算法:Prima算法和Kruskal算法。Prima算法是从网中的某个顶点出发选择与该顶点有路径的所有顶点中路径最小的一条路径从该最小路径的另一顶点出发重复上述过程直至图中所有顶点都被访问完成。Kruskal算法是从网中找出所有路径最小的一条路径记下已访问该路径的两个顶点再次从图中找出剩下路径中的最小路径重复上述过程直至所有顶点都被访问完成按访问的顺序依次输出各顶点即构造了一棵最小生成树。由某个集合上的一个偏序得到该集合的一个全序的操作就叫做拓扑排序。拓扑排序主要有两个方面的操作:()在有向图中选择一个没有前驱的顶点并输出()在图中删除该顶点和所有以它为尾的弧。重复上述两步直至全部顶点均已输出就得到了一个拓扑有序序列。求关键路径的算法如下:输入e条弧建立AOE网的存储结构从源点v出发,令ve=按拓扑有序求其余各顶点的最早发生时间。如果得到的拓扑有序序列中的顶点个数小于网中的顶点数则说明网中存在环不能求关键路径算法终止否则执行第三步。从汇点vn出发令vln=ven按逆拓扑有序求其余各顶点的最迟发生时间vli根据各顶点的和值求每条弧的最早开始时间e(s)和最迟开始时间e(s)若某条弧满足条件e(s)=l(s)则为关键活动。从某个源点到其余各顶点的最短路径问题:若从v到vi有弧则Di为弧上的权值否则Di为无穷大。显然长度为Dj=Min{Di|vi属于V}的路径就是从v出发的长度最短的一条路径。二、实现及测试过程按照设计任务的要求我先完成了存储结点、边、邻接矩阵、邻接表、队列、栈等储存结构体的设计。其次是栈和队列的基本操作和实现四种图的创建和显示然后是基于两种存储结构的各种算法的现最后是三层显示输出菜单。测试样图:三、实现代码#include<stdioh>#include<stdlibh>#include<limitsh>#defineERROR#defineOK#defineINFINITYINTMAX#defineMAXVERTEXNUM#defineSTACKINITSIZE#defineSTACKINCREAMENTtypedefenum{DG,DN,UDG,UDN}GraphKindtypedefstructArcCell{intadjinfotype*info}ArcCell,AdjMatrixMAXVERTEXNUMMAXVERTEXNUMtypedefstruct{charvexsMAXVERTEXNUMAdjMatrixarcsintvexnum,arcnumGraphKindkind}MGraph邻接矩阵typedefstructArcNode{intadjvexintquanstructArcNode*nextarc}ArcNode,*AListtypedefstructVNode{chardataAListfirstarc}VNode,AdjListMAXVERTEXNUMtypedefstruct{AdjListverticesintvexnum,arcnumGraphKindkind}ALGraph邻接表typedefstructQNode{chardatastructQNode*next}QNode,*QueuePretypedefstruct{QueuePrefrontQueuePrerear}LinkQueue队列typedefstruct{int*baseint*topintstacksize}SqStack栈typedefstruct{charadjvexintlowcost}closedgesMAXVERTEXNUM求最小生成树中的辅助数组intoptionintvisitedMAXVERTEXNUM顶点访问标记数组intindegreeMAXVERTEXNUM顶点入度记录数组intveMAXVERTEXNUM顶点权值记录数组intSetGraphKind(MGraphG,intoption){switch(option){case:Gkind=DGbreakcase:Gkind=DNbreakcase:Gkind=UDGbreakcase:Gkind=UDNbreakdefault:returnERROR}returnOK}邻接矩阵类型设置intSetGraphKind(ALGraphG,intoption){switch(option){case:Gkind=DGbreakcase:Gkind=DNbreakcase:Gkind=UDGbreakcase:Gkind=UDNbreakdefault:returnERROR}returnOK}邻接表类型设置intLocateVex(MGraphG,charv){intmfor(m=m<=Gvexnumm){if(Gvexsm==v)returnm}returnERROR}邻接矩阵顶点定位intLocateVex(ALGraphG,charv){intmfor(m=m<=Gvexnumm){if(Gverticesmdata==v)returnm}printf("您输入的顶点不存在")returnERROR}邻接表顶点定位intInitQueue(LinkQueueQ){Qfront=Qrear=(QueuePre)malloc(sizeof(QNode))if(!Qfront)returnERRORQfront>next=returnOK}队列创建intEnQueue(LinkQueueQ,inte){QueuePrepp=(QueuePre)malloc(sizeof(QNode))if(!p)returnOKp>data=ep>next=Qrear>next=pQrear=preturnOK}元素入队列intDeQueue(LinkQueueQ,inte){QueuePrepif(Qfront==Qrear)returnERRORp=Qfront>nexte=p>dataQfront>next=p>nextif(Qrear==p)Qrear=Qfrontfree(p)returnOK}元素出队列intQueueEmpty(LinkQueueQ){if(Qfront==Qrear)returnOKreturnERROR}判断队列是否为空intInitStack(SqStackS){Sbase=(int*)malloc(STACKINITSIZE*sizeof(int))if(!Sbase)returnERRORStop=SbaseSstacksize=STACKINITSIZEreturnOK}栈创建intPush(SqStackS,inte){if(StopSbase>=Sstacksize){Sbase=(int*)realloc(Sbase,(SstacksizeSTACKINCREAMENT)*sizeof(int))if(!Sbase)returnERRORStop=SbaseSstacksizeSstacksize=STACKINCREAMENT}*Stop=ereturnOK}元素入栈intPop(SqStackS,inte){if(Stop==Sbase)returnERRORe=*StopreturnOK}元素出栈intStackEmpty(SqStackS){if(Stop==Sbase)returnOKreturnERROR}判断栈是否为空intCreatGraph(MGraphG){inti,j,k,wcharx,yif(!SetGraphKind(G,option)){printf("对图类型的设置失败")returnERROR}printf("邻接矩阵:请输入定点的个数、弧的个数:")scanf("dd",Gvexnum,Garcnum)if(Gvexnum>){printf("您输入的顶点个数超过最大值")returnERROR}printf("请输入d个顶点n",Gvexnum)for(i=i<=Gvexnumi){fflush(stdin)scanf("c",Gvexsi)}if(Gkind==DG||Gkind==UDG){for(i=i<=Gvexnumi)for(j=j<=Gvexnumj)Garcsijadj=if(Gkind==DG){printf("请输入有向图的两个相邻的顶点<x,y>(如果互相邻接则<x,y>也要输入):n")for(k=k<=Garcnumk){fflush(stdin)scanf("cc",x,y)i=LocateVex(G,x)j=LocateVex(G,y)Garcsijadj=}}else{printf("请输入无向图的两个相邻的顶点(x,y):n")for(k=k<=Garcnumk){fflush(stdin)scanf("cc",x,y)i=LocateVex(G,x)j=LocateVex(G,y)Garcsijadj=Garcsjiadj=Garcsijadj}}}else{for(i=i<=Gvexnumi)for(j=j<=Gvexnumj)Garcsijadj=INTMAXif(Gkind==DN){printf("请输入有向网的两个相邻的顶点<x,y>以及相应的权值w(如果互相邻接则<y,x>也要输入):n")for(k=k<=Garcnumk){fflush(stdin)scanf("ccd",x,y,w)i=LocateVex(G,x)j=LocateVex(G,y)Garcsijadj=w}}else{printf("请输入无向网的两个相邻的顶点(x,y)以及相应的权值w:n")for(k=k<=Garcnumk){fflush(stdin)scanf("ccd",x,y,w)i=LocateVex(G,x)j=LocateVex(G,y)Garcsijadj=wGarcsjiadj=Garcsijadj}}}returnOK}创建邻接矩阵intCreatAList(ALGraphG){inti,j,m,n,keyMAXVERTEXNUMcharx,y,wAListp,qSetGraphKind(G,option)printf("邻接表:请输入顶点的个数和弧的个数:")scanf("dd",Gvexnum,Garcnum)if(Gvexnum>){printf("您输入的顶点个数超过最大值")returnERROR}printf("请输入个顶点:n")for(i=i<=Gvexnumi){fflush(stdin)scanf("c",Gverticesidata)Gverticesifirstarc=keyi=}if(Gkind==DG){printf("请输入弧(如AB,其中AB与BA是不同的弧):n")for(j=j<=Garcnumj){fflush(stdin)scanf("cc",x,y)m=LocateVex(G,x)n=LocateVex(G,y)p=Gverticesmfirstarcq=(AList)malloc(sizeof(ArcNode))if(!q)returnERRORq>nextarc=q>adjvex=nwhile(keymp>nextarc){p=p>nextarckeym}if(!keym){Gverticesmfirstarc=qkeym}elsep>nextarc=q}}if(Gkind==UDG){printf("请输入弧(如AB,其中AB与BA是不同的弧):n")for(j=j<=*Garcnumj){fflush(stdin)scanf("cc",x,y)m=LocateVex(G,x)n=LocateVex(G,y)p=Gverticesmfirstarcq=(AList)malloc(sizeof(ArcNode))if(!q)returnERRORq>nextarc=q>adjvex=nwhile(keymp>nextarc){p=p>nextarckeym}if(!keym){Gverticesmfirstarc=qkeym}elsep>nextarc=q}}if(Gkind==DN){printf("请输入依次输入弧以及这条弧的权值(如AB,其中AB与BA是不同的弧):n")for(j=j<=Garcnumj){fflush(stdin)scanf("ccd",x,y,w)m=LocateVex(G,x)n=LocateVex(G,y)p=Gverticesmfirstarcq=(AList)malloc(sizeof(ArcNode))if(!q)returnERRORq>nextarc=q>quan=wq>adjvex=nwhile(keymp>nextarc){p=p>nextarckeym}if(!keym){Gverticesmfirstarc=qkeym}elsep>nextarc=q}}if(Gkind==UDN){printf("请输入依次输入弧以及这条弧的权值(如AB,其中AB与BA是不同的弧):n")for(j=j<=*Garcnumj){fflush(stdin)scanf("ccd",x,y,w)m=LocateVex(G,x)n=LocateVex(G,y)p=Gverticesmfirstarcq=(AList)malloc(sizeof(ArcNode))if(!q)returnERRORq>nextarc=q>quan=wq>adjvex=nwhile(keymp>nextarc){p=p>nextarckeym}if(!keym){Gverticesmfirstarc=qkeym}elsep>nextarc=q}}returnOK}创建邻接表intFirstAdjVex(ALGraphG,intv){if(Gverticesvfirstarc)returnGverticesvfirstarc>adjvexreturn}intNextAdjVex(ALGraphG,intv,intw){AListss=Gverticesvfirstarcwhile(s>adjvex!=w)s=s>nextarcif(s>nextarc)returns>nextarc>adjvexreturn}voidDFS(ALGraphG,intv){intwvisitedv=printf("c",Gverticesv)for(w=FirstAdjVex(G,v)w>=w=NextAdjVex(G,v,w)){if(!visitedw)DFS(G,w)}}voidDFSTraverse(ALGraphG){intvvisited=for(v=v<=Gvexnumv)visitedv=for(v=v<=Gvexnumv)if(!visitedv)DFS(G,v)}图的深度遍历voidBFSTraverse(ALGraphG){intv,w,uLinkQueueQfor(v=v<=Gvexnumv)visitedv=visited=InitQueue(Q)for(v=v<=Gvexnumv)if(!visitedv){visitedv=printf("c",Gverticesv)EnQueue(Q,v)while(!QueueEmpty(Q)){DeQueue(Q,u)for(w=FirstAdjVex(G,u)w>=w=NextAdjVex(G,u,w)){if(!visitedw){visitedw=printf("c",Gverticesw)EnQueue(Q,w)}elsebreak}}}}图的广度遍历voidFindInDegree(ALGraphG,intin){inti,j,kAListpfor(k=k<=Gvexnumk)ink=for(i=i<=Gvexnumi){p=Gverticesifirstarcwhile(p){j=p>adjvexinjp=p>nextarc}}}计算各顶点入度intTopologicalSort(ALGraphG){inti,k,countAListpSqStackSFindInDegree(G,indegree)InitStack(S)for(i=i<=Gvexnumi)if(!indegreei)Push(S,i)count=if(StackEmpty(S))printf("此有向图不符合条件~")while(!StackEmpty(S)){Pop(S,i)printf("d",i)countfor(p=Gverticesifirstarcpp=p>nextarc){k=p>adjvexif(!(indegreek))Push(S,k)}}if(count<=Gvexnum)returnERRORelsereturnOK}拓扑排序intMinimum(MGraphG,closedgesm){inti,j,min=INFINITYfor(i=i<=Gvexnumi){if(milowcost){if(milowcost<min){min=milowcostj=i}}}returnj}voidMinSpanTreePRIM(MGraphG,charu){inti,j,kclosedgesclosedgek=LocateVex(G,u)for(j=j<=Gvexnumj)if(j!=k){closedgejadjvex=uclosedgejlowcost=Garcskjadj}closedgeklowcost=for(i=i<=Gvexnumi){k=Minimum(G,closedge)printf("cc",closedgekadjvex,Gvexsk)closedgeklowcost=for(j=j<=Gvexnumj)if(Garcskjadj<closedgejlowcost){closedgejadjvex=Gvexskclosedgejlowcost=Garcskjadj}}}求最小生成树intTopologicalOrder(ALGraphG,SqStackT){inti,j,k,countSqStackSAListpFindInDegree(G,indegree)InitStack(S)for(i=i<=Gvexnumi)if(!indegreei)Push(S,i)InitStack(T)count=for(i=i<=Gvexnumi)vei=while(!StackEmpty(S)){Pop(S,j)Push(T,j)countfor(p=Gverticesjfirstarcpp=p>nextarc){k=p>adjvexif(indegreek==)Push(S,k)if(vejp>quan>vek)vek=vejp>quan}}if(count<=Gvexnum)returnERRORelsereturnOK}intCriticalPath(ALGraphG){inti,j,k,ee,el,dut,vMAXVERTEXNUMSqStackTAListpchartagif(!TopologicalOrder(G,T))returnERRORfor(i=i<=Gvexnumi){vi=veGvexnum}while(!StackEmpty(T))for(Pop(T,j),p=Gverticesjfirstarcpp=p>nextarc){k=p>adjvexdut=p>quanif(vkdut<vj)vj=vkdut}for(j=j<=Gvexnumj)for(p=Gverticesjfirstarcpp=p>nextarc){k=p>adjvexdut=p>quanee=vejel=vkduttag=(ee==el)'*':''printf("dddddcn",j,k,dut,ee,el,tag)}returnOK}求关键路径voidDG(MGraphG,ALGraphG){inti,j,k,m,keyAListsfor(k=){key=printf("**************************n")printf("请选择对有向图进行的操作:n创建邻接矩阵n创建邻接表n拓扑结构n退出n")printf("**************************n")printf("请选择:")scanf("d",m)switch(m){case:CreatGraph(G)printf("有向图的邻接矩阵:n")for(i=i<=Gvexnumi){for(j=j<=Gvexnumj){printf("d",Garcsijadj)}printf("n")}breakcase:CreatAList(G)printf("有向图的邻接表:n")for(i=i<=Gvexnumi){printf("c:",Gverticesi)s=Gverticesifirstarcwhile(s){j=s>adjvexfflush(stdin)printf("<c",Gverticesi)printf("c>",Gverticesj)s=s>nextarc}printf("n")}breakcase:printf("有向图的拓扑排序:n")TopologicalSort(G)breakcase:key=break}printf("n")if(key)break}printf("nn")}DGvoidDN(MGraphG,ALGraphG){inti,j,k,m,keyAListsfor(k=){key=printf("**************************n")printf("请选择对有向网进行的操作:n创建邻接矩阵n创建邻接表n关键路径n退出n")printf("**************************n")printf("请选择:")scanf("d",m)switch(m){case:CreatGraph(G)printf("有向网的邻接矩阵:n")for(i=i<=Gvexnumi){for(j=j<=Gvexnumj){if(Garcsijadj==INTMAX)printf("#")elseprintf("d",Garcsijadj)}printf("n")}breakcase:CreatAList(G)printf("有向网的邻接表:n")for(i=i<=Gvexnumi){printf("c:",Gverticesi)s=Gverticesifirstarcwhile(s){j=s>adjvexfflush(stdin)printf("<c",Gverticesi)printf("c>",Gverticesj)printf("d",s>quan)s=s>nextarc}printf("n")}breakcase:printf("有向网关键路径:n")CriticalPath(G)breakcase:key=break}printf("n")if(key)break}printf("nn")}DNvoidUDG(MGraphG,ALGraphG){inti,j,k,m,keyAListsfor(k=){key=printf("**************************n")printf("请选择对无向图进行的操作:n创建邻接矩阵n创建邻接表n深度遍历n广度遍历n退出n")printf("**************************n")printf("请选择:")scanf("d",m)switch(m){case:CreatGraph(G)printf("无向图的邻接矩阵:n")for(i=i<=Gvexnumi){for(j=j<=Gvexnumj){printf("d",Garcsijadj)}printf("n")}breakcase:CreatAList(G)printf("无向图的邻接表:n")for(i=i<=Gvexnumi){printf("c:",Gverticesi)s=Gverticesifirstarcwhile(s){j=s>adjvexfflush(stdin)printf("(c",Gverticesi)printf("c)",Gverticesj)s=s>nextarc}printf("n")}breakcase:printf("无向图的深度优先遍历:n")DFSTraverse(G)printf("n")breakcase:printf("无向图的广度优先遍历:n")BFSTraverse(G)breakcase:key=break}printf("n")if(key)break}printf("nn")}UDGvoidUDN(MGraphG,ALGraphG){inti,j,m,k,keyAListscharufor(k=){key=printf("************************n")printf("请选择对无向图进行的操作:n创建邻接矩阵n创建邻接表n最小生成树n退出n")printf("*****************************n")printf("请选择:")scanf("d",m)switch(m){case:CreatGraph(G)printf("无向网的邻接矩阵:n")for(i=i<=Gvexnumi){for(j=j<=Gvexnumj){if(Garcsijadj==INTMAX)printf("#")elseprintf("d",Garcsijadj)}printf("n")}breakcase:CreatAList(G)printf("无向网的邻接表:n")for(i=i<=Gvexnumi){printf("c:",Gverticesi)s=Gverticesifirstarcwhile(s){j=s>adjvexfflush(stdin)printf("(c",Gverticesi)printf("c)",Gverticesj)printf("d",s>quan)s=s>nextarc}printf("n")}breakcase:printf("请输入第一个顶点:")fflush(stdin)scanf("c",u)printf("无向网的最小生成树:n")MinSpanTreePRIM(G,u)breakcase:key=break}printf("n")if(key)break}printf("nn")}UDNvoidmain(){MGraphGALGraphGinti,nfor(i=){n=printf("********************************n")printf("请输入你要进行操作的图类型的编码n:有向图n:有向网n:无向图n:无向网n:退出n")printf("********************************n")printf("请选择:")scanf("d",option)printf("nn")switch(option){case:DG(G,G)breakcase:DN(G,G)breakcase:UDG(G,G)breakcase:UDN(G,G)breakcase:n=breakdefault:printf("你输入的编码有误~")break}if(n)breakprintf("nn")}}四、课设小结:可改进的地方()错误处理机制不完善:程序执行时必须按照规定的方式输入一旦未按照规定方式输入程序就会运行出错且没有错误提示。可以在此程序的基础之上设计错误处理机制使程序的使用者更加便捷和可靠。()程序代码冗长:由于本使用的是结构体设计代码可重用率较低。如果使用面向对象的设计方法可用到继承的方法使程序更加简洁可读性也大大增强。()主程序界面不友好:主程序界面还是简单的dos界面看上去很不美观。可尝试设计更加美观友好的界面。收获和体会:一看到课设题目我就有一种书到用时方恨少的感觉平时在学习过程中仅仅只注重于方法上的掌握对于写程序却显得力不从心。说实话这次课设的代码大多是对着书本或是网上所查找的资料敲出来的如果让我在独立不借助参考资料的话我想我是完成不了这次任务的。当然在做课设的整个过程除了让我认识到编程能力不足的短处外还让我深刻体会到编写程序确实是一件枯燥、艰苦的工作但当你做出自己想要的东西时心情却又是无比的愉快。因此当你在编程时如果遇到无法解决的问题时很容易灰心丧气但此时切不可烦躁一定要静下心来认真分析出错的地方实在找不出来时可寻求同学或老师帮助不要轻言放弃当你做出成绩来时你会发现之前的努力是值得的。通过这次课设我有以下几点体会:()扎实掌握程序语言是编写程序的基础。我反思了这次课设为什么一些算法我可以轻松地讲出他的工作原理却写不出任何程序,我想这就是由于我对于编程语言的掌握还不够扎实我想以后要花更多的时间学习编程语言如C等程序设计语言这些才是最基础的必须牢固掌握这才有利于更好的学习更深层次的语言写出好程序。()要注重培养实践能力。仅仅熟悉书本上的知识是不够的软件工程是一门实践性极强的专业有扎实的程序编写能力和优秀的程序编写思想才是我们的最高目标才能真正将书本知识运用于实践。这恰恰也是我所缺乏的。()必须培养严谨的态度。自己在编程时经常因为一些小错误而导致程序出错不够认真细致这给自己带来许多麻烦也容易使自己失去信心。例如我在编写队列的操作时将指针的内存分配类型弄错了整整花了我两天的时间才找出错误。编程是一件十分严谨的事容不得马虎。所以今后自己一定要培养严谨的治学态度。我想这不仅是对于程序设计做任何事都应如此。()指导老师意见::教师签名:成绩年月日

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/44

图的基本操作及应用数据结构课程设计报告

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利