자료 구조의 개념

자료 구조의 정의

  • 자료의 표현과 그것과 고나련된 연산
  • 일련의 자료들을 조직하고 구조화
  • 어떠한 자료 구조에서도 필요한 모든 연산들을 처리하는 것이 가능
  • 자료 구조에 따라 프로그램 실행시간이 달라진다.

자료 구조의 이용

  • 정렬 : 기억 장치 내의 자료를 일정한 순서에 의해 나열하는 것
  • 검색 : 기억장치 내의 자료를 찾는 것
  • 파일 편성 : 자료를 기억 매체에 저장할 때의 파일 구조
  • 인덱스 : 파일에서 특정 자료를 빠르게 찾기 위한 색인표

Stack

스택의 개념

  • LIFO = 후입 선출 방식

  • TOP

    • STACK으로 할당된 기억 공간에 가장 마지막으로 삽입된 자료가 기억된 위치를 가리키는 요소
    • STACK 포인터라고 하기도 함

  • BOTTOM

    • 스택의 가장 밑바닥

스택의 응용 분야

  • 부 프로그램 호출 시 복귀주소를 저장할 때
  • 함수 호출의 순서 제어
  • 인터럽트가 발생하여 복귀주소를 저장할 때
  • 후위 표기법으로 표현된 수식을 연산 할 때
  • 0 주소 지정방식 명령어의 자료 저장소
  • 재귀 프로그램의 순서 제어
  • 컴파일러를 이용한 언어 번역 시

QUE 와 DEQUE

QUE

  • 선형 리스트의 한쪽에서는 삽입, 다른 한쪽에는 삭제 작업이 이루어지도록 구성한 자료구조

  • FIFO 방식

  • 시작과 끝을 표시하는 두 개의 포인터가 있다.

  • Front 포인터

    • 가장 먼저 삽입 되는 자료의 기억 공간을 가리킴
    • 삭제 잡업을 할 때 사용

  • REAR 포인터

    • 가장 마지막에 삽입된 자료의 기억 장소를 가리키는 포인터
    • 삽입 작업을 할 때 사용

  • 큐 응용

    • 대기 행렬 처리
    • 운영체제의 작업 스케줄링

DEQUE

  • 삽입과 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료 구조

  • stack과 queue의 장점만 따서 구성한것이다.

  • 입력 제한 데크 : scroll

  • 출력 제한 데크 : shelf

트리(tree)

트리의 정의

  • 트리는 정점(node)와 선분(branch)를 이용하여 사이클을 이루지 않도록 구성한 graph의 특수한 형태이다

트리 관련 용어

  • node : 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지를 합친 것
  • root node : 트리 맨 위에 있는 노드
  • degree : 각 노드에 뻗어나온 가지의 수
  • 단말 노드(termianl node) : 자식이 없는 노드

이진 트리의 운행법

트리의 운행범

  • Pre order : root - left -right
  • In order : left - order - right
  • Post order : left - right - root

수식의 표기법

  • 전위 표기
  • 후위 표기
  • 중위 표기 : 우린 보통 중위 표기

스레드 이진 트리

  • 이진트리에서 발생하는 null 링크를 트리 운행에 필요한 다른 노드의 포인터로 사용하도록 고안된 트리

  • 어떻게 사용하는가?

    • 어떤 노드의 왼쪽이 nil일 경우, 그 노드 직전에 검사된 노드를 가리키는 포인터로 사용
    • 어떤 노드의 오른쪽이 nil일 경우, 그 노드의 직후에 검사될 노드를 가리키는 포인터로 사용

  • 해당 노드의 직전, 직후 노드는 트리의 운행법에 따라 방문한 노드의 순서대로 결정한다.

그래프

그래프의 정의

  • 그래프 G는 정점과 간선의 두 집합으로 이루어진다.
  • 간선의 방향성 유무에 따라 방향 그래프와 무방향 그래프로 구분된다.
  • tree는 사이클이 없는 그래프이다.

용어 정리

  • Loop : 한 정점에서 그 자신에 이어지는 간선 loop
  • 차수(degree)
    • 무방향 그래프 : 한 정점에 여결된 간선의 수
    • 방향 그래프 : 진입 차수 + 진출 차수
  • 경로
    • 경로 길이 : 경로 상에 있는 간선들의 수
    • 단순 경로 : 같은 간선을 두번 이상 지나지 않는 경로
    • 기본 경로 : 같은 정점을 두번 이상 지나지 않는 경로
    • 사이클 : 같은 정점에서 시작과 끝이 이루어지는 경로
    • 최대 사이클 : 사이클을 이루는 경로 중 최대 경로 길이

