1. 자료구조의 개요
1-1. 자료와 정보와의 관계
자료(Data)
- 현실 세계로부터 단순한 관찰, 측정 등을 통하여 수집한 사실(facts)들 또는 값(values)
- 즉, 숫자로 표현되는 수치, 스트링(string)등의 정리되지 않은 자료를 의미
정보(infomation)
- 어떤 기준에 의해 처리되고 기록된 자료라는 의미
- 문자나 숫자 또는 이의 조합으로 이루어진 기호 등의 컴퓨터가 처리 하는 값
- 어떤 상황에 관한 의사결정(decision making)을 할 수 있게 하는 지식(knowledge)으로서 자료의 유효한 해석이나 자료 상호간의
관계를 말함
- 자료를 처리.가공한 결과
알고리즘
|
자료 -----------> 처리기 ------------> 정보
자료의 입력 특정한 상황에 필요한 정보의 산출
==================================================================================
자료구조의 정의
- 컴퓨터의 기억 장치 내에 자료의 표현 방법, 저장 방식, 한 집단을 구성하는 자료 항목(data item)간의 관계를 파악하여
여러 작업을 수행하기 위한 알고리즘(algorithm)을 연구하는 이론
자료구조를 선택할 때 프로그래머가 처하게 되는 문제점
- 처리 시간이 약간 늦더라도 적은 양의 기억 공간을 차지하는 프로그램을 작성할 것인가?
- 많은 양의 기억 공간을 차지하기는 하지만 처리 결과가 빠르게 나오는 프로그램을 작성할 것인가?
자료구조를 선택할 때 고려사항
- 포함된 자료의 양
- 자료의 사용빈도 및 방법
- 자료의 성질(자료가 동적인가, 정적인가)
- 구현에 필요한 기억 장소의 양
- 접근 시간(access time : 기억장치에서 데이터를 저장하거나 꺼내는데 걸리는 시간)
- 프로그램 작성의 용이성
자료구조의 정의
- 그래프의 정의
- 정점(vertex)이라고 불리는 원소들의 집합 V와 간선(edges)이라 불리는 V의 원소들의 비순서화된 쌍들의 집합 E로 구성
- V는 공집합이 아닌 정점들의 유한 집합
- E는 간선, 즉 연결선의 집합
- V(G)는 그래프의 정점의 집합
- E(G)는 그래프의 간선의 집합
탐색이란?
레코드(record)의 집합에서 특정한 레코드를 찾아내는 작업
- 탐색의 종류
- 내부 탐색(internal search)
- 주 기억 공간 내에 저장된 파일로부터 필요한 자료를 찾아내는 것
- 외부 탐색(external search)
- 보조 기억 공간 내에 저장된 파일로부터 필요한 자료를 찾아내는 것
- 탐색의 방법
- 비교 탐색 방법(Comparison search method)
- 파일 내의 레코드의 키를 비교하여 특정한 자료를 찾는 방법
1. 순차탐색(Linear Search)
2. 제어탐색(control search) - a. 이진탐색 b. 피보나치 탐색 c. 보간 탐색
3. 블록탐색
4. 이진 트리 탐색
- 직접 탐색 방법
- 주어진 키 자체의 계수적 성질을 이용하여 파일로부터 특정한 자료를 찾는 방법
1. 해싱 방법
정렬이란?
- 일련의 자료들을 필요에 따라 자료 중에 포함된 몇 가지 항목을 우선 순서대로 지정하면 그 순서에 따라 모든 자료를
배열하는 방법
- 각 레코드의 특정한 항목을 정렬키(key)로 정하고, 키 값에 따라 오름차순, 내림차순으로 파일의 레코드를 재배열하는 것
정렬장소에 따른 구분
- 내부 정렬(internal sort)
- 파일의 크기, 처리해야 할 자료의 양이 적을 경우 자료 이동 속도가 빠른 주 기억장치 내에 로드하여 재배열을 완료시키는 것
- 외부 정렬(external sort)
- 정렬하는 파일의 크기가 주기억 장치의 크기만으로 감당하기 어려울 때 파일 전체를 기억 장소에 로드 할 수 없기 때문에 보조
기억 장치(auxiliary memory)를 이용하여 정렬하는 것
처리 순서에 따른 구분
- 오름차순 정렬(ascending sort)
- 지정된 정렬키를 작은 것에서부터 큰 것 순서로 정렬하는 것
- 사전식 정렬
- 내림차순 정렬(descending sort)
- 지정된 정렬키를 큰 것에서부터 작은 순서로 정렬하는 것
정렬 방식에 따른 구분(정렬 알고리즘에 따른 구분 방법)
- 비교식 정렬
- 비교하고자 하는 각 레코드의 키 값들을 한 번에 두 개씩 비교, 교환하여 정렬하는 방법
- insertion sort, bubble sort, shell sort, quick sort, 2-way, merge sort, heap sort
- 분산식 정렬(distributive sort)
- 레코드의 키 값을 기준으로 전체 레코드 집합을 다수의 부분 집합으로 분해하는데, 한 부분 집합에 속한 킷값은 다른 부분 집합에 속한
레코드의 키값과 다르게 만들어진다. 즉 내용들을 한 비트씩 검토함으로써 정렬하는 방법의 키값과 다르게 만든다. 즉, 내용들을 한
비트씩 검토함으로써 정렬하는 방법
- radix sort, radix exchange sort(=binary sort)
- 주소 계산 정렬(address calculation sort)
- 비교하고자 하는 키 값을 주소로 변환하여 정렬하는 방식
정렬방식 분류
- 삽입법 : insertion sort, shell sort
- 교환법 : bubble sort, quick sort, selection sort
- 선택법 : heap sort
- 병합법 : 2-way merge sort
- 분배법 : radix sort, radix exchange sort
정렬 알고리즘을 선택할 때 고려해야 할 사항
- 사용하는 컴퓨터의 특성
- 정렬할 데이터 양
- 초기 데이터의 배열 상태
- 키 값들의 분포 상태
- 소요 공간 및 작업 시간
문자열(string)이란?
- 서로 인접합 기억 장소에 존재하는 문자들의 집합
종류
- 널 스트링(null string)
- 한 개의 문자도 갖지 않는 길이가 0인 스트링
- 공백 스트링(blank string)
- 길이가 0이 아닌 공백 문자(blank character)를 갖는 스트링
- 서브 스트링(substring)
- 스트링을 구성하는 연속적인 부분의 일부를 뜻하는 스트링
리스트(List)란?
- 선형리스트(linear list)
- 기억장소에 각 원소들이 연속적으로 나타나며, 리스트 시작으로부터 상대적으로 위치를 계산할 수 있으므로
임의의 노드에 접근 가능한 구조
- 연결리스트(linked list)
- 리스트 내의 모든 노드가 다음 노드의 위치를 가리키기 위한 포인터 소유
- 노드의 구성
연결리스트의 장.단점
- 장점
- 노드의 삽입, 삭제가 용이
- 연속적인 기억공간이 없어도 저장 가능
- 단점
- 링크 필드를 위한 추가 공간이 필요
- 알고리즘 구현이 복잡
- 노드 검색시 무한 루프에 빠질 수 있다.
트리란?
- 트리의 정의
- 트리는 자료의 항목(node)들이 가지(edge)로 연결될 수 있게 자료가 조직되는 것
- 다음 조건을 만족하는 하나 이상의 노드(node)들로 구성된 유한 집합 T를 의미
- 조건1. T의 원소 중 들어오는 가지가 없는 단 하나의 노드 즉, 근 노드(root node)라 불리는 특정한 1개의 노드가 존재
- 조건2. 근 노드를 제외한 나무지 노드들은 서로 분리된 부분 집합 T1, T2.....Tn으로 나누어 질 수 있으며 T1, T2, T3...은
각각 트리가 될 수 있으며, 이것을 특별히 서브트리(subtree)라 한다.
- 각 노드들 간에 순환(cycle)을 허용하지 않는다.
파일(File)이란
- 어떤 목적을 위해서 수집한 데이터의 조직적인 그룹
- 수집한 데이터를 체계적으로 정리한 것
ex) 회사나 기관에서 사용하는 임금지불 전표나 장부
- 인사 파일 : 종업원의 인사 기록을 모은 파일
- 재고 파일 : 상품의 재고 현황을 정리한 파일