리스트의 응용

다항식 표현

희소 행렬 표현

스트링 표현

연산식의 계산

후위 표기 연산식으로 변환

다항식 - 배열을 이용한 표현 I

배열로 표현된 리스트가 다항식 연산에 어떻게 활용될 수 있는가를 살펴보기로 한다. 아래의 다항식을 표현하기 위하여 다음과 같이 배열을 선언할 수 있다.

[eqn: p(x) = a_n x^n + a_n-1 x^n-1 + cdots + a_1 x + a_0 \ (n ge 0)]

#define  MAX_DEGREE  100

typedef struct{

int degree;

float coef[MAX_DEGREE]

} polytype;

변수 p가 polytype일 때, 다항식 [eqn: p(x)]는 다음과 같이 표시된다.

p.coef[i] = [eqn: a_i]

이러한 방법으로 표현하면 두 다항식 [eqn: p(x)]와 [eqn: q(x)]의 합은 두 배열의 합으로 간단히 계산될 수 있다.

그러나 위와 같은 방식은 아래와 같이 항의 개수는 작지만 차수가 큰 다항식을 표현하기에 부적합하다.

[eqn: p(x) = 3 x^1000 + 4x -1]

다항식 - 배열을 이용한 표현 II

이러한 단점을 보완하기 위해서 계수가 0이 아닌 항만을 저장할 필요가 있다. 아래와 같이 polytype을 선언하고, 다항식 [eqn: p(x) = 3 x^1000 + 4x -1]을 표현하여 보자.

#define MAX_SIZE 100

typedef struct {

float coef;

int exp;

} polytype;

polytype p[MAX_SIZE];

int last;

이와 같은 표현에서 두 다항식 [eqn: p(x)]와 [eqn: q(x)]를 더하여 [eqn: r(x)]를 구하는 알고리즘을 작성하여 보라. 다항식 곱셈은 어떻게 구현될 수 있을까?

다항식 - 연결 리스트를 이용한 표현

연결 리스트를 이용하여 다항식을 표현할 수 있다. 예를 들어 다항식 [eqn: p(x) = 3 x^14 + 2x^8 + 1]은 아래와 같이 나타난다. 여기서는 환형 연결 리스트를 이용하여 표현하였으나, 물론 마지막 노드의 link 필드에 NULL을 채움으로서 선형 연결 리스트로 표현할 수도 있다.

가. 해드 노드가 없는 경우

나. 해드 노드가 있는 경우

이러한 표현에서 두 다항식의 합과 곱은 각각 어떻게 구할 수 있을까?

희소 행렬 표현 - 배열 이용

0인 원소를 많이 포함하는 행렬을 희소 행렬(sparse matrix)이라고 부른다. 행렬의 크기가 큰 경우 희소 행렬이 자주 나타나게 된다. 다음과 같은 희소 행렬의 표현을 살펴보기로 한다.

위의 희소 행렬은 아래 그림 (a)와 같이 일차원 배열로 표현할 수 있다. 이 경우 그림 (b)와 같은 전치 행렬(transpose)을 어떻게 구할 수 있을까? 두 행렬 A, B가 주어져 있을 때, 그것들의 합과 곱은 어떻게 구할 수 있을까?

희소 행렬 표현 - 연결 리스트 이용

앞에서 본 희소 행렬을 다음과 같은 연결 리스트로 표현할 수 있다. 이 같은 경우 전치 행렬, 행렬의 합과 곱은 어떻게 구현될 수 있겠는가?

희소 행렬 표현 - 연결 리스트 이용

연결 리스트를 이용한 희소 행렬 표현의 다른 예를 살펴보자.

스트링 표현

C 언어에서 스트링은 NULL 문자 \0로 끝나는 character array로 표현한다.

#define MAX_SIZE 100

char s[MAX_SIZE] = {"dog"};

char t[MAX_SIZE] = {"house"};

이 경우 다음과 같은 C 함수는 어떻게 구현되어 있을까?

size_t strlen(char *str)

