'자료구조'에 해당되는 글 4건

  1. 2006.05.31 Linear Shifted Array Generator
  2. 2006.05.10 자료구조 과제 #2
  3. 2006.05.10 자료구조 과제 #1
  4. 2006.03.27 숫자 generator 프로그램

Linear Shifted Array Generator

Posted by !kKo geek_stuff/today : 2006.05.31 09:20

Linear Shifted Array Generator by !kKo

output_file<<((end-start)/shift)+1<<endl; // number of entries...

int j=0;
for (int i=start; i<=end; i=i+shift) // making array
{
  array[j++]=i;
}
 
//  Uncomment the following line to display the whole array.
// for (i=0;i<(end-start)/shift;i++){cout<<array[i]<<" ";} cout<<endl;
 
for (i=shift;i<=(end-start)/shift;i++) // writing to file
{
  output_file<<array[i]<<" ";
}
for (i=0;i<shift;i++) // writing to file
{
  output_file<<array[i];
  if(i<shift-1) output_file<<" ";
}
output_file<<endl;

Download Full Source Code
신고

'geek_stuff > today' 카테고리의 다른 글

맥북을 지를까..  (3) 2006.06.21
HSBC의 OTP (One time password) device.  (3) 2006.06.01
Linear Shifted Array Generator  (0) 2006.05.31
Tistory 초대권 응모관련...  (17) 2006.05.27
Tistory.com Beta에서의 첫 글  (3) 2006.05.26
1kko.com 블로그의 변천사  (0) 2006.05.21
태그 : 자료구조

자료구조 과제 #2

Posted by !kKo geek_stuff/today : 2006.05.10 00:49

/*
자료구조 - 2번째 과제물.
제출 기한 : 2006. 3. 31. Friday 6:00 PM.

주어진 숫자를 radix sort algorithm (pp. 350-357) 을 이용하여 정렬하라.

예 (radix 가 10일 경우):

329        720        720        329
457        355        329        355
657        436        436        436
839  ->    457   ->   839   ->   457
436        657        355        657
720        329        457        720
355        839        657        839


Input 양식:
5                // input 개수
10329353
2340213
234091223
2342321
2341323

Output 양식:
2340213
2341323
2342321
10329353
234091223


조건:
1. 각 숫자는 최대 9자리이다.
2. Input은 C:ass2_input.txt에서 입력 받아서 C:ass2_output.txt에 출력하면 된다.
3. 제출시 파일명은 "학번_이름_반"으로 작성하세요. 여기서 반은 과제물 제출 게시판의 반입니다.(A,B,C)
  예) 200621094_홍길동_A.exe /200621094_홍길동_A.c
4. 소스 파일과 실행 파일모두 제출 하셔야 합니다.  
5. input 개수에 상관없이 작동해야 합니다. 단 integer범위를 벗어나진 않습니다.
6. c: 폴더에 실행파일이 없을 경우에도 동작해야 합니다.
7. Radix_Size에 변동 사항이 있을 경우 공지사항에 다시 올리겠습니다.
8. 공지 사항을 꼭 확인해 주세요.
*/

#include <stdlib.h>  // to use function: atoi()
#include <string.h>  // to reset buffer: memset()
#include <windows.h> // for class CTimeCouter
#include <stdio.h>  // for class CTimeCouter

#define IN_FILE "c:\\ass2_input.txt"
#define OUT_FILE "c:\\ass2_output.txt"

// global variables here
struct data{
int* list;      // input data enters here
int* temp;  // mydata.temporary data to exchange
int num_in;    // number of inputs
}mydata;

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

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)
{
char tmpr[10]="";
int i;

fscanf(in_file,"%s",&tmpr);
if (atoi(tmpr)==0) return 0; // break if input is zero
else
{
 mydata.num_in=atoi(tmpr)+1;

 mydata.list = (int*)malloc(sizeof(int)*mydata.num_in); // memory allocation as size of mydata.num_in, and link this to mydata.list
 mydata.temp = (int*)malloc(sizeof(int)*mydata.num_in); // memory allocation as size of mydata.num_in, and link this to mydata.temp

 for(i=1; i<mydata.num_in; i++)
 {
  fscanf(in_file,"%s",&tmpr);
  mydata.list[i] = atoi(tmpr);
 }
}
return 1;
}


