자료구조와 함께 배우는 알고리즘 입문 C언어편 - 9, 10장

9장_리스트

Published in

Quantum Ant

18 min readAug 31, 2019

*선형 리스트

리스트는데이터를 순서대로 나열한 자료구조이다. 그중 가장 간단한 리스트가 선형 리스트(linear list) 또는 연결 리스트(linked list)이다.
리스트의 데이터를 노드(node) 또는 요소(element)라고 한다. 각각의 노드는 데이터와 다음 노드를 가리키는 포인터를 포함하고 있다. 리스트의 맨 처음에 해당하는 리스트를 머리 노드라 하며 마지막에 해당하는 노드를 꼬리노드라고 한다.

배열로 선형 리스트 만들기

<그림 2>는 전화번호부를 선형 리스트로 저장하기 위해 배열로 구현한 것이다.

배열로 선형 리스트를 만들 때다음 노드를 꺼내고 싶을 경우 인덱스를 1만큼 늘려 다음 노드에 접근하면 된다.
<그림 2>처럼 새로운 노드를 중간에 삽입하려고 하는 경우 삽입 요소 다음의 모든 요소를 하나씩 뒤로 옮겨야 한다. 삭제할 때도 모든 요소를 뒤로 밀거나 앞으로 당겨야 한다. 이때 쌓이는 데이터의 크기를 미리 알아야 하며, 데이터의 삽입, 삭제에 따라 데이터를 모두 옮기기 때문에 효율이 떨어진다.

*포인터로 연결 리스트 만들기

연결 리스트에 데이터를 삽입할 때 노드용 객체를 만들고, 삭제할 때 노드용 객체를 없애면 데이터를 밀고 당기는 문제를 해결할 수 있다.

<그림 3>처럼 next에넣어두는 값은 다음 노드를 가리키는 값이다. 리스트의 마지막인 꼬리 노드의 next에는 널(NULL) 값을 대입한다.

노드를 만드는 AllocNode 함수

Node형 객체를 만들고 만든 객체의 포인터를 반환

노드의 멤버 값을 설정하는 SetNode 함수

Node형 객체의 두 멤버(data, next)의 값을 설정한다. 첫 번째 매개 변수는 n이 가리키는 Node형 객체에 두 번째 매개 변수 x가 가리키는 값을 대입하고 세 번째 매개변수가 전달하는 next를 n의 next에 대입한다.

연결 리스트 초기화하는 Initialize 함수

머리 노드를 가리키는 list->head에 널(NULL)을 대입하여 노드가 없는 연결리스트를 만든다. 또한 list->crnt에도 널을 대입하여 노드를 선택하지 않은 상태로 초기화한다.

검색을 수행하는 Search 함수

Search 함수는 어떤 조건을 만족하는 노드를 검색하는 함수이다. 만약 반화하는 값을 찾을 경우 찾은 노드에 대한 포인터를 반환하고 검색을 실패 했을 경우 널(NULL)을 반환한다.
<그림 6>
1. 스캔하고 있는 노드를 기리키는 변수 ptr을 list->로 초기화한다. <그림 7>

2. while문을 통해 조건을 만족하는 노드를 찾지 못하고 꼬리 노드를 스캔을 완료했는지 판단한다. ptr이 널이 아니면 루프 본문의 3, 4를 실행한다. 만약 ptr이 널이면 5를 실행한다.

3. 조건을 만족하는 노드인지 판단하기 위해 compare 함수를 통해 노드의 데이터와 x가 가리키는 데이터를 비교한다. comapre 함수는 비교한 것이 같으면 0을 반환한다. 0을 반환할 경우 list->cmt 에 ptr을 대입하고 찾은 노드에 대한 포인터(ptr)를 반환한다.

4. ptr에 ptr->next를 대입한여 ptr의 다음 노드를 가리키게 하여 계속 스캔을 이어간다. (<그림 7>에서 a->b->c 로 업데이트)

5. 검색을 실패하여 널을 반환한다.

머리에 노드를 삽입하는 InsertFront 함수

연결 리스트의 머리에 노드를 삽입하는 함수이다.

삽입 전의 머리 노드 A에 대한 포인터를 ptr에 대입한다.
삽입할 노드 G를 AllocNode 함수로 만들고 list->head가 노드 G를 가리키도록 업데이트한다.
SetNode 함수를 이용하여 값을 설정한다. 노드 G의 다음 노드(next)에 ptr(삽입 전 머리 노드)를 대입한다.

꼬리에 노드를 삽입하는 InsertRear 함수

