Chapter 12 - Pointers and Arrays

Ch11 introduced pointers, and how they're used as function arguments, values returned by the functions.

포인터가 배열의 원소를 가리킬 때, 포인터에 덧셈과 뺄셈 연산을 할 수 있다. 

포인터와 배열의 관계는 C를 마스터하는데 critical한 부분이다. 그러나 배열을 다루는데 포인터를 써야 하는 가장 큰 이유 - 효율성- 은 예전만큼 중요하지 않은데, 컴파일러들이 더 발전했기 때문이다.

12.1 pointer arithmetic and how pointers can be compared using the relational and equality operators

12.2 how we can use pointer arithmetic for processing array elements

12.3 array name can serve as a pointer to the array's first element

12.4 how the topcis of first three sections apply to multidimensional arrays

12.5 wrap-up, by exploring the relationship between pointers and variable-length arrays (C99)

12.1 Pointer Arithmetic

int a[10], *p;

라고 정의 되어 있을 때,

p = &a[0]; 

=> p가 a[0]을 가리키게 한다.

그림으로 보면 위와 같다.

*p = 5; 라고 하면, a[0]자리에 5가 들어간다.

포인터에 pointer arithmetic (or address arithmetic)을 수행함으로써 배열의 다른 원소에 접근할 수 있다.

pointer arithmetic에는 다음 세가지 종류가 있다.

1. Adding an integer to a pointer

2. Subtracting an integer from a pointer

3. Subtracting one pointer from another

각각의 연산을 살펴보자. 다음부터 나올 예시에서는 다음 선언이 유효하다고 가정한다.

int a[10], *p, *q, i;

Adding an Integer to a Pointer

포인터 p의 값에 정수 j를 더하면, p가 가리키는 원소에서 j자리만큼 뒤의 원소를 가리킨다.

만약 p가 a[i]를 가리킨다면, p + j는 a[i+j]를 가리킨다(물론 a[i+j]가 있다는 전제 하이다).

p = &a[2];

q = p + 3;

p += 6;

Subtracting an Integer from a Pointer

p가 a[i]를 가리킬 때, p - j 는 a[i-j]를 가리키게 된다.

p = &a[8];

q = p - 3;

p -= 6;

Subtracting One Pointer from Another

포인터끼리 뺄셈을 수행했을 때, 그 결과는 포인터 간의 거리(measured in array elements)이다.

p가 a[i]를 가리키고 q가 a[j]를 가리킬 때, p - q는 i - j와 같다.

p = &a[2];

q = &a[5];

i = p - q;    /* i is 3 */

i = q - p;    /* i is -3 */

※ 배열의 원소를 가리키지 않는 포인터에 연산을 수행하는 것은 undefined behavior를 일으킨다. 나아가, 한 포인터에서 다른 포인터를 빼는 것도 두 포인터가 같은 배열의 원소를 가리키지 않으면 undefined behavior를 일으킨다.

Comparing Pointers

관계 연산자(<, <=, >, >=)와 동등 연산자(==)를 통해 복수의 포인터를 비교할 수 있다.

두 포인터에 관계 연산자를 사용하는 것은 두 포인터가 같은 배열에 있는 원소를 가리킬 때만 의미가 있다.

비교의 결과는 두 원소의 상대적인 포지션의 결과에 따른다. 예를 들어,

p = &a[5];

q = &a[1];

이면, p<=q의 값은 0이고 p>=q의 값은 1이다.

12.2 Using Pointers for Array Processing

Pointer arithmetic을 통해 배열의 원소에 반복적으로 증가하는 포인터 변수를 통해 하나하나 접근할 수 있다.

#define N 10

...

int a[N], sum, *p;

...

sum = 0;

for(p = &a[0]; p < &a[N]; p++)

sum += *p;

포인터를 사용하지 않고도 쉽게 loop문을 subscripting (a[i])을 이용해 쓸 수 있다.

subscripting 대신 pointer arithmetic을 써야 한다는 주장의 가장 큰 근거는 실행 속도가 더 빠르다는 것인데, 이는 implementation에 따라 다르다. 어떤 컴파일러는 subscripting을 사용할 때 더 나은 코드가 되기도 한다.

