자료 구조론 4주차 - 레코드와 배열 그리고 행렬

4주차

레코드

정의

• 서로 연관되었으면서, 다른 데이터 타입 및 크기를 가지는 여러 필드로 구성된 구조
  • 예시) 출석부
• 필드: 각각 서로 다른 데이터 형태와 크기를 가짐

선언

• 구조체를 이용함

  struct Structure-Name{
      data-type member 1;
      		.
               .
               .
      data-type member n;
  }
  

필드의 참조

• 레코드에 속한 특정 원소를 참조하기 위해서 사용함
• 필드 참조 연산자인 .를 사용함
  • 예시) person.age, car.number

레코드 배열

• 배열의 각 요소가 레코드 구조인 배열

중첩 레코드

• 레코드 내부의 필드가 다른 레코드인 경우
• 구조체 문 내부에 다른 구조체가 존재

배열

정의

• 동일한 데이터형을 가지는 원소들이 2차원 장방형 구조에 놓인 구조체

• 인덱스와 값의 쌍으로 구성됨

• 유한성을 가짐

1차원 배열

특징

• Vector
• 2차원 배열의 행이나 열이 1인 경우

표현 방법

• 배열의 범위(하한, 상한)을 명시하여 선언

특정 원소의 주소 산출

가정

• 배열: A(L:U)
• 각 원소가 K개의 메모리의 크기를 차지함
• 배열의 시작 주소: B(상한 인덱스), L(하한 인덱스)

원소의 개수

• U-L+1

배열 전체의 크기

• k x (U-L+1)

인덱스가 i인 A(i)의 주소

• B + K(i - L)

다차원 배열

특징

• m개의 Vector로 구성되어 있으며, 각 Vector의 길이는 n임
• 논리적으로 행과 열을 포함하는 직사각형
• 행과 열을 Index로 하여 각 원소를 표현함

2차원 배열의 물리적 표현 방법

행 우선 방법

• C, COBOL, PASCAL

  

열 우선 방법

• Fortran

  

행렬

정의

• 수들의 배열

• 표기 방법:

  • m행 n열의 배열: mxn

  • i번째 행, j번째 열 표현:

    

정의

정방 행렬

• 행과 열의 개수가 같은 행렬

표기방법

• nxn

대각 행렬

• 주 대각 이외의 원소가 모두 0인 행렬
• 주 대각 행렬 원소: A11, A22, …, Ann

전치 행렬

• 행과 열의 원소를 서로 바꾼 행렬

• 표현 방법:

  

희소 행렬

정의

• 행렬의 원소 중 0의 값을 가지는 값이 비교적 많은 행렬

희소 행렬의 효율적 표현 방법

방법

• 첫번째 칸에는 전체 행렬의 크기, 0이 아닌 값의 개수 순서대로 적는다

• 두번째 칸부터는 0이 아닌 원소의 행과 열, 값의 순서대로 적는다

• 예시

  

장점

• 메모리 절약
• 빠른 검색

단점

• 수정이 복잡함