03.구조체

ADT(Abstract Data Type)이 무엇인지에 대해서 이해해보자.
-> 내가 이해한 ADT는 말그대로 어떤 자료형을 추상적으로 구성해 놓은것이다.
연산이나 자료형에 대한 구현은 이루어지지 않고, 그 연산의 이름 파라미터 반환값등 필수적인 정보만을 제공함으로써
프로그램의 전체적인 핵심주제에 집중할 수 있게 하는 것이다.

구조체의 개념
배열은 하나의 데이터타입만 저장할 수 있다. 하지만 우리는 여러가지의 데이터 타입을 묶어 관리하고 싶은 경우이다. 예를 들어서 학생의 성적을 관리하기 위해 A의 이름, A의 과목성적, A의 과목등수 등등,, 을 여러개 만들어서 일일히 데이터 타입을 정의 하지말고 '성적'이라는 하나의 자료형안에서 저 모든 것을 관리하고자 하는 것이다.

#include <stdio.h>
typedef struct Student{
    char name[10];
    int age;
    int score;
}student;
void main(void){
    student A = {"이성준",24,100}; //student형 변수 초기화
    printf("%s의 성적은 %d입니다.",A.name,A.score);
}

• 유의해야할 것은 구조체는 자료형일 뿐이다. 따라서 자료형으로써 변수 앞에 쓰여서 사용되어야 한다.
• 구조체는 struct 키워드로 만든다.
• 구조체는 typedef struct 구조체이름{관리하고싶은 변수} 구조체별명; 으로 type을 define하여서 별명으로써 사용한다.
  만약 typedef를 사용하지 않는다면 일일히 struct 구조체이름 변수이름으로 변수를 선언해야한다.
• 구조체의 member에 접근하기 위에서는 참조를 위한 .을 사용해서 접근하면 된다.

예제> 우리는 두 다항식을 더하는 연산을 생각해볼 것이다.
구조체안에 있는 배열을 사용해서 다항식의 모든 차수를 생각할 것이다. 구조체에 있는 degree는 다항식의 차수이다.
Ex> $5X^5+X^3+X^2$를 생각해 볼 수 있다. 이때 degree는 5차이고 우리는 이때 coef라는 배열을 만들어서
5,0,1,1,0,0을 저장할 것이다.
아래 코드를 읽어보길 바란다.

#include <stdio.h>
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MAX_DEGREE 101

typedef struct { 			
	int degree;			
	float coef[MAX_DEGREE];	
} polynomial;

polynomial poly_add1(polynomial A, polynomial B)
{
	polynomial C; //결과변수
	int Apos = 0, Bpos = 0, Cpos = 0; //Marker의 역할
	int degree_a = A.degree; //A의 차수
	int degree_b = B.degree; //B의 차수
	C.degree = MAX(A.degree, B.degree); //C의 차수는 더하는 것이기 때문에 더 큰 차수를 갖음


	while (Apos <= A.degree && Bpos <= B.degree) { 
        /* 
        A의 최대차수가 B의 최대차수보다 클때는 if문이 실행 되고
        반대는 else문이 실행되다가, 차수가 같아지는 시점부터는 둘의 항을 더한다.
        */
		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--)
		printf("%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 } }; //5차함수이고 각 항의 계수도 표현
	polynomial b = { 4,{ 7, 0, 5, 0, 1 } }; //4차함수이고 각 항의 계수도 표현
	polynomial c; // 결과를 나타내기 위한 변수

	print_poly(a);
	print_poly(b);
	c = poly_add1(a, b);
	printf("-----------------------------------------------------------------------------\n");
	print_poly(c);
	return 0;
}

구조체는 위에서 데이터타입이라고 했다. 그러면 구조체를 배열로 만들수도 있는데, 이를 구조체 배열이라고 한다. 구조체 배열을 사용해서 두다항식을 더하는 프로그램을 작성해보겠다

#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 } };
//구조체 배열을 사용한 경우 
//8x^3 + 7x + 1 , 10x^3 + 3x^2 + 1
//두개의 다항식의 덧셈을 진행할 것이다.

int avail = 6; //사용가능한 배열의 공간 Index

// 두식의 차수를 비교1
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++;
}

