2장: 배열과 구조체

2.1 배열

2.1.1 추상자료형

대부분의 언어가 제공하는 배열의 표준연산: 생성, 검색, 저장

2.1.2 C에서의 배열

배열의 첫 원소의 주소를 base address라고 한다.

int list[5]에서의 base address는 list[0]의 주소
list[i]의 주소는 base address + i*sizeof(int)
(list2+i) = &list2[i], *(list2+i) = list2[i] (자료형의 크기를 곱하지 않는다.)

---

2.2 동적 할당 배열

2.2.1 1차원 배열

배열의 크기를 매우 크게 정하면
프로그램이 실행 시간에 실패하는 가능성은 떨어지지만,
메모리 부족으로 인해 컴파일에 실패할 가능성 증가

2.2.2 2차원 배열

할당

int **list;

MALLOC(list, rows*sizeof(*list));
// list = (int **)malloc(rows*sizeof(*list));
for(int i = 0; i < rows; ++i)
    MALLOC(list[i], cols*sizeof(**list));
    // list[i] = (int *)malloc(cols*sizeof(**list));

해제

for(int i = 0; i < rows; ++i)
    free(list[i]);
free(list);

calloc: 할당 후 0으로 초기화
realloc: 크기 조정

---

2.3 구조체와 공용체

2.3.1 구조체

cf ) 배열 - 동일 자료형
필드(멤버)로 구성
멤버 연산자 '.'
typedef 사용
패딩비트 사용

typedef struct _Human{
    char name[10];    // char pad[2]; 패딩비트
    int age;
    float salary;
} Human;

sizeof(Human);    // 20 ( 패딩비트 )

구조체의 대입 연산은 가능하지만 비교 연산은 불가능 // 비교 연산 시 각각의 멤버 변수에 대해서 비교
구조체 멤버로 구조체 사용 가능

2.3.2 공용체

공용체의 필드는 메모리 공간 공유 -> 한 필드만 주어진 시간에 기능을 한다.
크기는 가장 큰 필드의 크기
구조체와 같이 패딩비트 사용

union {
    char name[10];
    int age;
} info;

sizeof(info);    // 12 ( sizeof(name) > sizeof(age), 패딩비트 )

2.3.3 자기 참조 구조체

하나 이상의 멤버가 자신의 포인터인 구조체

typedef struct _List *ListPointer;
typedef struct _List{
    char data;
    ListPointer link;
} List;

---

2.4 다항식

---

2.5 희소행렬

---

2.6 다차원 배열의 표현

다차원 배열을 표현할 때 배열의 배열 꼴이 아닌 선형 리스트의 1차원 배열과 같은 꼴로 나타내는 경우 주소 공식이 복잡해진다.
다차원 배열 a[upper_0][upper_1][upper_2]...[upper_n-1]의 element 수: upper_0*upper_1*upper_2*...*upper_n-1

본 책에서는 다차원 배열의 표현법인 row major order와 column major order 중 row major order만 고려

A[upper_0][upper_1]은 upper_0줄이 각각 upper_1개의 element를 가지고 있는 형태이므로

A[0][0]의 주소를 a라고 할 때, A[i][0]의 주소는 a+i*upper1, A[i][j]의 주소는 a+i*upper_1+j

B[upper_0][upper_1][upper_2]는 upper_0 개의 upper_1*upper_2 2차원 배열로 구성된 형태이므로
B[0][0][0]의 주소를 b라고 할 때, B[i][0][0]의 주소는 b+i*upper1*upper2, B[i][j][k]의 주소는 b+i*upper_1*upper_2+j*upper_2+k

일반화하여, C[upper_0][upper_1]...[upper_n-1]에서
C[0][0]...[0]의 주소를 c라고 할 때,
C[i_0][i_1]...[i_n-1]의 주소는 c+sigma{j=0

n-1}(i_j*a_j), a_j = pi{k=j+1

n-1}(upper_k)

---

2.7 문자열

2.7.1 추상자료형

생성, 읽기 or 출력, 합성(연쇄), 비교, 삽입, 삭제, 찾기

2.7.2 C에서의 문자열

끝이 널문자(\0)로 끝나는 문자 배열

char s[100] = {"dog"};
// vs
char s[] = {"dog"};

strcat(s, t)를 호출했을 때, s에 t를 추가할 공간이 없다면 overwrite될 가능성 존재

* 참고: http://www.jbox.dk/sanos/source/lib/string.c.html
\ strspn에서의 control map의 비트를 설정하는 부분이 이해가 되지않는다.

insert = strncpy -> strcat -> strcat

2.7.3 패턴 매칭

strstr으로 가능

가장 쉬운 방법은 각 문자에 대해서 순차적으로 비교: O(nm)의 계산 시간 필요
비교하는 문자열의 길이를 고려하는 것으로 1차 개선
첫, 끝 글자를 비교하여 2차 개선
2번의 개선하더라도 최악의 경우에는 O(nm)의 계산 시간 필요

KMP 알고리즘의 계산 시간은 O(n+m)
\ KMP 알고리즘

---

* 단어

• sparse 부족한
• consecutive 연속적인
• retrieve 검색하다
• bracket 대괄호
• abbreviate 줄여 쓰다
• retrieve 검색하다
• stipulation 약정