자료구조 과제 #3

/*
Data Structure Assignment #3
Spring, 2006
Due Date: 2006. 5. 8. Monday 6:00 PM.

주어진 input sequence에 대하여 heap을 구성하여 array에 저장하고 이를 in-order(type 1), pre-order(type 2), post-order(type 3), level-order(type 4)로 저장하는 프로그램을 작성 하시오. 속도에 따라 점수가 부여된다. 따라서, heap은 array에 저장되어야 하고 traversal은 iterative한 방법을 사용해야 한다 (recursive한 프로그램은 0점 처리).

예:
? Input:
10 // number of item
2 // traversal type
1 3 20 61 91 123 8 71 32 21 // items

30
1
30 40 13 12 11 .....

:
:

-1 // end of input

첫 번째 input으로부터의 max heap은 다음과 같다.

   123
          /   /    \
71   /   91
     /      /
61  21  3  8
  /       /       \
  1    32    20

123719161213813220

? Output:
123 71 61 1 32 21 20 91 3 8 // preorder traversal (because traversal type = 2)
123 71 61 1 32 21 20 91 3 8
0.034 // 수행속도 (입출력 시간 제외, 소수점 3자리)

40 30 13 12 11 ....
0.040

.
제한 사항
1. Input item의 개수는 최대 100000개입니다.

2. Input은 C:\ass3_input.txt에서 입력 받아서 C:\학번_이름_반.txt에 출력하면 된다.
예)출력 파일 c:\200621094_홍길동_A.txt

3.제출시 파일명은 "학번_이름_반"으로 작성하세요. 여기서 반은 과제물 제출 게시판의 반입니다.(A,B,C) 실행 파일과  C파일 두 개를 올려주세요.
예) 200621094_홍길동_A.exe /200621094_홍길동_A.c

4.소스 파일과 실행 파일을 압축하지 말고 올려주세요.  

5. c:\ 폴더에 실행파일이 없을 경우에도 동작해야 합니다.

6.변동 사항이 있을 수 있으니 공지 사항을 꼭 확인해 주세요.

7.과제물 제출 시 반드시 비밀글을 체크하시고 올리셔야 합니다. 

*/
ac
#include<stdio.h>
#include<windows.h>

#define IN_FILE "c:\\ass3_input.txt"
#define OUT_FILE "c:\\200120993_이지황_B.txt"

struct time{
LARGE_INTEGER   st, ed, freq ;
  double          gap ;
  BOOL            bEnable;
  char            szName[256];
  UINT            counter;
  double          fTotal_Time;
}mytime;

struct dat{
int num; // number of input datas
int type;
int *heap, *temp, *out; 
}data;

void inorder(void) // when case 1,
{
int i=1, j=1;
for( ; i<=data.num/2; i*=2);
 
while(1)
{     
if(i == 1)
{
  data.out[j++] = data.heap[i];
  data.temp[i] = -1;
  for(i=i*2+1; i<=data.num/2; i*=2);
}
else
{
  if(i*2 <= data.num && data.temp[i*2] != -1)
  {
   data.out[j++] = data.heap[i*2];
   data.temp[i*2] = -1;
  }

  if(data.temp[i] != -1)
  {
   data.out[j++] = data.heap[i];
   data.temp[i] = -1;
  }
   
  if(i*2+1 <= data.num && data.temp[i*2+1]!= -1)
  {
   for(i=i*2+1; i<=data.num/2; i*=2);
   continue;
  }
  //printf("i:%d j:%d\n",i,j);
}
i/=2;
if(j>data.num) break;
}
}

void preorder(void) // when case 2,
{
int i=1, j=1;

while(1)
{
for( ; i<=data.num; i*=2)
{
  if(data.temp[i]!= -1)
  {
   data.out[j++]=data.heap[i];
   data.temp[i]= -1;
  }
}
if(i/2-1>=data.num)
{
  i=i/2+1;
  data.out[j++]=data.heap[i];
  data.temp[i]= -1;
}

i=i/2+1;

if(i%2==0)
{
  while(i%2==0)
  i=i/2;
}
if(j>data.num)
  break;
}

}

