언제나 휴일

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

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

[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언어 자료구조] 2.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,Ne..

[C언어 자료구조] 2.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){ 만약 저장소가 유효하면 저..

6.2 병합 정렬 알고리즘 구현 이제 병합 정렬 알고리즘을 구체적으로 구현합시다. #include "common.h" #include "Book.h" typedef void *Element; typedef int (*Compare)(Element , Element); void merge_sort(Element *base, int n, Compare compare) { n의 절반의 크기를 ahalf에 기억합니다. 이는 배열을 분할할 때 앞쪽 배열의 원소 개수입니다. int ahalf = n/2; 배열을 분할할 때 뒤쪽 배열의 원소 개수를 bhalf에 기억합니다. int bhalf = n - ahalf; 분할할 배열을 하나의 배열로 정복하기 위한 인덱스를 선언합니다. ai는 앞쪽 배열의 인덱스로 사용할 것이..

5.2 퀵 정렬 알고리즘 구현 앞에서 만들었던 정렬 알고리즘과 같은 방법으로 시뮬레이션 코드를 작성합니다. 여기에서는 퀵 정렬 알고리즘만 구현할게요. 참고로 퀵 정렬 알고리즘을 내부 알고리즘을 별도의 함수로 구현하지 않고 직접 구현할게요. 정렬 알고리즘은 수행 속도가 중요한 이슈이므로 복잡하더라도 하나의 함수로 구현할게요. void quick_sort(Element *base, int n, Compare compare) { 먼저 교환에 사용할 임시 변수와 피벗의 위치와 피벗보다 큰 값과 작은 값의 위치를 기억하기 위한 변수를 선언합시다. Element temp;//교환을 위한 임시 변수 int pivot = 0; //피벗의 위치를 기억하기 위한 변수 int big=0, small=0; //피벗보다 큰 값..

4.2 삽입 정렬 알고리즘 구현 삽입 정렬 알고리즘을 구현합시다. 시뮬레이션 함수 등은 앞과 같으므로 설명을 생략할게요. void insertion_sort(Element *base, int n, Compare compare) { 두 개의 반복문에서 사용할 변수를 선언하고 교환에 사용할 임시 변수도 선언할게요. int i = 0, j=0; Element temp; 외부 반복문은 정렬할 범위를 넓혀나가는 것입니다. 따라서 i를 1부터 n까지 점진적으로 증가할게요. for(i=1; i0; j--) { 만약 j번째 원소가 앞의 원소보다 크면 자리를 교환합니다. if(compare(base[j-1],base[j])

3.2 선택 정렬 알고리즘 구현이제 선택 정렬 알고리즘을 구현합시다. void select_sort(Element *base, int n, Compare compare) { 먼저 내부 반복문과 외부 반복문에서 사용할 두 개의 변수를 선언하세요. int i = 0, j=0; 그리고 최대값이 있는 위치를 기억할 변수도 선언합니다. 그리고 교환에서 사용할 임시 변수도 선언하세요. int max=0; Element temp; 외부 반복문에서는 정렬할 범위를 점진적으로 줄여나갑니다. for(i=n; i>1; i--) { 내부 반복문에서는 max를 0으로 초기화하고 j를 1로 초기화합니다. 이는 일단 맨 앞에 있는 요소를 최대값이 있는 위치로 설정하고 그 다음 요소부터 최대값과 비교하기 위해서입니다. 그리고 j는 ..

2.2 버블 정렬 알고리즘 구현 이번에는 버블 정렬 알고리즘을 구현하는 예를 보여드릴게요. 먼저 공통으로 사용할 파일을 프로젝트 폴더에 복사한 이후에 프로젝트에 추가하세요. 그리고 헤더 파일을 포함합니다. 이후의 작업에서는 언제나 필요하며 별다른 언급을 하지 않겠습니다. #include "Book.h" 여기에서 정의할 버블 정렬은 원소 형식에 관계없이 동적으로 생성한 개체의 집합을 정렬하게 정의할 것입니다. 이를 위해 void * 형식을 Element 형식 이름으로 정의할게요. typedef void *Element; typedef int (*Compare)(Element , Element); 버블 정렬은 n개의 원소가 있는 배열의 주소와 원소 개수 및 비교 알고리즘을 입력 인자로 필요합니다. void ..