자료구조의 개념과 정의에 대해 대략적인 내용이 적혀있습니다. 이 글을 통해, 자료구조란 무엇인가부터 그 개념이 어떠한 것인지에 대해 알아볼 수 있습니다. 세부 구체적인 자료구조들에 대해서는 다음 글에 이어집니다.
자료구조의 개념
자료구조에서는 프로그래밍 문제에서 처리해야 할 자료 객체들과 그들의 속성을 파악하여, 이들 사이의 상관관계와 처리 연산들을 정의하고 구현하는 것에 대한 체계적이고 효율적인 방법을 연구합니다. 프로그래밍 관점에서 보면, 자료구조는 프로그램의 변수들과 그 처리 함수들 형태로 구현되지만 자료의 관점에서 보면 , 현실세계에서 처리해야 할 자료 객체들을 처리 목적을 고려하여 체계적이고 효율적인 프로그래밍 객체로 모델링해서 표현하고 관리하는 것입니다. 자료구조에서 현실세계로부터 처리해야 할 자료 객체(data object)들을 파악하여 모델링하는 과정은 그림 1,2와 같이 논리적 자료 추상화(logical data abstraction)와 물리적 자료 추상화(physical data abstraction)의 두 과정으로 구분해서 이해할 수 있습니다. 논리적 자료 추상화는 현실세계의 자료 객체들을 처리 목적을 고려하여 사람들이 정확하게 인식하고 이해할 수 있는 요약된 논리적 자료 객체로 모델링해서 나타내는 것이고, 물리적 자료 추상화는 이를 프로그래밍 구현을 통해 실제 컴퓨터 내부 메모리에 효율적으로 저장해서 관리하는 것으로 자료구조의 구현(implementation)이라고 합니다.
예를 들면, 현실세계의 자료 객체들인 과일 정보를 자료구조로 표현한다면, 먼저 현실세계의 과일들을 각각 사과 4개, 배 3, 과일 7개 등과 같이 사람들이 인식할 수 있는 약속된 추상 개념(abstract concept)의 자료 객체들로 이해해서 이들을 문자(예: apple, pear, fruit), 수치(예: 3, 4, 7) 등과 같은 약속된 심벌(기호) 들을 이용하여 표현하고 이들에 대해 +, - 등과 같은 필요한 처리 연산들을 정의해서 논리적인 관계구조를 설계하고, 이를 프로그래밍을 통해 컴퓨터 시스템에 구현하게 됩니다.
논리적 자료 추상화 과정에서는 처리의 편의를 위해 현실세계의 자료 객체들을 처리 목적에 관련된 속성들(attributes)과 연산들(operations)만으로 요약해서 추상화된 개념의 객체들로 표현하게 되는데, 이렇게 표현한 추상화된 자료 객체들의 표현과 연산 집합을 논리적 자료구조(logical data structure)라고 합니다. 논리적 자료구조는 자료 객체들의 모든 실제 속성과 연산들을 표현한 것이 아니라 논리적 처리에 필요한 속성들과 연산들을 상실하지 않는 범위에서 최대한 요약해서 표현한 것입니다. 그리고 이런 논리적 자료구조를 프로그래밍을 통해 컴퓨터 내부의 메모리 표현으로 구현할 때는, 자료 객체들의 논리적 구조가 가진 의미를 상실하지 않는 범위에서 가능하면 메모리를 적게 사용하고, 필요할 때 신속하게 자료에 접근할 수 있는 방법을 고려하게 됩니다. 일반적으로 자료구조라고 하면, 자료 추상화를 통해 현실세계의 자료 객체들을 추상화된 자료 객체들의 집합과 처리 연산들의 집합으로 모델링하는 논리적 자료구조를 의미합니다. 넓은 의미로 보면 그 구현까지도 포함합니다. 이 책에서는 다루는 자료구조들은 먼저 해당 자료구조의 논리적 개념을 간단히 설명하고, 이를 C 프로그래밍을 통해 효과적으로 구현하는 방법들에 대해 설명합니다.
자료구조의 정의
자료구조 D는 처리해야 할 현실세계의 자료 객체들을 논리적 자료 추상화를 통해 표현된 추상 자료 객체들의 집합 Object와 이 객체 집합에 대한 처리 연산들의 집합 Operation입니다. 즉, D = <Object, Operation>입니다. 여기서, Object={x|x is an abstract obejct}이고, Operation = {f() | f() is an operation defined on Object}입니다.
위의 내용은 자료구조의 개념을 형식적으로 정의한 것입니다. 예를 들면 대부분의 프로그래밍 언어에서 기본 자료형으로 제공하는 정수와 배열은 다음 글에서 알아보도록 하겠습니다.
댓글