#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;
}

打赏

微信扫一扫，打赏作者吧～