[자료구조] 배열 구조체 포인터

배열

같은 형의 변수를 여러 개 만드는 경우에 사용한다. 반복 코드 등에서 배열을 사용하면 효율적인 프로그래밍이 가능하다.

• 배열의 응용 : 다항식

다항식의 일반적인 형태

다항식 표현 방법

모든 차수에 대한 계수값을 배열로 저장한다. 하나의 다항식을 하나의 배열로 표현한다.

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

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

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

// C = A+B 여기서 A와 B는 다항식이다. 구조체가 반환된다. 
polynomial poly_add1(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) { // A항 > B항
			C.coef[Cpos++] = A.coef[Apos++];
			degree_a--;
		}
		else if (degree_a == degree_b) { // A항 == B항
			C.coef[Cpos++] = A.coef[Apos++] + B.coef[Bpos++];
			degree_a--; degree_b--;
		}
		else {			// B항 > A항
			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()
{
	polynomial a = { 5,{ 3, 6, 0, 0, 0, 10 } };
	polynomial b = { 4,{ 7, 0, 5, 0, 1 } };
	polynomial c;
	print_poly(a);
	print_poly(b);
	c = poly_add1(a, b);
	printf("-----------------------------------------------------------------------------\n");
	print_poly(c);
	return 0;
}

• 배열의 응용 : 희소행렬

희소행렬은 대부분의 항들이 0인 배열이다.

희소행렬 표현방법

2차원 배열을 이용하여 배열의 전체 요소를 저장하는 방법이다. 장점은 행렬의 연산들을 간단하게 구현할 수 있는 것이고, 단점은 대부분의 항들이 0인 희소 행렬의 경우 많은 메모리 공간을 낭비한다는 것이다.

#include <stdio.h>
#define ROWS 3
#define COLS 3
// 희소 행렬 덧셈 함수
void sparse_matrix_add1(int A[ROWS][COLS],
	int B[ROWS][COLS], int C[ROWS][COLS]) // C=A+B
{
	int r, c;
	for (r = 0; r < ROWS; r++)
		for (c = 0; c < COLS; c++)
			C[r][c] = A[r][c] + B[r][c];
}
main()
{
	int array1[ROWS][COLS] = { { 2,3,0 },
				{ 8,9,1 },
				{ 7,0,5 } };
	int array2[ROWS][COLS] = { { 1,0,0 },
				{ 1,0,0 },
				{ 1,0,0 } };
	int array3[ROWS][COLS];
	sparse_matrix_add1(array1, array2, array3);
}

---

구조체

타입이 다른 데이터를 하나로 묶는 방법이다.

배열은 타입이 같은 데이터들을 하나로 묶는 방법이다.

• 구조체 사용의 예

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

//구조체 변수 생성
struct studentTag s;
strcpy(s.name, "kim");
s.age = 20;
s.gpa = 4.3;

• typedef 사용

C언어의 typedef 키워드는 이미 존재하는 타입에 새로운 이름을 붙일 때 사용한다.

구조체 변수를 선언하거나 사용할 때에는 매번 struct 키워드를 사용하여 구조체임을 명시해야 한다.

하지만 typedef 키워드를 사용하여 구조체에 새로운 이름을 선언하면 매번 struct 키워드를 사용하지 않아도 된다.

#include <stdio.h>

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

int main(void)
{
	student a = { "kim", 20, 4.3 };
	student b = { "park", 21, 4.2 };
	return 0;
}

---

포인터

다른 변수의 주소를 가지고 있는 변수이다. 포인터가 가리키는 내용의 변경: * 연산자 사용

• & 연산자: 변수의 주소를 추출
• * 연산자: 포인터가 가리키는 곳의 내용을 추출포인터의 종류

int *p;   // p는 int형 변수를 가리키는 포인터

float *pf; // pf는 double형 변수를 가리키는 포인터

char *pc; // pc는 char형 변수를 가리키는 포인터

 

함수의 파라미터로서의 포인터

#include <stdio.h>
void swap(int* px, int* py)
{
	int tmp;
	tmp = *px;
	*px = *py;
	*py = tmp;
}
main()
{
	int a = 1, b = 2;
	printf("swap을 호출하기 전: a=%d, b=%d\n", a, b);
	swap(&a, &b);
	printf("swap을 호출한 다음: a=%d, b=%d\n", a, b);
}

배열과 포인터

배열의 이름 : 사실상의 포인터와 같은 역할

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define SIZE 6
void get_integers(int 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;
}

구조체와 포인터

구조체의 요소에 접근하는 연산자: ->

#define _CRT_SECURE_NO_WARNINGS
#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));
	if (p == NULL) {
		fprintf(stderr, "메모리가 부족해서 할당할 수 없습니다.\n");
		exit(1);
	}
	strcpy(p->name, "Park");
	p->age = 20;
	free(p);
	return 0;
}

---

동적 메모리 할당

• 프로그램의 실행 도중에 메모리를 할당 받는 것
• 필요한 만큼만 할당을 받고 또 필요한 때에 사용하고 반납
• 메모리를 매우 효율적으로 사용가능

// MALLOC.C: malloc을 이용하여 정수 10를 저장할 수 있는 동적 메모리를 
// 할당하고 free를 이용하여 메모리를 반납한다. 
#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) {
		fprintf(stderr, "메모리가 부족해서 할당할 수 없습니다.\n");
		exit(1);
	}
	for (int i = 0; i < SIZE; i++)
		p[i] = i;
	for (int i = 0; i < SIZE; i++)
		printf("%d ", p[i]);
	free(p);
	return 0;
}