[자료구조]CH2. 자료구조 구현을 위한 C프로그래밍 기법(구조체,재귀호출)

참조 : C로 배우는 쉬운 자료구조(이지영 저)

공부날짜 : 2021.01.17

 

<Section 3> 구조체

 

1. 구조체 개념

 

 배열은 자료형이 같을 때만 그룹으로 묶을 수 있지만, 구조체는 서로 다른 자료형도 그룹으로 묶을 수 있어 복잡한 자료 형태를 정의할 때 사용할 수 있다.

 자료의 단위 형식을 레코드(행), 레코드를 구성하는 하위항목을 필드, 레코드가 여러 개 모이면 파일이 된다.

 

2. 구조체 선언

 

 구조체의 데이터 항목은 자료형은 서로 다를 수 있으므로 항목별로 자료형과 항목 이름(변수 이름)을 선언한다.

구조체형의 선언은 구조체의 모양을 선언한 것이므로, 사용할 때는 구조체 변수를 선언해주어야 한다.

 

*구조체형의 선언

struct 구조체형이름

{

      자료형 항목1;

      자료형 항목2;

      ...

      자료형 항목n;

};

 

*구조체 변수 선언

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

 

*구조체 변수의 사용 : 내부항목에 데이터를 저장하고 사용한다.

 

3. 구조체 변수의 초기화

 

 내부항목의 자료형과 개수를 순서에 맞추어 초깃값 리스트로 지정하고 중괄호{}를 사용한다.

struct employee

{

     char name[10];

     int year;

     int pay;

};

struct employee Lee = {"Ann",2015,4200};

 

4. 데이터 항목의 참조

 

 4.1 점 연산자(.)

 데이터 항목을 개별적으로 지정할 때 사용한다.

struct employee Lee;

Lee.name = "Ann";

Lee.year = 2015;

Lee.pay = 4200;

 

 4.2 화살표 연산자(->)

 구조체형 포인터에서 포인터가 가리티는 구조체 변수의 데이터 항목을 지정할 때 사용한다.

struct employee Lee;

struct employee *Sptr=&Lee;

Sptr->name = "Ann";

Sptr->year = 2015;

Sptr->pay = 4200;

 

5. 구조체 연산

 

 5.1 데이터 항목 참조 연산

  점 연산자와 화살표 연산자를 사용해서 데이터 항목을 개별적으로 참조할 수 있다.

 

 5.2 구조체 변수 복사 연산

  같은 구조체에 있는 구조체 변수라면 변수들끼리 내용을 한 번에 복사하는 연산을 할 수 있다.

 

 5.3 구조체 변수의 주소 구하기 연산

  포인터의 주소 연산자를 사용하여 구조체 변수의 주소를 구하거나, 구조체 변수가 배열인 경우에는

 배열의 특성에 따라 구조체 배열 변수의 이름에서 주소를 구할 수 있다.

 

<Section 4> 재귀호출

 

1. 재귀호출의 개념

 

 함수가 자기 자신을 호출하여 순환하여 수행되는 것으로 순환 호출 또는 recursion이라고 한다.

한 번에 해결할 수 없는 현재의 작업을 한 단계 작게 분할한 하위 작업에 대해 재귀호출을 반복하게 되면,

한 번에 해결할 수 있을 정도의 단계에 도달하게 되는데, 이 단계를 베이스케이스라고 한다.

베이스케이스에서 구한 답을 반환하여 재귀호출의 역순으로 반복하면 결국 처음의 문제를 해결할 수 있다.

 

2. 재귀호출의 예1 : 팩토리얼 함수

 

 팩토리얼(!)은 1부터 어떠한 값 n까지의 모든 자연수를 곱하는 연산이다.

현재 필요한 팩토리얼의 값을 구하려면 하위값에 대한 팩토리얼 구하는 작업을 1!(베이스케이스)까지 반복한다.

 

long int fact(int n)

{

     if(n<=1)

          return (1);

     else

          return(n*fact(n-1));

}

 

3. 재귀호출의 예2 : 하노이 탑

 

원반 개수가 n개이고 시작봉A, 작업봉B, 목적봉C가 있다.

 

*시작봉에 있는 원반1~원반n-1을 목적봉을 이용하여 중간 작업봉으로 옮긴다.

 hanoi(n-1,start,target,work) // 옮겨지는 원반의 수가 1이 될때까지 하위작업을 위한 재귀호출이 이루어진다.

 

*시작봉에 있는 마지막 원반n을 목적봉으로 옮긴다.

 hanoi(1,start,work,target)

 

*중간 작업봉에 있는 원반1~원반n-1을 시작봉을 이용하여 목적봉으로 옮긴다.

 hanoi(n-1,work,start,target) // 옮겨지는 원반의 수가 1이 될때까지 하위작업을 위한 재귀호출이 이루어진다.