자료구조 복습

자료구조란 자료를 효율적으로 사용하기 위해 자료를 조직화한 것이다.

구조 정의, 삽입 동작, 삭제 동작 등을 정의해야 한다.

 

자료구조의 종류

선형 자료구조

• 배열(array), 연결 리스트(linked list)
• 스택(stack), 큐(queue)

비선형 자료구조

• 트리(tree), 그래프(graph)

 

순차 자료구조

자료들의 논리적 순서와 물리적 순서가 일치한다.

배열('같은 자료형'을 가진 자료들을 메모리에 연속적으로 저장하는 방식)의 삽입과 삭제를 사용한다.

 

연결 자료구조

배열이 가지는 메모리 사용의 비효율성을 해결한다.

연결 리스트(다음 자료의 위치를 자료가 가지고 있는 방식, 노드와 링크로 구성)를 사용한다.

typedef struct _node {
    int key; // 정수형 key 필드를 사용하여 자료 관리
    struct _node *next; // 포인터 변수 next 필드로 다음 노드의 주소값 관리
} node;
node *SlinkedList;

- 단순 연결 리스트의 삽입 연산

Input: 단순 연결 리스트, 삽입값 k, 삽입 위치 노드 포인터 previous
Output: 삽입된 단순 연결 리스트
Procedure: 
insert_after(int k, node *previous){
    node *new; new -> key = k; // 새 노드 생성
    new -> next = previous -> next; // 새 노드의 next값 결정
    previous -> next = new; // 선행 노드의 next값 결정
}

- 단순 연결 리스트의 삭제 연산

Input: 단순 연결 리스트, 삭제값 k
Output: 삭제된 단순 연결 리스트
Procedure:
    delete(int k){
        node *temp = SlinkedList;
        while((temp->next != null) && (temp->next->key != k))
	        temp = temp -> next; // 선행 노드 temp 검색
        target = temp -> next ; // 삭제 노드 target 검색
        if((target->next) != null)
	        temp -> next = target -> next; // 링크 필드 조정
    }

 

원형 연결 리스트 (circular linked list)

마지막 노드가 첫 번째 노드를 가리킨다.

임의의 위치에서 검색과 삭제가 가능하다.

 

이중 연결 리스트 (double linked list)

다음 노드의 주소값과 이전 노드의 주소값을 모두 저장한다.

선행 노드와 후행 노드로 모두 접근 가능하다.

트리와 같이 두 개의 노드와 연결되어야 하는 경우에 유용하다.

확장성이 있다.

- 이중 연결 리스트의 삽입

Input: 이중 연결 리스트, 삽입값 k, 삽입 위치 노드 포인터 previous
Output: 삽입된 이중 연결 리스트
Procedure: 
    insert_after(int k, dnode *previous){
        dnode *new; new -> key = k; // 새 노드 생성
        new -> next = previous -> next; // 새 노드의 next값 결정
        previous -> next = new; // 선행 노드의 next값 갱신
        new -> prev = previous; // 새 노드의 prev값 결정
        new -> next -> prev = new; // 후행 노드의 prev값 갱신
    }

- 이중 연결 리스트의 삭제

 

스택 (Stack)

입구가 하나인 후입선출(LIFO, Last In First Out) 구조이다.

배열을 사용하여 push, pop 동작을 한다.

첨자 '0'은 스택의 첫 번째 원소이고, top은 마지막 원소이다.

공백 스택은 top==-1일 때이고, 포화 상태는 top==n-1일 때이다.

 

- 배열을 사용한 스택의 push, pop 연산

Input: 스택 int stack[n], 삽입값 k
Output: push, pop 동작 후의 스택
Procedure: 
    int top= -1; // top의 초기값
    push(int k) { 
        if(top >= n -1) OVERFLOW!!;
        else stack[++top]=k;
    } 
    int pop() { 
        if(top==-1) UNDERFLOW;
        else return stack[top--];
}

- 연결 리스트를 사용한 스택의 push, pop 연산

Input: 스택, 삽입값 k
Output: push, pop 동작 후의 스택
Procedure:
    top->next = null; // top의 초기값
    push(int k) {
        node* new;
        new->key = k;
        new->next = top->next;
        top->next = new;
    }
    int pop() {
    node* temp;
    temp = top->next;
    if(temp == null) UNDERFLOW;
    else {
	    top->next = temp->next;
	    return temp->key;
    }
}

 

큐 (Queue)

입출구가 별도인 선입선출(FIFO, First In First Out) 구조이다.

• 초기상태: front = rear = -1
• 공백상태: front = rear
• 포화상태: rear = n-1

 

- 배열을 사용한 enQueue, deQueue 동작

Input: 큐 int queue[n], 삽입값 k
Output: enQueue, deQueue 동작 후의 큐
Procedure:
    int front = rear = -1; // 큐의 초기 상태
    enQueue(int k) { 
        if(rear == n-1) OVERFLOW!!;
        else queue[++rear]=k;
    } 
    int deQueue() { 
        if(front == rear) UNDERFLOW;
        else return queue[++front];
    }

 

선형 큐의 단점

enQueue와 deQueue 반복하다 보면 비포화상태를 포화상태로 인식한다.

 

원형 큐

선형 큐의 단점을 해결한다. (연결 리스트도 가능하다.)

• 포화상태: (rear+1) mode n = front

 

 트리 (Tree)

계층 관계를 표현한다.

배열을 사용하여 트리를 표현했다.

 

그래프

정점(vertex)과 간선(edge)으로 표현한다.

인접 행렬(adjacency matrix) 법

이는 희소 행렬(sparse matirx) 처리로 비효율적이다.

 

인접 리스트(adjacency list) 법

인접 행렬 법보다 메모리를 덜 차지하지만, 시간 복잡도가 높아진다.

 

[참고] 알기 쉬운 알고리즘