邻接表表示的图的基本操作的实现.docx

《邻接表表示的图的基本操作的实现.docx》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、邻接表表示的图的基本操作的实现//采用邻接表完成无权无向及有向图的"建立、输出、深度遍历、广度遍历"操作#include#include#defineOK1#defineERROR-1typedefintStatus;typedefintElemType;//此例中设元素为单值元素，类型为整型#defineMAX_VERTEX_NUM20//最大顶点个数typedefintElemType;//图顶点数据类型typedefintQueueElemType;//队列结点数据类型//链表结点

2、类型定义typedefstructQnode{QueueElemTypedata;structQnode*next;}QNode;//队列类型定义：typedefstructLinkqueue{QNode*front,*rear;}LinkQueue;//图的数据类型定义typedefstructTablenode//表结点结构{intadjVex;//邻接点域，存放与vi相邻接的顶点vj的序号jstructTablenode*next;//指针域，将邻接表的所有表结点链在一起floatweight;//对于带权图，表示权值

3、，对于无权图则可省略此数据域}TableNode;typedefstructHeadnode//头结点结构{ElemTypevertex;//顶点域vertex，存放顶点vi的信息structTablenode*firstEdge;//vi的邻接表的头指针}HeadNode;typedefstructMgraph{structHeadnodevector[MAX_VERTEX_NUM];//顶点向量intvexnum;//图中当前顶点数}MGraph;//队列初始化StatusInitLinkQueue(LinkQueue*

4、Q){QNode*p;p=(QNode*)malloc(sizeof(QNode));//开辟头结点空间if(p!=NULL){p->next=NULL;Q->front=Q->rear=p;returnOK;}elsereturnERROR;}//链式队列的入队操作，在已知队列的队尾插入一个元素e，修改队尾指针rear。StatusInsertLinkQueue(LinkQueue*Q,ElemTypee){QNode*p;p=(QNode*)malloc(sizeof(QNode));if(p==NULL)returnE

5、RROR;//申请新结点空间失败，返回错误标志else{p->data=e;//存入新结点数据p->next=NULL;Q->rear->next=p;//新结点插入到队尾Q->rear=p;//新插入结点成为新的队尾returnOK;}}//链式队列的出队操作，取第一个数据结点的数据后删除该结点StatusDeleteLinkQueue(LinkQueue*Q,ElemType*e){QNode*p;if(Q->front==Q->rear)//可改为：if(Q->front->next==NULL)returnERROR

6、;//队空else{p=Q->front->next;//取队首结点*e=p->data;Q->front->next=p->next;//修改队首指针if(p==Q->rear)//条件成立说明只有一个数据结点Q->rear=Q->front;//当队列只有一个数据结点时应防止丢失队尾指针free(p);Q->rear->next=NULL;returnOK;}}//判断队列是否为空StatusIsEmptyLinkQueue(LinkQueue*Q){if(Q->front==Q->rear)returnOK;elser

7、eturnERROR;}//释放队列voidDestroyLinkQueue(LinkQueue*Q){QNode*p,*q;p=Q->front;//指向链表第一个结点，即整个链表的第一个结点while(p!=NULL){q=p->next;//保存链表后半段首地址以防丢失free(p);p=q;}}/**************以下为图的操作************///顶点在顶点向量中的定位，找到返回OK，否则返回ERROR//G为的数据结构，v为待查顶点，n用于返回找到的顶点下标StatusLocateVex(MGr

8、aphG,ElemTypev,int*n){inti;for(i=0;((i