언제나 휴일

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

5. 선형 자료구조 이번 장에서는 선형 자료구조에 관하여 살펴봅시다. 이미 앞 장에서 비선형 자료구조인 이진 탐색 트리는 살펴보았습니다. 선형 자료구조는 자료를 보관하는 논리적인 구조를 하나의 선으로 나타낼 수 있습니다. 대표적인 선형 자료구조에는 배열과 연결리스트, 스택과 큐가 있습니다. 배열은 같은 형태의 자료를 연속적인 메모리에 관리하는 자료구조입니다. 그리고 연결리스트는 노드의 선형 집합이며 노드는 하나의 자료와 다른 노드의 위치 정보인 링크로 구성합니다. 스택과 큐는 단순히 자료를 보관하고 꺼내는 동작을 제공하며 스택은 최근에 보관한 자료를 꺼내는 LIFO(Last In First Out), 큐는 먼저 보관한 자료를 꺼내는 FIFO(First In First Out) 구조입니다. 관련 게시글 [..

스택과 큐, 데크 스택(Stack) 가장 최근에 보관한 자료를 먼저 꺼내는 LIFO(Last In First Out)방식의 자료 구조이다. 리스트의 한쪽으로 삽입과 삭제 연산을 수행한다. 스택의 특징 가장 최근에 자료를 보관한 위치를 기억하며 Top이라 부른다. 자료를 보관하는 연산을 Push라고 부른다. 자료를 꺼내는 연산을 Pop이라 부른다. Push 연산 IF Top>= MAX Then //꽉 차면 Overflow //버퍼 오버플로우 Else //꽉 차지 않을 때 Top = Top +1 //Top 위치를 1 증가 Buffer[Top] = data //버퍼의 Top 위치에 data 보관 Pop 연산 IF Top=0 Then //비었으면 Underflow //버퍼 언더플로우 Else data = Buf..

디딤돌 자료구조와 알고리즘 C++ 책 소개 자료구조는 자료를 메모리에 표현하는 구조를 말하며 크게 선형 자료구조와 비 선형 자료구조로 나눠요. 선형 자료구조에는 같은 종류의 자료를 연속적인 메모리에 관리하는 배열과 데이터와 링크로 구성하는 노드들의 선형 집합인 연결리스트가 있어요. 그리고 임시적으로 자료를 보관하는 버퍼로 가장 최근에 보관한 자료를 꺼내주는 스택(Last In First Out)과 가장 먼저 보관한 자료를 꺼내주는 큐(First In First Out)도 선형 자료구조인 배열이나 연결리스트를 이용한 잘 알려진 버퍼입니다. 비 선형 자료구조에는 나무의 뿌리처럼 자료를 보관하는 모습을 계층적으로 표현할 수 있는 트리와 정점과 간선으로 표현하는 그래프 등이 있어요. 이 책에서는 이러한 자료구조..

3.5 큐를 이용한 스케쥴러 시뮬레이션 이번에는 큐를 이용하는 스케쥴러를 시뮬레이션 형태로 만들어 보아요. 여기서 작성할 시뮬레이션은 CPU가 하나 있는 컴퓨터 시스템에서 라운드 로빈 방식의 스케쥴러의 동작을 표현합시다. 스케쥴러는 컴퓨터 내에 여러 개의 프로세스(동작 중인 프로그램)중에서 누가 CPU를 사용할 것인지를 결정하는 운영체제의 핵심 모듈이죠. (참고로 Windows 운영 체제는 스케쥴링 대상이 쓰레드입니다.) 그 중에 라운드 로빈 방식의 스케쥴러는 시스템 내에 정해진 시간(타임 퀀텀)동안 CPU를 사용한 후 다시 대기 큐에 가서 대기하고 맨 앞에 대기하는 프로세스가 CPU를 점유하여 사용하게 운용해요. 여기에서는 프로세스의 상태를 Idel(휴먼 상태), Ready(준비 상태), Run(동작 ..

3.4 큐(Queue) 이번에는 큐를 알아보기로 해요. 큐는 자료를 한쪽으로 보관하고 다른쪽에서 꺼내는 FIFO(First In First Out) 방식의 자료구조입니다. 큐에 자료를 보관하는 연산을 PUT 혹은 ENQUEUE라 말하고 꺼내는 연산을 GET 혹은 DEQUEUE라고 말합니다. 그리고 보관할 위치 정보를 REAR, 꺼낼 위치 정보를 FRONT라고 말해요. 먼저 간단하게 보관하는 큐를 만들어 보기로 해요. class Queue { 여기에서는 자료를 저장할 버퍼를 생성할 때 정하기로 할게요. 버퍼의 위치를 기억할 멤버를 선언하세요. int *buffer; 버퍼의 크기를 기억할 멤버도 필요하겠죠. const int size; 자료를 꺼낼 위치 정보도 기억해야 합니다. int front; 자료를 보..

큐 - 연결리스트 이용, C언어 소스 //큐 - 연결리스트 이용#include #include #include typedef struct Node //노드 정의{ int data; struct Node *next;}Node; #define NEXT(index,QSIZE) ((index+1)%QSIZE) //원형 큐에서 인덱스를 변경하는 매크로 함수 typedef struct Queue //Queue 구조체 정의{ Node *front; //맨 앞(꺼낼 위치) Node *rear; //맨 뒤(보관할 위치) int count;//보관 개수}Queue; void InitQueue(Queue *queue);//큐 초기화int IsEmpty(Queue *queue); //큐가 비었는지 확인void Enqueue(..