2. 배열, 구조체, 포인터

본 카테고리에 게시되는 글은 제가 편입을 준비하며 정리한 자료들입니다.

참조한 서적은 다음과 같습니다.

1. C언어로 쉽게 풀어 쓴 자료구조. 천인국·공용해·하상호. 생능출판사

2. 윤성우의 열혈 자료구조. 윤성우. 오렌지미디어

학부 편입 면접을 위해 준비한 자료이기 때문에 지나치게 긴 코드 또는 너무 깊은 내용은 배제했습니다.

---

1. 배열

ㆍ 기본적인 배열에 관한 내용은 C언어 정리 참조. 여기서는 배열의 응용을 다룸.

(1) 배열의 응용 : 다항식(1)

ㆍ n차 방정식인 경우 n+1크기의 배열을 선언하고, 각각의 인덱스를 차수로 삼아 모든 차수에 대한 계수 값을 저장하는 방법.

ex)

 

ㆍ 다항식 구조체 polynomial

#define MAX_DEGREE 101 // 다항식이 가질 수 있는 최대 차수 100 + 1

typedef struct {

int degree; // 배열에 저장된 다항식의 최고 차수 (즉, 몇차식인지에 대한 정보)

float coef[MAX_DEGREE] // 계수가 저장될 배열

}polynominal;

ex) 

polynomial a = {5, {10, 0, 0, 0, 6, 3} };

 

ㆍ장점 : 차수별로 저장되어 있으므로 덧셈, 뺄셈 알고리즘 구현이 간단함.

ㆍ단점 : 대부분의 항이 0인 희소 다항식의 경우 공간 낭비가 심함

ex) 은 101개의 공간중 2개만 사용

(2) 배열의 응용 : 다항식(2)

ㆍ[계수, 차수]필드를 가지는 구조체 배열을 선언해, 0이 아닌 항들만 저장하는 방법.

ㆍ의미있는 항들만 저장하므로, 희소 다항식의 경우 공간을 절약할 수 있다.

    (단, 희소 다항식이 아닌 경우 공간의 낭비가 오히려 심하다. 첫번째 방법은 계수값만 저장하는 방식인데 반해 두 번째 방법은 계수와 차수를 모두     저장하기 때문이다.)

ㆍ전역 변수로 선언한 후, 하나의 배열에 여러 개의 다항식을 저장해 사용할 수 있다.

    (단, 다항식의 시작과 끝을 가리키는 변수를 관리해야 한다.)

ex) 구조체

#define MAX_TERMS 101

struct {

    float coef;

    int expon;

} terms[MAX_TERMS];

ex) 두 개의 다항식 저장

 

(3) 배열의 응용 : 희소 행렬(Sparse matrix)의 효율적인 저장 방법

ㆍ 희소 행렬 : 많은 항들이 0으로 되어 있는 행렬. 메모리 낭비가 심하고, 엄청난 크기의 희소 행렬인 경우 컴파일러에 따라 사용하지 못하는 경우도 있다.

ㆍ 행렬을 압축하여, 0이 아닌 요소만을 (행, 열, 값)으로 표시할 수 있음. 즉, [행, 열, 값]필드를 가진 구조체 배열을 선언해 효율적으로 저장 가능.

ㆍ 희소 행렬 구조체

※ 하나의 요소를 나타내는 elemenet 구조체를 선언한 후 → element 구조체형 배열을 선언한다.

1) 하나의 요소를 나타내는 element 구조체

ㆍ 행/열/값 필드를 가짐

typedef struct {

    int row;

    int col;

    int value;

} element;

 

2) SparseMatrix 구조체

ㆍ element 구조체 배열 필드(데이터 필드)를 가짐

    ex) element data[MAX_TERMS]

ㆍ rows, cols, terms 필드를 가짐(row, col 이랑 헷갈리지 말것!)

⇒ rows : 배열의 행 개수를 나타냄.

⇒ cols : 배열의 열 개수를 나타냄.

⇒ terms : 배열의 데이터 개수를 나타냄.

ㆍ typedef struct SparseMatrix {

element data[MAX_TERMS];

int rows;

int cols;

int terms;

    }SparseMatrix;

※ rows, cols, terms 필드 쓰는 이유 : 우리는 지금 압축된 행렬을 다루고 있다. 행렬은 그냥 더할 수 없다. ‘같은 크기의 행렬끼리만 더할 수 있다.’ 즉, 행렬의 덧셈 이전에 행렬 크기 검사가 우선되어야 한다!! rows, cols는 행렬 크기 비교에 사용된다. 

 

2. 구조체

(1) 구조체

ㆍ데이터 타입이 다른 데이터들의 모임

ㆍ구조체 대입(같은 구조체일 경우) : 구조체A = 구조체B 바로 대입 가능

ㆍ구조체 비교 : 구조체 자체끼리 비교 불가. 구조체 항목끼리 비교해야 함

(2) 자기 참조 구조체

ㆍ구조체 멤버로 자기자신의 구조체를 가리키는 포인터를 가짐

ㆍ연결 리스트, 트리 등을 구성

ㆍ 자기참조 구조체 코드

typedef struct ListNode {

char data[10];

struct ListNode *link;

} ListNode;

 

3. 포인터

ㆍ 다른 변수의 주소를 가지는 변수

ㆍ 포인터 연산자

ㆍ 상세한 내용은 C언어 정리를 참조

&	변수의 주소값을 반환
*	포인터가 가리키는 변수의 내용을 반환