开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 数据结构 > 查看源码
8_3_2.C
资源名称：04722-x　[点击查看]
上传用户：wyn840322
上传日期：2007-01-13
资源大小：294k
文件大小：5k
源码类别：

数据结构

开发平台：

C/C++

8_3_2.C：源码内容
  1. /* ======================================== */
  2. /*    程式实例: 8_3_2.c                     */
  3. /*    图形的广度优先搜寻法                  */
  4. /* ======================================== */
  5. #include <stdlib.h>
  6. #define MAXQUEUE 10               /* 伫列的最大容量       */
  8. struct node                       /* 图形顶点结构宣告     */
  9. {
  10.    int vertex;                    /* 顶点资料             */
  11.    struct node *nextnode;         /* 指下一顶点的指标     */
  12. };
  13. typedef struct node *graph;       /* 图形的结构新型态     */
  14. struct node head[9];              /* 图形顶点结构数组     */
  15. int visited[9];                   /* 遍历记录数组         */
  17. int queue[MAXQUEUE];              /* 伫列的数组宣告       */
  18. int front = -1;                   /* 伫列的前端           */
  19. int rear = -1;                    /* 伫列的后端           */
  21. /* ---------------------------------------- */
  22. /*  建立图形                                */
  23. /* ---------------------------------------- */
  24. void creategraph(int *node,int num)
  25. {
  26.    graph newnode;                 /* 新顶点指标           */
  27.    graph ptr;
  28.    int from;                      /* 边线的起点           */
  29.    int to;                        /* 边线的终点           */
  30.    int i;
  32.    for ( i = 0; i < num; i++ )    /* 读取边线的回路       */
  33.    {
  34.       from = node[i*2];           /* 边线的起点           */
  35.       to = node[i*2+1];           /* 边线的终点           */
  36.       /* 建立新顶点记忆体 */
  37.       newnode = ( graph ) malloc(sizeof(struct node));
  38.       newnode->vertex = to;       /* 建立顶点内容         */
  39.       newnode->nextnode = NULL;   /* 设定指标初值         */
  40.       ptr = &(head[from]);        /* 顶点位置             */
  41.       while ( ptr->nextnode != NULL ) /* 遍历至链表尾     */
  42.          ptr = ptr->nextnode;         /* 下一个顶点       */
  43.       ptr->nextnode = newnode;        /* 插入结尾         */
  44.    }
  45. }
  47. /* ---------------------------------------- */
  48. /*  伫列资料的存入                          */
  49. /* ---------------------------------------- */
  50. int enqueue(int value)
  51. {
  52.    if ( rear >= MAXQUEUE )        /* 检查伫列是否全满     */
  53.       return -1;                  /* 无法存入             */
  54.    rear++;                        /* 后端指标往前移       */
  55.    queue[rear] = value;           /* 存入伫列             */
  56. }
  58. /* ---------------------------------------- */
  59. /*  伫列资料的取出                          */
  60. /* ---------------------------------------- */
  61. int dequeue()
  62. {
  63.    if ( front  == rear )          /* 检查伫列是否是空     */
  64.       return -1;                  /* 无法取出             */
  65.    front++;                       /* 前端指标往前移       */
  66.    return queue[front];           /* 伫列取出             */
  67. }
  69. /* ---------------------------------------- */
  70. /*  图形的广度优先搜寻法                    */
  71. /* ---------------------------------------- */
  72. void bfs(int current)
  73. {
  74.    graph ptr;
  76.    /* 处理第一个顶点 */
  77.    enqueue(current);              /* 将顶点存入伫列       */
  78.    visited[current] = 1;          /* 记录已遍历过         */
  79.    printf("顶点[%d] ",current);   /* 印出遍历顶点值       */
  80.    while ( front != rear )        /* 伫列是否是空的       */
  81.    {
  82.       current = dequeue();        /* 将顶点从伫列取出     */
  83.       ptr = head[current].nextnode;   /* 顶点位置         */
  84.       while ( ptr != NULL )           /* 遍历至链表尾     */
  85.       {
  86.          if ( visited[ptr->vertex] == 0 ) /* 如过没遍历过 */
  87.          {
  88.             enqueue(ptr->vertex);     /* 递回遍历呼叫     */
  89.             visited[ptr->vertex] = 1; /* 记录已遍历过     */
  90.             /* 印出遍历顶点值 */
  91.             printf("顶点[%d] ",ptr->vertex);
  92.          }
  93.          ptr = ptr->nextnode;     /* 下一个顶点           */
  94.       }
  95.    }
  96. }
  98. /* ---------------------------------------- */
  99. /*  主程式: 建立图形后,将遍历内容印出.      */
  100. /* ---------------------------------------- */
  101. void main()
  102. {
  103.    graph ptr;
  104.    int node[20][2] = { {1, 2}, {2, 1},  /* 边线数组       */
  105.                        {1, 3}, {3, 1},
  106.                        {2, 4}, {4, 2},
  107.                        {2, 5}, {5, 2},
  108.                        {3, 6}, {6, 3},
  109.                        {3, 7}, {7, 3},
  110.                        {4, 8}, {8, 4},
  111.                        {5, 8}, {8, 5},
  112.                        {6, 8}, {8, 6},
  113.                        {7, 8}, {8, 7} };
  114.    int i;
  116.    for ( i = 1; i <= 8; i++ )
  117.    {
  118.       head[i].vertex = i;         /* 设定顶点值           */
  119.       head[i].nextnode = NULL;    /* 清除图形指标         */
  120.       visited[i] = 0;             /* 设定遍历初值         */
  121.    }
  122.    creategraph(node,20);          /* 建立图形             */
  123.    printf("图形的邻接链表内容:n");
  124.    for ( i = 1; i <= 8; i++ )
  125.    {
  126.       printf("顶点%d =>",head[i].vertex); /* 顶点值       */
  127.       ptr = head[i].nextnode;             /* 顶点位置     */
  128.       while ( ptr != NULL )       /* 遍历至链表尾         */
  129.       {
  130.          printf(" %d ",ptr->vertex);  /* 印出顶点内容     */
  131.          ptr = ptr->nextnode;         /* 下一个顶点       */
  132.       }
  133.       printf("n");               /* 换行                 */
  134.    }
  135.    printf("图形的广度优先遍历内容:n");
  136.    bfs(1);                        /* 印出遍历过程         */
  137.    printf("n");                  /* 换行                 */
  138. }