数据结构图的建立与计算

《数据结构图的建立与计算》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构图的建立与计算#include#include#include#include#include#defineNULL0#defineINFINITY2000//权值很大，表示两顶点不相关联#defineMAX20//图顶点数目最大值#defineNameLength20//顶点名称字符串容许的最大字符个数typedefenum{DG,DN,UDG,UDN//{有向图，有向网，无向图，无向网}}Graphkind;typedefstr

2、uctArcCell{intadj;//无权图，用1和0表示相邻否，对带权图，为权值char*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX][MAX];typedefstruct{charvexs[MAX][NameLength];//顶点名称AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数Graphkindkind;//图的种类标志}MGraph;typedefstructQNode{intdata;structQNode*next;}QNode,*

3、QueuePtr;//队列的结点结构体,存储的是指向二叉树结点的指针typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;//该结构体含指向队头的指针和队尾的指针//新建一个队列voidInitQueue(LinkQueue&Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));Q.front->next=NULL;}//将一个元素T插入队列voidEnQueue(LinkQueue&Q,inti){QueuePtrp;p=(QueueP

4、tr)malloc(sizeof(QNode));p->data=i;p->next=NULL;Q.rear->next=p;Q.rear=p;}//将一个元素从队列中删除，返回该元素intDeQueue(LinkQueue&Q,int&i){QueuePtrp;if(Q.front==Q.rear)return0;p=Q.front->next;i=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);return1;}//判断队列是否为空，若为空，返回

5、1，若不为空，则返回0intQueueEmpty(LinkQueueQ){if(Q.front==Q.rear)return1;elsereturn0;}//取得队头元素intGetHead(LinkQueueQ){return(Q.front->next->data);}//定位函数，求得字符串v在图G中的顶点序号，若不存在，返回-1，若存在，返回该序号intLocateVex(MGraphG,charv[5]){inti;for(i=0;i

6、ni;//查找printf("该顶点不存在！");return-1;}//该函数用于求与图G中序号为v的顶点相关联的第一个顶点（由于图用邻接矩阵表示，故有先后关系，//返回该顶点的序号intFirstAdjVex(MGraphG,intv){inti;for(i=0;i

7、ntw){inti;for(i=w+1;i

8、xnum;i++)gets(G.vexs[i]);//构造顶点向量for(i=0;i