长春大学课程设计内页.doc

长春大学课程设计内页.doc:.. 5程序清单 ,能快速的计算出有向图的入度。,设计并实现算法:求解冇n个顶点的冇A图各顶点(用1〜n表示)的入度。(1)数据结构设计在本次算法设计中,我主要运用了3个结构体类型,如下:ode{intweizhi;/ode*next;}ode;typedefstructvnode{typedata;//ode*firstarc;//指向第一条依附该顶点的边的指针}vnode,adjlist[maxsize];typedefstruct{intvexnum,um;adjlista;}graph;还运用了几个指针类型,举例如下:voidcreate(graph&G)cout<<"请输入图的顶点个数:cin〉〉;cout«"请输入顶点的信息(字符表示):”《endl;for(inti=l;i<=;i++){cin»[i].data;].firstarc=NULL;}for(i=1;i<=;i++){intk二0;intn;cout«"请输入与顶点H«].data«H相联通的顶点号(以大于顶点的数结束此次输入):”;while(cin»n&&>=n>=l)//以小于人于顶点的数结束输入{k++;ode*p;if(k==l)//第一个边表节点{p=ode;p->next=NULL;p->weizhi=n;[i].firstarc=p;}else{ode*s;s=ode;s-〉weizhi=n;s->next=NULL;p-〉next=s;p=s;}//cout«n请输入与顶点n«|«’’相联通的顶点号(以小于1的数或者大于顶点的数结束此次输入)(2)算法设计先是根据邻接表的顶点个数n,创建一个int型的数组a[nl(用来存储各顶点的入度),把a|n|中的每一项置为0。然后再邻接表遍历一下,先是顶点遍历,然后弧遍历。(1).根椐题意,设图(graph)的结构为:那么由上图可得如下邻接表: ►1—►Z.——►3Y. ►—►14 ►―►1—►1 ►0^—«►2Aindexnext在建立打向图的邻接表的时候,操作如下:确定图的顶点个数和边的个数;,并初始化该顶点的边表;;;;;(2)函数接口说明:odetypedefstructvnodetypedefstructintvexnum,um;voidcreate(graph&G)intgetchudu(graphQintn)//求有向图的第n个顶点入度voidgetrudu(graphG,intn)//打印有向图voidprint(graphG)voidmai