카누누카

- 순차 자료구조를 이용한 큐의 단점 1. 사용 크기가 배열 크기로 제한되므로 큐의 길이를 마음대로 사용할 수 없다. 2. 원소가 없어도 항상 고정된 크기를 유지해야 하므로 메모리가 낭비된다. --> 연결 자료구조를 이용해 크기 제한이 없는 연결 큐를 통해 한계점 보완. - 연결 큐 연결 큐에서 원소는 데이터 필드와 링크 필드를 가진 노드로 구성하며, 첫 번째 노드를 가리키는 front 포인터와 마지막 노드를 가리키는 rear 포인터를 사용한다. 연결 큐의 초기 상태(공백 큐)는 front와 rear를 NULL 포인터로 설정하여 표현한다. - 연결 큐의 대한 연산 알고리즘 - 연결 큐의 노드 구조체 1 2 3 4 5 6 7 8 9 10 11 12 #pragma once typedef char elemen..

1. 큐의 개념과 구조 큐(Queue)는 삽입과 삭제의 위치와 방법이 제한된 유한 순서 리스트라는 점은 스택과 같지만, 리스트의 한 쪽 끝에서는 삽입 작업만 이루어지고 반대쪽 끝에서는 삭제 작업만 이루어진다는 점이 스택과 다르다. 큐는 삽입된 순서대로 먼저 삽입된 데이터가 먼저 삭제되는 선입선출(FIFO: First In Fisrt Out) 구조로 운영된다. 큐는 한쪽 끝을 front(머리)로 정해 삭제 연산만 수행하고, 다른 쪽 끝을 rear(꼬리)로 정하여 삽입 연산만 수행하는 제한 조건을 가진 자료구조이다. - front : 가장 먼저 큐에 삽입된 첫 번째 원소 -> 삭제 연산 : deQueue - rear : 큐에 가장 늦게 삽입된 마지막 원소 -> 삽입 연산 : enQueue < 스택과 큐에서의..

1. 스택의 개념과 구조 스택(Stack) 자료구조는 접시에 음식을 쌓아올리듯 데이터를 차곡차곡 쌓아올린 형태로 자료를 구성한다. 스택은 같은 구조와 같은 크기의 데이터를 정해진 방향으로만 쌓을 수 있고, top으로 정한 한 곳으로만 접근하도록 제한되어 있다. 따라서 top을 통해 들어온 데이터가 일정한 방향, 즉 아래(Bottom)에서 위로 차곡차곡 쌓이게 된다. - top 스택에서 유일하게 액세스가 허용된 지점으로 삽입과 삭제가 일어나는 위치이며 현재 스택의 가장 위에 있는 데이터 위치가 된다. 새로 삽입되는 데이터가 스택에서 가장 위에 있는 데이터가 된다. 스택에서 자료를 삭제할 때 top을 통해서만 가능하기 때문에 top에 있는 데이터, 즉 가장 위에 있는 데이터가 삭제되고 삽입된다. 이러한 스택..

1. 단순 연결 리스트를 이용한 다항식 표현 - 다항식에 있는 항 하나는 노드 하나로 표현한다. - 각 항마다 계수와 지수를 저장해야하므로 노드의 데이터 필드는 계수를 저장하는 coef와 지수를 저장하는 expo 필드로 구성하고, 링크 필드는 다음 항을 연결하는 포인터로 구성한다. 1 2 3 4 5 typedef struct Node { float coef; int expo; struct Node *link; }; cs A(x) = 4x^3 + 3x^2 + 5x B(x) = 3x^4 + x^3 + 2x + 1 2. 다항식 연결 자료구조의 항 삽입 알고리즘 - 다항식에 항을 추가하려면 연결 리스트의 마지막 노드 다음에 새로운 노드를 추가하는 알고리즘으로 정의할 수 있다. 1 2 3 4 5 6 7 8 9 1..

1. 이중 연결 리스트의 개념 - 한계점 단순 연결 리스트 : 선행 노드로 접근하기 어렵다. -> 원형 연결 리스트를 통해 한계점 극복. 원형 연결 리스트 : 현재 노드 바로 이전 노드로 접근하려면 전체 리스트를 한 바퀴 순회해야 한다. -> 이중 연결 리스트를 통해 한계점 극복. - 이중 연결 리스트 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트 - 원형 이중 연결 리스트 1 2 3 4 5 typedef struct Dnode{ struct Dnode *llink; char data[5]; struct Dnode *rlink; } cs 2. 이중 연결 리스트의 알고리즘 - 공백 이중 연결 리스트를 생성하는 연산 1 2 3 4 5 6 7 // 공백 이중 연결 리스트를 생성하는 연산 linkedLi..

1. 원형 연결 리스트의 개념 단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 하여 리스트 구조를 원형으로 만든 연결 리스트를 원형 연결 리스트라고 한다. -> 즉, "단순 연결 리스트의 마지막 노드의 링크 필드에 첫 번째 노드의 주소를 연결하여 구성" 단순 연결 리스트는 시작 노드에서 링크를 따라 마지막 노드에서 순환이 끝나지만, 원형 연결 리스트는 링크를 따라 계속 순환이 가능하다. 1 2 3 4 5 6 7 8 9 10 // 원형 연결 리스트의 노드 구조를 구조체로 정의 typedef struct ListNode { char data[4]; struct ListNode* link; } listNode; // 리스트 시작을 나타내는 head 노드를 구조체로 정의 typedef st..