BLOG. 2won0

랜덤하게 2진트리를 생성하고, 각각의 방식 (Preorder, Inorder, Postorder) 으로 출력하는 프로그램을 만들어 보았다.

먼저 랜덤하게 생성되는 트리는 중복되지 않는 20개의 숫자를 랜덤하게 생성하여 이진트리로 만들었다.

랜덤하게 생성된 이진트리의 구조는 다음과 같다.

이를 각각의 방식으로 출력해주는 함수를 만들어 출력해 주었다.

출력함수는 다음과 같다.

Preorder 방식

Inorder 방식

Postorder 방식

다음과 같이 제대로 출력되는 모습을 확인 할 수 있다.

Binary Tree Traversal, 즉 2진트리 탐색에 대해 알아보자.

정보처리기사 시험문제에도 나오는 이론이기 때문에 중요할듯 싶다 ㅋ

이진트리탐색에서 항상 나오는 3가지 방법, Inorder Traversal, Preorder Traversal, Postorder Traversal이 있고,

한가지 더 추가적으로 보자면 Levelorder Traversal을 이야기 할 수 있을 것이다

이들의 방법은 각각 이렇다.

먼저 그림을 보고 이해하자면

다음과 같은 Binary Tree, 즉 2진트리가 있을 때

Inorder는 Left child -> Root -> Right child 순으로,

Preorder는 Root -> Left child -> Right child 순으로,

Postorder는 Left child -> Right child -> Root 순으로 탐색을 하는 방식이다.

각각 Root를 기준으로 Root가 언제 탐색되는지에 따라서 기억 하면 쉬울 것 같다.

그리고 Level Order방식은 트리의 레벨에 따라서 차례대로 탐색하면 된다.

각각의 방식으로 탐색을 하게 되면 결과는 다음과 같을 것이다.

Tree와 비교하면서 순서를 따져보면 쉽게 이해할 수 있을 것이다.

전체 소스 및 보고서 다운받기

다항식을 Linked LIst를 이용하여 표현하기 위해 다음과 같은 node를 구성하였다.

즉 2x^3 이라는 항이 있다면 node에 coef = 2; exp = 3; 이 저장되는 방식이다.

이러한 다항식을 List로 표현해 보았다.

값으로 0, 0을 가지는 header노드와 -1, -1을 가지는 tail 노드를 포함하여 List형태로 표현한다.

makePolynomial() 이라는 node* type의 함수를 이용하여 다항식을 생성해 보았다.

여기서 조건은 메인함수에서 최고차항의 지수를 입력받고, 항이 생성되는 조건은 70%의 확률로 항의 존재유무를 결정한다.

또한 SelectPlusMinus() 라는 함수를 이용하여 랜덤하게 항의 계수가 양수가 될수도있고, 음수가 될수도 있게 하였다.

이와 같은 방식으로 두개의 다항식을 생성한 뒤 두 다항식을 더해주었다.

다항식의 덧셈을 할 때에는 각각의 다항식에서 현재 위치를 저장할 포인터 변수가 필요하다.

덧셈과정은 다음과 같다.

A와 B라는 다항식이 있다면 제일먼저 P와 Q라는 포인터 변수가 제일 첫번째 항을 가르키고 있게 만든다.

그리고 P위치의 exp값과 Q위치의 exp값, 즉 각 현재위치 항의 차수를 비교하여 연산을 다르게 해준다.

1. P->exp == Q->exp 일때 (같은 차수의 항일 때)

두 계수를 더해서 0이 아니면 더한값을 새로운 다항식인 C에 저장하고, 만약 0이 된다면 항이 사라지는 것이기 때문에

P와 Q포인터를 다음 포인터로 증가시켜준다.

2. P->exp < Q->exp 일 때, 현재 P와 Q위치에서 B항의 차수가 더 클 때

Q가 가리키고 있는 항을 C에 노드로 만들어 주고 연결한다. 이후에 Q만 다음 포인터로 이동시킨다.