내부 정렬

삽입 정렬

  • 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬
  • 평균 최악 모두 수행 시간 복잡도는 O(n^2)

쉘 정렬

  • 삽입 정렬을 확장한 개념
  • 입력 파일이 부분적으로 정렬되어 있는 경우에 유리
  • 평균 수행 복잡도는 n^1.5, 최악의 수행 시간 복잡도는 n^2

선택 정렬

  • n개의 레코드 중에서 최소값을 찾아 첫 번째 레코드 위치에 두고 나머지 (n-1)개중에 앞의 행위를 반복함
  • 평균과 최악 모두 수행시간 복잡도는 n^2

버블 정렬

  • 주어진 파일에서 인접한 두개의 레코드 키값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식
  • 계속 정렬 여부를 플래그 비트로 결정
  • 평균과 최악 모두 수행 시간 복잡도는 n^2

퀵 정렬

  • 위치에는 관계없이 임의의 키를 분할 원소로 사용할 수 있다.
  • 정렬 방식 중 가장 빠른 방식이다
  • 분할과 정복을 통해 자료를 정렬한다.
  • 평균 수행 시간 복잡도는 nlog2n이고 최악의 수행시간 복잡도는 n^2

힙 정렬

  • 전이진 트리를 이용한 정렬 방식이다.
  • 평균과 최악 모두 시간 복잡도는 nlog2n이다.

2-way 합병 정렬

  • 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식이다.
  • 평균과 최악 모두 시간 복잡도는 nlog2n

기수 정렬

  • 기수 정렬은 queue를 이용하여 자릿수별로 정렬하는 방식이다.
  • 평균과 최악 모두 시간 복잡도는 dn이다.

검색 - 해싱

해싱의 개요

  • DAM(직접 접근) 파일을 구성할 때 사용되며 접근 속도는 빠르나 기억공간이 많이 요구된다.
  • 다른 방식에 비해 검색 속도가 가장 빠르다
  • 삽입 삭제 작업의 빈도가 많을 때 유리한 방식이다.
  • 키 - 주소 변환 방법이라고도 한다.

해싱 관련 용어

  • Hash table : 레코드를 한 개 이상 보관할 수 있는 bucket들로 구성된 기억공간, 보조기억장치, 주기억장치에 구성할 수 있다.
  • 버킷 : 하나의 주소를 갖는 파일의 한 구역을 의미, 버킷의 크기는 같은 주소에 포함 될 수 있는 레코드의 수를 의미
  • slot : 한 개의 레코드를 저장할 수 있는 공간으로 n개의 슬롯이 모여 하나의 버킷 형성
  • Collision(충돌 현상) : 서로 다른 두 개 이상의 레코드가 같은 주소를 갖는 현상
  • Synonym : 충돌로 인해 같은 home address를 갖는 레코드들의 집합이다
  • Overflow : 계산된 home address의 bucket 내에 저장할 기억공간이 없는 상태

해싱 함수

  • K : KEY ,Q = Prime

  • 제산법

    • 레코드 키를 해시표의 크기보다 큰 수 중에서 가장 작은 소수로 나눈 나머지를 홈 주소로 삼는 방식
    • h(K) = K mod Q

  • 제곱법

    • 레코드 키 값을 제곱한 후 그 중간 부분의 값을 홈 주소로 삼는 방식

  • 폴딩법

    • 레코드 키 값을 여러 부분으로 나눈 후 각 부분의 값을 더하거나 XOR한 값을 홈 주소로 삼는 방식이다.

  • 기수 변환법

    • 키 숫자의 진수를 다른 진수로 변환시켜 주소 크기를 초과한 높은 자릴수는 절단하고 이를 다시 주소범위에 맞게 조정하는 방법이다.

  • 대수적 코딩

    • 키 값을 이루고 있는 각 자리의 비트 수를 한 다항식의 계수로 간주 하고 이 다항식을 해시표의 크기에 의해 정의된 다항식으로 나누어 얻은 나머지 다항식의 계수를 홈주소로 삼는 방식이다.

  • 계수 분석법

    • 계수 분석법은 키 값을 이루는 숫자의 분포를 분석하여 비교적 고른 자리를 필요한만큼 택해서 홈 주소로 삼는 방식이다.

