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

자료구족발보쌈/1103

Difference between r1.1 and the current

@@ -35,7 +35,429 @@
== 박인서 ==

== 이원준 ==
=== 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);
}
}
}}}
 
=== 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);
}
}
}}}
== 남헌 ==

----

갓원준님의 추월


1. 참여자 명단


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

2. 수업

2.1. 진행

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

2.2. 내용

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

3. 코드

3.1. 예제1


4. 숙제

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



5. 숙제 제출

5.1. 천준현


5.2. 박인서


5.3. 이원준

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);
	}
}

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);
	}
}

5.4. 남헌

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