// C = A + B
void poly_add2(int As, int Ae, int Bs, int Be, int *Cs,
	int *Ce)
{
	float tempcoef;
	*Cs = avail;
	while (As <= Ae && Bs <= Be) 
	//각각의 메모리에서 A방정식의 시작(As)와 끝(Ae)
	//B방정식의 시작(Bs)와 끝(Be)가 존재한다
	//Cs와 Ce는 합연산으로 나오는 방정식 C의 시작점과 끝점
	//이전의 polynomial합은 일정차수 이하로 내려오면 동시에 끝났었는데
	//여기서는 start가 end보다 작은 동안만 while문을 돌린다
	//그렇다면 X^5이라는 A방정식과 X^3+2x라는 B방정식의 경우에는 어떻게 되는 것인가?
	//-> 이는 아래의 for문에서 처리를 해준다

		switch (compare(terms[As].expon, terms[Bs].expon)) {
		case '>': 	// A의 차수 > B의 차수이면 A의 항이 곧 C의 항
			attach(terms[As].coef, terms[As].expon);
			As++;			break;
	
		case '=': 	// A의 차수 == B의 차수이면 차수에 해당하는 계수를 합쳐서 넣어줌
			tempcoef = terms[As].coef + terms[Bs].coef;
			if (tempcoef)
				attach(tempcoef, terms[As].expon);
			As++; Bs++;		break;
		case '<': 	// A의 차수 < B의 차수이면 B의 항이 곧 C의 항
			attach(terms[Bs].coef, terms[Bs].expon);
			Bs++;			break;
		}
	// A의 나머지 항들을 이동함
	for (; As <= Ae; As++)
		attach(terms[As].coef, terms[As].expon);
	// B의 나머지 항들을 이동함
	for (; Bs <= Be; Bs++)
		attach(terms[Bs].coef, terms[Bs].expon);
	*Ce = avail - 1; 
	//attach함수를 거치면서 avail이 계속 커지고 
	//마지막으로 커졌을때 Ce는 이상한값(heap영역이니깐 maybe 00)을 가리킬 것이다.
	//이를 하나 빼줌으로써 정상화 시킨다.
}
void print_poly(int s, int e)
{
	for (int i = s; i < 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_add2(As, Ae, Bs, Be, &Cs, &Ce);
	print_poly(As, Ae);
	print_poly(Bs, Be);
	printf("-----------------------------------------------------------------------------\n");
	print_poly(Cs, Ce);
	return 0;
}

배열을 parameter로 갖는 함수

void test(int array[4]){
	array[2]=6;
}
int main(void)
{
	int a[4] = {1,2,3,4};
	test(a);
	printf("%d",a[2]);	
	return 0;
}

이전의 C Introduction을 진행하면서 위와 같은 상황은 생각해본적이 없는 것 같다.
->C언어에서 배열의 이름이 포인터 역할을 하기 때문에, 함수로 배열을 전달하면 항상 원본이 전달된다는 점에 유의하자.
-> 컴파일러는 배열의 이름에 공간을 할당하지는 않는다. 대신에 배열의 이름이 있는 곳을 배열의 첫 번째 요소의 주소로 대치한다. 따라서 배열의 이름이 포인터이다
->int A[4] = int (*A)[4]라고 봐도 된다는 소리이다.
이는 이전의 포스팅에서 확인한 길이가4인 배열을 가리키는 포인터이다.
예를 살펴보자 배열을 함수의 매개변수로 사용하는 프로그램이다.

#include <stdio.h>
#define SIZE 6

void get_integers(int list[]) // list라는 포인터이다.
{
	printf("6개의 정수를 입력하시오: ");
	for (int i = 0; i < SIZE; ++i) {
		scanf("%d", list+i)
		;
	}
}

int cal_sum(int list[])
{
	int sum = 0;
	for (int i = 0; i < SIZE; ++i) {
		sum += *(list + i);
	}
	return sum;
}

int main(void)
{
	int list[SIZE];
	get_integers(list);
	printf("합 = %d \n", cal_sum(list));
	return 0;
}

이제 구조체안에 구조체를 멤버로써 가지는 경우를 확인해보겠다.
구조체안에 구조체를 멤버로 갖게되면 .으로써 접근을 해주면 된다.
우리는 'Sparse Matrix'예시를 들것이다.
Sparse Matrix는 희소행렬로 행렬안에 0값이 너무 많이 들어있어서, 메모리와 연산시간을 많이 차지하는 행렬을 말한다. 이런 Sparse Matrix를 해결하기 위해서 이책에서는 행렬에 행을 따라 아래로 내려가면서,
행 열 value 순의 새로운 행렬을 만들고 이를
Transpose하는 연산을 구현해보겠다.

Sparse Matrix는 딥러닝의 경우 매우 빈번하게 생기는 행렬구조이고 이를 Informer에서 해결하기 위해 Contibution을 했다.

#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;

SparseMatrix matrix_transpose2(SparseMatrix a)
{
	SparseMatrix b;

	int bindex;		// 행렬 b에서 현재 저장 위치
	b.rows = a.rows; // 6
	b.cols = a.cols; // 6
	b.terms = a.terms; // 7

	if (a.terms > 0) { // zero matrix의 가능성이 있기 때문에
		bindex = 0;
		for (int c = 0; c < a.cols; c++) {
			for (int i = 0; i < a.terms; i++) {
				if (a.data[i].col == c) {
					// a의 항의 열이 몇번쨰 열인지 탐색하기위해서
					// a의 전체 열의 개수에 대해 반복문을 돌면서 맞는 것을 찾음
					b.data[bindex].row = a.data[i].col;
					b.data[bindex].col = a.data[i].row;
					// 구조체 안에 구조체 멤버에 접근해서 행과 열의 위치를 바꿔줌
					b.data[bindex].value = a.data[i].value;
					// value를 복사해준다
					bindex++;
					// b의 다음항에 접근하기 위한 연산
				}
			}
		}
	}
	return b;
}

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

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
		//총 6행6열 7개의 Non Zero Term이 있다.
	};
	SparseMatrix result;

	result = matrix_transpose2(m);
	matrix_print(result);
	return 0;
}

