数据结构实验3报告doc.docVIP

任课教师：孙树森 《数据结构与算法》 （2012-2013学年第2学期） 实 验 报 告 学号：2011329700214 姓名：周咪咪 班级：11数字媒体技术（2）班 实验3 图的建立与操作 一、实验目的和要求 在熟悉图的存储、遍历、及其应用的基础上，通过键盘输入数据，建立一个无向图的邻接表，输出该邻接表，并计算每个顶点的度。达到巩固图的存储思想及其存储实现。 二、实验内容 完成下图的邻接表表示，并计算每个顶点的度。 附加要求：进行深度优先和广度优先遍历 程序源码 #includeiostream #includemalloc.h #includestdio.h using namespace std; //----------无向图的邻接存储表示-------------- #define MAX_VERTEX_NUM 8 //顶点最大个数 int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//数组用于存储边信息 bool visited[MAX_VERTEX_NUM]; typedef struct ArcNode//边表结点 { int adjvex; //邻接点域，存储该顶点对应的下标 struct ArcNode *next;//链域，指向下一个邻接点 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 numNodes,numEdges;//当前顶点数，边数 }ALGraph; typedef struct{ int *elem; int front, rear; }Queue; void InitQueue(Queue Q) { Q.elem = new int[MAX_VERTEX_NUM]; Q.front = Q.rear = 0; } int QueueEmpty(Queue Q) { if(Q.front==Q.rear) return 0; else return 1; } void EnQueue(Queue Q, int e) { if((Q.rear + 1)%MAX_VERTEX_NUM != Q.front) Q.elem[Q.rear ] = e; else printf(队列满!\n); Q.rear = (Q.rear + 1)%MAX_VERTEX_NUM; } void DeQueue(Queue Q, int e) { if(Q.rear != Q.front) e = Q.elem[Q.front]; else printf(队列空!\n); Q.front = (Q.front+1)%MAX_VERTEX_NUM; } //---------建立无向图-------------- void CrateALGraph(ALGraph *G) { int i,j,k; //ArcNode *e; printf(输入顶点数和边数:\n); scanf(%d,%d,G-numNodes,G-numEdges); for(i=0;iG-numNodes;i++)//读入顶点信息，建立顶点表 { printf(输入顶点信息:\n); cinG-vertices[i].data; G-vertices[i].firstarc=NULL;//将边表置为空表 visited[i]=false; } for(k=0;kG-numEdges;k++)//建立边表 { printf(输入边(vi,vj)上的顶点序列:\n); scanf(%d,%d,i,j); //输入边(vi,vj)上的顶点序号 arc[i][j]=1;//两个顶点之间有边记作1 ArcNode *s1,*s2; s1=(ArcNode *)malloc(sizeof(ArcNode));//向内存申请空间，生成边表结点 s1-adjvex=j;//邻节序号为j s1-next=G-vertices[i].firstarc;//将e的