19장 자료구조

책정리/혼자 연구하는 C,C++ 1

19장 자료구조

GONII 2015. 2. 25. 17:57

19.1 동적 배열

19.1.1 배열 요소의 삽입, 삭제

배열의 장점은 크게 두 가지가 있는데 첫 번째로 구좌 단순하기 때문에 정보 자체를 기억하는 메모리 외에 추가로 소모하는 메모리가 전혀 없어 공간 효율이 좋다.

둘째로 배열 크기가 아무리 커지더라도 검색 속도가 일정하다. 배열의 첨자 연산은 포인터를 통해 시작 번지에 첨자*요소크기를 더하는 간단한 동작이므로 임의의 한 요소를 참조하는 시간이 상수이다.

그러나 배열에도 한가지 단점이 있는데 배열 요소가 연속된 메모리 공간에 배치되어 있어야 하므로 중간의 요소를 삭제하거나 새로운 요소를 삽입할 수 없다는 점이다.

예제 ArrayInsDel

#include <stdio.h>

#include <string.h>

char ar[16] = "abcdef";

void Insert( int idx, char ch )

{

memmove(ar+idx+1, ar+idx, strlen(ar)-idx+1);

ar[idx] = ch;

}

void Delete( int idx )

{

memmove(ar+idx, ar+idx+1, strlen(ar)-idx);

}

void Append( char ch )

{

Insert(strlen(ar), ch );

}

void main()

{

printf("최초 : %s\n", ar);

Insert(3, 't');

printf("t삽입 : %s\n", ar);

Delete(1);

printf("b 삭제 : %s\n",ar);

Append('s');

printf("s추가 : %s\n", ar);

}

이동할 길이는 이동 시작 번지 뒤쪽의 남은 요소 개수인데 이 개수는 전체 길이인 strlen(ar)에서 이동 시작 요소 번호인 idx를 빼서 구하괴 널 종료 문자도 포함시켜야 하므로 1을 더해준다

memmove 함수는 바이트 단위의 이동 길이를 요구하므로 이동할 요소 개수에 요소 타입의 크기인 sizeof(char)를 곱해야 하나 이 경우는 요소 크기가 1이므로 생략할 수 있다.

Insert(3,'t')호출 동작

Delete 함수 동작

19.1.2 동적 배열

배열도 메모리를 조작하면 중간에 삽입, 삭제가 가능하여 크기가 가변적인 정보를 다룰 수 있지만 배열의 크기가 자동으로 늘어나는 것은 아니므로 미리 선언한 크기 이상의 요소를 추가할 수는 없다.

실행 중에 필요한 만큼 크기를 늘렸다 줄였다 할 수 있는 배열을 동적배열이라고 한다.

예제 DynArray

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define ELETYPE int

ELETYPE *ar;

unsigned size;

unsigned num;

unsigned growby;

void InitArray( unsigned asize, unsigned agrowby )

{

size = asize;

growby = agrowby;

num = 0;

ar = (ELETYPE*)malloc(size * sizeof(ELETYPE));

}

void Insert( int idx, ELETYPE value )

{

unsigned need;

need = num+1;

if( need > size )

{

size = need + growby;

ar = (ELETYPE*)realloc(ar, size*sizeof(ELETYPE));

}

memmove(ar+idx+1, ar+idx, (num-idx)*sizeof(ELETYPE));

ar[idx] = value;

num++;

}

void Delete(int idx)

{

memmove(ar+idx, ar+idx+1, (num-idx-1)*sizeof(ELETYPE));

num--;

}

void Append(ELETYPE value)

{

Insert(num, value);

}

void UnInitArray()

{

free(ar);

}

void DumpArray(char *sMark)

{

unsigned i;

printf("%16s => 크기 = %02d, 개수 = %02d : ", sMark, size, num );

for ( i = 0 ; i < num ; i++ )

{

printf("%3d", ar[i]);

}

printf("\n");

}

void main()

{

int i;

InitArray(10, 5); DumpArray("최초");

for( i = 1 ; i <= 8 ; i++ ) Append(i); DumpArray("8개 추가");

Insert(3, 10); DumpArray("10 삽입");

Insert(3, 11); DumpArray("11 삽입");

Insert(3, 12); DumpArray("12 삽입");

Delete(7); DumpArray("요소 7 삭제");

UnInitArray();

}

:: 배열의 실체

배열의 실체는 ar 포인터이다. int ar[100]; 이런 식으로 배열을 선언하면 ㅡ기와 위치가 컴파일 할 때 확정되어 가변적인 크기를 다룰 수 없으므로 저장하고자 하는 타입의 포인터를 선언하고 이 포인터를 동적으로 할당해야 한다. ELETYPE 매크로는 배열 요소의 타입인데 필요에 따라 변경할 수 있도록 매크로 상수로 정의했다.

:: 배열 관리 변수

동적 배열은 컴파일 할 때 그 크기가 미리 정해지지 않으며 실행 중에 언제든지 크기를 변경할 수 있어야 한다. 그래서 현재 얼마만큼 할당되어 있는지 할당 크기를 별도의 변수에 저장해두어야 하는데 size 변수가 배열의 할당 크기를 기억한다. 또한 배열에 실제 저장된 요소의 개수도 항상 유지해야 하는데 num 변수가 이 정보를 저장한다. growby 변수는 재할당 할 때의 여유분을 지정한다

:: 배열 초기화

배열의 실체인 ar이 포인터 변수이므로 ar에 메모리가 할당되기 전까지 배열은 실제로 존재하지 않는다. 포인터가 실질적인 배열이 되기 위해서는 일단 메모리를 초기 할당해야 한다. InitArray 함수는 배열 관리 변수의 초기값을 설정하고 이 초기값대로 메모리를 할당하여 ar 포인터에 그 번지를 대입한다.

:: 재할당

1 ~ 8 까지 정수를 추가한 후 10, 11, 12를 요소 3의 위치에 순서대로 삽입하는데 10, 11까지 삽입되면 ar은 꽉 찬 상태가 된다. 이 상태에서 12를 더 삽입하려면 기억 공간이 부족하므로 배열의 크기를 늘려 재할당해야 한다.

:: 여유분

배열을 재할당할 때는 어느 정도의 여유분을 주는 것이 효율상 유리하다. 삽입은 보통 연속적으로 일어나므로 메모리가 부족해서 크기를 늘려야 한다면 조만간 메모리가 다시 부족해질 확률이 아주 높다. realloc 함수는 편리하기는 하지만 번지가 바뀔 경우 굉장히 느리며 특히 배열의 크기가 클수록 속도상의 불이익이 심하기 때문에 가급적이면 호출 회수를 줄여야 한다. 그래서 이왕 재할당을 할 때 여유분을 주어 다음 번 부족한 상황을 최대한 늦추는 것이 좋다.

:: 그 외 함수의 변화

Insert함수에는 배열 크기 점검과 재할당문이 추가되었고 배열 요소를 삽입하는 코드는 아의 예제와 거의 비슷하다. 다만 memmove 함수의 이동 길이가 조금 달라졌다. 배열에 기억되는 값이 문자열이 아니므로 널 종료 문자를 이동 길이에 포함 시킬 필요가 없으며 문자형에 대한 배열이 아닌 임의 타입에 대한 배열이므로 sizeof(ELETYPE)을 곱해야 한다.

19.1.3 동적 배열 활용

동적 배열은 관리 대상이 동일 타입의 집합이면서 크기가 가변적인 프로그램에 응용 가능하다. 자료의 집합을 다룰 수 있으므로 원시적인 데이터베이스라고 할 수 있다.

예제 JusoArray

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

struct tag_nameCard

{

char name[10];

char tel[15];

char addr[32];

};

#define ELETYPE tag_nameCard

ELETYPE *ar;

unsigned size;

unsigned num;

unsigned growby;

void InitArray( unsigned asize, unsigned agrowby )

{

size = asize;

growby = agrowby;

num = 0;

ar = (ELETYPE*)malloc(size * sizeof(ELETYPE));

}

void Insert( int idx, ELETYPE value )

{

unsigned need;

need = num+1;

if( need > size )

{

size = need + growby;

ar = (ELETYPE*)realloc(ar, size*sizeof(ELETYPE));

}

memmove(ar+idx+1, ar+idx, (num-idx)*sizeof(ELETYPE));

ar[idx] = value;

num++;

}

void Delete(int idx)

{

memmove(ar+idx, ar+idx+1, (num-idx-1)*sizeof(ELETYPE));

num--;

}

void Append(ELETYPE value)

{

Insert(num, value);

}

void UnInitArray()

{

free(ar);

}

void DumpArray(char *sMark)

{

unsigned i;

printf("%16s => 크기 = %02d, 개수 = %02d : ", sMark, size, num );

for ( i = 0 ; i < num ; i++ )

{

printf("%3d", ar[i]);

}

printf("\n");

}

void main()

