[자료구조] 자료구조(Data Structure)

* 프로그램이란?

 -. 데이터를 표현하고, 그렇게 표현된 데이터를 처리하는 것.

 -. 프로그램 = 자료구조(Data의 표현) + 알고리즘(Data 처리)

 

* 자료(Data)란?

 -. 현실 세계로부터 수집한 사실이나 개념의 값 또는 이들의 집합

 -. 가공되지 않은 형태의 데이터

 

* 자료구조

 1. 자료구조란?

   -. 데이터의 표현

   -. 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것

   -. 자료의 집합

   -. 각 원소들 사이의 관계가 논리적으로 정의된 일정한 규칙에 의하여 나열되며 효율적으로 수행할 수 있도록 자료를 조직적, 체계적으로 구분하여 표현한 것

 

 2. 자료구조를 배우는 이유

   -. 데이터를 체계적으로 저장하여, 효율적으로 활용하기 위함

  

 3. 자료구조의 선택기준

   -. 작업의 효율성, 추상화, 재사용성을 증가시키기 위해 상황에 따른 적절한 자료구조를 선택해야 함

    > 자료의 처리시간

    > 자료의 크기

    > 자료의 활용 빈도

    > 자료의 갱신 정도

 

 4. 자료구조의 특징

   -. 효율성 : 자료구조를 사용하는 목적은 상황에 맞게 효율적으로 자료를 관리하고 사용하는 것

   -. 추상화 : 복잡한 자료, 모듈, 시스템 등으로부터 핵심적인 개념 또는 기능을 간추려 내는 것. 자료구조의 추상화는 구현 언어에 따라 그 코드는 다르지만 추상적인 개념에 대해서만 알고 있으면 언어에 종속적이지 않다는 특징을 가짐

   -. 재사용성 : 자료구조를 설계할 때, 특정 프로그램에서만 동작하도록 설계하지 않고 다양한 프로그램에서 동작하도록 설계

 

5. 자료구조의 분류(형태의 따른 분류)

  -. 자료구조의 분류로 자료의 특성과 크기, 주요사용법과 수행하는 연산의 종류, 구현에 필요한 기억 공간 크기에 따라 여러가지 종류의 자료구조 중 하나를 선택할 수 있으며, 자료의 형태의 따라 분류하는 단순구조, 선형구조, 비선형구조, 파일구조로 분류

  -. 단순구조 : 정수, 실수, 문자, 문자열

  -. 선형구조 : 데이터가 일렬로 연결되어 있는 구조(자료구조가 1:1 선형관계)

    > 배열 : 가장 일반적인 구조로 인덱스와 인덱스에 대응하는 데이터들로 이루어진 자료구조

    > 연결리스트 : 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 구조

    > 스택 : 후입선출(LIFO)의 자료구조

    > 큐 : 선입선출(FIFO)의 자료구조

   -. 비선형구조 : 자료의 구성이 일렬이 아닌 형태를 띠는 구조로(자료들간의 앞뒤 관계가 1:다 또는 다:다의 관계)

    > 트리 : 부모노드 밑에 여러개의 자식노드가 연결되어 잇는 재귀적 형태의 자료구조

    > 그래프 : 정점(vertex)과 정점들을 연결하는 변(edge)으로 구성된 자료구조

   -. 파일구조 : 레코드의 집합인 파일에 대한 구조로 순차파일, 색인파일, 직접파일 등이 있음

    > 순차파일 : 파일내용이 하나의 긴 줄로 늘어선 형태로 저장되있어 순차접근만 가능한 구조

    > 색인파일 : 순차파일과 직접파일에서 지원하는 편성방법이 결합된 형태로 색인(인덱스)을 이용한 순차적인 접근방법을 제공하는 구조

    > 직접파일 : 구성하는 레코드(필드의 집합)를 임의의 물리적 저장공간에 기록하는 구조