static void sort(FILE* out_file)
{
int cnt[256], idx[256], i;

Start(); // start stopwatch

memset(cnt, 0, 1024); // initializing count
idx[0]=0; // initializing index
for(i=0; i<mydata.num_in; i++)   cnt[(mydata.list[i] >> 0) & 255]++;
for(i=1; i<256; i++)   idx[i] = idx[i-1] + cnt[i-1];
for(i=0; i<mydata.num_in; i++)   mydata.temp[idx[(mydata.list[i] >> 0) & 255]++] = mydata.list[i];

memset(cnt, 0, 1024); // initializing count
idx[0]=0; // initializing index
for(i=0; i<mydata.num_in; i++)   cnt[(mydata.temp[i] >> 8) & (255)]++;
 for(i=1; i<256; i++)   idx[i] = idx[i-1] + cnt[i-1];
for(i=0; i<mydata.num_in; i++)   mydata.list[idx[(mydata.temp[i] >> 8) & 255]++] = mydata.temp[i];

memset(cnt, 0, 1024); // initializing count
idx[0]=0; // initializing index
for(i=0; i<mydata.num_in; i++)   cnt[(mydata.list[i] >> 16) & (255)]++;
for(i=1; i<256; i++)   idx[i] = idx[i-1] + cnt[i-1];
for(i=0; i<mydata.num_in; i++)   mydata.temp[idx[(mydata.list[i] >> 16) & 255]++] = mydata.list[i];

memset(cnt, 0, 1024); // initializing count
idx[0]=0; // initializing index
for(i=0; i<mydata.num_in; i++)   cnt[(mydata.temp[i] >> 24) & (255)]++;
for(i=1; i<256; i++)   idx[i] = idx[i-1] + cnt[i-1];
for(i=0; i<mydata.num_in; i++)   mydata.list[idx[(mydata.temp[i] >> 24) & 255]++] = mydata.temp[i];

End();  // stop stopwatch

fprintf(out_file,"%.10f\n", mytime.fTotal_Time);
for(i=0; i<mydata.num_in-1;i++) fprintf(out_file,"%d ", mydata.list[i]);
fprintf(out_file,"\n");
}


void main(void)
{
   FILE *in_file, *out_file;

in_file=fopen(IN_FILE,"r");
out_file=fopen(OUT_FILE,"w");

while(read(in_file)) sort(out_file);

fclose(in_file);
fclose(out_file);

free(mydata.list);
free(mydata.temp);
}

신고

'geek_stuff > today' 카테고리의 다른 글

Tistory.com Beta에서의 첫 글  (3) 2006.05.26
1kko.com 블로그의 변천사  (0) 2006.05.21
자료구조 과제 #2  (0) 2006.05.10
자료구조 과제 #1  (0) 2006.05.10
심심해서 서버 하나를 뚫어봤다.  (0) 2006.05.08
Apple.com이 윈도우즈를 지원한다?!  (2) 2006.04.06

자료구조 과제 #1

Posted by !kKo geek_stuff/today : 2006.05.10 00:48

