U E D R , A S I H C RSS
ZeroWiki

자료구족발보쌈/1103

갓원준님의 추월


[edit]

1. 참여자 명단


함장 장용운 11학번 출석
선원 천준현 15학번 병결
박인서 출석
이원준 출석
남헌 출석

[edit]

2. 수업

[edit]

2.1. 진행

1. 장소 : 6층 학회실
2. 시간 : 15시 ~ 17시

[edit]

2.2. 내용

수심 4000m. 트리2
  • 우선순위 큐(priority와 value 분리)
  • heapify
[edit]

3. 코드

[edit]

3.1. 예제1


[edit]

4. 숙제

1. 고통받기
2. 고통받기
3. 고통받기



[edit]

5. 숙제 제출

[edit]

5.1. 천준현


[edit]

5.2. 박인서


[edit]

5.3. 이원준

[edit]

5.3.1. key가 따로있는 heapmax 

#include <stdio.h>
#include <stdlib.h>

typedef struct _node{
	struct _node *Rnode;
	struct _node *Lnode;
	char *name;
	int var;
} node;

typedef struct _PQ{
	node *one;
	int num; // num-1이 들어있는 갯수
} PQ;


void push(PQ *head,char *name, int input){
	node *temp = (node*)malloc(sizeof(node));
	int temp_n;
	char *temp_name;
	int past;
	int i, j;
	
	temp->Lnode = NULL;
	temp->Rnode = NULL;

	if (head->num == 1){
		temp->var = input;
		temp->name = name;
		head->one = temp;
		(head->num) += 1;
		return;
	}
	node *dir = head->one;
	int num = head->num;
	int num1 = 0;
	while (num != 1){
		num = num / 2;
		num1++;
	}

	for (j = 0; j < num1 - 1; j++){
		past = head->num;
		for (i = 0; i < num1 - 1 - j; i++){
			past = past / 2;
		}
		if (dir->var < input){
			temp_n = input;
			input = dir->var;
			dir->var = temp_n;
			temp_name = name;
			name = dir->name;
			dir->name = temp_name;

		}
		if (past % 2 == 0){
			dir = dir->Lnode;
		}
		else{
			dir = dir->Rnode;
		}
	}
	if (dir->var < input){
		temp_n = input;
		input = dir->var;
		dir->var = temp_n;
		temp_name = name;
		name = dir->name;
		dir->name = temp_name;
	}
	temp->var = input;
	temp->name = name;
	if (head->num % 2 == 0){
		dir->Lnode = temp;
	}
	else{
		dir->Rnode = temp;
	}
	(head->num)++;
}

void pop(PQ *head){
	int i, j;
	int num = (head->num) - 1;
	int num1 = 0;
	int temp;
	char *name;
	node *dir = head->one;
	if (num == 0){
		printf("안돼 돌아가 없어!\n");
		return;
	}

	printf("%s\n", dir->name);

	if (num == 1){
		free(head->one);
		(head->num)--;
		return;
	}

	while (num != 1){
		num = num / 2;
		num1++;
	}
	for (j = 0; j < num1-1; j++){
		num = (head->num) - 1;
		for (i = 0; i < num1 -1 - j; i++){
			num = num / 2;
		}
		if (num % 2 == 0){
			dir = dir->Lnode;
		}
		else{
			dir = dir->Rnode;
		}
	}

	num = (head->num) - 1;
	if (num % 2 == 0){
		temp = dir->Lnode->var;
		name = dir->Lnode->name;
		free(dir->Lnode);
		dir->Lnode = NULL;
	}
	else{
		temp = dir->Rnode->var;
		name = dir->Rnode->name;
		free(dir->Rnode);
		dir->Rnode = NULL;
	}
	(head->num)--;
	dir = head->one;

	while(1){
		if (dir->Lnode == NULL){
			dir->var = temp;
			dir->name = name;
			break;
		}
		else if (dir->Rnode == NULL){
			if (dir->Lnode->var > temp){
				dir->var = dir->Lnode->var;
				dir->Lnode->var = temp;
				dir->Lnode->name = dir->Lnode->name;
				dir->Lnode->name = name;
				break;
			}
			else{
				dir->var = temp;
				dir->name = name;
				break;
			}
		}
		else if (dir->Lnode->var > dir->Rnode->var && dir->Lnode->var > temp){
			dir->var = dir->Lnode->var;
			dir->name = dir->Lnode->name;
			dir = dir->Lnode;
		}
		else if (dir->Rnode->var > dir->Lnode->var && dir->Rnode->var > temp){
			dir->var = dir->Rnode->var;
			dir->name = dir->Rnode->name;
			dir = dir->Rnode;
		}
		else{
			dir->var = temp;
			dir->name = name;
			break;
		}
	}

}
int main(){
	PQ *PQhead = (PQ *)malloc(sizeof(PQ));
	int i;
	PQhead->num = 1;
	push(PQhead, "천준현", 2);
	push(PQhead, "남헌", 9);
	push(PQhead, "박인서", 8);
	push(PQhead, "이원준", 10);
	push(PQhead, "유재범", 2);
	for (i = 0; i < 6; i++){
		pop(PQhead);
	}
}

[edit]

5.3.2. heapify 

#include <stdio.h>
#include <stdlib.h>

