- 선형구조
: 데이터가 연속적으로 연결되어 있는 모양으로 구성하는 방법
: 포인터 등을 사용하여 자료를 연결하면 그 결과가 자료에 일직선, 하나의 원상에 표시
1) 리스트
1. 선형 리스트(Linear List): 배열과 같이 연속되는 기억장소에 저장되는 리스트 (배열)
: 가장 간단한 자료구조
: 접근 속도가 빠르다
: 중간에 자료를 삽입하기 위해서는 연속된 빈 공간이 있어야 한다
: 삽입 삭제시 자료의 이동이 필요하기 때문에 작업이 번거롭다
2. 연결 리스트(Linked List)
: 자료들을 연속적으로 배열시키지 않고 임의의 기억공간에 기억시키는 리스트
: 노드의 삽입, 삭제가 용이하다, 그러나 검색은 느리다
: 기억공간이 연속적으로 놓여 있지 않아도 저장이 가능
: 접근 속도가 느리다
: 트리를 표현할 때 가장 적합한 자료구조
: 연결을 해주는 포인터를 위한 추가 공간이 필요
: 중간 노드 연결이 끊어지면 그 다음 노드 찾기 힘듬
2) 스택(Stack) <LIFO: Last in First Out>
: 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료구조, 후입선출방식
- Stack 응용 분야
: 부 프로그램 호출 시 복귀 주소를 저장할 때
: 함수 호출의 순서 제어
: 인터럽트가 발생하여 복귀주소를 저장할 때
: 후기 표기법으로 표현된 수식을 연산할 때
: 0 주소지정방식 명령어의 자료 저장소
: 재귀 프로그램의 순서 제어
: 컴파일러를 이용한 언어 변역 시
3) 큐(Queue) <FIFO: First in First Out>
: 한쪽에서는 삽입이, 다른 한쪽에서는 삭제가 이루어지는 자료 구조, 선입선출방식
- 큐의 응용분야
: 운영체제의 작업 스케쥴링
: 순서를 기다리는 대기 행렬
4) 데크(Deque)
: 삽입과 삭제가 리스트의 양쪽에서 이루어지는 구조
- 비선형구조
- 트리(Tree)
: 정점(Node, 노드)와 선을 이용하여 사이클을 이루지 않도록 구성한 그래프 형태
: 노드(Node) - 트리의 기본 구성 요소 (A,B,C,D....M)
: 근 노드(Root Node) - 맨 위에 있는 노드 (A)
: 디그리(Degree) - 각 노드에서 뻗어나온 가지의 수 (A=3, B=2, C=1)
: 단말 노드(Terminal Node) - 자식이 하나도 없는 노드 (F,G,I,J,K,L,M)
: 비단말 노드(Non-Terminal Node) - 자식이 하나라도 있는 노드
: 조상 노드(Ancestors Node) - 한 노드에서 근 노드에 이르는 경로상에 있는 노드
(M - H, D, A)
: 자식 노드(Children Node) - 어떤 노드에 연결된 다음 레벨의 노드들 ( B - E, F)
: 부모 노드(Parent Node) - 어떤 노드에 연결된 이전 레벨의 노드( H - D)
: Level - 노드의 층 ( H - Level 3)
: 깊이(Depth, Height) - 트리에서 노드가 가질 수 있는 최대 레벨 (4)
: 트리의 디그리 - 노드들 중 디그리가 가장 많은 수 (위의 트리의 디그리는 3)
- 이진트리
: 차수가 2이하인 노드들로 구성된 트리
: 이진트리의 레벨 i에서 최대 노드의 수는 2 i+ 1 승
- 트리의 운행법
1. Preorder 운행: ROOT -> Left -> Right 순으로 운행
2. Inorder 운행: Left -> ROOT -> Right 순으로 운행
3. Postorder 운행: Left -> Right -> Root 순으로 운행
- 수식 표기법
1. 전위 표기법(PreFix): 연산자 -> Left -> Right
2. 중위 표기법(InFix): Left -> 연산자 -> Right (일반적인 연산방법)
3. 후위 표기법(PostFix): Left -> Right -> 연산자
: prefix 를 infix로 바꿀때 중간부터 계산
: 이진 트리에서 발생하는 널 링크를 트리 운행에 필요한 다른 노드의 포인터로 사용하도록 고안된 트리
- 그래프
: 정점과 간선의 두 집합으로 이루어짐
: 트리는 사이클이 없는 그래프
: 그래프는 사이클이 있는데 이는 같은 정점에서 시작과 끝이 이어지는 경로
2. 정렬(Sort)
: 특정 항목을 기준으로 오름차순 또는 내림차순으로 재배열하는 작업
: 오름차순(asc) - 작은 것 부터 큰 것으로 가는 순서
: 내림차순(desc) - 큰 것 부터 작은 것으로 가는 순서
- 내부정렬
: 주 기억장치에 기억시켜서 정렬하는 방식(소량의 데이터)
1. 삽입 정렬(Insertion Sort)
: 가장 간단한 정렬방식
: 두번째 키값과 첫번째 키값을 비교하여 교환 (조건에 해당하지 않으면 패스)
2. 선택 정렬(Selection Sort)
: 첫번째 키 값과 나머지를 비교하여 정렬
: 작은 값이 앞으로 나오는 정렬 방식
3. 버블 정렬(Bubble Sort)
: 인접한 두 개의 레코드 키 값을 비교하여 정렬(첫번째가 쭈루룩 뒤로 비교)
: 큰 값이 뒤로 밀리는 정렬방식
-쉘 정렬: 삽입 정렬을 확장한 개념(서브파일 구성)
-퀵 정렬: 정렬 방식 중 가장 빠른 방식(하나의 파일을 부분적으로 나누어 가면서 정렬)
-힙 정렬: 전이진 트리를 이용한 정렬 방식(자식, 부모노드 비교하여 큰 값을 올림)
-2way병합 정렬: 정렬된 2개의 파일을 한개의 파일로 병합
-기수 정렬: 큐를 이용하여 자릿수 별로 정렬, 버킷 정렬이라고도 함
- 외부정렬
: 보조 기억장치에 기억시켜서 정렬하는 방식(대량의 데이터)
- 정렬 알고리즘 선택 시 고려사항
: 데이터의 양
: 초기 데이터의 배열상태
: 키 값들의 분포 상태
: 소요공간 및 작업시간
: 컴퓨터 시스템의 특성
- 종류
: 밸런스, 케스케이드, 폴리파즈, 오실레이팅 병합정렬
3. 검색
1) 선형 검색(Linear Search)
: 순서화 되지 않은 파일에서 순차적으로 검색하는 방법
: 순차 검색(Sequential Search)
: 프로그램 작성이 가장 쉽다
2) 제어 검색(Control Search)
: 반드시 순서화된 파일이어야 검색 가능
: 이분 검색 - 전체 파일을 두개의 서브파일로 분리해 가면서 검색
: 피보나치 검색 - 피보나치 수열에 따라 비교할 대상을 선정하여 검색
: 보간 검색 - 찾으려는 레코드가 있음직한 부분의 키를 택하여 검색
: 블록 검색, 이진 트리 검색
3) 해싱(Hashing)
: 해싱 테이블이라는 기억공간을 할당하고, 해시 함수를 이용하여 레코드 키에 대한 해시 테이블 내의 Home Address를 계산한 후 주어진 레코드를 해당 기억장소에 저장하거나 검색작업을 수행하는 방식
: 접근속도는 빠르나 기억공간이 많이 요구
: 다른 방식에 비해 검색 속도가 빠름
: 삭제, 삭입 작업으 빈도가 많을 때 유리
: 키-주소 변환 방법
1. 제산법: 레코드 키를 해시 테이블 크기보다 큰 수중에서 가장 작은 소수로 나눈 나머지
2. 제곱법: 레코드의 키값을 제곱한후 그 중간 부분의 값을 홈 주소로 삼는 방식
3. 폴딩법: 레코드 키 값을 여러 부분으로 나눈 후 각 부분의 값을 더하거는 xor값을 홈주소
4. 기수 변환법: 키를 다른 진수로 변환시켜 주소 크기를 초과한 높은 자릿수를 절단, 조정
5. 대수적 코딩법: 키의 각 자리의 비트 수를 다항식의 계수로 간주, 다항식으로 나눈 나머지
6. 계수 분석법: 키 값을 이루는 숫자의 분포를 분석하여 홈 주소를 삼는 방식
7. 무작위법: 난수를 발생시켜 홈 주소로 삼는 방식
- Hashing 시 Overflow 해결방법
: Collision이 발생했을 때 그 버킷에 저장할 Slot이 없다면 Overflow가 발생.
1. 개방 주소법(Open Addressing)
: collision이 발생했을 때, 순차적으로 다음 빈 버킷을 찾아 저장하는 방법
2. 폐쇄 주소법(Close Addressing)
: 별도의 Overflow 영역에 저장하고 Chain으로 홈 버킷에 연결
: Direct Chaining - 해시표 내의 빈자리에 Overflow 레코드를 보관
: Indirect Chaining - 해시표와는 별도의 기억공간에 Overflow 레코드를 보관
3. 재해싱(Rehashing)
: collision이 발생하면 새로운 해싱 함수로 홈 주소를 구하는 방식
4. 인덱스
: 레코드를 빠르게 접근하기 위해서 구성
: 데이터가 저장된 물리적 구조와 밀접한 관계가 있다
: 레코드에 대한 액세스를 빠르게 수행할 수 있다
: 레코드의 삽입과 삭제가 수시로 일어나는 경우에는 인덱스의 개수를 최소화가 효율적
- m-원 검색 트리(m-Way Search Tree)
: 이진 검색 트리에서는 한 노드가 한 개의 키와 두개의 subtree를 갖는 반면 m-원 검색트리는 한 노드가 최대 m-1 개의 키와 m개의 subtree를 갖도록 구성
: 키 값의 일부분이 동일한 문자열이나 숫자로 구성된 자료를 표현하는 데 효율적이다
: 삽입, 삭제 시 트리 균형을 유지하기 위해서 연산이 복잡해진다
- B-트리
: 가장 많이 사용되는 균형된 m원 검색트리
: Root와 Leaf(단말)를 제외한 모든 노드는 최소 m/2, 최대 m개의 Subtree를 갖는다
: Root는 Leaf가 아닌 이상 적어도 두개의 Subtree를 가진다
: 모든 Leaf는 같은 Level에 있다
: Leaf가 아닌 노드의 키 값 수는 그 노드의 Subtree 수 보다 한 개 적으며, 각 Leaf Node수는 최소 m/2-1개 , 최대 m-1개의 키 값들을 갖는다
: 한 노드 안에 있는 키 값들은 오름차순을 유지해야한다
: 탐색, 추가, 삭제는 Root로 부터 시작한다
: 삽입 삭제를 하여도 데이터 구조의 균형을 유지해야한다
- B+트리
: B트리의 변형으로 Leaf가 아닌 노드로 된 인덱스 세트와 리프 노드로만 구성된 순차 데이터 세트로 구성된다.
: B-트리의 추가, 삭제 시 발생하는 노드의 분열과 합병 연산 과정을 줄일 수 있는 트리 구조
- 트라이(Trie) 색인
: 탐색을 위한 키 값을 직접 표현하지 않고, 키를 구성하는 문자나 숫자 자체의 순서로 키 값을 구성하는 구조
: 삽입 및 삭제 시 노드의 분열과 병합이 없다
5. 파일 편성
1) 순차 파일(Sequential File)
: 기억공간을 효율적으로 사용할 수 있다
: 어떠한 매체에도 적용할 수 있다
: 순서적으로 처리할 경우 속도가 빠르다
: 새로운 레코드를 삽입하거나 삭제하는 경우 시간이 많이 소요된다
: 순차 검색하기 때문에 검색 효율이 낮고, 응답시간이 느리다
: 자기 테이프에서 사용
2) 색인 순차 파일(Indexed Sequential File) = ISAM(Index Sequential Access Method)
: 순차처리와 랜덤처리가 모두 가능
: 기본구역, 색인구역, 오버플로우구역으로 구성
: 자기 디스크에서 사용, 자기 테이프는 사용할 수 없다
- 기본구역(Prime Area)
: 실제 레코드를 기록하는 부분
- 색인구역(Index Area)
: 기본 구역에 있는 레코드를 찾아가는 색인이 기록된 구역
: 트랙 색인 구역, 실린더 색인 구역, 마스터 색인 구역
- 오버플로우 구역(Overflow Area)
: 기본 구역이 Overflow 되서 기록할 공간이 없을 때를 대비하여 예비적으로 확보해둔 구역
- 장점
: 순차 처리와 랜덤 처리가 모두 가능
: 효율적인 검색이 가능
: 레코드를 추가, 삭제할 때 파일 전체를 복사할 필요가 없다
- 단점
: 색인 구역과 오버플로우 구역의 추가 공간이 필요
: 오버플로우 레코드가 많아지면 파일을 재편성 해야함
: 추가, 삭제가 많으면 효율이 떨어짐
: 기억장소 낭비
- 정적 인덱스
: 레코드가 삽입되거나 삭제되어도 인덱스의 구조가 변경되지 않고, 내용만 변하는 구조, 대표적인 파일이 ISAM(색인 순차 파일)
- 동적 인덱스
: 인덱스 파일이나 데이터 파일을 블록으로 구성하고 각 블록에는 추가로 삽입될 레코드를 감안하여 빈공간을 미리 예비해 두는 인덱스 방식. 대표적인 파일이 VSAM
: 블록에 레코드가 가득차면 동적으로 분열되고, 일정 수의 레코드가 유지되지 않는 블록은 합병된다
- VSAM(Virtual Storage Access Method)
: 동적 인덱스 방법을 이용한 색인 순차 파일
: 제어구간, 제어 구역, 순차세트, 인덱스 세트로 구성
: 기본구역과 오버플로우 구역을 구분하지 않는다
: 레코드를 삭제하면 그 공간을 재사용할 수 있다
: 제어 구간에 가변 길이 레코드를 쉽게 수용할 수 있다
- 직접파일(Direct File)
: 특정 순서 없이 임의의 물리적 공간에 기록하는 것
= DAM(Direct Access Method)
: 레코드의 특정 기준으로 키를 할당, 해시 함수를 이용하여 보조기억장치의 물리적 상대 레코드 주소를 계산한 후 해당 주소에 레코드 저장
: 레코드는 해시 함수에 의해 계산된 물리적 주소를 통해 접근할 수 있다
: 자기 디스크, 자기 드럼을 사용
: 데이터의 입/출력이 번번히 발생하는 곳에 응용 좋음
: 다른 레코드를 참조하지 않고 어떤 레코드를 접근 할 수 있다
- 다중 파일
- 역 파일(Inverted File)
: 특정 항목을 여러개의 색인으로 만들어서 특성에 맞게 작업할 수 있도록 함, 다중 키파일
: 검색 속도가 빠르고, 순차, 임의 처리가 모두 가능
- 다중 리스트 파일(Multi-List File)
: 다중 키 파일의 종류, 각 키에 대하여 색인을 만든 다음 각 데이터 레코드들간에 다중 리스트를 구축하여 구성한 파일
- 다중 링 파일(Multi-Ring File)
: 같은 특성을 가진 레코드들의 일련의 포인터로 연결하여 구성한 것
댓글 없음:
댓글 쓰기