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

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

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

8장 Exercise 문제다.

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

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

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

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

16. 정렬되지 않은 배열(array)를 이용하여 우선순위 큐 추상 자료형의 각종 연산들을 구현하여 보라.

<ArrayPQ.h>

#ifndef __ARRAY_PQ_H__
#define __ARRAY_PQ_H__
 
#define ELEMENT_MAX 200
 
typedef int element;
typedef struct {
    element Queue[ELEMENT_MAX];
    int size;
} PriorityQueue;
 
void Init(PriorityQueue* pq);
 
int IsEmpty(PriorityQueue* pq);
int IsFull(PriorityQueue* pq);
 
void InsertElement(PriorityQueue* pq, element item);
element DeleteTopPriority(PriorityQueue* pq);
element FindTopPriority(PriorityQueue* pq);
 
void PrintQueue(PriorityQueue* pq);
 
#endif

<ArrayPQ.cpp>

#include <stdio.h>
#include <stdlib.h>
#include "ArrayPQ.h"
 
void Init(PriorityQueue* pq)
{
    pq->size = 0;
}
 
int IsEmpty(PriorityQueue* pq)
{
    return pq->size == 0;
}
int IsFull(PriorityQueue* pq)
{
    return pq->size == ELEMENT_MAX - 1;
}
 
void InsertElement(PriorityQueue* pq, element item)
{
    if (IsFull(pq))
    {
        printf("Queue Memory Is Full!\n");
        return;
    }
    pq->Queue[pq->size++] = item;
}
element DeleteTopPriority(PriorityQueue* pq)
{
    if (IsEmpty(pq))
    {
        printf("Queue Memory Is Empty!\n");
        exit(-1);
    }
    int maxidx;
    element max = pq->Queue[0];
    maxidx = 0;
    for (int i = 1; i < pq->size; i++)
    {
        if (pq->Queue[i] > max)
        {
            max = pq->Queue[i];
            maxidx = i;
        }
    }
    pq->size--;
    for (int i = maxidx; i < pq->size; i++)
    {
        pq->Queue[i] = pq->Queue[i + 1];
    }
    return max;
}
element FindTopPriority(PriorityQueue* pq)
{
    if (IsEmpty(pq))
    {
        printf("Queue Memory Is Empty!\n");
        exit(-1);
    }
    element max = pq->Queue[0];
    for (int i = 1; i < pq->size; i++)
        if (pq->Queue[i] > max)
            max = pq->Queue[i];
    return max;
}
 
void PrintQueue(PriorityQueue* pq)
{
    if (IsEmpty(pq))
    {
        printf("Queue Memory Is Empty!\n");
        return;
    }
    printf("<우선 순위 큐>\n");
    for (int i = 0; i < pq->size; i++)
        printf("%d ", pq->Queue[i]);
    printf("\n\n");
}

<main.cpp>

#include <stdio.h>
#include "ArrayPQ.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("<<Array기반 최대 우선 순위 큐 구현>>\n\n");
    PrintQueue(&queue);
    printf("\n최우선 순위 값 탐색 및 삭제 : %d\n\n", DeleteTopPriority(&queue));
    PrintQueue(&queue);
    printf("\n최우선 순위 값 탐색 결과 : %d\n", FindTopPriority(&queue));
}