SDL 회전 대칭

SDL_RenderCopyEx(SDL_Renderer*, SDL_Texture*, SDL_Rect*, double angle, SDL_Point*, SDL_RendererFlip) // angle은 회전 각도 시계방향으로 회전해서 출력 SDL_RendererFlip은 어떻게 뒤집는지 SDL_FLIP_NONE은 뒤집지 않는 것, SDL_FLIP_HORIZEONTAL, SDL_FLIP_VERTICAL은 각각 횡방향, 종방향 뒤집는것

InitializeWindow

bool InitializeWindow(const char* title, int xpos, int ypos, int width, int height, int fullscreen)
{
int flags = 0;
if(fullscreen)
{
flags = SDL_WINDOW_FULLSCREEN;
}

// attempt to initialize SDL
if(SDL_Init(SDL_INIT_EVERYTHING) == 0)
{
std::cout << "SDL init success\n";
// init the window
g_window = SDL_CreateWindow(title, xpos, ypos,
width, height, flags); // 여기에 flags 대신 flags|SDL_WINDOW_RESIZABLE 을 넣으면 창 크기 조절가능

if(g_window != 0) // window init success
{
std::cout << "window creation success\n";
g_renderer = SDL_CreateRenderer(g_window, -1, 0);
if(g_renderer != 0) // renderer init success
{
std::cout << "renderer creation success\n";
SDL_SetRenderDrawColor(g_renderer,
255,255,255,255);
}
else
{
std::cout << "renderer init fail\n";
return false; // renderer init fail
}
}
else
{
std::cout << "window init fail\n";
return false; // window init fail
}
}
else
{
std::cout << "SDL init fail\n";
return false; // SDL init fail
}
std::cout << "init success\n";
g_flag_running = true; // everything inited successfully, start the main loop

return true;

}

SDL 기본 그리기

Intro::Intro()
{

SDL_Surface* temp_surface = IMG_Load("Resources/intro.png"); // 이미지를 가져와 메인메모리(CPU)에 할당한다.
texture_ = SDL_CreateTextureFromSurface(g_renderer, temp_surface); // CPU에 있는 이미지를 그래픽메모리에 할당
SDL_FreeSurface(temp_surface); // 메인메모리(CPU)에 있는 데이터를 삭제한다.

SDL_QueryTexture(texture_, NULL, NULL, &source_rectangle_.w, &source_rectangle_.h); // 텍스트 정보를 가져온다.

destination_rectangle_.x = source_rectangle_.x = 0; // source_rectangle은 원래 이미지의 시작이미지 destination은 가져올 이미지의 시작이미지
destination_rectangle_.y = source_rectangle_.y = 0;
destination_rectangle_.w = source_rectangle_.w; // 이말은 사진의 원래 크기만큼 생성한다는 말
destination_rectangle_.h = source_rectangle_.h;
}
void Intro::Render()
{
SDL_SetRenderDrawColor(g_renderer, 255,255,255,255); // 배경의 색을 지정해주는 함수
SDL_RenderClear(g_renderer); // clear the renderer to the draw color

    SDL_RenderClear(g_renderer); // clear the renderer to the draw color
SDL_RenderCopy(g_renderer, texture_, &source_rectangle_, &destination_rectangle_); // 그림을 그리기 위한 함수 범위를 전체로 하고싶다면 포인터대신 NULL

SDL_RenderPresent(g_renderer); // draw to the screen // 위에 가져온 그림을 화면에 출력
}

[대학교 알고리즘] HeapSort

void MakeHeap(int A[ ], int Root, int LastNode) {
/* 입력 : A[Root:LastNode] - 히프로 변환할 배열. 입력 당시에
  A[Root+1:LastNode] 는 이미 히프 구조이다.
출력 : A[Root:LastNode] - 최대값 히프 */
int Parent, LeftSon, RightSon, Son, RootValue;
Parent = Root;
RootValue = A[Root];
LeftSon = 2 * Parent + 1;
RightSon = LeftSon + 1;
while (LeftSon <= LastNode) {
if (RightSon <= LastNode && A[LeftSon] < A[RightSon])
Son = RightSon;
else Son = LeftSon;
if (RootValue < A[Son]) {
A[Parent] = A[Son];
Parent = Son;
LeftSon = Parent * 2 + 1;
RightSon = LeftSon + 1;
}
else break;
}
A[Parent] = RootValue;
}

