CS : 데이터 구조와 처리

<문자열>

여러 문자로 이뤄진 시퀀스를 문자열이라고 한다.

배열과 마찬가지로 문자열을 연산할 때도 그 길이를 알아야 한다.

한 가지 접근 방법은 문자열 안에 길이를 저장하는 것이다. 예를 들어 첫 번째 바이트에 문자열 길이를 넣을 수 있다.

이 방법은 잘 작동하지만 문자열 길이가 255자로 제한된다는 단점이 있다. 그리고 문자열은 바이트라서 메모리 정렬(alignment)이 그때그때 다를 수 있다. 하지만 길이를 저장하기 위해 몇 바이트를 할당하는 경우 길이 정보는 반드시 올바른 메모리 정렬 경계에 있어야 한다.

C는 PDP-11 어셈블리 언어의 .ASCIZ 의사명령어(pseudo-instruction)에서 빌려온 다른 접근 방법을 사용한다.

C는 다른 언어와 달리 문자열을 위한 전용 데이터 타입을 제공하지 않는다. 대신 1차원 바이트 배열을 사용한다. 문자열이 문자 배열이기 때문에 C에서 1바이트를 나타내는 데이터 이름이 char가 됬다.

하지만 C 문자열은 길이를 저장하지 않는다는 점이 다르다.

대신에 문자 배열에 들어있는 문자열 데이터 끝에 바이트를 하나 추가하고, 여기에 문자열의 끝을 표시하는 문자로 NUL을 넣는다. C는 아스키(ASCII) NUL문자, 즉 0을 문자열 터미네이터(string terminator, 문자열 끝을 표시하는 문자)로 사용한다. 이 방법은 아스키와 UTF-8 문자열에서 모두 사용할 수 있다.

그림을 보면 문자열 길이는 6이지만 실제로는 7바이트를 사용했음을 알 수 있다. 문자열 터미네이터에 1바이트가 더 쓰였기 때문이다.

장단점으로는 저장이 쉽다는 점은 아주 중요한 장점이고, 기본적으로 '문자열의 끝까지 각 문자를 출력하라'와 같은 일을 할 때 부가 비용이 들지 않는다는 점도 장점이다. 반면 문자열 길이를 알아내려면 문자열 터미네이터를 발견할 때 까지 문자열을 스캔하면서 문자 수를 세야 한다는 단점이 있다. 그리고 문자열 중간에 NUL 문자를 넣고 싶을 때는 이 방법을 사용할 수 없다.

<복합 데이터 타입>

현대적인 대부분의 언어는 여러분이 원하는대로 데이터 타입, 즉 '스위트(suite)'를 만들 수 있는 방법을 제공한다. 이를 '구조체structure'라고 한다.

구조체 스위트 안에 있는 여러 방을 구조체의 멤버(member)라고 한다.

그림 7-6은 일시를 C로 작성하며 표현한 구조체이다.

하지만 이런 구조가 꼭 필요한 것은 아니라는 점에 유의하라.

영국 컴퓨터과학자 피터 란딘(Peter Landin)은 1964년 이런식으로 프로그램을 더 ‘달콤하게’ 만들어주는 (비필수적) 요소에 대해 편의 문법(syntactic sugar)이라는 단어를 만들어 냈다.

물론 어떤 사람에게는 그냥 좀 편리하게 해주는 것에 불과한 요소가 다른사람에게는 필수 기능일 수도 있다. 이로 인해 격렬한 철학적 논쟁이 발생하기도 한다.

a =a+1을 a+=1이나 a++로 대신하는 경우가 편의 문법이라고 주장하는 사람은 아주 많지만, 구조체의 배열을 배열의 집합에 대한 편의 문법이라고 주장하는 사람은 더 적다.

일시를 표현하는 데이터 구조처럼 복잡한 데이터 타입을 마치 프로그래밍 언어가 기본 제공하는 데이터 타입처럼 사용할 수 있다.

그림 7-7은 일시를 표현하는 구조체 한 쌍과 이름을 나타내는 문자열을 담기 위한 작은 배열을 함께 조합해 사용하는 모습을 보여준다.

프로그래밍 언어는 멤버 순서가 바뀌면 문제가 될 수도 있기 때문에 프로그래머가 지정한 멤버 순서를 지킨다. 하지만 언어는 메모리 정렬도 지켜야 한다.

연도를 4번째와 5번째 바이트에 위치 시키면 경계에 걸치기 때문에 배치를 바꿔야 한다. 프로그래밍 언어 도구는 패딩(padding)을 필요한 만큼 추가해 이 문제를 해결한다. 일시 구조체의 실제 메모리 배치는 그림 7-8과 같다.

스위트 같은 데이터 구조 이외에 움직일 수 있는 파티션으로 구분한 사무실 같은 데이터 구조를 사용할 수도 있다. 이런 데이터 구조를 C에서는 공용체(union)라고 부른다.

 

<단일연결리스트>

배열은 물건 목록을 유지하는 가장 효율적인 방법이다.

배열은 실제 데이터만 저장하며 데이터 관리를 위한 부가 정보를 따로 요구하지 않는다.

연결 리스트(linked list)는 목록에 들어갈 원소 개수를 모르는 경우 배열보다 더 잘 작동한다. 단일 연결 리스트는 그림 7-10처럼 구조체를 사용해 만들 수 있다.

next는 리스트의 다음 원소 주소를 저장하는 포인터다. 리스트의 맨 앞은 헤드(head)라고 알려져있고, 리스트의 마지막은 테일(tail)이다.

그림 7-10 리스트와 배열의 가장 큰 차이는 배열의 각 원소는 메모리에서 연속적으로 위치하지만, 리스트 원소는 메모리에서 아무 위치에나 있을 수 있다는 점이다. 리스트 원소는 메모리에서 그림 7-11과 비슷하게 위치한다.

리스트에는 원소를 쉽게 추가 할 수 있다. 그림 7-12처럼 헤드 앞에 새 원소를 위치시키면 된다.

원소 삭제는 좀 더 복잡하다. 삭제할 리스트 원소의 바로 앞 원소의 next 포인터가 삭제할 원소의 next 포인터가 가리키는 원소를 가리키게 해야 하기 때문이다. 그림 7-13을 보라.

이런 식으로 포인터를 조작 하는 방법으로 포인터를 한 쌍 유지하는 방법을 들 수 있다.

그림 7-14와 같다.

current 포인터는 삭제할 노드를 검색하면서 리스트의 각 원소를 방문한다. previous 포인터를 통해 삭제할 노드 바로 앞 노드의 next 포인터를 조정할 수 있다. 점(.)을 사용해 구조체의 멤버를 가리킬 수 있다. 따라서 current.next는 현재 노드의 다음 노드(리스트의 다음 멤버)를 뜻한다.

그림 7-15의 알고리즘은 이중 간접 주소 지정(double indirect addressing)을 사용하면 이런 특별 취급을 없애서 더 간단한 코드를 만들어 낼 수 있다는 사실을 통해 이중 간접 주소 지정의 강력함을 보여준다. 이 알고리즘의 동작을 좀 더 자세히 살펴보려면 그림 7-16을 보면 cureent가 어떻게 변하는지를 보여준다. 리스트를 날짜, 이름등의 판단 기준에 따라 정렬하고 싶다면 이런 기능이 유용하다.