数据结构图的遍历实验报告.docx

数据结构图的遍历实验报告

第一篇：数据结构图的遍历实验报告实验报告课程名：数据结构（实验名：图的遍历姓名：班级：学号：时间：C语言版）2014.11.15一实验目的与要求1.掌握图的遍历的方法2.利用C语言实现图的遍历二实验内容•将一个图存储起来•对该图分别进行先深和先广遍历三实验结果与分析程序：#include#include#defineINFINITY32767#defineMAX_VEX20//最大顶点个数#defineQUEUE_SIZE(MAX_VEX+1)//队列长度//usingnamespacestd;bool*visited;//访问标志数组,避免同一顶点多次访问/****图的邻接矩阵存储结构******/typedefstruct{char*vexs;//顶点向量intarcs[MAX_VEX][MAX_VEX];//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数}Graph;/*********队列类************/classQueue{public:voidInitQueue(){base=(int*)malloc(QUEUE_SIZE*sizeof(int));front=rear=0;}voidEnQueue(inte){base[rear]=e;rear=(rear+1)%QUEUE_SIZE;}voidDeQueue(int&e){e=base[front];front=(front+1)%QUEUE_SIZE;}public:int*base;intfront;intrear;};/*图G中查找元素c的位置*/intLocate(GraphG,charc){for(inti=0;iG.vexs=(char*)malloc(G.vexnum*sizeof(char));//分配顶点数目printf(“输入%d个顶点.n”,G.vexnum);for(i=0;iprintf(“输入顶点%d:”,i);scanf(“%c”,&G.vexs[i]);temp=getchar();//接收回车}for(i=0;ifor(j=0;jprintf(“输入弧%d:”,i);scanf(“%c%c%d”,&a,&b,&w);//输入一条边依附的顶点和权值temp=getchar();//接收回车s1=Locate(G,a);s2=Locate(G,b);G.arcs[s1][s2]=G.arcs[s2][s1]=w;}}/*****图G中顶点k的第一个邻接顶点***********/intFirstVex(GraphG,intk){if(k>=0&&kfor(inti=0;i=0&&i=0&&jfor(intk=j+1;kvisited[k]=true;printf(“%c”,G.vexs[k]);//访问第k个顶点for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))if(!visited[i])DFS(G,i);//对k的尚未访问的邻接顶点i递归调用DFS}}/****************广度优先遍历***************/voidBFS(GraphG){intk;QueueQ;//辅助队列QQ.InitQueue();for(inti=0;ivisited[i]=true;printf(“%c”,G.vexs[i]);Q.EnQueue(i);//i入列while(Q.front!=Q.rear){Q.DeQueue(k);//队头元素出列并置为kfor(intw=FirstVex(G,k);w>=0;w=NextVex(G,k,w))if(!visited[w]){//w为k的尚未访问的邻接顶点visited[w]=true;printf(“%c”,G.vexs[w]);Q.EnQueue(w);}}}}/***********主函数***************/voidmain(){inti;GraphG;CreateUDN(G);visited=(bool*)malloc(G.vexnum*sizeof(bool));printf(“n广度优先遍历:”);for(i=0;i图1.图的遍历程序运行结果第二篇：数据结构-二叉树的遍历实验报告实验报告课程名：数据结构（C语言版）实验名：二叉树的遍历姓名：班级：学号：时间：2014.11.03一实验目的与要求1.掌握二叉树的存储方法2.掌握二叉树的三种遍历方法3.实现二叉树的三种遍历方法中的一种二实验内容•接受用户输入一株二叉树•输出这株二叉树的前根,中根,后根遍历中任意一种的顺序三实验结果与分析//*****************************************