Блог

Итак, да, я написал программу, которая сортирует строки двумерного массива в порядке возрастания в соответствии с суммой всех положительных четных элементов в каждой строке, НО она не работает должным образом. Иногда он может корректно менять местами строки, но в основном кажется, что эта программа меняет местами только две соседние строки или что-то в этом роде.

Вероятно, существует проблема с неправильным использованием пузырьковой сортировки для 2-мерных массивов. Вот функция, в которой я делал большинство вещей:

 void print(int** arr, int rows, int columns) {
    for (int i = 0; i < rows; i  ) {
        for (int j = 0; j < columns; j  ) {
            cout << setw(7) << arr[i][j];
        }
        cout << endl;
    }
    int* sumRows = new int[rows];
    int sum = 0;
    for (int i = 0; i < rows; i  ) {
        for (int j = 0; j < columns; j  ) {
            if (arr[i][j] > 0 amp;amp; arr[i][j] % 2 == 0)
            {
                //cout << setw(7) << arr[i][j];
                sum = sum   arr[i][j];
            }
        }
        cout << endl << "Sum of positive even elements in the row " << i   1 << " = " << sum;
        sumRows[i] = sum;
        sum = 0;
    }
    cout << endl << "Array of sums: ";
    for (int i = 0; i < rows; i  ) {
        cout << setw(7) << sumRows[i];
    }

    //for (int i = 0; i < r; i  ) cout << setw(7) << sumRows[i];
    cout << endl;

    bool swapped;
    for (int i = 0; i < rows - 1; i  )
    {
        swapped = false;
        for (int j = 0; j < columns - 1; j  )
        {
            for (int k = 0; k < rows - i - 1; k  ) {
                if (sumRows[k] > sumRows[k   1])
                {
                    swap(arr[k][j], arr[k   1][j]);
                    swapped = true;
                }
            }
        }

        if (swapped == false) break;
    }

    cout << endl << endl << "Swapped array:" << endl;
    for (int i = 0; i < rows; i  ) {
        for (int j = 0; j < columns; j  ) {
            cout << setw(7) << arr[i][j];
        }
        cout << endl;
    }
}

 

Полный код:

 #include <iostream>
#include <iomanip>
#include <time.h>
#include <conio.h>
#include <algorithm>
using namespace std;

int** createMalloc(int, int);
int** createCalloc(int rows, int columns);

int** createNew(int rows, int columns);
void deleteNew(int** arr, int rows);

void init(int**, int, int);
void freeMemory(int**, int);
void print(int**, const int, const int);

void initPrint(int** arr, int rows, int columns);

void main() {
    int rowCount, colCount;
    cout << "Enter number of rows: "; cin >> rowCount;
    cout << "Enter number of columns: "; cin >> colCount;
    cout << " Array creation algorithmn";
start:
    cout << "Input number : n1 for mallocn2 for callocn3 for newn";
    int k;
    cin >> k;
    switch (k) {
    case 1: {
        int** a = createMalloc(rowCount, colCount);
        initPrint(a, rowCount, colCount);

        freeMemory(a, rowCount);
        break;
    }
    case 2: {
        int** a = createCalloc(rowCount, colCount);
        initPrint(a, rowCount, colCount);

        freeMemory(a, rowCount);
        break;
    }
    case 3: {
        int** a = createNew(rowCount, colCount);
        initPrint(a, rowCount, colCount);

        deleteNew(a, rowCount);
        break;
    }
    default:cout << "Input 1, 2 or 3, please.";
        cout << endl << endl;
        goto start;
    }
    cout << endl << endl;
}

int** createMalloc(int rows, int columns) {
    int** arr = (int**)malloc(rows * sizeof(int*));
    for (int i = 0; i < rows; i  ) {
        arr[i] = (int*)malloc(columns * sizeof(int));
    }
    return arr;
}

int** createCalloc(int rows, int columns) {
    int** arr = (int**)calloc(rows, sizeof(int*));
    for (int i = 0; i < rows; i  ) {
        arr[i] = (int*)calloc(columns, sizeof(int));
    }
    return arr;
}

int** createNew(int rows, int columns) {
    int** arr = new int* [rows];
    for (int i = 0; i < rows; i  ) {
        arr[i] = new int[columns];
    }
    return arr;
}

void initPrint(int** arr, int rows, int columns) {
    init(arr, rows, columns);
    print(arr, rows, columns);
}

void init(int** arr, int rows, int columns) {
    const int Low = -10, High = 10;
    srand((unsigned)time(NULL));
    for (int i = 0; i < rows; i  ) {
        for (int j = 0; j < columns; j  ) {
            arr[i][j] = Low   rand() % (High - Low   1);
        }
    }
}

