또 학부 시절 이야기다, 10년 전쯤, 세상에는 C언어가 세계 최강의 언어라고 생각하고 있었을 철없을 나이에 수강하게 된 자료구조.
다행하게도 자료구조 수업도 완전히 C언어로만 수업을 진행했고, Linked List자료구조를 수업하고 나서 다항식을 연산하는 프로그램을 작성하라는 과제가 나왔다.
컴퓨터 정리중 아래와 같은 소스를 보고, 10년 전에 과제할때 끙긍되던 모습이 떠올라 올려본다 ㅋㅋㅋ
요즘은 일할 때도 주석을 거의 안달고 일하는데, 저때는 주석을 너무 많이 달았구나 싶은 정도로 달아뒀다 ^.^
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 제작기간 : 2002.11.21~2002.11.23
// 입력 : c:\data 파일
// 사용언어 및 컴파일러 : Visual C++ Enterprise,(C언어 구조 사용)
// 테스트 환경 : Intel Pentium3 866MHz
// 512MB Memory
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include <stdio.h> //기본 입출력 함수.
#include <stdlib.h> //atoi(),atof() 입력받은 문자열을 정수 및 실수로 변환하기 위한 함수.
#include <malloc.h> //malloc()함수.
#include <math.h> //pow함수.
#define DATAFILE "C:\\data06.txt" //입력 파일을 정의
#define EOS '#' // 파일에서 각 입력의 끝을 나타내는 문자 정의
#define REAL 2 // 파일에서 입력을 받을때 세번째 라인에는 실수가 입력되기 때문에 그 상태를 나타냄.
//0: 첫번째 다항식
//1: 두번째 다항식
typedef struct poly_node *poly_ptr; // 다항식 노드 정의
typedef struct poly_node {
int coef;
int expon;
poly_ptr link; // 수평이동하는 링크로서, 원형링크를 이루면서 다항식을 표현한다.
poly_ptr downlink; // 다항식의 곱셈에서 사용될 링크로서 각 다항식의 항을 곱할때 생기는 또 다른 다항식을 저장
// 자세한 구조는 리포트에 첨부
};
poly_ptr poly[2]={NULL}; // poly[0] : 첫번째 다항식 poly[1] : 두번째 다항식
poly_ptr avail=NULL; // 가용공간을 괸리하기 위한 포인터
float itemfloat=0; // 실수값이 들어오면 바로 저장
void create_polylist(FILE *);//문자열을 입력받아서 다항식 리스트를 만든다.
void pwrite(poly_ptr p); // 리스트 p에 있는 다항식을 출력한다.
poly_ptr padd(poly_ptr,poly_ptr,int state);//두 다항식을 더한 결과를 출력, state 1: add 결과 -1:sub 결과.
// psub함수는 padd함수에 state를 둬서 각항에 곱하면 된다.
poly_ptr pmult(poly_ptr,poly_ptr);//두 다항식을 곱한 결과를 출력.
short int compare(int x,int y);//두 정수의 크기를 비교 -1:x>y 0:x==y 1:x<y
void attach(int coefficient,int exponent,poly_ptr *ptr); // 노드에 다른 노드를 붙이는 함수(교재 변형)
void attach_down(poly_ptr *ptr); // 리스트가 아래로도 붙일수 잇으므로 밑으로 붙이는 함수
poly_ptr get_node(); // 가용공간 리스트나 시스템에서 노드 할당받는 함수
void perase(poly_ptr *ptr); // 사용이 끝난 노드나 리스트을 가용공간리스트에 반환.(곱셈과정중 생긴 리스트도 반환)
double peval(float r,poly_ptr p); // 실수값을 다항식에 넣어서 계산
void main()
{
int i=0;
FILE *fp; // file pointer 선언한다.
poly_ptr r; // 다항식의 연산 결과를 저장할 리스트
if((fp=fopen(DATAFILE,"r"))==NULL){ //지정 위치의 파일을 열지 못 할 경우에 에러 메세지 출력
printf("\nCan't open FILE(%s).\n",DATAFILE);
exit(0);
}//of if
create_polylist(fp); // 파일 로부터 정보를 입력받아서 다항식 리스트 만듬
for(i=0;i<2;i++) // 두 다항식을 출력
{
printf("Polynomial %d : ",i+1);
pwrite(poly[i]);
}//of for
printf("Real Value : %f\n\n",itemfloat); // 입력받은 실수값 출력
//다항식 덧셈 연산
printf("Add Polynomial1 and Polynomial2 : ");
r=padd(poly[0],poly[1],1);
pwrite(r);
printf("Computed result : %f \n",peval(itemfloat,r));
perase(&r);//리스트 반납
// 다항식 뺄셈연산
printf("Substact Polynomial2 from Polynomial1 : ");
r=padd(poly[0],poly[1],-1);//덧셈연산 하는 함수에 state를 -1로 두면 각 항에 -1을 곱하게 됨(두번째 다항식).
pwrite(r);
printf("Computed result : %f \n",peval(itemfloat,r));
perase(&r); // 리스트 반납
//다항식의 곱셈연산
printf("Multiply Polynomial1 and Polynomial2 ");
r=pmult(poly[0],poly[1]);
pwrite(r);
printf("Computed result : %f \n",peval(itemfloat,r));
perase(&r);//리스트 반납
for(i=0;i<2;i++)//다항식리스트 반납
{
perase(&poly[i]);
}//of for
}//of main()
// 입력 실수값을 다항식에 대입하여 계산한다.
double peval(float f,poly_ptr p)// 인자 : float형 실수, 다항식 리스트
{
double result=0;// 결과는 double형으로 선언한다.
// 지수 연산이 생각보다 큰 값을 만들기 때문에 오버플로우 발생시에는 더 큰 데이터 형을 선언할것.
poly_ptr temp; // 임시 노드 포인터 선언
temp=get_node(); // 할당
temp=p; // 임시노드는 다항식을 포인팅한다.
temp=temp->link;// 다항식리스트의 첫번째는 제로노드로 되어 있으므로 다음으로 이동.(수평)
while(temp!=p)// 리스트를 한번 돌때까지만
{
result=result+temp->coef*pow(f,temp->expon);//계산결과를 저장한다.
temp=temp->link;//다음으로 이동.
}//of while
return result;// 결과 반환
}//of peval()
//사용이 끝난 노드나 리스트 반납
void perase(poly_ptr *ptr)//인자: 반납할 리스트의 포인터.(교재와 동일)
{
poly_ptr temp;
if(*ptr)
{
temp=(*ptr)->link;
(*ptr)->link=avail;
avail=temp;
*ptr=NULL;
}//of if
}//of perase()
poly_ptr get_node()//노드 할당(교재와 동일)
{
poly_ptr node;
if(avail)
{
node=avail;
avail=avail->link;
}
else
{
node=(poly_ptr)malloc(sizeof(poly_node));
}
return node;
}//of get_node()
//다항식의 곱셈
poly_ptr pmult(poly_ptr p1,poly_ptr p2)//두다항식을 인자로 받는다.
{
poly_ptr res,result,temp1,temp2,headresult,lastd,starth,temph;
// 계산과정중에 사용될 여러 포인터 변수 선언. 결과는 res에 저장.
result=get_node();// 첫번째 다항식의 각 항을 두번째 다항식에 곱해서 새로운 리스트에 저장한다.
//result에 저장되는데, 수평 : 하나의 다항식 리스트, 수직: 첫번째 다항식의 각 항
result->expon=-1;
temp1=p1;
headresult=result;//headresult는 수직으로만 이동하게 구현(downlink사용)
headresult->expon=-1;
starth=headresult;//수직이동은 원형이 아니라 단순 리스트로 구현했음.
lastd=headresult;//수평 이동
temp1=temp1->link;
// 첫번째 다항식의 첫항과 두번째 다항식을 곱해서 저장
while(temp1!=p1)// 첫번째 다항식이 한바퀴 회전할때까지
{
temp2=p2;
temp2=temp2->link;
while(temp2!=p2)//두번째 다항식의 각 항들을 첫번째 다항식의 각 항과 곱해서 저장.
{
attach(temp1->coef*temp2->coef,temp1->expon+temp2->expon,&lastd);
temp2=temp2->link;
}//of while
lastd->link=headresult;
attach_down(&headresult);//첫번째 다항식의 어떤 항과 두번째 다항식과의 연산이 끝나면 첫번째 다항식의 다음 항으로 이동.
lastd=headresult;//수평 이동
headresult->expon=-1;
temp1=temp1->link;
}//of while
headresult->downlink=NULL;// 수직 리스트는 단순구조이므로 마지막에는 NULL을 넣어준다.
starth->expon=-1;
if(starth->downlink->downlink!=NULL)
{
res=padd(starth,starth->downlink,1);// 위의 과정을 통해서 나온 각 다항식들중 처음 두개의 다항식을 먼저 더한다.
// loop를 돌기 위해
temph=starth->downlink->downlink;
perase(&starth->downlink);//사용이 끝난 리스트 반납.
perase(&starth);
while(temph->downlink)//수직리스트가 끝날때 까지.
{
starth=temph;
res=padd(res,temph,1);// 위에서 나온결과와 남은 각항들을 더한다. 그리고 그 결과는 새로 저장되어 다음 loop에 사용.
res->downlink=NULL; // 잘못된 포인팅을 막기위해 수직이동은 없게 만든다.
temph=starth->downlink;
perase(&starth);// 사용이 끝난 리스트 반납.
}
return res;// 결과 반환.
}
else
{
return starth;
}
}
// 다항식의 덧셈
poly_ptr padd(poly_ptr p1,poly_ptr p2,int state)//교재와 동일(state가 -1이면 뺄셈 수행)
{
poly_ptr startp1,res,lastd;
int sum;
short int done=0;
startp1=p1;
p1=p1->link;
p2=p2->link;
res=get_node();
res->coef=0;
res->expon=-1;
lastd=res;
do{
switch(compare(p1->expon,p2->expon)){
case -1:
{
p2->coef=state*(p2->coef);
attach(p2->coef,p2->expon,&lastd);
p2->coef=state*(p2->coef);
p2=p2->link;
break;
}
case 0:
{
if(startp1==p1) done=1;
else
{ p2->coef=state*(p2->coef);
sum=p1->coef + p2->coef;
p2->coef=state*(p2->coef);
attach(sum,p1->expon,&lastd);
p1=p1->link;
p2=p2->link;
}
break;
}
case 1:
{
attach(p1->coef,p1->expon,&lastd);
p1=p1->link;
}
}
}while(!done);
lastd->link=res;
return res;
}
void attach_down(poly_ptr *ptr)// 수직 리스트를 만듬
{
poly_ptr temp;
temp=get_node();
(*ptr)->downlink=temp;// 수직 이동용
*ptr=temp;
}
void attach(int co,int ex,poly_ptr *ptr)// 수평 리스트 만듬
{
poly_ptr temp;
temp=get_node();
temp->coef=co;
temp->expon=ex;
(*ptr)->link=temp;
(*ptr)->downlink=NULL;// 수직이동을 못하게 한다.
*ptr=temp;
}
short int compare(int x,int y)// 두수의 크기 비교.
{
if(x<y)
return -1;
else if(x==y)
return 0;
else
return 1;
}
void pwrite(poly_ptr p)// 다항식의 출력(리스트를 읽어서 출력)
{
int a=0;
poly_ptr temp;
temp=get_node();
temp=p->link;
while(temp->link!=p)//부호가 있는 경우에는 신경써서 다루어 줘야 됨.(각 경우를 분리)
{
if((temp->coef<0)&&!(p->link==temp))//음수일때,그리고 처음수가 아닐때.
{
a=-1*(temp->coef);
printf("%dx",a);
}
else
{
printf("%dx",temp->coef);
}
printf("%d ",temp->expon);
if(temp->link->coef<0)//다음 항의 계수가 음수라면 '-'를 표현해야 됨.
{
printf("- ");
}
else
{
printf("+ ");
}
temp=temp->link;
}
printf("%d",abs(temp->coef));
if(temp->expon!=0)
{
printf("x%d",temp->expon);
}
printf("\n");
}
//다항식 만들기
void create_polylist(FILE *data)// 파일에서 입력 받은정보로 다항식 구성. 실수값 입력받음.
{
int line=0; // 0: 첫번째 다항식 1: 두번째 다항식 2: 실수 입력
int itemco,itemex=0;//계수,지수
char *item,*itemf;//문자열로 읽어들일 계획(나중에 변환)
poly_ptr lastd[2];
item=(char *)malloc(7*sizeof(char));//정수형이 표현할 수 있는 최대 자릿수가 6자리 이기 때문에.
itemf=(char *)malloc(9*sizeof(char));//실수형이 표현할 수 있는 최대 자릿수를 8로 제한한다.
for(line=0;line<2;line++)// 다항식을 만들기 전에 노드를 하나 만들어서 처음 초기화 시키고.
{
poly[line]=get_node();
poly[line]->expon=-1;
poly[line]->downlink=NULL;
lastd[line]=poly[line];
}
line=0;
while(!feof(data))// 각 정보를 읽어 들여서 위에서 만든 노드에 붙인다.
{
if(line==REAL)// 실수 값이 들어올 시점이면 실수값을 읽어들여서 변수에 저장
{
fscanf(data,"%s",itemf);
itemfloat=atof(itemf);
line++;
}
else if(line<REAL)// 다항식의 정보가 들어올때는
{
itemco=0;
fscanf(data,"%s",item);// 문자열 하나를 읽어서
if(!(item[0]==EOS))// 다항식의 끝이 아니라면
{
itemco=atoi(item);// 정수로 변환
fscanf(data,"%s",item);//또 문자열을 입력받는다.
itemex=atoi(item);// 정수로 변환
attach(itemco,itemex,&lastd[line]);// 각 정수가 계수와 지수이므로 리스트에 붙임
}// 한번에 두개씩 읽어서 각 항의 정보가 착착 들어온다.
else if(item[0]==EOS)//다항식의 끝이라면.
{
lastd[line]->downlink=NULL;// 수직이동이 없게 NULL을 넣어준다. 이전의 노드들은 attach에서 NULL해준다.
lastd[line]->link=poly[line];//원형 리스트로 만들어준다.
line++;
}
}
else
break;
}
fclose(data);//파일을 닫는다.이제는 파일이 더이상 필요없으므로.
}
그리고 추가로 자료구조를 설명하면 다음과 같은 자료구조로 프로그래밍했다.
typedef struct poly_node *poly_ptr; // 다항식 노드 정의
typedef struct poly_node {
int coef;
int expon;
poly_ptr link; // 수평이동하는 링크로서, 원형링크를 이루면서 다항식을 표현한다.
poly_ptr downlink; // 다항식의 곱셈에서 사용될 링크로서 각 다항식의 항을 곱할때 생기는 또 다른 다항식을 저장
// 자세한 구조는 리포트에 첨부
};
'코딩하고 > C,C++' 카테고리의 다른 글
| OS - Page Fault Simulation(FIFO,LRU,Optimal) (0) | 2012.10.21 |
|---|---|
| 자료구조 - 계산기 만들기 (10) | 2012.10.12 |
| C언어로 만든 객체 (0) | 2012.10.11 |
| ls 명령어 구현하기. (2) | 2012.10.09 |
| 조건문 제거하기 - Function Table사용법 (0) | 2012.08.11 |
커뉴
이 세상에서 꿈 이상으로 확실한 것을, 인간은 가지고 있는 것일까?