/*/////////////////////////////////
Data Structure Assignment #1


과제1:
Operand의 크기가 너무커서 integer type으로 처리하지 못하는 더하기 연산을 integer 덧셈처럼 처리하는 프로그램을 작성하시오.

채점에 사용될 양식
예)
input.txt

21123424543254546575767868
+4235465475678687979797

2335344365547657
-345463574687

25434665457655765879
+4547568798080980

3543454
-46576985679

..
..
..
EOF

output.txt
325243436576970808976

3655765876987908606080

654768780900897979799
..
..
..

답 생성시 음수는 숫자앞에 '-'기호를 붙이셔야 됩니다.
위의 방식으로 하겠습니다.

값 사이의 줄 공백은 input 파일에서는 처리하셔야 되고
처리가 안되어 있다면 '순서대로 2줄을 읽어들여' 처리하는 식으로 되어 있으면 됩니다.

output파일에서의 공백은 처리 안하셨어도 됩니다.
*/

#include <fstream.h> // includes iostream.h
#include <string.h>  // for strcmp()

#define IN_FILE "C:\\input.txt" // don't forget to use double '\\' instead of '\'
#define OUT_FILE "C:\\output.txt"
#define MAX_LEN 200 // up to 200 chars (w/ cr & sign, +1)
#define POSITIVE 0
#define NEGATIVE 1