void HeapSort(int A[ ], int n) {
/* 입력: A[0:n-1] - 정렬할 배열, n - 정렬할 원소의 개수.
출력: A[0:n-1] - 정렬된 배열. */
int i;
for (i=n/2; i>0; i--)
MakeHeap(A, i-1, n-1);
for (i=n-1; i>0; i--) {
Swap(&A[0], &A[i]);
MakeHeap(A, 0, i-1);
}
}

[대학교 알고리즘] MergeSort

void Merge(int A[ ], int Low, int Mid, int High) {
/* 입력: A[Low:Mid], A[Mid+1:High] - 정렬된 두 배열.
출력: A[Low:High] - A[Low:Mid]와 A[Mid+1:high]를 합병하여 정렬된 배열 */
int B[NUM_OR_KEYS]; // 퀵정렬에는 없지만 합병정렬에만 있는 합병을 하기 위한 배열.
int i, LeftPtr, RightPtr, BufPtr;
LeftPtr = Low; // 왼쪽
RightPtr = Mid +1; // 반을 나누기 위해 가운데
BufPtr = Low; // 이것도 왼쪽
while (LeftPtr <= Mid && RightPtr <= High) //
if (A[LeftPtr] < A[RightPtr])
B[BufPtr++] = A[LeftPtr++];
else B[BufPtr++] = A[RightPtr++];
if (LeftPtr > Mid)
for (i=RightPtr; i<=High; i++)
B[BufPtr++] = A[i];

else
for (i=LeftPtr; i<=Mid; i++)
B[BufPtr++] = A[i];
for (i=Low; i<=High; i++)
A[i] = B[i];
}

void MergeSort(int A[ ], int Low, int High) {
/* 입력: A[Low:High] - 정렬하려는 배열. Low, High - 정렬할 원소가 있는 곳을
나타내는 최소, 최대 인덱스.
출력: A[Low:High] - 정렬된 배열. */
int Mid;
if (Low < High) {
Mid = (Low + High) / 2;
MergeSort(A[ ], Low, Mid);
MergeSort(A[ ], Mid+1, High);
Merge(A[ ], Low, Mid, High);
}
}

[대학교 알고리즘] QuickSort

int Partition (int A[ ], int Left, int Right) {
/* 입력 : A[Left:Right] - 분할하려는 부분배열, A[Left] - 분할 원소,
  A[Right] - 더미 키.
출력 : A[Left:Right], Right - 분할 원소를 제자리에 위치시키고,
그 인덱스를 변수 Right에 담아서 복귀한다. */
int PartElem, Value;
PartElem = Left; // 분할 배열의 첫 번째 인덱스 복사.
Value = A[PartElem]; // 기준이 되는 인덱스의 값을 복사해서 비교값으로 사용한다 기준이지
do {
do { } while (A[++Left] < Value); // 첫값은 기준값이기 때문에 ++사용
do { } while (A[--Right] > Value); // 함수 입력받을때 +1로 원래 배열의 수보다 많이받아서 이것도 통일성을 위해 --사용
if (Left < Right) Swap(&A[Left], &A[Right]); // 위에서 두개 비교한 인덱스 값이 오른쪽이 더 크다면
else break; // 오른쪽에 작은값이 있고 왼쪽에 큰값이 있다는 것이다.
} while (1); // 둘이 같을수는 없고 Right이 더 작다면 정렬이 끝난 상태로 반복문 탈출
A[PartElem] = A[Right]; // 정렬이 끝난 그 기준값과 가운데 있는 값을 교환한다. 원래 Right값은 당연히 기준값보다 작다.
A[Right] = Value;
return Right; // 분할할때 중앙인덱스를 반환.

}
void QuickSort (int A[ ], int Left, int Right) {
/* 입력 : A[Left:Right+1] - 정렬할 배열, A[Right+1]은 배열 내의 최대값보다 큰 값.
   Left, Right - 배열 내의 정렬할 원소의 위치를 알리는 최소, 최대 인덱스.
출력 : A[Left:Right] - 정렬된 배열. A[Right+1]은 더미 키가 있는 곳.*/
int Middle;
if (Right > Left) { // Right가 Left보다 더 크다는건 정렬이 안끝났다는 말이다.
Middle = Partition(A[ ], Left, Right+1); // 반의 인덱스를 리턴받아서 새로운 Right값으로 사용. '
QuickSort(A[ ], Left, Middle-1); // 기준이 되는 인덱스는 최선의 값이기 때문에 제외하고 정렬
QuickSort(A[ ], Middle+1, Right); // 위와 마찬가지
} // 계속 반의 반의 반 이런식으로 하나가 남는다면 Right 와 Left가 같아진다. 그럼 반복문 종료 재귀함수 생각하면 편함.

}

