[자료구조 프로그래밍 연습문제] 이진탐색트리 (binary search tree), 힙 (heap), min cost spanning tree, 전위표기식 (postfix), 연결 리스트 (linked list)

728x90

1. binary search tree와 heap

binary search tree는 노드에 key 값만 저장하는 것이 아니라 key값과 관련된 정보(associated item)를 같이 저장한다. 후자를 단순히 value라고 하자. 이 (key, value) 쌍을 보통 dictionary pair라고 부른다 (교재 ADT 5.3 Dictionary 참조). <그림 1>은 binary search tree의 예로 각 노드에 키 값만 나타낸 것이다. <그림 2>는 각 노드에 (key, value) 쌍을 나타낸 것이다. (앞의 한자리 수는 key, 뒤의 두자리 수가 value) complete binary tree로 표현되는 heap도 노드에 (key, value) 쌍을 저장할 수 있다. (교재 5.6.3절에는 heap의 노드에 저장되는 데이터의 구조체 type element가 정의되어 있는데 key와 other fields로 구성된다.) 단, binary search tree에서는 모든 노드의 key가 서로 값이 다른데 반해, heap에서는 응용에 따라 노드의 key 값들이 중복될 수도 있다. <그림 3>은 min heap의 예이다. 노드에는 key 만 표시되어 있다. <그림 4>는 각 노드에 (key, value) 쌍을 나타낸 것이다. <그림 5>는 <그림 2>와 <그림 4>의 (key, value) 쌍들을 읽어서 각 key 값별로 해당 value의 합을 구해 key 값 오름순으로 출력한 것이다. 예를 들어, 첫줄의 (1, 52)는 key=1의 value가 <그림 2>에서는 18, <그림 4>에서는 key=1인 노드가 2개이고 그 value가 각각 19와 15이다. 따라서 18+19+15=52로 합이 계산된 것이다. key=3처럼 어느 한쪽에만 값이 있으면 그 value만 출력된다. key=6인 쌍은 양쪽 구조에 다 부재하여 출력되지 않았다.

binary search tree와 min heap이 주어졌을 때, 이들의 (key, value) 쌍들을 읽어서 각 key 값별로 해당 value의 합을 구해 key 값 오름순으로 출력하는 프로그램을 작성하시오.

프로그래밍 요건 :

binary search tree는 linked representation으로 구현한다. min heap은 배열로 구현한다.
<그림 5>의 결과를 산출하기 위해 두 구조의 (key, value) 쌍을 모두 배열로 옮긴 후 전체를 정렬하는 방법은 이용하지 않는다.
데이터 입력 후 정확히 입력되었는지 실행시간에 출력을 통해 확인해 볼 수 있도록 한다.

데이터 입출력 :

처음에 binary search tree와 min heap을 생성하고 empty로 초기화한다.
(key, value) 쌍은 key 값으로 정렬되지 않은 임의의 순서로 binary search tree 및 min heap에
입력된다고 가정하며, 아래 예와 같이 2차원 배열을 통해 프로그램으로 입력되어 배열의 row 값이 작은
것부터 큰 것 순서로 해당 자료구조에 삽입된다. 아래 예에서 bst[i][0]은 key 값이고, bst[i][1]은 value
이다. 마찬가지로 mh[i][0]은 key 값이고, mh[i][1]은 value이다. heap의 경우 중복되는 key 값이 최소
1개는 있도록 한다.
(key, value 합계)의 출력은 <그림 5>와 같이 한 줄에 한 쌍씩 key 값 오름순으로 한다.
[중요] 배열명 bst[][], mh[][]는 반드시 다른 이름 쓰지 말고 그대로 사용한다. (조교가 MaxRow의 값과
배열의 데이타 값만 바꾼 후 컴파일 예정)

// 예 : binary search tree (key, value) 쌍

#define MaxRow 5
int bst[MaxRow][2] = { //binary search tree: 배열명 bst
{ 3, 17 },
{ 1, 18 },
{ 5, 20 },
{ 4, 20 },
{ 2, 15 }
};

// 예 : min heap (key, value) 쌍
#define MaxRow 5
int mh[MaxRow][2] = { // min heap: 배열명 mh
{ 2, 20 },
{ 1, 15 },
{ 5, 20 },
{ 1, 19 },
{ 7, 17 }
};

#include <stdio.h>
#include <malloc.h>
#define MaxRow 5

int bst[MaxRow][2] = { //binary search tree: 배열명 bst
{ 3, 17 },
{ 1, 18 },
{ 5, 20 },
{ 4, 20 },
{ 2, 15 }
};

int mh[MaxRow][2] = { // min heap: 배열명 mh
{ 2, 20 },
{ 1, 15 },
{ 5, 20 },
{ 1, 19 },
{ 7, 17 }
};

int result[MaxRow * 2][2] = { 0, };
int result_cnt = 0;

typedef struct bst_node {
	int key;
	int value;
	struct bst_node* left;
	struct bst_node* right;
	struct bst_node* p;
}BSTNODE;