Combining the * and ++ Operators

배열의 원소를 다루는 statement에서 흔하게 * (indirection)과 ++ 연산자를 혼합해서 사용한다.

간단한 예로 한 배열 원소에 값을 저장하고, 다음 원소로 넘어가는 경우를 생각하자.

array subscripting 사용시,

a[i++] = j;

p가 배열 원소를 가리키고 있다면, 그에 대응하는 statement는

*p++ = j;

postfix ++연산자는 *보다 우선순위가 빠르기 때문에, 컴파일러는 위 식(expression)을 다음과 같이 본다.

*(p++) = j;

p++의 값은 p이다(postfix ++연산자를 사용하고 있는데, p의 값은 다음 expression(여기서는 j)이 evaluated되기 전까지는 증가하지 않는다).

따라서 *(p++)의 값은 *p, 즉 p가 가리키는 object이다.

(*p)++는 p가 가리키는 object의 값을 반환한 후, 그 object의 값을 1 증가시킨다(p 자체는 변하지 않는다).

Expression	Meaning
*p++ or *(p++)	Value of expression is *p before increment; increment p later
(*p)++	Value of expression is *p before increment; increment *p later
*++p or *(++p)	Increment p first; value of expression is *p after increment
++*p or ++(*p)	Increment *p first; value of expression is *p after increment

4개의 표현은 모두 사용하지만, *p++를 더 자주 사용한다. 이 표현은 loop에서 유용하다.

for (p = &a[0]; p < &a[N]; p++)

sum += *p;

대신에

p = &a[0];

while (p < &a[N])

sum += *p++;

라고 쓸 수 있다.

10.2에서 사용했던 stack에서 integer variable이었던 top을 바꿔 보자.

int *top_ptr = &contents[0];

void push(int i)

{

if (is_full())

stack_overflow();

else

*top_ptr++ = i;

}

int pop(void)

{

if (is_empty())

stack_underflow();

else

return *--top_ptr;

}

*top_ptr-- 이 아닌, *--top_ptr이라고 쓴 것에 유의할 것. pop 함수에서 top_ptr을 먼저 1 감소시키고, 그다음 그것이 가리키는 값을 얻기를 원하기 때문이다.

12.3 Using Array Name as a Pointer

배열의 이름은 배열 첫번째 원소를 가리키는 포인터로 쓰일 수 있다.

int a[10];

*a = 7;    /* stores 7 in a[0]    */

*(a+1) = 12;    /* stores 12 in a[1]    */

일반적으로 a + i는 &a[i] (a의 i번째 원소를 가리키는 포인터)와 같고, *(a + i) 는 a[i] (원소 i)와 같다.

배열의 이름을 포인터로 쓸 수 있기 때문에 배열 안을 도는 루프문을 더 간단하게 표현할 수 있다.

for (p = &a[0]; p < &a[N]; p++)

sum += *p;

대신

for (p = a; p < a + N; p++)

sum += *p;

배열의 이름이 포인터로 쓰이기는 하지만, 새로운 값을 assign할 수는 없다. 배열의 이름을 포인터 변수에 복사해서 그 포인터 변수에 값을 assign할 수는 있다.

/* Reverses a series of numbers (pointer version) */

#include <stdio.h>

#define N 10

int main(void)

{

int a[N], *p;

printf("Enter %d numbers: ", N);

for (p = a; p < a + N; p++) 

scanf("%d", p);

printf("In reverse order:");

for (p = a + N - 1; p >= a; p--)

printf(" %d", *p);

printf("\n");

return 0;

}

Array Arguments (Revisited)

함수로 전달되었을 때, 배열의 이름은 항상 포인터로 간주된다.

일반적인 변수가 함수로 전달될 때, 그 값은 복사되어 전달된다. 파라미터에 대한 어떤 변동도 원래 변수에는 영향을 끼치지 않는다. 반면, 배열이 argument로 사용되었을 때는 배열이 복사되지 않고, 함수 내에서의 값의 변동에 보호되지 않는다. 만약 배열 파라미터가 바뀌지 않고 그대로 남아있기를 원한다면, 함수 선언부에 const를 넣어 준다.

