четверг, 13 июня 2013 г.

Insert Sort (Сортировка вставками)


Сортировка вставками:
template <typename T>
void insertSort(T arr[], int left, int right)
{
int j = 0;
for (int i = left; i < right; ++i)
{
j = i;
T tmp = arr[i];
while (arr[j - 1] > tmp && j > 0 )
{
arr[j] = arr[j - 1];
--j;
}
arr[j] = tmp;
}
}

Selection Sort (Сортировка выбором)

Идея: ищем наименьший элемент - ставим на первое место массива, ищем второй наименьший элемент - ставим на второе место и т.д.  Причем кол-во итераций поиска следующего наименьшего элемента равно N - 1, т.к. последний элемент после сортировки предыдущих и так будет на своем месте.

Функция меняющая позиции двух элементов: 


template<typename T>
void mySwap(T &first, T &second)
{
T tmp = first;
first = second;
second = tmp;
}

Сортировка выбором:
template <typename T>
void selectionSort(T arr[], int left, int right)
{
for (int i = left; i < right - 1; ++i)
{
int min = i;
for (int j = i + 1; j < right; ++ j)
{
if (arr[min] > arr[j])
{
min = j;
}
}
mySwap(arr[min], arr[i]);
}
}

пятница, 7 июня 2013 г.

Наибольший общий делитель (greatest сommon divisor)

Функция находит наибольший общий делитель при first > second


int greatestCommonDivisor(int first, int second)
{
if (second == 0)
{
return first;
}
return greatestCommonDivisor(second, first % second);
}

Random Queue (имитация неупорядоченной очереди)

Из данной очереди элементы удаляются в случайном порядке.


#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;

template<typename T>
class RandomQueue
{
public:
RandomQueue(int size);
~RandomQueue();

void put(T item);
T get();
bool empty();
private:
T *m_random;
T m_head;
T m_tail;
T m_tmp;
};

template<typename T>
RandomQueue<T>::RandomQueue(int size)
{
m_tmp = size + 1;
m_head = m_tmp;
m_tail = 0;
m_random = new T[size + 1];
}

template<typename T>
RandomQueue<T>::~RandomQueue()
{
delete[] m_random;
}

template<typename T>
void RandomQueue<T>::put(T item)
{
if (m_tail < m_tmp - 1)
{
m_random[m_tail++] = item;
}
else
{
cout << "Queue is fill" << endl;
}
}

template<typename T>
T RandomQueue<T>::get()
{
if(m_tail > 0)
{
T outputItem;
srand(time(0));
m_head = rand()%m_tail;

outputItem = m_random[m_head];
for (int i = m_head; i < m_tail; ++i) //Смещаем все элементы на один влево
{                                                   //Заполняя получившийся пробел
m_random[i] = m_random[i + 1];
}
--m_tail;   //Номер хвоста

return outputItem;
}
}

template<typename T>
bool RandomQueue<T>::empty()
{
return (m_tail == 0);
}

среда, 5 июня 2013 г.

QUEUE (Реализация упрощенной очереди через список)


#include <iostream>
using namespace std;

template<typename T>
class MyQueue
{
public:
MyQueue();

void put(T item);
T get();
bool empty();
private:
struct Node
{
T m_item;
Node *m_next;
Node(T item);
};
Node *m_head;
Node *m_tail;
};

template<typename T>
MyQueue<T>::Node::Node(T item)
{
m_item = item;
m_next = 0;
}

template<typename T>
MyQueue<T>::MyQueue()
{
m_head = 0;
m_tail = 0;
}

template<typename T>
void MyQueue<T>::put(T item)
{
Node *tmp = m_tail;
m_tail = new Node(item);
(0 == m_head) ? m_head = m_tail : tmp->m_next = m_tail;
}

template<typename T>
T MyQueue<T>::get()
{
T tmpItem = m_head->m_item;
Node *tmp = m_head->m_next;

delete m_head;
m_head = tmp;

return tmpItem;
}

вторник, 4 июня 2013 г.

Стек (упрощенная реализация)

в  файле MyStack.h :


#include <iostream>
using namespace std;

template<typename T>
class MyStack
{
public:
MyStack();
MyStack(int size);
MyStack(const MyStack<T> &over);
~MyStack();
MyStack<T>& operator=(const MyStack<T> &over);

T pop();
void push(T item);
bool empty() const;
private:
int m_top;
int m_size;
T *m_stack;
};

template<typename T>
MyStack<T>::MyStack()
: m_top(-1)
, m_size(10) // по умолчанию стек на 10 элементов
{
m_stack = new T[m_size];
}

template<typename T>
MyStack<T>::MyStack(int size)
: m_top(-1)
, m_size(size)
{
m_stack = new T[m_size];
}

template<typename T>
MyStack<T>::~MyStack()
{
delete[] m_stack;
}

template<typename T>
MyStack<T>::MyStack(const MyStack<T> &over)
{
m_top = over.m_top;
m_size = over.m_size;
m_stack = new T[m_size];

for (int i = 0; i <= m_top; ++i)
{
m_stack[i] = over.m_stack[i];
}
}

template<typename T>
MyStack<T>& MyStack<T>::operator=(const MyStack<T> &over)
{
if (this != &over)
{
m_top = over.m_top;
m_size = over.m_size;

delete[] m_stack;
m_stack = new T[m_size];

for (int i = 0; i <= m_top; ++i)
{
m_stack[i] = over.m_stack[i];
}
}
return *this;
}

template<typename T>
T MyStack<T>::pop()
{
if (-1 != m_top)
{
return m_stack[m_top--];
}
else
{
cout << "Stack is empty ";
cout << endl;
}
}

