반응형

언어 자료구조 알고리즘/[C]디딤돌 자료구조와 알고리즘 39

[디딤돌 자료구조와 알고리즘] 5.4.1 스택 설계, 5.4.2 스택 구현, 5.4.3 스택 테스트

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)

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 큐 구현, 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) 설계

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

[디딤돌 자료구조와 알고리즘] 5.3 큐(QUEUE)

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

[디딤돌 자료구조와 알고리즘] 5.2 연결리스트 - 5.2.3 연결리스트 테스트

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

[디딤돌 자료구조와 알고리즘] 5.2 연결리스트 - 5.2.2 연결리스트 구현

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.2.1 연결리스트 설계

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

[디딤돌 자료구조와 알고리즘] 5.1 배열 - 5.1.3 동적 배열 테스트

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 배열 - 5.1.2 동적 배열 구현

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) { 만약 저장소가 유효하면 저장소를 ..

반응형