5.2. 박인서 ¶
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int val;
struct node* lnext;
struct node* rnext;
}node;
void push(node *, int);
int find(node *);
int pop(node *);
void swap(int *,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=find(&head);
if(a==-1) printf("숫자 없음\n");
else printf("%d가 있었다\n",a);
}
else printf("push나 pop이나 exit만 입력하라고...\n");
}
return 0;
}
void swap(int * a, int * b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
void push(node * target, int newval)
{
node * newnode;
int a=1,c,i,temp,flag=0;
int * b;
cnt++;
if(cnt==1)
{
target->val=newval;
target->lnext=NULL;
target->rnext=NULL;
return;
}
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;
}
newnode=(node *)malloc(sizeof(node));
temp=newval;
for(i=c-2;i>=1;i--)
{
if(target->val>newval) swap(&target->val,&newval);
if(b[i]==0) target=target->lnext;
else target=target->rnext;
}
if(target->val>newval) swap(&target->val,&newval);
newnode->val=newval,newnode->lnext=NULL,newnode->rnext=NULL;
if(b[0]==0) target->lnext=newnode;
else target->rnext=newnode;
free(b);
}
int find(node * target)
{
int res,regap;
node * imsi=(node *)malloc(sizeof(node));
imsi=target;
res=pop(target);
if(res==-1) return -1;
target=imsi;
regap=target->val;
target->val=res;
while(target->lnext!=NULL || target->rnext!=NULL)
{
if(target->lnext!=NULL && target->rnext!=NULL)
{
if(target->val>target->lnext->val && target->val>target->rnext->val)
{
if(target->lnext->val<=target->rnext->val)
{
swap(&target->val,&target->lnext->val);
target=target->lnext;
}
else
{
swap(&target->val,&target->rnext->val);
target=target->rnext;
}
}
else if(target->val>target->lnext->val)
{
swap(&target->val,&target->lnext->val);
target=target->lnext;
}
else if(target->val>target->rnext->val)
{
swap(&target->val,&target->rnext->val);
target=target->rnext;
}
else break;
}
else if(target->lnext!=NULL)
{
if(target->val>target->lnext->val)
{
swap(&target->val,&target->lnext->val);
target=target->lnext;
}
else break;
}
else if(target->rnext!=NULL)
{
if(target->val>target->rnext->val)
{
swap(&target->val,&target->rnext->val);
target=target->rnext;
}
else break;
}
else break;
}
return regap;
}
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;
}
5.3. 이원준 ¶
짜다맘(미완성)
#include <stdio.h>
#include <stdlib.h>
typedef struct _node{
struct _node *Rnode;
struct _node *Lnode;
int var;
} node;
typedef struct _PQ{
node *one;
int num;
} PQ;
void push(PQ *head, int input){
node *temp = (node*)malloc(sizeof(node));
int past;
int i, j;
temp->var = input;
if (head->num == 0){
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 = num1;
for (i = 0; i < num1 - 1 - j; i++){
past = past / 2;
}
if (past % 2 == 0){
dir = dir->Lnode;
}
else{
dir = dir->Rnode;
}
}
if (num1 % 2 == 0){
dir->Lnode = temp;
}
else{
dir->Rnode = temp;
}
(head->num)++;
past = num1;
while (past != 1){
}
}
int main(){
PQ PQhead;
PQhead.num = 0;
}
