카누누카

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

3. 원형 큐의 구현 순차 큐의 잘못된 포화 상태 인식 문제를 해결하기 위해 원형 큐를 사용한다. 원형 큐는 순차 큐와 같은 1차원 배열을 사용하지만, 논리적으로 배열의 처음과 끝이 연결되어 있는 원형 구조로 가정하고 사용한다. 원형 큐에서는 초기 공백 상태일 때 front와 rear의 값을 0으로 하고, 공백 상태와 포화 상태를 쉽게 구분하기 위해서 자리 하나를 항상 비워 둔다. 원형 큐에서도 공백 상태에는 front와 rear의 위치가 같다. 순차 큐와 마찬가지로 rear가 다음으로 이동하면서 원소를 삽입하고, front는 rear가 이동한 방향으로 따라가면서 원소를 삭제한다. 원형 큐에서는 인덱스가 n-1 다음에 다시 0이 되어야하므로 사용할 인덱스를 조정하기 위해 나머지 연산자 mod를 사용한다...

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

1. 스택을 이용한 역순 문자열 스택의 LIFO 특성을 이용하여 역순 문자열을 간단히 만들 수 있다. 1) 문자열을 순서대로 스택에 삽입한다. 2) 스택에서 삭제하여 문자열을 만든다. 2. 시스템 스택 프로그램에서 수행되는 함수 호출과 복귀 순서는 가장 나중에 호출된 함수가 먼저 실행을 완료하고 복귀하는 순서를 따른다. 이처럼 함수의 호출과 복귀 순서는 역순의 관계를 가지므로 스택의 LIFO 구조를 응용해 관리할 수 있다. -> 이때 사용하는 스택을 시스템 스택이라 한다. 함수나 서브 프로그램 호출이 발생하면 호출된 함수의 작업으로 전환하기 위해 현재 작업 중인 지역 변수, 매개 변수 및 완료 후 복귀할 주소 등의 정보를 스택 프레임에 저장하여 시스템 스택에 삽입한다. 시스템 스택의 top은 현재 실행 ..

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..