3. P->exp > Q->exp 일 때, 현재 P와 Q위치에서 A항의 차수가 더 클 때 

P가 가리키고 있는 항을 C에 노드로 만들어 주고 연결한다. 이후에 P만 다음 포인터로 이동시킨다.

위와 같은 과정을 통해 프로그램을 실행시켜 확인해 보면 다음과 같은 결과를 제대로 얻어 낼 수 있었다.

전체 소스 및 보고서 다운받기

Linked List란 다음 그림과 같은 구조로 포인터를 이용하여 List를 만들어 내는 것이다.

즉 데이터와 link를 이용하여 하나의 배열 형태로 이루어 져 있지만 실제로는 List형태로 연결되어 있는 것이다.

List를 사용하면 Array를 이용할 때 정적인 방법으로 코드 작성시에 Array 사이즈를 지정해 주던것을 동적인 방법으로 만들어 줄 수 있고,

구조체의 내용에 따라 다양한 data를 이용하여 List를 만들어 낼 수 있다.

위의 구조대로 node를 만들어 낸다면 구조체의 선언을 위와 같이 해주면 되고, 만약에 int형 data말고도 추가적으로 더 넣고 싶은게 있다면

구조체에 넣어주기만 하면 된다. 그렇게 되면 node 타입의 노드들이 List형태로 연결되는 자료구조를 만들어 낼 수 있다.

삽입시에도 원하는 노드 다음노드에 포인터를 연결해 주면 되고, 삭제시에도 원하는 노드에 연결되어 있는 포인터를

그다음 노드로 연결시켜주면 된다.

그렇다면 기본적인 Linked List를 생성하는 코드를 보도록 하겠다.

코드는 파일로 저장되어있는 20개의 정수를 읽어와 Linked List로 연결하는 프로그램 이다.

List를 생성할 때에는 기본적으로 두가지 기능을 할 수 있는 함수를 만들어 주었는데

하나는 새로운 노드를 생성하는 함수, 그리고 하나는 생성된 노드를 원하는 List의 마지막 노드에 연결시키는 함수 이다.

동적할당인 malloc을 이용해서 node* type의 메모리를 allocation해주고, 초기 data는 0, next link는 Null로 초기화 시켜준다.

다음과 같은 두개의 함수를 이용해서 만들어 주었다.

main함수 내에서 node* 형식의 변수를 하나 만들어 주고 그 포인터변수에 makeLL() 함수를 붙여 주었다.

makeLL() 함수 내에서는 fscanf()를 통해 파일로 부터 정수를 읽어오고, 매번 newnode()와 LinkNode() 를 Call하는것을 볼 수 있다.

파일에서 읽어온 정수인 buf를 파라미터로 넘겨 새로운 노드를 생성하고, 생성된 노드를 header 포인터 정보와 함께 넘겨

제일 마지막에 연결시키는 구조이다.

괄호가 없는 식일 때 Infix (중위표기식)에서 Postfix (후위표기식) 로 바꾸는 방법을 구현해 보았다.

이 과정에서는 연산자의 위치를 결정하기 위해 STACK을 이용하였다.

보고서 및 전체 소스 다운받으러 가기

예를들어 a+b*c 라는 식을 후위표기식으로 변환한다고 해보자.

연산자를 위한 STACK을 만들고 연산자를 만났을 때 STACK에 저장한다.

이 과정에서 연산자의 우선순위를 생각해 주어야 하는데, 우선순위는 우리가 일반적으로 알고 있는것과 같이 *,/ 가 +,- 보다

더 높은 경우들을 생각하면 된다.

이러한 우선순위를 적용하기 위해 프로그램 내에서 따로 우선순위를 결정해주는 함수를 만들어 주었다.

보고서 및 전체 소스 다운받으러 가기

Postfix로 작성된 수식을 STACK을 이용하여 연산하는 프로그램을 작성해 보았다.

보고서 및 전체 소스 다운로드

