U E D R , A S I H C RSS

자료구족발보쌈/0915

인간의 실수는 끝이 없고 같은 고통을 반복한다.


1. 참여자 명단


함장 장용운 11학번 출석
선원 천준현 15학번 중동
최지혁 출석
박인서 출석
이원준 지각
조종현 공강
남헌 출석

2. 수업

2.1. 진행

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

2.2. 내용

수심 3000m. 트리
  • 완전 이진트리에서 index주면 값찾기
  • 이진트리 사이에 node 삽입하기
빈부격차가 커지는 중

3. 코드

3.1. 예제1


4. 숙제

1. 트리내용 복습하기




5. 숙제 제출

5.1. 천준현


5.2. 최지혁


5.3. 박인서

5.3.1. index로 값찾기

//고통받기를 시작합니다.
#include <stdio.h>
#include <stdlib.h>

typedef struct node{
	int val;
	struct node* lnext;
	struct node* rnext;
}node;

void push(node *, int);
int pop(node *);
node * find(node *, int);
long cnt=1;

int main()
{
	int a;
	char ch[5];
	node head;
	node * findnode;
	printf("초기값 설정 ㄱㄱ\n");
	scanf("%d",&head.val);
	head.lnext=NULL;
	head.rnext=NULL;
	for(;;)
	{
		printf("push나 pop이나 find나 exit 입력(push/pop/find/exit)\n");
		scanf("%s",ch);
		if(ch[0]=='e' && ch[1]=='x' && ch[2]=='i' && ch[3]=='t') break;
		else if(ch[0]=='f' && ch[1]=='i' && ch[2]=='n' && ch[3]=='d')
		{
			printf("인덱스 입력 ㄱㄱ : ");
			scanf("%d",&a);
			if(a>=cnt)
			{
				printf("범위를 넘어섬 ㅂㅅ아\n");
			}
			else
			{
				findnode=find(&head,a);
				printf("니가 찾는거 : %d\n",findnode->val);
			}
		}
		else if(ch[0]=='p' && ch[1]=='u' && ch[2]=='s' && ch[3]=='h')
		{
			printf("넣을 숫자 입력 ㄱㄱ(자연수만) : ");
			scanf("%d",&a);
			push(&head,a);
		}
		else if(ch[0]=='p' && ch[1]=='o' && ch[2]=='p')
		{
			a=pop(&head);
			if(a==-1) printf("숫자 없음 ㅂㅅ아\n");
			else printf("%d가 있었다 ㅂㅅ아\n",a);
		}
		else
		{
			printf("push나 pop이나 exit만 입력하라고...\n");
		}
	}
	return 0;
}

void push(node * target, int newval)
{
	node * newnode=(node *)malloc(sizeof(node));
	int a=1,c,i;
	int * b;
	cnt++;
	for(c=1;;c++)
	{
		if(a<=cnt && cnt<2*a) break;
		a*=2;
	}
	a=cnt;
	b=(int *)malloc((sizeof(int))*c);
	for(i=0;i<c;i++)
	{
		if(a%2==0) b[i]=0;
		else b[i]=1;
		a/=2;
	}
	for(i=c-2;i>=1;i--)
	{
		if(b[i]==0)
			target=target->lnext;
		else
			target=target->rnext;
	}
	newnode->val=newval;
	newnode->lnext=NULL;
	newnode->rnext=NULL;
	if(b[0]==0) target->lnext=newnode;
	else target->rnext=newnode;
	free(b);
}

int pop(node * target)
{
	int a=1,c,i;
	int * b;
	if(cnt==0) return -1;
	if(cnt==1)
	{
		cnt--;
		return target->val;
	}
	for(c=1;;c++)
	{
		if(a<=cnt && cnt<2*a) break;
		a*=2;
	}
	a=cnt;
	b=(int *)malloc((sizeof(int))*c);
	for(i=0;i<c;i++)
	{
		if(a%2==0) b[i]=0;
		else b[i]=1;
		a/=2;
	}
	for(i=c-2;i>=1;i--)
	{
		if(b[i]==0)
			target=target->lnext;
		else
			target=target->rnext;
	}
	if(b[0]==0)
	{
		a=target->lnext->val;
		free(target->lnext);
		target->lnext=NULL;
	}
	else
	{
		a=target->rnext->val;
		free(target->rnext);
		target->rnext=NULL;
	}
	free(b);
	cnt--;
	return a;
}
node * find(node * root,int index)
{
		int a=1,c,i;
	int * b;
	if(index==0)
	{
		return root;
	}
	index++;
	for(c=1;;c++)
	{
		if(a<=index && index<2*a) break;
		a*=2;
	}
	a=index;
	b=(int *)malloc((sizeof(int))*c);
	for(i=0;i<c;i++)
	{
		if(a%2==0) b[i]=0;
		else b[i]=1;
		a/=2;
	}
	for(i=c-2;i>=0;i--)
	{
		if(b[i]==0)
			root=root->lnext;
		else
			root=root->rnext;
	}
	return root;
}

5.3.2. 이진트리 사이에 node 삽입

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

typedef struct node{
	int val;
	struct node* lnext;
	struct node* rnext;
}node;

void push(node *, int);
int pop(node *);
node * find(node *, int);
void doing(node *, int, int);
long cnt=1;

