[C언어로 쉽게 풀어쓴 자료구조] 9장 우선순위 큐 연습문제 해설

출처 : https://www.booksr.co.kr/product/9788970509716/

 

1. 1

2. 3

3. 2

4. 1

5. 2

6. 2번노드와 3번노드 중 더 작은 값을 가지고 있는 노드가 2번째로 작은 데이터를 가지고 있는 노드이다.

7. 완전이진트리로 높이가 4가 된다.

11. 

typedef struct element {
	char todo[50] = {};
	int prior;
}element;

14.

#include<stdio.h>
#include<stdlib.h>
#define MAX_ELEMENT 200
#define MAX 987654321
#define MIN -987654321

typedef struct {
	int heap[MAX_ELEMENT];
	int heap_size;
}HeapType;

void init(HeapType* h) {
	h->heap_size = 0;
}

void insert_max_heap(HeapType* h, int item) {
	h->heap[h->heap_size] = item;
	h->heap_size++;
}

int delete_max_heap(HeapType* h) {
	int m = MIN, index;
	for (int i = 0; i < h->heap_size; i++) {
		if (h->heap[i] > m) {
			m = h->heap[i];
			index = i;
		}
	}
	for (int i = index; i < h->heap_size; i++)
		h->heap[i] = h->heap[i + 1];
	h->heap_size--;

	return m;
}

bool is_empty(HeapType* h) {
	return h->heap_size == 0;
}

bool is_full(HeapType* h) {
	return h->heap_size == MAX_ELEMENT;
}

int find_max_heap(HeapType* h) {
	int m = MIN;
	for (int i = 0; i < h->heap_size; i++) {
		if (h->heap[i] > m)
			m = h->heap[i];
	}
	return m;
}

15.

#include<stdio.h>
#include<stdlib.h>
#define MAX_ELEMENT 200
#define MAX 987654321
#define MIN -987654321

typedef struct HeapType{
	int data;
	struct HeapType* link;
}HeapType;


HeapType* create_node(int data) {
	HeapType* new_node;
	new_node = (HeapType*)malloc(sizeof(new_node));
	new_node->data = data;
	new_node->link = NULL;
	return new_node;
}

void insert_max_heap(HeapType** phead, HeapType* new_node) {
	if (*phead == NULL) {
		new_node->link = NULL;
		*phead = new_node;
	}
	else {
		new_node->link = NULL;
		HeapType* p = *phead;
		while (p->link != NULL)
			p = p->link;
		p->link = new_node;
	}
}

int pop_max_heap(HeapType** head) {
	int m = MIN;
	HeapType* p = NULL, * removed = *head;
	HeapType* temp1 = NULL, * temp2 = *head;
	while (removed != NULL) {
		if (removed->data > m) {
			m = removed->data;
			temp1 = p;
			temp2 = removed;
		}
		p = removed;
		removed = removed->link;
	}

	if (temp1 == NULL)
		*head = (*head)->link;
	else
		temp1->link = temp2->link;

	return m;
}


bool is_empty(HeapType* h) {
	return h == NULL;
}

bool is_full(HeapType* h) {
	HeapType* n;
	n = (HeapType*)malloc(sizeof(n));
	return n == NULL;
}

int find_max_heap(HeapType* h) {
	int m = MIN;
	HeapType* p = h;
	while (p != NULL) {
		if (p->data > m)
			m = p->data;
		p = p->link;
	}
	return m;
}

16.

int delete_some_heap(HeapType* h, int key) {
	int p, c;
	for(int i = 1; i <= h->heap_size; i++)
		if (h->heap[i] == key) {
			p = i;
			c = 2 * i;
			break;
		}

	int item = h->heap[p], temp = h->heap[(h->heap_size)--];
	while (c <= h->heap_size) {
		if ((c < h->heap_size) && (h->heap[c] < h->heap[c + 1]))
			c++;
		if (temp >= h->heap[c])
			break;
		h->heap[p] = h->heap[c];
		p = c;
		c *= 2;
	}
	h->heap[p] = temp;
	return item;
}

 

관심이 있으신 분들에게 유용한 정보였길 바라며

다음은 10장 핵심정리를 가져오도록 하겠습니다.