void postorder(void) // when case 3,
{
int i=1, j=1;  
for( ; i<=data.num/2; i*=2);
 
while(1)
{     
if(data.temp[i]!= -1)
{
  data.out[j++]=data.heap[i];
  data.temp[i]=-1;
}

if(i+1<=data.num && data.temp[i+1]!= -1 && (i+1)%2==1) 
{
  i++;
  if(i*2<=data.num)
  {
   for( ; i<=data.num/2; i*=2);
   continue;
  }
  data.out[j++] = data.heap[i];
  data.temp[i]= -1;
}

i/=2;
if(j > data.num) break;
}
}

static void Start()
{
mytime.gap = 0.0;  // init
mytime.bEnable = FALSE;
mytime.counter = 0;
mytime.fTotal_Time = 0.0;

// system test
QueryPerformanceCounter ( &mytime.st ) ;
if ( mytime.st.QuadPart == 0 )
{
mytime.bEnable= FALSE;
OutputDebugString("시스템이 지원이 안됨,,, 사용할 수 없음[CTimeCounter Class]\n");
}

// start()
mytime.counter ++;
QueryPerformanceCounter ( &mytime.st ) ;
}

static void End()
{
char szMsg[64];

QueryPerformanceCounter ( &mytime.ed ) ;
QueryPerformanceFrequency ( &mytime.freq ) ;

// 소요 시간 계산
mytime.gap = ( (double) (mytime.ed.QuadPart - mytime.st.QuadPart )) / ( (double) mytime.freq.QuadPart ) ;
mytime.fTotal_Time += mytime.gap;

sprintf ( szMsg, "수행시간 %.6f초\n", mytime.gap) ;
OutputDebugString(szMsg);
}

int read(FILE *in_file)
{
int i;
fscanf(in_file,"%d",&data.num);
if(data.num== -1) return 0;
else
{
data.heap=(int*)malloc(sizeof(int)*(data.num+1)); // memory allocation
data.temp=(int*)malloc(sizeof(int)*(data.num+1));
data.out= (int*)malloc(sizeof(int)*(data.num+1));

fscanf(in_file,"%d",&data.type);

for(i=1; i<=data.num; i++)
{
  fscanf(in_file,"%d",&data.temp[i]);
}
}
return 1;
}

void sort(FILE *out_file)
{
int i,j,tmp;
int flaglevelorder=0;

Start(); // clock starts

// max heap insertion occurs here.
for(i=1; i<=data.num; i++)
{
data.heap[i]=data.temp[i];
for(j=i; j>1; j/=2)
{
  if(data.heap[j]<data.heap[j/2]) break;
  else
  {
   tmp=data.heap[j/2];
   data.heap[j/2]=data.heap[j];
   data.heap[j]=tmp;
  }
}
}

switch(data.type)
{
case 1:
inorder();
break;
case 2:
preorder();
break;
case 3:
postorder();
break;
case 4: //level-order
flaglevelorder=1;
//for(i=1; i<=data.num; i++) data.out[i]=data.heap[i];
break;
}

End(); // clock stops

if(flaglevelorder)
{
for(i=1;i<=data.num;i++) fprintf(out_file, "%d ", data.heap[i]);
}
else
{
for(i=1;i<=data.num;i++) fprintf(out_file, "%d ", data.out[i]);
}

fprintf(out_file,"\n%5.3f\n\n", mytime.fTotal_Time);

free(data.heap); // unallocation of memory
free(data.temp);
free(data.out);
}

void main(void)
{
FILE *infile, *outfile;

infile=fopen(IN_FILE,"r");
outfile=fopen(OUT_FILE,"w");

while(read(infile)) sort(outfile);

fclose(infile);
fclose(outfile);
}