내 소식

오르비

태그

내 태그
입시
학습
생활
클럽
직업·취업
Epioptimus
Centurion
오르비 랭킹
XDK 누적 복권
XDK 경매
RARE

✨컴공주✨ [1052682] · MS 2021 · 쪽지

2022-11-09 22:06:41
조회수 2,120

컴공 일기201

게시글 주소: https://dev.orbi.kr/00059269553

오늘 공부했던 구조는 우선순위 큐. 순위를 인지하고 무엇을 먼저 큐에서 꺼낼 것이냐는 문젠데, 큐의 응용이라고 볼 수 있죠. 재미있는 구조입니다. 내가 우선적으로 꺼내고 싶은 것을 꺼낼 수 있으니까요. 대신 논리는 꽤 어려운 측면이 있습니다. 



PriorityQueue.h


#pragma once

#ifndef PRIORITYQUEUE_H

#define PRIORITYQUEUE_H


#include <stdio.h>

#include <memory.h>

#include <stdlib.h>


typedef struct tagPQNode

{

    int Priority;

    void* Data;

}PQNode;


typedef struct tagPriorityQueue

{

    PQNode* Nodes;

    int Capacity;

    int UsedSize;

}PriorityQueue;



PriorityQueue* PQ_Create(int InitialSize);

void           PQ_Destroy(PriorityQueue* PQ);

void           PQ_Enqueue(PriorityQueue* PQ, PQNode NewData);

void           PQ_Dequeue(PriorityQueue* PQ, PQNode* Root);

int            PQ_GetParent(int Index);

int            PQ_GetLeftChild(int Index);

void           PQ_SwapNodes(PriorityQueue* PQ, int index1, int index2);

int            PQ_IsEmpty(PriorityQueue* PQ);


#endif






PriorityQueue.c



#include "PriorityQueue.h"




PriorityQueue* PQ_Create(int InitialSize)

{

    PriorityQueue* NewPQ = (PriorityQueue*)malloc(sizeof(PriorityQueue));

    NewPQ->Capacity = InitialSize;

    NewPQ->UsedSize = 0;

    NewPQ->Nodes = (PQNode*)malloc(sizeof(PQNode) * NewPQ->Capacity);


    return NewPQ;

}


void PQ_Destroy(PriorityQueue* PQ)

{

    free(PQ->Nodes);

    free(PQ);

}


void PQ_Enqueue(PriorityQueue* PQ, PQNode NewNode)

{

    int CurrentPosition = PQ->UsedSize;

    int ParentPosition = PQ_GetParent(CurrentPosition);


    if (PQ->UsedSize == PQ->Capacity)

    {

        if (PQ->Capacity == 0)

            PQ->Capacity = 1;


        PQ->Capacity *= 2;

        PQ->Nodes = (PQNode*)realloc(PQ->Nodes, sizeof(PQNode) * PQ->Capacity);

    }


    PQ->Nodes[CurrentPosition] = NewNode;


    while (CurrentPosition > 0 && PQ->Nodes[CurrentPosition].Priority < PQ->Nodes[ParentPosition].Priority)

    {

        PQ_SwapNodes(PQ, CurrentPosition, ParentPosition);

        CurrentPosition = ParentPosition;

        ParentPosition = PQ_GetParent(CurrentPosition);

    }


    PQ->UsedSize++;

}


void PQ_SwapNodes(PriorityQueue* PQ, int Index1, int Index2)

{

    int CopySize = sizeof(PQNode);

    PQNode* Temp = (PQNode*)malloc(CopySize);


    memcpy(Temp, &PQ->Nodes[Index1], CopySize);

    memcpy(&PQ->Nodes[Index1], &PQ->Nodes[Index2], CopySize);

    memcpy(&PQ->Nodes[Index2], Temp, CopySize);


    free(Temp);

}



void PQ_Dequeue(PriorityQueue* PQ, PQNode* Root)

