数据结构-图及其应用(代码+报告).doc

发布时间：2022-06-09 发布人：admin 分类：说明书资料大小：0.21M 资料格式：doc 举报版权申诉

lesin_-4186070-4744302543016765669.doc.pdf-第1页.png

第1页 / 共11页

lesin_-4186070-4744302543016765669.doc.pdf-第2页.png

第2页 / 共11页

lesin_-4186070-4744302543016765669.doc.pdf-第3页.png

第3页 / 共11页

lesin_-4186070-4744302543016765669.doc.pdf-第4页.png

第4页 / 共11页

lesin_-4186070-4744302543016765669.doc.pdf-第5页.png

第5页 / 共11页

lesin_-4186070-4744302543016765669.doc.pdf-第6页.png

第6页 / 共11页

lesin_-4186070-4744302543016765669.doc.pdf-第7页.png

第7页 / 共11页

lesin_-4186070-4744302543016765669.doc.pdf-第8页.png

第8页 / 共11页

文本预览

附件 2：北京理工大学珠海学院实验报告 ZHUHAI CAMPAUS OF BEIJING INSTITUTE OF TECHNOLOGY 实验题目图及其应用实验时间 2011.5.10 一、实验目的、意义（1）熟悉图的邻接矩阵（或邻接表）的表示方法；（2）掌握建立图的邻接矩阵（或邻接表）算法；（3）掌握图的基本运算，熟悉对图遍历算法；（4）加深对图的理解，逐步培养解决实际问题的编程能力二、实验内容及要求说明 1：学生在上机实验时，需要自己设计出所涉及到的函数，同时设计多组输入数据并编写主程序分别调用这些函数，调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。具体要求：（1）建立图的邻接矩阵（或邻接表）；（2）对其进行深度优先及广度优先遍历。三、实验所涉及的知识点 1.创建一个图: CreateUDN(MGraph &G) 2.查找 v 顶点的第一个邻接点: FirstAdjVex(MGraph G,int v) 3. 查找基于 v 顶点的 w 邻接点的下一个邻接点: NextAdjVex(MGraph G,int v,int w) 4.图的矩阵输出: printArcs(MGraph G) 5:顶点定位: LocateVex(MGraph G,char v) 6. 访问顶点 v 输出: printAdjVex(MGraph G,int v) 7. 深度优先遍历: DFSTraverse(MGraph G,Status (*Visit)(MGraph G,int v)) 8. 广度优先遍历 BFSTraverse(MGraph G,Status (*Visit)(MGraph G,int v)) 9. DFS,从第 v 个顶点出发递归深度优先遍历图 G: DFS(MGraph G,int v) 四、实验记录 1.对顶点的定位其数组下标，利用了找到之后用 return 立即返回，在当图顶点多的情况下节省了搜索时间，程序如下 //对顶点 v 定位，返回该顶点在数组的下标索引，若找不到则返回-1 int LocateVex(MGraph G,char v){ 1

for (int i=0;i

a 1 2 3 c e 2 b d 4 顶点为：a，b，c，d，e 弧及其权值为：a,b,2 a,c,3 b,d,4 b,e,2 d,e,1 结果如下： 1.图的创建，先输入顶点个数与边数，如图 4.1.1，接着输入各顶点的值，如图 4.1.2，最后输入三条边依附的顶点以及权值，当输入的顶点不在图中时，会提示重新输入，如图 4.1.3 图 4.1.1 图 4.1.2 图 4.1.3 3

2.图的矩阵输出，如图 4.2 3.深度优先遍历图，输出序列，如图 4.3 图 4.2 4.广度优先遍历图，输出序列，如图 4.4 图 4.3 图 4.4 六、总结与体会图，是一种较线性表和树更为复杂的数据结构将其用深度遍历后，可以变成一棵树，或者一个森林。和树的遍历相类似，都利用了递归的方法，逐个搜索输出。用邻接矩阵表示图，形象地体现出顶点与顶点之间的紧密关系。七、程序清单(包含注释) /****************************** *题目:图及其应用 * * * * *姓名:刘锷欣 *学号:090202021029 * ******************************/ #include "stdio.h" #include "limits.h" #include "windows.h" #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 #define OVERFLOW -1 #define OK 1 #define ERROR 0 typedef int Status; //INT_MAX 头文件 //boolean 头文件 4

typedef enum {DG,DN,UDG,UDN} GraphKind; typedef int VRType; typedef char VertexType; typedef char* InfoType; typedef int QElemType; //边信息 typedef struct ArcCell{ VRType adj; InfoType *info; //图结构 typedef struct { //1 或 0 表示是否邻接,对带权图，则为权值类型 }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; VertexType vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; GraphKind kind; //定点向量 //邻接矩阵，为一二维数组 //图的当前顶点数和弧数 //图的种类标志 }MGraph; //辅助队列 typedef struct QNode{ QElemType data; struct QNode *next; }QNode, *QueuePtr; typedef struct{ QueuePtr front; QueuePtr rear; }LinkQueue; //数值域 //指针域 //队头 //队尾 //初始化队列 Status InitQueue(LinkQueue &Q){ printf("内存分配失败!"); exit(OVERFLOW); } Q.front->next = NULL; return OK; } Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)); if (!Q.front){ //插入元素到队尾 Status EnQueue(LinkQueue &Q,QElemType e){ QueuePtr p = (QueuePtr)malloc(sizeof(QNode)); if (!p) { 5

printf("\n 内存分配失败!"); exit(OVERFLOW); } p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return OK; } //队列判空 Status QueueEmpty(LinkQueue Q){ return Q.front == Q.rear; } //销毁队列 Status DestroyQueue(LinkQueue &Q){ while (Q.front) { Q.rear = Q.front->next; free(Q.front); Q.front = Q.rear; } return OK; //删除队头元素 Status DeQueue(LinkQueue &Q,QElemType &e){ } } if (QueueEmpty(Q)) { printf("\n 队列为空！"); return ERROR; } QueuePtr p = Q.front->next; e = p->data; Q.front->next = p->next; if(Q.rear==p) Q.rear = Q.front; free(p); return OK; //对顶点 v 定位，返回该顶点在数组的下标索引，若找不到则返回-1 int LocateVex(MGraph G,char v){ for (int i=0;i

return i; } return -1; } //create a graph Status CreateUDN(MGraph &G){ G.kind = UDN; printf("输入顶点个数和边数(如：4,3):"); scanf("%d,%d",&G.vexnum,&G.arcnum); //判断是否超过顶点最大个数 while(G.vexnum>MAX_VERTEX_NUM) { printf("最大顶点为 20，重新输入(如：4,3):"); scanf("%d,%d",&G.vexnum,&G.arcnum); } printf("\n 依次输入顶点向量值\n"); int i; for (i=0;i\n"); for(i=0;i

printf("输入顶点或不在此图中，请重新输入！\n"); i--; continue; } //赋予对应矩阵位置的权值，以及对称弧的权值 G.arcs[m][n].adj = values; G.arcs[n][m].adj = values; } return OK; } //CreateUDG //矩阵输出 void printArcs(MGraph G){ int i; printf(" "); //输出第一行的顶点向量 for (i=0;i

分享到：

赞收藏

资料库

数据结构-图及其应用(代码+报告).doc

相关推荐

课程资源

热门标签

最新资料