블로그 이미지

[C언어] 링크드 리스트로 구현한 int 저장형 큐 예제

2013. 11. 4. 01:57

'뇌를 자극하는 알고리즘' 의 링크드 큐 부분을 그대로 복사하여 int형에 맞게 수정한 것입니다.


LinkedQueue.h (헤더파일)

#ifndef LINKED_QUEUE_H #define LINKED_QUEUE_H #include <stdio.h> #include <stdlib.h> typedef struct tagNode { int Data; struct tagNode* NextNode; }Node; typedef struct tagLinkedQueue { Node* Front; Node* Rear; int Count; }LinkedQueue; void LQ_CreateQueue(LinkedQueue** Queue); void LQ_DestoryQueue(LinkedQueue** Queue); Node* LQ_CreateNode(int NewData); void LQ_DestoryNode(Node* _Node); void LQ_Enqueue(LinkedQueue* Queue, Node* NewNode); Node* LQ_Dequeue(LinkedQueue* Queue); int LQ_IsEmpty(LinkedQueue* Queue); #endif



LinkedQueue.c (헤더 구현파일)

#include <"LinkedQueue.h"

void LQ_CreateQueue(LinkedQueue** Queue)
{
	/* 큐를 자유 저장소에 생성 */
	(*Queue) = (LinkedQueue*)malloc(sizeof(LinkedQueue));
	(*Queue)->Front = NULL;
	(*Queue)->Rear = NULL;
	(*Queue)->Count = 0;
}
void LQ_DestoryQueue(LinkedQueue* Queue)
{
	while(!LQ_IsEmpty(Queue))
	{
		Node* Popped = LQ_Dequeue(Queue);
		LQ_DestoryNode(Popped);
	}
	/*	큐를 자유 저장소에서 해제 */
	free(Queue);
}
Node* LQ_CreateNode(int NewData)
{
	Node* NewNode = (Node*)malloc(sizeof(Node));

	NewNode->Data = NewData;	/* 데이터를 저장한다. */

	NewNode->NextNode = NULL;	/* 다음 노드에 대한 포인터는 NULL로 초기화한다. */
	
	return NewNode;	/* 노드의 주소를 반환한다. */
}
void LQ_DestoryNode(Node* _Node)
{
	free(_Node);
}
void LQ_Enqueue(LinkedQueue* Queue, Node* NewNode)
{
	if(Queue->Front == NULL)
	{
		Queue->Front = NewNode;
		Queue->Rear = NewNode;
		Queue->Count++;
	}else{
		Queue->Rear->NextNode = NewNode;
		Queue->Rear = NewNode;
		Queue->Count++;
	}
}
Node* LQ_Dequeue(LinkedQueue* Queue)
{
	/* LQ_Dequeue() 함수가 반환할 최상위 노드 */
	Node* Front = Queue->Front;

	if(Queue->Front->NextNode == NULL)
	{
		Queue->Front = NULL;
		Queue->Rear = NULL;
	}else{
		Queue->Front = Queue->Front->NextNode;
	}

	Queue->Count--;

	return Front;
}
int LQ_IsEmpty(LinkedQueue* Queue)
{
	return (Queue->Front == NULL);
}


Test_LinkedQueue.c
#include "LinkedQueue.h"

int main(void)
{
	Node* Popped;

	LinkedQueue* Queue;

	
	LQ_CreateQueue(&Queue);

	LQ_Enqueue(Queue, LQ_CreateNode(123));
	LQ_Enqueue(Queue, LQ_CreateNode(456));
	LQ_Enqueue(Queue, LQ_CreateNode(789));
	LQ_Enqueue(Queue, LQ_CreateNode(101));
	
	printf("Queue Size : %d\n\n", Queue->Count);
	
	while(LQ_IsEmpty(Queue) == 0)
	{
		Popped = LQ_Dequeue(Queue);
		printf("Dequeue: %d \n\n", Popped->Data);
		LQ_DestoryNode(Popped);
	}

	LQ_DestoryQueue(Queue);

	return 0;
}



  1. 야호야호123 2013.11.21 16:34  address  modify / delete  reply

    C#강의도 해주세[요


블로그 이미지

[정렬][C++] Template를 이용한 퀵 정렬(Quick Sort)

2013. 2. 14. 16:15

Quick Sort(퀵 정렬)

C++, Array Version (배열 버전)


Quick Sort Function(퀵 정렬 함수)

 // 첫번째 인자 : 배열