void freeMemory(int** arr, int rows) {
    for (int i = 0; i < rows; i  ) {
        free(arr[i]);
    }
    free(arr);
}

void deleteNew(int** arr, int rows) {
    for (int i = 0; i < rows; i  ) {
        delete[] arr[i];
    }
    delete[] arr;
}

void print(int** arr, int rows, int columns) {
    for (int i = 0; i < rows; i  ) {
        for (int j = 0; j < columns; j  ) {
            cout << setw(7) << arr[i][j];
        }
        cout << endl;
    }
    int* sumRows = new int[rows];
    int sum = 0;
    for (int i = 0; i < rows; i  ) {
        for (int j = 0; j < columns; j  ) {
            if (arr[i][j] > 0 amp;amp; arr[i][j] % 2 == 0)
            {
                //cout << setw(7) << arr[i][j];
                sum = sum   arr[i][j];
            }
        }
        cout << endl << "Sum of positive even elements in the row " << i   1 << " = " << sum;
        sumRows[i] = sum;
        sum = 0;
    }
    cout << endl << "Array of sums: ";
    for (int i = 0; i < rows; i  ) {
        cout << setw(7) << sumRows[i];
    }

    //for (int i = 0; i < r; i  ) cout << setw(7) << sumRows[i];
    cout << endl;

    bool swapped;
    for (int i = 0; i < rows - 1; i  )
    {
        swapped = false;
        for (int j = 0; j < columns - 1; j  )
        {
            for (int k = 0; k < rows - i - 1; k  ) {
                if (sumRows[k] > sumRows[k   1])
                {
                    swap(arr[k][j], arr[k   1][j]);
                    swapped = true;
                }
            }
        }

        //IF no two elements were swapped by inner loop, then break 
        if (swapped == false) break;
    }

    cout << endl << endl << "Swapped array:" << endl;
    for (int i = 0; i < rows; i  ) {
        for (int j = 0; j < columns; j  ) {
            cout << setw(7) << arr[i][j];
        }
        cout << endl;
    }
}
 

P.S. Двумерные массивы должны быть обязательно динамическими. Кроме того, мне нужно было предоставить пользователю выбор создания массива с malloc помощью, calloc или new . Кроме того, пока не удается выполнить эту задачу с помощью vector .

P.P.S. Я знаю, что большинству из вас это будет легко, но для меня это определенно не так, поскольку эта задача является моей домашней работой в университете, и мы не изучали никаких алгоритмов сортировки. В любом случае, когда я спросил учителя, как я могу сортировать строки таким образом, он сказал мне использовать пузырьковую сортировку, так что я здесь

Меня беспокоят 3 цикла, поэтому я зашел в Википедию, чтобы проверить свои предположения.

Полностью непроверенный код, используйте на свой страх и риск

 void BSort(int **arr, int *sumRows, int rows, int columns) {
    bool swapped;
    while (true) {
        swapped = false;
        for (int k = 0; k < rows - 1; k  , rows--) { // reduce max row
            if (sumRows[k] > sumRows[k   1]) {
                swap(arr[k], arr[k   1]); // swaps the pointers
                swap(sumRows[k], sumRows[k   1]); // swap the sums too or we swap on false conditions afterward.
                swapped = true;
            }
        }

        if (swapped == false) break;
    }
}
 

далее

• вы должны каким-то образом заменить свой цикл goto на while.
• sumRows не удаляется.
• используйте меньшие блоки кода, используйте функции для суммирования, сортировки пузырьками и т. Д.

В принципе, ваша программа уже хороша. (За исключением проблемы сортировки)

Но я хотел бы показать вам решение в более «C -стиле», использующее объектно-ориентированный подход.

И это полный и проверенный код с множеством комментариев, позволяющий легко понять.

Мы инкапсулируем все наши данные в класс и добавляем методы для работы с этими данными. Мы делаем это, потому что внешний мир не должен интересоваться нашим внутренним представлением данных. Мы можем изменить внутренние компоненты класса, и никто в остальном мире не должен этого заметить.

Кроме того, все функции класса могут обращаться к данным класса. Таким образом, мы не загрязняем пространство имен ненужными данными.

Реализация метода выделения — это просто упражнение, и оно добавляет не так много ценности. Это просто ввод текста.

Чтобы упростить вывод, мы перезаписываем оператор вставки класса. Это совсем не сложно и позволяет нам интуитивно использовать существующие ostreams, например std::cout .

В функции сортировки у вас возникла проблема. Вы просто хотите отсортировать строки по заданному предикату: сумме четных положительных чисел в столбце строки.

