반응형

언어 자료구조 알고리즘/디딤돌 자료구조 (C언어) 39

[C언어 자료구조] 5. 스택(Stack)

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

[C언어 자료구조] 4.4 큐 소스 코드

[C언어 자료구조] 4.4 큐 소스 코드//common.h #pragma once //헤더 파일을 한 번만 포함해서 컴파일 #include #include #include #include #include #include #include #pragma warning(disable:4996) //4996컴파일 경고 메시지 출력 해제 //Book.h #pragma once #include "common.h" #define MAX_TIT_LEN 200 #define MAX_AUT_LEN 20 typedef struct _Book Book; struct _Book { char title[MAX_TIT_LEN+1]; char author[MAX_AUT_LEN+1]; int num; }; Book *New_Book(..

[C언어 자료구조] 4.3 큐 테스트

[C언어 자료구조] 4.3 큐 테스트 큐를 테스트하는 코드를 작성합시다. int main() { EHQueue *ehq = 0; Book *book = 0; 먼저 동적으로 큐를 생성합니다. ehq = New_EHQueue(); 그리고 큐에 자료를 보관합니다. EHQueue_Put(ehq,New_Book("C언어","홍길동",10)); EHQueue_Put(ehq,New_Book("C++언어","강감찬",20)); EHQueue_Put(ehq,New_Book("자료구조","김구",5)); 이 상태에서 꺼내면 가장 먼저 보관한 "C언어" 제목의 도서여야 합니다. 이를 확인해 봅시다. book = (Book *)EHQueue_Get(ehq); if(book) { Book_View(book); Delete_Bo..

[C언어 자료구조] 4.2 큐 구현

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

[C언어 자료구조] 4.1 큐 설계

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

[C언어 자료구조] 4. 큐(Queue)

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

[C언어 자료구조] 3.4 연결리스트 소스 코드

[C언어 자료구조] 3.4 연결리스트 소스 코드//common.h #pragma once //헤더 파일을 한 번만 포함해서 컴파일 #include #include #include #include #include #include #include #pragma warning(disable:4996) //4996컴파일 경고 메시지 출력 해제 //Book.h #pragma once #include "common.h" #define MAX_TIT_LEN 200 #define MAX_AUT_LEN 20 typedef struct _Book Book; struct _Book { char title[MAX_TIT_LEN+1]; char author[MAX_AUT_LEN+1]; int num; }; Book *New_B..

[C언어 자료구조] 3.3 연결리스트 테스트

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

[C언어 자료구조] 3.2 연결리스트 구현

[C언어 자료구조] 3.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..

[C언어 자료구조] 3.1 연결리스트 설계

[C언어 자료구조] 3.1 연결리스트 설계 동적 배열처럼 연결리스트도 동적으로 생성한 개체는 형식에 관계없이 보관할 수 있게 정의할게요. 사용하기 편리하게 void * 형식을 Element 형식으로 타입 재지정할게요. typedef void * Element; 연결리스트는 노드의 선형 집합입니다. 노드는 링크와 데이터의 조합으로 여기에서는 두 개의 링크를 갖는 노드를 정의할 것입니다. typedef struct _Node Node; typedef Node *Link; struct _Node { Link next; Link prev; Element data; }; 연결리스트 구조체에는 맨 앞에 있는 더미 노드의 위치 정보인 head와 맨 뒤에 있는 더미 노드의 위치 정보인 tail과 보관한 자료 개수를 멤..

반응형