데이터 구조의 대기 열의 실현

2 단 링크 를 이용 하여 대기 열의 기본 조작 을 실현 하 다.
대기 열의 구조 체 및 인터페이스:
#ifndef _QUEUE_H_
#define _QUEUE_H_

#include "dlist.h"

typedef struct Queue{
    Dlist *dlist;
}Queue;

Queue *init_queue(void);  //      
void destroy_queue(Queue **queue);  //     
Boolean is_empty(Queue *queue);
Boolean input(Queue *queue, void *value);
Boolean output(Queue *queue);
Boolean get_queue_front(Queue *queue, void **value);
int  get_count(Queue *queue);


#endif

대기 열의 인터페이스 구현:
#include <stdlib.h>
#include <stdio.h>
#include <strings.h>
#include "queue.h"


Queue *init_queue(void)  //      
{
    Queue *queue = NULL;

    queue = (Queue *)Malloc(sizeof(Queue));
    queue->dlist = init_dlist();

    return queue;
}

void destroy_queue(Queue **queue)  //     
{
    if(queue == NULL || *queue == NULL){
        return ;
    }

    destroy_dlist(&(*queue)->dlist);
    free(*queue);
    *queue = NULL;
}

Boolean is_empty(Queue *queue)
{
    return get_dlist_count(queue->dlist) == ZERO;
}

Boolean input(Queue *queue, void *value)
{
    if(queue == NULL || value == NULL){
        return FALSE;
    }

    return push_back(queue->dlist, value);
}
Boolean output(Queue *queue)
{
    if(queue == NULL){
        return FALSE;
    }

    return pop_front(queue->dlist);
}

Boolean get_queue_front(Queue *queue, void **value)
{
    if(!is_empty(queue) && value != NULL){
        return get_front(queue->dlist, value);
    }

    return FALSE;
}
int  get_count(Queue *queue)
{
    if(queue == NULL){
        return -1;
    }

    return get_dlist_count(queue->dlist);
}


대기 열 에 필요 한 패키지 함수 설명:
#ifndef _TOOLS_H_
#define _TOOLS_H_

//      
#define TRUE (1)
#define FALSE (0)

typedef unsigned char Boolean;

//    
void *Malloc(size_t size);

#endif

대기 열 에 필요 한 패키지 함수 구현:
#include <stdio.h>
#include <stdlib.h>
#include "tools.h"

void *Malloc(size_t size)
{
    void *result = malloc(size);
    if(result == NULL){
        fprintf(stderr, "the memory is full!
"
); exit(1); } return result; }

대기 열 의존 을 실현 하 는 쌍 단 링크 의 성명:
#ifndef _DLIST_H_
#define _DLIST_H_
#include "tools.h"

#define TRUE (1)
#define FALSE (0)
#define ZERO (0)
#define ONE (1)

typedef void (*Print_func)(void *value);   //    

//      
typedef struct Dlist_node{
    struct Dlist_node *prev;  //  
    struct Dlist_node *next;  //  
    void              *data;  //           (       )
}Dlist_node;

//      
typedef struct Dlist{
    struct Dlist_node *head; //   
    struct Dlist_node *tail; //   
    int               count; //  

    //data          
    void (*free)(void *ptr); //         (    )
    //data          
    Boolean (*match)(void *value1, void *value2);
    //data          
    void *(*copy_node)(void *value);
}Dlist;

//         
Dlist   *init_dlist(void)                                       ;  //       
void    destroy_dlist(Dlist **dlist)                            ;  //       
Boolean push_front(Dlist *dlist, void *value)                   ;  //    
Boolean push_back(Dlist *dlist, void *value)                    ;  //    
Boolean pop_front(Dlist *dlist)                                 ;  //    
Boolean pop_back(Dlist *dlist)                                  ;  //    

