图的遍历-广度优先

奥普瓯江

原理：


备注：



代码：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #define MAX 9
   
4. 
   
5. 
   
6. typedef struct list
   
7. {
   
8.     int data;
   
9.     struct list *next;
   
10. }list, *lists;
    
11. 
    
12. typedef struct dack
    
13. {
    
14.     char litte;
    
15.     int Blo;
    
16.     list *happy;
    
17. }dack;
    
18. void get_list(list **happy);
    
19. //void print_list(list *happy);
    
20. void loop_list(dack OK[MAX]);
    
21. void free_list(list *temp);
    
22. 
    
23. void free_list(list *temp)      //释放
    
24. {
    
25.     if(!temp)
    
26.     {
    
27.         return;
    
28.     }
    
29.     free_list(temp->next);
    
30.     free(temp);
    
31. }
    
32. 
    
33. void loop_list(dack OK[MAX])            //广度优先遍历
    
34. {
    
35.     list *temp;                 //临时变量
    
36.     int i, S = 0;
    
37. 
    
38.     for(int j = 0; j < MAX; j++)           //遍历每一个节点A-I
    
39.     {
    
40.         temp = OK[j].happy;                 //把赋予temp初始变量，这个初始变量是每个节点的初始变量A的初始变狼B的初始变量等等
    
41.         i = j;
    
42.         while(1)                            //循环每个节点后的变量
    
43.         {
    
44.             if(OK[i].Blo != 1)               //如果这个节点被打印过就不对该几点进行执行输出
    
45.             {
    
46. 
    
47.                 printf("%c", OK[i].litte);
    
48.                 OK[i].Blo = 1;                //标记该节点证明其被输出过
    
49.                 S++;
    
50.                 if(S > MAX)                   //减少遍历次数，如果前几个节点已经全部遍历完整个图及结束函数，后面的节点就不用遍历了
    
51.                 {
    
52.                     return;
    
53.                 }
    
54.             }
    
55.             if(temp == NULL)                  //如果该节点以执行到最后空的位置及跳出while循环
    
56.             {
    
57.                 break;
    
58.             }
    
59.             else
    
60.             {
    
61.                 i = temp->data;                 //未执行到连边最后的位置则将该位置链表所包含的数据传给i使得其继续循环
    
62.             }
    
63.             temp = temp->next;                  //链表向后循环
    
64.         }
    
65.     }
    
66. }
    
67. 
    
68. /*void print_list(list *happy)        //打印输出
    
69. {
    
70.     while(happy)
    
71.     {
    
72.         printf("%3d", happy->data);
    
73.         happy = happy->next;
    
74.     }
    
75. }*/
    
76. 
    
77. void get_list(list **happy)         //生成链表及顶点
    
78. {
    
79.     list *temp, *tail;
    
80. 
    
81.     int A = 0;
    
82. 
    
83.     while(1)
    
84.     {
    
85.         scanf("%d", &A);
    
86.         if(A >= 0 && A <= 9)
    
87.         {
    
88.             temp = (list *)malloc(sizeof(list ));
    
89.             temp->data = A;
    
90.             temp->next = NULL;          //复制最后一个指针如没有数据赋值为NULL，这个赋值在first_list函数中会使用到
    
91. 
    
92.             if(*happy == NULL)
    
93.             {
    
94.                 *happy = temp;
    
95.             }
    
96.             else
    
97.             {
    
98.                 tail->next = temp;
    
99.             }
    
100.             tail = temp;
     
101. 
     
102.         }
     
103.         else
     
104.         {
     
105.             break;
     
106.         }
     
107. 
     
108.     }
     
109. }
     
110. 
     
111. int main()
     
112. {
     
113.     dack first[MAX];
     
114. 
     
115.     first[0].litte = 'A';
     
116.     first[1].litte = 'B';
     
117.     first[2].litte = 'C';
     
118.     first[3].litte = 'D';
     
119.     first[4].litte = 'E';
     
120.     first[5].litte = 'F';
     
121.     first[6].litte = 'G';
     
122.     first[7].litte = 'H';
     
123.     first[8].litte = 'I';
     
124. 
     
125. 
     
126.     for(int i = 0; i < MAX; i++)
     
127.     {
     
128.         first[i].happy = NULL;
     
129.         first[i].Blo = 0;
     
130.         get_list(&first[i].happy);
     
131.     }
     
132. 
     
133. 
     
134.     loop_list(first);       //传入的数据为first[0].happy的指针
     
135. 
     
136.     for(int i = 0; i < MAX; i++)
     
137.     {
     
138.         free_list(first[i].happy);
     
139.     }
     
140. 
     
141.     /* for(int i = 0; i < MAX; i++)
     
142.     {
     
143.         printf("%c", first[i].litte);
     
144.         print_list(first[i].happy);
     
145.         putchar('\n');
     
146.     }*/
     
147. 
     
148. 
     
149.     return 0;
     
150. }
     

复制代码

输入输出结果：




print_list函数输入输出结果：


备注：用于印证广度遍历输出

zhangjinxuan

This word is NB!