typedef struct _node{
	struct _node *Rnode;
	struct _node *Lnode;
	char *name;
	int var;
} node;

typedef struct _PQ{
	node *one;
	int num; // num-1이 들어있는 갯수
} PQ;

void down(node *dir){
	char* name;
	int temp;

	if (dir->Lnode != NULL){
		down(dir->Lnode);
		if (dir->Rnode != NULL){
			down(dir->Rnode);
		}
	}

	if (dir->Lnode == NULL){
		return;
	}
	else if (dir->Rnode == NULL){
		if (dir->Lnode->var < dir->var){
			temp = dir->Lnode->var;
			dir->Lnode->var = dir->var;
			dir->var = temp;
			name = dir->Lnode->name;
			dir->Lnode->name = dir->name;
			dir->name = name;
		}
	}
	else if (dir->Lnode->var < dir->Rnode->var && dir->Lnode->var < dir->var){
		temp = dir->Lnode->var;
		dir->Lnode->var = dir->var;
		dir->var = temp;
		name = dir->Lnode->name;
		dir->Lnode->name = dir->name;
		dir->name = name;
	}
	else if (dir->Rnode->var < dir->Lnode->var && dir->Rnode->var < dir->var){
		temp = dir->Rnode->var;
		dir->Rnode->var = dir->var;
		dir->var = temp;
		name = dir->Rnode->name;
		dir->Rnode->name = dir->name;
		dir->name = name;
	}
}

void heapify(PQ *head){

	if (head->num == 1){
		return;
	}

	node *dir = head->one;
	int num = head->num;
	int num1 = 0;

	down(dir);
}

void pop(PQ *head){
	int i, j;
	int num = (head->num) - 1;
	int num1 = 0;
	int temp;
	char *name;
	node *dir = head->one;
	if (num == 0){
		printf("안돼 돌아가 없어!\n");
		return;
	}

	printf("%s\n", dir->name);

	if (num == 1){
		free(head->one);
		(head->num)--;
		return;
	}

	while (num != 1){
		num = num / 2;
		num1++;
	}
	for (j = 0; j < num1 - 1; j++){
		num = (head->num) - 1;
		for (i = 0; i < num1 - 1 - j; i++){
			num = num / 2;
		}
		if (num % 2 == 0){
			dir = dir->Lnode;
		}
		else{
			dir = dir->Rnode;
		}
	}

	num = (head->num) - 1;
	if (num % 2 == 0){
		temp = dir->Lnode->var;
		name = dir->Lnode->name;
		free(dir->Lnode);
		dir->Lnode = NULL;
	}
	else{
		temp = dir->Rnode->var;
		name = dir->Rnode->name;
		free(dir->Rnode);
		dir->Rnode = NULL;
	}
	(head->num)--;
	dir = head->one;
	dir->var = temp;
	dir->name = name;

	while (1){
		if (dir->Lnode == NULL){
			dir->var = temp;
			dir->name = name;
			break;
		}
		else if (dir->Rnode == NULL){
			if (dir->Lnode->var < temp){
				dir->var = dir->Lnode->var;
				dir->Lnode->var = temp;
				dir->name = dir->Lnode->name;
				dir->Lnode->name = name;
				break;
			}
			else{
				dir->var = temp;
				dir->name = name;
				break;
			}
		}
		else if (dir->Lnode->var < dir->Rnode->var && dir->Lnode->var < temp){
			dir->var = dir->Lnode->var;
			dir->name = dir->Lnode->name;
			dir = dir->Lnode;
		}
		else if (dir->Rnode->var < dir->Lnode->var && dir->Rnode->var < temp){
			dir->var = dir->Rnode->var;
			dir->name = dir->Rnode->name;
			dir = dir->Rnode;
		}
		else{
			dir->var = temp;
			dir->name = name;
			break;
		}
	}

}

void push(PQ *head, char *name, int input){
	node *temp = (node*)malloc(sizeof(node));
	int temp_n;
	char *temp_name;
	int past;
	int i, j;

	temp->Lnode = NULL;
	temp->Rnode = NULL;

	if (head->num == 1){
		temp->var = input;
		temp->name = name;
		head->one = temp;
		(head->num) += 1;
		return;
	}
	node *dir = head->one;
	int num = head->num;
	int num1 = 0;
	while (num != 1){
		num = num / 2;
		num1++;
	}

	for (j = 0; j < num1 - 1; j++){
		past = head->num;
		for (i = 0; i < num1 - 1 - j; i++){
			past = past / 2;
		}
		if (past % 2 == 0){
			dir = dir->Lnode;
		}
		else{
			dir = dir->Rnode;
		}
	}
	

	temp->var = input;
	temp->name = name;
	if (head->num % 2 == 0){
		dir->Lnode = temp;
	}
	else{
		dir->Rnode = temp;
	}
	(head->num)++;
}


int main(){
	PQ *PQhead = (PQ *)malloc(sizeof(PQ));
	int i;
	PQhead->num = 1;

	push(PQhead, "천준현", 2);
	push(PQhead, "남헌", 9);
	push(PQhead, "박인서", 8);
	push(PQhead, "이원준", 10);
	push(PQhead, "유재범", 2);
	heapify(PQhead);

	for (i = 0; i < 6; i++){
		pop(PQhead);
	}
}
[edit]

5.4. 남헌

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:30:38
Processing time 0.0197 sec