Dlist_node *find_node(Dlist *dlist, void *value)                ;
Boolean insert_prev(Dlist *dlist, Dlist_node *node, void *value);  //         
Boolean insert_next(Dlist *dlist, Dlist_node *node, void *value);  //         
Boolean remove_dlist_node(Dlist *dlist, Dlist_node *node)       ;  //      
void    print_dlist(Dlist *dlist, Print_func print)             ;  //     
Boolean get_front(Dlist *dlist, void **value)                   ;  //      data
//Boolean get_front(Dlist *dlist, void *value) ; //      data
Boolean get_tail(Dlist *dlist, void **value)                     ;  //      data
int     get_dlist_count(Dlist *dlist)                           ;   //       


#endif

대기 열 이 사용 하 는 링크 의 인터페이스 구현:
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
#include "dlist.h"


Dlist   *init_dlist(void)                                         //       
{
    Dlist *dlist = NULL;

    dlist = (Dlist *)Malloc(sizeof(Dlist));
    bzero(dlist, sizeof(Dlist));

    return dlist;
}

void    destroy_dlist(Dlist **dlist)                              //       
{
    Dlist_node *p_node = NULL;

    if(dlist == NULL || *dlist == NULL){
        return ;
    }

#if 0
    p_node = (*dlist)->head;

    while((*dlist)->head != NULL){
        (*dlist)->head = p_node->next;
        if((*dlist)->free != NULL){
            (*dlist)->free(p_node->data);
        }
        free(p_node);
        p_node = (*dlist)->head;
    }
#endif

    while((*dlist)->count){
        pop_front(*dlist);
    }
    free(*dlist);
    *dlist = NULL;
}

static Dlist_node *create_node(void);   //      
static Dlist_node *create_node(void)
{
    Dlist_node *result = NULL;

    result = (Dlist_node *)Malloc(sizeof(Dlist_node));
    bzero(result, sizeof(Dlist_node));

    return result;
}

Boolean push_front(Dlist *dlist, void *value)                     //    
{
    //*value       
    Dlist_node *p_node = NULL;

    if(dlist == NULL || value == NULL){
        return FALSE;
    }

    //      
    p_node = create_node();
    p_node->data = value;

    if(dlist->count == ZERO){     //      
        dlist->head = dlist->tail = p_node;
    }else{      //      
        p_node->next = dlist->head;
        dlist->head->prev = p_node;
        dlist->head = p_node;
    }

    dlist->count++;
    return TRUE;
}

Boolean push_back(Dlist *dlist, void *value)                      //    
{
    Dlist_node *p_node = NULL;

    if(dlist == NULL || value == NULL){
        p_node->prev = dlist->tail;
        return FALSE;
    }

    p_node = create_node();
    p_node->data = value;

    if(dlist->count == ZERO){     //      
        dlist->head = dlist->tail = p_node;
    }else{    //      
        dlist->tail->next = p_node;
        p_node->prev = dlist->tail;
        dlist->tail = p_node;
    }

    dlist->count++;
    return TRUE;
}

Boolean pop_front(Dlist *dlist)                                   //    
{
    Dlist_node *p_node = NULL; 

    if(dlist == NULL || dlist->count == ZERO){
        return FALSE;
    }

    p_node = dlist->head;

    if(dlist->count == ONE){
        dlist->head = dlist->tail = NULL;
    }else{
        dlist->head = p_node->next;
        dlist->head->prev = NULL;
    }

    //    ,  free     (data       )
    if(dlist->free != NULL){   //  (   free  )
        dlist->free(p_node->data);
    }

    free(p_node);   //  
    dlist->count--;
    return TRUE;
}

Boolean pop_back(Dlist *dlist)                                    //    
{
    Dlist_node *p_node = NULL;

    if(dlist == NULL || dlist->count == ZERO){
        return FALSE;
    }

    p_node = dlist->tail;

    if(dlist->count == ONE){   //      
        dlist->head = dlist->tail = NULL;
    }else{    //    
        dlist->tail = p_node->prev;
        dlist->tail->next = NULL;
    }

    if(dlist->free != NULL){
        dlist->free(p_node->data);
    }

    free(p_node);
    dlist->count--;

    return TRUE;
}

