Introduction to Data Structure Using C

윤성우의 열혈 자료구조

자료구조에 대한 기본적 이해
프로그램 = 자료구조(데이터 표현) + 알고리즘(데이터 처리)
자료구조가 결정되어야 그에 따른 효율적인 알고리즘 설계 가능하다.
알고리즘은 자료구조에 의존적이다.

알고리즘의 성능분석 방법
시간 복잡도(Time Complexity) - 속도
     연산의 횟수를 통해 알고리즘의 빠르기 판단
          데이터 수의 증가에 따른 연산횟수의 변화 정도 판단
          탐색 알고리즘에서 시간 복잡도를 결정하는 핵심 연산자는 동등비교(==)이다.
공간 복잡도(Space Complexity) - 메모리 사용량
일반적으로 알고리즘 성능 평가할 때 메모리 사용량보다 실행속도에 초점을 둔다.
일반적인 알고리즘의 평가에는 논란의 소지가 거의 없는 '최악의 경우(worst case)가 선택된다.
Big-Oh Notation은 '데이터 수의 증가에 따른 연산횟수의 증가패턴을 나타내는 표기법이다.' 또는 '데이터 수의 증가에 따른 연산횟수 증가율의 상한선을 표현한 것'이다.

Recursive
하노이 타워
     가장 작은 단위 패턴을 코딩하고 이를 일반화시키면 된다.

리스트 (List)
     순차 리스트 (배열 기반)
          배열 자료구조 특징인 Index를 통해서 어느 곳이든 바로 이동이 가능하다.
          하지만, 프로그램 실행 전에 크기가 결정되어야 한다.
          그리고 배열은 메모리의 특성이 정적이므로 메모리 길이 변경이 불가능하다.
          정적인 배열은 필요로 하는 메모리의 크기에 유연하게 대처하지 못한다.
     연결 리스트 (메모리 동적 할당 기반)
          프로그램 실행 중에도 필요할때 마다 필요한 크기만큼 할당, 해제 할 수 있다.
          head, tail, cur의 구조체 node가 필요하므로 추가적인 메모리 할당이 필요하다.
          자료구조 특성상 항상 처음부터 순차적으로 탐색 할 수 밖에 없다.
       
* 함수포인터
ex) Main함수: SetSortRule(&list, WhoIsPrecede)
ex) void SetSortRule(List *plist, int(*comp)(LData d1, LData d2)) { plist->comp = comp; }
list 구조체에 WhoIsPreced 정렬함수의 주소를 저장하여 Insert 함수에 정렬함수가 사용될 수 있도록 해준다. Main함수에서 정렬 함수를 사용자 정의로 구현해서, 쓰임새에 맞게 여러가지 정렬 함수를 함수 포인터를 이용하여 선언된 list 구조체에 설치해주므로써 유용하게 사용할 수 있도록 해준다.

     원형 연결 리스트 (Circular Linked List)
          마지막 노드가 첫 번째 노드를 가리켜서, 연결의 형태가 원을 이루는 구조
          원형 연결 리스트에서는 머리와 꼬리의 구분이 없다
     변형된 원형 연결 리스트 ( 일반적인 원형 연결 리스트 )
          단순 연결 리스트처럼 머리와 꼬리를 가리키는 포인터 변수를 각각 두지 않아도,
          하나의 포인터 변수만 있어도 머리 또는 꼬리에 노드를 간단히 추가할 수 있다.
          즉, 포인터 변수 한개만으로도 양방향으로 노드를 추가할 수 있다. (간결성)
          꼬리를 가리키는 포인터 변수 : tail
          머리를 가리키는 포인터 변수 : tail->next
     양방향 연결 리스트 (이중 연결 리스트)
          더미 노드 양방향 연결리스트
          원형 연결 기반의 양방향 연결 리스트
          - 리스트가 한쪽 방향으로만 조회가 가능했을 때의 포인터 변수 before가 필요없다.
          양방향 연결 리스트는 양방향으로 얼마든지 조회가 가능하므로,
          포인터 변수 before가 불필요하고, before를 유지하기 위해 곳곳에 존재하는
          문장들도 불필요하다.
          - 첫 번째 노드 추가와 두 번째 이후의 노드 추가 구현이 서로 다르므로,
          더미노드를 사용해 통일시킨다. (간결성)

스택 (Stack) - 연결 리스트 기반 구현(배열도 가능)
     LIFO(Last-In, First-Out), 후입선출
     그냥 포인터 변수 head가 하나 있는 자체가 Stack구조랑 유사하다.
     스택 ADT
          push
          pop
          peak
         
     계산기 프로그램 구현
          연산자의 우선순위를 신경쓰지 않아도 되고, 소괄호 처리도 필요없는
          후위 표기법(postfix notation)을 사용한다.
          계산기 사용자를 위해 중위 표기법(infix notation)으로 나타내어주지만,
          컴파일러에(계산기 프로그램) 의해서 Stack data structure를 이용해
          후위 표기법으로 바뀌어 처리된다.

큐 (Queue)
     FIFO(First-In, First-Out), 선입선출
     큐의 ADT
          enqueue
          dequeue
     배열 기반의 큐
          일반적인 배열 구조의 큐 구현은 다음과 같은 여러가지 제약이 따른다.
               dequeue 연산 시마다 저장된 데이터를 한 칸씩 이동시켜야 하는 단점
               배열 끝까지 갔지만 꽉 차지 않은 상황
          이를 극복하기 위해 원형 큐 (Circular Queue)를 구현한다.
     리스트 기반의 큐
             
덱 (Deque)
     노드가 양방향으로 연결되어 있지 않으면, 꼬리에 위치한 노드의 삭제는 간단하지 않다.
     따라서 덱의 구현에 있어서 양방향 연결 리스트는 매우 좋은 선택이다.