More actions
2학기가 밝았습니다. 모두들 고통 받을 준비 하세요.
참여자 명단
| 함장 | 장용운 | 11학번 | 출석 |
| 선원 | 천준현 | 15학번 | 출석 |
| 최지혁 | 집감 | ||
| 박인서 | 출석 | ||
| ~~이정재~~ | ~~탈주~~ | ||
| 이원준 | 출석 | ||
| 조종현 | 공강 | ||
| 남헌 | 출석 |
수업
진행
- 장소 : 6층 학회실
- 시간 : 15시~17시
내용
수심 3000m. 트리
- 완전 이진 트리 만들기(push, pop)
~~수심이 계속 안 내려가는 것처럼 보이는 것은 기분 탓입니다.~~
코드
예제1
숙제
- 완성하지 못한 완전 이진 트리 완성해오기
숙제 제출
천준현
최지혁
박인서
//고통받기를 시작합니다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node{
int val;
struct node* lnext;
struct node* rnext;
}node;
void push(node *, int);
int pop(node *);
int find(node * ,int);
long cnt=1;
int main()
{
int a;
char ch[5];
node head;
printf("초기값 설정 ㄱㄱ\n");
scanf("%d",&head.val);
head.lnext=NULL;
head.rnext=NULL;
for(;;)
{
printf("push나 pop이나 exit 입력(push/pop/exit)\n");
scanf("%s",ch);
if(ch[0]=='e' && ch[1]=='x' && ch[2]=='i' && ch[3]=='t') break;
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;
}