[정처기] 데이터 입출력 구현_자료 구조

자료구조

자료를 기억장치의 공간 내에 저장하는 방법과 자료 간의 관계, 처리 방법 등을 연구 분석하는 것

저장 공간의 효율성과 실행 시간의 단축을 위해 사용한다

• 선형구조
  • 배열
  • 선형리스트
    • 연속 리스트
    • 연결 리스트
  • 스택
  • 큐
  • 데크
• 비선형 구조
  • 트리
  • 그래프

배열

크기와 타입이 동일한 자료들이 순서대로 나열된 자료의 집합

반복적인 데이터 처리 작업에 적합한 구조

정적인 자료구조로, 기억장소의 추가가 어렵다

데이터 삭제 시 기억 장소가 빈 공간으로 남아있ㅇ어 메모리의 낭비가 발생한다

연속 리스트

배열과 같이 연속되는 기억장소에 저장되는 자료 구조

중간에 데이터를 삽입하기 위해서는 연속된 빈 공간이 있어야 한다

삽입 삭제 시 자료의 이동이 필요하다

연결 리스트

자료들을 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료구조

연결을 위한 링크(포인터) 부분이 필요하기 때문에 기억 공간의 이용 효율이 좋지 않다

접근 속도가 느리고, 연결이 끊어지면 다음 노드를 찾기 어렵다

스택

리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료구조

후입선출(LIFO) 방식으로 자료를 처리한다

저장할 기억 공간이 없는 상태에서 데이터가 삽입되면 오버플로가 발생한다

삭제할 데이터가 없는 상태에서 데이터를 삭제하면 언더플로가 발생한다

큐

리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지는 자료 구조

선입선출(FIFO)

시작을 표시하는 Front 포인터와 끝을 표시하는 Rear 포인터가 있다

그래프

정점과 간선의 두 집합으로 이루어지는 자료구조

사이클이 없는 그래프를 트리라고 한다

간선의 방향성 유무에 따라 방향 그래프와 무방향 그래프로 구분된다

방향/무방향 그래프의 최대 간선 수

방향 그래프의 최대 간선 수 : n(n-1)

무방향 그래프에서 최대 간선 수 : n(n-1)/2