언제나 휴일

4.3.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는 앞쪽 배열의 인덱스로 사용할 것이므로..

4.2 이진 탐색 알고리즘 이번에는 이진 탐색 알고리즘을 알아봅시다. 이진 탐색 알고리즘은 특정 키순으로 정렬 상태의 배열에서 원하는 값의 요소를 빠르게 검색하는 알고리즘입니다. 순차적으로 비교하여 검색한다면 자료의 개수가 N개인 배열에서 최악의 경우 N번 비교해야 합니다. 하지만 이진 탐색 알고리즘으로 검색하면 logN 번이면 검색할 수 있습니다. 이진 탐색 알고리즘은 배열의 중간에 있는 요소와 비교해서 배열의 요소가 크면 재귀적으로 앞쪽 배열에서 검색하고 배열의 요소가 작으면 재귀적으로 뒤쪽 배열에서 검색합니다. 만약 같은 값이면 해당 인덱스를 반환합니다. 그리고 배열의 원소 개수가 0이면 재귀를 탈출하기 위해 인덱스 -1을 반환합니다. 이진 탐색 알고리즘(base:배열, asize:원소 개수, ke..

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

3. 2 하노이 타워 재귀 알고리즘 중에 하노이 타워가 있습니다. 하노이 타워 알고리즘은 n 개의 돌을 이동시키는 문제입니다. 세 개의 기둥이 있고 하나의 기둥에 n 개의 돌이 크기 순으로 있습니다. 한 번에 하나의 돌을 이동할 수 있고 작은 돌 위에 큰 돌이 올 수 없습니다. 이와 같은 규칙을 이용하여 n 개의 돌이 있는 기둥에서 다른 기둥으로 모든 돌을 옮기는 문제입니다. [그림 3.1] 하노이 타워 이 문제를 재귀적으로 해결하면 다음과 같은 방법으로 해결할 수 있습니다. 가정: n-1개의 돌을 옮길 수 있다.가정에 의해 먼저 A에 있는 n-1개의 돌을 C를 이용하여 B로 옮깁니다.규칙에 의해 1개의 돌을 A에서 C로 옮깁니다.가정에 의해 B에 있는 n-1개의 돌을 A를 이용하여 C로 옮깁니다.따라서..

2.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])

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

2.2.2 순차 정렬 알고리즘 구현 이번에는 순차 정렬 알고리즘을 구현해 보기로 해요.순차 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리) 반복(i:=0->n) 반복(j:=i+1->n) 조건(compare(base[i], base[j]) > 0) 교환(base[i],base[j]) 이번에는 버블 정렬 알고리즘을 구현하는 예를 보여드릴게요. 먼저 공통으로 사용할 파일을 프로젝트 폴더에 복사한 이후에 프로젝트에 추가하세요. 그리고 헤더 파일을 포함합니다. 이후의 작업에서는 언제나 필요하며 별다른 언급을 하지 않겠습니다.#include "Book.h" 여기에서 정의할 버블 정렬은 원소 형식에 관계없이 동적으로 생성한 개체의 집합을 정렬하게 정의할 것입니다. 이를 위해 void *..

이진 탐색 트리 운행, C언어 소스 //이진 탐색 트리 운행#include #include typedef struct Node//노드 정의{ int data; struct Node *lchild; struct Node *rchild;}Node; typedef Node *Tree;//트리 형식명 정의 Node *NewNode(int data);//노드 생성void InitTree(Tree *bst);//트리 초기화int AddData(Tree *bst, int data); //데이터 보관void Preorder(Node *sr);//전위 순위 운행void Inorder(Node *sr);//중위 순위 운행void Postorder(Node *sr);//후위 순위 운행void ClearTree(Tree *b..

이중 연결리스트 - 정렬 상태로 보관, C언어 소스 //이중 연결리스트 - 정렬 상태로 보관//연결리스트 정의, 노드 정의, 초기화, 추가, 삭제, 검색, 전체 출력, 해제#include #include typedef struct Node//노드 정의{ int data;//데이터 struct Node *next;//링크(다음 노드의 위치 정보) struct Node *prev;//링크(이전 노드의 위치 정보)}Node; Node *NewNode(int data){ Node *now = (Node *)malloc(sizeof(Node)); now->data = data; now->prev = now->next = NULL; return now;} typedef struct List//연결리스트 정의{ No..