实验报告--第七章--2011211102--车红岫.doc

实验名称：第7章实验 实验类型：验证性实验班级：20112111学号：2011211102姓名：车红岫实验日期：2013.61. 问题描述以下验证性实验都做（1）邻接矩阵l 邻接矩阵的C语言描述l 基本运算的算法建立无向网的邻接矩阵、求图中与顶点i邻接的第一个顶点、求图中顶点i相对于顶点j的下一个邻接点、若图G中存在顶点u，则返回该顶点在图中的位置、图的广度优先遍历、图的深度优先遍历（2）邻接表l 邻接表的C语言描述l 基本运算的算法建立无向网的邻接表、求图中与顶点i邻接的第一个顶点、求图中顶点i相对于顶点j的下一个邻接点、若图G中存在顶点u，则返回该顶点在图中的位置、图的广度优先遍历、图的深度优先遍历2.2. 数据结构设计（一）邻接矩阵typedef struct char *vexs; int arcsMAX_VEXMAX_VEX; int vexnum,arcnum; Graph;（2） 邻接表typedef struct arcnode int num; /该弧所指向的顶点的位置 struct arcnode *nextarc; /指向下一条弧的指针arcnode;typedef struct vexnode char data; /顶点信息 arcnode *firstarc; /指向第一条依附该顶点的弧的指针vexnode;typedef struct vexnode vertexmax; int vexnum; /图的当前顶点数 int arcnum; /图的当前弧数ALG;typedef struct int datamax+10; int front; int rear;queue;3. 算法设计l 建立无向网的邻接矩阵、求图中与顶点i邻接的第一个顶点、求图中顶点i相对于顶点j的下一个邻接点、若图G中存在顶点u，则返回该顶点在图中的位置、图的广度优先遍历、图的深度优先遍历l 建立无向网的邻接表、求图中与顶点i邻接的第一个顶点、求图中顶点i相对于顶点j的下一个邻接点、若图G中存在顶点u，则返回该顶点在图中的位置、图的广度优先遍历、图的深度优先遍历2.4. 界面设计（1） 邻接矩阵 （二）邻接表5. 运行、测试（一）邻接矩阵（1） 运行程序，显示菜单 （2） 输入数量 (3)输出结果 （二）邻接表（1）运行程序，显示菜单 （2） 输入n (3)输出结果6. 实验收获及思考 注意每个表示要求的输入，且选择适当的结构体可简化问题。 附录：源代码（1）邻接矩阵#include #include #define INFINITY 32767#define MAX_VEX 20 #define QUEUE_SIZE (MAX_VEX+1) bool *visited; typedef struct char *vexs; int arcsMAX_VEXMAX_VEX; int vexnum,arcnum; Graph;class Queue public: void InitQueue() base=(int *)malloc(QUEUE_SIZE*sizeof(int); front=rear=0; void EnQueue(int e) baserear=e; rear=(rear+1)%QUEUE_SIZE; void DeQueue(int &e) e=basefront; front=(front+1)%QUEUE_SIZE; public: int *base; int front; int rear;int Locate(Graph G,char c) for(int i=0;iG.vexnum;i+) if(G.vexsi=c) return i; return -1;void CreateUDN(Graph &G) int i,j,w,s1,s2; char a,b,temp; printf(输入顶点数和弧数:); scanf(%d%d,&G.vexnum,&G.arcnum); temp=getchar(); G.vexs=(char *)malloc(G.vexnum*sizeof(char); printf(输入%d个顶点.n,G.vexnum); for(i=0;iG.vexnum;i+) /构造顶点向量 printf(输入顶点%d:,i); scanf(%c,&G.vexsi); temp=getchar(); for(i=0;iG.vexnum;i+) /初使化邻接矩阵 for(j=0;jG.vexnum;j+) G.arcsij=INFINITY; printf(输入%d条弧.n,G.arcnum); for(i=0;i=0 & kG.vexnum) for(int i=0;i=0 & i=0 & jG.vexnum) for(int k=j+1;kG.vexnum;k+) if(G.arcsik!=INFINITY) return k; return -1;void DFS(Graph G,int k) int i; if(k=-1) for(i=0;i=0;i=NextVex(G,k,i) if(!visitedi) DFS(G,i); void BFS(Graph G) int k; Queue Q; Q.InitQueue(); for(int i=0;i=0;w=NextVex(G,k,w) if(!visitedw) visitedw=true; printf(%c ,G.vexsw); Q.EnQueue(w);void main() int i; Graph G; CreateUDN(G); visited=(bool *)malloc(G.vexnum*sizeof(bool); printf(n广度优先遍历: ); for(i=0;iG.vexnum;i+) visitedi=false; DFS(G,-1); printf(n深度优先遍历: ); for(i=0;iG.vexnum;i+) visitedi=false; BFS(G); printf(n程序结束.n); system(pause);（2） 邻接表#include#define max 20#include#includetypedef struct arcnode int num; /该弧所指向的顶点的位置 struct arcnode *nextarc; /指向下一条弧的指针arcnode;typedef struct vexnode char data; /顶点信息 arcnode *firstarc; /指向第一条依附该顶点的弧的指针vexnode;typedef struct vexnode vertexmax; int vexnum; /图的当前顶点数 int arcnum; /图的当前弧数ALG;typedef struct int datamax+10; int front; int rear;queue;int visitedmax;queue q;int locate(ALG *g,char v) inti; for(i=0;ivexnum;i+) if(g-vertexi.data=v) break; return(i);void creatgraph(ALG *g) inti; charc; arcnode *rear,*temp; printf(输入图的顶点数和边数n); scanf(%d%d,&g-vexnum,&g-arcnum); getchar(); printf(输入所有顶点n); for(i=0;ivexnum;i+) scanf(%c,&(g-vertexi.data); g-vertexi.firstarc=NULL; getchar(); for(i=0;ivexnum;i+) printf(输入所有和%c相连的顶点，以*结束n,g-vertexi.data); if(c=getchar()!=*) rear=(arcnode *)malloc(sizeof(arcnode); g-vertexi.firstarc=rear; rear-num=locate(g,c); while(c=getchar()!=*) temp=(arcnode *)malloc(sizeof(arcnode); temp-num=locate(g,c); rear-nextarc=temp; rear=temp; rear-nextarc=NULL; getchar(); void depthfirstsearch(ALG *g,intvi) arcnode *rear; putchar(g-vertexvi.data); visitedvi=1; rear=g-vertexvi.firstarc; while(rear!=NULL)&(!visitedrear-num) depthfirstsearch(g,rear-num); rear=rear-nextarc; void travel(ALG *g) intv; for(v=0;vvexnum;v+) if(!visitedv) depthfirstsearch(g,v);void enterqueue(int v) q.dataq.rear=v; q.rear+;int deletequeue() intt; t=q.dataq.front; q.front+; return(t);int empty() if(q.front=q.rear) return1; return0;void breadfirstsearch(ALG *g) int v,t; arcnode *rear; for(v=0;vvexnum;v+) if(!visitedv) putchar(g-vertexv.data); visitedv=1; enterqueue(v); while(!empty() t=deletequeue(); rear=g-vertext.firstarc; while(rear!=NULL)&(!visitedrear-num) putchar(g-vertexrear-num.data); visitedrear-num=1; enterqueue(rear-num); rear=rear-nextarc; void main() i