수업 출처) 숙명여자대학교 소프트웨어학부 수업 "자료구조", 유석종 교수님
1. 다차원 배열
- 2차원 이상의 배열을 다차원 배열이라고 한다.
- 논리적으로는 m차원이지만, 물리적으로는 1차원으로 메모리 상에 표현됟나.
- m차원 배열 A : int A[n₀][n₁] ··· [nₘ₋₁];
- 배열 A에 저장되는 원소의 총 개수 : n₀ x n₁ x ··· nₘ₋₁
예를 들어 A[10][9][8]로 선언된 배열 원소의 총 개수는 10 x 9 x 8 = 720개이다.
1-1. 행 우선 순서 (Row-major order)
- 기본 주소에서부터 행을 기준으로 원소가 저장된다.
- 배열 원소의 오른쪽 차원의 인덱스가 먼저 증가되고, 상한 경계에 도달하면 바로 왼쪽 옆자리가 1씩 증가된다.
- 이런식으로 인덱스 값이 오른쪽에서 왼쪽 방향으로 증가하면서 메모리에 저장된다.
- (ex) A[0][0] → A[0][1] → A[1][0] → A[1][1] → A[2][0] → A[2][1]
1-2. 열 우선 순서
- 열을 우선적으로 채워가는 형식이다.
- 배열 원소의 왼쪽 차원의 인덱스가 먼저 증가되고, 상한 경계에 도달하면 바로 오른쪽 옆자리가 1씩 증가된다.
- (ex) A[0][0] → A[1][0] → A[2][0] → A[0][1] → A[1][1] → A[2][1]
2. 원소의 주소
2-1. 1차원 배열
- 원소의 위치는 시작주소(α) + 오프셋(offset) 값으로 계산된다.
- n개의 원소를 가지고 있는 1차원 배열 A의 시작 주소가 α이고, 각 원소에 s바이트가 할당된다고 할 때,
&A[0] = α + 0 * s
&A[1] = α + 1 * s
...
&A[n-1] = α + (n-1) * s
→ &A[i] = α + i * s
2-2. 2차원 배열
- A[u₀][u₁]으로 선언된 2차원 배열에서 A[i][j] 주소는 α + (i * u₁ + j) * s 이다. // 행 우선 순서일 때
- 열 우선 순서일 때의 주소는 α + (i + u₀ * j) * s 이다.
2-3. 3차원 배열
- A[u₀][u₁][u₂] 으로 행 우선 순서로 선언된 2차원 배열에서 A[i][j][k]의 주소는 α + (i * u₁ * u₂ + j * u₂ + k) * s이다.
- 열 우선 순서로 저장된 배열의 주소는 α + (i * u₁ * u₂ + j + u₁ * k) * s이다.
3. Stack 스택
- 선형 리스트의 특별한 형태로, 한 방향으로 쌓아둔 것을 의미한다.
- 후입 선출 구조이다. (LIFO : Last-In, First-Out)
- 함수 호출 관리, 문법 검사, 연산식 평가 등에 활용된다.
- S = [a₀, a₁, ..., aₙ₋₁] 형식으로 원소들의 리스트로 정의할 수 있다.
- aₙ₋₁ 이 가장 나중에 삽입된 원소이다.
- 스택에 원소를 추가하는 연산을 "push"라고 하고, 원소를 삭제하는 연산을 "pop"이라고 한다.
- top 포인터는 가장 나중에 삽입된 원소를 가리키며, 그 위치에 해당하는 배열 인덱스 값을 갖는다.
- 빈 스택에서 top 포인터는 -1 값을 갖는다.
- 1차원 배열로 구성된 스택에 최초로 들어오는 원소는 stack[0]에 저장된다.
- (ex) Function Call
- A()가 실행 중일 때 B를 호출하면, B()가 끝날 때까지 A()는 멈춰있다.
- 새로운 함수가 실행될 때마다 현재 실행 중인 함수의 환경 변수를 시스템 스택에 Stack Frame 형태로 저장해야 한다.
- Stack Frame (Activation record)
- 지역 변수
- 재개할 때 다음에 실행될 명령어의 주소
- 이전 stack frame의 포인터
#define STACK_SIZE 100
int stack[STACK_SIZE];
int top = -1;
void push(int item);
int pop;
void print_stack();
void main()
{
push(3);
push(4);
push(5);
pop();
print_stack();
pop();
print_stack();
pop();
print_stack();
pop();
print_stack();
}
void print_stack()
{
int i;
for(i = 0; i <= top; i++)
printf("%d", stack[i]);
printf("\n");
}
void push(int item)
{
if (top >= STACK_SIZE - 1){
printf("stack full");
return;
}
stack[++top] = item;
print_stack();
}
int pop()
{
if (top < 0) {
printf("stack empty");
return -999;
}
return stack[top--];
}
- 실행 결과
3
3 4
3 4 5
3 4
3
stack empty
4. Queue 큐
- 처리를 기다리고 있는 원소들의 리스트라고 볼 수 있다.
- 스택과 같은 선형 리스트 구조이다.
- 스택과 다른 점은 "선입 선출" 방식이라는 것이다. (FIFO : First-In, First-Out)
- 새로운 원소는 큐의 맨 뒤(rear)에 삽입되고, 큐의 맨 앞(front)원소가 가장 먼저 삭제된다.
- Q = [a₀, a₁, ..., aₙ₋₁] 형식으로 정의할 수 있으며, a₀가 가장 먼저 삽입된 원소이고, aₙ₋₁가 가장 나중에 삽입된 원소이다.
- 큐의 맨 앞과 맨 뒤를 가리키기 위한 두 개의 포인터 (front, rear) 가 필요하다.
- 원소가 삽입될 때에는 rear 포인터가, 삭제될 때에는 front 포인터가 각각 사용된다.
- rear 포인터 값이 큐의 상한 경계와 같으면 full queue로 판단하고, rear와 front 포인터의 값이 같으면 empty queue로 간주한다.
#define QUEUE_SIZE 100
int queue[QUEUE_SIZE];
int rear = -1;
int front = -1;
void print_queue();
void addq(int item);
int deleteq();
void main()
{
int temp;
addq(3);
addq(5);
addq(7);
temp = deleteq();
print_queue;
}
void print_queue()
{
int i;
for (i = front + 1; i <= rearl i ++)
printf("%d", queue[i]);
printf("\n");
}
void addq(int item)
{
if(rear == QUEUE_SIZE - 1) {
printf("Queue Full. item not added");
return;
}
queue[++rear] = item;
print_queue;
}
int deleteq()
{
if (front == rear) {
printf("Queue empty.");
return -999;
}
return queue[++front];
}
- 실행 결과
3
3 5
3 5 7
5 7
4-1. 일반 큐
- 원소의 삽입, 삭제 시 rear와 front 포인터 값이 모두 증가된다.
- 삽입 삭제 빈도가 증가할수록 큐에서 원소들의 저장 위치가 점점 오른쪽으로 이동하게 되고, 왼쪽에 빈공간이 생기게 된다.
- 따라서 원소가 다 차지 않았음에도 queue full 신호가 발생할 수 있다.
- 큐의 빈공간을 재사용하기 위해서는 원소들을 왼쪽으로 이동시키는 작업을 주기적으로 해주어야 한다. 이를 해결한 자료구조가 "순환 큐"이다.
4-2. 순환 큐
- 큐의 오른쪽 끝을 반대편 끝과 연결하여 원소가 이동할 필요 없이 전체 공간을 모두 사용할 수 있다.
- 일반 큐와 마찬가지로 front와 rear 포인터 값이 같을 때를 empty queue로 정의한다.
- front와 rear의 초기값은 각각 0이다.
- 순환 큐의 모든 공간에 원소가 삽입되면 front와 rear 값이 또 같아지게 된다.
- 이런 상황을 피하기 위해 rear = front - 1인 시점, 즉 원소가 n-1개 삽입된 상태를 full queue로 간주한다.
#include <stdio.h>
#define QUEUE_SIZE 100
int front, rear;
int cqueue[QUEUE_SIZE];
void addcq(int item);
int deletecq;
void print_queue();
void main()
{
int temp;
front = rear = 0;
addcq(11);
addcq(13);
addcq(17);
addcq(19);
temp = deletecq();
print_queue();
temp = deletecq();
print_queue();
temp = deletecq();
print_queue();
temp = deletecq();
print_queue();
}
void addcq(int item)
{
if (front == ((rear + 1) % QUEUE_SIZE) {
printf("queue full");
return;
}
rear = (rear + 1) % QUEUE_SIZE;
cqueue[rear] = item;
print_queue();
}
int deletecq()
{
if (front == rear) {
printf("queue empty");
return -999;
}
front = (front + 1) % QUEUE_SIZE;
return cqueue[front];
}
void print_queue()
{
int i = front;
while (i != rear) {
i = (i + 1) % QUEUE_SIZE;
printf("%d", cqueue[i]);
}
printf("\n");
}
- 일반 큐와는 달리 순환 큐이기 때문에 if (front == ((rear + 1) % QUEUE_SIZE) 와 같이 "%" 연산자를 사용해야 한다.
- (ex) QUEUE_SIZE = 6이면 인덱스는 0 ~ 5가 존재한다. 이번에 마지막 칸인 인덱스가 5인 칸에 값을 넣었다면 그 다음칸은 6 % 6 인 0이 되어야 한다. 그리고 그것이 front 값과 같기 때문에 full queue가 되었음을 알 수 있다.
5. Deque
- Double ended queue
- 양방향으로 삽입과 삭제가 모두 가능한 자료구조이다.
6. 수식 평가
- 수식은 연산자와 피연산자로 구성된 문장이다.
- 연산자는 산술 연산자, 논리 연산자, 대입 연산자 등이 있다.
- 피연산자는 변수 또는 상수가 될 수 있다.
- 표기법
- 중위 표기법
- a / b - c + d * e - a * c
- 후위 표기법
- ab / c - d e * + a c *
- 전위 표기법
- - + - / a b c * d e * a c
6.1 후위 수식 계산 알고리즘
- 수식을 왼쪽에서 오른쪽으로 스캔한다.
- 수식에서 들어온 입력이 피연산자이면 스택에 넣는다.
- 입력이 연산자이면 스택에서 피연산자를 2개 꺼내서 계산한 후 결과 값을 다시 스택에 넣는다.
- 수식 평가 스택
#include <stdio.h>
#include <string.h>
#define STACK_SIZE 100
#define EXPR_SIZE 100
typedef enum
{
open_b, close_b, plus, minus, times, divide, mod, eos, operand
} priority; // 열거형 -> 0, 1, 2, ..., 8
int stack[STACK_SIZE]; // 수식 평가 스택
char expr[EXPR_SIZE]; // 수식 문자열
int pos = 0; // 문자열 현재 위치
char sym;
int sym_type;
int top = -1;
- 후위 수식 평가
int eval_postfix();
void push(int item);
int pop();
void main()
{
// strcpy(expr, "57 * 9 + 34 / -"); // 5 * 7 + 9 - 3 / 4
strcpy(expr, "936 + 5 - / 7 * 64 - *"); // 9 / (3 + 6 - 5) * 7 * (6 - 4)
eval_postfix();
}
int eval_postifx()
{
char sym;
int op1, op2;
sym = read_item();
while (sym_type != eos) {
if (sym_type == operand)
push(sym - '0');
else {
op2 = pop();
op1 = pop();
switch (sym_type) {
case plus : push(op1 + op2);
case minus : push(op1 - op2);
case times : push(op1 * op2);
case divide : push(op1 / op2);
case mod : push(op1 % op2);
}
}
sym = read_item();
}
return pop();
}
void push (int item)
{
if (top >= STACK_SIZE - 1) {
printf("stack full");
return;
}
stack[++top] = item;
print_stack;
}
int pop()
{
if (top < 0) {
printf("empty stack");
return -999;
}
return stack[top--];
}
- 심볼 입력
char read_item()
{
char sym;
sym = expr[pos++];
switch (sym)
{
case '(' : sym_type = open_b;
break;
case ')' : sym_type = close_b;
break;
case '+' : sym_type = plus;
break;
case '-' : sym_type = minus;
break;
case '*' : sym_type = times;
break;
case '/' : sym_type = divide;
break;
case '%' : sym_type = mod;
break;
case '\0' : sym_type = eos;
break;
default : sym_type = operand; // 피연산자
}
return sym;
}
- 실행 결과
9 3 6 + 5 - / 7 * 6 4 - *
9
9 3
9 3 6
9 9
9 9 5
9 4
2
2 7
14
14 6
14 6 4
14 2
28
6-2. 중위 수식 → 후위 수식
- 입력이 피연산자이면 그대로 출력한다.
- 입력의 우선 순위가 스택 top의 연산자보다 높거나, 스택이 비어있으면 입력을 스택에 넣는다.
- 스택의 연산자 우선 순위가 입력보다 크거나 같으면 스택 연산자를 pop하고 입력을 스택에 넣는다.
- 입력이 '(' 이면, ')'이 들어올 때까지 다음 연산자를 위의 규칙을 따라서 스택에 넣는다.
- 입력이 ')' 이면, '('이 나올 때까지 스택에서 계속 연산자를 pop해서 출력하고 '(' 은 출력하지 않고 버린다.
- 입력이 문자열의 끝(eos)이면, 스택의 모든 연산자를 꺼내서 출력한다.
- (ex)
a + (b * c + d) * e
입력 | 출력 | 스택 |
a | a | |
+ | a | + |
( | a | + ( |
b | a b | + ( |
* | a b | + ( * |
c | a b c | + ( * |
+ | a b c * | + ( + |
d | a b c * d | + ( + |
) | a b c * d + | + |
* | a b c * d + | + * |
e | a b c * d + e | + * |
\0 | a b c * d + e * + |
#include <stdio.h>
#include <ctype.h>
#define STACK_SIZE 100
char token_stack[STACK_SIZE];
int token_top = -1;
void infix_to_postfix();
int precedence(char op);
void push_token(char sym);
char pop_token();
void main()
{
infix_to_postfix();
}
void infix_to_postfix()
{
char expr[50], sym, token;
int pos = 0;
printf("Enter the expression :: ");
scanf("%s", expr);
while ((token = expr[pos++]) != '\0') {
if (isalnum(token)) // 알파벳 또는 숫자
printf("%c", token);
else if (token == '(')
push_token(token);
else if (token == ')') {
while ((sym = pop_token()) != '(')
pirntf("%c", sym);
}
else {
while(precedence(token_stack[token_top]) >= precedence(token) &&
token_top != -1) {
printf("%c", pop_token());
}
push_token(token);
}
}
while (token_top != -1)
printf("%c", pop_token());
}
int precedence (char op)
{
if (op == '(')
return 0;
else if (op == '+' || op == '-')
return 1;
else if (op == '*' || op == '/' || op == '%')
return 2;
}
void push_token(char sym)
{
if (token_top < STACK_SIZE -1)
token_stack[++token_top] = sym;
else
printf("token stack full\n");
}
char pop_token()
{
if (token_top >= 0)
return token_stack[token_top--];
printf("token stack empty\n");
return ' ';
}
- 실행 결과
Enter the expression :: a + (b * c + d) * e
a b c * d + e * +
Enter the expression :: 5 * 7 + (4 - 3) / 6 % 9
5 7 * 4 3 - 6 / 9 % +
'Software > Data Structures' 카테고리의 다른 글
[자료구조] 탐색 (0) | 2021.04.20 |
---|---|
[자료구조] 연결 리스트 (0) | 2021.04.20 |
[자료구조] 알고리즘 성능 분석 (0) | 2021.04.17 |
[자료구조] Recursion 재귀 호출 (0) | 2021.04.17 |
[자료구조] C언어 기초 (0) | 2021.04.17 |