030 자료 구조의 개념
1. 자료 구조의 정의
- 프로그램 작성시 고려사항 : 저장공간의 효율성, 실행 시간의 신속성
- 자료를 저장하는 방법, 자료 간의 관계, 처리하는 방법
- 자료의 표현, 관련 연산
- 자료 조직, 구조화
- 어떠한 자료 구조에서도 필요한 모든 연산 처리 가능
- 자료 구조 따라 프로그램 실행시간 상이
2. 자료 구조의 분류
- 선형 구조
•리스트
- 선형 리스트
- 연결 리스트
•스택
•큐
•데크
- 비선형 구조
•트리
•그래프
3. 자료 구조의 이용
- 정렬
- 검색
- 파일 편성
- 인덱스 : 색인표
031 리스트
1. 선형 리스트
- 연속되는 기억장소에 저장되는 리스트
- 연접 리스트 (Dense List), 축차 구조 (Sequential Structure)
- 배열
- 특징
•가장 간단한 자료 구조
•접근 속도 빠름
•중간에 자료 삽입 -> 연속된 빈 공간 필요
•기억장소 이용 효율 좋음 : 밀도 1
•자료 개수 n, 평균 이동 횟수 : (n+1)/2, 삭제시 이동 횟수 = (n-1)/2
•삽입, 삭제시 자료 이동 필요 -> 번거로움
2. 연결 리스트
- 임의의 기억공간에 저장
- 순서에 따라 포인터로 연결
- 특징
•삽입, 삭제 용이
•연속 x -> 저장가능
•링크(포인터) 필요 -> 기억공간 이용 효율 bad
•접근 속도 느림
•중간 노드 연결 끊어짐 -> 다음 노드 찾기 어려움
•희소 행렬 표현 용이 (기억공간 절약)
•트리
- 종류
•단순 연결 리스트
•단순 환상 연결 리스트
•이중 연결 리스트
•이중 환상 연결 리스트
032 스택
1. 스택의 개념
- 한쪽 끝으로만 자료 삽입, 삭제 작업
- LIFO
- TOP : 마지막 자료 기억 위치, 스택 포인터(SP)
- Bottom : 스택 바닥
2. 자료의 삽입
- Top = Top + 1
If Top > M Then
Overflow
else
X(Top) <- Item
3. 자료의 삭제
- If Top = 0 Then
Underflow
else
Item <- X(Top)
Top = Top - 1
4. 스택의 응용 분야
- 부 프로그램 호출 시 복귀주소 저장
- 함수 호출 순서 제어
- 인터럽트 발생 시 복귀주소 저장
- 후위 표기법 수식 연산
- 0 주소지정방식 명령어 자료 저장소 ?
- 재귀 프로그램 순서 제어
- 컴파일러 이용 언어 번역
033 큐와 데크
1. 큐
- 한쪽 삽입 한쪽 삭제
- FIFO
- 시작 끝 : 2개 포인터
- 프런트 : 앞쪽, 삭제 시 이용
- 리어 : 뒤쪽, 삽입 시 이용
- 응용 분야
•대기 행렬 처리
•운영체제 작업 스케줄링
2. 데크
- 삽입 삭제 양쪽
- Double Ended Queue
- 스택, 큐 장점만 따서 구성
- 입력 제한 데크, 출력 제한 데크 (Scroll, Shelf)
034 트리
1. 트리의 정의
- 정점(Node), 선분(Branch)로 구성
- Cycle 없는 그래프
- 계보, 연산 수식, 회사 조직 구조도, 히프
2. 트리 관련 용어
- 노드(Node)
- 근 노드(Root Node) : 맨 위 노드
- 차수(Degree) : 노드 가지 수
- 단말 노드(Terminal Node, Leaf Node)
- 비단말 노드(non-Terminal Node)
- 조상 노드(Ancestor Nodes)
- 자식 노드(Child Node)
- 부모 노드(Parent Node)
- 형제 노드(Siblings)
- Level : 근 노드 - level 1
- 깊이(Depth) : max(Level)
- 숲(Forest)
- 트리의 디그리 : max(Degree)
035 이진 트리
1. 이진 트리의 특성
- 차수 2 이하 노드들로 구성된 트리
- 레벨 i 최대 노드 수 : 2^(i-1)
- Depth i 최대 노드 수 : 2^i - 1
- n0 = n2 + 1
2. 이진 트리의 종류
- 정이진 트리 (Full Binary Tree)
- 전이진 트리 (Complete Binary Tree)
- 사향 이진 트리 (Skewed Binary Tree)
036 이진 트리의 운행법
1. 트리의 운행법
- Preorder : Root -> Left -> Right
- Inorder : Left -> Root -> Right
- Postorder : Left -> Right -> Root
2. 수식의 표기법
- 전위 표기법(Prefix) : 연산자 -> Left -> Right
- 중위 표기법(Infix) : Left -> 연산자 -> Right
- 후위 표기법(Postfix) : Left -> Right -> 연산자
- 순서
•연산 우선순위에 따라 괄호
•연산자 해당 괄호 전/후로 이동
•괄호 제거
3. 스레드 이진 트리
- Null 링크를 다른 노드의 포인터로 사용
037 그래프
1. 그래프의 정의
- 그래프 G : 정점 V(Vertex), 간선 E(Edge)로 구성
- 통신망, 교통망, 이항관계, 연립방정식, 유기화학 구조식, 무향선분 해법
2. 용어 정리
- Loop
- 차수(Degree)
•무방향 그래프 : 한 정점에 연결된 간선 수
•방향 그래프 : Indegree, Outdegree
- 경로
•경로 길이
•단순 경로
•기본 경로
•사이클
•최대 사이클
3. 인접행렬을 이용한 그래프 표현 방법
- ViVj 관계 -> 행렬 P : Edge 있으면 Pij = 1, 없으면 Pij = 0
4. 특수 그래프
- 최소 비용 신장 트리
- 간선 작업 네트워크
덧글