컴공 일기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)
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
오르비문학 1화 0 0
오르비문학 1화
-
Test 0 0
Tetsteyey
-
수학 4등급만 받으면 2 0
쫀득하게 인서울 할 수 있는데
-
엘든링 왜 자꾸 멈추지 1 0
컴퓨터 좋은건데 씨발
-
목 졸라줘 5 1
켁켁켁 숨막혀 ㅜㅜ
-
시험지에 따라서 난이도가 가장 극단적으로 달라지는 번호같음....
-
개쉽게 풀리는데 이거 맞나
-
정시로 갑시다 8 0
내신반영을 노려서 내신 깡패 정시러
-
나왔어 12 0
다시감 근데 저게 왜 이륙햇냐
-
갑자기생각난썰 1 1
고1 2학기 학급회장선거때 후보가 2명이엇는데 그 친구들 둘이 합의하고 한명이...
-
그만하고 잘까 1 0
흐름이 끊겨버렷네
-
세기말 수능 1 1
2000학년도 대학수학능력시험
-
강은양t 0 0
현역 고3이고 작년까지 모고 3~4등급 나왔는데 지금부터 강은양t 들으려고 합니다....
-
2시열차 1 0
출발
-
지금 강민철 현강 다니고 있는데 저랑 너무 안맞는 느낌이 심하게 들어서...
-
뭘 해야하나요 0 0
이번에 고등학교 2학년 된 이공계 지망하는 지방 일반고학생입니다. 생기부를 제대로...
-
이게 오르비를 재밌게 오래하려면 10 4
수험생활을 지속해야 함
-
에ㅔㅔㅔㅔㅔㅔㄴ들리스레인ㄴㄴ 0 1
폴온마이헐트 코코로노 키즈니ㅣㅣㅣ
-
내 이상형 중단발에 속눈썹 1 0
-
우와 보추야동 많이떴다 2 2
보다자야지
-
심심한데 무물보 5 0
응애 나 아가학생
-
본인 물1 점수 꼬라지 0 1
3모 48점 (99) 5더프 47점인가였는데 시험이 어려웠어서 전국석차 30등쯤...
-
오후8시부터자다가깼더니 1 0
다시잠이안오네.. 비상..!!
-
생각나는구나
-
ㅇㄴ근데 0학점 패논패과목을 오ㅑㄹ케 빡세게시켜 0 0
그냥 좀 봐주면 안되나
-
-
시발점 한 다음 스블 0 0
고2이고대수 개념원리, 쎈, 고쟁이 했습니다개정 시발점 사놓은 게 있어서...
-
러셀 외부생 더프 성적표 0 0
문자로 발송되나요?? 아님 직접 찾으러 가야햐나요??
-
원래 사람은 별을 쫓아 달려갈 때 가장 빛나는 법이여설령 닿지 못할지라도적어도 내...
-
저걸 어케 함 진짜 와.. 원과목 중 생1만 수능공부로 안해봤는데 안하길잘한듯
-
시발 나 개폐급임 2 1
조별과제 하는족족 내것만 교수님 피드백 나오고 술처먹다 팀원들한테 자료 제출 개늦게하고 자퇴마렵다
-
딱 한 마디만 하고 자러감 9 3
미쿠 ㅈㄴ 예뻐어~~~~~~~~~~~~
-
중앙대 가기 59일차 3 1
안녕하세요 중앙대29학번 부산사나이 이동현입니다 음 오늘이 벌써 59일차군요...
-
이제 좀 자보실까 11 1
음음
-
리젠존나느리네 1 0
오르비망함?
-
너무멍청해짐 1 0
ㅜㅜㅜㅜㅜ
-
생윤 진짜 1도 모르는 쌩노베인데 누구 듣는 게 좋을가여
-
15살과 엄마 그 사이는 2 0
뭐라함 급함
-
대신 연세대 가겠다 선언
-
작년 10모 20번 0 0
이렇게 푸는거 맞나..?
-
-
위키하우 도움 ㅈㄴ 안되네 6 0
ㅗㅗㅗㅗㅗㅗ
-
새르비 할수록 4 0
헛소리가 늘어가는듯
-
아니 난 신라면 쳐돌이라 5 0
신라면만 먹는데….
-
-
내가사실은생명과학을좋아함 1 0
수능말고 그냥생명과학
-
. 11 1
-
님들 최애 과목 말해보셈 7 0
난 국어
-
님들 최애 라면 말해보셈 10 0
난 신라면
-
라면이랑 과자 안먹은지 6일차 2 0
후후
첫번째 댓글의 주인공이 되어보세요.