🤖 3. 배열, 구조체, 포인터

배열

배열(array) : 동일한 타입의 데이터를 한 번에 여러 개 만들 때 사용됨
=> random access(direct access) : 순차X
=> 연속적인 메모리 공간 필요 : 인덱스 사용

배열 ADT(추상 자료형) : <인덱스(index), 값(value)>의 쌍으로 이루어진 집합

• create(size) : size개의 요소를 저장할 수 있는 배열 생성
• get(A, i) : 배열 A의 i번째 요소 반환
• set(A, i, v) : 배열 A의 i번째 위치에 값 v 저장
  (c언어에서는 구현할 필요 X)
  
  
  

✅ 1차원 배열

• create 연산 : int list[6];
• set 연산 : list[0] = 100;
• get 연산 : value = list[0];

컴파일러 주소 : base+i*sizeof(int) (시작주소: base, type: int)

✅ 2차원 배열
ex) int list[3][5];

	0열(column)	1열	2열	3열	4열
0행	list[0][0]	list[0][1]	list[0][2]list[0][3]	list[0][4]	list[0][5]
1행	list[1][0]	list[1][1]	list[1][2]	list[1][3]	list[1][4]
2행	list[2][0]	list[2][1]	list[2][2]	list[2][3]	list[2][4]

계산 1) int test[3][5]로 선언된 배열에서 test[2][3]의 원소의 주소값은?
2*5 + 3 = 13

계산 2) int test[3][4][5]로 선언된 배열에서 test[2][3][3]의 원소의 주소값은?
2*4*5 + 3*5 + 3 = 58

구조체

구조체(structure) : 타입이 다른 데이터를 묶는 방법

📌 'struct' 키워드 사용

구조체 형식	구조체 변수
struct 구조체이름 { 항목1; 항목2; ... };	struct 구조체이름 구조체변수;
struct studentTag { char name[10]; int age; double gpa; };	struct studentTag s;

📌 구조체 안의 멤버 사용 : 변수 뒤에 멤버연산자 '.' 사용

strcpy(s.name, "kim");
s.age = 20;
s.gpa = 4.3;

📌 c언어에서는 typedef을 사용해 구조체를 새로운 타입으로 선언 가능

struct studentTag {
    char name[10];
    int age;
    double gpa;
} student;

📌 변수 선언 및 초기화 가능

student s = { "kim", 20, 4.3 };

배열의 응용: 다항식

p(x) = aₙxⁿ + aₙ₋₁xⁿ⁻¹ + ... + a₁x + a₀
=> a: 계수, x: 변수, n: 차수 (가장 큰 차수=다항식의 차수)

① 모든 차수의 계수값을 배열에 저장 : dense(분포도 좁은 형태)에서 유리
=>간단하고 쉽게 이해 가능
=> 대부분의 항의 계수가 0인 희소 다항식에선 공간의 낭비가 심함

ex) 10x⁵+6x+3 = 10∙x⁵+0∙x⁴+0∙x³+0∙x²+6∙x+3

#include <stdio.h>
#define MAX(a,b) (((a)>(b))?(a):(b))    // a>b->a, a<=b->b
#define MAX_DEGREE 101    // 다항식 최대 차수:100 + 상수:1

typedef struct {
	int degree;    // 다항식의 차수를 degree에 저장
    float coef[MAX_DEGREE];    // 계수를 coef에 저장
} polynomial;

polynomial poly_add(polynomial A, polynomial B) {
	polynomial C;
    int Apos = 0; Bpos = 0; Cpos = 0;
    int degree_a = A.degree;
    int degree_b = B.degree;
    C.degree = MAX(A.degree, B.degree);
    
    while (Apos <= A.degree && Bpos <= B.degree) {
    	if (degree_a > degree_b) {
        	C.coef[Cpos++] = A.coef[Apos++];
            degree_a--;
        }
        else if (degree_a == degree_b) {
        	C.coef[Cpos++] = A.coef[Apos++] + B.coef[Bpos++];
            degree_a--; degree_b--;
        }
        else {
        	C.coef[Cpos++] = B.coef[Bpos]++;
            degree_b--;
        }
    }
    return C;
}