int main()
{
	int a,b;
	char ch[6];
	node * findnode;
	node head;
	printf("초기값 설정 ㄱㄱ\n");
	scanf("%d",&head.val);
	head.lnext=NULL;
	head.rnext=NULL;
	for(;;)
	{
		printf("push나 pop이나 find나 doing이나 exit 입력(push/pop/find/doing/exit)\n");
		scanf("%s",ch);
		if(ch[0]=='e' && ch[1]=='x' && ch[2]=='i' && ch[3]=='t') break;
		else if(ch[0]=='f' && ch[1]=='i' && ch[2]=='n' && ch[3]=='d')
		{
			printf("인덱스 입력 ㄱㄱ : ");
			scanf("%d",&a);
			findnode=find(&head,a);
			printf("니가 찾는거 : %d\n",findnode->val);
		}
		else if(ch[0]=='d' && ch[1]=='o' && ch[2]=='i' && ch[3]=='n' && ch[4]=='g')
		{
			printf("인덱스 입력 ㄱㄱ : ");
			scanf("%d",&a);
			printf("넣을 숫자 입력 ㄱㄱ(자연수만) : ");
			scanf("%d",&b);
			doing(&head,a,b);
		}
		else if(ch[0]=='p' && ch[1]=='u' && ch[2]=='s' && ch[3]=='h')
		{
			printf("넣을 숫자 입력 ㄱㄱ(자연수만) : ");
			scanf("%d",&a);
			push(&head,a);
		}
		else if(ch[0]=='p' && ch[1]=='o' && ch[2]=='p')
		{
			a=pop(&head);
			if(a==-1) printf("숫자 없음 ㅂㅅ아\n");
			else printf("%d가 있었다 ㅂㅅ아\n",a);
		}
		else
		{
			printf("push나 pop이나 exit만 입력하라고...\n");
		}
	}
	return 0;
}

void push(node * target, int newval)
{
	node * newnode=(node *)malloc(sizeof(node));
	int a=1,c,i;
	int * b;
	cnt++;
	for(c=1;;c++)
	{
		if(a<=cnt && cnt<2*a) break;
		a*=2;
	}
	a=cnt;
	b=(int *)malloc((sizeof(int))*c);
	for(i=0;i<c;i++)
	{
		if(a%2==0) b[i]=0;
		else b[i]=1;
		a/=2;
	}
	for(i=c-2;i>=1;i--)
	{
		if(b[i]==0)
			target=target->lnext;
		else
			target=target->rnext;
	}
	newnode->val=newval;
	newnode->lnext=NULL;
	newnode->rnext=NULL;
	if(b[0]==0) target->lnext=newnode;
	else target->rnext=newnode;
	free(b);
}

int pop(node * target)
{
	int a=1,c,i;
	int * b;
	if(cnt==0) return -1;
	if(cnt==1)
	{
		cnt--;
		return target->val;
	}
	for(c=1;;c++)
	{
		if(a<=cnt && cnt<2*a) break;
		a*=2;
	}
	a=cnt;
	b=(int *)malloc((sizeof(int))*c);
	for(i=0;i<c;i++)
	{
		if(a%2==0) b[i]=0;
		else b[i]=1;
		a/=2;
	}
	for(i=c-2;i>=1;i--)
	{
		if(b[i]==0)
			target=target->lnext;
		else
			target=target->rnext;
	}
	if(b[0]==0)
	{
		a=target->lnext->val;
		free(target->lnext);
		target->lnext=NULL;
	}
	else
	{
		a=target->rnext->val;
		free(target->rnext);
		target->rnext=NULL;
	}
	free(b);
	cnt--;
	return a;
}

node * find(node * root,int index)
{
		int a=1,c,i;
	int * b;
	if(index==0)
	{
		return root;
	}
	index++;
	for(c=1;;c++)
	{
		if(a<=index && index<2*a) break;
		a*=2;
	}
	a=index;
	b=(int *)malloc((sizeof(int))*c);
	for(i=0;i<c;i++)
	{
		if(a%2==0) b[i]=0;
		else b[i]=1;
		a/=2;
	}
	for(i=c-2;i>=0;i--)
	{
		if(b[i]==0)
			root=root->lnext;
		else
			root=root->rnext;
	}
	return root;
}

void doing(node * root,int index,int val)
{
	int a=1,c,i;
	int * b;
	node * newnode=(node *)malloc(sizeof(node));
	node * temp;
	newnode->val=val;
	if(index==0)
	{
		newnode->lnext=root;
		root=newnode;
		return;
	}
	if(index==1)
	{
		temp=root;
		newnode->lnext=root->lnext;
		root->lnext=newnode;
		return;
	}
	if(index==2)
	{
		temp=root;
		newnode->rnext=root->rnext;
		root->rnext=newnode;
		return;
	}
	index++;
	for(c=1;;c++)
	{
		if(a<=index && index<2*a) break;
		a*=2;
	}
	a=index;
	b=(int *)malloc((sizeof(int))*c);
	for(i=0;i<c;i++)
	{
		if(a%2==0) b[i]=0;
		else b[i]=1;
		a/=2;
	}
	for(i=c-2;i>0;i--)
	{
		if(b[i]==0)
			root=root->lnext;
		else
			root=root->rnext;
	}
	if(b[0]==0)
	{
		temp=root;
		newnode->lnext=root->lnext;
		root->lnext=newnode;
	}
	else
	{
		temp=root;
		newnode->rnext=root->rnext;
		root->rnext=newnode;
	}
	return;
}

5.4. 이원준


5.5. 조종현


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