int find_largest(const int a[], int n)

만약 const가 있다면, 컴파일러는 함수의 body에 배열의 원소에 assignment가 있는지를 체크한다.

배열의 크기는 배열을 함수로 pass 하는 시간에 영향을 끼치지 않는다. 왜냐하면 배열의 복사본이 만들어지지 않기 때문이다.

배열 파라미터는 원한다면 포인터로 선언되어도 된다.

int find_largest(int *a, int n)

a를 포인터로 선언하는 것은 배열로 선언하는 것과 동일하다. 컴파일러는 그 둘을 동일하게 취급한다.

배열을 파라미터로 갖는 함수에는 배열의 "slice" - a sequence of conseucutive elements 가 전달될 수 있다. 예를 들어 b라는 배열의 b[5], ..., b[14] 중 가장 큰 원소를 찾고 싶다면, 

largest = find_largest(&b[5], 10);

Using a Pointer as an Array Name

배열의 이름을 포인터로 사용할 수 있다면, 포인터를 마치 배열인 것처럼 subscript해서 사용할 수 있는가? 답은 Yes이다.

#define N 10

...

int a[N], i, sum=0, *p = a;

...

for (i = 0; i < N; i++)

sum += p[i];

컴파일러는 p[i]를 *(p+i)와 같게 취급한다(perfectly legal use of pointer arithmetic).

12.4 Pointers and Multidimensional Arrays

포인터는 일차원 배열의 원소를 가리킬 수 있을 뿐 아니라, 다차원 배열의 원소도 가리킬 수 있다. 이 섹션에서는 이차원 배열을 다루지만, 더 높은 차원의 배열에도 적용할 수 있다.

Processing the Elements of a Multidimensional Array

8.2에서 살펴보았듯이 2차원 배열은 row-major order로 저장된다.

이 점을 포인터와 연관지어 이용해 볼 수 있다. 포인터 p를 반복적으로 증가하면서, 2차원 배열의 모든 원소에 접근할 수 있다.

int a[NUM_ROWS][NUM_COLS];

int row, col;

...

for (row = 0; row< NUM_ROWS; row++)

for (col = 0; col < NUM_COLS; col++)

a[row][col] = 0;

이것이 지금까지 배운 nested for loops로 이차원 배열의 모든 원소에 접근하는 방법이다. 그러나 배열 a를 일차원 배열로 바라보면(실제로 그렇게 저장됨), 이중 for 문을 하나의 for 문으로 표현할 수 있다.

int *p;

...

for (p = &a[0][0]; p <= &a[NUM_ROWS-1][NUM_COLS-1]; p++)

*p = 0;

이러한 방법은 대부분의 C 컴파일러에서 제대로 작동한다. 가독성을 다소 떨어트리기는 하지만, 오래된 컴파일러에서는 이러한 방식이 효율성 측면에서 더 우월하다. 그러나 최근의 많은 컴파일러에서는 속도의 차이가 거의 없거나 아예 없는 경우가 많다.

Processing the Rows of a Multidimensional Array

배열 i행의 첫번째 원소에 접근하는 포인터는,

p = &a[i][0]; 또는 p = a[i];

배열의 한 행 전체에 접근하는 코드

int a[NUM_ROWS][NUM_COLS], *p, i;

...

for (p = a[i]; p < a[i] + NUM_COLS; p++)

*p = 0;

Processing the Columns of a Multidimensional Array

배열이 열이 아니라 행으로 저장되기 때문에 열에 접근하는 것은 좀 더 복잡하다.

int a[NUM_ROWS][NUM_COLS], (*p)[NUM_COLS], i;

...

for (p = &a[0]; p < &a[NUM_ROWS]; p++)

(*p)[i] = 0;

(*p) [NUM_COLS] : NUM_COLS만의 길이를 가진 정수 배열의 포인터(괄호 없이 *p[NUM_COLS]라고 하면 포인터로 구성된 배열을 의미한다)

p++ : p가 다음 행을 가리키게 함

