fullstack

'자료구조'에 해당되는 글 4건

  1. [C++] 이진 검색 구현
  2. [C++] Bubble Sort 구현
  3. [C++] 간단한 Queue 만들기
  4. [C++] 간단한 Stack 만들기

[C++] 이진 검색 구현

자료구조

이진 검색 알고리즘은 정렬된 리스트에서 특정한 값의 위치를 찾기위해 찾을 값과 현재 유효한 값의 범위의 중간값을 비교해 범위를 좁히는 식으로 검색하여 빠르게 목표값을 찾을 수 있는 장점이 있다.


1
2
3
4
5
6
7
8
9
10
11
12
int binarySearch(int arr[], int size, int find)
{
    int low=0, high=size-1, mid;
    while(low<=high)
    {
        mid = (low+high)/2;
        if(arr[mid] > find) high = mid - 1;
        else if(arr[mid] < find) low = mid + 1;
        else return mid;
    }
    return -1;
}



#4 low가 high보다 커진다면 찾으려는 데이터가 없다는 것이다.

#11 목표값이 없을 경우에는 -1을 리턴해 준다.

저작자표시

'자료구조' 카테고리의 다른 글

[C++] Bubble Sort 구현  (0) 2015.11.12
[C++] 간단한 Queue 만들기  (0) 2015.11.12
[C++] 간단한 Stack 만들기  (0) 2015.11.11
,

[C++] Bubble Sort 구현

자료구조

정렬기법중 버블소트는 시간복잡도가 n제곱으로 상당히 비효율적이지만 코드가 단순해서 가장 많이 사용된다.


len만큼의 길이를 가진 배열 arr을 오름차순으로 정렬하고 싶다면 다음과 같다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void bubbleSort(int arr[], int len)
{
    for(int i=0; i<len; i++)
    {
        for(int j=0; j<len-1-i; j++)
        {
            if(arr[j] > arr[j+1])
            {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}



저작자표시

'자료구조' 카테고리의 다른 글

[C++] 이진 검색 구현  (0) 2015.11.16
[C++] 간단한 Queue 만들기  (0) 2015.11.12
[C++] 간단한 Stack 만들기  (0) 2015.11.11
,

[C++] 간단한 Queue 만들기

자료구조

Queue는 Stack과 반대로 먼저 넣은 데이터가 먼저나오는 FIFO(First In First Out) 형태의 자료구조이다.

선형큐는 빈공간을 사용하면 모든자료를 한칸씩옮겨야하는 단점이 있기 때문에 원모양으로 이어지는 환형큐를 사용하는 것이 좋다.


가장 경량화된 환형큐를 구현해 보았다.


1
2
3
4
5
6
7
8
9
10
11
class myQueue {
private:
    int arr[maxQueueSize];
    int front, rear;
public:
    void init() { front = 0; rear = 0; }
    void enq(int item) { if(!isFull()) arr[++rear%maxQueueSize] = item; }
    int deq() { if(!isEmpty()) return arr[++front%maxQueueSize]; }
    bool isEmpty() { return front==rear?true:false; }
    bool isFull() { return (rear+1)%maxQueueSize==front?true:false; }
};



저작자표시

'자료구조' 카테고리의 다른 글

[C++] 이진 검색 구현  (0) 2015.11.16
[C++] Bubble Sort 구현  (0) 2015.11.12
[C++] 간단한 Stack 만들기  (0) 2015.11.11
,

[C++] 간단한 Stack 만들기

자료구조

Stack은 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 LIFO(Last In First Out) 형태의 자료구조이다.


가장 경량화된 스택을 구현해 보았다.


1
2
3
4
5
6
7
8
9
10
11
class myStack {
private:
    int arr[maxStackSize];
    int idx;
public:
    void init() { idx = 0; }
    void push(int item) { arr[idx++] = item; }
    int pop() { return arr[--idx]; }
    bool isEmpty() { return idx==0?true:false; }
    bool isFull() { return idx==maxStackSize?true:false; }
};




저작자표시

'자료구조' 카테고리의 다른 글

[C++] 이진 검색 구현  (0) 2015.11.16
[C++] Bubble Sort 구현  (0) 2015.11.12
[C++] 간단한 Queue 만들기  (0) 2015.11.12
,

티스토리툴바