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

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

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

8장 Exercise 문제다.

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

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

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

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

17. 연결 리스트(linked list)를 이용하여 우선순위 큐 추상 자료형의 각종 연산들을 구현하여보라.

<ListPQ.h>

#ifndef __LIST_PQ_H__
#define __LIST_PQ_H__
#define ELEMENT_MAX 200
 
typedef int element;
typedef struct ListNode {
    element data;
    struct ListNode* link;
} ListNode;
typedef struct {
    ListNode* head;
    int size;
} PriorityQueue;
 
void Init(PriorityQueue* pq);
 
int IsEmpty(PriorityQueue* pq);
int IsFull(PriorityQueue* pq);
 
void InsertElement(PriorityQueue* pq, element x);
element DeleteTopPriority(PriorityQueue* pq);
element FindTopPriority(PriorityQueue* pq);
 
void PrintQueue(PriorityQueue* pq);
 
#endif

<ListPQ.cpp>

#include <stdio.h>
#include <stdlib.h>
#include "ListPQ.h"
 
void Init(PriorityQueue* pq)
{
    if (pq == NULL)
        return;
    pq->size = 0;
    pq->head = NULL;
}
 
int IsEmpty(PriorityQueue* pq)
{
    return pq->head == NULL;
}
int IsFull(PriorityQueue* pq)
{
    return pq->size == ELEMENT_MAX;
}
 
void InsertElement(PriorityQueue* pq, element x)
{
    ListNode* newnode=(ListNode*)malloc(sizeof(ListNode));
    newnode->data = x;
    ListNode** phead = &(pq->head);
 
    if (phead == NULL)
    {
        newnode->link = NULL;
        *phead = newnode;
        pq->size++;
    }
    else
    {
        newnode->link = *phead;
        *phead = newnode;
        pq->size++;
    }
}
element DeleteTopPriority(PriorityQueue* pq)
{
    ListNode* cur = pq->head;
    ListNode* before = pq->head;
    ListNode* pmaxnode = NULL;
    ListNode* maxnode = cur;
    ListNode** phead = &(pq->head);
    element max = cur->data;
    cur = cur->link;
    while (cur != NULL)
    {
        if (max < cur->data)
        {
            max = cur->data;
            maxnode = cur;
            pmaxnode = before;
        }
        cur = cur->link;
        before = before->link;
    }
 
    if (pmaxnode == NULL)
        *phead = (*phead)->link;
    else
        pmaxnode->link = maxnode->link;
 
    free(maxnode);
    pq->size--;
    return max;
}
element FindTopPriority(PriorityQueue* pq)
{
    ListNode* p = pq->head;
    element max = p->data;
    while (p != NULL)
    {
        if (p->data > max)
            max = p->data;
        p = p->link;
    }
    return max;
}
 
void PrintQueue(PriorityQueue* pq)
{
    ListNode* p = pq->head;
    printf("(  ");
    for (int i = 0; i < pq->size; i++)
    {
        printf("%d ", p->data);
        p = p->link;
    }
    printf(" )\n");
}

<main.cpp>

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