연산과정은 다음과 같다.

예를들어 8/2-3 이라는 Infix방식의 수를 82/3- 의 Postfix방식으로 바꾼뒤 STACK을 이용하여 연산을 하게 되면

연산될 두 숫자를 STACK에 저장하고 연산자를 만났을 때 연산, 결과를 다시 STACK에 넣는다.

같은 방식으로 식이 종료될 때 까지 반복하면 STACK에는 전체의 연산 결과가 저장될 것이고, 이를 결과로 출력해 준다.

int calculate(char *oper) {
	
	int i=0;
	int j;
	int temp = 0; // 연산된 값을 저장하기 위한 temp 변수
	int temp_mul = 1; // 제곱 연산을 하기 위한 변수


	while(oper[i] != 0) // oper[i] 가 null값, 즉 배열의 마지막 값을 만나면 반복문 종료
	{					// 배열의 마지막 값이 0으로 입력되어 0으로 해주었다.
		
		if(isdigit(oper[i])) // isdigit() -> 배열 값이 정수일때 return 1
		{
			push(oper[i] - '0'); // character 문자형을 정수형으로 바꾸어 주기 위해
								 // ASCII 코드값에서 '0'을 빼주어 push 시킨다.
		}
		else // 배열값이 정수가 아닌 문자일 때
		{
			switch(oper[i])
			{
			case '+': // 더하기 연산
				temp = stack[top-1] + stack[top]; // stack에 들어있는 두 숫자를 더해서 temp에 저장
				// 현재 top index 이전 값과 현재 top index값 두개를 더한다.
				pop(); 
				pop(); // 두 숫자를 더했기 때문에 두번 pop 시킨다.
				push(temp); // temp 값을 다시 push 시킨다.
				break;
			
			case '-': // 빼기 연산
				temp = stack[top-1] - stack[top];
				pop();
				pop();
				push(temp);
				break;

			case '*': // 곱하기 연산
				temp = stack[top-1] * stack[top];
				pop();
				pop();
				push(temp);
				break;

			case '/': // 나누기 연산
				if(stack[top] == 0)
				{
					printf("0으로 나눌 수 없습니다.\n");
					exit(1);
				} // 나눌 숫자가 0일 경우 나눌 수 없기 때문에 에러메시지 출력후 프로그램 종료
				else
				{
					temp = stack[top-1] / stack[top];
					pop();
					pop();
					push(temp);
				}
				break;

			case '%': // 나머지 연산
				if(stack[top] == 0)
				{
					printf("0으로 나눌 수 없습니다.\n");
					exit(1);
				} // 나눌 숫자가 0일 경우 나눌 수 없기 때문에 에러메시지 출력후 프로그램 종료
				else
				{
					temp = stack[top-1] % stack[top];
					pop();
					pop();
					push(temp);
				}
				break;


			case '^': // 제곱연산
				for(j=0;j<stack[top];j++)
				{
					temp_mul = temp_mul * stack[top-1];
				} // 제곱을 만나면 제곱 수 만큼 반복해서 곱해준뒤 변수에 저장한다.
				pop();
				pop();
				push(temp_mul);
				break;


			default:
				printf("알수없는 연산자가 있습니다.\n"); 
				// 알수없는 연산자가 있을 경우 에러메시지 출력후 프로그램 종료
				exit(1);
				break;

			}
		}

		i++;
	}


	return stack[0];
	
}

Calculate라는 Integer형 함수를 만들어 연산 식이 저장되어있는 파일로 부터 식을 읽어와 함수로 넘겨주었다.

 

함수내에서는 STACK을 이용하여 식을 연산하고 최종적으로 STACK의 [0]번째 index, 즉 최종값을 return 시켜 주었다.

 

 

위와 같은 input data를 txt파일로 작성한 뒤 프로그램을 실행시켰을 때

 

 

 

위와 같은 연산 결과를 얻어 낼 수 있었다.

 

보고서 및 전체 소스 다운로드