DataStructure] C언어로 쉽게 풀어쓴 자료구조 8장 - 3

DataStructure] C언어로 쉽게 풀어쓴 자료구조 8장 - 3

C언어로 쉽게 풀어쓴 자료구조

8장 Exercise 문제다.

필자가 학교 다니면서 자료구조론 수업을 들었는데,

과제로 제출했던 것들이고,

난항을 겪고 있는 사람들에게 참고가 되었으면 하는 마음으로 올린다.

자고로, 버그가 존재할 수 있으니 디버깅 작업은 필수다.

18. 앞에서 공부한 리스트 추상 자료형을 사용하여 우선순위 큐 추상 자료형을 구현하여보라.

리스트 추상 자료형의 각종 연산들을 사용하라.

삽입 연산은 O(1)의 시간 안에, 삭제 연산은 O(n)만큼의 시간이 걸리게끔 구현하라.

여기서 n은 큐 안에 있는 요소들의 개수이다.

<SLinkedList.h>

#ifndef __S_LINKED_LIST_H__
#define __S_LINKED_LIST_H__
 
typedef int element;
typedef struct ListNode    {
    element data;
    struct ListNode *link;
}ListNode;
 
typedef struct{
    ListNode *head;
    int size;
}List;
 
void insert_node(ListNode **phead, ListNode *p, ListNode *new_node);
void remove_node(ListNode **phead, ListNode *p, ListNode *new_node);
 
void Init(List *list);
ListNode *get_node(List *list, int pos);
 
void error(char *message);
 
void add(List *list, element data);
 
int empty(List *list);
 
void delete_node(List *list, int pos);
 
ListNode *creat_node(element data, ListNode *link);
 
#endif

<SLinkedList.cpp>

#include <stdio.h>
#include <stdlib.h>
#include "SLinkedList.h"
 
// phead : head pointer's pointer
// p : previous node(insert next this node)
// new_node : inserting node
void insert_node(ListNode **phead, ListNode *p, ListNode *new_node)
{
    if (*phead == NULL)
    {
        new_node->link = NULL;
        *phead = new_node;
    }
    else if (p == NULL)
    {
        new_node->link = *phead;
        *phead = new_node;
    }
    else
    {
        new_node->link = p->link;
        p->link = new_node;
    }
}
 
// phead : head pointer's pointer
// p : previous node(remove next this node)
// removed : removing node
void remove_node(ListNode **phead, ListNode *p, ListNode *removed)
{
    if (p == NULL)
        *phead = (*phead)->link;
    else
        p->link = removed->link;
    free(removed);
}
 
// Initialize List
void Init(List *list)
{
    if (list == NULL)
        return;
    list->size = 0;
    list->head = NULL;
}
 
// Return node that correspond pos
ListNode *get_node(List *list, int pos)
{
    int i;
    ListNode *tmp = list->head;
    if (pos < 0)
        return NULL;
    for (i = 0; i < pos; i++)
        tmp = tmp->link;
    return tmp;
}
 
// Print error message
void error(char *message)
{
    fprintf(stderr, "%s\n", message);
    exit(1);
}
 
// Insert data that correspond pos
void add(List *list, element data)
{
    ListNode *p;
    int pos = 0;
    ListNode *node = (ListNode*)malloc(sizeof(ListNode));
    node->data = data;
    p = get_node(list, pos - 1);
    insert_node(&(list->head), p, node);
    list->size++;
}
 
// list empty? (Empty : T, not : F)
int empty(List *list)
{
    return list->head == NULL;
}
 
// Delete node that correspond pos
void delete_node(List *list, int pos)
{
    if (!empty(list) && pos >= 0 && pos < list->size)
    {
        ListNode *p = get_node(list, pos-1);
        remove_node(&(list->head), p, (p != NULL) ? p->link : NULL);
        list->size--;
    }
}
 
// Allocate Node
ListNode *creat_node(element data, ListNode *link)
{
    ListNode *new_node;
    new_node = (ListNode*)malloc(sizeof(ListNode));
    new_node->data = data;
    new_node->link = link;
    return new_node;
}

<ListBasePQ.h>

#ifndef __LIST_BASE_PQ_H__
#define __LIST_BASE_PQ_H__
#include "SLinkedList.h"
 
typedef List PriorityQueue;
 
void InitPQ(PriorityQueue* pq);
 
int IsEmptyPQ(PriorityQueue* pq);
int IsFullPQ(PriorityQueue* pq);
 
void InsertElement(PriorityQueue* pq, element x);
element DeleteTopPriority(PriorityQueue* pq);
element FindTopPriority(PriorityQueue* pq);
 
void PrintQueue(PriorityQueue* pq);
 
#endif

<ListBasePQ.cpp>

#include <stdio.h>
#include <stdlib.h>
#include "ListBasePQ.h"
#include "SLinkedList.h"
 
#define ELEMENTMAX 200;
 
void InitPQ(PriorityQueue* pq)
{
    Init(pq);
}
 
int IsEmptyPQ(PriorityQueue* pq)
{
    return empty(pq);
}
int IsFullPQ(PriorityQueue* pq)
{
    return pq->size == ELEMENTMAX;
}
 
void InsertElement(PriorityQueue* pq, element x)
{
    add(pq, x);
}
element DeleteTopPriority(PriorityQueue* pq)
{
    ListNode* p = pq->head;
    int max = p->data;
    int pos = 0;
    int maxpos = 0;
 
    while (p != NULL)
    {
        if (max < p->data)
        {
            max = p->data;
            maxpos = pos;
        }
        pos++;
        p = p->link;
    }
    delete_node(pq, maxpos);
    return max;
}
element FindTopPriority(PriorityQueue* pq)
{
    ListNode* p = pq->head;
    int max = p->data;
 
    while (p != NULL)
    {
        if (max < p->data)
            max = p->data;
        p = p->link;
    }
    return max;
}
 
void PrintQueue(PriorityQueue* pq)
{
    ListNode* p = pq->head;
 
    printf("<우선순위 큐 내부>\n");
    printf("(  ");
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->link;
    }
    printf(" )\n");
}

<main.cpp>

#include <stdio.h>
#include "ListBasePQ.h"
int main()
{
    PriorityQueue queue;
 
    Init(&queue);
 
    InsertElement(&queue, 210);
    InsertElement(&queue, 40);
    InsertElement(&queue, 30);
    InsertElement(&queue, 5);
    InsertElement(&queue, 12);
    InsertElement(&queue, 6);
    InsertElement(&queue, 115);
    InsertElement(&queue, 9);
    InsertElement(&queue, 100);
 
    printf("<<Linked List ADT를 이용한 최대 우선 순위 큐 구현>>\n\n");
    PrintQueue(&queue);
    printf("\n최우선 순위 값 탐색 및 삭제 : %d\n\n", DeleteTopPriority(&queue));
    PrintQueue(&queue);
    printf("\n최우선 순위 값 탐색 결과 : %d\n", FindTopPriority(&queue));
}