图的遍历-深度优先

奥普瓯江

原理：



备注：



代码：

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], int Blo[MAX], int i);
    
21. void loop_list(dack OK[MAX], list *temp);
    
22. void free_list(list *temp);
    
23. 
    
24. void free_list(list *temp)      //释放
    
25. {
    
26.     if(!temp)
    
27.     {
    
28.         return;
    
29.     }
    
30.     free_list(temp->next);
    
31.     free(temp);
    
32. }
    
33. 
    
34. void loop_list(dack OK[MAX], list *temp)        //图的深度优先遍历
    
35. {
    
36.     if(temp == NULL)                            //递归结束条件，temp传入的时候是存在数据的只有当便利到本链表最后一个的时候才会等于NULL这个是在get_list函数中以赋值NULL
    
37.     {
    
38.         return;
    
39.     }
    
40. 
    
41.    loop_list(OK, temp->next);                   //将所有链表传入到递归栈中
    
42. 
    
43.    if(OK[temp->data].Blo != 1)                  //如果OK数组中的Blo子项被赋予了1这个值那么就表明这个顶点已被读取过,及不执行该语句
    
44.    {
    
45.        printf("%c", OK[temp->data].litte);
    
46.        OK[temp->data].Blo = 1;
    
47.        loop_list(OK,OK[temp->data].happy);      //这条很重要，当执行了上面if语句也就是说ok[temp->data].litte顶点以经被读取并已经赋值，那就需要从新把赋值成功的这个顶点以及后面的链表地址传入循环
    
48.    }
    
49.    //如果没有执行if语句及说明这个链表中的数字顶点以被执行过及自动回弹不执行任何操作
    
50. 
    
51.     /*list *temp;
    
52. 
    
53.     if(Blo[i] == 1)
    
54.     {
    
55.         return;
    
56.     }
    
57.     printf("%c", OK[i].litte);
    
58.     Blo[i] = 1;
    
59. 
    
60.     loop_list(OK, Blo, i = OK[i].happy->data);
    
61. 
    
62.     temp = OK[i].happy;
    
63. 
    
64.     while(Blo[i] == 1)
    
65.     {
    
66.         temp = temp->next;
    
67.         if(temp != NULL)
    
68.         {
    
69.             i = temp->data;
    
70.         }
    
71.         else
    
72.         {
    
73.             break;
    
74.         }
    
75.     }
    
76. 
    
77.     loop_list(OK, Blo, i);*/
    
78. }
    
79. void print_list(list *happy)        //打印输出
    
80. {
    
81.     while(happy)
    
82.     {
    
83.         printf("%3d", happy->data);
    
84.         happy = happy->next;
    
85.     }
    
86. }
    
87. void get_list(list **happy)         //生成链表及顶点
    
88. {
    
89.     list *temp, *tail;
    
90. 
    
91.     int A = 0;
    
92. 
    
93.     while(1)
    
94.     {
    
95.         scanf("%d", &A);
    
96.         if(A >= 0 && A <= 9)
    
97.         {
    
98.             temp = (list *)malloc(sizeof(list ));
    
99.             temp->data = A;
    
100.             temp->next = NULL;          //复制最后一个指针如没有数据赋值为NULL，这个赋值在first_list函数中会使用到
     
101. 
     
102.             if(*happy == NULL)
     
103.             {
     
104.                 *happy = temp;
     
105.             }
     
106.             else
     
107.             {
     
108.                 tail->next = temp;
     
109.             }
     
110.             tail = temp;
     
111. 
     
112.         }
     
113.         else
     
114.         {
     
115.             break;
     
116.         }
     
117. 
     
118.     }
     
119. }
     
120. 
     
121. int main()
     
122. {
     
123.     dack first[MAX];
     
124.     //int Blo[MAX] = {0, 0, 0, 0, 0, 0, 0, 0, 0};
     
125. 
     
126.     first[0].litte = 'A';
     
127.     first[1].litte = 'B';
     
128.     first[2].litte = 'C';
     
129.     first[3].litte = 'D';
     
130.     first[4].litte = 'E';
     
131.     first[5].litte = 'F';
     
132.     first[6].litte = 'G';
     
133.     first[7].litte = 'H';
     
134.     first[8].litte = 'I';
     
135. 
     
136. 
     
137.     for(int i = 0; i < MAX; i++)
     
138.     {
     
139.         first[i].happy = NULL;
     
140.         first[i].Blo = 0;
     
141.         get_list(&first[i].happy);
     
142.     }
     
143. 
     
144. 
     
145.     loop_list(first, first[0].happy);       //传入的数据为first[0].happy的指针
     
146. 
     
147.     for(int i = 0; i < MAX; i++)
     
148.     {
     
149.         free_list(first[i].happy);
     
150.     }
     
151. 
     
152. 
     
153.    /* for(int i = 0; i < MAX; i++)
     
154.     {
     
155.         printf("%c", first[i].litte);
     
156.         print_list(first[i].happy);
     
157.         putchar('\n');
     
158.     }*/
     
159. 
     
160. 
     
161.     return 0;
     
162. }
     

复制代码

输入输出结果：