자료구조 요약정리

소개

"자료구조 요약정리"에 대한 내용입니다.

목차

없음

본문내용

[연결리스트]
-리스트
기본적인 연산: 삽입, 삭제, 검색 등
리스트를 구현하는 대표적인 두 가지 방법: 배열, 연결 리스트

[스택(LIFO)]
리스트의 일종. 데이터의 삽입과 삭제가 한 쪽 끝(top)에서만 이루어짐.

[큐(FIFO)]
리스트의 일종. 데이터의 삽입은 한 쪽 끝(rear)에서, 삭제는 반대쪽 끝(front)에서만 일어남. 따라서 연결리스트의 앞쪽을 front, 뒤쪽을 rear로 하는 것이 유리함.
삽입을 위해서는 마지막 노드의 주소를 항상 기억해야 함.

[정렬]
데이터를 특정한 조건에 따라 일정한 순서가 되도록 다시 배열하는 일.
레코드: 정렬의 대상
필드: 레코드를 구성하는 작은 단위의 데이터
키: 레코드를 식별하는 역할을 하는 필드
1. 단순하나 비효율적- 삽입 정렬, 선택 정렬, 버블 정렬
2. 복잡하나 효율적- 퀵 정렬, 히프 정렬, 합병 정렬, 기수 정렬

-선택 정렬-
정렬 대상 데이터에서 가장 작은 수 또는 가장 큰 수를 찾아 정렬
정렬 대상 데이터 수만큼의 저장 공간(정렬 공간)을 마련한 후 정렬 대상 데이터 집합에서 기준으로 수를 선택한 후 결과 공간으로 옮기는 정렬

-삽입 정렬-
정렬 대상 데이터를 정렬하기 위해 정렬된 목록과 정렬되지 않은 목록으로 구분
정렬되지 않은 목록의 데이터 하나를 정렬된 목록의 올바른 위치에 삽입하여 정렬을 유지
비교해서 크면 비교한 데이터 뒷 자리에 추가, 작으면 비교한 데이터를 뒷 자리로 이동

-버블 정렬-
정렬 대상 데이터를 정렬하기 위해 인접한 두 개의 데이터를 비교
크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 수행

-합병 정렬-
하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬

-퀵 정렬-
분할 정복 방법에 근거: 합병 정렬과 유사하게 전체 리스트를 2개의 부분 리스트로 분할(비 균등 분할), 각각의 부분 리스트를 다시 퀵 정렬

참고자료

· 없음