너비 우선 탐색 프로그램

트리가 주어질 때, 너비 우선탐색을 실시하는 프로그램
중복된 노드는 탐색하지 않음.
연결리스트, 큐를 사용하여 구현함

/*너비 우선 탐색 프로그램*/

#include <stdio.h>
#include <stdlib.h>

#define LIMITL 256
#define GOAL 999
#define OPENLIST 0
#define CLOSEDLIST 1

typedef struct node {
int id;
int pid;
struct node* nextNode;
}node, *pnode;

struct queue {
pnode head, tail;
int numOfNode;
}openList, closedList;

int tree1[][5] = { {1,2,3,5}, {2,4}, {3,6,7}, {5,4,8}, {6,5,7}, {8,7,999}, {0} };

pnode popQueue(int listNum){

pnode removedNode;
struct queue* targetList;

if(listNum == OPENLIST) targetList = &openList;
else if(listNum == CLOSEDLIST) targetList = &closedList;

if(targetList->numOfNode == 0) return NULL;

removedNode = targetList->head;
targetList->head = targetList->head->nextNode;
targetList->numOfNode--;

return removedNode;
}

void pushQueue(int listNum, pnode newNode){

struct queue* targetList;

if(listNum == OPENLIST) targetList = &openList;
else if(listNum == CLOSEDLIST) targetList = &closedList;

if (targetList->numOfNode == 0) {
targetList->head = newNode;
targetList->tail = newNode;
}
else {
targetList->tail->nextNode = newNode;
targetList->tail = newNode;
}
targetList->numOfNode++;
return ;
}

void initializeQueue(int listNum){

struct queue* targetList;

if(listNum == OPENLIST) targetList = &openList;
else if(listNum == CLOSEDLIST) targetList = &closedList;

targetList->numOfNode = 0;
targetList->head = NULL;
targetList->tail = NULL;

return ;
}

pnode toNode(int parentId, int id){

pnode newNode = (pnode)malloc(sizeof(node));
newNode->id = id;
newNode->pid = parentId;

return newNode;
}

int isInTheList(int listNum, int target){

int i = 0;
struct queue* targetList;
pnode temp;


if(listNum == OPENLIST) targetList = &openList;
else if(listNum == CLOSEDLIST) targetList = &closedList;

if(targetList->numOfNode == 0) return -1;

temp = targetList->head;

while(i < targetList->numOfNode){
if(temp->id == target) return 1;
i++;
temp = temp->nextNode;
}

return 0;
}
int main(){

int i = 0,j = 0,k;
pnode p,q;

initializeQueue(OPENLIST);
initializeQueue(CLOSEDLIST);

pushQueue(OPENLIST, toNode(tree1[0][0],tree1[0][0]));

do{
q = openList.head;
printf("\nopen list  :");
for (k = 0; k < openList.numOfNode; k++) {
printf(" %d,", q->id);
q = q->nextNode;
}

q = closedList.head;
printf("\nclosed list:");

for (k = 0; k < closedList.numOfNode; k++) {
printf(" %d,", q->id);
q = q->nextNode;
}

p = popQueue(OPENLIST);
if(p == NULL) break;
pushQueue(CLOSEDLIST, p);

i = 0;

while(tree1[i][0] != 0){
if(tree1[i][0] == p->id){
for(j=0; tree1[i][j] != 0; j++){
if(isInTheList(OPENLIST,tree1[i][j])== 1 ||isInTheList(CLOSEDLIST,tree1[i][j])== 1) continue;
pushQueue(OPENLIST, toNode(tree1[i][0],tree1[i][j]));
}
}
i++;
}
}while(1);

}