#include <iostream>
#include <stdlib.h>
using namespace std;
void swap(int *, int *);
int * init(size_t *); //질문 1 여기서 size_t가 어떤것을 의미하는 변수인가요??
void destroy(int *, size_t *);
int * Add(int *, size_t *, int);
void Remove(int *, size_t, size_t *);
void printParent(int *, size_t);
void printChild(int *, size_t, size_t);
void printAll(int *, size_t);
void DownHeap(int *, int, int);
void heapify(int *, int);
void heap(int *, size_t);
#define LeftCHILD(a) ((a * 2) + 1) //질문 2 왜 헤더를 이렇게 * + 등으로 선언한것인가요??
#define RightCHILD(a) (LeftCHILD(a) + 1)
#define PARENT(a) ((a - 1) / 2)
#include "heap.h"
int main() {
int *Items = NULL;
int menu;
size_t n = 0;
bool loop = true;
while (loop) {
cout << "메뉴 " << endl;
cout << "1. 생성" << endl;
cout << "2. 파기" << endl;
cout << "3. 삽입" << endl;
cout << "4. 삭제" << endl;
cout << "5. 다중 삽입" << endl;
cout << "6. 다중 삭제" << endl;
cout << "7. 부모 출력" << endl;
cout << "8. 자식 출력" << endl;
cout << "9. 힙 출력" << endl;
cout << "0. 종료" << endl;
cout << "" << endl;
cout << " >> ";
cin >> menu;
switch (menu) {
case 1: Items = init(&n); heap(Items, n); break;
case 2: destroy(Items, &n); break;
case 3: {
Items = (int *)realloc(Items, sizeof(int) * (n + 1));
Items = Add(Items, &n, 1);
heap(Items, n);
}break;
case 4: {
size_t index;
cout << "삭제할 노드번호 입력 >> ";
cin >> index;
Remove(Items, index, &n);
heap(Items, n);
}break;
case 5: {
int count;
cout << "추가할 노드 갯수 >> ";
cin >> count;
Items = (int *)realloc(Items, sizeof(int) * (n + count));
Items = Add(Items, &n, count);
heap(Items, n);
}break;
case 6: {
int count;
size_t index;
cout << "삭제할 노드 갯수 >> ";
cin >> count;
cout << endl << count << "개의 삭제할 노드번호 입력 >> ";
for (int i = 0; i < count; i++) {
cin >> index;
Remove(Items, index - i, &n);
}
}break;
case 7: {
size_t n;
cout << "부모를 출력할 노드 번호 >> ";
cin >> n;
printParent(Items, n);
}break;
case 8: {
size_t n1;
cout << "자식을 출력할 노드 번호 >> ";
cin >> n1;
printChild(Items, n1, n);
}break;
case 9: printAll(Items, n); break;
case 0: loop = false; break;
default: cout << "잘못된 입력입니다. 재시도 해주세요." << endl; break;
}
}
return 0;
}
int * init(size_t *n) { // 생성함수
cout << "몇 개의 노드를 생성하시겠습니까? >> ";
cin >> *n;
if (*n < 0) return NULL;
int *Items = new int[*n];
cout << *n << "개의 노드값을 입력해주세요. " << endl << " >> ";
for (size_t i = 0; i < *n; i++) {
cin >> Items[i];
}
return Items;
}
void destroy(int *Items, size_t *n) { // 파기함수
*n = 0;
delete Items; //동적 할당된 메모리 삭제 연산자
}
int * Add(int *Items, size_t *n, int count) { // 삽입함수
Items = (int *)realloc(Items, sizeof(int) * (*n + count));
cout << "추가할 " << count << "개의 노드값 입력" << endl << ">> ";
for (size_t i = *n; i < *n + count; i++) { // 질문 3 여기서 추가할 노드는 count를 입력받았으므로 i는 *n아닌 count가 되어야 하는것 아닌가요??
cin >> Items[i];
}
*n += count;
return Items;
}
void Remove(int *Items, size_t index, size_t *n) { // 삭제함수 /index 배열함수에 대한 데이터 접근번호
if (*n == 0) {
cout << "현재 노드가 비어있습니다." << endl;
return;
}
if (index >= *n || index < 0) {
cout << "유효하지 않은 노드번호입니다." << endl;
return;
}
for (size_t i = index; i < *n - 1; i++) { // 질문 4 이 삭제함수 부분은 아예 이해를 못하겠습니다 ㅠㅠ
Items[i] = Items[i + 1];
}
(*n)--;
}
void printParent(int *Items, size_t n) { // 부모출력함수
if (n == 0) { // 질문 5 노드 n==0 이면 왜 부모인가요??
cout << "루트노드입니다." << endl;
return;
}
cout << Items[PARENT(n)] << "(" << PARENT(n) << ")" << " -> " << Items[n] << "(" << n << ")" << endl;
}
void printChild(int *Items, size_t n, size_t size) { // 자식출력함수
if (LeftCHILD(n) >= size && RightCHILD(n) >= size) {
cout << "자식노드가 없습니다." << endl;
}
if (LeftCHILD(n) < size) { cout << Items[LeftCHILD(n)] << "(" << LeftCHILD(n) << ")" << " <- "; }
cout << Items[n] << "(" << n << ")";
if (RightCHILD(n) < size) { cout << " -> " << Items[RightCHILD(n)] << "(" << RightCHILD(n) << ")"; }
cout << endl;
}
void printAll(int *Items, size_t n) { // 힙출력함수
cout << "===== 모든 노드 출력 =====" << endl;
for (size_t i = 0; i < n; i++) {
cout << Items[i] << " ";
}
cout << endl << "총 노드 수 : " << n << endl;
}
void DownHeap(int *data, int cur, int k){ // 이하 힙 정렬 함수
int left, right, p;
while (cur < k) { // 질문 6 cur과 k가 무엇을 의미하는지 모르겠습니다 ㅜ
left = cur * 2 + 1;
right = cur * 2 + 2;
if ((left >= k) && (right >= k)) break;
p = cur;
if ((left < k) && (data[p] > data[left])) {
p = left;
}
if ((right < k) && (data[p] > data[right])) {
p = right;
}
if (p == cur) break;
swap(&data[cur], &data[p]);
cur = p;
}
}
void heapify(int *data, int n){
int i, p;
for (i = (n - 1) / 2; i >= 0; i--) {
DownHeap(data, i, n);
}
}
void heap(int *data, size_t n){
int k;
heapify(data, n);
for (k = n - 1; k > 0; ) {
swap(&data[0], &data[k]);
k--;
DownHeap(data, 0, k);
}
}
void swap(int *a, int *b) { // 스왑
int tmp = *a;
*a = *b;
*b = tmp;
}
본인삭제금지
글쓰기