이제 구조체 포인터를 알아볼 것이다.
우리는 구조체를 가리키는 포인터를 생성하고 포인터를 통해서 멤버에 접근할 수 있다.

이때 편리한점은 포인터를 통해 구조체 멤버에 접근하는 편리한 표기법은 ->이다.
가령, struct element * p element라는 struct를 가리키는 포인터를 생각해보자. 이때 (*p).i보다 p->i가 더 편하다.
다시말해서 ->는 구조체 포인터에서 구조체의 멤버에 접근하는 연산자이다 p->i는 가리키는 구조체의 i멤버를 의미한다.

malloc을 사용한 동적메모리 할당으로 구조체 크기의 메모리를 할당받고 그안에 요소에 접근하는 코드를 살펴보겠다.

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

typedef struct  studentTag {
	char name[10]; // 문자배열로 된 이름
	int age;	  // 나이를 나타내는 정수값
	double gpa;	  // 평균평점을 나타내는 실수값
} student;

int main(void)
{
	student *p;

	p = (student *)malloc(sizeof(student)); //student*형 주소로 casting돼서 반환된다.
	if (p == NULL) {
		fprintf(stderr, "메모리가 부족해서 할당할 수 없습니다.\n");
		exit(1); //에러발생으로 프로그램 강제종료
	}

	strcpy(p->name, "Park"); //변수에 값을 copy하는 strcpy()
	p->age = 20;

	free(p);
	return 0;
}