(*p) [i]: *p는 a의 한 행을 가리키므로, (*p) [i]는 그 행의 i열을 가리킨다(괄호 없이 *p[i]라고 하면 *(p[i])를 의미한다.

Using the Name of a Multidimensional Array as a Pointer

일차원 배열의 이름이 포인터로 쓰일 수 있는 것과 마찬가지로, 차원에 관계 없이 모든 배열은 그 이름이 포인터로 쓰일 수 있다. 그러나 좀더 조심해서 다뤄야 한다.

int a[NUM_ROWS][NUM_COLS]; 

위와 같은 배열이 있을 때, a는 a[0][0]에 대한 포인터가 아닌 a[0]의 포인터이다.

C의 관점에서는 배열 a를 이차원 배열이 아닌 일차원 배열(원소가 일차원 배열인)로 본다.

a가 포인터로 쓰였을 때, a의 type은 int (*) [NUM_COLS]이다(길이가 NUM_COLS인 배열의 포인터).

a가 a[0]을 가리킨다는 사실을 이용하면 이차원 배열의 원소를 다루는 루프를 간단하게 만들 수 있다.

for (p = &a[0]; p < &a[NUM_ROWS]; p++)

(*p)[i] = 0;

// 대신

for (p = a; p < a + NUM_ROWS; p++)

(*p)[i] = 0;

이것을 다르게 이용하면, 다차원 배열을 일차원 배열인 것처럼 C를 '속이는' 경우에 편리하다.

int a[NUM_ROWS][NUM_COLS];

...

largest = find_largest(a[0], NUM_ROWS * NUM_COLS);

largest = find_largest(a, NUM_ROWS * NUM_COLS);    /*** WRONG ***/

마지막 줄은, 포인터 a의 타입은 int (*)[NUM_COLS]이지만 find_largest가 expect하는 것은 int * 이므로 틀렸다.

Q&A 해석

Q: 포인터가 주소라면, p + j와 같은 표현은 p에 저장된 주소에 j를 더하는 것이 아닌가?

A: 아니다. 포인터연산에 쓰이는 정수는 포인터의 타입에 따라 scaled된다. p의 type이 int *라면, p + j는 일반적으로 p에 4 * j를 더한다. (int 저장에 4바이트가 쓰인다는 전제하에) 만약 p가 double * type이라면, double은 보통 8바이트가 필요하므로 8 * j가 더해진다.

Q: 배열에 loop 문을 사용할 때, array subscripting과 pointer arithmetic 중 어느 쪽이 더 나은가?

A: 어떤 machine을 쓰는지, 어떤 컴파일러를 쓰는지에 따라 다르기 때문에 쉽게 대답할 수 없다. PDP-11에 있던 초창기의 C에서는 포인터 연산이 더 빨랐다. 요즘의 machine과 컴파일러에서는 차이가 없거나 때로는 array subscripting이 더 빠르다. 한줄 요약: 둘 다 배우고, 네가 쓰는 프로그램의 종류에 자연스럽게 들어맞는 방법을 사용하라.

Q: i[a]가 a[i]가 같은가?

A: 그렇다. 컴파일러는 i[a]를 *(i + a)로 다루고, 이는 *(a + i)와 같고, 이는 a[i]와 같다. 그러나 Obfuscated C contest에 나갈게 아니라면 이런 표현을 사용하지 말 것.

Q: 파라미터 선언에서 어째서 *a는 a[]와 같은가?

둘 다 argument로 포인터가 들어올 것을 기대한다. 둘 다 a에 대해 같은 연산(포인터 연산, array subscripting)이 가능하다. 함수 내에서 a에 새로운 값이 assign될 수 있다. (단, 배열 변수의 이름은 constant pointer로만 사용할 수 있고, array parameter의 경우에는 그러한 제약이 없다)

Q: array 파라미터 선언시 *a 와 a[] 중 어떤게 더 나은 스타일인가?

A: *a는 배열을 의미하는지 아니면 single object의 포인터인지 다소 애매모호하다. 그러나 *a를 사용하는 편이 array의 copy가 아닌 포인터가 전달된다는 사실을 더 정확히 표현해 준다고 주장하는 프로그래머들이 많다. 실무에서는 *a가 a[]보다 더 많이 사용되므로, 여기에 익숙해지는 것이 좋다. 

Q: C에서 배열과 포인터가 밀접한 관계를 가진다는 것을 보았는데, 그 둘이 interchangeable이라고 해도 정확한가?

A: 틀렸다. array parameter가 pointer parameter와 interchangeable하다는 것은 맞지만, 배열 변수는 포인터 변수와 완전히 같지는 않다. 배열의 이름이 포인터라고 말할 수는 없다. 단지 컴파일러가 필요할 때 그것을 포인터로 변환하는 것이다. 이를 명확히 알아보기 위해서 a가 배열일 때 sizeof(a)의 값은 array에 들어있는 모든 바이트의 합이다(원소의 개수 곱하기 한 원소를 저장하는데 필요한 바이트). 그러나 p가 포인터 변수일 때 sizeof(p)의 값은 포인터 변수를 저장하는데 필요한 바이트 수이다.

Q: 이차원 배열을 일차원 배열인 것처럼 다루는 것이 "대부분의" 컴파일러에서 가능하다고 했는데, 가능하지 않은 컴파일러도 있는가? 

A: 그렇다. 현대의 컴파일러 중 "bounds-checking" 컴파일러는 포인터의 타입 뿐 아니라, 배열의 길이도 추적한다. 예를 들어, p가 a[0][0]을 가리키는 포인터일 때를 가정해 보자. p는 일차원 배열인 a[0]의 첫번째 원소를 가리킨다. p를 계속 증가시켜서 a[0]의 모든 원소를 지나게 되면, bound를 넘게 되는데 bounds-checking을 수행하는 컴파일러에서는 p가 배열의 끝을 지나면 에러가 발생한다.

Q: a가 이차원 배열일 때,  find_largest에 어째서 a가 아닌 a[0]을 전달하는가? a와 a[0]는 둘 다 배열의 가장 첫 원소를 가리키지 않는가?

A: 두 포인터가 모두 a[0][0]을 가리키는 것은 맞다. 문제가 되는 것은 a가 틀린 type을 갖고 있다는 것이다. argument로 사용되었을 때, a는 배열을 가리키는 포인터지만 find_largest에는 정수형을 가리키는 포인터가 argument로 사용되어야 한다.  a[0]은 int * type이므로 문제가 없는 argument이다. C가 까다롭기 때문에 별의별 이상한 포인터 실수를 방지할 수 있다.

4번 Stack using Pointer

#include <stdbool.h>

#define STACK_SIZE 100

/* external variables */

int contents[STACK_SIZE];

int *top_ptr = &contents[0];

void make_empty(void) {

*top_ptr = 0;

}

bool is_empty(void) {

return top_ptr == &contents[0];

}

bool is_full(void) {

return top_ptr == &contents[STACK_SIZE];

}

void push(int i) {

if (is_full())

stack_overflow();

else

*top_ptr++ = i;

}

int pop(void) {

if (is_empty())

stack_underflow();

else

return *--top_ptr;

}

6번 배열 원소들의 합을 구하는 함수를 포인터 연산으로 작성

int sum_array(const int *a, int n) {

int *p, sum;

sum = 0;

for (p = a; p < a + n; p++)

sum += *p;

return sum;

}

int main(void) {

int a[] = { 1,3,5,7,9 };

printf("%dn", sum_array(a, 5));

}

7번

bool search(const int a[], int n, int key) {

int *p;

for (p = a; p < a + n; p++) 

if (*p == key) return true;

return false;

}

//exer8

void store_zeros(int a[], int n) {

int *p;

for (p = a; p < a + n; p++) {

*p = 0;

}

}

//exer9

double inner_product(const double *a, const double *b, int n) {

double *p = a, *q = b, sum = 0.0;

int i;

for (i = 0; i < n; i++) 

sum += *(p + i)**(q + i);

return sum;

}

//exer 10

int *find_middle(int a[], int n) {

int *p = a;

return p + n / 2;

}

11번 find_largest를 pointer arithmetic으로

int find_largest(int a[], int n) {

int *p, max;

p = a;

max = *p;

for (p = a + 1; p < p + n; p++)

if (*p > max)

max = *p;

return max;

}

12번

//exer12

void find_two_largest(const int *a, int n, int *largest, int *second_largest) {

int *p = a, *temp = a;

if (*p > *(p + 1))

*largest = *p, *second_largest = *(p + 1);

else

*largest = *(p + 1), *second_largest = *p;

for (p = a + 2; p < a + n; p++) {

if (*p > *second_largest) {

if (*p > *largest)

{

*temp = *largest;

*largest = *p;

*second_largest = *temp;

}

else

*second_largest = *p;

}

}

}

13번

int main(void) {

double ident[N][N];

double *p = &ident[0][0];

int i = 0;

while (i <= N * N - 1) {

if (i % (N + 1) == 0)

*(p + i) = 1.0;

else

*(p + i) = 0.0;

i++;

}

}

14번

int main(void) {

int temperatures[7][24];

int i;

for (i = 0; i < 7; i++)

search(temperatures[i], 24, 32);

}

15번

17번

#define LEN 10

int sum_two_dimensional_array(const int a[][LEN], int n) {

int *p, sum = 0;

for (p = &a[0][0]; p <= &a[n - 1][LEN - 1]; p++)

sum += *p;

return sum;

}

18번

// exer 18

int evaluate_position(char board[8][8]) {

char *p;

int value_white = 0;

int value_black = 0;

for (p = &board[0][0]; p <= &board[7][7]; p++) {

switch (*p) {

case 'Q': value_white += 9; break;

case 'R': value_white += 5; break;

case 'B': value_white += 3; break;

case 'N': value_white += 3; break;

case 'P': value_white += 1; break;

case 'q': value_black += 9; break;

case 'r': value_black += 5; break;

case 'b': value_black += 3; break;

case 'n': value_black += 3; break;

case 'p': value_black += 1; break;

}

}

return value_white - value_black;

}

1번(b)

#include <stdio.h>

int main(void) {

char a[100], ch, *p;

printf("Enter a message: ");

p = a;

while ((ch = getchar()) != '\n') {

*p++ = ch;

}

printf("Reversal is: ");

for (p--; p >= a; p--)

printf("%c", *p);

printf("\n");

}

2번

#include <stdio.h>

#include <ctype.h>

#define LEN 100

int main(void) {

char ch, a[LEN], *p = a, *q;

int i = 0;

printf("Enter a message: ");

while((ch=getchar())!='\n') {

if (isalpha(ch))

*p++ = tolower(ch);

else if (ch == '\n')

break;

}

q = a;

for (p--; p >= a; p--) {

if (*q++ != *p) {

printf("Not a palindrome\n");

return 0;

}

}

printf("Palindrome\n");

return 0;

}

5번 퀵소트를 포인터로 표현

#include <stdio.h>

#define N 10

void quicksort(int a[], int *low, int *high);

int *split(int a[], int *low, int *high);

int main(void) {

int a[N], *p;

printf("Enter %d numbers to be sorted: ", N);

for (p = a; p < a + N; p++)

scanf("%d", p);

quicksort(a, a, a + N - 1);

printf("In sorted order: ");

for (p = a; p < a + N; p++)

printf("%d ", *p);

printf("\n");

return 0;

}

void quicksort(int a[], int *low, int *high) {

int *middle;

// low, high is index of elements

if (low >= high) return; // if lowest index >= highest index, end recursion

middle = split(a, low, high); // find middle index

quicksort(a, low, middle - 1); // call itself recursively from low to middle-1

quicksort(a, middle + 1, high); // call itself recursively from middle+1 to high

}

int *split(int a[], int *low, int *high) {

int part_element = *low;

for (;;) {

while (low < high && part_element <= *high) // high is on the right side of array, high-- and check again

high--;

if (low >= high) break;

*low++ = *high; // high is on the wrong side, switch low and high, and low++ and check low is on the right side

while (low < high && *low <= part_element) // low is on the right side of array, low++ and check again

low++;

if (low >= high) break;

*high-- = *low; // low is on the wrong side, switch low and high, and high-- and check high is on the right side

}

*high = part_element; // after switching is all done, return high as new part_element

return high;

}