369 lines
9.9 KiB
C++
369 lines
9.9 KiB
C++
#include <iostream>
|
||
#include <vector>
|
||
#include <cmath>
|
||
|
||
using namespace std;
|
||
|
||
class MyArrayParent
|
||
{
|
||
protected:
|
||
//сколько памяти выделено?
|
||
int capacity;
|
||
//количество элементов - сколько памяти используем
|
||
int count;
|
||
//массив
|
||
double* ptr;
|
||
public:
|
||
//конструкторы и деструктор
|
||
MyArrayParent(int Dimension = 100)
|
||
{
|
||
cout << "\nMyArrayParent constructor";
|
||
//выделить память под массив ptr, заполнить поля
|
||
ptr = new double[Dimension];
|
||
capacity = Dimension;
|
||
count = 0;
|
||
}
|
||
//конструктор принимает существующий массив
|
||
MyArrayParent(double* arr, int len)
|
||
{
|
||
cout << "\nMyArrayParent constructor";
|
||
if (arr == nullptr) {
|
||
// обработка ошибки, например, можно выкинуть исключение
|
||
throw invalid_argument("Input array is nullptr");
|
||
}
|
||
//заполнить массив ptr, заполнить поля
|
||
ptr = new double[len];
|
||
capacity = len;
|
||
count = len;
|
||
for (int i = 0; i < len; i++) ptr[i] = arr[i];
|
||
}
|
||
//деструктор
|
||
~MyArrayParent()
|
||
{
|
||
cout << "\nMyArrayParent destructor";
|
||
//освободить память, выделенную под ptr
|
||
delete[] ptr;
|
||
}
|
||
|
||
//обращение к полям
|
||
int Capacity() { return capacity; }
|
||
int Size() { return count; }
|
||
double GetComponent(int index)
|
||
{
|
||
if (index >= 0 && index < count)
|
||
return ptr[index];
|
||
//сгенерировать исключение, если индекс неправильный
|
||
return -1;
|
||
}
|
||
void SetComponent(int index, double value)
|
||
{
|
||
if (index >= 0 && index < count)
|
||
ptr[index] = value;
|
||
//сгенерировать исключение, если индекс неправильный
|
||
}
|
||
|
||
//добавление в конец нового значения
|
||
void push(double value)
|
||
{
|
||
if (count >= capacity)
|
||
return;
|
||
ptr[count] = value;
|
||
count++;
|
||
}
|
||
|
||
//удаление элемента с конца
|
||
void RemoveLastValue()
|
||
{
|
||
if (count > 0)
|
||
{
|
||
//ptr[count-1] = 0;
|
||
count--;
|
||
}
|
||
//что делаем, если пуст?
|
||
}
|
||
|
||
int IndexOf(double value, bool bFindFromStart = true)
|
||
{
|
||
if (bFindFromStart)
|
||
{
|
||
for (int i = 0; i < count; i++)
|
||
{
|
||
if (fabs(ptr[i] - value) < 0.001)
|
||
return i;
|
||
}
|
||
}
|
||
else
|
||
{
|
||
for (int i = count - 1; i >= 0; --i)
|
||
{
|
||
if (abs(ptr[i] - value) < 0.001)
|
||
return i;
|
||
}
|
||
|
||
}
|
||
return -1; // элемент не найден
|
||
}
|
||
|
||
double& operator[](int index)
|
||
{
|
||
//перегрузка оператора []
|
||
return ptr[index];
|
||
}
|
||
|
||
MyArrayParent& operator=(MyArrayParent& V)
|
||
{
|
||
if (capacity < V.capacity)
|
||
{
|
||
delete[] ptr;
|
||
ptr = new double[V.capacity];
|
||
}
|
||
capacity = V.capacity;
|
||
count = V.count;
|
||
|
||
for (int i = 0; i < count; i++)
|
||
ptr[i] = V[i];
|
||
|
||
return *this;
|
||
}
|
||
|
||
MyArrayParent(const MyArrayParent& V)
|
||
{
|
||
//создание копии объекта - в основном, при возвращении результата из функции / передаче параметров в функцию
|
||
ptr = new double[V.capacity];
|
||
capacity = V.capacity;
|
||
count = V.count;
|
||
|
||
for (int i = 0; i < count; i++)
|
||
ptr[i] = V.ptr[i]; //V[i]
|
||
}
|
||
|
||
void print()
|
||
{
|
||
cout << "\nMyArrParent, size: " << count << ", values: {";
|
||
int i = 0;
|
||
for (i = 0; i < count; i++)
|
||
{
|
||
cout << ptr[i];
|
||
if (i != count - 1)
|
||
cout << ", ";
|
||
}
|
||
cout << "}";
|
||
}
|
||
|
||
MyArrayParent IndicesOfMax() const {
|
||
MyArrayParent indices;
|
||
|
||
if (count == 0) {
|
||
return indices;
|
||
}
|
||
|
||
double maxVal = ptr[0];
|
||
|
||
// Find the maximum value
|
||
for (int i = 1; i < count; i++) {
|
||
if (ptr[i] > maxVal) {
|
||
maxVal = ptr[i];
|
||
}
|
||
}
|
||
|
||
// Find indices of all occurrences of the maximum value
|
||
for (int i = 0; i < count; i++) {
|
||
if (fabs(ptr[i] - maxVal) < 0.001) {
|
||
indices.push(i);
|
||
}
|
||
}
|
||
|
||
return indices;
|
||
}
|
||
};
|
||
|
||
void f(MyArrayParent p)
|
||
{
|
||
cout << "\nIn f(): ";
|
||
p.print();
|
||
}
|
||
|
||
class MyArrayChild : public MyArrayParent
|
||
{
|
||
public:
|
||
//используем конструктор родителя. Нужно ли что-то ещё?
|
||
MyArrayChild(int Dimension = 100) : MyArrayParent(Dimension) { cout << "\nMyArrayChild constructor"; }
|
||
|
||
~MyArrayChild() { cout << "\nMyArrayChild destructor\n"; }
|
||
|
||
//удаление элемента
|
||
void RemoveAt(int index = -1)
|
||
{
|
||
if (index == -1) RemoveLastValue();
|
||
if (index < 0 || index >= count) return;
|
||
|
||
for (int i = index + 1; i < count; i++)
|
||
ptr[i - 1] = ptr[i];
|
||
count--;
|
||
}
|
||
|
||
//вставка элемента
|
||
void InsertAt(double value, int index = -1)
|
||
{
|
||
if (index == -1 || index == count) { push(value); return; }
|
||
if (index < 0 || index > count) return;
|
||
|
||
for (int i = count - 1; i >= index; i--)
|
||
ptr[i + 1] = ptr[i];
|
||
count++;
|
||
ptr[index] = value;
|
||
}
|
||
|
||
//выделение подпоследовательности
|
||
|
||
MyArrayChild SubSequence(int StartIndex = 0, int Length = -1)
|
||
{
|
||
if (StartIndex < 0 || StartIndex >= count || Length == 0)
|
||
{
|
||
throw out_of_range("Invalid start index or length");
|
||
}
|
||
|
||
if (Length == -1)
|
||
{
|
||
Length = count - StartIndex;
|
||
}
|
||
|
||
MyArrayChild subArray(Length);
|
||
|
||
for (int i = 0; i < Length; i++)
|
||
{
|
||
subArray.push(ptr[StartIndex + i]);
|
||
}
|
||
|
||
return subArray;
|
||
}
|
||
//добавление элемента в конец
|
||
//operator + ?
|
||
MyArrayChild operator+(double value)
|
||
{
|
||
MyArrayChild result(count + 1);
|
||
|
||
int index = 0;
|
||
while (index < count && ptr[index] < value)
|
||
{
|
||
result.push(ptr[index]);
|
||
index++;
|
||
}
|
||
|
||
result.push(value);
|
||
|
||
while (index < count)
|
||
{
|
||
result.push(ptr[index]);
|
||
index++;
|
||
}
|
||
|
||
return result;
|
||
}
|
||
};
|
||
|
||
class MySortedArray : public MyArrayChild
|
||
{
|
||
protected:
|
||
int BinSearch(double value, int left, int right)
|
||
{
|
||
if (value <= ptr[left])
|
||
return left;
|
||
if (value >= ptr[right])
|
||
return right + 1;
|
||
|
||
// база рекурсии
|
||
if (right == left + 1)
|
||
{
|
||
if (ptr[left] < value && ptr[right] > value)
|
||
return right;
|
||
else
|
||
return left;
|
||
}
|
||
|
||
int middle = (left + right) / 2;
|
||
|
||
if (fabs(ptr[middle] - value) < 0.001)
|
||
return middle;
|
||
if (ptr[middle] > value)
|
||
return BinSearch(value, left, middle - 1);
|
||
|
||
return BinSearch(value, middle + 1, right);
|
||
}
|
||
public:
|
||
//используем конструктор родителя. Нужно ли что-то ещё?
|
||
MySortedArray(int Dimension = 100) : MyArrayChild(Dimension) { cout << "\nMySortedArray constructor"; }
|
||
~MySortedArray() { cout << "\nMySortedArray destructor\n"; }
|
||
|
||
int IndexOf(double value)
|
||
{
|
||
return IterativeBinarySearch(value);
|
||
}
|
||
|
||
int IterativeBinarySearch(double value)
|
||
{
|
||
int left = 0;
|
||
int right = count - 1;
|
||
|
||
while (left <= right)
|
||
{
|
||
int middle = (left + right) / 2;
|
||
|
||
if (fabs(ptr[middle] - value) < 0.001) //если модуль зн <, то return middle
|
||
return middle;
|
||
|
||
if (ptr[middle] < value)
|
||
left = middle + 1;
|
||
else
|
||
right = middle - 1;
|
||
}
|
||
|
||
return -1; // не найдено
|
||
}
|
||
|
||
|
||
void push(double value)
|
||
{
|
||
if (count >= capacity) return;
|
||
if (count == 0 || ptr[count - 1] <= value) { MyArrayParent::push(value); return; } //Если массив пустой или
|
||
//новый элемент больше последнего элемента, добавляем новый элементв конец
|
||
int index = BinSearch(value, 0, count - 1);
|
||
InsertAt(value, index);
|
||
|
||
}
|
||
};
|
||
|
||
int main()
|
||
{
|
||
MySortedArray arr1;
|
||
MySortedArray arr;
|
||
if (true)
|
||
{
|
||
int i = 0;
|
||
for (i = 0; i < 10; i++)
|
||
{
|
||
arr.push((int)(50 * sin(i + 1)));
|
||
arr.print();
|
||
}
|
||
arr.print();
|
||
arr.print();
|
||
arr1 = arr;
|
||
cout << "\nFind: " << arr.IndexOf(7) << "\n";
|
||
cout << "\nFind: " << arr.IndexOf(20) << "\n";
|
||
cout << "\nFind: " << arr.IndexOf(45) << "\n";
|
||
}
|
||
|
||
MyArrayParent maxIndices = arr.IndicesOfMax();
|
||
cout << "\nIndices of maximum value: ";
|
||
for (int i = 0; i < maxIndices.Size(); ++i) {
|
||
cout << maxIndices.GetComponent(i) << " ";
|
||
}
|
||
cout << endl;
|
||
int index = arr.IterativeBinarySearch(42);
|
||
cout << "\nIterrative Searh: " << index;
|
||
|
||
arr1.print();
|
||
// char c; cin >> c;
|
||
return 0;
|
||
}
|