연결 리스트의 꼬리에 노드를 삽입하는 함수이다.

리스트가 비어 있을 경우 InsertFront 함수로 처리한다.
리스트가 비어 있지 않을 경우 머리 노드를 가리키는도록 초기화한 ptr이 꼬리 노드를 가리키도록 업데이트를 반복한다. ptr->next가 가리키는 노드가 널이 되면 while문을 종료한다. 이때 ptr은 꼬리 노드(F)를 가리킨다.
삽입할 노드 G를 Allocnode 함수로 만든다. 그 후 삽입 전 꼬리 노드(F)의 다음 포인터 ptr->next가 가리키는 노드에 노드 G를 대입한다. 마지막으로 SetNode 함수를 통해 노드 G의 값을 설정한다. 이때 노드 G의 다음 노드에 널을 대입한다.

머리 노드를 삭제하는 RemoveFront 함수

리스트가 비어 있지 않은 경우 머리 노드를 삭제하는 함수이다. 만 머리 노드 A를 삭제하기 위해 머리 노드에 대한 포인터 list ->head에 두 번째 노드 B에 대한 포인터 list->head->next를 대입한다. 그 후 머리 노드 A의 메모리 영역을 해제한다. 선택한 노드(crnt)를 새 머리 노드인 B로 업데이트한다.

꼬리 노드 삭제하는 RemoveRear 함수

꼬리 노드를 삭제하는 함수이다.

리스트에 노드가 1개만 있을 경우 RemoveFront 함수를 실행하여 삭제한다.
리스트에 노드가 2개 이상 있을 경우 꼬리 노드(F)와 꼬리 이전 노드(E)를 찾아야 한다.
꼬리 이전 노드(E)의 다음을 가리키는 포인터에 널을 대입하고 꼬리노드(F)의 메모리 영역을 해제한다.

선택한 노드를 삭제하는 RemoveCurrent 함수

현재 선택한 노드(list->crnt)를 삭제하는 함수이다.

선택한 노드가 머리 노드일 경우 RemoveFront 함수로 처리한다.
선택한 노드가 머리 노드가 아닐 경우 선택한 노드의 앞 노드(ptr)를 찾는다. ptr->next와 list->crnt가 같을 때까지 while문을 반복한다. ptr은 선택한 노드의 앞 노드(C)가 된다.
선택한 노드(D)의 다음 노드 포인터 lsit->crnt->next를 선택한 노드의 앞 노드(C)의 다음 포인터(ptr->next)에 대입한다. 선택한 노드(D)를 해제하고 list->crnt를 해제한 노드의 앞 노드(C)로 업데이트한다.

모든 노드를 삭제하는 Clear 함수

연결 리스트의 모든 노드를 삭제하는 함수이다. 연결 리스트가 완전히 빈 상태가 될 때까지 RemoveFront 함수를 반복 실행한다.

연결 리스트를 종료하는 Terminate 함수

연결 리스트를 종료하는 함수이다. 모든 노드를 삭제하는 Clear 함수를 호출한다.

포인터를 이용한 연결 리스트는 데이터의 이동 없이 노드의 삽입, 삭제를 수행할 수 있는다는 특징이 있지만 이것을 수행할 때마다 메모리 영역을 만들고 해제해야하는 단점이 있다.

*커서로 연결 리스트 만들기

커서를 이용한 연결 리스트는 프로그램 실행 중에 데이터의 개수가 크게 바뀌지 않고 데이터의 최댓값을 미리 알 수 있을 때 효율적으로 이용할 수 있다.

배열의 커서에 해당하는 값은 다음 노드에 해당하는 값은 다음 노드에 대한 포인터가 아닌 다음 노드가 들어 있는 요소의 인덱스 값이다.

배열의 비어 있는 요소 처리하기

커서로 연결 리스트를 만들 때에는 ‘삭제한 노드 관리’가 중요하다. <그림 17>©가 끝난 상태는 빈 레코드가 있어 효율이 떨어진다. 효율을 높이기 위해 프리 리스트를 이용하여 삭제한 레코드를 관리한다.

새로운 노드를 추가할 때 가장 꼬리쪽에 있는 레코드(6)의 다음 레코드(7)에 저장하는 것이 아닌 프리 리스트의 머리 노드(3)에 저장한다. 그 후 프리 리스트의 머리 노드를 머리 노드(3) 다음 노드(1)로 업데이트한다.
레코드를 삭제할 때 삭제하는 레코드의 인덱스를 프리 리스트의 헤더로 업데이트해 비여있는 요소를 처리한다.

*원형 이중 연결 리스트

