추상 데이터 타입(ADT: Abstract Data Type)
데이터 타입을 추상적(수학적)으로 정의한 것
데이터나 연산이 무엇(what)인가는 정의되지만 데이터나 연산을
어떻게(how) 컴퓨터 상에서 구현할 것인지는 정의되지 않는다.
자연수
Nat_No zero() ::= return 0;
Boolean is_zero() ::= if (x=0) return TRUE;
else return FALSE;
Nat_No add(x,y) ::= if( (x+y) <= INT_MAX ) return x+y;
else return INT_MAX
Nat_No sub(x,y) ::= if ( x
else return x-y;
Boolean equal(x,y)::= if( x=y ) return TRUE;
else return FALSE;
Nat_No successor(x)::= if( (x+1) <= INT_MAX )
return x+1;
include
#include
#include
void main( void )
{
clock_t start, finish;
double duration; start = clock();
// 수행시간을 측정 하는 코드....
// ....
finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC;
printf("%f 초입니다. \n", duration);
}
알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법
순환함수 장점:
복잡한 프로그램을 간결하게 작성할 수 있다.
가독성이 높다. (?)
순환함수의 단점
메모리 소비가 높다.
함수 내부에서 사용되었던 변수
변수에 할당된 메모리 해제 이전에 (자신의) 함수를 다시 호출한다. 따라서 새로운 함수의 변수를 위해 메모리 할당이 다시 수행
시스템(운영체제)의 활성레코드의 저장(스택)
재귀 호출은 함수 리턴 이전에 새 함수를 연속적으로 호출함으로 리턴할 주소, 매개변수, 지역변수를 저장하는 운영체제 영역의 스택도 소비됨
struct studentTag {
char name[10]; // 문자배열로 된 이름
int age; // 나이를 나타내는 정수값
double gpa; // 평균평점을 나타내는 실수값
};
& 연산자: 변수의 주소를 추출
* 연산자: 포인터가 가리키는 곳의 내용을 추출
void *p; // p는 아무것도 가리키지 않는 포인터
int *pi; // pi는 정수 변수를 가리키는 포인터
float *pf; // pf는 실수 변수를 가리키는 포인터
char *pc; // pc는 문자 변수를 가리키는 포인터
int **pp; // pp는 포인터를 가리키는 포인터
struct test *ps; // ps는 test 타입의 구조체를 가리키는 포인터
void (*f)(int) ; // f는 함수를 가리키는 포인터
수식을 왼쪽에서 오른쪽으로 스캔하여 피연산자이면 스택에 저장하고 연산자이면 필요한 수만큼의 피연산자를 스택에서 꺼내 연산을 실행하고 연산의 결과를 다시 스택에 저장
(예) 82/3-32*+
중위표기와 후위표기
중위 표기법과 후위 표기법의 공통점은 피연산자의 순서는 동일
연산자들의 순서만 다름(우선순위순서)
->연산자만 스택에 저장했다가 출력하면 된다.
2+3*4 -> 234*+
자료의 개수가 많은 경우에는 차수가 가장 큰 항이 가장 영향을 크게 미치고 다른 항들은 상대적으로 무시될 수 있다
1. Factorial 프로그램
-소스코드
#include
#include
#include
int main()
{
clock_t start, end;
double duration;
start = clock();
int n = 1; //측정할값
int i;
int result = 1;
printf("정수입력: ");
scanf_s("%d", &n);
for (i = 1; i <= n; i++) //for문조건
{
result *= i;
}
printf("%d!= %d\n", n, result);
end = clock();
duration = (end - start) / CLOCKS_PER_SEC
printf("수행시간: %f", duration);
return 0;
}
2. 하노이 프로그램
-소스코드
#include
#include
#include
void hanoi_tower(int n, char from, char tmp, char to);
int main()
{
clock_t start, end;
double duration;
start = clock();
int num;
printf("원판의갯수: ");
scanf_s("%d", &num);
hanoi_tower(num, 'A', 'B', 'C');
end = clock();
duration = (end - start) / CLOCKS_PER_SEC
printf("수행시간: %f", duration);
return 0;
}
void hanoi_tower(int n, char from, char by, char to)
{
if (n == 1)
{
printf("1번원판이동경로: %c -> %c\n", from, to);
}
else
{
hanoi_tower(n - 1, from, to, by);
printf("%d번원판이동경로: %c -> %c\n", n, from, to);
hanoi_tower(n - 1, by, from, to);
}
}
3.리스트
void clear(ArrayListType *L)
{
L->size= 0;
}
void replace(ArrayListType *L, int position, element item)
{
if (is_empty(L) == 1)
printf("비어있습니다.");
else if (position<0 || position >= L->length)
printf("위치오류");
L->list[position] = item;
}
void get_length(ArrayListType *L)
{
int length;
length = L->size;
printf("리스트의 길이는 %d 입니다. \n", length);
}