搜索
长春大学课程设计纸共10页第1页┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊目录1.设计目的与任务.........................................22.算法设计2.1设计思想............................................22.2设计表示............................................43.用户手册...............................................44.测试数据及测试结果.....................................45.课程设计总结...........................................5程序清单.................................................5长春大学课程设计纸共10页第2页┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊1.设计目的与任务1.1设计目的设计出一个有关邻接表的算法，能快速的计算出有向图的入度。1.2设计任务采用邻接表方式存储有向图，设计并实现算法：求解有n个顶点的有向图各顶点（用1~n表示）的入度。2.算法设计2.1设计思想（1）数据结构设计在本次算法设计中，我主要运用了3个结构体类型，如下：typedefstructarcnode{intweizhi;//该边所指的顶点的位置structarcnode*next;}arcnode;typedefstructvnode{typedata;//顶点信息arcnode*firstarc;//指向第一条依附该顶点的边的指针}vnode,adjlist[maxsize];typedefstruct{intvexnum,arcnum;adjlista;}graph;还运用了几个指针类型，举例如下：voidcreate(graph&G){cout请输入图的顶点个数：;cinG.vexnum;长春大学课程设计纸共10页第3页┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊cout请输入顶点的信息(字符表示)：endl;for(inti=1;i=G.vexnum;i++){cinG.a[i].data;G.a[i].firstarc=NULL;}for(i=1;i=G.vexnum;i++){intk=0;intn;cout请输入与顶点G.a[i].data相联通的顶点号(以大于顶点的数结束此次输入)：;while(cinn&&G.vexnum=n=1)//以小于大于顶点的数结束输入{k++;arcnode*p;if(k==1)//第一个边表节点{p=newarcnode;p-next=NULL;p-weizhi=n;G.a[i].firstarc=p;}else{arcnode*s;s=newarcnode;s-weizhi=n;s-next=NULL;p-next=s;p=s;}//cout请输入与顶点G.a[i].data相联通的顶点号(以小于1的数或者大于顶点的数结束此次输入)：;}长春大学课程设计纸共10页第4页┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊}}（2）算法设计先是根据邻接表的顶点个数n,创建一个int型的数组a[n]（用来存储各顶点的入度）,把a[n]中的每一项置为0。然后再邻接表遍历一下，先是顶点遍历，然后弧遍历。2.2设计表示（1）.根据题意，设图(graph)的结构为：那么由上图可得如下邻接表：长春大学课程设计纸共10页第5页┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊在建立有向图的邻接表的时候,操作如下：a.确定图的顶点个数和边的个数；b.输入顶点信息存储在顶点表中，并初始化该顶点的边表；c.依次输入边的信息并将边所对应的邻接点信息存储在边表中；d.输入边所依附的两个顶点的序i和j；e.生成新的邻接点序号为j的边表结点s；f.将结点s插入到第i个边表的头部；（2）函数接口说明：typedefstructarcnodetypedefstructvnodetypedefstructintvexnum,arcnum;voidcreate(graph&G)intgetchudu(graphG,intn)//求有向图的第n个顶点入度voidgetrudu(graphG,intn)//打印有向图voidprint(graphG)长春大学课程设计纸共10页第6页┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊voidmain()3.用户手册1.本程序的运行环境为Windows7/8/10操作系统,执行文件为VisualC++6.0.exe。2.进入演示程序后,即显示文本方式的用户界面。3.在完成上面两步的输入后按enter键便能得到程序的运行结果，即给出题目所求的各顶点的入度。（例如：某题操作运行后结果如下：）4.测试数据及测试结果测试数据如下：7912232526354352546779126779程序运行结果如下：长春大学课程设计纸共10页第7页┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊5.课程设计总结在刚刚开始写程序时，根本无从下手，“Graph.h”都不会打开，更不会创建头文件直到把教材上有关有向图的邻接表相关知识看了几遍，基本上明白是怎么回事，才开始写代码。虽然书上和附赠的光盘上都有给出伪代码，但是有些定义的方法尚未给出，还需要自己编译。这5天的数据结构课程设计大家都是在摸石头过河和打破沙锅问到底的状态下完成的，我是在边看书边看PPT和网上百度求教完成的此次的任务书。这几天在机房里把数据结构编写出来，感觉自己在编程方面的水平有了较大幅度的提高，特别是原先对于邻接表方面的知识十分模糊，现在慢慢的有了感觉知道他在计算机里面的存储方式和应用的优缺点。图这一章的内容整体来说是整个数据结构里面的重点和难点，它的关系是多对多，对于计算机方面的应用是比线性表和树更为灵活的，所以掌握图的操作是十分必要的。如果时间再充沛些的话我想我可以把此次的课程设计完成的更好一些。长春大学课程设计纸共10页第8页┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊程序清单#includeiostreamusingnamespacestd;#includestdlib.h#includestdio.h#definetypechar#definemaxsize100typedefstructarcnode{intweizhi;//该边所指的顶点的位置structarcnode*next;}arcnode;typedefstructvnode{typedata;//顶点信息arcnode*firstarc;//指向第一条依附该顶点的边的指针}vnode,adjlist[maxsize];typedefstruct{intvexnum,arcnum;adjlista;}graph;voidcreate(graph&G){cout请输入图的顶点个数：;cinG.vexnum;cout请输入顶点的信息(字符表示)：endl;for(inti=1;i=G.vexnum;i++){cinG.a[i].data;G.a[i].firstarc=NULL;}for(i=1;i=G.vexnum;i++){intk=0;intn;cout请输入与顶点G.a[i].data相联通的顶点号(以大于顶点的数结束此次输入)：;while(cinn&&G.vexnum=n=1)//以小于大于顶点的数结束输入{k++;arcnode*p;if(k==1)//第一个边表节点{p=newarcnode;p-next=NULL;p-weizhi=n;G.a[i].firstarc=p;}else{长春大学课程设计纸共10页第9页┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊arcnode*s;s=newarcnode;s-weizhi=n;s-next=NULL;p-next=s;p=s;}//cout请输入与顶点G.a[i].data相联通的顶点号(以小于1的数或者大于顶点的数结束此次输入)：;}}}//求有向图的第n个顶点出度intgetchudu(graphG,intn){intcount=0;arcnode*p;p=G.a[n].firstarc;if(p==NULL)return0;while(p){count++;p=p-next;}returncount;}//求有向图的第n个顶点入度voidgetrudu(graphG,intn){intcount=0;for(inti=1;i=G.vexnum;i++){arcnode*p;p=G.a[i].firstarc;if(p==NULL)continue;//跳过以下操作while(p){if(p-weizhi==n){count++;p=p-next;}elsep=p-next;}}if(count!=0)cout顶点G.a[n].data的入度为:countendl;长春大学课程设计纸共10页第10页┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊elsecout顶点G.a[n].data没有入度endl;}//打印有向图voidprint(graphG){for(inti=1;i=G.vexnum;i++){cout顶点G.a[i].data指向的顶点有：;arcnode*p;p=G.a[i].firstarc;while(p){coutG.a[p-weizhi].data;p=p-next;}coutendl;}}voidmain(){intn;graphG;create(G);print(G);cout请输入要求出度和入度的顶点号(以大于顶点的数目结束输入)：;while(cinn&&G.vexnum=n=1){cout顶点G.a[n].data的出度为：;coutgetchudu(G,n)endl;getrudu(G,n);cout请输入要求出度和入度的顶点号(以大于顶点的数目结束输入)：;}}