void print_poly(polynomial p) {
	for (int i=p.degree; i>0; i--) {
        print("3.1fx^%d + ", p.coef[p.degree - i], i);
    printf("%3.1f \n", p.coef[p.degree]);
}

int main(void) {
    polynomial a = {5, {3, 6, 0, 0, 0, 10}};    // degreen, coef
    polynomial b = {4, {7, 0, 5, 0, 1}};
    polynomial c;
    
    print_poly(a);
    print_poly(b);
    c = poly_add(a, b);
    print_poly(c);
    return 0;
}

Q. C.coef[Cpos++] = A.coef[Apos++]와 C.coef[++Cpos] = A.coef[++Apos]의 차이점?

A. for문에서는 차이 없음. 전자는 계산 후 포지션 값 증가, 후자는 포지션 값 증가 후 계산

② 다항식에서 0이 아닌 항만을 하나의 전역 배열에 저장하는 방법 : sparse(분포도 넓은 형태)에 유리
=> 공간 낭비 적음
=> 인덱스 변수를 관리해야함, 다항식에 따라 공간을 더 차지할 수 있음, 방법이 좀 더 어려움

ex) A = 8x³+7x+1 = ( (8,3), (7,1), (1,0) ) , B = 10x⁵+6x+3 = ( (10,5), (6,1), (3,0) )

coef: 계수, expon: 차수, avail: 현재 비어있는 요소의 인덱스

#include <stdio.h>
#include <stdlib.h>
#define MAX_TERMS 101

typedef struct {
	float coef;
    int expon;
} polynomial;

polynomial terms[MAX_TERMS] = { {8,3}, {7,1}, {1,0}, {10,3}, {3,2}, {1,0} };
int avail = 6;    // c의 시작 인덱스

char compare(int a, int b) {
	if (a>b) return '>';
    else if (a == b) return '=';
    else return '<';
}

void attach(float coef, int expon) {
	if (avail > MAX_TERMS) {
    	fprintf(stderr, "항의 개수가 너무 많음\n");
        exit(1);
    }
    terms[avail].coef = coef;
    terms[avail].expon = expon;
    avail++;
}

void poly_add(int As, int Ae, int Bs, int Be, int *Cs, int *Ce) {
	float tempcoef;
    *Cs = avail;
    
    while (As <= Ae && Bs <= Be) {
    	switch (compare(terms[As].expon, terms[Bs].expon)) {
        	case '>':
            	attach(terms[As].coef, terms[As].expon);
                As++; break;
            case '=':
            	tempcoef = terms[As].coef + terms[Bs].coef;
                if (tempcoef)    // 0 일 때 아무것도X, 0 아닐 때 attach
                	attach(tempcoef, terms[As].expon);
                As++; Bs++; break;
            case '&lt;':
            	attach(terms[Bs].coef, terms[Bs].expon);
                Bs++; break;
            }
            
        for (; As<=Ae; As++)    // A의 나머지 항들 이동
        	attach(terms[As].coef, terms[As].expon);
        for (; Bs<=Be; Bs++)    // B의 나머지 항들 이동
        	attach(terms[Bs].coef, terms[Bs].expon);
        *Cs = avail - 1;
    }
    
    void print_poly(int s, int e) {
    	for (int i=s; i&lt;e; i++)
        	printf("%3.1fx^&d + ", terms[i].coef, terms[i].expon);
        printf("%3.1fx^&d\n", terms[e].coef, terms[e].expon);
    }
    
    int main(void) {
    	int As=0, Ae=2, Bs=3, Be=5, Cs, Ce;
        poly_add(As, Ae, Bs, Be, &Cs, &Ce);
        print_poly(As, Ae);
        print_poly(Bs, Be);
        print_poly(Cs, Ce);
        return 0;
    }

배열의 응용: 희소행렬

희소행렬 표현방법

① 행렬을 2차원 배열로 표현 : dense
=> 많은 항이 0으로 되어있는 경우(희소행렬) -> 메모리 낭비 심함

a[i][j] => a[j][i]

#include <stdio.h>
#define ROWS 3
#define COLS 3

void matrix_transpose(int A[ROWS][COLS], int B[ROWS][COLS]) {
	for (int r=0; r<ROWS; r++)
    	for (int c=0; c<COLS; c++)
        	B[c][r] = A[r][c];
}

void matrix_print(int A[ROWS][COLS]) {
	for (int r=0; r<ROWS; r++) {
    	for (int c=0; c<COLS; c++)
        	printf("%d ", A[r][c]);
        printf("\n");
    }
}

int main(void) {
	int array1[ROWS][COLS] = { {2,3,0}, {8,9,1}, {7,0,5} };
    int array2[ROWS][COLS];
    
    matrix_transpose(array1, array2);
    matrix_print(array1);
    matric_print(array2);
    return 0;
}

② 0이 아닌 항만 표현 : sparse
=> 희소행렬 : 배열 사용하되 0이 아닌 요소들만 나타냄 -> 메모리 낭비 적음
=> 전치연산 : 상당한 프로그래밍 필요

(row, col, value) => (col, row, value)

#include <stdio.h>
#include <stdlib.h>
#define MAX_TERMS 100

typedef struct {
	int row;
    int col;
    int value;
} element;

typedef struct SparseMatrix {
	element data[MAX_TERMS];
    int rows;
    int cols;
    int terms;
} SparseMatrix;

SparseMaxtrix matrix_transpose(SparseMatrix a) {
	SparseMatrix b;
    
    int bindex;
    b.rows = a.rows;
    b.cols = a.cols;
    b.terms = a.terms;
    
    if (a.terms > 0) {
    	bindex = 0;
        for (int c=0; c<a.cols; c++) {
        	for (int i=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++;
                }
            }
        }
    }
    return b;
}

