[자료구조] 02. Arrays and Structures

1. Arrays

1.1 ADT

• 배열 : <index, value>의 쌍으로 구성된 집합
• 기본 기능 : 값 검색, 값 저장
• ADT Array

  Objects : index의 각 값에 대해 집합 item에 속한 한 값이 존재하는 <index, value> 쌍의 집합. index는 1차원 또는 다차원의 유한 순서 집합이다.
  Functions:
     모든 A∈Array / i∈index / x∈item / j,size∈integer
     Array Create(j, list)
          return j 차원의 배열
     Item Retrieve(A, i)
          if (i∈index)
              return 배열 A의 인덱스 i 값과 관련된 항목
          else return 에러
     Array Store(A, i, x)
          if (i∈index)
              return 새로운 쌍 <i, x>가 삽입된 배열 A
          else return 에러

1.2 C에서의 배열

• 1차원 배열의 선언 : int list[5];(정수의 배열) / int *plist[5];(정수 포인터의 배열)
• 배열 간의 주소 차이는 배열을 구성하는 변수의 크기에 비례한다.
  
  → 정수형(4 byte) 만큼 주소값 증가
• C에서 list[i]는 정수의 포인터로 사용할 수 있다
  • int *list1 과 int list2[5]가 같은 것을 나타낼 수 있다
  • (list2+i) = &list2[i]
  • *(list2+i) = list2[i]
• 배열 프로그램의 예

#define MAX_SIZE 100
float sum(float a[], int n);
float input[MAX_SIZE], answer;

void main(){
  int i;
  for (i = 0; i < MAX_SIZE; i++)
    input[i] = i;
  answer = sum(input, MAX_SIZE);
  printf("The sum is: %f\n", answer);
}

float sum(float a[], int n){
  int i;
  float tempsum = 0;
  for(i = 0; i < n; i++)
    tempsum += a[i];
  return tempsum;
}

→ sum 함수 호출시 a배열의 첫 원소에 대한 주소값 복사.
→ main 에선 i번째 원소에 i 저장
→ sum 에선 a의 모든 원소를 더함

• [1차원 배열의 주소 계산]
  int one[] = {0,1,2,3,4}; 의 i 번째 주소와 그 주소 내 값을 출력하는 함수

void print1(int *ptr, int rows){
  // 포인터를 사용해 1차원 배열을 출력
  int i;
  printf("Address Contents\n");
  for(i = 0; i < rows; i++)
    printf("%8u%5d\n", ptr + i, *(ptr + i));
  printf("\n");
}

---

2. Dynamically Allocated Array

2.1 1차원 배열의 동적 할당

// malloc 을 이용한 1차원 배열
int i,n,*list;
printf("Enter the number of numbers to generate: ");
scanf("%d",&n);
if(n < 1){
	fprintf(stderr, "Improper value of n\n");
	exit(EXIT_FAILURE);
}
MALLOC(list, n * sizeof(int));

// malloc 매크로
#define MALLOC(p,s) \ // 포인터 p, 자료형의 크기 s
    if ((p = malloc(s) == NULL) { \
        fprintf(stderr, "Insufficient memory"); \
				exit(EXIT_FAILURE); \
    }

2.2 2차원 배열의 동적 할당

// 2차원 배열의 동적 할당
int** make2dArray(int rows, int cols){
  // rows x cols 크기의 2차원 배열을 생성
  int **x, i;
	
  MALLOC(x, rows * sizeof(int *));  // 행에 대한 공간 생성
  for(i = 0; i < rows; i++) 
    MALLOC(x[i], cols * sizeof(int)); // 각 행마다의 열에 대한 공간 생성
  return x;
}

• void *calloc(elt_count, elt_size 함수
  • elt_size만큼의 데이터 크기를 가진 elt_count길이의 동적 배열을 만드는 함수
  • 사용자가 지정한 매모리 할당 & 0으로 자동 초기화(malloc은 초기화 X)
• void *realloc(p, s) 함수
  • 기존 포인터 p를 s만큼의 사이즈로 바꾸는 함수

---

3. Structures and Unions

3.1 구조체

• 구조체 : 서로 다른 타입의 데이터를 그룹화 하는 것

// 구조체 만들기
typedef struct {
	char name[10];
	int age;
	float salary;
} Person;

// 값 할당하기
strcpy(person.name, "james");
person.age = 10;
person.salary = 35000;

→ typedef + struct로 단축해서 생성 가능

• 구조체 값 자체의 동등성 여부는 검사할 수 없음. 대신 함수를 생성해서 처리해야 함

// 구조체 비교
#define FALSE 0
#define TRUE 1
typedef struct{
  char name[20];
  int age;
  float salary;
} humanBeing;

humanBeing person1, person2;
// person1과 person2 직접적 비교는 불가능

int humansEqual(humanBeing person1, humanBeing person2){
  // 동일인 일시 TRUE, 그렇지 않으면 FALSE 반환
  if (strcmp(person1.name, person2.name))
    return FALSE;
  if (person1.age != person2.age)
    return FALSE;
  if (person1.salary != person2.salary)
    return FALSE;
  return TRUE;
}

• 구조체 속 구조체 정의 가능

// 구조체 속 구조체
typedef struct date{
	int month;
	int day;
	int year;
} date;

typedef struct{
  char name[20];
  int age;
  float salary;
  date dob;
} humanBeing;

// 접근 방법
humanBeing person;
person.dob.month = 2;
person.dob.day = 11;
person.dob.year = 2022;

3.2 유니온

• 유니온 : 메모리 공간을 공용으로 사용
  • 여러 필드 중 한 필드만 활성화 되어 사용 가능

ex) humanBeing 에서 sexType을 추가해 한 필드에서 여자라면 출산 아동수를, 남자라면 턱수염 여부를 저장

typedef struct {
	enum tagField {female, male} sex;
	union {
		int childern;  // 여자인 경우
		int beard;  // 남자인 경우 
	} u;
} sexType;

typedef struct{
  char name[20];
  int age;
  float salary;
  sexType sexInfo;
} humanBeing;

// 접근 방법
humanBeing person1, person2;

person1.sexInfo.sex = male;
person1.sexInfo.u.beard = FALSE;

person1.sexInfo.sex = female;
person1.sexInfo.u.childern = 4;

→ 먼저 enum을 통해 태그 필드에 값 설정
→ union에 있는 필드의 활성화를 결정

• C언어는 union의 올바른 필드 사용을 요구하지 않는다 (오류 발생 X)

3.3 구조체의 내부 구현

• 구조체 내부 요소의 주소값
  • 구조 정의에서 명세된 순서로 주소의 위치를 저장
  • 실제로는 메모리를 맞추기 위해 padding 할 수 있다
• 구조는 같은 유형의 메모리 경계에서 시작하고 끝남.
  • 짝수 바이트 or 4, 8, 16 배수 메모리 경계

3.4 자기 참조 구조(Self-Referential Structures)

• 자기 참조 구조 : 구성 요소 중 자기 자신을 가리키는 포인터가 1개 이상 존재하는 구조
  • 동적 저장 관리 루틴(malloc / free)가 필요

typedef struct {
	char data;
	struct list *link;
} list;

→ data는 하나의 문자, link는 자기 자신(list)에 대한 포인터
→ 이를 활용해 list 구조 여러 개를 서로 연결할 수 있다.