Ⅲ 배열, 구조체, 포인터
Chapter 03 배열, 구조체, 포인터
1. 배열
① 배열이란?
타입이 같은 데이터들을 하나로 묶는 방법
② 배열 ADT
배열은 elements로 구성, 각각의 요소는 인덱스로 표시한다.
배열은 elements로 구성, 각각의 요소는 인덱스로 표시한다.
- Create 배열 구현 방법
create(10)
int A[10];
get(A, i)
value = A[i]; (read읽어와서 value에 집어 넣는 것)
set(A, I, v)
A[i] = v;
③ 1차원 배열
int list[6];
list[0] = 100; //set 연산에 해당된다.
value = list[0]; // get 연산에 해당된다.
④ 배열의 응용: 다항식
프로그램에서 다항식을 처리하려면 다항식을 위한 자료구조가 필요하다. 어떤 자료구조를 사용해야 연산이 편리해질 수 있을까?
- 다항식 표현 방법
장점: 다항식의 각종 연산이 간단해진다.
단점: 대부분의 항의 계수가 0이면 공간의 낭비가 심하다.
• 예) 다항식의 덧셈 연산
다항식을 배열에 표현
- 모든 차수에 대한 계수값을 배열에 저장
- 변수 degree상에 몇 차식인지 표현한다.
#define MAX_DEGREE101 //다항식의 최대차수 +1
typedef struct{
int degree;
float coef[MAX_DEGREE];
}polynomial;
polynomial a = {5, {10, 0, 0, 0, 6, 3}};
- poly_add()
p = 8x^3 + 7x + 1, q = 10x^3 + 3x^2 + 1
- p, q 의 표현은?
- p, q 의 덧셈 결과 다항식을 r이라 할 때, r은?
처리가 끝나면 position_화살표가 그 다음 열로 옮겨간다.
p + q의 결과를 리턴해주는 poly_add를 호출한다.
- 다항식 구조체 구현 코드
#include <stdio.h>
#define Max(a,b) (((a)>(b))?(a):(b))
#define MAX_DEGREE 101
typedef struct { // 다항식 구조체 타입 선언
int degree; // 다항식의 차수
float coef[MAX_DEGREE]; // 다항식의 계수
} polynomial;
// 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); // 결과 다항식 차수, C의 차수는 A와 B의 차수 중 큰 것이다.
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;
}
// 주함수
int main()
{
polynomial a = {5, {3, 6, 0, 0, 0, 10}};
polynomial b = {4, {7, 0, 5, 0, 1}};
polynomial c;
c = poly_add1(a, b);
printf(“---------------------------------------\n”);
printf_poly©;
return 0;
}
2. 구조체
① 구조체(structure)란?
타입이 다른 데이터를 하나로 묶는 방법
배열과의 공통점: 데이터를 여러 개 묶은 것
차이점: 같은 데이터를 묶은 것과 다른 데이터를 하나로 묶는 것의 차이
② 구조체 사용 예시
구조체의 선언과 구조체 변수의 생성
struct studentTag {
char name[10]; // 문자배열로 된 이름
int age; // 나이를 나타내는 정수값
double gpa; // 평균평점을 나타내는 실수값
};
struct studentTag s;
strcpy(s, name, “kim”);
s.age = 20;
s.gpa = 4.3;
s에는 3개의 멤버(name, age, gpa)가 존재한다.
age는 s의 멤버로서 존재하기 때문에 age = 20; 이라고 단독으로 쓰일 수 없다.
s.age = 20;의 형태로 자신의 소속을 밝혀주어야 한다.
③ typedef
C언어에 나오는 기능으로 자료형의 이름을 바꿔주는 역할을 한다.
- 구조체의 선언과 구조체 변수의 생성
struct studentTag {
char name[10];
int age;
double gpa;
};
typedef studentTag{
char name[10];
int age;
double gpa;
}student;
문제
1) 2차원 좌표 공간에서 하나의 점을 나타내는 구조체 Point를 정의하여 보라. Typedef도 사용하여서 구조체 Point를 하나의 타입으로 정의한다.
Struct Point{
int x;
int y;
};
Struct Point p1 = {1, 2};
Struct Point p2 = {9, 8};
2) 1에서 정의한 구조체의 변수인 p1과 p2를 정의하여 보라.
Struct Point p1;
Struct Point p2;
+ typedef struct Point{ … };로 정의하였을 경우 Point p1;으로 간결하게 작성 가능하다.
3) p1과 p2를 각각 (1,2)와 (9, 8)로 초기화하라.
Struct Point p1 = {1, 2};
Struct Point p2 = {9, 8};
4) 점을 나타내는 두 개의 구조체 변수를 받아서 점 사이의 거리를 계산하는 함수 get_distance(Point p1, Point p2)를 작성하라.
#include <math.h>
double sqrt(double n)
get_distance(Point p1, Point p2){
return(sqrt((p1.x – p2.x) * (p1.x – p2.x) + (p1.y – p2.y) * (p1.y – p2.y)));
};
3. 포인터
① 포인터란?
다른 변수의 주소를 가지고 있는 변수
char a = ‘A’
char *p; // p가 문자형 데이터의 주소값을 가진다.
p = &a;
- 변수를 선언하면 그 변수에 대한 메모리가 할당된다. 메인함수에 있는 지역변수는 함수가 일을 할 때 메모리를 할당받는다. 다시 말해, 자신이 속한 함수가 호출을 당하면 지역변수는 메모리를 할당받는다.이후, return문을 만나면 함수는 종료된다.
- 함수의 매개변수로 포인트 사용하기 : 함수 안에서 매개변수로 전달된 포인터를 이용하여 외부 변수의 값 변경 가능
- 주소를 받아와서 원본을 수정하는 것이 가능하기 때문에 포인터를 사용한다.
② 함수의 매개변수로 포인터 사용하기
포인터는 int x처럼 변수이고 데이터다. x하고 다른 점이 있다면 가질 수 있는 값, 모든 데이터는 속성 3가지가 있다. 이름이 있고 그 데이터가 저장된 곳에 주솟값이 있다. 그리고 그 데이터가 갖는 값이 있다. 내 프로그램의 정수는 항상 선언을 하고 써야 한다.
int x;
선언은 내가 사용할 거니까 미리 준비하라는 의미를 담고있다. 준비하라 함은 메모리에 x라는 변수를 위한 공간을 마련하라는 뜻이다. 데이터의 이름, 주소, 값을 지정해주는 것이다.
③ 포인터와 관련된 연산자
& 연산자: 변수 주소를 추출
* 연산자: 포인터가 가리키는 곳의 값을 추출
3가지 속성 : 이름, 주소, 값
오리지날 값: argument 인수 (인자)
swap(&a, &b)
swap(int *px, int *py)
함수를 호출할 때 이 인수의 값이 해당하는 파라미터에 카피가 된다. 이게 바로 ‘Call by value’
값을 호출하는 것 (모든 언어가 그런 것은 아니고 주소가 전달되는 것도 있다. 그런 것은 Call by reference 라고 한다. reference는 주소와 같다고 생각하면 된다.)
④ 포인터를 사용하는 이유
함수 호출을 통해서 argument(원본의 값)을 바꾸기 위해 사용한다. 주소를 복사해서 넘기는 것이다. 그 주소만 가지면 원본 데이터를 찾아갈 수 있기 때문이다.
원본의 데이터를 바꾸고 싶을 때는 그 원본의 주소를 복사해서 보내주면 호출당한 함수 쪽에서 그 열쇠(주소)를 가지고 원본을 찾아가서 바꿀 수 있는 것이다.
(함수 안에서 매개변수로 전달된 포인터를 이용하여 외부 변수의 값 변경 가능)
포인터의 제일 중요한 용도: 원본 변경
⑤ 배열과 포인터
배열의 이름: 사실상 포인터와 같은 역할
int a[6];
배열은 자동으로 포인터로 선언된다.
배열의 첫 번째 원소의 주소가 자동으로 들어간다.
C언어에서 배열을 선언하면 배열이름이 자동으로 포인터로 선언되고, 그 포인터에는 배열의 첫번째 원소의 주소가 자동으로 들어간다.
배열이름은 포인터 상수가 된다.
배열의 경우는 함수 호출과 관계가 있다. 배열을 파라미터로 보낼 때는 배열의 이름과 배열의 크기가 같이 가야 된다. 배열의 이름은 주소다. 배열의 이름이 파라미터로 갈 때 배열의 이름이 복사가 돼서 간다. 배열의 이름에 그 주소가 들어가 있으므로 배열 전체가 통째로 복사되어 가는 게 아니고 배열의 주소가 복사돼서 간다. 호출된 함수에서 배열의 주소를 복사해서 받았기 때문에 원본에 해당하는 배열의 값이 바뀌게 된다.
<포인터와 배열에 관한 2가지 정리>
1. 주소를 통해 원본을 찾아가서 바꿀 때 포인터를 사용하는 것
2. 배열 안에 포인터가 들어있는 것이므로 배열의 이름을 보내주면 배열의 주소가 복사되어 간다.
⑥ 함수 호출 시에 인수 전달 방법
값에 의한 호출(call by value)
- 함수로 복사본이 전달된다.
- 기본적인 방법
참조에 의한 호출(call by reference)
- 함수로 원본이 전달된다.
- C에서는 포인터를 이용하여 흉내 낼 수 있다.
- 리스트 배열 코드
#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;
}
리스트 배열 이름이 포인트라는 것을 강조해준 코드에 해당한다.
list의 값과 list[0]의 값은 동일하다.
*list list[0]
수식이란 연산자와 피연산자의 조합이라고 할 수 있다.
연산자가 2개 이상 나올 때는 우선순위가 높은 것부터 연산을 진행한다.
⑦ 동적 메모리 할당
프로그램 실행 중에 필요한 만큼의 기억공간을 동적 할당 가능
메모리 할당 관련 C함수 (stdlib 라이브러리에 포함)
- Malloc(): 매개변수로 전달된 개수만큼의 메모리를 할당하여 반환. 메모리 공간이 충분하지 않으면 NULL을 반환한다.
- free(): malloc()으로 할당된 기억공간을 시스템에 반환
<Memory Allocation>
- static
- dynamic
정적할당은 이 프로그램이 실행되기 전에 필요한 자원이 미리 할당된다.
동적 할당은 프로그램이 실행되는 도중에 할당되는 것이다.
- 변수
지역변수: 함수 안에서만 선언되는 변수 (함수 안에서만 사용되는 것)
전역변수: 함수 바깥에 선언되어 모든 곳에서 공통으로 사용가능한 것
+ (클래스) 객체 안에 있는 변수를 객체 변수라고 한다. instance
자바는 전역변수가 없다.
자기가 속한 함수가 호출을 당하면 그 함수에 선언되어 있는 지역변수가 일을 한다. 그리고 그 함수가 종료되면 할당되었던 메모리를 회수한다. 동적 할당은 실행 도중 명령문을 만나면 그때 할당되는 것을 말한다.
- 동적 메모리 할당 코드
프로그램 실행 중에 필요한 만큼의 기억공간을 동적 할당 가능
전형적인 동적 메모리 할당 코드
main()
{
int *pi;
pi = (int*)malloc(sizeof(int)); // 동적 메모리 할당
… // 동적 메모리 사용
free(pi); // 동적 메모리 반납
}
어디다 할당됐는지 알지 못하면 사용할 수 없기 때문에 할당한 다음에 그 할당된 곳의 주소를 리턴해준다. 그렇기에 pi는 그 앞에 포인터로 선언을 한다.
- 동적 메모리 할당 관련 라이브러리 함수
malloc(size) // 메모리 할당
free(ptr) // 메모리 할당 해제
sizeof(var) // 변수나 타입의 크기 반환 (바이트 단위)
무턱대고 크게 잡기 보다 프로그래밍을 진행하면서 할당 가능하다는 장점이 있다.
[예제]
10개의 정수를 포함하는 배열을 동적 할당하고, 이 배열에 10개의 난수(범위: 1~10)를 발생시켜서 저장하고, 출력하라.
int *p, i;
p = (int*)malloc(sizeof(int)*10); //동적 배열 생성
for(i=0; i<10; i++)
1) *p++ = rand()%10+1 //난수 발생하여 배열에 저장
for (i=0; i<10; i++)
printf("%d\n", p[i]); //배열 출력
다른 방법: 2) p[i] = rand()%10 + 1;
3) *(p+1) = rand()%10 + 1;
[문제] 다음 프로그램의 오류를 모두 지적하시오.
int main(void){
double *p1;
p1 = (int*)malloc(double);
p1 = 23.92;
}
답: double이 아닌 sizeof
int main(void){
double *p1;
p1 = (double*)malloc(sizeof(double);
*p1 = 23.92;
}
동적 자료구조
동적 메모리 할당을 통해서 구성되는 자료구조
구조체를 3개 생성하여 한 줄로 연결하기
struct linkedNum
{
int val;
struct linkedNum *next;
}
next는 포인터로 선언하여 next가 가리키는 곳을 가면 이 구조체가 있다. 이 구조체의 타입은 struct linkedNum
struct linkedNum *pi;
p1 = (struct linkedNUm*)malloc(sizeof(struct linkedNum));
p2 = (struct linkedNUm*)malloc(sizeof(struct linkedNum));
p3 = (struct linkedNUm*)malloc(sizeof(struct linkedNum));
p1 -> val = 10;
p1 -> next = p2;
p2 -> val = 20;
p2 -> next = p3;
p3 -> val = 30;
p3 -> next = NULL;