Dlist_node *find_node(Dlist *dlist, void *value)
{
    Dlist_node *p_node = NULL;

    if(dlist == NULL || value == NULL){
        return NULL;
    }

#if 0
    for(p_node = dlist->head; p_node; p_node = p_node->next){
        if(dlist->match){     //        
            if(!dlist->match(p_node->data, value)){
                return p_node;
            }
        }else{
            if(p_node->data == value){
                return p_node;
            }
        }
    }
#endif

    if(dlist->match){
        for(p_node = dlist->head; p_node; p_node = p_node->next){
            if(!dlist->match(p_node->data, value)){
                return p_node;
            }
        }
    }else{ 
        for(p_node = dlist->head; p_node; p_node = p_node->next){
            if(p_node->data == value){
                return p_node;
            }
        }
    }

    return p_node;
}

Boolean insert_prev(Dlist *dlist, Dlist_node *node, void *value)  //         
{
    Dlist_node *p_node = NULL;

    if(dlist == NULL || node == NULL || value == NULL){
        return FALSE;
    }

    p_node = create_node();
    p_node->data = value;

    p_node->next = node;
    p_node->prev = node->prev;

    if(node->prev == NULL){
        dlist->head = p_node;
    }else{
        node->prev->next = p_node;
    }

    node->prev = p_node;
    dlist->count++;

    return TRUE;
}

Boolean insert_next(Dlist *dlist, Dlist_node *node, void *value)  //         
{
    Dlist_node *p_node = NULL;

    if(dlist == NULL || node == NULL || value == NULL){
        return FALSE;
    }

    p_node = create_node();
    p_node->data = value;

    p_node->prev = node;
    p_node->next = node->next;

    if(node->next == NULL){
        dlist->tail = p_node;
    }else{
        node->next->prev = p_node;
    }

    node->next = p_node;
    dlist->count++;

    return TRUE;
}

Boolean remove_dlist_node(Dlist *dlist, Dlist_node *node)         //      
{   //        1.  2.  3.   
    if(dlist == NULL || node == NULL ){
        return FALSE;
    }

    if(node->next == NULL){   //  
        pop_back(dlist);
    }else if(node->prev == NULL){  //  
        pop_front(dlist);
    }else{   //   
        node->prev->next = node->next;
        node->next->prev = node->prev;

        if(dlist->free != NULL){
            dlist->free(node->data);
        }
        free(node);
        dlist->count--;
    }

    return TRUE;
}

void    print_dlist(Dlist *dlist, Print_func print)               //     
{
    Dlist_node *p_node = NULL;   

    if(dlist == NULL || print == NULL || dlist->count == ZERO){
        return ;
    }

    p_node = dlist->head;

    while(p_node){
        print(p_node->data);    //print           
        p_node = p_node->next;
    }

    printf("
"
); } Boolean get_front(Dlist *dlist, void **value) // data { if(dlist == NULL || value == NULL || dlist->count == ZERO){ return FALSE; } *value = dlist->head->data; return TRUE; } //Boolean get_front(Dlist *dlist, void *value) // data Boolean get_tail(Dlist *dlist, void **value) // data { if(dlist == NULL || dlist->count == ZERO || value == NULL){ return FALSE; } *value = dlist->tail->data; return TRUE; } int get_dlist_count(Dlist *dlist) // { if(dlist == NULL){ return -1; } return dlist->count; }

대기 열 에서 실 현 된 테스트 코드:
#include <stdlib.h>
#include <stdio.h>
#include "queue.h"
#include "tools.h"

int main(int ac, char **av)
{
    Queue *queue = NULL;
    int array[] = {21, 34, 56, 65, 76, 74, 78};
    int  i = 0;
    int arr_len = sizeof(array) / sizeof(array[0]);
    void *value = NULL;

    queue = init_queue();
    for(i = 0; i < arr_len; ++i){
        input(queue, &array[i]);
    }

    for(i = 0; i < arr_len; ++i){
        get_queue_front(queue, &value);
        output(queue);
        printf("%d ", *(int *)value);
    }
    printf("
"
); destroy_queue(&queue); return 0; }

대기 열 에서 실 현 된 테스트 결과:
[root@localhost queue_dlist]# ./queue 
21 34 56 65 76 74 78 
[3]+  Done                    gedit queue.* tools.* dlist.* main.c
[root@localhost queue_dlist]# 

좋은 웹페이지 즐겨찾기