원형 리스트란 꼬리 노드가 머리 노드를 가리키는 선형 리스트를 뜻한다. 즉 꼬리 노드의 다음 노드를 가리키는 포인터가 널이 아닌 머리 노드의 포인터인 것이다.

이중 연결 리스트는 선형 리슽트의 단점인 앞 노드를 찾을 수 없다는 점을 보완한 자료구조이다.

원형 이중 연결 리스트는 원형 리스트의 개념과 이중 연결 리스트의 개념을 합한 자료구조이다.

노드를 생성하는 AllocDnode 함수

Dnode형 객체를 생성하고 핻당 객체의 포인터를 반환하다.

노드의 멤버 값을 설정하는 SetDnode 함수

Dnode형 객체의 멤버 값을 설정한다. 첫 번째 매개변수 n은 Dnode형 객체 포인터, 객체 멤버 data, prev, next는 각각 두 번째, 세 번째 ,네 번째 매개변수에 해당 된다.

원형 이중 연결 리스트를 초기화하는 Initialize 함수

텅 빈 상태의 원형 이중 연결 리스트를 만든다. 노드 삽입, 삭제를 수행하기위한 비어 있는 노드를 1개 만드는데 이 노드를 더미노드라고 한다. 더미 노드의 앞쪽 포인터prev와 뒤쪽 포인터next를 자기 자신으로 설정하여 초기화 시킨다.

리스트가 비어 있는지 검사하는 IsEmpty함수

리스트가 비어 있는지 검사하는 함수이다. 더미 노드인 list->head와 list->head->next, list->head->prev가 같으면 리스트가 비어 있는 상태이며 함수의 반환 값은 비어 있을 경우 1, 아닐 경우 0이다.

노드를 검색하는 Search 함수

리스트에서 노드를 선형 검색하는 함수이다. 머리 노드는 더미 노드 다음 노드이므로 list->head가 아닌 list->head->next부터 검색을 시작한다.

선택한 노드의 다음으로 진행시키는 Next 함수

선택한 노드의 다음 노드로 진행시키는 함수이다. 리스트가 비어 있지 않고 선택한 노드의 다음 노드가 잇을 경우에만 작동한다. 성공 시 1, 실패 시 0을 반환한다.

선택한 노드의 앞쪽으로 진행시키는 함수 Prev 함수

선택한 노드의 앞쪽 노드로 되돌아가게 하는 함수이다.

바로 다음 노드에 삽입하는 InsertAfter 함수

포인터 p가 가리키는 노드의 바로 다음에 새로운 노드를 삽입하는 함수이다.

머리에 노드를 삽입하는 InsertFront 함수

리스트의 머리에 노드를 삽입한는 함수이다. 더미 노드의 바로 뒤에 삽입한다.

꼬리에 노드를 삽입하는 InsertRear 함수

리스트의 머리에 노드를 삽입하는 함수이다.

노드를 삭제하는 Remove 함수

p가 가리키는 노드를 삭제하는 함수이다.

머리 노드를 삭제하는 RemoveFront 함수

머리 노드를 삭제하는 함수이다. 더미 노드는 삭제되면 안되므로 리스트가 비어있는지 확인한다. 리스트가 비어 있다면 실행하지 않는다.

꼬리 노드를 삭제하는 RemoveRear 함수

꼬리 노드를 삭제하는 함수이다.

선택한 노드를 삭제하는 RemoveCurrent 함수

선택한 노드를 삭제하는 함수이다.

모든 노드를 삭제하는 Clear 함수

더미 노드를 제외한 모든 노드를 삭제하는 함수이다.

원형 이중 연결 리스트를 종료하는 Terminate함수

원형 이중 연결 리스트를 종료하는 함수이다.

10장_트리

*트리 관련 용어

루트

트리의 가장 윗부분에 위치한 노드를 루트라고 한다.

리프

트리의 가장 아랫부분에 위치하는 노드를 리프라고한다. ‘가장 아래에 위치한다’라는 말은 물리적인 위치의 의미가 아닌 더 이상 뻗어나갈 수 없는 마지막을 의미한다.

안쪽 노드

루트를 포함하고 리프를 제외한 노드를 안쪽 노드라고 한다.

서브 트리

트리 안에서 다시 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리를 서브 트리라고 한다.

자식

어떤 노드로부터 가지로 연결된 아래쪽 노드를 자식이라고 한다.

부모

어떤 노드로부터 가지로 연결도니 위쪽 노드를 부모라고 한다.

형제

같은 부모를 가지는 노드를 형제라고 한다.

조상