[대학교 알고리즘] ShellSort

void ShellSort(int A[ ], int n) {
/* 입력 : A[0:n-1] - 정렬할 원소가 있는 배열, n - 정렬할 원소의 개수.
출력 : A[0:n-1] - 정렬된 배열.*/
int h, i, j, Value;
h = 1; // 간격을 설정해줄 변수
do h = 3 * h + 1; while (h < n); // 일단 크기를 늘린다.
do {
h = h / 3; // h는 이미 n보다 큰 수 이기때문에 한번 나누어준다.
for (i=h, i<n; i++) { // i = h 부터 시작하지만 큰 반복문에서 h값은 점점 줄어들기 때문에 전체적으로 반복하게 된다.
Value = A[i]; // 현재의 기준값을 저장
j = i; // 인덱스 일치
while (A[j-h] > Value) { // 처음엔 A[0] 인덱스와 비교 그후에 1씩 증가하는것을 볼 수 있다.
A[j] = A[j-h]; // 삽입정렬과 방법은 같다. 거리가 다르다.
j -= h; // i 값이 h값보다 커지게 되는 순간에는 자신의 아래쪽 간격으로 비교를 할 수도 있다.
if (j <= h-1) break;
}
A[j] = Value; // 만약 비교하여 자리가 바뀌었다면 그자리에 넣어준다.
}
} while (h > 1); // h간격이 1일때까지 실행을 마친후에 종료된다.
}

[대학교 알고리즘] InsertionSort

void InsertionSort(int A[ ], int n) {
/* 입력: A[0:n] - 정렬할 원소가 있는 배열, n - 정렬할 원소의 개수.
 A[0]는 A[1:n]의 어느 값보다도 더 작은 더미 키이다.
출력: A[0;n] - A[0]은 더미 키이고, A[1:n]은 정렬된 배열임. */
int i, j, Value;
for (i=2; i<=n; i++) { // 인덱스가 하나씩 늘어나지만 자신의 왼쪽의 숫자와 비교
Value = A[i]; // 비교대상의 제일 오른쪽 값을 넣어준다.
j = i; // 인덱스 일치
while (A[j-1] > Value) { // 자신의 왼쪽 값과만 비교를 실행
A[j] = A[j-1]; j--; // 왼쪽이 크다면 기존값은 저장이 되어있으므로 하나씩 밀어준다.
}
A[j] = Value; // 마지막에 자리에 비교대상을 넣어준다.
}

}

[대학교 알고리즘] BubbleSort

void BubbleSort(int A[ ], int n) {
/* 입력 : A[0:n-1] - 정렬할 원소가 있는 배열, n - 정렬할 원소의 개수.
출력 : A[0:n-1] - 정렬된 배열.*/
int i, Sorted;
Sorted = FALSE; // 이미 정렬된 함수일 경우 반복문을 빠져나간다.
while (!Sorted) { // 이미 정렬되어있을경우 Sorted 값이 TURE에서 바뀌지 않는다.
Sorted = TRUE;
for (i=1; i<n; i++) // 처음부터 마지막 까지 반복한다. 매번 n번 반복한다.
if (A[i-1] > A[i]) { // 뒤에있는 값이 크다면 자리를 바꿔주고 Sorted 값을 바꿔주어 반복이 지속되게 해준다.
Swap(&A[i-1], &A[i]); // 처음에는 마지막에 제일 큰수가 다음실행엔 두번째로 큰수가 마지막-1에 저장. 반복을 많이 실행.
Sorted = FALSE;
}
}
}

