C언어로 쉽게 풀어쓴 자료구조 3장- 배열, 구조체, 포인터

ch3 : 배열, 구조체, 포인터

3.1배열

배열 = 동일한 타입의 데이터를 한 번에 여러 개 만들 때 사용

배열을 사용할 경우 “연속적인 메모리 공간”이 할당 되고 인덱스(index) 번호를 사용하여 쉽게 접근이 가능하기 때문에 반복 루프를 이용하여 여러 가지 작업들을 손쉽게 할 수 있다.

2차원 배열은 요소들이 2차원 형태로 나열된 배열이다. 2차원 배열에서 가로줄을 행(row), 세로줄을 열(column)이라고 한다. C언어에서 2차원 배열은 다음과 같이 선언한다.

int list[3][5];

위의 선언에서는 3개의 행과 5개의 열을 가지는 2차원 배열이 생성된다. C언어에서는 배열의 배열을 만들어서 2차원 배열을 구현한다. 즉 크기가 3인 1차원 배열을 만들고 이 배열의 요소에 크기가 5인 배열을 생성하여 추가한다.

list[0][0] list[0][1] list[0][2] list[0][3] list[0][4]

list[1][0] list[1][1] list[1][2] list[1][3] list[1][4]

list[2][0] list[2][1] list[2][2] list[2][3] list[2][4]

3.2구조체

구조체의 개념

배열이 타입이 같은 데이터의 모임이라면 구조체(structure) = 타입이 다른 데이터를 묶는 방법이다. C언어에서는 struct 키워드를 이용하여 표기한다.

[그림 3–3] 배열과 구조체의 비교

구조체의 형식은 다음과 같이 정의한다.

구조체의 형식이 위와 같이 정의되었다면 구조체 변수는 다음과 같이 생성한다.

• 문자 배열로 된 이름
• 나이를 나타내는 정수 값
• 평균평점을 나타내는 실수 값

struct 구조체이름 구조체 변수;

struct 키워드 다음에 오는 studentTag 는 구조체와 구조체를 구별할 수 있게 해주는 식별자

structstudentTag{

charname[10];//문자배열로된이름

intage;//나이를나타내는정수값

doublegpa;//평균평점을나타내는실수값

};

로서 보통 구조체 태그(tag)라고 한다. 위의 문장은 구조체 형식만을 정의한 것이고 실제로 구조체가 만들어진 것은 아니다. 구조체를 만들려면 다음과 같이 하여야 한다.

struct studentTag s;

