CS과목/자료구조

[CS과목/자료구조] 03 배열, 구조체, 포인터

johyeongseob 2024. 9. 15. 22:35

교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외)

 

3.1 배열

  배열은 동일한 타입의 데이터를 한 번에 여러 개 만들 때 사용된다. 대량의 데이터를 저장하기 위하여 배열을 사용하면 "연속적인 메모리 공간"이 할당되고 인덱스(index) 번호를 사용하여 쉽게 접근이 가능하기 때문에 반복 루프를 이용하여 여러 가지 작업을 손쉽게 할 수 있다.

 

배열 ADT

  배열은 <인덱스, 값>의 쌍의로 이루어진 집합으로 정의할 수 있다. 즉 인덱스(index)가 주어지면 해당하는 값(value)이 대응되는 자료 구조이다. 수학적으로 배열은 인덱스에서 값의로의 사상(mapping)에 해당된다.

3.2 구조체

구조체의 개념

 복잡한 객체어는 다양한 타입의 데이터들이 한데 묶여져서 있다. 배열이 타입이 같은 데이터의 모임이라면 구조체(structure)는 타입이 다른 데이터를 묶는 방법이다. C언어에서는 struct 키워드를 이용하여 표기한다. 구조체의 형식은 다음과 같이 정의한다.

struct 구조체이름 {
	항목1;
	항목2;
	...
};

 

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

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

 

  구조체 안에 들어 있는 맴버를 사용하려면 어떻게 할까? 구조체 변수 뒤에 '.'을 첨가한 후 항목 이름을 적으면 된다. '.'을 맴버연산자(membership operator)라고 한다. C언어에서는 typedef을 사용하여 구조체를 새로운 타입으로 선언하는 것이 가능하다. 그리고 구조체는 중괄호를 사용하여 선언 시에 초기화하는 것이 가능하다.

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

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

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

student s;

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

 

3.3 배열의 응용: 다항식

  수학에서 나오는 다항식을 배열을 이용하여 표현해보자. 방법은 모든 차수의 계수값을 배열에 저장한는 것이다. 아래 코드를 참고한다.

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

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

polynomial poly_add(polynomial A, polynomial B);
void print_poly(polynomial p);

int main(void)
{
	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_add(a, b);
	printf("--------------------------------------------------------------\n");
	print_poly(c);
	return 0;
}

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) { // 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]);
}

 

3.5 포인터

포인터의 개념

 포인터(pointer)는 다른 변수의 주소를 가지고 있는 변수이다. 모든 변수는 메모리 공간에 저장되고 메모리의 각 바이트에는 주소가 매겨져 있다. 이 주소가 포인터에 저장된다.

 

포인터와 관련된 연산자

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

  • & 연산자 - 주소연산자: 변수의 주소를 추출하는 연산자이다.
  • * 연산자 - 간접참조 연산자 (역참조 연산자라고도 한다): 포인터가 가리키는 장소에 값을 저장하는 연산자이다.

함수 매개변수로 포인터 사용하기

 포인터는 함수의 매개변수로 전달될 수 있다. 특정한 변수를 가리키는 포인터가 함수의 매개변수로 전달되면 그 포인터를 이용하여 함수 안에서 외부 변수의 값을 변경할 수 있다. 하나의 예로 외부 변수 2개의 값을 서로 바꾸는 swap()함수를 포인터를 이용하여 작성해보자.

#include <stdio.h>
void swap(int* px, int* py);

int main(void)
{
	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);
	return 0;
}

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

 

배열과 포인터

 컴파일러는 배열의 이름이 있는 곳을 배열의 첫 번째 요소의 주소로 대치한다. 따라서 배열의 이름이 포인터이기 때문에 배열이 함수의 매개변수로 전달될 때에 사실은 포인터가 전다로디는 것이다. 이것은 메모리 공간과 함수 호출 시간을 절약하는 기법이기도 하다. 함수 호출 시에 배열을 복사할 필요가 없기 때문이다.

#include <stdio.h>
#define SIZE 6
#define _CRT_SECURE_NO_WARNINGS

void get_integers(int list[]);
int cal_sum(int list[]);

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

void get_integers(int list[])
{
	printf("%d개의 정수를 입력하시오: ", SIZE);
	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);
		/*
		포인터 연산에서 중요한 것은 list가 가리키는 데이터의 타입의 크기입니다.
		list가 int 타입의 포인터라면, int 타입의 크기(일반적으로 4바이트)가 중요해집니다.
		포인터 연산 list + i를 수행할 때, 실제로 메모리 주소에서 더해지는 바이트 수는 i * sizeof(*list)가 됩니다.
		*/
	}
	return sum;
}

 

3.6 동적 메모리 할당

 C언어에서는 필요한 만큼의 메모리를 운쳥체제로부터 할당받아서 사용하고, 사용이 끝나면 시스템에 메로리를 반납하는 기능이 있다. 이것을 동적 메모리할당(dynamic memory allocation)이라고 한다. 동적 메모리가 할당하는 공간을 히프(heap)라고 한다. 히프는 운영체제가 사용되지 않는 메모리 공간을 모아 놓은 곳이다. 전형적인 동적 메모리 할당 코드는 다음과 같다.

main()
{
	int* pi;
	pi = (int*)malloc(sizeof(int)); // 동적 메모리 할당
	*pi = 1000;	// 동적 메모리 사용
	free(pi); // 동적 메모리 반납
}
  • malloc()함수는 size 바이트 만큼의 메모리 블록을 할당한다.
  • 동적 메모리는 포인터로만 사용할 수 있다.
  • free()함수는 할당된 메모리 블록을 운영체제에게 반환한다.

malloc()은 시스템의 메모리가 부족해서 요구된 메머리를 할당할 수 없으면 NULL을 반환한다. 따라서 malloc의 반환값은 항상 NULL인지 검사하여야 한다.

 

구조체와 포인터

 우리는 구조체에 대한 포인터를 선언하고 포인터를 통하여 구조체 멤버에 접근할 수 있다. 여기서 하나 주의할 것은 포인터를 통하여 구조체의 맴버에 접근하는 편리한 표기법 "->"이다. ps가 구조체를 가리키는 포인터라고 할 때, (*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;

	printf("age: %d, name: %s", s->age, s->name);
	free(s);
	return 0;
}

 

'CS과목 > 자료구조' 카테고리의 다른 글

[CS과목/자료구조] 06 연결 리스트 1  (0) 2024.09.15
[CS과목/자료구조] 05 큐  (0) 2024.09.15
[CS과목/자료구조] 04 스택  (0) 2024.09.15
[CS과목/자료구조] 02 순환  (0) 2024.09.15
[CS과목/자료구조] 01 자료구조와알고리즘  (0) 2024.09.15

'CS과목/자료구조'의 다른글

  • 현재글[CS과목/자료구조] 03 배열, 구조체, 포인터

관련글

티스토리툴바