[대학교 알고리즘] SelectionSort

void SelectionSort (int A[], int n) {
/* 입력 : A[0:n-1] - 정렬할 원소가 있는 배열, n - 정렬할 원소의 개수.
출력 : A[0:n-1] - 정렬된 배열.*/
int i, j, MinIndex;
for (i=0; i<n-1; i++){ // 맨 처음부터 마지막 원소 전까지 반복
MinIndex = i; // 현재의 값을 기준으로
for (j = MinIndex+1; j<n; j++) // 기준 +1에서부터 마지막 까지 반복
if (A[MinIndex] > A[j]) // 반복문을 돌면서 제일 작은 값을 찾는다.
MinIndex = j;
if (MinIndex != i)
Swap(&A[i], &A[MinIndex]); // 제일작은 값을 기준값과 바꾸어주면서 제일 작은 값이 왼쪽에 위치한다.
}
}

[대학교 과제] 미디어처리 알고리즘, postfix / stack / parse tree / queue

주어진 postfix 표기의 식을 입력해서 스택을 사용해서 주어진 식을 연산하는 알고리즘을완성하시오.

 

#include <iostream>

using namespace std;

 

class Stack // 스택을 사용하기 위한 클래스다.

{

public:

Stack() // 메인함수에서 선언과 동시에 실행 되게 한다.

{

stack_top = -1; // 스택을 사용하기 위해 스택번호의 초기화

i = 0; // 입력받은 데이터 배열에서 사용하기 위한 인덱스 초기화

cout << "테스트 데이터를 입력하세요. [숫자와 연산자 중간에는 띄어쓰기를 해야 한다.]" << endl << "테스트 데이터 : "; // 입력받을 데이터 출력

cin.getline(test_data, 100, '\n'); // getline 함수를 사용해 띄어쓰기까지 입력받아서 test_data에 넣는다.

}

void Start() // 입력받은 데이터로 실행하는 함수

{

buf_ptr = buf; // buf_ptr를 buf의 시작주소로 초기화

while(test_data[i] != NULL) // test_data의 모든 단어를 읽은 후 반복문 종료

{

if(test_data[i] == ' ') // 띄어쓰기일때 실행

{

if(buf_ptr != buf) // 버퍼에 자료가 들어가 있다면 실행

Push(); // Push()함수를 이용해 test_data를 stack_arr에 넣는다.

while(buf_ptr != buf){ // buf의 데이터와 buf_ptr의 시작주소를 초기화

(*buf_ptr) = NULL;

buf_ptr--;

}

}

else if(test_data[i] < 48) // 유니코드 48아래인 특수기호가 test_data에 들어있을때 실행

Push(test_data[i]); // Push함수를 이용해 연산을 처리한다.

else

{

*buf_ptr = test_data[i]; // test_data의 숫자를 buf_ptr을 이용해 buf에 하나씩 넣는다.

buf_ptr++; // buf_ptr가 가리키는 주소 하나 증가

}

i++; // test_data의 인덱스 하나 증가

 

}

cout << "입력된 값에 대한 결과 값이 나왔습니다." << endl; // 모든 과정이 나온후 출력된다.

}

void Push()

{

stack_arr[++stack_top] = atoi(buf); // buf에 문자로 저장되어있는 숫자를 숫자로 바꾸어 인덱스 하나 증가하여 stack_arr에 넣는다..

}

void Push(char a)

{

if(a == '*') // 입력받은 문자중 '*'라면 스택에서 숫자 두개를 곱한후 두개중 첫번째 숫자 위치에 수를 저장하고 인덱스 하나 감소

stack_arr[stack_top-1] *= stack_arr[stack_top--];

else if(a == '+') // 입력받은 입력받은 문자중 '+'라면 스택에서 숫자 두개를 더한후 두개중 첫번째 숫자 위치에 수를 저장하고 인덱스 하나 감소

stack_arr[stack_top-1] += stack_arr[stack_top--];

}

void Print_Stack(void)

{

cout << "계산된 결과는 : " << *stack_arr << endl; // 계산된 결과를 출력하는 코드다.

}

private:

char test_data[100], buf[10]; // 클래스에서 사용 될 변수의 선언

char *buf_ptr;

int stack_arr[100];

int stack_top, i;

};

 

