[자료구조] c++ 스택
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 | #include <iostream> template <class T> typedef struct Node{ int data; }Node; class Stack{ private: Node node; int size; int num; public: Stack(int size){ this->size = size; num = 0; node = new node[size]; } void push(int in){ node[num++]->data = in; } int pop(){ return node[--num]; } bool isempty(){if(num == 0) return true;} } | cs |
'개발 > 자료구조' 카테고리의 다른 글
| [자료구조] [C++] CircularQueue 사이클 큐 (0) | 2016.11.16 |
|---|---|
| q_sort (1) | 2016.11.16 |
| [자료구조] Select Sort (0) | 2016.10.26 |
| Recursive 를 이용한 Permutation Generator (순열 생성기) (0) | 2016.10.25 |
| Binary Search 이진 탐색 (0) | 2016.10.25 |
[자료구조] [C++] CircularQueue 사이클 큐
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 41 42 43 44 45 46 47 48 49 50 | #include<iostream> #include<string> typedef struct Node { std::string data; }Node; class cir_queue { private: Node* node; int size; int front; int back; public: cir_queue(int size) { this->size = size + 1; //더미 공간 node = new Node[this->size]; front = 0; back = 0; } void enqueue(std::string data) { int index; if (back == size - 1){ index = back; back = 0; } else { index = back++; } node[index].data = data; } std::string dequeue() { int index = front; if (front == size - 1) front = 0; else front++; return node[index].data; } int get_size() { if (front <= back) return back - front; else return size - front + back; } }; | cs |
'개발 > 자료구조' 카테고리의 다른 글
| [자료구조] c++ 스택 (0) | 2016.11.17 |
|---|---|
| q_sort (1) | 2016.11.16 |
| [자료구조] Select Sort (0) | 2016.10.26 |
| Recursive 를 이용한 Permutation Generator (순열 생성기) (0) | 2016.10.25 |
| Binary Search 이진 탐색 (0) | 2016.10.25 |
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 41 42 43 44 45 | //q_sort #include <iostream> void qsort(int num[], int left, int right) { int pivot = num[(left+right) / 2]; //중앙 값 int l = left; int r = right; while (l < r) { while (pivot > num[l]) l++; while (pivot < num[r]) r--; if (l <= r) { int ch = num[l]; num[l] = num[r]; num[r] = ch; l++; r--; } } if (left < r) qsort(num, left, r); if (right > l) qsort(num, l, right); } int main(void) { int n[8] = { 67, 90, 57, 25, 84, 32, 73, 54 }; qsort(n, 0, 7); for (int i = 0; i < 8; i++) { std::cout << n[i] << " "; } std::cout << std::endl; return -1; } |
'개발 > 자료구조' 카테고리의 다른 글
| [자료구조] c++ 스택 (0) | 2016.11.17 |
|---|---|
| [자료구조] [C++] CircularQueue 사이클 큐 (0) | 2016.11.16 |
| [자료구조] Select Sort (0) | 2016.10.26 |
| Recursive 를 이용한 Permutation Generator (순열 생성기) (0) | 2016.10.25 |
| Binary Search 이진 탐색 (0) | 2016.10.25 |
[자료구조] Select Sort
Select sort는 정렬이 되지 않은 전체 배열에서 하나를 선택하여 위치를 교환하는 정렬방법이다.
1) 7[0] 을 선택한 뒤 배열 [1]~[6] 까지 중 가장 작은 수를 선택한다. 가장 작은 수 = 1[6]
2) 가장 작은 수 1[6]과 7[0]의 자리를 swap 한다.
3) 그다음 4[1]를 선택한 뒤 배열 [2]~[6] 가장 작은 수를 선택한다. 가장 작은 수 = 2[5]
4) 끝에 도달할 때 까지 반복한다.
ex)
void sort(int *a, const int n)
{ // Sort the n integers a[0] to a[n-1] into nondecreasing order.
for (int i = 0; i < n; i++)
{
int j = i;
// find smallest integer in a[i] to a[n-1]
for (int k = i + 1; k < n; k++)
if (a[k] < a[j]) j = k;
swap(a[i], a[j]);
}
}
'개발 > 자료구조' 카테고리의 다른 글
| [자료구조] c++ 스택 (0) | 2016.11.17 |
|---|---|
| [자료구조] [C++] CircularQueue 사이클 큐 (0) | 2016.11.16 |
| q_sort (1) | 2016.11.16 |
| Recursive 를 이용한 Permutation Generator (순열 생성기) (0) | 2016.10.25 |
| Binary Search 이진 탐색 (0) | 2016.10.25 |
Recursive 를 이용한 Permutation Generator (순열 생성기)
perm(a, b, c, d);
1) a + perm(b, c, d)
2) b + perm(a, c, d)
3) c + perm(a, b, d)
4) d + perm(a, b, c)
perm(b, c, d)
1) b + perm(c, d)
2) c + perm(b, d)
3) d + perm(b, c)
perm(c, d)
1) c + perm(d)
2) d + perm(c)
perm(a, 0, n) → a[0], a[1], ⋯, a[n-1]
소스 C++)
void Permutations (char *a, const int k, const int m)
{// Generate all the permutations of a[k], ..., a[m].
if (k == m) { // output permutation
for (int i = 0; i <= m; i++) cout << a[i] << “ “;
cout << endl;
}
else // a[k:m] has more than one permutation. Generate these recursively
for (int i = k; i <= m; i++) {
swap(a[k], a[i]);
Permutations(a, k+1, m);
swap(a[k], a[i]);
}
}
'개발 > 자료구조' 카테고리의 다른 글
| [자료구조] c++ 스택 (0) | 2016.11.17 |
|---|---|
| [자료구조] [C++] CircularQueue 사이클 큐 (0) | 2016.11.16 |
| q_sort (1) | 2016.11.16 |
| [자료구조] Select Sort (0) | 2016.10.26 |
| Binary Search 이진 탐색 (0) | 2016.10.25 |
Binary Search 이진 탐색
Binary Search란
< 그림으로 설명 >
[이진 탐색]
left, right: 배열(a[0], a[1], ⋯, a[n-1])의 왼쪽, 오른쪽 끝 지점
초기 값으로 left = 0, right = n-1
list의 중간 위치 middle = (left + right) / 2로 설정
a[middle]과 x를 비교할 경우 3가지 경우 중에 하나를 고려
⑴ x > a[middle]: left를 middle+1로 설정
⑵ x < a[middle]: right를 middle-1로 설정
⑶ x = a[middle]: middle을 반환
예시) C++
int BinarySearch (int *a, const int x, const int n){ // x - 찾으려는 값, n = 배열의 원소 수 or 찾으려는 배열의 크기
int left = 0, right = n -1;
// 찾거나 left가 right 넘어갈 경우 멈춘다.
while(left <= right){
int middle = (left + right) / 2; //중간위치 항상
if(x > a[middle]) left = middle + 1 ;
else if (x < a[middle]) right = middle - 1;
else return middle //찾앗다.
}
//못 찾았다.
return -1;
}
'개발 > 자료구조' 카테고리의 다른 글
| [자료구조] c++ 스택 (0) | 2016.11.17 |
|---|---|
| [자료구조] [C++] CircularQueue 사이클 큐 (0) | 2016.11.16 |
| q_sort (1) | 2016.11.16 |
| [자료구조] Select Sort (0) | 2016.10.26 |
| Recursive 를 이용한 Permutation Generator (순열 생성기) (0) | 2016.10.25 |
