배열

#먼저 추상데이터 타입 ADT(Abstract Data Type)에 대해서 알아보자!

추상 데이터 타입(Abstract Data Type, ADT)이란

: 추상적으로 수학적으로 정의된 데이터 타입

: 어떠한 자료와 자료의 연산이 정의되어 있다. 연산은 추상 데이터 유형과 외부 간의 인터페이스 역할을 한다. 실제로 자료와 연산이 어떻게 구현되었는 지는 사용자가 알 필요가 없다.

 

예를 들어, 자연수를 추상 데이터 타입으로 정의하자면,

자료는 0부터 INT_MAX까지의 정수

연산은 zero(), is_zero(), add(x,y), sub(x,y), equal(x,y), successor(x) 등이 될 수 있다.

 

일상 생활에서 추상 데이터 타입과 비슷한 사례를 찾아보면 자판기가 있을 수 있다. 자판기 안에서 어떤 일이 일어나는 지 모르지만, 원하는 음료수 버튼을 누르면 해당 음료수가 나오도록 되어있다. 이 때 버튼을 누르는 것이 연산을 통해 외부에서 추상 자료형 내부의 자료에 접근하는 것이라고 할 수 있다. 따라서 추상 자료형의 인터페이스(연산, 사용법)만 알면, 내부 자료나 실제 구현을 몰라도 사용할 수 있다.

 

프로그래밍 언어에서 ADT 구현

: C에서는 struct 를 활용하여 구현

: C++이나 java 에서는 class 를 활용한다. 

 

추상데이터 타입(1)

• 대부분의 프로그래머에게 배열은 단지 '연속된 메모리 위치'
– 구현의 관점에서 정의 → 일반적인 관점에서 정의할 필요가 있음
• 배열을 추상데이터 타입 ADT(Abstract Data Type) 관점에서 고려
• 정의: <index, value>쌍의 집합
– set of mappings (or correspondence) between index and values
– array : i → ai

ADT의 장점은 배열을 더 일반적인 구조로 설명 →구현에 독립적으로 설명

구현의 관점에서 배열

 

C언어에서의 배열(Arrays in C) (1)

• C의 일차원 배열:
        int list[5], *plist[5];     /* 5개의 정수 vs. 정수에 대한 5개 포인터*/
– 정수 값 : list[0], list[1], list[2], list[3], list[4]

– 정수포인터 : plist[0], plist[1], plist[2], plist[3], plist[4]

 

 

C언어에서의 배열(Arrays in C) (2)

-C에서 index가 0부터 시작하는 이유

Base Position에서의 Offset

offset : 기준점에서 얼마나 떨어져 있는지 메모리상에서 offset 포지션을 해야하기 떄문에 index를 0부터 시작

index : 기준점을 통해서 얼마만크 떨어져 있는지 offset을 나타낸다.

 

 

C언어에서의 배열(Arrays in C) (3)

◎포인터 해석

      int * list1;

      int list2[5];

- list2 = list2[0]를 가리키는 포인터

- list2 + i = list2[i]를 가리키는 포인터

- (list2+i) = &list2[i], *(list2+i) = list2[i]

 

C언어에서의 배열(Arrays in C) (4)

#define MAX_SIZE 100
float sum(float list[], int);
float input[MAX_SIZE], answer;
int i;
void main(void)
{
   for(i=0; i < MAX_SIZE; i++)
         input[i] = i;
   answer = sum(input, MAX_SIZE);               //호출 시 input(=&input[0])은 
   printf(“The sum is: %f\n”, answer);                주소를 담고 있고,주소가 
}                                                                         sum함수의 list에 복사

 

float sum(float list[], int n)                                //list -> call by reference
{                                                                         input의 주소를 list가 받아
int i;                                                                    input  배열을  list에 복사
float tempsum = 0;                                          //n -> call by value
for(i = 0; i < n; i++)                                            값을 그대로 변수 n에 복사 n이
   tempsum += list[i];                                     변경 되도 caller의 값은 변하지 않음
return tempsum;
}

 

 

C언어에서의 배열(Arrays in C) (5)

일차원 배열의 주소 계산
– int one[ ] = {0, 1, 2, 3, 4};
– print1(&one[0], 5)