int main()

{

Stack s; // 선언과 동시에 사용자에게 입력을 받는다.

s.Start(); // 입력받은 문자를 이용해 연산

s.Print_Stack(); // 연산후 출력

}

 

 

스택을 사용해서 postfix 표기의 식을 입력받아 연산한다. 모든 데이터를 char형으로 입력받아 그것을 buf배열과 atoi함수를 이용해 int 형 배열에 스택으로 넣어놓고 연산기호를 입력 받았을 때 스택에 있는 수를 계산하고 다시 집어넣는 방식으로 구현 하였다.

 

 

2. 포인터를 사용하여 데이터구조 스택(STACK2)을 구현하고, 다른 연산( -./ )도 포함된 다음의 data를 처리하는 알고리즘으로 수정하여 실습하시오.

 

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

using namespace std;

 

class Stack // 스택을 사용하기 위한 클래스다.

{

public:

Stack() // 메인함수에서 선언과 동시에 실행 되게 한다.

{

cout << "테스트 데이터를 입력하세요. [숫자와 연산자 중간에는 띄어쓰기를 해야 한다.]" << endl << "테스트 데이터 : "; // 입력받을 데이터 출력

cin.getline(test_data, 100, '\n'); // getline 함수를 사용해 띄어쓰기까지 입력받아서 test_data에 넣는다.

}

void Start() // 입력받은 데이터로 실행하는 함수

{

buf_ptr = buf; // buf_ptr를 buf의 시작주소로 초기화

stack_ptr = stack_arr; // 스택을 사용하기 위해 변수 대신에 포인터를 사용한다.

stack_ptr--; // 변수로 사용 할 때와 동일한 방식으로 사용하기 위해 주소값을 -1해준다.

i = 0; // test_data의 인덱스 초기화

while(test_data[i] != NULL) // test_data의 모든 단어를 읽은 후 반복문 종료

{

if(test_data[i] == ' ') // 띄어쓰기일때 실행

{

if(buf_ptr != buf) // 버퍼에 자료가 들어가 있다면 실행

Push(); // Push()함수를 이용해 test_data를 stack_arr에 넣는다.

while(buf_ptr != buf){ // buf의 데이터와 buf_ptr의 시작주소를 초기화

(*buf_ptr) = NULL;

buf_ptr--;

}

}

else if(test_data[i] < 48) // 유니코드 48아래인 특수기호가 test_data에 들어있을때 실행

Push(test_data[i]); // Push함수를 이용해 연산을 처리한다.

else

{

*buf_ptr = test_data[i]; // test_data의 숫자를 buf_ptr을 이용해 buf에 하나씩 넣는다.

buf_ptr++; // buf_ptr가 가리키는 주소 하나 증가

}

i++; // test_data의 인덱스 하나 증가

 

}

cout << "입력된 값에 대한 결과 값이 나왔습니다." << endl; // 모든 과정이 나온후 출력된다.

}

void Push()

{

*++stack_ptr = atoi(buf); // buf에 문자로 저장되어있는 숫자를 숫자로 바꾸어 인덱스 하나 증가하여 stack_arr에 넣는다..

}

void Push(char a)

{

if(a == '*') // 입력받은 문자중 '*'라면 스택에서 숫자 두개를 곱한후 두개중 첫번째 숫자 위치에 수를 저장하고 인덱스 하나 감소

*(--stack_ptr) *= *(stack_ptr+1);

else if(a == '+') // 입력받은 문자중 '+'라면 스택에서 숫자 두개를 더한후 두개중 첫번째 숫자 위치에 수를 저장하고 인덱스 하나 감소

*(--stack_ptr) += *(stack_ptr+1);

else if(a == '/') // 입력받은 문자중 '/'라면 스택에서 숫자 두개를 나눈후 두개중 첫번째 숫자 위치에 수를 저장하고 인덱스 하나 감소

*(--stack_ptr) /= *(stack_ptr+1);

else if(a == '-') // 입력받은 문자중 '-'라면 스택에서 숫자 두개를 뺀후 두개중 첫번째 숫자 위치에 수를 저장하고 인덱스 하나 감소

*(--stack_ptr) -= *(stack_ptr+1);

}

void Print_Stack(void)

{

cout << "계산된 결과는 : " << *stack_ptr << endl; // 계산된 결과를 출력하는 코드다.

}

private:

char test_data[100], buf[10]; // 클래스에서 사용 될 변수의 선언

char *buf_ptr;

int stack_arr[100];

int i;

int *stack_ptr;

};

 