typedef struct mh_node {
	int key;
	int value;
}MHNODE;

typedef struct minheap {
	MHNODE* node;
	int capacity;
	int filled;
}HEAP;

void bst_addnode(BSTNODE** t, int key, int value)
{
	BSTNODE* n = (BSTNODE*)malloc(sizeof(BSTNODE));
	BSTNODE* temp = *t;

	n->key = key;
	n->value = value;
	n->p = NULL;
	n->left = NULL;
	n->right = NULL;

	if (temp == NULL) {
		*t = n;
		return;
	}

	while (temp != NULL) {
		n->p = temp;

		if (temp->key > key) {
			temp = temp->left;
		}
		else {
			temp = temp->right;
		}
	}

	if ((n->p)->key > key) {
		(n->p)->left = n;
	}
	else {
		(n->p)->right = n;
	}
}

HEAP* mh_init(int row)
{
	HEAP* n = (HEAP*)malloc(sizeof(row));
	n->capacity = row;
	n->filled = 0;
	n->node = (MHNODE*)malloc(sizeof(MHNODE) * n->capacity); // trigger
	return n;
}

void mh_swap(HEAP** t, int first, int second)
{
	HEAP* H = *t;
	MHNODE temp;

	temp.key = H->node[first].key;
	H->node[first].key = H->node[second].key;
	H->node[second].key = temp.key;

	temp.value = H->node[first].value;
	H->node[first].value = H->node[second].value;
	H->node[second].value = temp.value;
}

void mh_addnode(HEAP** t, int key, int value)
{
	HEAP* H = *t;

	int current = H->filled;
	int parent = (int)((current - 1) / 2);

	H->node[current].key = key;
	H->node[current].value = value;

	while (current > 0 && H->node[current].key < H->node[parent].key) {
		mh_swap(&H, current, parent);
	}

	H->filled++;
}

void bst_print(BSTNODE* t)
{
	if (t == NULL) return;
	printf("node[%d]:%d >", t->key, t->value);
	if (t->left != NULL) {
		printf("left [%d]:%d ", t->left->key, t->left->value);
	}
	if (t->right != NULL) {
		printf("right [%d]:%d", t->right->key, t->right->value);
	}
	printf("\n");
	if (t->left)
	{
		bst_print(t->left);
	}
	if (t->right)
	{
		bst_print(t->right);
	}
}

void mh_print(HEAP* t)
{
	for (int i = 0; i < t->filled; i++) {
		printf("[%d]:%d\n", t->node[i].key, t->node[i].value);
	}
	printf("\n");
}

void bst_push(BSTNODE* t)
{
	if (t == NULL) return;
	bst_push(t->left);
	result[result_cnt][0] = t->key;
	result[result_cnt][1] = t->value;
	result_cnt++;
	bst_push(t->right);
}

void mh_push(HEAP* t)
{
	int key;
	for (int i = 0; i < t->filled; i++) {
		key = t->node[i].key;
		for (int j = 0; j < result_cnt; j++) {
			if (result[j][0] == key) {
				result[j][1] += t->node[i].value;
			} else {
				result[result_cnt][0] = t->node[i].key;
				result[result_cnt][0] = t->node[i].value;
				result_cnt++;
			}
		}
	}
}

int main()
{
	BSTNODE* bst_root = NULL;
	HEAP* MH = mh_init(MaxRow);

	for (int i = 0; i < MaxRow; i++) {
		bst_addnode(&bst_root, bst[i][0], bst[i][1]);
	}

	for (int i = 0; i < MaxRow; i++) {
		mh_addnode(&MH, mh[i][0], mh[i][1]);
	}

	printf("binary search tree =====\n");
	bst_print(bst_root);
	printf("\n");
	printf("min heap =====\n");
	mh_print(MH);

	bst_push(bst_root);
	mh_push(MH);

	printf("result =====\n");
	for (int i = 0; i < result_cnt; i++) {
		printf("[%d]:%d", result[i][0], result[i][1]);
	}
	printf("\n");

	return 0;
}

2. min cost spanning tree

(a) 아래 그래프의 min cost spanning tree를 Sollin의 알고리즘으로 구하는 과정을 보이면서 설명하시오.

(b) 교재 Program 6.7에는 Kruskal의 알고리즘이, Program 6.8에는 Prim의 알고리즘이 각각 슈도코드로 기술되어 있다. Sollin의 알고리즘을 기술하는 슈도코드를 Program 6.7 및 Program 6.8과 명세하는 명령어의 상세 수준이 유사하도록 하여 쓰시오.

3. shortest path

(a) 아래 graph에서 0번 노드에서 모든 노드로의 shortest path를 수업시간에 공부한 교재의 Dijkstra의 알고리즘으로 구할 때 수업시간에 아래 형식의 표로 작성했던 방식대로 found 배열, distance 배열, predecessor 배열의 값이 변경되어 가는 과정을 알고리즘이 종료될 때까지 보이면서 설명하시오.

