언제나 휴일

5.4.1 스택 설계, 5.4.2 스택 구현, 5.4.3 스택 테스트 5.4.1 스택 설계 스택도 연결리스트를 래핑하여 만들게요. 연결리스트 형식을 스택 형식으로 타입 재지정합니다.#include "LinkedList.h"typedef LinkedList EHStack; 동적으로 스택을 생성하는 함수와 소멸하는 함수를 제공합시다.EHStack *New_EHStack();void Delete_EHStack(EHStack *ehs); 스택에 자료를 보관하는 함수와 꺼내는 함수를 제공합시다.void EHStack_Push(EHStack *ehs, Element data);Element EHStack_Pop(EHStack *ehs); 스택이 빈 상태인지 확인하는 함수도 제공합시다. int EHStack_IsEm..

5.4 스택(STACK) 스택은 큐와 달리 가장 최근에 보관한 자료를 먼저 꺼내는 후입선출(LIFO, Last In First Out)형태로 동작하는 자료구조입니다. 스택은 배열이나 연결리스트로 구현할 수 있어요.여기에서는 배열로 구현하는 것을 먼저 해 본 후에 미리 만든 연결리스트를 래핑하는 방법을 살펴보아요. 먼저 스택 구조체를 정의하세요.스택에는 저장소와 가장 최근에 보관한 위치를 멤버로 갖고 있어야 해요. #define STACK_SIZE 10typedef struct Stack //Stack 구조체 정의{ int buf[STACK_SIZE];//저장소 int top; //가장 최근에 보관한 인덱스}Stack; 스택에는 보관하는 동작을 Push라 부르고 꺼내는 동작을 Pop이라 불러요.void P..