int main()

{

Stack s; // 선언과 동시에 사용자에게 입력을 받는다.

s.Start(); // 입력받은 문자를 이용해 연산

s.Print_Stack(); // 연산후 출력

}

 

위에 주어진 실습1과 동일한 방식에서 인덱스를 변수로 사용하지 않고, 포인터를 이용해 가리키게 하였다. 추가로 –와 /연산도 추가하였으며 이 또한 포인터를 이용하여 처리하였다.

 

3. 다음 주어진 postfix 표기의 수식을 입력하여 스택을 사용해서 이진 parse 트리로 표현하고, 이 트리를 postorder 트래버설한 결과를 출력하시오.

 

#include <iostream>

using namespace std;

 

typedef struct treeNode{ //tree를 사용하기위해 구조체 노드를 사용하였다.

char data; // 노드에 들어갈 값

struct treeNode *left; // 트리의 왼쪽을 가르키기 위한 값

struct treeNode *right; // 트리의 오른쪽을 가르키기 위한 값

} treeNode;

 

class Stack // 스택을 사용하기 위한 클래스다.

{

public:

Stack() // 메인함수에서 선언과 동시에 실행 되게 한다.

{

stack_top = -1; // 스택을 사용하기 위해 스택번호의 초기화

i = 0; // 입력받은 데이터 배열에서 사용하기 위한 인덱스 초기화

cout << "테스트 데이터를 입력하세요. [각 문자 중간에는 띄어쓰기를 해야 한다.]" << endl << "테스트 데이터 : "; // 입력받을 데이터 출력

cin.getline(test_data, 100, '\n'); // getline 함수를 사용해 띄어쓰기까지 입력받아서 test_data에 넣는다.

}

void Start() // 입력받은 데이터로 실행하는 함수

{

while(test_data[i] != NULL) // test_data의 모든 단어를 읽은 후 반복문 종료

{

if(test_data[i] == ' '){} // test_data의 값이 ' '일 때 아무런 처리도 하지않고 넘어간다.

else if(test_data[i] < 48) // 유니코드 48아래인 특수기호가 test_data에 들어있을때 실행

push(test_data[i]);

else // testdata에 문자가 들어 있을 때 그 문자를 push를 이용해 스택에 넣는다.

push();

i++; // test_data의 인덱스 1 증가.

 

}

cout << "입력된 값에 대한 결과 값이 나왔습니다." << endl << "postorder 트래버설한 결과 : "; // 모든 과정이 나온후 출력된다.

postorder(Node_ptr[0]); // postorder함수를 사용해 만들어진 트리를 postdorder트래버설한 결과를 출력한다.

cout << endl;

}

void push() // 문자를 입력받을 경우 트리의 최하위를 차지하게 되므로 바로 노드를 만들어준다.

{

Node_ptr[++stack_top] = new treeNode; // 노드를 만든다.

Node_ptr[stack_top]->data = test_data[i]; // 데이터에 testdata로 부터 입력받은 값을 넣는다.

Node_ptr[stack_top]->left = NULL; // 최하위 노드이므로 NULL 저장.

Node_ptr[stack_top]->right = NULL; // 최하위 노드이므로 NULL 저장.

}

void push(char a) // 문자가 아닌 특수기호를 입력받을 경우 이미 만들어진 노드를 이용해 트리 구조를 만든다.

{

Node_ptr[++stack_top] = new treeNode; // 노드를 생성한다.

Node_ptr[stack_top]->data = test_data[i]; // testdata로부터 입력 받은 값을 넣는다.

Node_ptr[stack_top]->right = Node_ptr[stack_top-1]; // 스택에 들어있는 상위 2개중 먼저 들어있는 노드를 가리킨다.

Node_ptr[stack_top]->left = Node_ptr[stack_top-2]; // 스택에 들어있는 상위 2개중 나중에 들어있는 노드를 가리킨다.

Node_ptr[stack_top-2] = Node_ptr[stack_top]; // 새로만든 인덱스를 사용한 2개의 노드중 앞에 노드위치에 넣는다.

stack_top -= 2; // stack_top 값도 -2해준다.

}

void postorder(treeNode* root) // postorder 트래버설을 실행하는 함수

{

if(root) {

postorder(root->left); // 먼저 왼쪽노드를 방문하고 두번째 노드를 방문하고 자신의 값을 출력한다.

postorder(root->right); // 왼쪽 노드와 오른쪽 노드가 없다면 최하위 노드이므로 바로 출력한다.

cout << root->data << ' ';

}

}

 

 

private: // class에서 사용할 변수 선언

char test_data[100];

int stack_top, i;

struct treeNode *Node_ptr[100];

};

 

 