Overflow 해결 방법

  • 개방 주소법(open addressing)
    • 선형 방법이라고도 하는데, collision이 발생했을 때 순차적으로 다음 빈 버킷을 찾아 저장하는 방법
  • 폐쇄 주소법(close addressing)
    • Overflow된 레코드들을 별도의 overflow 영역에 저장하고 chain으로 홈버킷에 연결
    • direct chaining
      • 해시표 내의 빈 자리 에 overflow 레코드를 보관
    • indirect chaining
      • 해시표와는 별도의 기억 공간에 overflow 레코드를 보관한다.
  • 재해싱
    • collision이 발생하면 새로운 해싱 함수로 새로운 홈 주소를 구하는 방식

파일 편성

순차 파일 (sequential file) = 순서 파일

  • 입력되는 데이터들을 논리적 순서에 따라 물리적 연속 공간에 순차적으로 기록하는 방식

    • 순차접근이 가능한 자기테이프에서 사용한다.
    • 변동사항이 크지 않고 기간별로 일괄 처리를 주로 하는 경우에 적합

  • 순차 파일의 장점

    • 기록 밀도가 높아 기억공간을 효율적으로 사용
    • 매체 변환이 쉬워 어떠한 매체에도 적용할 수 있다.
    • 레코드가 키 순서대로 편성되어 취급이 용이하다
    • 레코드를 기록할 때 사용한 키 순서대로 레코드를 처리하는 경우 다른 편성법 보다 처리 속도가 빠르다

  • 순차 파일의 단점

    • 파일에 새로운 레코드를 삽입,삭제하는 경우 파일 재구성을 위해 전체를 복사해야하므로 시간이 많이 소요
    • 데이터 검색시 처음부터 순차적으로 검색하기 때문에 검색 효율이 낮고, 시간 및 응답 시간이 느림

색인 순차 파일(indexed sequential file)

  • 순차 처리와 랜덤 처리가 모두 가능한 레코드들을 키값 순으로 정렬시켜 기록하고, 레코드의 키 항목만을 모은 색인을 구성하여 편성하는 방식
    • 색인을 이용한 순차적인 접근 방법을 제공하여 ISAM(index sequential access method)이라고 함
    • 레코드를 참조할 때 색인을 탐색한 후 색인이 가리키는 포인터(주소)를 사용하여 직접 참조할 수 있다.
    • 일반적으로 자기 디스크에 많이 사용되며, 자기 테이프에서는 사용할 수 없다.

색인 순차 파일의 구성

  • 색인 순차 파일은 기본구역, 색인 구역, 오버플로 구역으로 구성

  • 기본 구역

    • 실제 레코드들을 기록하는 부분으로 각 레코드는 키 값 순으로 저장

  • 색인 구역

    • 기본 구역에 있는 레코드들의 위치를 찾아가는 색인이 기록되는 부분으로 트랙 색인 구역, 실린더 색인 구역, 마스터 색인 구역이 있다.
    색인 구역 기능
    트랙 색인 구역 기본 구역의 한 트랙 상에 기록되어 있는 데이터 레코드 중의 최대 키 값과 주소가 기록되는 색인으로, 한 실린더당 하나씩 만들어진다.
    처리할 레코드가 실제로 어느 트랙에 기록되어 있는지 판별할 수 있게 함
    실린더 색인 구역 각 트랙 색인의 최대키 값과 해당 레코드가 기록된 실린더의 정보가 기록되는 색인, 한 파일당 하나씩 만들어진다.
    마스터 색인 구역 실린더 색인 구역의 정보가 많을 경우 그것을 일정한 크기의 블록으로 구성하는데, 이때 해당 레코드가 어느 실린더 색인 구역에 기록되어 있는지를 기록하는 색인

  • 오버플로 구역

    • 기본 구역에 빈 공간이 없어 새 레코드가 삽입 불가할 때 대비하여 예비적으로 확보해둔 부분
    오버플로 구역 기능
    실린더 오버플로 구역 각 실린더마다 만들어지는 오버플로 구역,해당 실린더의 오버플로 내용을 기록
    독립 오버플로 구역 실린더 오버플로 구역에서 데이터를 더이상 기록 할 수 없을 때를 대비하는 구역

  • 색인 순차 파일의 장점

    • 융통성
    • 효율적인 검색 가능, 레코드의 삽입 삭제 갱신이 용이
    • 레코드를 추가 및 삽입하는 경우, 파일 전체를 복사할 필요가 없음

  • 색인 순차 파일의 단점

    • 색인 구역과 오버플로 구역을 구성하기 위한 추가 기억공간이 필요
    • 파일 사용 중 오버플로 레코드가 많아지면 파일을 재편성해야한다.
    • 파일이 정렬되어 있어야 하므로 추가 삭제가 많으면 효율이 떨어짐
    • 색인을 이용하여 액세스 하기 때문에 액세스 시간이 랜덤 편성 파일보다 느리다.

