자료구조 배열

배열의 정의

일정한 차례나 간격에 따라 벌여 놓음(사전적 정의)

차례(순서)와 관련된 기본적인 자료구조

원소릐 메모리공간의 물리적인 위치를 순서적으로 결정하는 특징

배열의 순서는 메모리 공간에서 저장되는 원소값의 물리적 순서

인덱스와 원소값으로 구성됨

 

의미

원소들이 모두 같은 자료형과 같은 크기의 기억공간을 가짐

배열의 인덱스 값 : 추상화 된 값 = 컴퓨터의 내부구조나 메모리 주소와 무관하게 개발자에게 개념적으로 정의됨

메모리 주소 값은 실제 모모리의 물리적인 위치 값

인텍스와 주소값 의 관계 (보통 배열의 인덱스는 0부터 시작)

 

배열의 추상 자료형

추상자료형 *수학접 접근

객체 및 관련된 연산의 정의로 구성됨

자료구조 구현전의 설계 단계

 

자료형

메모리 저장 할당을 위한 변수 선언

자료구조의 구현 단계(프로그래밍 언어를 이용한 선언)

 

 ADT Array객체 <i index, e Element>쌍 들의 집합

create, retrieve, store

 

배열연산의 구현

create 배열 생성

retrieve 배열 반환

store 배열 저장 

 

1차원 배열

한 줄짜리 배열을 의미, 하나의 인덱스로 구분

 

정의 

a[i]는 배열의 첫 번째 원소 A[0]이 저장된 메모리 주소인 a로부터 시작하며 A[0] ~ A[i-1]개까지 i개의 배열 a[]를 지나서 저장

따라서 A[]의 메모리 시작주소를 a라고 가정하면 A[i] 메모리 저장 주소는 [a + i * k]

 

배열의 확장

행렬의 표현

행렬을 컴퓨터에서 표현하기에는 2차우너 배열이 적합함

 

행우선 배열

1차월 배열을 여러 개 쌓아 놓은 것이 2차원 배열

행우선 할당

가로의 1차원 배열 단위로 메모리 영역을 우선 할당함

 

열우선 배열

1차월 배열을 어려개 세워 놓은것이 2차원 배열

 

C언어에서 2차원 배열 = 행 우선 순서 저장

 

희소행렬의 개념

원소값이 0인 원소가 그렇지 않은 원소보다 상대적으로 많음

 

희소행렬의 효율적 배열 표현

0인원소는 저장 하지 않고 0이 아닌 값만을 따로 모아서 저장

메모리 낭비 막고 효율성 향상

 

1. 배열은 인덱스와 원소값()의 쌍으로 구성된 집합으로서, 정의된 각 인덱스는 그 인덱스와 관련된 값을 갖습니다.
2. 배열의 순서는 메모리 공간에서 저장되는 ‘원소값의 물리적 순서’를 의미합니다.
3. 배열의 각 원소의 물리적인 위치(메모리 주소)의 순서가 배열의 인덱스의 순서(논리적인 순서)와 일치합니다.
4. 배열의 인덱스값을 이용해서 배열의 원소값에 접근하기 때문에 직접 접근(direct access)입니다.
5. 배열의 물리적인 저장 순서는 배열의 인덱스에 의해서 결정되며, 그 순서에 따라 메인 메모리에서의 저장 위치의 순서가 됩니다.
6. create(n)은 n개의 원소들을 저장할 수 있는 공백 배열(empty array)을 생성합니다. 배열을 생성할 때 n개의 원소들을 저장할 수 있는 공간은 만들어지지만 그 안에 채워진 원소값들이 아직은 없다는 것을 의미합니다.
7. 연산 retrieve(a,i)는 배열 a와 인덱스 i를 매개 변수로 전달받아 인덱스 i 위치에 대응되는 원소값 e가 있다면 원소값 e를 반환하고 그렇지 않은 경우 에러 메시지를 반환합니다.
8. 연산 store(a, i, e)는 배열 a와 인덱스 i, 원소값 e를 매개 변수로 전달받아 Index를 검사하여 i값이 유효할 경우 쌍이 되게 원소값을 i번째 인덱스에 저장하고 배열 a를 반환합니다.
9. 가장 기본적인 배열은 1차원 배열이며, 한줄짜리 배열을 의미하므로 인덱스는 하나입니다. 한줄짜리 배열은 메모리 영역도 한줄로 할당받습니다.
10. 2차원 배열의 행우선 저장방식은 하나의 행이 모두 연속적으로 메모리 영역을 할당받고, 다음 행이 메모리 영역을 연속적으로 할당받는 방식입니다.
11. 2차원 배열의 열우선 저장방식은 하나의 열이 모두 연속적으로 메모리 영역을 할당받고, 다음 열이 메모리 영역을 연속적으로 할당받는 방식입니다.
12. 원소값이 0인 원소가 그렇지 않은 원소보다 상대적으로 많은 행렬을 희소행렬(sparse matrix)이라 합니다.