C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 10

[1번]

/*

힙을 이용하지 않고 우선순위 큐를 작성하려고 한다.

정렬되지 않은 1차원 배열을 이용해 우선순위 큐 클래스

MaxPriorityQueue를 다음과 같이 작성한다.

*/

#include <iostream>

#include <ctime>

#include <cstdlib>

using namespace std;

 

#define MAX_ELEMENT 100

 

class MaxPriorityQueue

{

private:

        int elem[MAX_ELEMENT]; //요소의 배열

        int size; //현재 요소의 개수

public:

        MaxPriorityQueue()

        {

               size = 0;

        }

        int getParent(int i)

        {

               return i / 2;

        }

        int getLeft(int i)

        {

               return i * 2;

        }

        int getRight(int i)

        {

               return i * 2 + 1;

        }

        void insert(int data) //삽입 함수

        {

               if (size == MAX_ELEMENT)

                       return;

               int i = ++size;

               while (i != 1 && data > elem[getParent(i)]) //루트가 아니고 부모노드보다 값이 크면

               {

                       elem[i] = elem[getParent(i)]; //부모를 자식노드로 끌어내리고

                       i /= 2; //한 레벨 상승

               }

               elem[i] = data;

        }

        int remove() //최대 항목 삭제 및 반환 함수

        {

               if (!size)

                       return NULL;

               int root = elem[1];

               int last = elem[size--];

               int parent = 1;

               int child = 2;

               while (child <= size)

               {

                       if (child < size && elem[getParent(parent)] < elem[getParent(parent)])

                              child++;

                       if (elem[last] >= elem[child])

                              break;

                       elem[parent] = elem[child];

                       parent = child;

                       child *= 2;

               }

               elem[parent] = last;

               child *= 2;

        }

        int find() //최대 항목 반환 함수

        {

               return elem[1];

        }

        void display() //우선순위 큐의 모든 항목 출력

        {

               int res = 1;

               int square = 2;

               int height = 1;

               int start = 0;

               while (res <= size)

               {

                       res *= 2;

                       height++;

               }

               for (int i = 1; i <= size; i++)

               {

                       if (i==1 || i == square)

                       {

                              cout << endl;

                              for (int j = start; j < height; j++)

                                      cout << "    ";

                              if(i!=1)

                                      square *= 2;

                              start++;

                       }

                       cout << elem[i];

                       for (int j = 0; j < height - start; j++)

                       {

                              if (i % 2)

                                      cout << "  ";

                              else

                                      cout << "    ";

                       }

               }

               cout << endl;

        }

};

 

int main(void)

{

        MaxPriorityQueue q;

        int arr[10];

        srand((unsigned)time(NULL));

        cout << "정렬 안된 배열: ";

        for (int i = 0; i < 10; i++)

        {

               arr[i] = rand() % 100 + 1;

               cout << arr[i] << " ";

        }

        cout << endl;

        cout << "우선순위 큐" << endl;

        for (int i = 0; i < 10; i++)

               q.insert(arr[i]);

        q.display();

        return 0;

}

[3번]

/*

배열로 표현된 완전 이진트리 a가 힙 조건을 만족하는지를 검사하는

다음 함수를 순환적인 방법으로 구현하고 테스트한다

*/

#include <iostream>

using namespace std;

 

bool isHeapRecur(int a[], int i, int size)

{

        if (i > (size - 1) / 2) //말단 노드라면

               return true;

 

        //자식보다 큰 값을 갖고 있다면(그 자식들도 그들의 자식보다 커야하므로 재귀)

        if (a[i] >= a[2 * i + 1] && a[i] >= a[2 * i + 2] && isHeapRecur(a, 2*i+1, size) && isHeapRecur(a, 2*i+2, size))

               return true;

        return false;

}

 

int main(void)

{

        int arr[11] = { 0, 9, 7, 6, 5, 4, 3, 2 , 2, 1, 3 }; //그림 10.13

        if (isHeapRecur(arr, 1, 11))

               cout << "힙이다" << endl;

        else

               cout << "힙이 아니다" << endl;

        return 0;

}

[4번]

/*

3번 문제의 함수를 반복적인 방법으로 구현하고 테스트한다

*/

#include <iostream>

using namespace std;

 

bool isHeapIter(int a[], int size)

{

        for (int i = 1; i <= (size - 1) / 2; i++) //자식이 있는 노드들만 보면 된다

        {

               //자식들보다 부모가 커야한다

               if (a[2 * i + 1] > a[i])

               {

                       cout << "거짓" << i << endl;

                       return false;

               }

               if (size<2*i+2 && a[2 * i + 2] > a[i]) //size보다 크면 배열값이 쓰레기값이 되어 크다고 나올 수 있다

               {

                       cout << "거2짓" << i << endl;

                       return false;

               }

        }

        return true;

}

 

int main(void)

{

        int arr[11] = { 0, 9, 7, 6, 5, 4, 3, 2 , 2, 1, 3 }; //그림 10.13

        if (isHeapIter(arr, 11))

               cout << "힙이다" << endl;

        else

               cout << "힙이 아니다" << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] C++로 쉽게 풀어쓴 자료구조

*1번 문제 display() 함수를 정교하게 작성하면 완벽한 트리 모양으로 출력되겠지만, 시간 관계상 형태라도 유지하게 했습니다.

*2번 문제는 정렬된 연결리스트를 굳이 우선순위 큐로 만들 필요성을 못 느껴 구현하지 않았습니다.