长春大学课程设计内页

1、装订线长 春 大 学 课程设计纸目 录1.设计目的与任务22.算法设计2.1设计思想22.2设计表示43.用户手册44.测试数据及测试结果45.课程设计总结5程序清单51.设计目的与任务1.1设计目的设计出一个有关邻接表的算法，能快速的计算出有向图的入度。1.2设计任务采用邻接表方式存储有向图，设计并实现算法：求解有n个顶点的有向图各顶点（用1n表示）的入度。2.算法设计2.1设计思想 （1）数据结构设计在本次算法设计中，我主要运用了3个结构体类型，如下：typedef struct arcnode int weizhi;/该边所指的顶点的位置 struct arcnode *next;arc

2、node;typedef struct vnode type data;/顶点信息 arcnode *firstarc;/指向第一条依附该顶点的边的指针vnode,adjlistmaxsize;typedef struct int vexnum,arcnum; adjlist a;graph;还运用了几个指针类型，举例如下：void create(graph &G) cout<<"请输入图的顶点个数：" cin>>G.vexnum; cout<<"请输入顶点的信息(字符表示)："<<endl; fo

3、r(int i=1;i<=G.vexnum;i+) cin>>G.ai.data; G.ai.firstarc=NULL; for(i=1;i<=G.vexnum;i+) int k=0; int n; cout<<"请输入与顶点"<<G.ai.data<<"相联通的顶点号(以大于顶点的数结束此次输入)：" while(cin>>n&&G.vexnum>=n>=1) /以小于大于顶点的数结束输入 k+; arcnode *p; if(k=1) /第一个边表

4、节点 p=new arcnode; p->next=NULL; p->weizhi=n; G.ai.firstarc=p; else arcnode *s; s=new arcnode; s->weizhi=n; s->next=NULL; p->next=s; p=s; /cout<<"请输入与顶点"<<G.ai.data<<"相联通的顶点号(以小于1的数或者大于顶点的数结束此次输入)：" （2）算法设计先是根据邻接表的顶点个数n,创建一个int型的数组an（用来存储各顶点的入度）,把a

5、n中的每一项置为0。然后再邻接表遍历一下，先是顶点遍历，然后弧遍历。2.2设计表示 （1）.根据题意，设图(graph)的结构为： 那么由上图可得如下邻接表： 在建立有向图的邻接表的时候,操作如下：a.确定图的顶点个数和边的个数； b.输入顶点信息存储在顶点表中，并初始化该顶点的边表；c.依次输入边的信息并将边所对应的邻接点信息存储在边表中；d.输入边所依附的两个顶点的序i和j；e.生成新的邻接点序号为j的边表结点s；        f.将结点s插入到第i个边表的头部；（2）函数接口说明：typedef

6、struct arcnodetypedef struct vnodetypedef struct int vexnum,arcnum;void create(graph &G)int getchudu (graph G,int n)/求有向图的第n个顶点入度void getrudu(graph G,int n)/打印有向图void print(graph G) void main()3.用户手册1.本程序的运行环境为Windows7/8/10操作系统,执行文件为Visual C+ 6.0.exe。2.进入演示程序后,即显示文本方式的用户界面。3.在完成上面两步的输入后按enter键便能

7、得到程序的运行结果，即给出题目所求的各顶点的入度。（例如：某题操作运行后结果如下：）4.测试数据及测试结果测试数据如下：7 91 22 32 52 63 54 35 25 46 77 91 26 77 9程序运行结果如下：5.课程设计总结在刚刚开始写程序时，根本无从下手，“Graph.h”都不会打开，更不会创建头文件直到把教材上有关有向图的邻接表相关知识看了几遍，基本上明白是怎么回事，才开始写代码。虽然书上和附赠的光盘上都有给出伪代码，但是有些定义的方法尚未给出，还需要自己编译。这5天的数据结构课程设计大家都是在摸石头过河和打破沙锅问到底的状态下完成的，我是在边看书边看PPT和网上百度求教完成

8、的此次的任务书。这几天在机房里把数据结构编写出来，感觉自己在编程方面的水平有了较大幅度的提高，特别是原先对于邻接表方面的知识十分模糊，现在慢慢的有了感觉知道他在计算机里面的存储方式和应用的优缺点。图这一章的内容整体来说是整个数据结构里面的重点和难点，它的关系是多对多，对于计算机方面的应用是比线性表和树更为灵活的，所以掌握图的操作是十分必要的。如果时间再充沛些的话我想我可以把此次的课程设计完成的更好一些。程序清单#include<iostream>using namespace std;#include<stdlib.h>#include<stdio.h>#d

9、efine type char#define maxsize 100typedef struct arcnode int weizhi;/该边所指的顶点的位置 struct arcnode *next;arcnode;typedef struct vnode type data;/顶点信息 arcnode *firstarc;/指向第一条依附该顶点的边的指针vnode,adjlistmaxsize;typedef struct int vexnum,arcnum; adjlist a;graph;void create(graph &G) cout<<"请输入图的

10、顶点个数：" cin>>G.vexnum; cout<<"请输入顶点的信息(字符表示)："<<endl; for(int i=1;i<=G.vexnum;i+) cin>>G.ai.data; G.ai.firstarc=NULL; for(i=1;i<=G.vexnum;i+) int k=0; int n; cout<<"请输入与顶点"<<G.ai.data<<"相联通的顶点号(以大于顶点的数结束此次输入)：" while(c

11、in>>n&&G.vexnum>=n>=1) /以小于大于顶点的数结束输入 k+; arcnode *p; if(k=1) /第一个边表节点 p=new arcnode; p->next=NULL; p->weizhi=n; G.ai.firstarc=p; else arcnode *s; s=new arcnode; s->weizhi=n; s->next=NULL; p->next=s; p=s; /cout<<"请输入与顶点"<<G.ai.data<<&quo

12、t;相联通的顶点号(以小于1的数或者大于顶点的数结束此次输入)：" /求有向图的第n个顶点出度int getchudu (graph G,int n) int count=0; arcnode *p; p=G.an.firstarc; if(p=NULL) return 0; while(p) count+; p=p->next; return count;/求有向图的第n个顶点入度void getrudu(graph G,int n) int count=0; for(int i=1;i<=G.vexnum;i+) arcnode *p; p=G.ai.firstarc

13、; if(p=NULL) continue; /跳过以下操作 while(p) if(p->weizhi=n) count+; p=p->next; else p=p->next; if(count!=0) cout<<"顶点"<<G.an.data<<"的入度为:"<<count<<endl; else cout<<"顶点"<<G.an.data<<"没有入度"<<endl;/打印有向图v

14、oid print(graph G) for(int i=1;i<=G.vexnum;i+) cout<<"顶点"<<G.ai.data<<"指向的顶点有：" arcnode *p; p=G.ai.firstarc; while(p) cout<<G.ap->weizhi.data<<" " p=p->next; cout<<endl; void main() int n; graph G; create(G); print(G); cout<<"请输入要求出度和入度的顶点号(以大于顶点的数目结束输入)：" while(cin>&g