#include <iostream>
#include <iomanip>
#include <locale>
#include <algorithm>
#include <functional>
#include <cstdlib>
using namespace std;
const size_t COUNT=20; // Количество элементов массива
const size_t INS_COUNT=3; // Количество вставляемых элементов
typedef int dataType; // Тип данных для массива
// Выводит массив на stdout
template<class Ty,size_t Dim>
void printArray(const char* const msg,Ty (&arr)[Dim])
{
cout<<msg<<endl;
for(size_t i=0;i<Dim;++i)
{
cout<<setw(4)<<arr[i]<<' ';
}
cout<<endl;
}
// Заполняет массив случайными числами
template<class Ty,size_t Dim>
void fillArray(Ty (&arr)[Dim])
{
for(size_t i=0;i<Dim;++i)
{
arr[i]=rand()%50;
}
}
// Вставляет в упорядоченный по возрастанию массив значение сохраняя порядок
template<class Ty,size_t Dim>
void insertInArray(Ty (&arr)[Dim],Ty val)
{
// Бинарный поиск места вставки в массиве
size_t first=0,last=Dim;
while(first<last)
{
size_t mid=(last-first)/2+first;
if(arr[mid]>val)
{
last=mid;
}
else
{
first=mid+1;
}
}
// Вставка и сдвиг элементов
for(size_t i=first;i<Dim;++i)
{
swap(arr[i],val);
}
}
int main()
{
srand(time(0));
locale::global(locale(""));
// Массив
dataType array[COUNT];
// Заполним массив
fillArray(array);
// Распечатаем
printArray("Исходный массив:",array);
// Отсортируем массив
sort(array,array+COUNT,less<dataType>());
printArray("Отсортированный массив:",array);
cout<<"Вставим "<<INS_COUNT<<" числа"<<endl;
// Вставим несколько элементов
for(size_t i=0;i<INS_COUNT;++i)
{
dataType value=rand()%50;
cout<<"Вставим число "<<value<<endl;
insertInArray(array,value);
printArray("Массив после вставки:",array);
}
return 0;
}
Исходный массив:
41 45 16 9 15 38 23 30 22 43 17 24 31 42 8 11 27 47 32 3
Отсортированный массив:
3 8 9 11 15 16 17 22 23 24 27 30 31 32 38 41 42 43 45 47
Вставим 3 числа
Вставим число 37
Массив после вставки:
3 8 9 11 15 16 17 22 23 24 27 30 31 32 37 38 41 42 43 45
Вставим число 10
Массив после вставки:
3 8 9 10 11 15 16 17 22 23 24 27 30 31 32 37 38 41 42 43
Вставим число 20
Массив после вставки:
3 8 9 10 11 15 16 17 20 22 23 24 27 30 31 32 37 38 41 42
#include <cstdlib>
#include <cstdio>
#include <locale>
#include <limits>
#include <iostream>
#include <iomanip>
#include <stdexcept>
using namespace std;
typedef int dataType; // Тип данных для элементов массива
template<class Ty>
Ty input(const char* const msg)
{
while (true)
{
Ty result = Ty();
cout << msg;
cin >> result;
if (cin.fail())
{
cout << "Ошибочный ввод" << endl;
cin.clear();
cin.ignore(numeric_limits<streamsize>::max(), '\n');
}
else
{
cin.ignore(numeric_limits<streamsize>::max(), '\n');
return result;
}
}
}
// Варианты ввода
enum menuChoice
{
MANUAL,
RANDOM
};
// Меню выбора вариантов ввода
menuChoice menu()
{
while (true)
{
cout << "Выберите как будут вводиться данные:" << endl
<< "1 - Вручную" << endl
<< "2 - Автогенерация" << endl
<< "Ваш выбор:";
char choice = 0;
cin.get(choice);
cin.ignore(numeric_limits<streamsize>::max(), '\n');
switch (choice)
{
case '1':
return MANUAL;
case '2':
return RANDOM;
}
cout << "Будьте внимательней!" << endl;
}
}
// Выводит массив на stdout
void printArray(const char* const msg, dataType* arr, size_t count)
{
cout << msg << endl;
for (size_t i = 0; i < count; ++i)
{
cout << setw(4) << arr[i] << ' ';
}
cout << endl;
}
// Вставка в упорядоченный массив
void insertInArray(dataType* &array, size_t& count, dataType value)
{
// Выделяем дополнительно память
dataType* newPtr = static_cast<dataType*> (realloc(array, sizeof (dataType)*(count + 1)));
if (!newPtr)
{
throw bad_alloc();
}
array = newPtr;
// Бинарный поиск места вставки в массиве
size_t first = 0, last = count++;
while (first < last)
{
size_t mid = (last - first) / 2 + first;
if (array[mid] > value)
{
last = mid;
}
else
{
first = mid + 1;
}
}
// Вставка и сдвиг элементов
for (size_t i = first; i < count; ++i)
{
swap(array[i], value);
}
}
// Заполнение массива
void fillArray(dataType* &array, size_t maxCount, menuChoice choice)
{
size_t count = 0;
while (count < maxCount)
{
dataType value;
switch (choice)
{
case MANUAL:
value = input<dataType>("Введите значение:");
break;
case RANDOM:
value = rand() % 50;
break;
default:
throw runtime_error("Ошибка в параметре choice");
}
insertInArray(array, count, value);
cout << "Вставим элемент " << value << endl;
printArray("Массив:", array, count);
}
}
int main()
{
srand(time(0));
locale::global(locale(""));
dataType* array = 0; // Массив будем хранить здесь
try
{
size_t maxCount = input<size_t > ("Количество элементов :"), count = 0;
fillArray(array, maxCount, menu());
}
catch (bad_alloc&)
{
cout << "Невозможно выделить память" << endl;
}
catch (runtime_error& ex)
{
cout << ex.what() << endl;
}
if (array)
{
delete[] array;
}
return 0;
}
Количество элементов :5
Выберите как будут вводиться данные:
1 - Вручную
2 - Автогенерация
Ваш выбор:1
Введите значение:2
Вставим элемент 2
Массив:
2
Введите значение:8
Вставим элемент 8
Массив:
2 8
Введите значение:4
Вставим элемент 4
Массив:
2 4 8
Введите значение:1
Вставим элемент 1
Массив:
1 2 4 8
Введите значение:7
Вставим элемент 7
Массив:
1 2 4 7 8
-------------------------------------------
Количество элементов :5
Выберите как будут вводиться данные:
1 - Вручную
2 - Автогенерация
Ваш выбор:2
Вставим элемент 27
Массив:
27
Вставим элемент 23
Массив:
23 27
Вставим элемент 5
Массив:
5 23 27
Вставим элемент 5
Массив:
5 5 23 27
Вставим элемент 42
Массив:
5 5 23 27 42
Если Вы уже зарегистрированы на Портале - войдите в систему, если Вы еще не регистрировались - пройдите простую процедуру регистрации.