[자료구조] 배열 (2차정리)

배열의 정의

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

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

• 원소의 메모리 공간(메인 메모리, DDR)의 물리적인 위치를 ‘순서’적으로 결정하는 특징
  
• 배열의 순서는 메모리 공간에서 저장되는 ‘원소값의 물리적 순서’
  
• 인덱스와 원소값<index, value>의 쌍으로 구성된 집합
  
• 원소들이 모두 같은 자료형과 같은 크기의 기억 공간을 가짐
  

• 배열의 인덱스값을 이용해서 원소값에 접근하기 때문에 직접 접근이 가능함
  
  

• 배열의 인덱스 값 : 추상화된 값 = 컴퓨터의 내부구조나 메모리 주소와 무관하게 개발자에게 개념적으로 정의 됨
  
• 메모리 주소값은 실제 메모리의 물리적인 위치 값
  
• 배열의 (추상화된) 인덱스값은 프로그래밍 언어와 컴파일 과정을 통해 메모리 주소값과 연결됨
  
  

배열의 추상 자료형

• 추상자료형
  
  • 객체 및 관련된 연산의 정의로 구성됨
    
  • 자료구조 구현전의 설계 단계
    
    
• 자료형
  
  • 메모리 저장 할당을 위한 변수 선언
    
  • 자료구조의 구현 단계 (프로그래밍 언어를 이용한 선언)
    
    

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차원 배열
  
  • 세로의 1차원 배열 단위로 메모리 영역을 우선 할당함
    
    
• C언어에서의 2차원 배열 = 행 우선 순서 저장
  
  

희소행렬의 표현

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

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

  • 0인 원소는 저장하지 않고 0이 아닌 값만을 따로 모아서 저장
    
  • 메모리 낭비를 막고 효율성 향상