{

    int ParentPosition = 0;

    int LeftPosition = 0;

    int RightPosition = 0;


    memcpy(Root, &PQ->Nodes[0], sizeof(PQNode));

    memset(&PQ->Nodes[0], 0, sizeof(PQNode));


    PQ->UsedSize--;

    PQ_SwapNodes(PQ, 0, PQ->UsedSize);


    LeftPosition = PQ_GetLeftChild(0);

    RightPosition = LeftPosition + 1;


    while (1)

    {

        int SelectChild = 0;


        //반복문 탈출 조건 배열의 원소 다 살펴봤는데 UsedSize보다 커지면 종료

        if (LeftPosition >= PQ->UsedSize)

            break;



        //오른쪽 인덱스는 경계 밖인데, 왼쪽은 아직 경계 내일 수 있으므로 SelectChild = LeftPosition으로 

        if (RightPosition >= PQ->UsedSize)

        {

            SelectChild = LeftPosition;

        }


        //왼쪽과 오른쪽 모두 USEDSIZE 범위 내에 들어오는 경우라면 


        else

        {


            if (PQ->Nodes[LeftPosition].Priority < PQ->Nodes[RightPosition].Priority)

                SelectChild = LeftPosition;

            else

                SelectChild = RightPosition;


        }


        if (PQ->Nodes[SelectChild].Priority < PQ->Nodes[ParentPosition].Priority)

        {

            PQ_SwapNodes(PQ, ParentPosition, SelectChild);

            ParentPosition = SelectChild;

        }

        else

            break;


        LeftPosition = PQ_GetLeftChild(ParentPosition);

        RightPosition = LeftPosition + 1;

    }

    

    if (PQ->UsedSize < (PQ->Capacity / 2))

    {

        PQ->Capacity /= 2;

        PQ->Nodes = (PQNode*)realloc(PQ->Nodes, sizeof(PQNode) * PQ->Capacity);

    }

}



int PQ_GetParent(int Index)

{

    return (int)((Index - 1) / 2);

}


int PQ_GetLeftChild(int Index)

{

    return (2 * Index + 1);

}


int PQ_IsEmpty(PriorityQueue* PQ)

{

    return (PQ->UsedSize == 0);

}





main.c


#include "PriorityQueue.h"



void PrintNode(PQNode* Node)

{

    printf("사이트 명 : %s (우선순위:%d)\n", Node->Data, Node->Priority);

}



int main()

{

    PriorityQueue* PQ = PQ_Create(3);


    PQNode Popped;


    PQNode Nodes[5] =

    {

        {5, (void*)"수만휘"},

        {1, (void*)"오르비"},

        {4, (void*)"윤통시"},

        {3, (void*)"수갤"},

        {2, (void*)"포만한"},    

    };


    PQ_Enqueue(PQ, Nodes[0]);

    PQ_Enqueue(PQ, Nodes[1]);

    PQ_Enqueue(PQ, Nodes[2]);

    PQ_Enqueue(PQ, Nodes[3]);

    PQ_Enqueue(PQ, Nodes[4]);



    printf("큐에 남아 있는 사이트 :%d\n", PQ->UsedSize);


    while (!PQ_IsEmpty(PQ))

    {

        PQ_Dequeue(PQ, &Popped);

        PrintNode(&Popped);

    }


    return 0;

}


실행결과 : 


큐에 남아 있는 사이트 :5

사이트 명 : 오르비 (우선순위:1)

사이트 명 : 포만한 (우선순위:2)

사이트 명 : 수갤 (우선순위:3)

사이트 명 : 윤통시 (우선순위:4)

사이트 명 : 수만휘 (우선순위:5)

rare-백예린입니다

0 XDK (+0)

  1. 유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.

✨컴공주✨ [1052682]

쪽지 보내기


  • 첫번째 댓글의 주인공이 되어보세요.
글쓰기
오르비 1455013번째 회원 되기
아이디 찾기 비밀번호 찾기

오늘의 추천 글

오르비 과외시장

2027 수능 D - 192

오르비 플레이
오르비 RARE
Move
our corporate site
Orbi Class
on-line classes
Orbi Books
educational books & resources
Gae9
humor and fun

© 2000-2026 Move Inc.

orbisoptimus (v17-b0aa00)