Задача 6. Удалить строки, в которых есть два одинаковых элемента (без использования std::vector)
Для начала решим эту задачу способом, близкому к чистому С.
Как и в C# матрицу можно рассматривать как массив строк. Поэтому для начала рассмотрим одну строку матрицы и создадим класс для нее.
Строка матрицы – массив чисел. Поэтому нам в формируемом классе нужна переменная типа int * (для хранения указателя на массив) и переменная типа int (для хранения размера массива, т.к. он нам не известен заранее).
Для создания строки нам нужно знать её размер. Поэтому, в конструктор строки будем передавать её размер. С учетом того, что по заданию не сказано, как заполняется матрица, будем заполнять её случайными числами. Если в конструктор передается размер массива, то в нем мы можем создать массив, используя оператор new []. Если мы его используем, то мы должны обязательно использовать оператор delete []. Оператор delete[] мы должны использовать когда нам строка уже не нужна, т.е. в дуструкторе (имя которого начинается с «~» и далее идет имя класса). Реализуем эти рассуждения в коде:
#include <stdlib.h>
#include <time.h>
class MatrixString {
private:
int *data;
int size;
int getRandValue(int max, int min) {
return (((double)rand())/RAND_MAX)*(max - min) + min;
}
void fillString() {
for (int i = 0; i < size; i++) {
data[i] = getRandValue(-10, 10);
}
}
public:
MatrixString(int size_) {
size = size_;
data = new int[size];
fillString();
}
~MatrixString() {
delete[] data;
}
};
Теперь необходимо написать функцию, которая определяет есть ли в строке хотя бы два одинаковых элемента. Они есть, если количество вхождений какого-либо элемента больше одного. Поэтому в начале надо написать функцию, которая определяет количество вхождений элемента в строку. Она не представляет из себя сложной функции и почти полностью аналогичная функции на C#:
int getCount(int element) {
int res = 0;
for (int i = 0; i < size; i++) {
if (data[i] == element) {
res++;
}
}
return res;
}
Функция перчати одной строки полностью эквивалентна функции печати одномерного массива (которая рассмотрена в предыдущих задачах), поэтому останавливаться на реализации этой функции мы не будем.
Ответом на вопрос, есть ли в строке два одинаковых элемента, является да или нет, т.е. логический тип. Реализация этой функции так же почти аналогичная функции на C#. Приведем полный код класса MatrixString, который получился на текущий момент:
#include <stdlib.h>
#include <time.h>
class MatrixString {
private:
int *data;
int size;
int getRandValue(int max, int min) {
return (((double)rand())/RAND_MAX)*(max - min) + min;
}
void fillString() {
for (int i = 0; i < size; i++) {
data[i] = getRandValue(-10, 10);
}
}
int getCount(int element) {
int res = 0;
for (int i = 0; i < size; i++) {
if (data[i] == element) {
res++;
}
}
return res;
}
public:
MatrixString(int size_) {
size = size_;
data = new int[size];
fillString();
}
void print() {
for (int i = 0; i < size; i++) {
printf("%d ", data[i]);
}
printf("\n");
}
bool needDelete() {
for (int i = 0; i < size; i++) {
if (getCount(data[i]) > 1) {
return true;
}
}
return false;
}
~MatrixString() {
delete[] data;
}
};
Теперь вернемся к матрице. Матрица – массив строк. Как и в C# что бы создать массив строк надо создать сам массив и создать каждый его элемент. Однако, что бы создать элемент массива, необходимо вызвать оператор new SimpleString(РазмерСтроки). Поэтому элемент массива будет иметь тип SimpleString *, а сам массив будет объявляться как SimpleString **strings. Так же нам нужно знать его размер. Для создания матрица надо знать её размеры, т.е. два числа. С учетом этого начало реализации класса матрицы будет выглядить:
class Matrix {
private:
MatrixString **strings;
int size;
public:
Matrix(int sizeX, int sizeY) {
size = sizeY;
strings = new MatrixString *[sizeY];
for (int i = 0; i < sizeY; i++) {
strings[i] = new MatrixString(sizeX);
}
}
~Matrix() {
for (int i = 0; i < size; i++) {
delete strings[i];
}
delete []strings;
}
};
Что бы распечатать матрицу надо распечатать каждую строку в ней. С учетом того, что в массиве хранится указатель на строку, необходимо использовать оператор -> для вызова функции печати у строки.
void print() {
for (int i = 0; i < size; i++) {
strings[i]->print();
}
printf("\n");
}
Следующим необходимым атомарным действием является удаление строки по индексу. В целом оно почти идентично удалению на C#. Но следует учитывать, что удаляемым элементом массива является указатель на память, выделенную с помощью оператора new. Поэтому перед удалением элемента из массива надо освободить память по удаляемому указателю с помощью оператора delete. И естественно надо удалить старый массив строк (а вернее массив указателей на строки). С учетом этого реализация алгоритма примет следующий вид:
void delByIndex(int index) {
MatrixString **newStrings = new MatrixString *[size - 1];
for (int i = 0; i < index; i++) {
newStrings[i] = strings[i];
}
delete strings[index];
for (int i = index; i < size; i++) {
newStrings[i] = strings[i + 1];
}
delete[] strings;
strings = newStrings;
size--;
}
Теперь надо удалить строки по условию. Для того, что бы избежать проблем, связанных со сдвигом индексации после удаления, будем идти с конца массива к его началу.
void process() {
for (int i = size - 1; i >= 0; i--) {
if (strings[i]->needDelete()) {
delByIndex(i);
}
}
}
Теперь разобъем получившееся решение на 2 h файла (для объявления строки матрицы и самой матрицы) и 3 cpp файла (главная функция, реализация строки матрицы и реализация матрицы. Структура и содержимое файлов конечного решения представлены на рисунке:
Содержимое файла MatrixString.h:
#ifndef _MATRIXSTRING_H_
#define _MATRIXSTRING_H_
class MatrixString {
private:
int *data;
int size;
int getRandValue(int max, int min);
void fillString();
int getCount(int element);
public:
MatrixString(int size_);
~MatrixString();
void print();
bool needDelete();
};
#endif
СодержимоефайлаMatrixString.cpp:
#include <stdlib.h>
#include "MatrixString.h"
#include <stdio.h>
int MatrixString::getRandValue(int max, int min) {
return (((double)rand())/RAND_MAX)*(max - min) + min;
}
void MatrixString::fillString() {
for (int i = 0; i < size; i++) {
data[i] = getRandValue(-10, 10);
}
}
int MatrixString::getCount(int element) {
int res = 0;
for (int i = 0; i < size; i++) {
if (data[i] == element) {
res++;
}
}
return res;
}
MatrixString::MatrixString(int size_) {
size = size_;
data = new int[size];
fillString();
}
void MatrixString::print() {
for (int i = 0; i < size; i++) {
printf("%d ", data[i]);
}
printf("\n");
}
bool MatrixString::needDelete() {
for (int i = 0; i < size; i++) {
if (getCount(data[i]) > 1) {
return true;
}
}
return false;
}
MatrixString::~MatrixString() {
delete[] data;
}
СодержимоефайлаMatrix.h:
#ifndef _MATRIX_H_
#define _MATRIX_H_
#include "MatrixString.h"
class Matrix {
private:
MatrixString **strings;
int size;
void delByIndex(int index);
public:
Matrix(int sizeX, int sizeY);
~Matrix();
void print();
void process();
};
#endif
СодержимоефайлаMatrix.cpp:
#include "MatrixString.h"
#include "Matrix.h"
#include <stdio.h>
void Matrix::delByIndex(int index) {
MatrixString **newStrings = new MatrixString *[size - 1];
for (int i = 0; i < index; i++) {
newStrings[i] = strings[i];
}
delete strings[index];
for (int i = index; i < size; i++) {
newStrings[i] = strings[i + 1];
}
delete[] strings;
strings = newStrings;
size--;
}
Matrix::Matrix(int sizeX, int sizeY) {
size = sizeY;
strings = new MatrixString *[sizeY];
for (int i = 0; i < sizeY; i++) {
strings[i] = new MatrixString(sizeX);
}
}
void Matrix::print() {
for (int i = 0; i < size; i++) {
strings[i]->print();
}
printf("\n");
}
void Matrix::process() {
for (int i = size - 1; i >= 0; i--) {
if (strings[i]->needDelete()) {
delByIndex(i);
}
}
}
Matrix::~Matrix() {
for (int i = 0; i < size; i++) {
delete strings[i];
}
delete []strings;
}
Содержимоефайлаlab2_1.cpp:
#include <stdlib.h>
#include <time.h>
#include <conio.h>
#include "Matrix.h"
#include <stdio.h>
int main(int argc, char* argv[]) {
srand(time(NULL));
int sizeX;
int sizeY;
printf("input size x: ");
scanf("%d", &sizeX);
printf("input size y: ");
scanf("%d", &sizeY);
Matrix z(sizeX, sizeY);
z.print();
z.process();
z.print();
printf("press any key");
_getch();
return 0;
}