[자료구조] 배열과 구조(Array and Structure)

배열(Array)

대부분의 프로그래머에게 배열은 '연속된 메모리 위치'

- 구현의 관점에서 한 정의이므로 일반적인 관점에서 정의할 필요가 있다.

 

추상 데이터 타입(Abstract Data Type, ADT) 관점에서 고려하면

(이는 배열을 더 일반적 구조로 설명하여 구현에 독립적이게 한다.)

배열은 <index, value> 쌍의 집합

 

 

*배열 index를 0부터 시작하는 이유: Base Position에서의 Offset(얼마나 떨어져 있는지)

 

 

동적으로 할당된 배열(Dynamically Allocated Arrays)

동적 할당의 필요성: 배열의 크기가 프로그램 실행 시간에 동적으로 변화할 경우.

-> 배열의 크기를 결정하기 힘들 때 실행시간을 미루었다가 배열의 크기가 정해지면 동적으로 할당.

#define MALLOC(p, s) \
	if(!((p) = malloc(s))){\
    	fprintf(stderr, "Insufficient Memory");\
        exit(EXIT_FAILURE);
    }

2차원 배열에서는 차원이 커지더라도 배열의 배열로 생각

-크게 만들고, 그 안에서 다시 할당.

 

calloc: 사용자가 지정한 양의 메모리를 할당 후 0으로 초기화

realloc: malloc, calloc으로 할당된 메모리 크기 재조정

 

 

구조와 유니언(Structures and Unions)

struct

-타입이 다른 데이터를 그룹화(레코드)

-데이터 항목의 집단 - 각 항목은 타입과 이름으로 식별

 

typedef를 이용한 구조 데이터 타입 생성

 

동등성 검사는 if(structure1 == structure2) 형식으로 검증할 수 없고, 일일히 비교해봐야 함.

 

union

필드들은 메모리 공간을 공유

 

structure의 내부 구현

- 오름차 주소의 위치를 이용하여 저장

- 내부 빈 공간을 두거나 padding을 할 수 있음(compiler마다 차이)

- 같은 메모리 경계에서 시작하고 끝나야 함

- 짝수 바이트, 4, 8, 16등의 배수에서 메모리 경계가 있음.

 

자기 참조 구조: 구성요소 중 자신을 가리키는 포인터가 존재하는 구조.

통상적으로 동적 저장공간 관리 루틴(malloc, free) 필요

 

 

다항식(Polynomials)

배열을 이용하여 다항식 추상데이터 타입 정의

배열은 자체가 자료구조이면서 다른 추상데이터 타입 구현에 이용

 

순서 리스트(Ordered list, linear list)

-원소들의 순서가 있는 모임(요일, 카드 순서, 층 등)

- 계산/읽기/검색/대체/삽입/제거 등의 연산

 

순서 리스트의 표현

-메모리 표현

-순차 사상(sequence mapping)

-물리적 인접성(array)

 

(자세한거 생략하기)

 

희소 행렬(Sparse Matrices)

행렬 m*n matrix A = A[MAX_ROW][MAX_COL]

희소행렬: 결정은 직관적(기준은 없음)

희소행렬을 일반적인 배열로 구현하면 저장 공간이 낭비

 

추상데이터 타입

희소행렬의 표현

-3원소 쌍 <행, 열, 값>으로 표현

-전치 연산을 위해 행을 오름차순으로 조직

-동일 행이면 열에 대한 오름차순

-연산 종료 보장을 위해서 행과 열의 수와 행렬 내의 0이 아닌 항의 수를 알아야함.

 

 

다차원 배열의 표현(Representations of Multidimensional Arrays)

다차원 배열 표현 방법- 행 우선/열 우선

 

쓰자니 복잡해서.

 

문자열(String)

 

널 문자(\0)로 끝나는 문자 배열을 의미

 

패턴 매칭

'pat'이라는 패턴을 string 내에서 탐색하려고 할 때에

1) 가장 간단한 방법은 strstr을 이용하여 탐색.

 

2) 개선안 --복잡도 O(min(m, n)^2)

-strlen(pat)이 string의 나머지 문자 수보다 크면 종료->성능개선

-pat과 string의 첫 문자와 마지막 문자를 검사->성능 개선

 

3) nfind 시뮬레이션

-string과 pat 배열의 끝을 각각 lasts와 lastp로 가리키게 하고

-string[endmatch]와 pat[lastp]를 비교

-매칭시 nfind는 매치되지 않거나, pat가 모두 매치될 때까지 두 스트링 이동을 위한 i,j 사용

-start는 매치되지 않을 경우 i의 재설정에 이용됨.