문자열 자료는 한 글자만 표현할 수 있는 문자 자료와 달리 여러 글자로 이루어진 문자 그룹을 하나의 자료로 취급하여 메모리에 연속적으로 저장하는 자료 형식이다. 문자열 하나는 부분 문자열을 여러개 포함할 수 있다.

부분 문자열을 포함하는 문자열 자료를 메모리에 저장하는 방법에는 다음 세 가지가 있다.

① 부분 문자열 사이에 구분자를 사용하여 저장한다.

② 가장 긴 문자열의 길이에 맞춰 고정 길이로 저장한다.

③ 부분 문자열을 연속하여 저장하고 각 부분 문자열에 대한 포인터를 사용한다.

[그림 1-22]와 같이 {COMPUTER, DATA STRUCTURE, STRING}과 같은 부분 문자열 세 개로 구성된 문자열 자료구조를 메모리에 저장하는 방법을 살펴보자. ①번 방법을 이용한 (a)는 표현하기는 간단하지만 필요한 부분 문자열을 찾아야 할 때 문자를 비교하여 구분자를 식별해야 하므로 연산하거나 처리하는 데 시간이 많이 든다. ②번 방법을 이용한 (b)는 부분 문자열 중 가장 긴 문자열의 길이를 고정 길이로 이용한다. 부분 문자열마다 저장되는 고정 길이가 같기 떄문에 부분 문자열을 찾기는 쉽지만 부부 문자열의 길이 차이가 큰 경우에는 사용하지 않는 공간이 늘어난다. ③번 방법을 이용한 (c)는 부분 문자열에 대한 주소와 문자열의 마지막 주소를 포인터에 젖아하여 포인터 주소 연산으로 부분 문자열을 찾는다.

[그림 1-22] 문자열 자료의 표현 예 : {COMPUTER, DATA STRUCTURE, STRING} 저장

문자열을 표현하는 세 가지 방법의 메모리 이용률과 부분 문자열 탐색 시간을 비교하면 [표 1-7]과 같다.

[표 1-7] 문자열 표현 방법 비교