template<typename T>
void MyStack<T>::push(T item)
{
if ( m_top != m_size - 1)
{
m_stack[++m_top] = item;
}
else
{
cout << "Stack is fill ";
cout << endl;
}
}

template<typename T>
bool MyStack<T>::empty() const
{
return (-1 == m_top);
}

main.cpp:


#include "MyStack.h"

int main()
{
MyStack<int> obj1(2);
MyStack<int> obj2;
obj1.push(20);
obj1.push(10);

obj2 = obj1;
cout << obj2.pop() << endl;
cout << obj2.pop() << endl;
return 0;
}

Сортировка списка вставкой

Сортировка довольно медленная О(n в квадрате). Для сортировки большого кол-ва элементов не пойдет. Использовались фиктивные узлы указывающие на головы списков.
Идея  : берем неотсортированный список и по очереди вытаскиваем из него узлы (current). Данный узел помещаем в отсортированный список, который вначале состоит из одного фиктивного узла.

Сортировка списка методом вставки:


void listSort(Node *notSorted, Node *sorted)
{
Node *current; //указывает на узел из неотсортированного списка
Node *nextPosition; //указывает на следующий после текущего
Node *afterWhichInsert; //после которого следует вставка

for (current = notSorted->m_next; current != 0; current = nextPosition)
{
nextPosition = current->m_next; //сохраняем указатель на след. узел
for (afterWhichInsert = sorted; afterWhichInsert->m_next != 0;
                      afterWhichInsert = afterWhichInsert->m_next)
{
if (afterWhichInsert->m_next->m_item > current->m_item)
{
break;
}
}
current->m_next = afterWhichInsert->m_next;
afterWhichInsert->m_next = current;
}
}

main :

int main()
{
srand(time(0));

Node *headNotSorted = new Node(0, 0);  //Фиктивный узел указывает на голову                  неотсортированного списка
Node *headSorted = new Node(0, 0);   //Фиктивный узел указывает на голову отсортированного списка

Node *current = headNotSorted;

for(int i = 1; i < 10; ++i)   //Заполняем список случайными числами
{
current->m_next = new Node(rand()%100, 0);
current = current->m_next;
}
print(headNotSorted->m_next);

listSort(headNotSorted, headSorted);
print(headSorted->m_next);

return 0;
}


понедельник, 3 июня 2013 г.

Реверс связного списка

было: node1 -> node2 ->node3->NULL
стало: node3->nod2->node1->NULL

//Узел связного списка

class Node
{
public:
int m_item;
Node *m_next;

Node(int item, Node *next){m_item = item, m_next = next;}
};

Сама функция реверса списка:

Node* reverse(Node *first)
{
Node *tmp;
Node *current = first;
Node *anotherEnd = 0;

while (NULL != current)
{
tmp = current->m_next;
current->m_next = anotherEnd;
anotherEnd = current;
current = tmp;
}
return anotherEnd;  //возвращает новое начало списка
}

Отображение данных узлов:

void print(Node *first)
{
Node *tmp = first;
while (NULL != tmp)
{
cout << tmp->m_item << ' ';
tmp = tmp->m_next;
}
cout << endl;
}

Ну и main() :

int main()
{
srand(time(NULL));

Node *first = new Node(rand()%10, 0);
Node *tmp = first;
for (int i = 0; i < 8; ++i)  //Создаем список из 8 элементов
{
tmp->m_next = new Node(rand()%10, 0);
tmp = tmp->m_next;
}

print(first);

Node *end = reverse(first);
print(end);

return 0;
}




Задача Иосифа (циклический список)

Описание задачи:
http://ru.wikipedia.org/wiki/Задача Иосифа


Решение (Перебором):


#include <iostream>
using namespace std;

class Node   //Узел связного списка
{
public:
int m_item;
Node *m_next;

Node(int item, Node *next){m_item = item, m_next = next;}
};

int main()
{
cout << "Enter number of people: ";
int numberOfPeople = 0;
cin >> numberOfPeople;

cout << "Enter interval: ";
int interval;
cin >> interval;

Node *first =new Node(1, 0); //Создаем первый узел. m_item содержит номер
first->m_next = first;       //и зацикливаем его на себя

Node *tmp = first; //Указатель с которым будем работать в дальнейшем

for (int i = 2; i <= numberOfPeople; ++i)  //Создаем циклический список
{
tmp->m_next = new Node(i, first);
tmp = tmp->m_next;
}
while (tmp != tmp->m_next)    //Удаляем элемент через интервал
{
for (int i = 1; i < interval; ++i)
{
tmp = tmp->m_next;
}
Node *deleteNode = tmp->m_next;
tmp->m_next = tmp->m_next->m_next;

delete deleteNode;
}

cout << tmp->m_item << endl;  //Выводим оставшийся
}

Решето Эратосфена

Данный код выводит все простые числа в интервале от 2 ... number.


#include <iostream>
using namespace std;

void sieveOfEratosthenes(int arr[], int size);
void print(int arr[], int size);
int main()
{
cout << "Enter a number: ";
int number = 0;
cin >> number;
int *arr = new int[number];

sieveOfEratosthenes(arr, number);
print(arr, number);

return 0;
}

void sieveOfEratosthenes(int arr[], int size)
{
for (int i = 2; i < size; ++i)
{
arr[i] = 1;
}

for (int i = 2; i < size; ++i)
{
if (0 != arr[i])
{
for (int j = i; j * i < size; ++j)
{
arr[i*j] = 0;
}
}
}
}

void print(int arr[], int size)
{
for (int i = 2; i < size; ++i)
{
if (1 == arr[i])
{
cout << i << ' ';
}
}
cout << endl;
}

Сначала массив инициализируется единицами (признак, что число простое). Далее по ходу итераций, значение в ячейке массива меняется на нуль, т.е. число не является простым.