Пожалуйста, обратите внимание: нет необходимости касаться каких-либо данных столбца. Если требуется замена, мы просто меняем указатель на нужные строки. Итак, не так много значений столбца, только один указатель строки, который указывает на значение первого столбца. Это очень эффективно.

Пожалуйста, обратите внимание. В этом примере вы не можете предварительно вычислить сумму строк, потому что строки необходимо поменять местами.

Если мы хотим это сделать, нам нужно ввести структуру данных, состоящую из значений столбцов и сумм. Также легко возможно. Или, в случае дополнительного предварительно вычисленного массива для сумм строк, нам также нужно будет поменять местами эти значения. Но в приведенном ниже решении мы идем простым путем и каждый раз пересчитываем значение строки и тратим на это много времени . , ,

В любом случае. Пожалуйста, проверьте приведенный ниже пример:

 #include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>

// Lower and Upper Bound of our random test values
constexpr int LowerBound = -10;
constexpr int UpperBound = 10;

// We may have 3 different types of allocators
enum class Allocater { New, Malloc, Calloc};

// An ultra simple, stripped down representation of a 2d array with 3 types of allocaters
class Array2D {
    const Allocater allocater{};                    // Type of allocator. Default is new
    const size_t numberOfRows{};                    // Number of Rows in the 2d array
    const size_t numberOfColumns{};                 // Number of Columns of our 2d array
    int** data{};

    void allocaterMalloc();                         // Allocation using malloc
    void allocaterCalloc();                         // Allocation using calloc
    void allocaterNew();                            // Allocation using new
    void deallocateMallocCalloc();                  // Deallocatio using calloc and malloc
    void deallocateNew();                           // Deallocation using new 
    void initData();                                // Initialize our 2d array with random data
    int sumOfPositiveEvenValuesIn(size_t row) const;// Predicate function to calculate row sums for even positive values 

public:
    // Constructor. Buidl an array with given number of rows and columns using a given allocator implementation
    explicit Array2D(const size_t numRows, const size_t numColumns, Allocater alloc = Allocater::New);
    Array2D() = delete;                             // No default constructor
    ~Array2D();                                     // Free all allocated memory

    friend std::ostreamamp; operator << (std::ostreamamp; os, const Array2Damp; a2d); // Simple output
    void sort();                                    // Sort according to predicate
};

// ---------------------------------------------------------------------------------------------------------
// Main constructor. Build a 2d array with given number of rows and columns using the given allocator method
Array2D::Array2D(const size_t numRows, const size_t numColumns, Allocater alloc) : allocater(alloc), numberOfRows(numRows), numberOfColumns(numColumns) {
    // Depending on the requested method, allocate the memory for our 2d array
    switch (allocater) {
    case Allocater::Malloc:                         // We shall us malloc
        allocaterMalloc();                          // Call apropriate allocater
        break;
    case Allocater::Calloc:                         // We shall use calloc
        allocaterCalloc();                          // Call apropriate allocater
        break;
    case Allocater::New: // Fallthrough             // We shal use new
    default:                                        // Or, if there is some unknown specifier (should never happen)
        allocaterNew();                             // Call apropriate allocater
        break;
    }
    if (data) initData();                           // And initialize our 2d array with random values
}

// Destructor: Release all allocated memory 
Array2D::~Array2D() {
    // Call appropriate deallocator
    if (allocater == Allocater::Malloc || allocater == Allocater::Calloc)
        deallocateMallocCalloc();                   // Deallocate using std::free
    else
        deallocateNew();                            // Deallocate using delete
}

// --------------------------------
// The different alloctor functions

void Array2D::allocaterMalloc() {

    // First get memory to store the row pointer that will later point to the first coulmn of the row
    data = static_cast<int**>(std::malloc(numberOfRows * sizeof(int*)));

    // Now get space for all coulmns in this row
    if (data) for (size_t row{}; row < numberOfRows;   row)
        data[row] = static_cast<int*>(std::malloc(numberOfColumns * sizeof(int)));
}

void Array2D::allocaterCalloc() {
    // First get memory to store the row pointer that will later point to the first coulmn of the row
    data = static_cast<int**>(std::calloc(numberOfRows, sizeof(int*)));

    // Now get space for all coulmns in this row
    if (data)for (size_t row{}; row < numberOfRows;   row)
        data[row] = static_cast<int*>(std::calloc(numberOfColumns, sizeof(int)));
}
void Array2D::allocaterNew() {
    // First get memory to store the row pointer that will later point to the first coulmn of the row
    data = new int* [numberOfRows];

    // Now get space for all coulmns in this row
    if (data) for (size_t row{}; row < numberOfRows;   row)
        data[row] = new int[numberOfColumns];
}

