[ACES] 3rd week - Graph

사용되는 자료구조

 - Graph

 - Linked List

 - Queue

파일:

ADT_llist.c        ADT_llist.h

ADT_graph.c    ADT_graph.h

ADT_queue.c    ADT_queue.h

문제 - bfs를 풀기 위한 파일들

ADT_graph_bfs.c     main.c

모든 파일들을 손쉽게 엮어줄 Makefile

ADT_llist.h

#ifndef ADT_LLIST
#define ADT_LLIST
 
#include <stdio.h>
#include <stdlib.h>
 
//typedef int bool;
#define true 1
#define false 0
 
// List Node
typedef struct node {
    void* data_ptr;
    struct node* next;
} NODE;
 
// List
typedef struct {
    int count;
    NODE* front;
    NODE* rear;
    NODE* pos;
    int (*cmp_func)(void* x, void* y);
    void (*print_func)(void* x);
} LLIST;
 
//Operations
LLIST* create_list( int (*cmp_func)(void* x, void* y),
    void (*print_func)(void* x));
bool add_node_at(LLIST* list, unsigned int index, void* data);
bool del_node_at(LLIST* list, unsigned int index);
void* get_data_at(LLIST* list, unsigned int index);
int find_data(LLIST* list, void* search_data);
LLIST* copy_list(LLIST* list);
void print_all(LLIST* list, NODE* from_front);
void destroy_list(LLIST* list);
 
#endif
 
 

ADT_llist.c

#include "ADT_llist.h"
 
LLIST* create_list(
    int (*cmp_func)(void* x, void* y),
    void (*print_func)(void* x)) {
    LLIST* list;
    list = (LLIST*)malloc(sizeof(LLIST));
    if(list) {
        list->front = NULL;
        list->rear = NULL;
        list->pos = NULL;
        list->cmp_func = cmp_func;
        list->print_func = print_func;
        list->count = 0;
    }
    return list;
}
void destroy_list(LLIST* list) {
    while(list->count != 0) {
        del_node_at(list, 0);
        //printf("deleting node... %d rest...\n", list->count);
    }
    free(list);
    //printf("deleted list!\n");
}
 
 
bool add_node_at(
    LLIST* list, unsigned int index,
    void* data) {
    if((list == NULL) || (index > list->count))
        return false;
 
    NODE* new_p;
    new_p = (NODE*)malloc(sizeof(NODE));
    if(!new_p) return false;
 
    new_p->data_ptr = data;
    new_p->next = NULL;
 
    if(list->count == 0) {
        list->front = new_p;
        list->rear = new_p;
        (list->count)++;
                               
    int iter_i = 0;
    if(index == 0) {
        new_p->next = list->front;
        list->front = new_p;
        (list->count)++;
        return true;
    }
 
    iter_i++;
    list->pos = list->front;
    while(iter_i != index) {
        list->pos = list->pos->next;
        iter_i++;
    }
 
    if(iter_i == list->count) {
        list->rear->next = new_p;
        list->rear = new_p;
        (list->count)++;
        return true;
    }
 
    else {
        new_p->next = list->pos->next;
        list->pos->next = new_p;
        (list->count)++;
        return true;
    }
}
 
bool del_node_at(
    LLIST* list, unsigned int index) {
    if((list == NULL) || (index >= list->count))
        return false;
 
    if(list->count == 1) {
        free(list->front);
        list->front = NULL;
        list->rear = NULL;
        list->count = 0;
        return true;
    }
 
    int iter_i = 0;
    list->pos = list->front;
    NODE* pre = NULL;
    while(iter_i != index) {
        pre = list->pos;
        list->pos = list->pos->next;
        iter_i++;
    }
 
    if(index == 0) {
        list->front = list->pos->next;
        free(list->pos);
        list->pos = NULL;
        (list->count)--;
        return true;
    }
 
    if(index == (list->count - 1)) {
        list->rear = pre;
        pre->next = NULL;
        free(list->pos);
        list->pos = NULL;
        (list->count)--;
        return true;
    }
 
    else {
        pre->next = list->pos->next;
        free(list->pos);
        list->pos = NULL;
        (list->count)--;
        return true;
    }
 
    return false;
}
 
void* get_data_at(
    LLIST* list, unsigned int index) {
    if((list == NULL) || (index >= list->count))
        return NULL;
    list->pos = list->front;
    int iter_i=0;
    while(list->pos !=NULL) {
        if(iter_i == index)
            return list->pos->data_ptr;
        list->pos = list->pos->next;
        iter_i++;
    }
    return NULL;
}
 
int find_data(LLIST* list, void* search_data) {
    list->pos = list->front;
    int cmp_result;
    int iter_i=0;
    while(list->pos != NULL) {
        cmp_result = (*(list->cmp_func))(list->pos->data_ptr, search_data);
        if(cmp_result == 0)
            return iter_i;
        list->pos = list->pos->next;
        iter_i++;
    }
    return -1;
}
 
 
LLIST* copy_list(LLIST* list) {
    LLIST* copied_list;
    copied_list = create_list(list->cmp_func, list->print_func);
    if(copied_list) {
        int iter_i = 0;
        while(iter_i != list->count) {
            add_node_at(copied_list, iter_i,
           get_data_at(list, iter_i));
            iter_i++;
        }
    }
    return copied_list;
}
 
void print_all(LLIST* list, NODE* from_front) {
    NODE* pos = from_front;
    while(pos != NULL) {
        (*(list->print_func))(pos->data_ptr);
        pos = pos->next;
    }
}
 
 

ADT_graph.h

ADT_graph.c

ADT_queue.h

#ifndef ADT_QUEUE
#define ADT_QUEUE
 
#include <stdio.h>
#include <stdlib.h>
 
/*
typedef int bool;
#define true 1
#define false 0
*/
 
/* ==== Queue Node ==== */
 
#ifndef ADT_LLIST
typedef struct node {
    void *data_ptr;
    struct node *next;
} QUEUE_NODE;
#endif
 
#ifdef ADT_LLIST
typedef struct qnode {
    void *data_ptr;
    struct node *next;
} QUEUE_NODE;
#endif
 
/* ==== Queue ==== */
typedef struct queue{
    int count;
    QUEUE_NODE *front;
    QUEUE_NODE *rear;
} QUEUE;
 
 
/* ==== define function ==== */
QUEUE* create_queue();
bool enqueue (QUEUE *queue, void *in);
void *dequeue (QUEUE *queue);
 
void *queue_hook_front (QUEUE *queue);
void *queue_hook_rear (QUEUE *queue);
void destroy_queue (QUEUE *queue);
 
#endif
 

ADT_queue.c

ADT_graph_bfx