长春大学课程设计内页

《长春大学课程设计内页》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1.设计目的与任务22.算法设计2.1设计思想22.2设计表示43.用户手册44.测试数据及测试结果45.课程设计总结5程序清单51.设计目的与任务1.1设计目的设计出一个有关邻接表的算法，能快速的计算出有向图的入度。1.2设计任务采用邻接表方式存储冇向图，设计并实现算法：求解冇n个顶点的冇A图各顶点（用1〜n表示）的入度。2.算法设计2.1设计思想（1）数据结构设计在本次算法设计中，我主要运用了3个结构体类型，如下:typedefstructarcnode{intweizhi;/A该边所指的顶

2、点的位置structarcnode*next;}arcnode;typedefstructvnode{typedata;//顶点信息arcnode*firstarc;//指向第一条依附该顶点的边的指针}vnode，adjlist[maxsize];typedefstruct{intvexnum，arcnum;adjlista;}graph;还运用了几个指针类型，举例如下：voidcreate(graph&G)cout<<"请输入图的顶点个数:cin〉〉G.vexnum;cout«"请输入顶点的信

3、息(字符表示)：”《endl;for(inti=l;i<=G.vexnum;i++){cin»G.a[i].data;G.afi].firstarc=NULL;}for(i=1;i<=G.vexnum;i++){intk二0;intn;cout«"请输入与顶点H«G.afi].data«H相联通的顶点号(以大于顶点的数结束此次输入)：”;while(cin»n&&G.vexnum>=n>=l)//以小于人于顶点的数结束输入{k++;arcnode*p;if(k==l)//第一个边表节点{p=ne

4、warcnode;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«n请输入与顶点n«G.a

5、il.data«’’相联通的顶点号(以小于1的数或者大于顶点的数结束此次输入)(2)算法设计先是根据邻接表的顶点个数n，创建一个int型的数组a[nl(用来存储各顶点的入度)，把a

6、n

7、中的每一项置为0。然后再邻接表遍

8、历一下，先是顶点遍历，然后弧遍历。2.2设计表示(1).根椐题意，设图(graph)的结构为:那么由上图可得如下邻接表:►1—►Z.——►3Y.►—►14►―►1—►1►0^—«►2Aindexnext在建立打向图的邻接表的时候，操作如下：确定图的顶点个数和边的个数；b.输入顶点信息存储在顶点表屮，并初始化该顶点的边表；C.依次输入边的信息并将边所对应的邻接点信息存储在边表中;d.输入边所依附的两个顶点的序i和j;e.生成新的邻接点序号为j的边表结点s;d.将结点s插入到第i个边表的头部；(2)

9、函数接口说明：typedefstructarcnodetypedefstructvnodetypedefstructintvexnum，arcnum;voidcreate(graph&G)intgetchudu(graphQintn)//求有向图的第n个顶点入度voidgetrudu(graphG，intn)//打印有向图voidprint(graphG)voidmain()1.用户手册1.本程序的运行环境为Windows7/8/10操作系统，执行文件为VisualC++6.0.exeo2.进入

10、演示程序后，即显示文木方式的用户界面。3.在完成上面两步的输入后按enter键便能得到程序的运行结果，即给出题口所求的各顶点的入度。（例如：某题操作运行后结果如下：）MC:Users£r^DesktopDebug2Cpp1.exe"3232入入入入01233232tLhvlk.vlsVy度度度度k出出出出？uh、>J^"^Lh、>kh、>arnli.&1.Jiilnll0123scontinue中文＜简体〉-百度输入法半：4.测试数据及测试结果测试数据如下：79122325263543

11、52546779I26779程序运行结果如hS3"D:cDebugCpp1.exe"b孺灸溝檔房表示〉:『青输入与顶点?相联通的顶点号〈以大于顶点的数结束此次输入〉:25263543B227^输入与顶点9相联通的顶点号＜以大于顶点的数结朿此次输入〉，39f奮输入甚顶点1裡睹瑭迫逗卓号少、大于顶点的数结束此次输入〉：请输入与顶点2相联通的顶＜号＜以大于顶点函薮鍤棄此戎输X〉：1267^输入与顶点2相联通的顶点号＜以大于顶点的数结朿此次输入〉：79入输束结3@2数2的9点2顶1于2大2似1#<