实验3图的建立与操作.doc

实验3 图的建立与操作 一、实验目的和要求 在熟悉图的存储、遍历、及其应用的基础上，通过键盘输入数据，建立一个无向图的邻接表，输出该邻接表，并计算每个顶点的度。达到巩固图的存储思想及其存储实现。 二、实验内容 完成下图的邻接表表示，并计算每个顶点的度。 附加要求：进行深度优先和广度优先遍历 三、实验提示 １．类型定义（邻接表存储） #define MAX_VERTEX_NUM 8 //顶点最大个数 typedef struct ArcNode { int adjvex; struct ArcNode *nextarc; int weight; //边的权 }ArcNode; //表结点 #define VertexType char //顶点元素类型 typedef struct VNode { int degree;//顶点的度，入度 VertexType data; ArcNode *firstarc; }VNode/*头结点*/,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum;//顶点的实际数，边的实际数 }ALGraph; 2．实验步骤 1）输入图中顶点信息，完成邻接表的VNode内容的初始化。 2）根据图中边的信息，把各边的信息链到firstarc指针链上，同时统计degree 3）输出邻接表。 代码 #include stdafx.h #includecstdlib #includeiostream #define WeightMax 100 #define UNDRIECT #define MAXDATA 100 #define MAXVEX 10 //#define WEIGHTTREE ////////////////////////////////////// using namespace std; /////////////////////////////////////////// //////////////////////////////////////////// typedef char DataType; struct ENode { int tailvex,headvex; int weight; struct ENode *tailnext,*headnext; }; struct VerNode { DataType data; ENode *firstin; ENode *firstout; }; //typedef VerNode AdjList[MAXVEX]; struct MGraphs{ VerNode adjList[MAXVEX]; //ENode *edgeList[MAXVEX][MAXVEX]; int numNode,numEdge; }; ////////////////////////////////////// /////////////////////////////////// int LocateVex(MGraphs G,DataType data) { int i=0; for( i=0;iG.numNode;++i) {if(G.adjList[i].data==data) return i; } return -1; } //////////////////////////////////////// ////////////the build graph//////////////// //////////////one construct////////////////////// void CreatALGraph(MGraphs G) { int weight; int i,j; DataType vi,vj; ENode *e; coutplease input the numNode and numEdgeendl; cinG.numNodeG.numEdge; coutplese input the node informationendl; for(i=0;iG.numNode;i++) { cinG.adjList[i].data; G.adjList[i].firstin=NULL; G.adjList[i].firstout=NULL; } fo