어떤 노드에서 가지로 연결된 위쪽 노드 모두를 조상이라고 한다.

자손

어떤 노드에서 가지로 연결된 아래쪽 노드 모두를 자손이라고 한다.

레벨

루트로부터 얼머나 떨어져 있는지에 대한 값을 레벨이라고 한다.

차수

노드가 갖는 자식의 수를 차수라고 한다.

높이

루트부터 가장 멀리 떨어진 리프까지의 거리를 높이라고 한다. <그림 32>의 트리 높이는 3이다.

순서 트리와 무순서 트리

형제 노드의 순서가 있는지 없는지에 따라 트리를 두 종류로 분류한다. 순서를 따지면 순서 트리, 따지지 않으면 무순서 트리라고 한다.

*순서트리 탐색

순서 트리의 노드를 스캔하는 방법은 너비 우선 탐색, 깊이 우선 탐색 두 가지 방법이 있다.

너비우선 탐색

낮은 레벨에서 시작해 왼쪽에서 오른쪽 방향으로 검색하고 그 레벨이 끝나면 다음 레벨로 내려가는 탐색이다.
<그림 33>의 탐색 순서는 [A->B->C->D->E->F->G-.H->I->J->K->L]

깊이 우선 탐색

깊이 우선 탐색은 리프까지 내려가면서 검색하는 것을 우선순위로 하는 탐색 방법이다. 깊이 우선 탐색에는 3가지 방식이 있다.

전위 순회

[노드 방문 -> 왼쪽 자식 -> 오른쪽 자식] 의 순으로 우선 탐색한다. <그림 34>를 보면 노드 A를 지나가는 경우는 다음과 같다. [A방문 -> B로 이동 -> C로 이동] 전위 순회로 깊이 우선 탐색을 진행하면 다음과 같은 순서로 방문한다. [A->B->D->H->E->I->J->C->F->K->L->G]

중위 순회

[왼쪽 자식 -> 노드 방문 -> 오른쪽 자식]의 순으로 우선 탐색을 한다. 노드 A를 지나가는 경우는 다음과 같다. [B로 이동 -> A방문 -> C로 이동] 중위 순회로 깊이 우선 탐색을 진행하면[H->D->B->I->E->J->A->K->F->L->C->G] 순으로 방문한다.

후위 순회

[왼쪽 자식 -> 오른쪽 자식 -> 노드 방문]의 순으로 우선 탐색을 한다. 노드 A를 지나가는 경우는 다음과 같다. [B로 이동 -> C로 이동 -> A방문] 후위 순회로 깊이 우선 탐색을 진행하면[H->D->I->J->E->B->K->L->F->G->C->A]순으로 방문한다.

*이진트리와 이진검색트리

이진트리란 노드가 왼쪽 자식, 오른쪽 자식을 갖는 트리를 말한다. 각 노드의 자식은 2명이하(차수가 2이하)를 유지해야한다. 이진트리는 왼쪽 자식과 오른쪽 자식을 구분한다.
완전이진트리란 루트부터노드가 채워져 있는 이진트리이다.

이진검색트리

이진트리가 다음 조건을 만족하면 이진검색트리라고 부른다.

어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값을 N의 값보다 작아야 한다.
오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야 한다.
같은 키 값을 갖는 노드는 없다.

이진검색트리를 중위 선회하면 키 값을 오름차순으로 노드를 얻을 수 있다. 또한 구조가 단순하고, 비슷한 방식으로 검색이 가능하며 노드의 삽입이 쉽다.

노드를 생성하는 AllocBinNode 함수

BinNode형 객체를 만드는 함수이다.

노드 멤버의 값을 설정하는 SetBinNode 함수

BinNode형 객체의 멤버 값을 설정하는 함수이다. 첫 번째 매개변수 n이 가리키는 Binnode형 객체에 두 번째 매개변수, 세 번째 매개변수, 네 번째 매개변수를 각각 객체 멤버 data, left, right를 대입한다.

비어 있는 상태의 이진 검색트리 만들기

루트 노드를 가리키는 BinNode형 객체를 널 값을 대입하면 비어있는 이진검색트리를 만들 수 있다.

키 값으로 검색하는 Search 함수

검색하는 값 Key와 선택한 노드 p의 키 값을 비교하여 같으면 p 반환(검색 종료), key가 p의 키 값보다 작으면 선택한 노드(p)에 왼쪽 자식 노드 대입,(왼쪽으로 검색 진행), key가 p의 키 값보다 크면 선택한 노드에 오른쪽 자식 노드 대입한다. 이 과정을 반복하여 검색을 실행한다.