{

char ch;

unsigned i;

tag_nameCard temp;

InitArray(10, 5);

for( ;; )

{

printf("명령을 입력하세요(1:보기, 2:추가, 3:삭제, Q:종료) > ");

scanf("%c", &ch);

printf("\n");

if ( ch == 'Q' || ch == 'q' )

{

break;

}

switch(ch)

{

case '1' :

if( num == 0 )

{

printf("등록된 내용이 없습니다.\n");

}

else

{

for ( i = 0 ; i < num ; i++ )

{

printf("%d, 이름 : %s, 전화 : %s, 주소 : %s\n", i, ar[i].name, ar[i].tel, ar[i].addr);

}

break;

case '2' :

fflush(stdin);

printf("이름을 입력하세요(9자) : "); gets(temp.name);

printf("전화번호를 입력하세요(14자) : "); gets(temp.tel);

printf("주소를입력하세요(31자) : "); gets(temp.addr);

Append(temp);

break;

case '3' :

printf("삭제할 번호를 입력하세요 : "); scanf("%d", &i);

if( i < num )

{

Delete(i);

}

else

{

printf("등록되지 않은 번호입니다.\n");

}

break;

}

UnInitArray();

}

19.2 연결 리스트

19.2.1 단순 연결 리스트

연결 리스트와 동적 배열은 완전히 용도가 같은 자료 구조로서 서로 대체 가능하지만 구성 원리나 관리 방법은 질적으로 다르다.

연결리스트는 요소들의 메모리의 도처에 흩어져서 존재하지만 링크에 의해 논리적으로 연결되어 있어 링크를 따라가면 이전, 이후 요소를 찾을 수 있다. 삽입, 삭제를 할 때도 물리적인 메모리 이동 없이 요소간의 링크만 조작하면 되므로 속도가 빠르다.

연결리스트의 요소인 노드는 데이터 외에 연결 상태에 대한 정보인 링크를 추가로 가져야 한다. 자기 다음의 요소가 누구인지를 스스로 기억하고 있어야 흩어져 있는 노드들의 순서를 알 수 있는데 이 연결 정보를 저장하는 것이 바로 링크이다.

링크를 하나만 가지는 것을 단순 연결 리스트(Single Linked List)라고 하고 두 개의 링크를 가지는 것을 이중 연결 리스트(Double Linked List)라고 한다.

struct node

{

int value; // 데이터

node* next; // 링크

};

value는 노드가 기억하는 정보의 실체인 데이터이다.

next는 다음 노드에 대한 포인터를 가지는 링크이다.

연결 리스트의 첫 번째 노드인지는 따로 저장해야 하는데 시작점을 기억하는 노드를 머리(head)라고 한다.

노드3의 링크는 NULL로 되어 잇는데 다음 노드가 없다는 것은 연결 리스트의 끝이라는 뜻이다.

예제 SingleList

#include <stdio.h>

#include <stdlib.h>

// 노드

struct node

{

int value;

node *next;

};

node *head;

// 연결 리스트 초기화 - head를 할당

void InitList()

{

head = (node*)malloc(sizeof(node));

head->next = NULL;

}

// target 다음 노드를 삽입

node* InsertNode(node* target, node* aNode)

{

node *newNode;

newNode = (node*)malloc(sizeof(node));

*newNode = *aNode;

newNode->next = target->next;

target->next = newNode;

return newNode;

}

// target 다음 노드를 삭제

bool DeleteNode(node* target)

{

node* del;

del = target->next;

if( del == NULL )

{

return false;

}

target->next = del->next;

free(del);

return true;

}

// 연결리스트의 노드와 head를 해제

void UnInitList()

{

while(DeleteNode(head)) {;}

free(head);

head = NULL;

}

void main()

{

int i;

node* now, temp;

InitList();

now = head;

// 다섯 개 노드 삽입

for ( i = 1 ; i <= 5 ; i++ )

{

temp.value = i;

now = InsertNode(now, &temp);

}

// 두번째 노드 삭제

DeleteNode(head->next);

// 출력

for( now = head->next ; now ; now = now->next )

{

printf("%d\t", now->value);

}

printf("\n");

UnInitList();

}

:: node 구조체

node 구조체는 연결 리스트의 한 요소인 노드를 정의한다. 정보를 저장하는 멤버 변수는 얼마든지 추가할 수 있다. node형 포인터 head는 전역으로 선언되어 있는데 이 변수가 연결 리스트의 진입점이다. 설사 연결 리스트가 비어 있더라도 머리는 반드시 있어야 하며 또한 적절하게 초기화되어야 한다. InitList함수는 head에 node 구조체를 할당하며 최초 머리 노드만 존재하므로 head의 링크는 NULL로 초기화한다.

:: 노드의 삽입

노드는 자신과ㅏ 연결된 노드의 정보를 가지고 있으므로 물리적인 메모리 이동없이 링크만 조작하여 리스트의 중간에 새로운 노드를 쉽게 삽입 할 수 있다.

node 구조체를 새로 할당하며 newNode를 만들고 value를4로 초기화
새로 만든 노드4의 링크에 노드3의 번지를 대입(newNode->next = target->next)
노드 2의 링크에 노드4를 대입( target->next = newNode )하여 노드4가 노드2다음에 위치하도록 연결

InsertNode 함수는 두 개의 인수를 받아들인다. target인수는 삽입하고자하는 노드의 이전 노드이며 target 다음에 새 노드를 삽입한다.

두번째 매개변수 aNode는 삽입 대상이 되는 노드의 데이터를 가지는 임시 노드이다. main에서 node 구조체를 만들고 이 구조체의 alue에 원하는 값을 채워 보내면 InsertNode는 aNode 자체를 newNode에 대입한다. value만 전달할 수도 있지만 이렇게 하면 node구조체가 바뀔때마다 InsertNode 함수를 수정해야 하는 번거로움이 있어 임시 노드를 전달하는 방법을 쓴다. 구조체 대입은 메모리 복사이므로 멤버가 늘어나도 수정할 필요가 없다.

node* InsertNode(node* target, node* aNode)

{

node *newNode;

newNode = (node*)malloc(sizeof(node)); // 노드 생성, 그림1번 과정

*newNode = *aNode;

newNode->next = target->next; // 뒤쪽 노드 연결, 그림2번 과정

target->next = newNode; // 앞쪽 노드 연결, 그림3번 과정

return newNode;

}

:: 노드의 삭제

노드를 삭제하는 방법도 역시 링크를 조작하는 것이다. DeleteNode 함수는 인수로 주어진 target노드 다음의 노드를 삭제한다.

노드2를 제거하려면 DeleteNode함수로 노드1을 전달해야 head->next로 쉽게 구할 수 있다. target->next로 삭제 대상 노드를 찾아 del에 대입한다. 그리고 del이 가리키고 있는 다음 노드를 target의 다음 노드로 설정(target->next = del->next)함으로써 del을 리스트에서 제외시킨다. 이렇게 되면 del은 메모리에 아직 남아 있지만 연결 리스트에서는 논리적으로 삭제된 것이다. del이 차지하고 있는 메모리는 free함수로 해제하면 이 노드는 물리적으로 제거된다.

:: 순회

순회란 연결 리스트에 포함된 모든 노드를 한 번씩 읽어 보는 것이다. 순회 중에 여러 가지 작업을 할 수 있으며 일단 순회를 해야 어떤 처리라도 할 수 있다. 특정값을 가진 노드를 검색한다거나 노드 전체를 출력할 때는 머리에서부터 링크를 따라 모든 노드를 방문해 봐야 한다.

노드들은 연속적인 메모리 공간에 있지도 않고 생성되는 위치를 예측할 수도 없지만 머리에서부터 next링크만 따라 다니면 순서에 맞게 모든 노드를 순회할 수 있다.

:: 해제

연결리스트의 노드들은 실행 중에 메모리를 할당해서 생성되므로 다 사용했으면 해제해야 한다. UnInitList 함수가 담당

head의 다음 노드인 첫 번째 노드를 삭제하기를 실패할 때까지, 즉 머리가 리스트의 끝이 될 때까지 반복한다. head 자체는 DeleteNode함수로 삭제할 수 없으므로 별도로 해제한다.

19.2.2 이중 연결 리스트

이중 연결 리스트는 전후의 노드에 대한 링크를 각각 따로 가지며, 순방향뿐만아니라 역방향 순회도 가능하다.

struct node

{

int value;

node* prev; // 이전 노드

node* next; // 다음 노드

};

링크가 하나 더 들어가기 때문에 기억장소를 그만큼 더 소비하고 링크를 관리하는 코드가 조금 더 복잡해진다는 단점이 있다.

예제 DoubleList

#include <stdio.h>

#include <stdlib.h>

// 노드 구조체

struct node

{

int value;

node* prev;

node* next;

};

node* head;

// 연결 리스트 초기화

void InitList()

{

head = (node*)malloc(sizeof(node));

head->next = NULL;

head->prev = NULL;

}

// 지정한 노드의 오른쪽에 삽입

node* InsertNodeRight(node* target, node* aNode)

{

node* newNode;

node* right;

newNode = (node*)malloc(sizeof(node));

*newNode = *aNode;

right = target->next;

newNode->next = right;

newNode->prev = target;

target->next = newNode;

if( right )

{

right->prev = newNode;

}

return newNode;

}

// 지정한 노드의 왼쪽에 삽입

node* InserNodeLeft(node* target, node* aNode)

{

node* left;

left = target->prev;

if( left )

{

return InsertNodeRight(left, aNode);

}

return NULL;

}

// 제일 끝에 노드 추가

void AppendNode(node* aNode)

{

node* tail;

for( tail = head ; tail->next ; tail = tail->next ) {;}

InsertNodeRight(tail, aNode);

}

// 단순 연결 리스트와는 달리 자기 자신을 지울 수 있다.

bool DeleteNode( node* target )

{

node *left, *right ;

// 헤더는 지울 수 없음

if( target== NULL || target == head )

{

return false;

}

left = target->prev;

right = target->next;

left->next = right;

// target이 끝 노드 이면

if( right )

{

right->prev = left;

}

free(target);

return true;

}

// idx번째 노드를 찾는다

node* FindNodeIndex(int idx)

{

node *now;

int index = 0;

for ( now = head->next ; now ; now = now->next )

{

if( index == idx )

{

return now;

}

index++;

}

return NULL;

}

// 노드의 순서값을 구한다

int GetNodeIndex(node* target)

{

node* now;

int index = 0;

for( now = head->next ; now ; now = now->next )

{

if( now == target )

{

return index;

}

index++;

}

return -1;

}

// 노드의 개수를 조사한다.

int GetListCount()

{

node* now;

int count = 0 ;

for( now = head->next ; now ; now = now->next )

{

count++;

}

return count;

}

// 연결리스트의 모든 노드 해제

void UnInitList()

{

while(DeleteNode(head->next)){;}

free(head);

head = NULL;

}

void main()

{

int i;

node *now, temp;

InitList();

for( i = 1 ; i <= 5 ; i++ )

{

temp.value = i;

AppendNode(&temp);

}

// 순회하며 출력

for( now = head->next ; now ; now = now->next )

{

printf("%d\t", now->value);

}

printf("\n");

//개수, 데이터 3을 가진 노드와 앞뒤 노드를 조사

printf("노드 개수 = %d\n", GetListCount());

for( now = head->next ; now ; now = now->next )

{

if( now->value == 3 )

{

break;

}

if( now )

{

printf("Mid = %d, 앞 노드 = %d, 뒷 노드 = %d\n", now->value, now->prev->value, now->next->value);

}

printf("3번째 노드 = %d\n", FindNodeIndex(3)->value);

UnInitList();

}

:: 노드의 삽입

이중 연결 리스트는 양쪽에 새 노드를 삽입 할 수 있다.

newNode를 삽입한다면 새 노드를 메모리상에 할당하고 이를 초기화한다.

기존 노드의 링크를 변경하기 전 먼저 새로 만든 노드의 링크를 수정하여 연결리스트에 포함시킨다. newNode의 다음 노드는 right가 되고 이전 노드는 target이 된다. 그리고 기존 노드의 링크를 변경하여 새로 생성된 노드를 앞뒤 노드로 배치하는데 newNode는 target의 다음 노드이면서 right의 이전 노드가 되어 두 노드 사이에 끼어든다. 노드 하나를 삽입하기 위해 앞뒤 및 자신의 링크까지 4개의 링크 조작이 필요하다.

제일 앞에 삽입될 경우는 target으로 head가 주어졌을 때 인데 머리 노드가 존재하므로 일반적인 경우와 동일하게 처리하면된다. 제일 뒤에 삽입될 경우는 target이 마지막 노드일 때인데 이때는 오른쪽 노드인 right가 NULL이므로 right->prev를 조작하는 코드만 제외하면 된다. NULL->prev 코드를 실행하면 프로그램이 다운된다.

:: 왼쪽 삽입 및 추가

지정한 노드의 왼쪽에 삽입하는 InsertNodeLeft 함수는 링크를 조작하는 코드가 모두 오른쪽 삽입 함수에 있으므로 이 함수를 호출하면 된다.

어떤 노드의 왼쪽이란 이전 노드의 오른쪽과ㅏ 같으므로 target->prev를 대상으로 InsertNodeRight 함수를 호출하면 나머지는 호출된 함수가 알아서 할 것이다.

머리 노드의 왼쪽에 어떤 노드를 삽입할 수 없으므로 에러로 처리한다.

:: 노드의 삭제

이중 연결 리스트는 양쪽 노드에 모두 접근할 수 있으므로 target자체를 삭제할 수 있다.

타겟의 좌우 노드를 left, right에 구해 놓는데 left는 target->prev, right는 target->next로 쉽게 구할 수 있다. left, right가 서로 이웃할 수 있도록 만든 다음에 target을 해제하면된다.

:: 검색

FindNodeInext 함수는 순서값으로부터 원하는 노드를 찾는다. 연결 리스트의 노드는 배열과ㅏ 달리 첨자가 없지만 연결 순서에 따라 번호를 붙일 수 있다. 머리부터 순회하면서 각 노드의 번호를 세다가 지정한 번호에 이르렀을 때의 노드 포인터를 리턴한다. 총 노드 개수보다 더 크다면 검색은 실패하고 NULL이 리턴된다.

내용으로 노드를 찾는 것이 더 실용적이다.

:: 개수 조사

연결 리스트에 포함된 노드의 총 개수를 알고 싶다면 이때도 순회를 이용한다.

19.2.3 그 외의 연결 리스트

이 예제는 head에 node 구조체를 할당하고 head->next가 첫번째 노드를 가리키도록 하고 있다. head는 포인터만 가리키고 실제로 데이터를 저장하지 않는다. 별도의 head노드를 만드는 대신 head 포인터 변수가 곧바로 첫 번째 노드를 가리키도록 할 수 있다.

head가 첫 노드를 가리키면 메모리 공간을 약간 절약할 수 있고 초기화를 위해 머리 노드를 할당하 필요도 없다.
연결리스트의 마지막 노드는 끝임을 나타내기 위해 링크를 NULL로 설정하는데 이 방법 대신 자기 자신을 가리키도록 할 수 있다.

임의의 노드 N이 끝인지 확인하는 조건문이 N->next == NULL 에서 N->next == N으로 바뀌는데 버그로 인해 링크 끝을 찾지 못할 경우 엉뚱한 메모리 영역을 침범하는 대신 무한 루프에 빠지도록 함으로써 디버깅을 조금 더 쉽게 하는 것 외에는 별다른 차이점이 없다.
마지막 노드를 기억하는 tail 노드를 별도로 유지할 수 있다.
노드의 총 개수를 참고해야 할 경우 전역 변수를 선언하고 리스트에 변화가 있을 때마다 이 값을 관리할 수 있다.
InsertNode함수를 통해 노드의 삽입이 이루어질 때 임시 객체를 사용하는 대신 정수값 하나만 인수로 넘겨 삽입하거나 검색할 노드 데이터를 전달할 수도 있다.
끝 노드의 링크가 첫 노드를 가리키고 있어 원 ㅁ모양을 하고 있는 원형 연결 리스트도 만들 수 있다

19.2.4 연결 리스트의 활용

동적 배열과 연결 리스트는 구조가 조금 다르기는 하지만 같은 타입의 데이터 집합을 다룬다는 면에서 용도가 완전히동일하며 서로 대체 가능하다. 즉, 동적 배열로 풀 수 있는 문제라면 연결리스트로 풀 수 있고 반대의 경우도 마찬가지다. 노드나 요소의 크기, 삽입과 삭제의 빈도, 검색 속도 요구치, 메모리 소모량 등에 따라 둘 중 하나를 선택해서 사용하면 된다.

예제 JusoList

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <conio.h>

// 노드 구조체

struct node

{

char name[10];

char tel[15];

char addr[32];

node *prev;

node *next;

};

node* head;

// 연결 리스트 초기화

void InitList()

{

head = (node*)malloc(sizeof(node));

head->next = NULL;

head->prev = NULL;

}

// 지정한 노드의 오른쪽에 삽입

node* InsertNodeRight(node* target, node* aNode)

{

node* newNode;

node* right;

newNode = (node*)malloc(sizeof(node));

*newNode = *aNode;

right = target->next;

newNode->next = right;

newNode->prev = target;

target->next = newNode;

if( right )

{

right->prev = newNode;

}

return newNode;

}

// 지정한 노드의 왼쪽에 삽입

node* InserNodeLeft(node* target, node* aNode)

{

node* left;

left = target->prev;

if( left )

{

return InsertNodeRight(left, aNode);

}

return NULL;

}

// 제일 끝에 노드 추가

void AppendNode(node* aNode)

{

node* tail;

for( tail = head ; tail->next ; tail = tail->next ) {;}

InsertNodeRight(tail, aNode);

}

// 단순 연결 리스트와는 달리 자기 자신을 지울 수 있다.

bool DeleteNode( node* target )

{

node *left, *right ;

// 헤더는 지울 수 없음

if( target== NULL || target == head )

{

return false;

}

left = target->prev;

right = target->next;

left->next = right;

// target이 끝 노드 이면

if( right )

{

right->prev = left;

}

free(target);

return true;

}

// idx번째 노드를 찾는다

node* FindNodeIndex(int idx)

{

node *now;

int index = 0;

for ( now = head->next ; now ; now = now->next )

{

if( index == idx )

{

return now;

}

index++;

}

return NULL;

}

// 노드의 순서값을 구한다

int GetNodeIndex(node* target)

{

node* now;

int index = 0;

for( now = head->next ; now ; now = now->next )

{

if( now == target )

{

return index;

}

index++;

}

return -1;

}

// 노드의 개수를 조사한다.

int GetListCount()

{

node* now;

int count = 0 ;

for( now = head->next ; now ; now = now->next )

{

count++;

}

return count;

}

// 연결리스트의 모든 노드 해제

void UnInitList()

{

while(DeleteNode(head->next)){;}

free(head);

head = NULL;

}

node* FindNode(node *start, node* aNode )

{

node *now;

for( now=start->next ; now ; now = now->next )

{

if( strcmp(now->name, aNode->name) == 0 )

{

return now;

}

return now;

}

void main()

{

char ch;

node *now;

node temp;

InitList();

for( ;; )

{

printf("명령을 입력하세요(1:보기, 2:추가, 3:삭제, Q:종료) > " );

ch = getch();

printf("\n");

if( ch == 'Q' || ch == 'q' )

break;

switch(ch)

{

case '1':

if( head->next == NULL )

{

printf("등록된 내용이 없습니다.\n");

}

else

{

now = head->next;

{

printf("이름:%s, 전화:%s, 주소:%s\n", now->name, now->tel, now->addr);

now = now->next;

}while(now);

}

break;

case '2':

printf("이름 입력(9자) : "); gets(temp.name);

printf("전화 번호(14자) : "); gets(temp.tel);

printf("주소 입력(31자) : "); gets(temp.addr);

AppendNode(&temp);

break;

case '3':

printf("삭제할 사람의 이름을 입력하세요 : "); gets(temp.name);

now = FindNode(head, &temp);

if( now != NULL )

{

DeleteNode(now);

printf("삭제 완료\n");

}

else

{

printf("등록되지않은 사람\n");

}

break;

}

UnInitList();

}

연결 리스트의 단점
- 읽기 속도가 형편없이 느리다. 노드간의 관계가 링크로만 저장되기 때문에 중간의 한 노드를 찾으려면 순회하는 것만이 유일한 방법이다. 삽입, 삭제는 빨라졌지만 대신 검색 속도가 느리다. 자료를 다루는 동작의 90%는 읽기이며 삽입, 삭제는 상대적으로 흔한 동작이 아니므로 읽는 동작이 느리다는 것은 치명적인 단점이다.
- 메모리 효율이 좋지 못하다. 데이터 외에 링크를 별도로 가져야 하므로 링크 분만큼의 메모리가 더 소모됨은 물론이고 개별 노드를 동적으로 할당해야 하므로 할당 헤더에 의한 메모리 소모도 만만치 않다.
- 코드가 그리 어렵지는 않지만 배열과 비교했을 때 상대적으로 복잡하고 포인터 구문이 많아 개발자가 실수를 할 가능성이 많다.
- 자료 구조의 내부적인 모양이 선형(Linear)이 아닌 입체적인 모양을 하고 있어 스트림 입출력이 번거롭다.
- qsort, bsearch 등의 알고리즘을 구현하는 표준 함수들은 기본적으로 배열에 대해 동작하도록 작성되어 있다. 연결리스트는 임의 접근을 지원하지 않으므로 이런 표준 함수의 서비스를 받을 수 없다.

19.3 스택

19.3.1 스택

스택은 LIFO(Last In First Out)의 원리로 동작하는 선형적인 자료구조이다. 같은 타입의 자료 집합을 관리한다는 면에서 배열이나 연결리스트와 동일하지만 자료를 관리하는 방식이 미리 정해져 있다는 점이 다르다.

스택은 데이터가 들어가고 나오는 입구가 하나뿐이므로 입구로 들어간 데이터가 스택에 차곡차곡 쌓여 있다가 들어간 반대 순서로 나온다. 주로 계산 중에 잠시 기억해야 하는 임시적인 자료를 관리하는 용도로 사용된다.

CPU도 여러 가지 정보를 저장하기 위해 스택을 사용하는데 이를 시스템 스택이라고 한다. 시스템 스택에는 함수로 전달되는 인수, 지역변수 등의 임시 변수들이 저장되고 함수 실행 후 돌아갈 복귀 번지도 저장된다. CPU의 레지스터 개수가 많지 않기 때문에 이미 사용중인 레지스터를 다른 용도로 쓰고 싶ㅍ을 때는 스택에 잠시 저장해 두고 사용한 후 다시 원래값을 꺼내 복구한다.

예제 Stack

#include <stdio.h>

#include <stdlib.h>

int *stack;

int size;

int top;

void InitStack(int aSize)

{

size = aSize;

stack = (int*)malloc(size*sizeof(int));

top = -1;

}

void FreeStack()

{

free(stack);

}

bool Push(int data)

{

if( top < size-1 )

{

top++;

stack[top] = data;

return true;

}

return false;

}

int Pop()

{

if( top >= 0 )

{

return stack[top--];

}

else

{

printf("no data\n");

return -1;

}

void main()

{

InitStack(256);

Push(7);

Push(0);

Push(6);

Push(2);

Push(9);

Push(15);

printf("%d\n", Pop());

FreeStack();

}

스택을 궇ㄴ하기 위해서는 세 개의 변수가 필요하다. stack은 데이터를 저장할 저장소인데 필요한 만큼 동적으로 할당하기 위해 포인터로 선언했다. size는 스택의 할당 크기이다. top은 스택의 현재 위치를 가리키는 값이며 스택의 어디까지 차 있는지를 기억한다.

InitStack 함수는 스택을 초기화하는데 인수로 전달된 aSize 크기만큼 메모리를 할당하여 stack 포인터에 대입한다. 동적으로 할당하면 스택을 사용하는 쪽에서 필요한 크기를 결정할 수 있는데 필요한 최대 크기로 잡는 것이 좋다. 최초 스택에는 아무런 데이터가 들어 있지 않으므로 top은 비어 있다는 뜻의 -1로 초기화한다.

스택에 데이터를 저장하는 동작을 푸시라고 한다. push함수는 데이터가 들어 있는 top을 1 증가시킨 후 이자리에 인수로 전달된 data를 집어넣는다.

스택이 가득 차서 더 데이터를 삽입할 수 없는 상태를 스택 오버플로우라고 하는데 이때는 삽입을 중지하고 에러를 리턴한다.

스택에 저장한 값을 빼내는 것을 팝이라고 한다. pop함수는 top의 위치의 값을 읽고 top은 하나 감소시킨다. 스택이 텅 비어서 더 꺼낼 데이터가 없는 상태를 스택 언더플로우라고 하며 -1이라는 에러값을 리턴하도록 했다.

임시적인 정보를 저장하는 용도상 스택은 굳이 길이가 가변적인 필요가 없다

19.3.2 스택을 이용한 계산기

:: 수식의 계산

컴퓨터는 계산은 하는 기계이므로 복잡한 수식도 계산할 수 있다. 이때 계산식은 사람으로부터 주어지는데 키보드로 입력된 문자열에서 숫자와 연산자를 추출해서 계산해야 하는 경우가 많다.

:: TextCalc

예제 TextCalc

#include <stdio.h>

#include <stdlib.h>

#include <ctype.h>

#include <string.h>

#include <math.h>

char *cStack;

int cSize;

int cTop;

void cInitStack(int aSize)

{

cSize = aSize;

cStack = (char*)malloc(cSize*sizeof(char));

cTop = -1;

}

void cFreeStack()

{

free(cStack);

}

bool cPush(char data)

{

if( cTop < cSize-1 )

{

cTop++;

cStack[cTop] = data;

return true;

}

else

{

printf("stack overflow\n");

return false;

}

char cPop()

{

if( cTop >= 0 )

{

return cStack[cTop--];

}

else

{

printf("stack underflow\n");

return -1;

}

double *dStack;

int dSize;

int dTop;

void dInitStack(int aSize)

{

dSize = aSize;

dStack = (double*)malloc(dSize*sizeof(double));

dTop = -1;

}

void dFreeStack()

{

free(dStack);

}

bool dPush(double data)

{

if( dTop < dSize-1 )

{

dTop++;

dStack[dTop] = data;

return true;

}

else

{

return false;

}

double dPop()

{

if( dTop >= 0 )

{

return dStack[dTop--];

}

else

{

printf("dStack underflow\n");

return -1;

}

int GetPriority(int op)

{

switch(op)

{

case '(':

return 0;

case '+':

case '-':

return 1;

case '*':

case '/':

return 2;

case '^':

return 3;

}

return 100;

}

void MakePostfix(char* post, const char *mid)

{

const char *m = mid;

char *p = post, c;

cInitStack(256);

while(*m)

{

// 숫자 - 그대로 출력하고 뒤에 공백 하나를 출력

if( isdigit(*m))

{

while( isdigit(*m) | *m == '.' )

{

*p++ = *m++;

}

*p++ = ' ' ;

}

// 연산자 - 스택에 있는 자기보다 높은 연산자를 모두 꺼내 출력하고 자신은 푸쉬

else if(strchr("^*/+-", *m))

{

while(cTop != -1 && GetPriority(cStack[cTop]) >= GetPriority(*m))

{

*p++ = cPop();

}

cPush(*m++);

}

// 여는 괄호 - 푸쉬

else if( *m == '(' )

{

cPush(*m++);

}

// 닫는 괄호 - 연느 괄호가 나올 때까지 팝해서 출력하고 연느 괄호는 버린다

else if( *m == ')' )

{

for ( ;; )

{

c = cPop();

if( c == '(' ) break;

*p++ = c;

}

m++;

}

else

{

m++;

}

// 스택에 남은 연산자를 모두 꺼냄

while( cTop != -1 )

{

*p++ = cPop();

}

*p = 0;

cFreeStack();

}

double CalcPostfix(const char *post)

{

const char *p = post;

double num;

double left, right;

dInitStack(256);

while( *p )

{

// 숫자는 스택에 넣는다.

if( isdigit(*p) )

{

num = atof(p);

dPush(num);

for( ; isdigit(*p) || *p == '.' ; p++ ) {;}

}

else

{

// 연산자는 스택에 두 수를 꺼내 연산하고 다시 푸쉬

if( strchr("^*/+-", *p) )

{

right = dPop();

left = dPop();

switch(*p)

{

case '+':

dPush(left+right);

break;

case '-':

dPush(left-right);

break;

case '*':

dPush(left*right);

break;

case '/':

if( right == 0.0 )

{

dPush(0.0);

}

else

{

dPush(left/right);

}

break;

case '^':

dPush(pow(left, right));

break;

}

p++;

}

if ( dTop != -1 )

{

num = dPop();

}

else

{

num = 0.0;

}

dFreeStack();

return num;

}

double CalcExp(const char* exp, bool *bError = NULL )

{

char post[256];

const char *p;

int count;

if( bError != NULL )

{

for ( p = exp, count = 0 ; *p ; p++ )

{

if( *p == '(' ) count++;

if( *p == ')' ) count--;

}

*bError = (count != 0);

}

MakePostfix(post, exp);

return CalcPostfix(post);

}

void main()

{

char exp[256];

bool bError;

double result;

const char *p = strchr("^*/+-", NULL);

strcpy(exp, "2.2+3.5*4.1"); printf("%s = %.2f\n", exp, CalcExp(exp));

for ( ;; )

{

printf("수식을 입력하세요(끝낼 때 0) : ");

gets(exp);

if( strcmp(exp, "0") == 0 ) break;

result = CalcExp(exp, &bError);

if( bError )

{

puts("수식의 괄호짝이 틀립니다.");

}

else

{

printf("%s = %.2f\n", exp, result);

}

표기식 변환을 위해서 문자열 스택이 필요하고 수식 계산을 위해서 실수형 스택이 필요해 각 타입별로 두 개의 스택을 만들었다. cStack과 dStack은 저장하는 데이터의 타입이 다를 뿐 동작하는 방식은 앞에서 만든 정수형 스택과 동일하다.

:: 후위 표기법

우리가 수식을 표기할 때 사용하는 표기법을 중위 표기법(Infix Notation)이라고 하는데 연산자가 가운데 오고 피연산자를 연산자의 양쪽에 쓰는 방식이다. 수학에서 이 방법을 사용하고 일상생활에서도 흔히 사용되므로 이런 표기법은 사람이 보기에는 좋지만 기계가 계산하기는 어렵다. 중위식 외에도 연산자의 위치에 따라 두가지 방법이 더 있다.

전위식(Prefix Notation) : 연산자가 앞쪽에 오고 피연산자가 뒤에 온다. +AB

후위식(Postfix Notation) : 피연산자가 앞쪽에 오고 연산자가 뒤에 온다. AB+

중위식	전위식	후위식
(A*B)+C	+*ABC	AB*C+
A*(B+C)	*A+BC	ABC+*

:: 후위식 변환

후위식이 계산이 아무리 편리하다 하더라도 사람이 후위식으로 입력하기는 불편하다. 그래서 중위식으로 입력된 연산식을 프로그램이 후위식으로 바꾸어 연산해야 한다.

모든 연산문을 우선 순위에 맞게 괄호로 전부 둘러싼다. 중위식은 괄호가 없으면 어떤 식이 먼저인지 알 수 없으므로 각 부분 연산식에 괄호가 있어야 한다.
연산자를 자신이 속한 괄호 바깥으로 보낸다. 즉, 두 피연산자 사이에 있는 연산자를 바로 뒤쪽으로 보낸다
후위식으로 바꾸면 이제 괄호는 필요가 없으므로 모두 제거한다.

:: 스택을 이용한 후위식 변환

문자열을 바로 조작하여 후위식으로 변환하는 방법은 직관적이고 쉽기는 하지만 중위식의 괄호가 완전해야 한다는 제약 조건이 있어 현실적으로 사용하기는 어렵다. 스택을 이용한 후위식 변환은 이에 비해 괄호가 완전하지 않고 일부 생략되어 있더라도 내부적인 우선 순위 규칙에 따라 후위식으로 변환 가능하다

다음은 스택을 이용하여 후위식으로 변환하는 절차이다.

숫자를 만나면 버퍼로 바로 출력한다. 숫자를 구성하는 연속된 문자를 모두 추출해서 하나의 수치값을 만들어야 하는데 정수이면 연속되는 아라비아 숫자를 출력하고 실수일 경우 소수점(.)도 같이 출력해야한다. 그리고 이어지는 다른 피연산자와의 구분을 위해 공백을 하나 삽입한다. 중위식은 피연산자들 사이에 연산자가 있지만 후위식은 피연산자가 동시에 둘 이상 연속으로 나올 수 있으므로 구분을 위한 공백이 필요하다.
연산자를 만나면 스택을 검사하여 자신보다 우선 순위가 높은 연산자를 모두 꺼내 출력한다. 예를 들어 *가 스택에 이미 들어가 있는 상태에서 +연산자를 만났다면 *가 먼저 연산될 수 있도록 한다. 그리고 자기 자신을 스택에 푸시하여 저장한다. 연산자는 일단 스택에 저장되어 차례를 기다려야 하는데 자신보다 낮은 연산자나 닫는 괄호, 또는 수식의 끝일 때 꺼내진다.
여는 괄호를 만나면 스택에 푸쉬한다. 여는 괄호는 닫는 괄호가 부분 수식의 시작점을 찾기 위해, 그리고 2번 규칙에서 높은 우선 순위의 연산자를 어디까지 찾을 것인가를 결정하기 위해 필요하다.
닫는 괄호를 만나면 여는 괄호가 나올 때까지 스택에 쌓여 있는 모든 연산자를 꺼내 출력한다. 괄호 안에 있는 식은 우선 연산되어야 하므로 다음 차례를 기다릴 필요없이 즉시 연산해야 한다. 양쪽 괄호는 우선 순위 지정을 위한 임무를 마쳤으므로 버퍼로 보낼 필요가 없다. 닫는 괄호는 단순히 무시하고 스택에 저장된 여는 괄호는 빼서 버린다. 중위식에서는 괄호가 연산 순위 지정을 위해 필요하지만 후위식에서는 필요하지 않다.
중위식이 끝날 때까지 1~4의 과정을 계속 반복한다. 모든 과정을 마친 후 스택에 남아 있는 연산자를 차례대로 꺼내 버퍼로 출력한다. 남아 있는 연산자들은 우선순위가 느린 연산자들이므로 제일 뒤쪽에 붙여야 한다.

:: 연산 우선 순위

괄호는 우선 순위를 지정하는 역할을 하므로 괄호가 있으면 괄호의 안쪽을 우선적으로 계산해야 한다. 그러나 괄호가 없는 수식에 대해서는 미리 정한 연산 순위 규칙에 따라 연산자를 배치하여 후위식으로 변환해야 한다.

연산자	우선 순위
(	0
+,-	1
*, /	2
^(누승)	3

괄호의 우선 순위가 가장 낮게 설정되어 있는 이유는 2번 규칙이 제대로 동작하기 위해서이다. 연산자를 만날 때 우선 순위가 높은 연산자를 스택에서 먼저 꺼내도록 되어 있는 연느 괄호의 왼쪽에 있는 연산자까지는 볼 필요가 없다.

예를 들어 2^(3*4+5)에서 ^이 스택에 먼저 들어가고 다음에 (, *가 들어가는데 +를 만났을 때 *을 우선적으로 꺼내야 하지만 괄호 바깥의 ^은 아직 꺼낼 필요가 없는 것이다. 스택에서 여는 괄호를 만났다면 현재 연산자가 괄호 안에 있다는 뜻이고 괄호의 안은 바깥보다 항상 우선이므로 괄호를 만나면 자신보다 높으느 연산자를 더 이상 찾지 않아도 된다.

:: 변환의 예

다음은 A+B*C를 후위식으로 바꾸는 절차이다.

입력 문자	출력 버퍼	스택	설명
A	A		숫자는 바로 출력
+	A	+	연산자는 스택에 저장
B	AB	+	숫자는 바로 출력
*	AB	+*	스택에 푸쉬. +가 *보다 낮으므로 꺼내지 않음
C	ABC	+*	숫자는 바로 출력
NULL	ABC*+		스택에서 역순으로 꺼냄

A*B+C를 후위식으로 변환

입력 문자	출력 버퍼	스택	설명
A	A		숫자는 바로 출력
*	A	*	연산자는 스택에 저장
B	AB	*	숫자는 바로 출력
+	AB*	+	+보다 가 높으므로 는 먼저 꺼낸다
C	AB*C	+	숫자는 바로 출력
NULL	AB*C+		남는 연산자를 꺼내 출력

(A+B)*C를 후위식으로 변환

입력 문자	출력 버퍼	스택	설명
(		(	여는 괄호는 바로 푸쉬
A	A	(	숫자는 바로 출력
+	A	(+	+푸시, (보다 +가 높으므로 팝 할 필요가 없다
B	AB	(+	숫자는 바로 출력
)	AB+		여는 괄호를 만날 때까지 모든 연산자 출력
*	AB+	*	*푸쉬
C	AB+C	*	숫자는 바로 출력
NULL	AB+C*		남은 연산자를 꺼내 출력

:: MakePostfix

예제에서 중위식을 후위식으로 변환하는 작업은 MakePostfix라는 함수로 구현하고 있는데 이 함수가 하는 일은 앞에서 설명한 공식을 그대로 코드로 옮긴 것 뿐이다. 변환에 필요한 스택을 생성하고 입력 버퍼 포인터 m을 뒤로 진행시키면서 만나는 문자별로 규칙에 따라 처리한다.

숫자는 있는 그대로 출력 버퍼로 보내되 연속되는 숫자를 모두 보낸다. 숫자를 구성하는 문자로는 아라비아 숫자와 소수점이 있다

연산자를 만나면 자신보다 높은 우선 순위의 연산자를 모두 꺼내 출력하되 스택 언더플로우는 점검한다. 스택에 대기 중인 연산자가 더 없으면 아무것도 꺼낼 필요가 없다.

여는 괄호는 단순히 푸시만 하고 닫는 괄호는 여는 괄호가 나올 때까지 모든 연산자를 팝해서 출력하고 여는 괄호는 버린다.

:: 후위식 계산

만들어진 후위식은 이제 기계적으로 연산하기만 하면된다. 피연산자가 먼저 오고 연산자가 나오므로 왼쪽부터 순서대로 읽어 나가다가 연산자를 만났을 때 앞쪽 두 연산자를 연산하면된다.

공백은 단순히 건너뛰기만 하면 되고 두 경우만 다음과 같이 처리한다.

숫자 : 숫자로 인식되는 부분만큼 읽어서 스택에 푸쉬한다. atof 함수로 변환하면 숫자로 인정되는 부분까지 자동으로 변환되므로 이 함수로 입력 버퍼를 숫자로 바꿔 푸시하기만 하면된다. 이렇게 저장된 숫자는 다음 연산자를 만날 때 피연산자로 사용된다. 푸시한 숫자는 건너 뛰어 입력 버퍼의 다음 위치에 맞춰 놓는다.
연산자 : 스택에 있는 피 연산자를 두 개 꺼내 연산한다. 입력 버퍼의 앞쪽부터 순서대로 읽어 왔다면 스택에는 최소한 두 개 이상의 숫자가 들어 있으므로 이 값을 꺼내연산하기만 하면 된다. 먼저 꺼내는 값이 우변이고 나중에 꺼내는 값이 좌변인데 덧셈, 곱셈은 순서가 중요하지 않지만 뺄셈, 나눗셈은 순서를 잘 지켜 연산해야 한다. 연산된 결과는 다른 연산식의 피연산자가 될 수 있으므로 다시 스택에 밀어 넣어야 한다.

이런 식으로 만나는 숫자와 연산자를 순서대로 처리하다가 널 문자를 만났을 때 스택에 마지막으로 남아 있는 값이 최종 연산 결과이다.

이 논리를 구현한 함수가 CalcPostfix함수이다. 후위식 연산을 위해서는 중간 과정의 피연산자를 스택에 저장해야 하므로 실수 스택을 만들고 이 스택에 숫자들을 푸시, 팝 하면서 연산했다.

"(34+93)*2-(42/2)"의 후위식 "34 93 + 2 * 43 2 / -"의 연산 과정을 보면 다음과 같다

입력 버퍼	스택	설명
34	34	숫자 푸시
93	34 93	숫자 푸시
+	127	34+93 연산 후 푸시
2	127 2	숫자 푸시
*	254	127*2 연산 후 푸시
43	254 43	숫자 푸시
2	254 43 2	숫자 푸시
/	254 21.5	43/2 연산 후 푸시
-	232.5	254-21.5 연산 후 푸시
NULL		스택에 남은 232.5를 결과로 취함

:: 예제 전체 분석

TextCalc예제는 상기 분석한 알고리즘대로 중위식을 후위식으로 바꾸고 후위식을 연산하여 결과를 출력한다.

중위식을 전달하면 후위식으로 바꾼 후 연산하는 랩퍼 함수 CalcExp를 작성했다. 이 함수는 연산하기 전에 기본적인 에러 점검을 하는데 괄호의 짝이 맞지 않을 경우 실패를 리턴한다.

이 예제는 후위식 변환을 위해 그리고 변환된 후위식 계산을 위해 두 개의 스택을 사용한다. 연산자의 경우 뒤쪽을 더 읽어 봐야 정확한 연산 순위를 알 수 있으므로 자기 차례가 될 때까지 잠시 대기해야 하며 계산식의 경우 부분식의 계산 결과가 이어지는 연산자의 피연산자로 사용되기 위해 임시적으로 저장되어야 한다. 그리고 연산자와 부분식 모두 들어간 역순으로 꺼내야 하므로 스택이 가장 적절한 자료구조이다.

19.4 큐

19.4.1 배열로 규현한 큐

큐는 스택과 반대로 FIFO(First In First Out)의 원리대로 동작하는 자료구조이다. 넣은 순서대로 자료를 꺼내가므로 순서대로 처리해야 하는 자료를 임시적으로 저장하는 용도로 흔히 사용한다.

저장되는 자료의 타입이 동일하므로 배열 또는 연결 리스트로 큐를 구현할 수 있다. 큐는 자료가 삽입되는 곳과 삭제되는 곳의 위치가 다르기 때문에 두 개의 포인터를 관리해야 한다. 여기서 포인터라고 함은 위치를 가리키는 값(offset)이라는 뜻이지 C의 포인터 타입과는 다른 뜻이다.

head : 다음 삭제될 위치를 가리킨다.
tail : 다음 삽입될 위치를 가리킨다.

큐를 초기화할 때 최초 head, tail은 모두 배열 선두인 0을 가리키는데 두 포인터가 같은 위치를 가리키면 대기 중인 데이터가 없고 큐가 비어있다는 뜻이다. 자료가 추가되면 tail 위치에 삽입되고 tail은 다음 칸으로 이동한다. 자료를 읽어서 삭제하면 head가 다음 칸으로 이동한다.

자료를 계속 삽입, 삭제 하다보면 배열의 뒤쪽 공간이 금방 부족해진다. 그런데 앞쪽에 먼저 들어왔던 자료들이 삭제되었기 때문에 공간이 비어 있다. 배열의 크기만큼 자료가 들어있지도 않은데 기억 공간이 부족해진 것이다. 큐의 자료는 빈번하게 삽입, 삭제되므로 배열 크기를 늘리는 것으로는 이 문제를 근본적으로 해결할 수 없다. 이 문제를 해결하려면 tail이 배열 끝에 닿았을 때 head의 데이터를 배열 처음으로 보내고 tail 직전까지의 모든 데이터를 앞쪽으로 복사해서 이동시킨다. 데이터가 이동하면 포인터도 따라서 이동해야 한다.

그러나 큐가 찰 때마다 이런식으로 매번 복사를 한다면 느리고 비효율적이다. 그래서 이 방법 대신 포인터가 배열의 끝에 닿았을 때 앞쪽으로 보내어 배열의 원형(Circular)으로 연결하는 방법을 많이 사용하는데 이는 %연산자로 간단하게 구현할 수 있다. head와 tail은 원형의 큐를 빙글 빙글 돌아가면서 자료를 삽입하고 삭제한다.

만약 삽입하는 속도가 삭제하는 속도보다 빨라 tail이 head를 따라 잡으면 큐가 가득찬 상태이다. head가 tail과 같은 상태는 큐가 빈 상태와 같으므로 두 포인터의 값만 비교해서는 큐의 정확한 상태를 알 수 없다. 그래서 head 앞의 한칸은 미사용으로 남겨 두어 tail이 head의 앞쪽에 있을 때, 즉 tail == head-1 일 때 큐가 가득찬 것으로 정의한다.

예제 ArrayQueue

#include <stdio.h>

#include <stdlib.h>

int *Queue;

int QSize;

int head, tail;

void InitQueue(int size)

{

QSize = size;

Queue = (int*)malloc(QSize*sizeof(int));

head = tail = 0;

}

void FreeQueue()

{

free(Queue);

}

bool Insert(int data)

{

if( (tail+1) % QSize == head )

{

return false;

}

Queue[tail] = data;

tail = (tail+1) % QSize;

return true;

}

int Delete()

{

int data;

if ( head == tail )

{

return -1;

}

data = Queue[head];

head = (head+1) % QSize;

return data;

}

void main()

{

int i;

InitQueue(10);

printf("빈 상태에서 삭제할 때 = %d\n", Delete());

for( i = 0 ; i < 9 ; i++ )

{

Insert(i);

}

printf("가득찬 상태에서 삽입 %s\n", Insert(100) ? "성공":"실패");

for ( i = 0 ; i < 9 ; i++ )

{

printf("%d ", Delete());

}

FreeQueue();

}

Queue 포인터가 큐이며 QSize는 큐의 크기, head, tail은 큐의 양끝 포인터이다.

InitQueue함수가 큐를 초기화하는데 인수로 전달받은 size만큼 Queue 배열을 할당하고 head, tail은 0으로 초기화한다. 이후 삽입, 삭제되면 head와 tail이 이동하면서 큐를 회전할 것이다. FreeQueue함순느 동적으로 할당된 Queue 배열을 해제한다

큐에 데이터를 삽입하는 Insert함수의 동작은 Queue[tail++] = data;로 설명할 수 있다. 이 코드에 두 가지 예외 처리가 추가되었다. 먼저 tail이 배열의 끝일 때 선두로 보내기 위해 QSize와 나머지 연산을 취한다. tail의 다음 위치는 tail+1이지만 배열 끝인 QSize에 이르렀을 때는 배열의 선두인 0으로 다시 돌아가야 한다. 또 큐가 가득 차서 더 이상 삽입할 수 없는 오버플로우도 처리하는데 tail의 다음 위치가 head와 같으면 에러 처리하고 리턴한다.

tail과 head사이에 사용하지 않는 빈칸을 하나 둠으로써 가득 찼을 때와 비어 있을 때를 구분할 수 있다.

Delete함수는 간단하게 return Queue[head++] 동작을 한다. head가 배열의 끝일 때 선두로 돌려보내고 큐가 비었을 때는 자료가 없다는 의미로 -1을 리턴한다.

19.4.2 연결 리스트로 구현한 큐

배열 대신 연결리스트로 구현하면 여러 가지 불편한 점을 해결할 수 있다.

예제 LinkedQueue

#include <stdio.h>

#include <stdlib.h>

struct node

{

int value;

node* prev;

node* next;

};

node *head;

void InitQueue()

{

head = (node*)malloc(sizeof(node));

head->prev = NULL;

head->next = NULL;

}

void Insert(int data)

{

node* newNode;

node* tail;

for( tail = head ; tail->next ; tail = tail->next ) {;}

newNode = (node*)malloc(sizeof(node));

newNode->value = data;

newNode->next = NULL;

newNode->prev = tail;

tail->next = newNode;

}

int Delete()

{

int data;

node* target;

target = head->next;

if( target == NULL )

{

return -1;

}

data = target->value;

head->next = target->next;

if( head->next )

{

head->next->prev = head;

}

free(target);

return data;

}

void FreeQueue()

{

while( Delete() != -1 ) {;}

free(head);

head = NULL;

}

void main()

{

int i ;

InitQueue();

for( i = 0 ; i < 100 ; i++ )

{

Insert(i);

}

for( i = 0 ; i < 100 ; i++ )

{

printf("%d ", Delete());

}

FreeQueue();

}

19.4.3 프린터 큐

큐는 하드웨어, 운영체제 등의 여러 곳에서 사용되는데 대표적으로 키보드의 키입력 큐를 들 수 있다. 키보드는 눌러진 키의 목록을 본체로 전송하는데 본체가 이 입력을 즉시즉시 받아들이지 못할 정도로 바쁠 수도 있으므로 입력된 키의 정보를 큐에 일단 저장한다. 그리고 본체는 큐에 쌓여진 키 코드를 입력된 순서대로 빼 내가는데 먼저 입력된 키를 먼저 가져가야 햐므로 FIFO의 원리로 움직이는 큐가 적합하다.

윈도우즈 운영체제의 메시지 큐도 대표적인 큐의 활용예이다. 키보드, 마우스, 타이머 등의 메시지들이 발생한 순서대로 큐에 쌓여 있다가 메시지 루프에 의해 순서대로 꺼내져 처리된다. 이 외에도 큐가 사용되는 곳은 아주 많은데 응용 프로그램이 큐를 필요로 한다면 언제든지 만들어 쓸 수 있다.

다음 예제는 프린터의 인쇄 시스템인 스풀러가 사용하는 큐를 시뮬레이션한다. 프린터의 인쇄 속도는 일반적으로 무척 느리기 때문에 문서를 보내는 즉시 인쇄하지 못한다. 그래서 인쇄할 문서 목록을 저장해 놓고 하나씩 꺼내 인쇄하는데 이때도 큐가 사용된다.

예제 PrintQueue

#include <stdio.h>

#include <stdlib.h> // malloc()

#include <time.h> // srand(time(NULL))

#include <conio.h> // srand()

#include <windows.h>// gotoxy(), wherex(), wherey()

int *Queue;

int QSize;

int head, tail;

void gotoxy(int x, int y);

int wherex();

int wherey();

void InitQueue(int size)

{

QSize = size;

Queue = (int*)malloc(QSize * sizeof(int));

head = tail = 0;

}

void FreeQueue()

{

free(Queue);

}

bool Insert(int data)

{

if ( (tail+1) % QSize == head )

{

return false;

}

Queue[tail] = data;

tail = (tail+1) % QSize;

return true;

}

int Delete()

{

int data;

if( head == tail )

{

return -1;

}

data = Queue[head];

head = (head+1)%QSize;

return data;

}

void PrintQueue()

{

int num;

int x, y;

num = tail-head;

if( num < 0 ) num += QSize;

x = wherex();

y = wherey();

gotoxy(0,0);

printf("대기 중인 문서 수 : %d", num);

}

void main()

{

int doc = -1;

int num;

srand(time(NULL));

InitQueue(128);

puts("인쇄 대기 중...");

for(;;)

{

if( kbhit()) if( getch() == ' ' ) break;

// 5초에 한번 꼴로 문서가 들어온다 페이지는 2~10페이지

if( rand()%5 == 0 )

{

num = rand()%9+2;

if( Insert(num) == true )

{

printf("%d페이지짜리 새 문서 삽입\n", num);

}

else

{

puts("큐가 가득참");

}

if( doc == -1 )

{

doc = Delete();

if( doc != -1 )

{

system("cls");

PrintQueue();

gotoxy(0, 5);

printf("%d 페이지짜리 문서 인쇄 시작\n", doc);

}

else

{

printf("%d페이지 인쇄중...\n",doc);

if( doc == 1)

{

doc = -1;

}

else

{

doc--;

}

Sleep(1000);

}

FreeQueue();

}

void gotoxy(int x, int y)

{

COORD Pos={x,y};

SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),Pos);

}

int wherex()

{

CONSOLE_SCREEN_BUFFER_INFO BufInfo;

GetConsoleScreenBufferInfo(GetStdHandle(STD_OUTPUT_HANDLE),&BufInfo);

return BufInfo.dwCursorPosition.X;

}

int wherey()

{

CONSOLE_SCREEN_BUFFER_INFO BufInfo;

GetConsoleScreenBufferInfo(GetStdHandle(STD_OUTPUT_HANDLE),&BufInfo);

return BufInfo.dwCursorPosition.Y;

}

5초에 한 번 꼴로 새로운 문서를 인쇄하는데 2~10페이지 정도의 길이를 가진다. 프린터가 초당 1페이지씩 인쇄한다고 가정하고 있으므로 인쇄하는 속도보다 쌓이는 속도가 더 빠르게 되어있다.

스택이나 큐 외에 양쪽 끝에 삽입, 삭제가 가능한 데크(Dequeue : Double Ended Queue)라는 자료구조도 있다. 데크는 원형의 배열과 두 개의 포인터로 구현하며 양 끝에서 삽입, 삭제 동작을 할 수 있다.

19.5 트리

19.5.1 트리의 용어

트리는 2차원적인 구조를 가진다. 구조가 입체적이고 다소 복잡하기 때문에 배열이나 연결리스트보다는 다루기 어렵고 까다롭다. 또한 스택이나 연결 리스트처럼 구현 방법이 정형화되어 있지 않고 적용하는 알고리즘에 따라 천차만별로 모양이 달라져 응용력을 필요로 하기도 한다.

그러나 입체적인 구조로 인해 자료의 삽입, 삭제 속도가 빠르면서도 검색 속도까지 만족할만하며 용량이 커지더라도 속도의 감소가 적어 대용량의 자료를 다룰 때 훨씬 더 효율적이다. 어느 정도 규모가 있고 복잡한 데이터를 다룰 때는 주로 트리가 사용되는데 사용 DB 엔진들도 트리 구조로 데이터를 관리한다. 디렉토리 구조나 기구도, 토너먼트 대진표 등과 같이 계층적인 자료들을 다룰 때도 트리가 가장 어울린다.

트리는 실제 데이터를 가지는 노드(Node)와 노드를 연결하는 링크(Link)로 구성된다. 위 그림에서 원처럼 표현된 것이 노드이며 원을 잇는 선분들이 링크인데 노드, 링크라는 용어 대신 버텍스(Vertex), 에지(Edge)라는 용어를 사용하기도 한다. 트리의 노드들은 항상 루트로 향하는 링크를 하나씩 가지는데 루트는 링크를 가지지 않으므로 링크의 개수는 항상 노드보다 하나 적다.

노드 중에 가장 기본이 되는 최상위 노드를 루트(Root)라고 부른다. 모든 트리는 단 하나의 유일한 루트를 가지며 루트 아래로 무수히 많은 노드들이 있다. 트리를 구성하는 노드끼리의 관계는 흔히 가족관계에 비유하는데 아래쪽의 노드를 자식이라고 하며 위쪽의 노드를 부모라고 한다. 같은 부모를 가진 노드들을 형제라고 한다

레벨(Level)은 루트에서의 거리를 의미하는데 루트의 레벨은 1이다.

경로(Path)란 특정 노드에서 다른 노드로 가는 길이다.

차수(Degree)는 자식 노드의 개수인데 B의 차수는 3, C의 차수는2, M의 차수는 0이다. 자식이 하나도 없는 노드를 잎(Leaf)노드 또는 외부(External)노드라고 하며 자식이 있는 노드를 내부(Internal)노드라고 한다.

노드의 자식들 사이에 순서가 있는 노드를 순서 트리(Ordered Tree)라고 하며 순서가 의미없는 노드를 비순서 트리(OrientedTree)라고 한다.

트리를 구성하는 작은 트리를 서브 트리(Sub Tree)라고 한다.

19.5.2 이진 트리

struct node

{

int data;

node *link;

};

data는 이 노드가 저장할 실제 데이터이며 link는 자식 노드들로 연결되는 링크의 배열이며 자식의 개수만큼 동적으로 할당된다.

자식의 개수가 정해져 있지 않기 때문의 노드의 차수에 따라 링크의 개수가 가변적이다. 동적 할당해서 만드는 노드의 멤버가 또 동적 할당을 한다면 관리하기 무척 번거롭고 불편해진다.

그래서 임의 차수를 지원하는 트리는 잘 사용하지 않고 이진 트리(Binary Tree)는 모든 노드의 차수가 2이하인 트리이며 구조가 단순하기 때문에 현실적으로 가장 많이 사용된다.

struct node

{

int data;

node *left;

node *right;

};

만약 부모 노드까지도 기억하고 싶다면 parent 포인터를 하나 더 추가하면 된다.

포화 이진 트리(Full Binary Tree) : 트리의 높이까지모든 노드가 가득찬 트리이다. 높이가 1이면 루트 하나만 있으므로 노드 개수는 1개이며, 높이가 2이면 루트와 양쪽 자식을 합쳐 세개의 노드가 존재한다. 일반적으로 높이가 n인 포화 이진 트리의 노드 개수는 2ⁿ-1개이다.
완전 이진 트리(Complete Binary Tree) : 포화 이진 트리의 노드를 좌에서 우로, 위에서 아래로 번호를 붙였을 때 번호가 큰 뒤쪽 노드만 생략된 트리이다.

19.5.3 트리의 순회

트리로 어떤 작업을 하려면 트리의 모든 노드를 한 번씩 방문하는 순회를 해야 한다. 그래야 노드의 값을 출력하거나 검색, 삭제 등의 작업을 할 수 있다.

여섯 가지 순회 방법을 생각할 수 있다.

루트 - 왼쪽 - 오른쪽
루트 - 오른쪽 - 왼쪽
왼쪽 - 루트 - 오른쪽
왼쪽 - 오른쪽 - 루트
오른쪽 - 루트 - 왼쪽
오른쪽 - 왼쪽 - 루트

이 중 왼쪽을 반드시 오른쪽보다 먼저 순회하도록 한다면 1,3,4 세가지만 남는다.

이 세 가지 순회 방법을 각각 전위 순회(PreOrder), 중위 순회(InOrder), 후위 순회(PostOrder)라고 하는데 루트의 방문 위치에 따라 일므을 붙인다.

차일드가 또 다른 자식을 가지고 있다면 차일드의 자식을 먼저 순회하고 돌아와야 하므로 트리의 순회함수들은 재귀적인 호출을 한다.

예제 TreeTraverse

#include <stdio.h>

#include <stdlib.h>

struct node

{

int data;

node *left;

node *right;

};

node *Root;

void InitTree(int data)

{

Root = (node*)malloc(sizeof(node));

Root->data = data;

}

node* AddChild(node* parent, int data, bool bLeft)

{

node* newNode;

newNode = (node*)malloc(sizeof(node));

newNode->data = data;

newNode->left = NULL;

newNode->right = NULL;

if( bLeft )

{

parent->left = newNode;

}

else

{

parent->right = newNode;

}

return newNode;

}

void PreOrder(node *r)

{

printf("%d ", r->data);

if( r->left ) PreOrder(r->left);

if( r->right ) PreOrder(r->right);

}

void InOrder( node *r)

{

if( r->left) InOrder( r->left );

printf("%d ", r->data);

if( r->right) InOrder( r->right );

}

void PostOrder( node *r )

{

if( r->left ) PostOrder( r->left );

if( r->right ) PostOrder( r->right );

printf("%d ", r->data );

}

void FreeTree(node *r)

{

if( r->left ) FreeTree( r->left );

if( r->right ) FreeTree( r->right ) ;

free(r);

}

void main()

{

node *left, *right;

InitTree(1);

left = AddChild(Root, 2, true );

right = AddChild( Root, 3, false );

AddChild(left, 4, true);

AddChild(left, 5, false);

AddChild(right, 6, true);

PreOrder(Root); puts("");

InOrder(Root); puts("");

PostOrder(Root); puts("");

FreeTree(Root);

}

이렇게 생성된 트리를 PreOrder, InOrder, PostOrder 방식으로 순회하며 노드의 data를 출력하였다.

생성한 트리를 해제하는 FreeTree 함수는 각 노드를 해제하되 자식 노드를 먼저 해제한 후 루트를 해야해야 하므로 후위 순회법을 사용한다.

레벨별 순회는 레벨이 낮은 순으로 노드를 방문하는 방식이다. 전위 중위, 후위 순회는 일단 주어진 서브 트리를 먼저 완전히 방문한 후 다음 서브 트리를 찾지만 레벨별 순회는 서브 트리를 기준으로 하지 않고 레벨을 기준으로 하므로 재귀 호출을 하지 않는다. 대신 노드를 만날 때마다 자신을 출력한 후 자신의 자식들을 차례대로 큐에 밀어 넣어 직계 자식들이 우선적으로 처리되도록 한다.

예제 LevelTraverse

#include <stdio.h>

#include <stdlib.h>

struct node

{

int data;

node *left;

node *right;

};

node *root;

node **Queue;

int QSize;

int head, tail;

void InitQueue(int size)

{

QSize = size;

Queue = (node**)malloc(QSize * sizeof(node*));

head = tail = 0;

}

void FreeQueue()

{

free(Queue);

}

bool Insert(node *data)

{

if( (tail+1) % QSize == head )

{

return false;

}

Queue[tail] = data;

tail = (tail+1) % QSize;

return true;

}

node *Delete()

{

node *data;

if( head == tail )

{

return NULL;

}

data = Queue[head];

head = (head+1) % QSize;

return data;

}

void InitTree(int data)

{

root = (node*)malloc(sizeof(node));

root->data = data;

}

node* AddChild(node *parent, int data, bool bLeft)

{

node *newNode;

newNode = (node*)malloc(sizeof(node));

newNode->data = data;

newNode->left = NULL;

newNode->right = NULL;

if( bLeft )

{

parent->left = newNode;

}

else

{

parent->right = newNode;

}

return newNode;

}

void FreeTree(node *r)

{

free(r);

}

void LevelOrder(node *r)

{

node *tNode;

Insert(r);

while( head != tail )

{

tNode = Delete();

printf("%d ", tNode->data);

if( tNode->left ) Insert(tNode->left);

if ( tNode->right ) Insert(tNode->right);

}

void main()

{

node *left, *right ;

InitQueue(128);

InitTree(1);

left = AddChild(root, 2, true);

right = AddChild(root, 3, false);

AddChild(left, 4, true);

AddChild(left, 5, false);

AddChild(right, 6, true);

LevelOrder(root); puts("");

FreeTree(root);

FreeQueue();

}

LevelOrder 함수는 큐에 저장된 노드를 순서대로 꺼내 출력하는데 먼저 루트부터 큐에 밀어 넣고 루프를 시작한다. 매 루프에서 큐에 최후로 저장된 노드를 꺼내 이 노드를 출력하고 자신의 차일드를 차례대로 큐에 삽입한다.

레벨별로 좌에수 우로 모든 노드를 큐에 삽입하면서 하나씩 꺼내 출력하면 레벨별 순회를 할 수 있다.

먼저 삽입된 노드가 먼저 처리되어야 하므로 이 경우는 큐가 가장 적절하다.

'책정리 > 혼자 연구하는 C,C++ 1' 카테고리의 다른 글

20장 알고리즘 (0)	2015.02.26
18장 C 고급 문법 (0)	2015.02.22
17장 파일 입출력 (0)	2015.02.22
16장 함수 고급 (0)	2015.02.20
15장 포인터 고급 (0)	2015.02.19

현재글19장 자료구조

GONI