char *strcat(char *dest, char *src)

char *strcpy(char *dest, char *src)

int strcmp(char *str1, char *str2)

만약 스트링이 연결 리스트로 표현되어 있다면 위와 같은 함수는 어떻게 구현할 수 있겠는가?

연산식의 계산

우리는 주로 연산식(expression)을 표현할 때 연산자를 피연산자 가운데에 위치시킨다. 이러한 표현을 중위 표기법(infix notation)이라고 한다.

A+B

(A-B)*C	* 연산자 우선 순위, 괄호

A-B-C	* (A-B)-C, 결합 규칙

2^3^2	* 2^(3^2), 결합 규칙

이러한 연산식을 왼쪽에서부터 읽어서 처리하기가 복잡하기 때문에 컴파일러 등에서는 연산자를 뒤에 위치시키는 후위 표기법(postfix notation, Polish notation)을 즐겨 사용한다.

Infix:	A+B

Prefix:   +AB

Postfix:  AB+

후위 표기법은 연산식을 계산할 때 왼쪽에서 오른쪽으로 한번만 읽으면서 처리할 수 있고, 연산자의 우선 순위를 고려하지 않아도 되며 괄호 없이 연산식을 표현할 수 있어서 편리하다.

후위 표기 연산식의 계산

후위 표기법으로 표기된 연산식을 계산하기 위해서는 연산식을 왼쪽에서 오른쪽으로 읽으면서 피연산자는 스택에 push하고 연산자가 나오면 피연산자를 스택에서 필요한 개수만큼 pop하여 연산을 수행한 후 결과를 스택에 push한다. 최종적으로 스택의 top에 남는 것이 계산 결과이다.

예를 들어 연산식 “6 2 / 3 - 4 2 * +”는 다음과 같이 계산하게 된다.

후위 표기 연산식에서는 왼쪽에서 오른쪽으로 연산식을 읽을 때 연산자가 나타나는 순서대로 연산이 이루어짐을 관찰할 수 있다.

후위 표기 연산식으로 변환 I

앞에서 후위 표기 연산식의 계산은 매우 간단히 실행될 수 있음을 보았다. 그러면 중위 표기 연산식에서 연산자 우선 순위, 결합 법칙 등의 복잡성은 어디로 간 것일까? 중위 표기 연산식을 후위 표기 연산식으로 변환할 때 이러한 것들을 고려해 주어야 한다.

후위 표기 변환 알고리즘은 연산식을 왼쪽에서 오른쪽으로 읽으면서 피연산자는 그래도 출력하고 연산자는 스택에 저장하였다가 다음에 오는 연산자와 비교하여 우선 순위가 같거나 큰 경우에 출력한다. 입력이 종료되면 스택내의 모든 연산자를 출력한다. 아래 연산식 “a + b * c”의 예에서 살펴보자.

만약 연산식이 “a * b / c - d”이면 어떻게 되겠는가?

연산식이 “a^b^c”로 주어진다면 위 알고리즘은 “a b ^ c ^”를 출력하여 (a^b)^c와 같은 의미를 가지게 된다. 이 경우처럼 연산자가 우결합하는 경우는 우선 순위가 같더라도 스택에 push하여야 옳은 변환을 할 수 있다.

후위 표기 연산식으로 변환 II

괄호가 있는 연산식인 경우 어떻게 변환할 수 있을까? 왼쪽 괄호를 스택에 push하고 해당하는 오른쪽 괄호가 나타날 때까지는 하나의 중위 표기 연산식이므로 이를 완전히 변환할 수 있어야 한다. 아래 예처럼 “a * ( b + c ) * d”라는 연산식이 주어지면 괄호로 묶인 연산식을 완전히 후위 표기 연산식으로 변환하고 나서 이를 하나의 피연산자처럼 생각하고 변환을 계속한다.

“a * ( ( b - c ) * d ) - ( e - f)”를 후위 표기 연산식으로 변환하여 보자.

여기서 완전한 알고리즘은 생략하고 교재를 참고하기로 한다.