5.3.2 큐 구현, 5.3.3 큐 테스트 5.3.2 큐 구현 먼저 동적으로 큐를 생성하는 함수를 작성합시다.EHQueue *New_EHQueue(){ 여기서 설계한 큐는 연결 리스트이므로 연결리스트를 동적으로 생성하여 반환합니다. 이처럼 이미 작성한 기능을 이용하여 전달하는 역할만 하는 함수를 래퍼(Wrapper) 함수라고 부릅니다. return New_LinkedList();} 동적으로 생성한 큐를 소멸하는 함수도 래퍼 함수로 작성합니다.void Delete_EHQueue(EHQueue *ehq){ Delete_LinkedList(ehq);} 큐에 자료를 보관하는 함수도 연결리스트에 순차 보관하는 함수를 호출하는 래퍼 함수로 작성합니다.void EHQueue_Put(EHQueue *ehq, Eleme..

5.3.1 큐(QUEUE) 설계 여기에서는 연결리스트를 큐로 감싸(Wrapping)하여 선입선출(FIFO, First In First Out)방식으로 자료를 보관 및 꺼내기 동작을 제공하도록 설계할게요.#include "LinkedList.h"typedef LinkedList EHQueue; 큐를 설계할 때 내부에 자료를 보관하는 저장소를 배열로 만드는 방법도 있는데 이미 만들어진 연결리스트를 이용하여 자료를 보관하게 정의하면 저장소의 한계가 없는 큐를 만들 수 있습니다. 물론 메모리의 한계까지 없는 것은 아닙니다. 일반적으로 대학에서 배우는 큐는 자료를 보관하는 저장소를 정적 크기의 배열로 정의하는 큐를 배우고 꽉 찼을 때의 처리에 관한 고민을 합니다. 특히 이 문제를 원형 큐 형태로 만들어 문제를 해..

5.3 큐(QUEUE) 이번에는 큐를 알아보기로 해요.큐는 순차적으로 자료를 보관하고 가장 최근에 보관한 자료를 꺼내는(FIFO, First In First Out) 버퍼예요. 여기에서는 버퍼의 크기가 정적인 배열로 정의하는 것을 먼저 구현할 거예요.그리고 난 후에 이미 작성한 연결리스트를 이용하는 큐를 만들기로 해요. 배열로 큐를 정의할 때 자료를 보관하는 버퍼 외에 자료를 보관할 위치와 꺼낼 인덱스를 기억하고 있어요.보관할 위치는 맨 뒤에 보관해서 rear라고 부르고 꺼낼 위치는 맨 앞이어서 front라 불러요.그리고 큐에 자료를 보관하는 행위를 EnQueue 혹은 Put이라 불러요.큐에서 자료를 꺼내는 행위는 DeDueue 혹은 Get이라 불러요.그리고 배열로 큐를 구현할 때는 큐가 비었는지 혹은 ..

5.2.3 연결리스트 테스트 연결리스트를 사용하는 방법은 순차적으로 보관하거나 원하는 위치를 찾아 보관하는 방법이 대표적입니다. 동적 배열에서는 이 외에도 인덱스를 사용하는 방법이 있었지만 연결리스트를 사용할 때는 이 방법은 사용하지 않습니다. 따라서 테스트 코드는 크게 순차 보관하는 시뮬레이션과 원하는 순서로 보관하는 예로 구성할게요. int main() { Simul_Seq(); Simul_Order(); return 0; } 먼저 순차적으로 보관하는 테스트 코드를 작성합시다. void Simul_Seq() { 먼저 연결리스트를 동적으로 생성합니다. LinkedList *linkedlist = New_LinkedList(); 그리고 도서 개체를 생성하여 연결리스트에 순차 보관합니다. 순차 보관할 때는..

5.2.2 연결리스트 구현 연결리스트를 동적으로 생성하는 함수를 작성합시다. LinkedList *New_LinkedList() { LinkedList *linkedlist = 0; 먼저 LinkedList 형식 크기의 메모리를 할당합니다. linkedlist = (LinkedList *)malloc(sizeof(LinkedList)); 그리고 head와 tail에 더미 노드를 생성합니다. 노드를 생성하는 함수는 별도로 작성합시다. linkedlist->head = New_Node(0); linkedlist->tail = New_Node(0); head의 next링크를 tail을 가리키게 하고 tail의 prev 링크를 head를 가르키게 합니다. linkedlist->head->next = linked..

5.2 연결리스트 연결리스트는 노드의 선형 집합입니다. 노드란 데이터와 링크의 조합으로 하나의 데이터를 보관하는 작은 저장소입니다. 그리고 링크는 노드의 위치 정보입니다. [그림 5.1] 연결리스트 연결리스트는 노드에 링크가 하나만 있는 단일(단순) 연결리스트와 링크가 두 개 있는 이중 연결리스트로 구분할 수 있습니다. 이 책에서는 노드에 이전 노드의 위치 정보를 가르키는 링크와 다음 노드의 위치 정보를 가르키는 링크를 갖고 있는 이중 연결리스트를 만들고 사용하는 방법을 소개할 것입니다. 특히 연결리스트를 생성할 때 연결리스트의 맨 앞과 맨 뒤에 더미 노드를 생성하여 자료를 보관하는 노드들을 이들 사이에 배치할게요. 5.2.1 연결리스트 설계 동적 배열처럼 연결리스트도 동적으로 생성한 개체는 형식에 관계..

5.1.3 동적 배열 테스트 앞에서 만든 동적 배열이 잘 동작하는지 확인하는 시뮬레이션 코드를 작성합시다. 여기에서는 순차적으로 자료를 보관하는 예와 특정 키순으로 보관하는 예, 인덱스를 사용하는 예를 들게요. int main() { Simul_Seq(); Simul_Order(); Simul_Index(); return 0; } 먼저 순차적으로 동적 배열을 사용하는 시뮬레이션 코드를 작성합시다. void Simul_Seq() { 먼저 동적 배열을 생성합니다. Array *arr = New_Array(); 그리고 도서 개체를 생성하여 순차적으로 동적 배열에 보관합니다. Array_PushBack(arr,New_Book("C언어","홍길동",10)); Array_PushBack(arr,New_Book("C..

5.1.2 동적 배열 구현 먼저 동적 배열을 생성하는 함수를 작성합시다. Array *New_Array() { 동적 배열 형식 크기의 메모리를 할당합니다. Array *arr = 0; arr = (Array *)malloc(sizeof(Array)); 자료를 보관할 저장소는 0으로 초기화합니다. 여기서 구현할 동적 배열은 저장소가 꽉 차면 내부적으로 저장소의 크기를 확장해 나갈 것입니다. arr->base = 0; 저장소에 용량과 보관한 자료 개수를 0으로 초기화한 후 동적 배열을 반환합니다. arr->capacity = arr->usage = 0; return arr; } 동적 배열을 소멸하는 함수를 작성합시다. void Delete_Array(Array *arr) { 만약 저장소가 유효하면 저장소를 ..