void main()

{

Stack s; // 선언과 동시에 사용자로 부터 입력받는다.

s.Start(); // Start함수를 이용해 입력받은 데이터 처리

}

사용자로부터 문자를 입력받아 그것을 트리로 구현하였다. 문자는 자식노드가 없는 하위 노드이고 연산자를 만났을땐 연산자가 상위노드가 되고 문자가 그 연산자의 하위노드가 되는 형식을 취한다. 기본적인 트리구조와 스택구조를 사용하여 스택구조를 이용하여 문자를 받는 동시에 트리를 완성할 수 있도록 처리하였다.

 

4. 앞 문제에서 만들어진 트리에 대해서 큐를 정의하고, 이것을 사용하여 level order로 트래버설한 결과를 출력하는 프로그램을 완성하고 실습하시오.

 

#include <iostream>

using namespace std;

 

typedef struct treeNode{ //tree를 사용하기위해 구조체 노드를 사용하였다.

char data; // 노드에 들어갈 값

struct treeNode *left; // 트리의 왼쪽을 가르키기 위한 값

struct treeNode *right; // 트리의 오른쪽을 가르키기 위한 값

} treeNode;

 

class Stack // 스택을 사용하기 위한 클래스다.

{

public:

Stack() // 메인함수에서 선언과 동시에 실행 되게 한다.

{

init_queue(); // 큐를 사용하기 위해 큐를 초기화 하는 함수

init_stack(); // 스택을 사용하기 위해 스택을 초기화 하는 함수

cout << "테스트 데이터를 입력하세요. [각 문자 중간에는 띄어쓰기를 해야 한다.]" << endl << "테스트 데이터 : "; // 입력받을 데이터 출력

cin.getline(test_data, 100, '\n'); // getline 함수를 사용해 띄어쓰기까지 입력받아서 test_data에 넣는다.

}

void Start() // 입력받은 데이터로 실행하는 함수

{

while(test_data[i] != NULL) // test_data의 모든 단어를 읽은 후 반복문 종료

{

if(test_data[i] == ' '){} // test_data의 값이 ' '일 때 아무런 처리도 하지않고 넘어간다.

else if(test_data[i] < 48) // 유니코드 48아래인 특수기호가 test_data에 들어있을때 실행

push(test_data[i]);

else // testdata에 문자가 들어 있을 때 그 문자를 push를 이용해 스택에 넣는다.

push();

i++; // test_data의 인덱스 1 증가.

 

}

cout << "입력된 값에 대한 결과 값이 나왔습니다." << endl; // 모든 과정이 나온후 출력된다.

cout << "postorder : ";

postorder(node_ptr[0]); // postorder함수를 사용해 만들어진 트리를 postdorder트래버설한 결과를 출력한다.

cout << endl;

cout << "levelorder : ";

levelorder(node_ptr[0]); // postorder방식으로 만들어진 함수를 사용해 levelorder트래버설한 결과를 출력한다.

}

void push() // 문자를 입력받을 경우 트리의 최하위를 차지하게 되므로 바로 노드를 만들어준다.

{

node_ptr[++stack_top] = new treeNode; // 노드를 만든다.

node_ptr[stack_top]->data = test_data[i]; // 데이터에 testdata로 부터 입력받은 값을 넣는다.

node_ptr[stack_top]->left = NULL; // 최하위 노드이므로 NULL 저장.

node_ptr[stack_top]->right = NULL; // 최하위 노드이므로 NULL 저장.

}

void push(char a) // 문자가 아닌 특수기호를 입력받을 경우 이미 만들어진 노드를 이용해 트리 구조를 만든다.

{

node_ptr[++stack_top] = new treeNode; // 노드를 생성한다.

node_ptr[stack_top]->data = test_data[i]; // testdata로부터 입력 받은 값을 넣는다.

node_ptr[stack_top]->right = node_ptr[stack_top-1]; // 스택에 들어있는 상위 2개중 먼저 들어있는 노드를 가리킨다.

node_ptr[stack_top]->left = node_ptr[stack_top-2]; // 스택에 들어있는 상위 2개중 나중에 들어있는 노드를 가리킨다.

node_ptr[stack_top-2] = node_ptr[stack_top]; // 새로만든 인덱스를 사용한 2개의 노드중 앞에 노드위치에 넣는다.

stack_top -= 2; // stack_top 값도 -2해준다.

}

void postorder(treeNode* root) // postorder 트래버설을 실행하는 함수

{

if(root) {

postorder(root->left); // 먼저 왼쪽노드를 방문하고 두번째 노드를 방문하고 자신의 값을 출력한다.

postorder(root->right); // 왼쪽 노드와 오른쪽 노드가 없다면 최하위 노드이므로 바로 출력한다.

cout << root->data << ' ';

}

}

void init_stack() // 스택에 사용할 변수를 초기화 하는 함수

{

stack_top = -1;

i = 0;

}

void init_queue() // 큐에서 사용할 변수를 초기화 하는 함수

{

front = rear = 0;

}

void put_queue(treeNode *p) // 큐에 노드를 저장하고 rear를 1증가한다.

{

queue_ptr[rear++] = p;

}

treeNode *get_queue() // 현재위치의 큐를 반납하고 front를 1증가한다.

{

return queue_ptr[front++];

}

void levelorder(treeNode* Q)

{

put_queue(Q); // 시작할때 트리의 최상위 노드를 큐에 넣어준다.

while(notsame()){ // notsame()는 큐의 시작위치와 마지막위치가 같은경우 0을 반납한다.

Q = get_queue(); // get_queue함수로부터 반납받은 노드를 Q에 넣어준다

cout << Q->data << ' '; // 그 노드의 값을 출력한다.

if(Q->left != NULL) // 그리고 왼쪽노드의 자식이있으면 큐에 넣어주고 오른쪽도 자식이 있으면 큐에 넣어준다.

put_queue(Q->left); // 큐에 레벨 별로 저장하고 다음 반복문에서 그 레벨의 값을 출력하고 자식이 있다면 넣어주는

if(Q->right != NULL) // 방식을 반복한다.

put_queue(Q->right);

}

cout << endl;

}

int notsame() // 큐의 시작 위치와 마지막위치가 같으면 0을 반납하여 while을 종료하게 된다.

{

if(queue_ptr[front] == queue_ptr[rear])

return 0;

else

return 1;

}

private: // class에서 사용할 변수 선언

char test_data[100];

int stack_top, i;

struct treeNode *node_ptr[100];

struct treeNode *queue_ptr[100];

int front, rear;

};

 

 

 

void main()

{

Stack s;

s.Start();

}

위에 3번 문제에서 완성한 트리를 이용하고 큐를 정의하여 levelorder 트래버설한 결과를 출력한 것이다. 자신의 레벨에서 출력을 한 후 자식 노드를 큐에 넣어두고 다음 반복문에서 실행하게 함으로써 레벨 별로 출력이 가능하도록 했다.