#include <stdio.h> #include <stdlib.h> #include <string.h> #include <conio.h> #include <windows.h> #define MAX 7 const char *name[]= {"大成桥","广场","图书馆","人工湖","餐厅","篮球场","足球场"}; const char *describe[]= {"一座拱桥","齐鲁广场","很漂亮","没修好","第三食堂","还是水泥地","一圈400米"}; typedef struct { int num; char name[20]; char describe[30]; } GNode; typedef struct Node_Index { int index; struct Node_Index *next; } Index; typedef struct { GNode GraphNode; Index *next; } MGraph; /*-------------------------------Queue----------------------------------*/ #define DATATYPE MGraph typedef struct Queue_Node { DATATYPE data; struct Queue_Node *next; } QNode; typedef struct { QNode *head; QNode *end; int queuesize; } Queue; BOOL EnQueue(Queue **Q,DATATYPE Elem) { if(!*Q) { if((*Q=(Queue *)malloc(sizeof(Queue)))==NULL) return FALSE; memset(*Q,NULL,sizeof(Queue)); } if(!(*Q)->head) { //队列头结点为空 (*Q)->head=(*Q)->end=(QNode *)malloc(sizeof(QNode)); if((*Q)->head==NULL) return FALSE; memset((*Q)->head,NULL,sizeof(QNode)); (*Q)->head->data=Elem; (*Q)->queuesize++; return TRUE; } (*Q)->end->next=(QNode *)malloc(sizeof(QNode)); if((*Q)->end->next==NULL) return FALSE; memset((*Q)->end->next,NULL,sizeof(QNode)); (*Q)->end=(*Q)->end->next; (*Q)->end->data=Elem; (*Q)->queuesize++; return TRUE; } BOOL DeQueue(Queue *Q,DATATYPE *Elem) { if(!Q || !Q->head) return FALSE; QNode *temp=Q->head; Q->queuesize--; //队列长度减一 *Elem=Q->head->data; Q->head=Q->head->next; free(temp); return TRUE; } BOOL QueueEmpty(Queue *Q) { return Q->head==NULL?TRUE:FALSE; } //------------------------------------------------------------------------- void importInfo(MGraph *graph) { int i; for(i=0; i<MAX; i++) { memcpy(graph[i].GraphNode.name,name[i],strlen(name[i])); memcpy(graph[i].GraphNode.describe,describe[i],strlen(describe[i])); graph[i].GraphNode.num=i; } return; } int linkNode(MGraph *graph,int x,int y) { MGraph *G=NULL; Index *index=NULL,*temp=NULL; if((index=(Index *)malloc(sizeof(Index)))==NULL) return 0; memset(index,NULL,sizeof(Index)); G=graph+x; if(G->next==NULL) { G->next=index; } else { temp=G->next; while(temp->next) temp=temp->next; temp->next=index; } index->index=y; //=========================================== if((index=(Index *)malloc(sizeof(Index)))==NULL) return 0; memset(index,NULL,sizeof(Index)); G=graph+y; if(G->next==NULL) { G->next=index; } else { temp=G->next; while(temp->next) temp=temp->next; temp->next=index; } index->index=x; return 1; } int CreateGraph(MGraph **graph) { *graph=(MGraph *)malloc(sizeof(MGraph)*MAX); if(*graph==NULL) return 0; memset(*graph,NULL,sizeof(MGraph)*MAX); importInfo(*graph); return 1; } void visit(MGraph *graph) { printf("节点%d:景点:%s\t\t描述:%s\n",graph->GraphNode.num,graph->GraphNode.name,graph->GraphNode.describe); return; } int Traversal[MAX]; MGraph *root=NULL; int DFS(MGraph *graph) { //深度优先遍历 int i; Index *index=NULL; for(i=0; i<MAX; i++) if(graph->GraphNode.num==Traversal[i]) return 0; //检查节点是否已被访问过 visit(graph); for(i=0; i<MAX; i++) if(Traversal[i]==-1) { Traversal[i]=graph->GraphNode.num; break; } index=graph->next; while(index) { DFS(&root[index->index]); index=index->next; } return 1; } int BFS(MGraph *graph) { //广度优先遍历 Queue *Q=NULL; int i; MGraph temp,*ptemp=NULL; Index *index=NULL; visit(graph); index=graph->next; while(index) { EnQueue(&Q,root[index->index]); index=index->next; } Traversal[0]=0; while(!QueueEmpty(Q)) { memset(&temp,NULL,sizeof(MGraph)); DeQueue(Q,&temp); index=temp.next; while(index) { for(i=0; i<MAX; i++) if(index->index==Traversal[i]) goto skip; EnQueue(&Q,root[index->index]); skip: index=index->next; } visit(&temp); for(i=0; i<MAX; i++) if(Traversal[i]==-1) { Traversal[i]=temp.GraphNode.num; break; } } return 1; } int main() { int i,x,y; MGraph *graph=NULL; CreateGraph(&graph); root=graph; printf("请输入要连接的节点:(格式:X-Y)\n"); while(1) { if(scanf("%d-%d",&x,&y)!=2) break; linkNode(graph,x,y); } int j,k; Index *index=NULL; for(i=0; i<MAX; i++) { printf("%d ",graph[i].GraphNode.num); index=graph[i].next; while(index) { printf("->%d",index->index); index=index->next; } puts(""); } printf("深度优先遍历:\n"); for(i=0; i<MAX; i++) Traversal[i]=-1; DFS(graph); printf("\n广度优先遍历:\n"); for(i=0; i<MAX; i++) Traversal[i]=-1; BFS(graph); return 0; }
previous post