0

После сортировки в массиве NxN появляется мусор, с каждым разом мусор в разных местах.

Помогите решить проблему.

#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>

using namespace std;

void siftDown(int *numbers, int root, int bottom)       //формирование кучи
{
    int maxChild;                                       //индекс максимального потомка
    int done = 0;                                       //флаг, куча сформирована

    while ((root * 2 <= bottom) && (!done))             //пока не дошли до последнего ряда
    {
        if (root * 2 == bottom)                         //если мы в последнем ряду, 
            maxChild = root * 2;                        //запоминаем левый потомок

        else if (numbers[root * 2] > numbers[root * 2 + 1])     //иначе запоминаем больший потомок из двух
            maxChild = root * 2;
        else
            maxChild = root * 2 + 1;

        if (numbers[root] < numbers[maxChild])                  //если элемент вершины меньше максимального потомка
        {
            int temp = numbers[root];                           //меняем их местами
            numbers[root] = numbers[maxChild];
            numbers[maxChild] = temp;
            root = maxChild;
        }
        else 
            done = 1;                                           //пирамида сформирована
    }
}

void heapSort(int *numbers, int array_size)                     //сортировка
{

    for (int i = (array_size / 2) - 1; i >= 0; i--)             //нижний ряд пирамиды
        siftDown(numbers, i, array_size);

    for (int i = array_size - 1; i >= 1; i--)                   //просеиваем через пирамиду остальные элементы
    {
        int temp = numbers[0];
        numbers[0] = numbers[i];
        numbers[i] = temp;
        siftDown(numbers, 0, i - 1);
    }
}

int main() {

    int size;
    int R, C;
    int tempp[50];
    char *str = new char[30];

    ifstream inn("dann.txt");
    while (!inn.eof()) {                            //подсчет размера массива NxN

        inn.getline(str, '\n');
        size++;
        R = size;

    }


        //inn.seekg(0, ios_base::beg);
        inn.close();

        inn.open("dann.txt");

        int **arr = new int* [R];                   //создание динамического двумерного массива
        for (int i = 0; i < R; i++) {
            arr[i] = new int[R];
        }

        while (!inn.eof()) {                        //заполнение массива из файла   

            for (int i = 0; i < R; i++) {
                for (int j = 0; j <R; j++) {
                    inn >> arr[i][j];
                }
            }
        }

        for (int i = 0; i < R; i++) {               //вывод массива без сортировки
            for (int j = 0; j < R; j++) {
                cout << arr[i][j] << "\t";
            }
            cout << endl;
        }

        for (int i = 0; i < R; i++) {           //временное хранение столбца
            tempp[i] = arr[i][0];
        }

        heapSort(tempp, R);                     //вызов сортировки

        for (int i = 0; i < R; i++) {
            arr[i][0] = tempp[i]; 
        }


        for (int i = 0; i < R; i++) {               //вывод массива
            for (int j = 0; j < R; j++) {
                cout << arr[i][j] << "\t";
            }
            cout << endl;
        }

    for (int i = 0; i < R; i++) {               //очистка памяти от масива 
        delete[] arr[i];
    }
    delete[] arr;


inn.close();
system("pause");
return 0;
}

1 ответ 1

1

Ерунды в коде много, но что касается мусорных значений, то вот это ветвление в siftDown

    if (root * 2 == bottom)
        maxChild = root * 2;
    else if (numbers[root * 2] > numbers[root * 2 + 1])
        maxChild = root * 2;
    else
        maxChild = root * 2 + 1;

это какая-то белиберда. Величина bottom изначально - это размер массива. Поэтому по индексу bottom в массив доступаться нельзя - там в лучшем случае сидит мусор. У вас же запросто может получиться, что maxChild станет равно bottom, а потом мусор из numbers[maxChild] запросто может затянуться внутрь массива.

Равенство root * 2 == bottom говорит о том, что у узла вообще нет сыновей. В условии цикла сравнение должно быть строгим

while (root * 2 < bottom && !done) 

и т.д.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.