图状数据结构实验报告要求

《图状数据结构实验报告要求》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、图状数据结构实验报告要求1目的与要求:1）掌握图的邻接矩阵、邻接表、十字链表、邻接多重链表存储结构表示及其创建算法的c语言实现；2）掌握图的深度优先搜索遍历算法和图的广度优先搜索遍历算法及C语言实现；3）掌握普里姆构造最小生成树算法的数据结构和算法实现；4）按照实验题目要求独立完成实验内容（提交程序清单及相关实验数据与运行结果）；5）认真书写实验报告,并按时提交。2实验内容或题目题目1：图的建立与遍历；连通网的最小生成树生成实现。内容：1）用邻接表表示方法建立图1所示图的存储结构，用邻接矩阵存表示方法建立图2所示网的存储结构。2）在图1存储结构（邻接表）上实现深度优先搜索遍历和广度优先搜索遍历

2、，并给出遍历结果（序列）。3）按照普里姆算法，在图2所示连通网的存储结构（邻接矩阵）上实现此网的最小生成树，并输出生成树。V1V2V4V5V3V7V6V8例1有向图图2通信连通网（权值单位：百万元）V1v6v5v4v3V2265135664253实验步骤与源程序实验步骤：1.分析题目，分段思考算法。2.编写代码并输入代码。3.编译并调试。4．修正错误后，运行程序。5.完善程序。源程序：#include#include#defineMAX_VERTEX_NUM20#defineN20#defineINFINITY32768#defineTrue1#defin

3、eFalse0#defineError-1#defineOk1typedefenum{DG,DN,UDG,UDN}GraphKind;typedefstructArcNode1{intadj;}ArcNode1;typedefstruct{charvexs[N];ArcNode1arcs[N][N];intvexnum1,arcnum1;GraphKindkind1;}AdjMatrix1;typedefstructArcNode2{intadjvex;structArcNode2*nextarc;}ArcNode2;typedefstructVertexNode{chardata;ArcNo

4、de2*firstarc;}VertexNode;typedefstruct{VertexNodevertex[N];intvexnum2,arcnum2;GraphKindkind2;}AdjList;typedefstructNode{intdata;structNode*next;}LinkQueueNode;typedefstruct{LinkQueueNode*front;LinkQueueNode*rear;}LinkQueue;intInitQueue(LinkQueue*Q){Q->front=(LinkQueueNode*)malloc(sizeof(LinkQueueNod

5、e));if(Q->front!=NULL){Q->rear=Q->front;Q->front->next=NULL;return(True);}elsereturn(False);}intEnterQueue(LinkQueue*Q,intx){LinkQueueNode*NewNode;NewNode=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));if(NewNode!=NULL){NewNode->data=x;NewNode->next=NULL;Q->rear->next=NewNode;Q->rear=NewNode;return(T

6、rue);}elsereturn(False);}intDeleteQueue(LinkQueue*Q,int*x){LinkQueueNode*p;if(Q->front==Q->rear)return(False);p=Q->front->next;Q->front->next=p->next;if(Q->rear==p)Q->rear=Q->front;*x=p->data;free(p);return(True);}intIsEmpty(LinkQueue*Q){if(Q->front==Q->rear)return(True);elsereturn(False);}typedefst

7、ructnode1{chardata;structnode1*next;}Node1,*LinkList1;typedefstructnode2{chardata1;chardata2;structnode2*next;}Node2,*LinkList2;inta[2];intvisited[N];intLocateVertex1(AdjMatrix1*G1,charv){intk,j=Error