(b) 교재 Program 6.9는 그래프에서 shortest path를 구하는 과정에서 found[] 배열과 distance[] 배열만 사용한다. 이를 predecessor[] 배열도 사용하도록 하려면 프로그램의 어느 부분을 어떻게 수정해야 하는지 설명하시오.

(d) 교재 Program 6.9는 그래프가 adjacency matrix로 표현되어 있을 경우의 프로그램이다. 만약 그래프가 adjaceny list로 표현되었다면 프로그램의 어느 부분을 어떻게 수정해야 하는지 설명하시오. (c)의 adjaceny list 예를 이용하여 설명하시오.

4. maze

교재의 maze 알고리즘을 아래와 같이 수정할 경우 경로찾기를 수행하는 C 코드를 작성하고자 한다. 교재의 알고리즘과 차이가 생기는 부분의 코드를 C로 쓰고 왜 그런 차이가 필요한지 설명하시오.
수정 : 스택에 방향정보로 8 방향을 나타내는 8 bit 스트링을 저장하고 (가본 방향은 1 안가본 방향은 0)이 방향정보로부터 비트 연산 (AND, OR 등)을 통해 안가본 방향 중 임의의 방향을 선택하여 시도한다. (제출할 필요 X)

5. postfix

이항 사칙연산(+,-,*,/)으로 구성된 postfix식을 입력받아 해당 연산과정을 표현한 binary tree를 linked representation으로 생성하여 그것의 루트 노드로의 포인터를 반환하는 알고리즘 postfix2bintree()를 작성하고자 한다. 예: postfix 식 ABC*+$ 가 주어지면 ($는 string 끝 표시) 아래 binary tree가 생성되고 루트 노드(즉, + 노드)로의 포인터가 반환됨. postfix2bintree()를 슈도코드로 작성하시오. 단, postfix식의 operand는 1 char (예: A, B, ...)라 가정. 또한 postfix식의 다음 char를 반환해주는 get_next_char() 함수와 binary tree의 노드 하나를 할당해주는 get_node() 함수가 제공된다고 가정.

6. linked list

양의 정수를 원소로 하는 집합을 header가 있는 circular doubly linked list로 표현한다고 하자. 예를 들어, 집합 S = {1, 3, 9, 5}는 아래 그림과 같이 표현된다. (S가 가리키는 0 이 저장된 노드가 header 노드)

(a) 공집합 S = { }은 어떻게 표현되는지 그림으로 그리시오.

(b) 두 집합 S1과 S2의 교집합(∩) (예: S1={2, 3, 4}, S2={3, 4, 5}이면 S1 ∩ S2={3, 4})을 구하여 그 헤더 노드 포인터를 반환하는 함수 intersect(S1, S2)를 슈도코드로 작성하고자 한다. ‘가’ 로 표시된 곳을 채우시오.

intersect(S1, S2) {
	S := copy(S1) // copy(T) : 집합 T를 copy하여 생성된 리스트의 헤더 노드 포인터를 반환
    
	// S의 각 노드의 값이 S2에 없으면 해당 노드를 S에서 삭제함으로써 교집합 S를 구한다
	p := S->rlink // header 노드 오른쪽 다음 노드부터 시작
	while(p->data != 0) { // header 노드가 아니면 수행
		if( ! member(S2, p->data) ) { // member(T, n): 양의 정수 n 이 집합 T의 원소인지 테스트하여 n ∈ T이면 그 노드의 pointer를, n ∉T 이면 NULL을 반환

			// ‘가’ // p가 가리키는 노드를 삭제
		}
		p := p->rlink // 오른쪽 다음 노드
	}
	return(S)
}

728x90

저작자표시 비영리 변경금지

'College Computer Science > Data Structure' 카테고리의 다른 글

[자료구조 프로그래밍 연습문제] 힙 정렬 (heap sort) (0)	2022.01.28
[자료구조 프로그래밍 연습문제] 연결 리스트 (linked list) invert 함수, 원형 연결 리스트 (circular linked list) (0)	2022.01.12
[자료구조 프로그래밍 연습문제] 다항식 덧셈, 희소행렬 덧셈 (0)	2022.01.12
[자료구조 프로그래밍 연습문제] maze 미로 경로 찾기 (0)	2022.01.11
[자료구조 프로그래밍 연습문제] 희소행렬 전치 (0)	2022.01.11

Garden of Eden

[자료구조 프로그래밍 연습문제] 이진탐색트리 (binary search tree), 힙 (heap), min cost spanning tree, 전위표기식 (postfix), 연결 리스트 (linked list)

'College Computer Science > Data Structure' 카테고리의 다른 글

댓글

티스토리툴바

[자료구조 프로그래밍 연습문제] 이진탐색트리 (binary search tree), 힙 (heap), min cost spanning tree, 전위표기식 (postfix), 연결 리스트 (linked list)

'College Computer Science > Data Structure' 카테고리의 다른 글

관련글

댓글

티스토리툴바