// --------------------
// And the deallocators
void Array2D::deallocateMallocCalloc() {
    if (data) for (size_t row{}; row < numberOfRows;   row)
        std::free(data[row]);                   // Free each row with columns
    std::free(data);                            // Free all rows
}
void Array2D::deallocateNew() {
    if (data) for (size_t row{}; row < numberOfRows;   row)
        delete[] data[row];                     // Free each row with columns
    delete[] data;                              // Free all rows
}
//-------------------------------------------
// Initialize our 2d array with random values
void Array2D::initData() {
    // Seed the random generator
    std::srand(static_cast<unsigned int>(std::time(NULL)));

    // Calculate a random value for all data in our 2d array
    if (data) for (size_t row{}; row < numberOfRows;   row)                     // For all rows
            if (data[row])  for (size_t col{}; col < numberOfColumns;   col)    // For all columns
                data[row][col] = LowerBound   (std::rand() % (UpperBound - LowerBound   1));
}
//--------------------------------------------------------------
// A function which calculates the positive even values of a row
int Array2D::sumOfPositiveEvenValuesIn(size_t row) const {
    int sum{};
    // Iterate over values in a given row
    for (size_t col{}; col < numberOfColumns;   col)
        // Predicate
        if (data[row] amp;amp; (data[row][col] > 0) amp;amp; ((data[row][col] % 2) == 0))
            sum  = data[row][col];              // Calculate the sum
    return sum;                                 // Return result
}
//-------------------------------------------------------------------
// Simple output function. Overwrite inserter operator for this class
std::ostreamamp; operator << (std::ostreamamp; os, const Array2Damp; a2d) {

    // For all rows
    if (a2d.data) for (size_t row{}; row < a2d.numberOfRows;   row) {

        // For all columns
        if (a2d.data[row]) for (size_t col{}; col < a2d.numberOfColumns;   col)
            os << a2d.data[row][col] << 't';                       // Show column values
        os << 't' << a2d.sumOfPositiveEvenValuesIn(row) << 'n';   // Show conditional sum of columns
    }
    return os << "nn";
}
//--------------------------------------
// Bubble sort. Algorithm from Wikipedia
void Array2D::sort() {
    bool swapped{};             // Optimization. If there is now more swap, we can stop
    size_t n{ numberOfRows };   // NUmber of rows in our 2d array
    do {
        swapped = false;        // In the beginning, we did not do any swapping
        for (size_t row{}; row < (n - 1);   row)

            // We must call the function everytime, because the rows are swapped
            if (sumOfPositiveEvenValuesIn(row) > sumOfPositiveEvenValuesIn(row   1)) {

                // Swap pointer only. Do not touchg column values at all
                std::swap(data[row], data[row   1]);
                swapped = true;
            }
        --n;
    } while (swapped);
}

int main() {

    // Define iportant variables
    size_t rowCount{}, columnCount{}, allocaterSelection{};
    Allocater allocater{};
    // Shwo main menu
    std::cout << "nnYou need to specify 3 values:n"
        "1. Enter the allocater methodn"
        "   Enter 1 for malloc      orn"
        "   Enter 2 for calloc      orn"
        "   Enter any other number for newn"
        "2. Then enter the number of rowsn"
        "3. Then enter the number of columns.nn";

    // Get user selection and check, if that worked
    if (std::cin >> allocaterSelection >> rowCount >> columnCount) {
        // Depending on user selection for the allocation algorithm
        switch (allocaterSelection) {
        case 1:
            allocater = Allocater::Malloc;
            break;
        case 2:
            allocater = Allocater::Calloc;
            break;
        default: // fallthrough
        case 3:
            allocater = Allocater::New;
            break;
        }

        // Now define our array and initialize all data
        Array2D array2d(rowCount, columnCount, allocater);

        // Show data to user
        std::cout << "nnnData:nn" << array2d;

        // Sort
        array2d.sort();

        // Show sorted data to user
        std::cout << "Sortednn" << array2d;
    }
    return 0;
}
 

В случае возникновения вопросов, пожалуйста, задавайте.

Что на самом деле помогло мне:

 void swapInitial(int** arr, int* sumRows, int rows, int columns) {
    bool swapped;
    for (int i = 0; i < rows - 1; i  )
    {
        swapped = false;

        for (int k = 0; k < rows - i - 1; k  ) {
            if (sumRows[k] > sumRows[k   1])
            {
                swap(arr[k], arr[k   1]); 
                swap(sumRows[k], sumRows[k   1]); 
                swapped = true;
            }
        }

        if (swapped == false) break;
    }
}