// 두번째 인자 : 무조건 1 (두번째 인자 Index)
// 세번째 인자 : 배열의 길이 + 1 (마지막 인자 Index)
// 네번째 인자 : Ascending 일 때 오름차순, Descending 일 때 내림차순
template<typename T, size_t n>
void sort_quick(T (&_input)[n], int Left, int Right, bool _option)
{
	int Base_Index = Left-1;	//가장 왼쪽의 값을 기준 값으로 잡음
	int Left_Index = Left;
	int Right_Index = Right;

	if(Right_Index <= Left_Index)
		return;

	while(Left_Index < Right_Index)
	{
		if(_option)
		{
			//오름차순
			//우측 포인터 부터 접근
			while((Left_Index < Right_Index) && (_input[Base_Index] < _input[Right_Index]))
			{
				Right_Index--;	
			}

			while((Left_Index < Right_Index) && (_input[Base_Index] > _input[Left_Index]))
			{
				Left_Index++;
			}
		}else{
			//내림차순
			//우측 포인터 부터 접근
			while((Left_Index < Right_Index) && (_input[Base_Index] > _input[Right_Index]))
			{
				Right_Index--;
			}
			while((Left_Index < Right_Index) && (_input[Base_Index] < _input[Left_Index]))
			{
				Left_Index++;
			}
		}
		Swap(_input[Left_Index], _input[Right_Index]);
	}

	//오름차순
	if(_option)
	{
		if(_input[Base_Index] > _input[Right_Index])
			Swap(_input[Base_Index], _input[Right_Index]);
	}else{
	//내림차순
		if(_input[Base_Index] < _input[Right_Index])
			Swap(_input[Base_Index], _input[Right_Index]);
	}
	
	//좌측 정렬 재귀함수 호출
	sort_quick(_input,Left ,Right_Index-1, _option);
	//우측 정렬 재귀함수 호출
	sort_quick(_input,Right_Index+1,Right, _option);
}



예제)

#include <iostream>

#define ARRAY_LENGTH(X) sizeof(X)/sizeof(X[0])
#define Ascending true
#define Descending false

template <typename T>
void Swap(T& _input1, T& _input2)
{
	T temp = _input1;
	_input1 = _input2;
	_input2 = temp;
}

// 첫번째 인자 : 배열
// 두번째 인자 : 무조건 1 (두번째 인자 Index)
// 세번째 인자 : 배열의 길이 + 1 (마지막 인자 Index)
// 네번째 인자 : Ascending 일 때 오름차순, Descending 일 때 내림차순
template<typename T, size_t n>
void sort_quick(T (&_input)[n], int Left, int Right, bool _option)
{
	int Base_Index = Left-1;	//가장 왼쪽의 값을 기준 값으로 잡음
	int Left_Index = Left;
	int Right_Index = Right;

	if(Right_Index <= Left_Index)
		return;

	while(Left_Index < Right_Index)
	{
		if(_option)
		{
			//오름차순
			//우측 포인터 부터 접근
			while((Left_Index < Right_Index) && (_input[Base_Index] < _input[Right_Index]))
			{
				Right_Index--;	
			}

			while((Left_Index < Right_Index) && (_input[Base_Index] > _input[Left_Index]))
			{
				Left_Index++;
			}
		}else{
			//내림차순
			//우측 포인터 부터 접근
			while((Left_Index < Right_Index) && (_input[Base_Index] > _input[Right_Index]))
			{
				Right_Index--;
			}
			while((Left_Index < Right_Index) && (_input[Base_Index] < _input[Left_Index]))
			{
				Left_Index++;
			}
		}
		Swap(_input[Left_Index], _input[Right_Index]);
	}

	//오름차순
	if(_option)
	{
		if(_input[Base_Index] > _input[Right_Index])
			Swap(_input[Base_Index], _input[Right_Index]);
	}else{
	//내림차순
		if(_input[Base_Index] < _input[Right_Index])
			Swap(_input[Base_Index], _input[Right_Index]);
	}
	
	//좌측 정렬 재귀함수 호출
	sort_quick(_input,Left ,Right_Index-1, _option);
	//우측 정렬 재귀함수 호출
	sort_quick(_input,Right_Index+1,Right, _option);
}

int main(void)
{
	char a[] = {'a','f','d','e','b','k','z','i','g','h','c','b'};

	sort_quick(a, 1, ARRAY_LENGTH(a)-1, Ascending);

	for(int i=0; i<ARRAY_LENGTH(a); i++)
	{
		std::cout << a[i] << " ";
	} 
} 



  1. wmfdod123 2016.05.13 20:58  address  modify / delete  reply

    이게 quicksort가 맞나요 bubble sort아닌가요??


블로그 이미지

[정렬] 매크로를 이용한 배열의 길이 계산

2013. 2. 12. 23:25

[자료구조][정렬] 매크로를 이용한 배열의 길이 계산

 #define ARRAY_LENGTH(X) sizeof(X) / sizeof(X[0])



예제 코드(C++용)

int main(void) { int test[] = {1, 5, 3, 6, 9, 11}; cout <<"배열의 길이는 "<<ARRAY_LENGTH(test)<<endl

} 



블로그 이미지

[정렬] 쉘 정렬 (Shell Sort)

2013. 1. 29. 16:43

알고리즘

쉘 정렬은 삽입 정렬의 단점을 보완하기 위해서 Donald Shell이 1958년 고안한 방법이다.
삽입 정렬은 Array 전체에 대해서 정렬을 수행하게 된다. 
최악의 경우, 다시말해서 오름차순 정렬을 해야하는데, Array가 내림차순 정렬이 되어있는 경우
연산이 많아지게 될 수 밖에 없다. 