void matrix_print(SparseMatrix a) {
	for (int i=0; i&lt;a.terms, i++) {
    	printf("(%d, %d, %d) \n", a.data[i].row, a.data[i].col, a.data[i].value);
    }
}

int main(void) {
	SparseMatrix m = {
    	{ {0,3,7}, {1,0,9}, {1,5,8}, {3,0,6}, {3,1,5}, {4,5,1}, {5,2,2} },
        6,
        6,
        7
    };
    SparseMatrix result;
    
    result = matrix_transpose(m);
    matrix_print(result);
    return 0;
}

포인터

• 포인터(pointer) : 다른 변수의 주소를 가지고 있는 변수
  => 실질적인 메모리(하드웨어) 접근

int a = 100;
int *p;
p = &a;
// *p == a

• 연산자
  ① & 연산자 : 변수의 주소를 추출하는 연산자
  ② * 연산자 : 포인터가 가리키는 장소에 값을 저장하는 연산자

• 자료형에 따른 포인터

int *p;  // int형 변수
float *pf;  // double형 변수
char *pc;    // char형 변수

• 널 포인터 : 어떤 객체도 가리키지 않는 포인터 (포인터를 사용하기 전에 반드시 널 포인터인지 검사해야함)

if (p == NULL) {
	fprintf(stderr, "오류: 포인터가 아무 것도 가리키지 않습니다.");
    return;
}

• 이중포인터

int **a;
a = 200;
*a = 100;
**a = 10;

• 포인터를 함수 매개변수로 사용

#include <stdio.h>

void swap(int *px, int *py) {
	int tmp;
    tmp = *px;
    *px = *py;
    *py = tmp;
}

int main(void) {
	int a=1, b=2;
    print("swap을 호출하기 전: a=%d, b=%d\n", a, b);
    swap(&a, &b);
    print("swap을 호출한 다음: a=%d, b=%d\n", a, b);
    return 0;
}

Q. swap(&a, &b)로 call하고 (*px, *py)로 받는 이유?

A. swap에서 a, b가 바뀌어도 main으로 넘어가지 않음 (px, py는 주소를 갖고 있으니 괜찮음)

동적 메모리 할당

- 동적 메모리 할당(dynamic memory allocation) : 필요한 만큼의 메모리를 운영체제로부터 할당 받아서 사용하고, 끝나면 시스템에 메모리를 반납하는 기능 => 효율적

- 히프(heap) : 동적 메모리가 할당되는 공간, 운영체제가 사용되지 않는 메모리 공간을 모아 놓은 곳

int *p;
p = (int *)malloc(sizeof(int));  // ① 동적 메모리 할당
*p = 1000;  // ② 동적 메모리 사용
free(p);  // ③ 동적 메모리 반납

① malloc( ) : 동적 메모리 블럭의 시작 주소를 반환
    void * : 반환되는 주소의 타입
    메모리 확보가 불가능하면 NULL을 함수의 반환값으로 반환
② 동적 메모리는 포인터로만 사용 가능
③ free( ) : 할당된 메모리 블록을 운영체제에게 반환
    주의! malloc( ) 함수가 반환했던 포인터 값을 잊어버리면 안됨 => 잊어버리면 동적 메모리 반환 불가능
    malloc( )은 메모리가 부족하면 NULL을 반환 (반드시 NULL인지 검사)

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define SIZE 10

int main(void) {
	int *p;
    
    p = (int *)malloc(SIZE * sizeof(int));
    if (p == NULL) {
    	fprint(stderr, "메모리가 부족해서 할당할 수 없습니다. \n");
        exit(1);
    }
    
    for (int i=0; i<SIZE; i++) 
    	p[i] = i;
        printf("%d ", p[i]);
        
    free(p);
    return 0;
}

(*ps).i == ps->i : 포인터를 통해 구조체 멤버에 접근

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct studentTag {
	char name[10];
    int age;
    double gpa;
} student;

int main(void) {
	student *s;
    
    s = (student *)malloc(sizeof(student));
    if (s == NULL) {
    	fprintf(stderr, "메모리가 부족해서 할당할 수 없습니다.\n");
        exit(1);
    }
    
    strcpy(s->name, "Park");
    s->age = 20;
    
    free(s);
    return 0;
}