VSAM 파일

  • VSAM : Virtual storage access method ,동적 인덱스 방법을 이용한 색인 순차 파일
  • 제어 구간, 제어 구역, 순차 세트 , 인덱스 세트로 구성
이름 기능
제어 구간 데이터 레코드가 저장되는 부분
제어 구역 몇 개의 제어 구간을 모아 놓은 것
순차 세트 제어 구역에 대한 인덱스를 저장한 것
안덱스 세트 순차 세트의 상위 인덱스
  • 기본 구역과 오버플로 구역을 구분하지 않음
  • 레코드를 삭제하면 그 공간을 재사용할 수 있다.
  • 제어 구간에 가변 길이 레코드를 쉽게 수용할 수 있다.

직접 파일(direct file, random file)

  • DAM파일이라고도 불림

  • 레코드에 특정 기준으로 키 할당, 해시 함수를 이용하여 키에 대한 보조기억장치의 물리적 상대 레코드 주소를 계싼한 후 해당하는 주소에 레코드를 저장

  • 레코드는 해시 함수에 의해 계산된 물리적 주소를 통해 접근

  • 임의 접근이 가능한 자기 디스크나 자기드럼을 사용

  • 직접 파일의 장점

    • 직접 접근 기억장치(DASD)의 물리적 주소를 통하여 파일의 각 레코드에 직접 접근하거나 기록할 수 있으며 접근 및 기록의 순서에는 제약이 없다.
    • 접근 시간이 빠르고 레코드의 삽입, 삭제, 갱신이 용이
    • 어떤 레코드라도 평균 접근 시간 내에 검색이 가능하다.

  • 직접 파일의 단점

    • 레코드의 주소 변환과정(HASH)이 필요하며 이 과정으로 시간이 소요 됨
    • 기억 공간의 효율이 저하될 수 있음
    • 기억 장치의 물리적 구조에 대한 지식 필요, 프로그래밍 작업이 복잡
    • 충돌이 발생할 염려가 있으므로, 이를 위한 기억공간의 확보가 필요

역 파일

  • 특정 항목을 여러 개의 색인으로 만들어 항목별 특성에 맞게 작업할수 있도록 한 파일로, 다중 키 파일에 속한다.

    • 하나 또는 몇 개의 색인값을 결합하여 레코드의 주소를 결정할 수 있다.
    • 각 응용마다 적합한 색인을 별도로 구현 할 수 있다.
    • 새로운 레코드를 파일 중간에 삽입하기 쉽고, 검색 속도가 빠르다
    • 데이터 파일에 접근하지 않아 질의 응답시간이 줄어들고, 처리가 비교적 쉽다.
    • 질의를 만족하는 레코드 검색 시 한 번씩만 접근하면 된다.
    • 색인의 각 항목들의 길이가 가변적이다.

다중 리스트 파일

  • 다중 키 파일의 한 종류로 각 키에 대하여 색인을 만든 다음 각 데이터 레코드들 간에 다 중 리스틀 구축하여 구성한 파일이다.
    • 색인은 동일한 키 값을 갖는 데이터 레코드 중 하나의 레코드에 대한 포인터만을 갖고 후속데이터는 포인터로 추적하도록함
    • 색인의 각 항목들의 길이가 고정적이므로 관리가 용이하며 수정 삭제 전체 검색이 효율적

다중 링 파일

  • 다중 링 파일은 같은 특성을 가진 레코드들을 일련의 포인터로 연결하여 구성한 것이다.
  • 같은 항목값을 가진 레코드들을 한꺼번에 처리하는 데 효과적이다.
  • 기억 장소가 절약되고 자료의 중복성을 배제할 수 있다.
  • 레코드 형식이 다른 경우에도 처리가 가능하다.