쉘 정렬의 기본적인 아이디어는 삽입 정렬을 하기 전에 정리를 해놓자는 것이다.
그렇다면, 어떻게 정리할 것인가?
삽입 정렬은 모든 원소에 대해서 검사를 하지만,
쉘 정렬의 경우, 앞에서 구한 어떠한 간격만큼 떨어진 원소에 대해서 삽입정렬을 먼저 수행하고,
그 간격을 점점 줄여 계속 삽입정렬을 하는 방법을 취한다.
간격은 결국 1이 될 것이며, 1이 되는 때는 곧, 삽입 정렬을 수행하는 것과 동일하다.
하지만 이미 Array가 어느정도 정리 되어 있기 때문에, 삽입 정렬에 소모되는 연산이 줄어드는 것이다.

설명이 난해할 것 같아, 예제를 통해 설명을 이어나가도록 하겠다.

45, 39, 98, 15, 52, 44, 33, 28, 40, 38, 77, 68, 11, 43

위와 같은 정렬이 있다. 우리는 간격을 5, 3, 1로 놓고 삽입 정렬을 시작할 것이다.
간격이 5일 경우, 같은 묶음 끼리 같은 색으로 표시해 보면,

45, 3998, 15, 52, 44, 33, 28, 4038, 77, 681143

이제 각각의 묶음에 대해서 삽입 정렬을 한다. 즉, 

묶음1: 45, 44, 77
묶음2: 39, 33, 68
묶음3: 98, 28, 11
묶음4: 15, 40, 43
묶음5: 52, 38

위와 같은 5개의 묶음을 가지고 각각에 대해서 삽입 정렬을 하는 것이다.
정렬된 Array의 모습은 아래와 같다.

44, 3311, 15, 38, 45, 39, 28, 4052, 77, 689843

물론 각각의 묶음의 위치는 변동이 없다.
이제 3의 간격을 가지고 새로운 묶음을 만들어 보자.

44, 33, 11, 15, 3845, 39, 28, 40, 52, 77, 68, 98, 43

묶음1: 44, 15, 39, 52, 98
묶음2: 33, 38, 28, 77, 43
묶음3: 11, 45, 40, 68

이제 위 묶음들에 대해서 삽입 정렬을 수행한다.

15, 28, 11, 39, 3340, 44, 38, 45, 52, 43, 68, 98, 77

이제 대략적으로 작은 숫자들은 앞쪽, 큰 숫자들은 뒤쪽에 모여있는것을 볼 수 있다.
이제 묶음을 만들 필요 없이 전체 Array에 대해서 삽입 정렬을 하는 것으로 쉘 정렬이 마무리된다.



간격을 어떻게 설정할 것인가

위에서는 임의로 5, 3, 1이라는 간격을 사용했다.
이 간격을 어떻게 설정해 줄 것인가에 대한 문제가 상당히 고심이 되는 부분이 아닐 수 없다.

일단, 배열의 길이를 토대로 설정하는 방법을 생각해 볼 수 있다.
배열의 길이를 N이라고 잡았을 때,
첫번째 간격을 N/2, 두번째 간격을 N/4 ... 와 같이 잡는 방법이 있다.
(물론 각각의 간격을 int에 저장하면 소수점 이하는 소실된다. 길이가 23이라면 23, 11, 5, 2, 1 과 같이 될 것이다.)

N/3, N/9 ... 와 같이 잡을 수도 있다.
(길이가 23이라면, 23, 7, 2, 1 과 같이 된다.)

Donald Shell은 처음에 간격을 2^k, (k는 0 이상의 자연수) 혹은 2^k-1로 잡았으며,
Marcin Ciura의 연구에 의하면  1, 4, 10, 23, 57, 132, 301, 701, 1750 ... 과 같은 간격을 사용하는 것이 
연산 시간을 많이 줄인다고 한다.

아래의 코드는 간격을 N/3 - 1로 잡고 코딩을 한 것이다.



코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>
 
void shell_sort(int num[],int len);
void tracer(int num[],int len);
 
int main(void){
    int testArr[] = {485,241,454,325,452,685,498,890,281};
    int len = sizeof(testArr)/sizeof(int);
    shell_sort(testArr,len);
}
 
void shell_sort(int num[],int len){
    int i,j,m,tempINT;
    int k = len;
    do {
        k = k/3 + 1; // 다음 간격을 k/3 + 1로 구함
        printf("간격 k = %d\n",k); // 간격을 보여준다.
        for (m=0; m<k; m++){ //m은 각 묶음의 첫 인덱스가 된다.
            for (i=m+k; i<len; i+=k){
                // 삽입정렬은 첫번째 원소를 정렬된 것으로 간주함
                // 따라서 첫 인텍스는 m+k가 된다.
                tempINT = num[i];
                for(j=i-k; num[j] > tempINT && j>=0; j-=k){
                    num[j+k] = num[j];
                }
                num[j+k] = tempINT;
                // 나머지 부분은 삽입 정렬과 같다.
            }
        }
        tracer(num,len);
    } while (k != 1); // k가 1이 되면, 더 이상 정렬할 필요 없음
}
 
void tracer(int num[],int len){
    int i;
    for(i=0;i<len;i++){
        printf("%d\t",num[i]);
    }
    printf("\n\n");
}