자료구조 정리 (MFC 클래스)

[ 자료구조 ]

< 구현방법에 따른 분류 >
* 배열 - array
    메모리 상에 같은 타입의 자료가 연속적으로 저장

* (연결) 리스트 - linked list
    노드를 단위로 한다. 노드는 자료와 다음 노드를 가리키는 참조값으로 구성

    - 환형 : 노드에 다음노드에 대한 정보만 있음( 이전노드 정보가 없음), 마지막 노드는 처음노드를 가르킴
   
    - 이중 연결 : 노드에 이전과 다음노드에 대한 정보가 있음
        마지막 노드는 다음 정보가 없음
   
    - 환형 이중연결 :

* 해시 (테이블) - hash table
    - 검색을 위한 키가 있음

* 튜플 - tuple
    둘 이상의 자료형을 묶음으로 다루는 구조


//==============
< 형태에 따른 분류 >
* 선형구조
    - 스택(Stack) : LIFO( Last In, First Out), 후입선출
    - 큐(Queue) :  FIFO(First In, First Out), 선입선출(대기열)
    - 덱(dequeue, deck) : 앞뒤에서 입출 가능

* 비선형구조
    - 그래프(Graph)
        점(노드)들과 간선(점끼리 연결)들 의 집합

    - 트리(Tree) : 그래프를 단순화
        - 두 노드(점)를 잇는 선이 하나뿐
        - 여러 점이 한점을 가르킬수 없다.
        - 이진트리(Binary Tree) : 자식 노드가 2개 이하(가장 간단한 트리)
            - 힙 : 이진트리에 특성 부여
        - 이진 탐색 트리(Binary Search Tree, BST)
            - 왼쪽에 작은 값 배치
            - AVL-tree, 234 Tree, B Tree, B+ Tree

        - 힙(Heap) : 아래쪽에 작은 값 배치

    - 포레스트(Forest) : 하나 이상의 트리의 집합

< 알고리즘 >
    - 정렬, 탐색, 최단 거리 찾기


//==============
< MFC 자료구조 >
* CArray(template) - 배열
template < class TYPE, class ARG_TYPE = const TYPE& >
    - Byte (CByteArray), DWord, Ob, Ptr, String, UInt, Word
    - 메모리상에 순차적으로 배열됨, 임의 접근이 빠름
    - 임의 추가, 삭제시 메모리가 재배열됨(메모리 복사 해제 수행), 속도에 문제 생김
    - 간단한 자료형에는 문자가 없지만 구조체나 클래스에서는 복사시 문제가 발생할수 있음

        -> CList, CPtrArray사용

    - 전체 크기를 알경우(예측가능하면) 미리 크기확보해 놓으면 성능 향상됨, CArray::SetSize()

* CList(template) - 이중 연결 리스트(doubly-linked lists)
template< class TYPE, class ARG_TYPE = const TYPE& >
    - Ptr(CPtrList), Ob, String
    - 멤버함수 예 : AddHead, RemoveTail, RemoveAt
    - 임의 접근 느림 : 노드의 정보를 따라가야 함
        - 100번째 노드를 찾으려면 1번째 노드의 다음정보를 읽어서 100번 거처야 100번째 노드를 알아낼수 있음
    - 맨 처음과 끝에서 삭제, 추가가 빠름( 추가적인 메모리 대량복사 삭제가 일어나지 않음)
    - 임의 접근이 필요없는 스택, 큐, 덱 등의 자료구조에 적합


* CMap(template) - 해쉬 테이블
template< class KEY, class ARG_KEY, class VALUE, class ARG_VALUE >class CMap : public CObject
    - WordToPtr(CMapWortToPtr), PtrToWorld, PtrToPtr, WordToOb, StringToPtr, StringToOb, StringToString
    - 대용량 자료에서 빠른 검색이 필요할때 사용

// 참고

CArray, CList 사용 선택 방법 http://codens.info/659