구조체 안에 들어 있는 멤버를 사용하려면 어떻게 할까? 구조체 변수 뒤에 ‘.’을 첨가한 후 항목 이름을 적으면 된다. ‘.’을 멤버연산자(membership operator)라고 한다.(s.

strcpy(s.name,”kim”);

s.age=20;

s.gpa=4.3;

C언어에서는 typedef을 사용하여 구조체를 새로운 타입으로 선언하는 것이 가능하다. 아래의 예에서 student은 새로운 데이터 타입의 이름이 된다.

이 경우에는 새로운 타입인 student만을 사용하여서 변수를 선언하는 것이 가능해진다. student는 C에서의 기본 데이터 타입인 int나 float와 마찬가지로 새로운 데이터 타입의 이름이 된다.

typedefstudentTag{

charname[10];//문자배열로된이름

intage;//나이를나타내는정수값

doublegpa;//평균평점을나타내는실수값

} student;

구조체는 중괄호를 사용하여 선언 시에 초기화하는 것이 가능하다. 다음 문장을 참조하라.

student s = { “kim”, 20, 4.3 };

3.3 배열의 응용: 다항식

수학에서 나오는 다항식을 배열을 이용하여 표현해보자. 다항식의 일반적인 형태는 다음과 같다.

위의 다항식에서 a: 계수 x:변수, n: 차수라 부른다. 가장 큰 차수를 다항식의 차수라고 부른다. 다항식을 나타내는 두 가지의 자료 구조를 생각할 수 있다.

첫 번째 방법

첫 번째 방법은 모든 차수의 계수값을 배열에 저장하는 것이다. 예를 들어 다항식

은 다음과 같이 다시 쓸 수도 있다.

모든 차수에 대한 계수값들의 리스트인 (10, 0, 0, 0, 6, 3)을 배열 coef에 저장하는 것이다. 여기서 다항식의 차수는 변수 degree에 저장 된다.

하나의 다항식이 하나의 degree 변수와 하나의 coef 배열을 필요로 하므로 이를 묶어서 구조체를 만들고 이 구조체를 사용하여 하나의 다항식을 표현할 수 있다. 일반적으로 계수는 실수일 수 있으므로 coef 배열은 실수 배열로 선언 되었다. 아래 코드에서 구조체 변수

를 표현하고 있다.

[그림3–4] 하나의 배열로 하나의 다항식을 표현

두 번째 방법

공간을 절약하기 위하여 다항시게서 0이 아닌 항만을 하나의 전역 배열에 저장하는 방법도 생각할 수 있다. 다항식의 0이 아닌 항들은 (계수, 차수)의 형식으로 구조체 배열에 저장된다.

#defineMAX_DEGREE101//다항식의최대차수+1

typedefstruct{

intdegree;

floatcoef[MAX_DEGREE];

}polynomial;

polynomiala={5,{10,0,0,0,6,3}}; 즉

의 경우, ( (10, 5), (6, 1), (3, 0) )로 표시하는 것이다. 이 방식에서는 하나의 배열에 하나이상의 다항식을 저장할 수 있다. 먼저 (계수, 차수)쌍을 구조체로 선언하고 이 구조체의 배열을 생성한다. 이 배열을 사용하여 다항식을 표현한다.

이 방법을 이용하여 다음 2개의 다항식을 표현해보자.

,

terms 배열의 내용을 나타내면 다음과 같이 될 것이다. avail 변수는 현재 비어있는 요소의 인덱스를 가르친다. 위의 예제에서는 avail 변수가 6이 된다.

#defineMAX_TERMS101

struct{

float coef;

int expon;

}terms[MAX_TERMS];

int avail;

[그림 3–5] 하나의 배열로 여러 개의 다항식을 표현

이러한 표현 방법은 terms안에 항의 총 개수가 MAX_TERMS을 넘지만 않으면 많은 다항식을 저장할 수 있다. 그러나 이 방식도 단점이 존재한다. 우선 하나의 다항식이 시작되고 끝나는 위치를 가리키는 인덱스 변수들을 관리하여야 한다. 또한 차수도 저장해야 하기 때문에, 다항식에 따라서는 덧셈을 비롯한 연산들의 구현이 첫 번째 방법보다 좀 더 어려워진다.

두 개의 다항식을 더하는 알고리즘을 생각해보자. 두 개의 다항식 A, B를 더하여 다항식 C를 구하려고 하면, 순서대로 A와 B의 각 항의 차수를 비교하여, 차수가 같으면 A와 B의 각 항의 계수를 더하여 C로 옮기고, 차수가 다르면 A와 B중에서 차수가 큰 항을 C로 옮기면 된다. 이와 같은 과정을 어느 한쪽의 다항식이 끝날 때까지 계속한다.

3.4 배열의 응용: 희소행렬

행렬(matrix)은 자연과학에서 많은 문제를 해결하는데 사용된다. 따라서 행렬을 프로그램에서 표현하는 것은 중요한 문제이다.

[그림 3–7] 행렬의 예

행렬을 어떻게 표현할 것인지를 생각해보자. 일반적으로 행렬을 표현하는 자연스러운 방법은 다음과 같은 2차원 배열을 사용하는 것이다.

이 방법을 1이라고 하자. 이 방법으로 다음과 같은 행렬을 표현해보면 [그림 3–8]과 같다.

[그림 3–8] 희소행렬 표현방법 #1: 행렬을 2차원 배열로 표현

#define MAX_ROWS

#define MAX_COLS 100

int matrix[MAX_ROWS][MAX_ROW];

그러나 [그림3–8] (b)처럼 많은 항들이 0으로 되어 있는 희소행렬인 경우에는 메모리의 낭비가 심하게 된다. 더구나 엄청난 크기의 희소행렬인 경우에는 컴파일러에 따라 사용하지 못하는 경우도 있다. 따라서 희소 행렬을 표현하는 다른 방법을 생각해보자. 한가지의 방법은 배열을 이용하되, 0이 아닌 요소들만을 나타내는 방법이다. 이 방법을 방법 2이라고 하자. 즉 0이 아닌 노드만을 (행, 열, 값)으로 표시하는 것이다. [그림 3–9]는 똑같은 행렬을 두 번째 방법으로 나타내는 것이다.

[그림 3–9] 희소행렬 표현방법#2: 0이 아닌 항만 표현

방법 1은 행렬을 전통적인 2차원 배열로 나타낸 것이고 방법 2는 새로운 방식으로 표현한 것이다. 각 방법은 각자 장단점을 가지고 있다. 방법 1은 2차원 배열 요소(i, j)를 (j, i)와 교환하면 된다.

전치 행렬 계산하기 #1

#include<stdio.h>

#defineROWS3

#defineCOLS3

//행렬전치함수

voidmatrix_transpose(intA[ROWS][COLS],intB[ROWS][COLS])

{

for(intr=0;r<ROWS;r++)

for(intc=0;c<COLS;c++)

B[c][r]=A[r][c];

}

voidmatrix_print(intA[ROWS][COLS])

{

printf(“====================\n”);

for(intr=0;r<ROWS;r++){

for(intc=0;c<COLS;c++)

printf(“%d”,A[r][c]);

printf(“\n”);

}

printf(“====================\n”);

}

intmain(void)

{

intarray1[ROWS][COLS]={{2,3,0},

{8,9,1},

{7,0,5}};

intarray2[ROWS][COLS];

matrix_transpose(array1,array2);

matrix_print(array1);

matrix_print(array2);

return0;

}

계산 결과

전치 행렬 계산하기 #2

#include <stdio.h>

#include <stdlib.h>

typedefstruct{

introw;

intcol;

intvalue;

}element;

typedefstructSparseMatrix{

elementdata[MAX_TERMS];

introws;//행의개수

intcols;//열의개수

intterms;//항의개수

}SparseMatrix;

SparseMatrixmatrix_transpose2(SparseMatrixa)

{

SparseMatrixb;

intbindex;//행렬b에서현재저장위치

b.rows=a.rows;

b.cols=a.cols;

b.terms=a.terms;

if(a.terms>0){

bindex=0;

for(intc=0;c<a.cols;c++){

for(inti=0;i<a.terms;i++){

if(a.data[i].col==c){

b.data[bindex].row=a.data[i].col;

b.data[bindex].col=a.data[i].row;

b.data[bindex].value=a.data[i].value;

bindex++;

}

}

}

}

returnb;

}voidmatrix_print(SparseMatrixa)

{

printf(“====================\n”);

for(inti=0;i<a.terms;i++){

printf(“(%d,%d,%d)\n”,a.data[i].row,a.data[i].col,a.data[i].value);

}

printf(“====================\n”);

}

intmain(void)

{

SparseMatrixm={

{{0,3,7},{1,0,9},{1,5,8},{3,0,6},{3,1,5},{4,5,1},{5,2,2}},

6,

6,

7

};

SparseMatrixresult;

result=matrix_transpose2(m);

matrix_print(result);

return0;

}

계산결과

3.5 포인터

포인터의 개념

포인터 = 다른 변수의 주소를 가지고 있는 변수

int a = 100;

int *p;

p = &a;

[그림 3–10] 포인터는 변수를 가리킨다.

포인터와 관련된 연산자

포인터와 관련된 2가지의 중요한 연산이 있다.

& 연산자 — 주소 연산자

* 연산자 — 간접참조 연산자(역참조 연산자라고도 한다)

int a;

int* p;

p = &a;

*p = 200;

[그림3–11] 포인터를 통한 변수 값의 변경

널 포인터

널 포인터 = 어떤 객체도 가리키지 않는 포인터 일반적으로 C 언어에서 널 포인터는 NULL이라는 매크로로 표시한다.

배열과 포인터

함수로 배열이 전달되면 함수 안에서 배열의 내용을 변경할 수 있다. 그 이유는 [그림 3–12]와 같이 배열의 이름이 배열의 시작위치를 가리키는 포인터이기 때문이다.

[그림 3–12] 배열과 포인터의 관계: 배열의 이름은 배열의 시작부분을 가리키는 포인터이다.

3.6 동적 메모리 할당

일반적으로 배열은 크기가 고정되어 있다 하지만 동적 메모리 할당을 이용하면 필요한 만큼은 메모리를 운영체제로부터 할당받아서 사용하고, 사용이 끝나면 시스템에 메모리를 반납할 수 있다. 그리고 동적 메모리가 할당되는 공간을 히프(heap)라고 한다.

구조체와 포인터

포인터를 선언하고 포인터를 통하여 구조체 멤버에 접근할 수 있는데 그 표기법은 “->”이다. 예를 들면 ps가 구조체를 가리키는 포인터이면 (*ps).i보다 ps->i라고 쓰는 것이 더 편리하다.