자료구족발보쌈/0915

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

참여자 명단

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

수업

진행

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

내용

수심 3000m. 트리

• 완전 이진트리에서 index주면 값찾기
• 이진트리 사이에 node 삽입하기

~~빈부격차가 커지는 중~~

코드

숙제

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

이진트리 사이에 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;
}

남헌

---

---

활동지도/2015 자료구족발보쌈