数据结构与算法实验报告-图

1、数据结构与算法实验报告-图 导读：就爱阅读网友为您分享以下“数据结构与算法实验报告-图”的资讯，希望对您有所帮助，感谢您对的支持! q=(ArcNode *)malloc(sizeof(ArcNode); q-weight=weight; q-adjvex=m1; if(list.vexnoden1.firstArc=NULL) list.vexnoden1.firstArc=q; q-next=NULL; else q-next=list.vexnoden1.firstArc; list.vexnoden1.firstArc=q; printf(邻接表构造成功nntt邻接矩阵构造成功！n s

2、ystem( system( void inputMatric() /输出邻接矩阵 printf(邻接矩阵：n printf( for(i=0;i printf( printf( for(i=0;inext) printf( printf( 10 int FirstAdjVex(int i) /返回邻接表中该弧的第一个节点指向的位置 int a; if(list.vexnodei.firstArc=NULL) a=-1; else a=list.vexnodei.firstArc-adjvex; / printf(/ return a; int NextAdjVex(int i,int j)

3、/返回第i个顶点的邻接表中指向j的节点的后面节点的指向 int a; for(p=list.vexnodei.firstArc;p!=NULL;p=p-next) if(p-adjvex=j) break; if(p=NULL) return -1; else if(p-next=NULL) return -1; else return p-next-adjvex; void Depth_First_Search() /深度优先搜索 11 printf(深度优先搜索:n for(i=0;i0;j=NextAdjVex(i,j) if(!visitedj) DFS(visited,j); voi

4、d Breadth_First_Search() /广度优先搜素 printf(广度优先搜素:n for(i=0;i list.visitedi=0; for(i=0;inext) if(!visitedp-adjvex) printf( visitedp-adjvex=1; EnQueue(p-adjvex); 13 沈 阳 工 程 学 院 学 生 实 验 报 告 （课程名称： 数据结构与算法 ） 图 实验题目： 1 一、实验目的 1掌握图的基本存储方法。 2掌握有关图的操作算法并用高级语言实现。 3熟练掌握图的两种搜索路径的遍历方法。 4掌握图的有关应用。 二、实验环境 Turbo C或是

5、Visual C+ 三、实验内容与要求 实验1 建立无向图的邻接矩阵或邻接表存储并输出 本题给出了一个无向图的邻接矩阵存储表示，在此基础上稍加改动就可以实现有向图、无向图和有向网的邻接矩阵表示。 实验2 建立图的邻接矩阵或邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历 图的广度优先遍历用非递归方法很容易理解，非递归方法需要辅助队列Q以及出队、入队函数。 四、实验过程及结果分析 1.程序代码 #include #include #define MAXSIZE 50 typedef struct /邻接矩阵结构体 int arcsMAXSIZEMAXSIZE; /矩阵数组 char *v

6、exs; /顶点向量 int vexnum,arcnum; 2 int GraphKind; /图的种类，1无向图，2有向图 Matric; typedef struct ArcNode /邻接表弧的结构体 int adjvex; /该弧指向定点的位置 int weight; struct ArcNode *next; ArcNode; typedef struct VexNode /邻接表的数组节点 char vex; ArcNode * firstArc; VexNode ; typedef struct /邻接表的顶点数组 VexNode *vexnode; int *visited;

7、/储存是否被检索过 int vexnum,arcnum; int GraphKind; List; typedef struct QueueNode int local; struct QueueNode *next; 3 QueueNode; typedef struct QueueNode *head; QueueNode *rear; int count; Queue; typedef struct char adjvex; int lowcost; CloseDge; CloseDge *closedge; /*-深度优先搜索相关函数-*/ void Depth_First_Searc

8、h(); /深度优先搜索 void DFS(int *visited,int i); int FirstAdjVex(int i); /返回邻接表中该弧的第一个节点指向的位置 int NextAdjVex(int i,int j); /返回第i个顶点的邻接表中指向j的节点的后面节点的指向 /*-*/ /*-广度优先搜索相关函数-*/ void Breadth_First_Search(); /广度优先搜素 void EnQueue(int i); /元素入队 int DeQueue(); /元素出队 void inputQueue();/输出队列中的元素 4 void BFS(int * vi

9、sited,int i); /*-*/ void create(); /创建邻接矩阵,邻接矩阵 void inputMatric();/输出邻接矩阵 void inputList();/输出邻接表 int mininum(CloseDge *closedge); int i,j,m,n; int weight; char head,rear,m1,n1; Matric matric; List list; Queue queue; QueueNode *temqueuenode; ArcNode *p,*q ; void create() /创建邻接矩阵 printf(请输入图的种类：ntt1

10、.无向图ntt2.有向图n fflush(stdin); scanf( list.GraphKind=matric.GraphKind; system( system( printf(请输入顶点数： fflush(stdin); 5 void BFS(int * visited,int i); /*-*/ void create(); /创建邻接矩阵,邻接矩阵 void inputMatric();/输出邻接矩阵 void inputList();/输出邻接表 int mininum(CloseDge *closedge); int i,j,m,n; int weight; char head

11、,rear,m1,n1; Matric matric; List list; Queue queue; QueueNode *temqueuenode; ArcNode *p,*q ; void create() /创建邻接矩阵 printf(请输入图的种类：ntt1.无向图ntt2.有向图n fflush(stdin); scanf( list.GraphKind=matric.GraphKind; system( system( printf(请输入顶点数： fflush(stdin); 5 scanf( list.vexnum=matric.vexnum; printf(请输入弧数： f

12、flush(stdin); scanf( list.arcnum=matric.arcnum; queue.count=0; queue.head=NULL; queue.rear=NULL; matric.vexs=(char *)malloc(sizeof(char)*(matric.vexnum); list.vexnode=(VexNode *)malloc(sizeof(VexNode)*matric.vexnum); list.visited=(int *)malloc(sizeof(int)*list.vexnum); for(i=0;i printf(请输入第%d个顶点: ff

13、lush(stdin); scanf( list.vexnodei.vex=matric.vexsi; printf(顶点集输入成功！n system( system( printf(请输入弧集(输入模式：“弧头，弧尾,权值”,若为无权图，则权值均输入”1“):n for(i=0;i if(head=matric.vexsm) m1=m; for(n=0;nweight=weight; p-adjvex=n1; if(list.vexnodem1.firstArc=NULL) list.vexnodem1.firstArc=p; p-next=NULL; else p-next=list.ve

14、xnodem1.firstArc; list.vexnodem1.firstArc=p; if(matric.GraphKind=1) matric.arcsn1m1=weight; 8 q=(ArcNode *)malloc(sizeof(ArcNode); q-weight=weight; q-adjvex=m1; if(list.vexnoden1.firstArc=NULL) list.vexnoden1.firstArc=q; q-next=NULL; else q-next=list.vexnoden1.firstArc; list.vexnoden1.firstArc=q; pr

15、intf(邻接表构造成功nntt邻接矩阵构造成功！n system( system( void inputMatric() /输出邻接矩阵 printf(邻接矩阵：n printf( for(i=0;i list.visitedi=0; for(i=0;inext) if(!visitedp-adjvex) printf( visitedp-adjvex=1; EnQueue(p-adjvex); 13 if(queue.count!=0) BFS(visited,DeQueue(); void EnQueue(int i) /元素入队 temqueuenode=(QueueNode *)ma

16、lloc(sizeof(QueueNode); temqueuenode-local=i; if(queue.count=0) queue.head=temqueuenode; queue.rear=temqueuenode; temqueuenode-next=NULL; queue.count+; else queue.rear-next=temqueuenode; queue.rear=temqueuenode; queue.count+; /printf(元素%c入队成功！n /inputQueue(); int DeQueue() /元素出队 14 if(queue.count=0)

17、 printf(队列为空！无法完成输出操作！n else temqueuenode=queue.head; queue.head=queue.head-next; queue.count-; /printf(元素%c出队成功！n /inputQueue(); return temqueuenode-local; void inputQueue() for(i=0,temqueuenode=queue.head;inext) printf(队列中第%d个元素：%cn 15 int main() create(); inputMatric(); printf( system( system( inputList(); printf( system( system( Depth_First_Search(); printf( system( system( Breadth_First_Search(); printf( system( return 0; 2.程序运行分析 (1)主菜单 16 图1 主菜单 (2) 初始化邻接表与邻接矩阵 图 2 初始化邻接表与邻接矩阵 17 图1 主菜单 (2) 初始化邻接表与邻接矩阵 图 2 初始化邻接表与邻接矩阵 17 (3)输入顶点集 图 3 输入