C++로 쉽게 풀어쓴 자료구조/ 배열과 클래스

배열(Array)

배열의 개념

배열은 거의 모든 프로그래밍 언어에서 기본적으로 제공되는 자료형으로 많은 고급 자료구조들에서 사용된다. 배열은 주로 여러 개의 동일한 자료형의 데이터를 한꺼번에 만들 때 사용된다.

배열의 가장 기본적인 특징은 ‘인덱스, 요소’ 쌍의 집합이라는 것이다. 즉, 인덱스가 주어지면 해당하는 요소가 대응되는 자료구조이다. 배열에서는 모든 요소가 동일한 자료형이며 인덱스를 사용하여 직접 접근 할 수 있다.

배열의 추상 자료형

  • 객체
    • ‘인덱스, 요소’ 쌍의 집합
  • 연산
    • create(n): n개의 요소를 가진 배열을 생성한다.
    • retrieve(i): 배열의 i번째 요소를 반환한다.
    • store(i, item): 배열의 i번째 위치에 item을 저장한다.

배열과 메모리

함수의 파라미터로서의 배열

배열의 이름은 포인터의 역할을 한다. 즉, 배열의 이름을 전달하면 배열의 포인터가 전달되는 것이다. 따라서 함수 안에서 파라미터로 배열을 받아서 배열의 내용을 수정하면 원래의 배열이 수정된다.

C나 C++에서는 파라미터로 전달 받은 배열의 길이를 알 수 있는 방법이 없다. 따라서 배열을 전달할 때 반드시 배열의 길이도 함께 전달해야 한다. —C#으로 프로그래밍을 시작한 나에게 매우 놀라웠던 부분

만일 2차원 배열을 매개변수로 넘긴다면 해당 배열의 가로 값을 지정해줘야 한다. 2차원 배열을 넘길 때마다 가로 값을 지정해 주는 것은 번거롭기 때문에 보통은 동적 할당과 2중 포인터를 이용해서 이 문제를 해결한다.

클래스(Class)

구조체의 개념

배열이 같은 자료형의 데이터 모임이라면 구조체는 다양한 자료형의 데이터를 묶어주는 방법이다.

(이하 C++의 클래스 문법에 대한 설명은 생략)

배열과 클래스의 응용: 다항식 프로그램

다항식의 추상 자료형

p(x) = 10x5 + 6x + 3 와 같은 다항식을 프로그램에서 표현할 때는 배열을 이용하는 것이 간단하다. 앞의 식에서 값이 0인 계수를 모두 포함하면 p(x) = 10x5 + 0x4 + 0x3 + 0x2 + 6x + 3 이 되는데, 각 계수 (10, 0, 0, 0, 6, 3)을 배열에 저장하고 출력할 때 배열의 index를 기준으로 차수를 설정해 주면 된다.

10x100 + 6과 같은 다항식을 위와 같은 방법으로 표현하면 메모리 낭비가 커진다. 이런 경우 항의 정보를 (계수, 지수) 식으로 2차원 배열을 이용하여 저장하면 메모리 낭비를 막을 수 있다. 예컨대 10x100 + 6는 ( (10, 100), (6, 0) )이 된다.

[ssba]

The author

지성을 추구하는 디자이너/ suyeongpark@abyne.com

댓글 남기기

This site uses Akismet to reduce spam. Learn how your comment data is processed.