void mysort(char *mychar) // clear out spaces;
{
int j=0;
char temp[MAX_LEN]=""; // clearing garbages out (will temporary store cleared *mychar values)
for (int i=0;i<=MAX_LEN+1;i++)
{
 if (mychar[i]!=' ') temp[j++]=mychar[i]; // if the character is not a blank, than save to the temp.
}
strcpy(mychar, temp); // overwrite strings with 'blank removed' ones.


int signcheck_rmv(char *mychar) // check sign and return 1 if it's negative, else 0.
{
int ret_key=0;
for (int i=0;i<=MAX_LEN+1;i++)
{
 switch(mychar[i])
 {
 case '-':
  ret_key=1;     // if it's negative turn the flag on.
 case '+':
  mychar[i]=' '; // and then change the sign symbol to a blank.
  break;
 }
}
mysort(mychar); // call sort function to remove spaces

return ret_key; // return 1 if it's negative, otherwise 0
}


void remove_zeros(char* output) // remove front zeros, ej) 001023 -> 1023
{
char temp[MAX_LEN]="";
strcpy(temp,output);

for (int i=0;(unsigned)i<strlen(temp);i++) {
 if(temp[i]>='1') break;
 else temp[i]=' ';
}
mysort(temp);

if (strcmp(temp,"")==0) strcpy(temp,"0"); // leave one '0', if output is null.
strcpy(output,temp);
}


inline int bigger(int a, int b){ if(a>b) return a; else return b; }  // return bigger integer, else return first input.


void reform(char *mychar, int len) //digit count and modify 11 as 0011 to fit for 2222
{
int j=len-strlen(mychar); //+1 is for case of increase of number over 10
if (strlen(mychar)==(unsigned)len) {} //skip if strlen(mychar) is equal to itself.
else {
 while(j--) {
  for (int i=len; i>=0; i--) //repeat as length of mychar.
  {
   if(i<=0) mychar[i]='0'; // put '0' to mychar[i] if [i] is 0.
   else mychar[i]=mychar[i-1]; //otherwise
  }
 }
}
}


void calculate_plus(char* a, char* b, char *output, int last) // calculate and saves value to *output
{
int c=0;
int inta, intb;

char temp[MAX_LEN]="";

// digit count and modify 11 as 0011 to fit for 2222
reform(a, last);
reform(b, last);
reform(temp, last);

for (int i=1;i<=last;i++)
{
 inta=a[last-i]-'0';
 intb=b[last-i]-'0'; // converts a character to an integer
 //cout<<"inta+intb:"<<inta+intb<<endl;

 temp[last-i]=(((inta+intb)%10)+c)+'0'; // perform plus calculation

 if((inta+intb)/10) // if a+b is over 10, then we need to
 {
  c=1;    // set flag to 1 which says the output is more than 10.
  if(i==last) // in case the output have more digit than input, like 999+999.
  {
   reform(temp,strlen(temp)+1); // increase one more digit
   temp[0]='1';                 // then put 1 in front.
  }
 }
 else c=0; // otherwise reset the flag
}

remove_zeros(temp);
strcpy(output,temp); // copy temp to output
}


void calculate_minus(char* a, char* b, char *output, int last) // calculate and saves value to *output
{
int inta=0, intb=0, c=0;
char temp[MAX_LEN]="";
char my_a[MAX_LEN]="";
char my_b[MAX_LEN]="";

strcpy(my_a,a);
strcpy(my_b,b);

// count digit and modify 11 as 0011 to fit for 2222
reform(temp, last);
reform(my_a, last);
reform(my_b, last);

for (int i=1;i<=last;i++)
{
 if((my_a[last-i]-'0')==0) inta=0;
 else inta=(my_a[last-i]-'0');
 if((my_b[last-i]-'0')==0) intb=0;
 else intb=(my_b[last-i]-'0'); // converts a character to an integer


 if(inta-intb-c>=0)
 {
  temp[last-i]=(((inta-intb)%10)-c)+'0'; // perform minus calculation
  c=0;
 }
 else //if(inta-intb-c<0)
 {
  temp[last-i]=(inta-intb-c+10)+'0';
  c=1;
 }
}
remove_zeros(temp);
strcpy(output, temp);
}


int calculate(char *a, char *b, char *output, int a_is_neg, int b_is_neg) //(unsigned)bigger number comes to a, return 1 when the answer is MINUS.
{
char temp[MAX_LEN]="";
int type_a=0, type_b=0, i;
int len_a=strlen(a);
int len_b=strlen(b);
int last=bigger(len_a,len_b);

int a_size=1, b_size=1;

if(len_a==len_b) // assume that we have same length, because we already reform(a)&(b)
{
 for (i=0;i<=last;i++) // compare one by one
 {
  if(a[i]>b[i]) a_size*=(i+1); // +1 to prevent result is 0,  when i==0;
  if(b[i]>a[i]) b_size*=(i+1);
 }
 //cout<<"a_size: "<<a_size<<endl<<"b_size: "<<b_size<<endl;
 if(a_size>b_size)
 {
  if(a_is_neg) {calculate_minus(a,b,output,last); return NEGATIVE;} // when a_is_big and a_is_neg, output must be NEGATIVE
  if(b_is_neg) {calculate_minus(a,b,output,last); return POSITIVE;}
  calculate_plus(a,b,output,last); return POSITIVE;
 }
 if(b_size>a_size) //switch between (a,b) is occuring here.
 {
  if(b_is_neg) {calculate_plus(b,a,output,last); return NEGATIVE;} // when b_is_big and b_is_neg, output must be NEGATIVE
  if(a_is_neg) {calculate_plus(b,a,output,last); return POSITIVE;}
  calculate_plus(a,b,output,last); return POSITIVE;
 }
 calculate_plus(a,b,output,last); return POSITIVE;
}


int LONG=1;  //define as variable because we have to change later..
int SHORT=0;
//negative=1
//positive=0

if (len_a>len_b) { type_a=LONG; type_b=SHORT; }
if (len_b>len_a) { type_b=LONG; type_a=SHORT; }
if (a_is_neg) type_a+=NEGATIVE; else type_a+=POSITIVE;
if (b_is_neg) type_b+=NEGATIVE; else type_a+=POSITIVE;

// long-  type_x=2,
// long+  type_x=1,
// short- type_x=1,
// short+ type_x=0.

// first determine two definite situation.
// long+a(1) - short-b(1) = 0 // minus_calc, return POSITIVE
// long+a(1) - short+b(0) = 1 // plus_calc, return POSITIVE
// long-a(2) - short-b(1) = 1 // plus_calc, return NEGATIVE
// long-a(2) - short+b(0) = 2 // minus_calc, return NEGATIVE
// short+a(0) - long-b(2) = -2 // switch, minus_calc, return NEGATIVE
// short+a(0) - long+b(1) = -1 // plus_calc, return POSITIVE
// short-a(1) - long-b(2) = -1 // plus_calc, return NEGATIVE
// short-a(1) - long+b(1) = 0 // switch, minus_calc, return NEGATIVE

// now arranging by output, we can see top 2 has distinctive output.

// long-a(2) - short+b(0) = 2 // minus_calc, return NEGATIVE
// short+a(0) - long-b(2) = -2 // switch, minus_calc, return NEGATIVE

// long+a(1) - short-b(1) = 0 // minus_calc, return POSITIVE
// short-a(1) - long+b(1) = 0 // switch, minus_calc, return NEGATIVE
// long+a(1) - short+b(0) = 1 // plus_calc, return POSITIVE
// long-a(2) - short-b(1) = 1 // plus_calc, return NEGATIVE
// short+a(0) - long+b(1) = -1 // plus_calc, return POSITIVE
// short-a(1) - long-b(2) = -1 // plus_calc, return NEGATIVE

// so we can write:
if ( (type_a-type_b) == 2 ) { calculate_minus(a,b,output,last); return NEGATIVE; }
else if ( (type_a-type_b) == -2 ) { calculate_minus(b,a,output,last); return NEGATIVE; }

// now we have 6 conditions left, so we change the calculation from a-b to a+b.
// then we'll have two distinctive output from them.

// long+a(1) + short-b(1) = 2 // minus_calc, return POSITIVE
// short-a(1) + long+b(1) = 0 // switch, minus_calc, return NEGATIVE

// long+a(1) + short+b(0) = 1 // plus_calc, return POSITIVE
// long-a(2) + short-b(1) = 3 // plus_calc, return NEGATIVE
// short+a(0) + long+b(1) = 1 // plus_calc, return POSITIVE
// short-a(1) + long-b(2) = 3 // plus_calc, return NEGATIVE

// so we can write:
else if ( (type_a+type_b) == 2 ) { calculate_minus(a,b,output,last); return POSITIVE; }
else if ( (type_a+type_b) == 0 ) { calculate_minus(b,a,output,last); return NEGATIVE; }

// now we have 4 conditions left, so we change the definition of long
// now change the def of long.
else{
 LONG=10;
 type_a=type_b=0; //reset type_a and type_b

 // recalculate then.
 if (len_a>len_b) { type_a=LONG; type_b=SHORT; }
 if (len_b>len_a) { type_b=LONG; type_a=SHORT; }
 if (a_is_neg) type_a+=NEGATIVE; else type_a+=POSITIVE;
 if (b_is_neg) type_b+=NEGATIVE; else type_a+=POSITIVE;

 // LONG=10
 // SHORT=0
 // NEGATIVE=1
 // POSITIVE=0
 
 // which makes
 // long-  type_x=11,
 // long+  type_x=10,
 // short- type_x=1,
 // short+ type_x=0.

 // we perform the plus calculations to determine next top two.
 // long+a(10) + short+b(0) = 10 // plus_calc, return POSITIVE
 // short+a(0) + long+b(10) = 10 // plus_calc, return POSITIVE
 
 // long-a(11) + short-b(1) = 12 // plus_calc, return NEGATIVE
 // short-a(1) + long-b(11) = 12 // plus_calc, return NEGATIVE

 // so we now can write:
 if ((type_a+type_b) == 10) { calculate_plus(a,b,output,last); return POSITIVE; }
 else { calculate_plus(a,b,output,last); return NEGATIVE; }
}

return POSITIVE; // return positive if the answer is 0 situation(a=b) like (111-111)=0
}


void main(void)
{
char a[MAX_LEN]="";
char b[MAX_LEN]="";
char output[MAX_LEN]="";  // clearing out garbages

// opening files...
ifstream input_file(IN_FILE); //open file to read
ofstream output_file(OUT_FILE); //open file to write
if(input_file.fail()) //input file check
 cerr << "Error opening "<<IN_FILE<<endl;
else if(output_file.fail()) //output file check
 cerr << "Error opening "<<OUT_FILE<<endl;
else
{
 while (! input_file.eof()) //loop starts to get lines, stops end of the file.
 {
  strcpy(output,""); // just in case if the line have odd number
  //read file by line
  input_file.getline(a, sizeof(a)); //get a line, when repeats get the next odd line
  input_file.getline(b, sizeof(b)); //get a next line, when repeats get the next even line
  if (strcmp(a,"EOF")==0 || strcmp(b,"EOF")==0) break; // break out loop when meets "EOF" string, no matter if there's more to read.
   // so, really doesn't matter either line number is on even, or odd.

  //calculation
  //remove the sign
  int is_a_neg=signcheck_rmv(a);
  int is_b_neg=signcheck_rmv(b);

  switch(calculate(a, b, output, is_a_neg, is_b_neg)) // check out whether output positive calculation or negative.
  {
  case NEGATIVE:
   reform(output,strlen(output)+1);
   output[0]='-';
  case POSITIVE:
   break;
  }

  //cout<<"a: "<<a<<endl<<"b: "<<b<<endl<<"o: "<<output<<endl;  // just for testing purpose.
  output_file<<output<<endl; // write a line to output file.
 }//end of eof checking loop
}//end of input file error checking

// closing files...
input_file.close();
output_file.close();
} //end of main(void)*/

신고

'geek_stuff > today' 카테고리의 다른 글

1kko.com 블로그의 변천사  (0) 2006.05.21
자료구조 과제 #2  (0) 2006.05.10
자료구조 과제 #1  (0) 2006.05.10
심심해서 서버 하나를 뚫어봤다.  (0) 2006.05.08
Apple.com이 윈도우즈를 지원한다?!  (2) 2006.04.06
숫자 generator 프로그램  (0) 2006.03.27

숫자 generator 프로그램

Posted by !kKo geek_stuff/today : 2006.03.27 09:10

학교에서 자료구조 수업을 듣는데, 벌써 2번째 과제가 나왔다.

첫번째 과제는 개강 첫날 수업을 듣자마자 대뜸 내주시던 교수님...

생각했던대로 쉬웠던것은 아니였다. 그리고 결과는 참담;;;


이번에는 반드시 제대로 만들리라 하고 다짐했는데,

이번과제는 radix소트를 하는 프로그램이다.

아아.. 이런... 냅다 만들어서 테스트를 하려는데 entry를 쉽게쉽게

만들기 귀찮아서 그냥 프로그램으로 해결...;

갯수를 지정할수도 있고, random인지, 거꾸로 정렬된것인지, 제대로 정렬된것인지

모두 고를수있다!

음하하하!

(일반인은 다운받아도 별 소용없는거다.)
[버그있음] 때문에 새로운 버전(checker.exe)을 다운받길 권장한다.
아~주 아주 허접한 소스 공개한다.

보기

3/27 추가포스팅: 몇몇 버그가 있어서 소스코드와 함께 다시 올린다.
변경된 사항은 코멘트가 몇가지 추가된것, 9자리 숫자가 나와야하는데 10자리가 나오는 버그, output을 check하는 프로그램이다.

소스보기


(최종버전이길 기대하면서;;)

신고

'geek_stuff > today' 카테고리의 다른 글

심심해서 서버 하나를 뚫어봤다.  (0) 2006.05.08
Apple.com이 윈도우즈를 지원한다?!  (2) 2006.04.06
숫자 generator 프로그램  (0) 2006.03.27
뉴 개념의 PC 등장!  (0) 2006.03.10
도전 PC 100만원!  (5) 2006.02.23
옛날 컴퓨터에 대한 단상.  (3) 2006.02.13
 «이전 1  다음»