图的遍历-广度优先
本帖最后由 奥普瓯江 于 2022-9-11 17:01 编辑原理：
备注：
代码：
#include <stdio.h>
#include <stdlib.h>
#define MAX 9
typedef struct list
{
int data;
struct list *next;
}list, *lists;
typedef struct dack
{
char litte;
int Blo;
list *happy;
}dack;
void get_list(list **happy);
//void print_list(list *happy);
void loop_list(dack OK);
void free_list(list *temp);
void free_list(list *temp) //释放
{
if(!temp)
{
return;
}
free_list(temp->next);
free(temp);
}
void loop_list(dack OK) //广度优先遍历
{
list *temp; //临时变量
int i, S = 0;
for(int j = 0; j < MAX; j++) //遍历每一个节点A-I
{
temp = OK.happy; //把赋予temp初始变量，这个初始变量是每个节点的初始变量A的初始变狼B的初始变量等等
i = j;
while(1) //循环每个节点后的变量
{
if(OK.Blo != 1) //如果这个节点被打印过就不对该几点进行执行输出
{
printf("%c", OK.litte);
OK.Blo = 1; //标记该节点证明其被输出过
S++;
if(S > MAX) //减少遍历次数，如果前几个节点已经全部遍历完整个图及结束函数，后面的节点就不用遍历了
{
return;
}
}
if(temp == NULL) //如果该节点以执行到最后空的位置及跳出while循环
{
break;
}
else
{
i = temp->data; //未执行到连边最后的位置则将该位置链表所包含的数据传给i使得其继续循环
}
temp = temp->next; //链表向后循环
}
}
}
/*void print_list(list *happy) //打印输出
{
while(happy)
{
printf("%3d", happy->data);
happy = happy->next;
}
}*/
void get_list(list **happy) //生成链表及顶点
{
list *temp, *tail;
int A = 0;
while(1)
{
scanf("%d", &A);
if(A >= 0 && A <= 9)
{
temp = (list *)malloc(sizeof(list ));
temp->data = A;
temp->next = NULL; //复制最后一个指针如没有数据赋值为NULL，这个赋值在first_list函数中会使用到
if(*happy == NULL)
{
*happy = temp;
}
else
{
tail->next = temp;
}
tail = temp;
}
else
{
break;
}
}
}
int main()
{
dack first;
first.litte = 'A';
first.litte = 'B';
first.litte = 'C';
first.litte = 'D';
first.litte = 'E';
first.litte = 'F';
first.litte = 'G';
first.litte = 'H';
first.litte = 'I';
for(int i = 0; i < MAX; i++)
{
first.happy = NULL;
first.Blo = 0;
get_list(&first.happy);
}
loop_list(first); //传入的数据为first.happy的指针
for(int i = 0; i < MAX; i++)
{
free_list(first.happy);
}
/* for(int i = 0; i < MAX; i++)
{
printf("%c", first.litte);
print_list(first.happy);
putchar('\n');
}*/
return 0;
}
输入输出结果：
print_list函数输入输出结果：
备注：用于印证广度遍历输出
This word is NB!
页:
[1]