Алгоритм перевода двумерного массива в одномерный

@Trombovoz · Регистрация: 29.12.2013

Author24 — интернет-сервис помощи студентам

Доброй ночи, Форумчане! У меня есть вопросы по заданию. Задание я выполнил, программа работает, всё правильно выводит. Думаю, сейчас сдам! Не тут то было... Меня с таким кодом послали куда подальше и в итоге сказали переделывать....

Вообщем, суть задания в том:

У нас дана матрица NxM с отсортированными по возрастанию строками (для простоты я думаю вводить матрицу в ручную). Составить алгоритм перевода этой матрицы в одномерный отсортированный ( так же по возрастанию) массив.

Т.е. должно получится так:

1 2 3
4 5 6 -----> 1 2 3 4 5 6 7 8 9 (числа взял с потолка)
7 8 9

Как сделал Я:
Тупо создал двумерный массив, отсортировал по возрастанию строк (это уже лишне), затем перевёл в одномерный массив и отсортировал его. Всё это, на языке преподавателя, просто. Слишком просто сделал.

Как нужно:
Нужно чтобы был алгоритм и он сразу переводил в одномерный отсортированный массив.

Код полностью не нашёл, т.к. посеял флешку, но вот наскрёб наброски на компе! Этот код не сортирует по возрастанию строк матрицу, а в целом, работает так же!

За любые подсказки и пенки буду благодарен!)

C++

#include <iostream>
#include <ctime>
#include <iomanip>
using namespace std;
int main(int argc, char *argv[])
{
    // Создаем двумерный массив и память под него
    cout << "Vvedite kol-vo strok ";
    int n, m;
    cin >> n; cout << "Vvedite kol-vo stolbcov "; cin >> m;
    int **mass = new int *[n];
    for (int i = 0; i<n; i++)
        mass[i] = new int[m];
    cout << "Massive:\n";
    for (int i = 0; i<n; i++)
    {
        for (int j = 0; j<m; j++)
        {
            mass[i][j] = 1 + rand() % 100;
            cout << setw(4) << mass[i][j];
        }
        cout << endl;
    }
 
    // переводим его в одномерный
    int *mass_odnom = new int[n*m];
    int k = 0;
    cout << endl << "Odnomerniyu massive: ";
    for (int i = 0; i<n; i++)
    {
        for (int j = 0; j<m; j++)
        {
            mass_odnom[k] = mass[i][j];
            cout << mass_odnom[k] << " ";
            k++;
        }
    }
    cout << endl;
 
 
    ///////////////////////////////////////////////////////////////// сортируем массив
    int j;
    cout << endl << "Otsortirovanyiu massive: ";
    for (int i = 0; i < k; i++)
    {
        int tmp = mass_odnom[i];
        for (j = i - 1; j >= 0 && mass_odnom[j] > tmp; --j)
        {
            mass_odnom[j + 1] = mass_odnom[j];
        }
        mass_odnom[j + 1] = tmp;
    }
    for (int i = 0; i < k; i++)
    {
        cout << mass_odnom[i] << " ";
    }
 
 
    ////////////////////////////////////////////////////////////// очищаем память
    for (int i = 0; i<n; i++)
        delete[]mass[i];
    delete[]mass_odnom;
    system("pause");
    return 0;

Добавлено через 9 часов 59 минут
спасибо, товарищи, за "помощь"!

@Tordek · 23.01.2015, 14:59

Быть может твой учитель подразумевал это...

C++

int mass[n][m];//То бишь, ты имеешь такие два массива.
int mass_odnom[n*m];
int k=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{mass_odnom[i*(m-1)+j]=mass[i][j];
k++;//кол-во элементов в одномерном массиве
if(k>1)
    {if(mass_odnom[i*(m-1)+j]<mass_odnom[i*(m-1)+j-1])
        {int min=mass_odnom[i*(m-1)+j];
         mass_odnom[i*(m-1)+j]=mass_odnom[i*(m-1)+j-1];
         mass_odnom[i*(m-1)+j-1]=min;
         for(int q=0;q<k-1;q++)
         for(int w=q+1;w<k)
            {if(mass_odnom[i*(m-1)+j-q]<mass_odnom[i*(m-1)+j-w])
                {int m=mass_odnom[i*(m-1)+j-q];
                 mass_odnom[i*(m-1)+j-q]=mass_odnom[i*(m-1)+j-w];
                 mass_odnom[i*(m-1)+j-w]=m;
                }
            }
        }
    }
}

Выглядит неоправданно сложно, но зато одномерный массив сортируется по мере своего заполнения. Может подойдёт?

@Trombovoz · 23.01.2015, 15:27 **[ТС]**

Как-то непонятно и запутанно..... Боюсь объяснить алгоритм не смогу!.....

@Tordek · 24.01.2015, 00:03

По сути то же самое, только сразу всё вместе.

@Trombovoz · 24.01.2015, 00:45 **[ТС]**

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

@Tordek · 24.01.2015, 16:57

Окей, тебе обязательно массивы создавать динамические?

Добавлено через 15 секунд
Если нет - скину программу

Добавлено через 8 минут
Если да - всё-равно скину

Добавлено через 2 минуты

Добавлено через 51 минуту

C++

#include <iostream>
#include <ctime>
#include <iomanip>
using namespace std;
int main(int argc, char *argv[])
{
    // Создаем двумерный массив и память под него
    cout << "Vvedite kol-vo strok ";
    int n, m;
    cin >> n; cout << "Vvedite kol-vo stolbcov "; cin >> m;
    int **mass = new int *[n];
    for (int i = 0; i<n; i++)
        mass[i] = new int[m];
    cout << "Massive:\n";
    for (int i = 0; i<n; i++)
    {
        for (int j = 0; j<m; j++)
        {
            mass[i][j] = 1 + rand() % 100;
            cout << setw(4) << mass[i][j];
        }
        cout << endl;
    }//сортируем и переводим его в одномерный одновременно
int *mass_odnom = new int[n*m];
int k = 0;
cout << endl << "Odnomerniyu massive: ";
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)//циклы прохода двумерного массива, опираясь на которые мы выражаем одномерный
{mass_odnom[i*m+j]=mass[i][j];//по формуле, где m - кол-во столбцов, i*m - кол-во столбцов в полностью //пройденных строках(текущее i - номер текуще строки или кол-во уже пройденных(т.к. номера строк начинаются //с 0)),j - номер текущего столбца
k++;//кол-во элементов в одномерном массиве (увеличивается за каждую итерацию внутреннего цикла)
if(k>1)//если заполнилось больше одного элемента массива
    {for(int q=0;q<k-1;q++)//
       for(int w=q+1;w<k;w++)
         {if(mass_odnom[i*m+j-q]<mass_odnom[i*m+j-w])//элементарный метод пузырька, только мы сравниваем //назад
             {int m=mass_odnom[i*m+j-q];
              mass_odnom[i*m+j-q]=mass_odnom[i*m+j-w];
              mass_odnom[i*m+j-w]=m;
             }//Таким образом получаем отсортированый одномерный массив от меньшего к большему
         }
    }
}cout<<"Odnomerniyu otsortirovanyiu massive: "//Выводим его
for(int p=0;p<n*m;p++)
cout<<mass_odnom[p]<<" ";
 
 
 ////////////////////////////////////////////////////////////// очищаем память
    for (int i = 0; i<n; i++)
        delete[]mass[i];
    delete[]mass_odnom;
    system("pause");
    return 0;

Вот и всё

Добавлено через 46 секунд
Я в предыдущей писульке пару ошибок и ненужностей допустил

@Trombovoz · 24.01.2015, 23:30 **[ТС]**

Спасибо! Очень выручили

Я, правда, тоже пыхтел, и сделал немного другим вариантом.

@lex2148 · 15.03.2015, 10:24

Tordek, а можно ваш алгоритм переделать так чтобы первые элементы строк записывались в промежуточный массив, из него наименьший элемент идёт в результат а на место него следующий элемент этой же строки (по сути сбалансированное н-ленточное слияние)?

Добавлено через 9 минут
Trombovoz, можешь скинуть свой вариант? делаю практически то же самое

@Tordek · 15.03.2015, 15:04

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

@lex2148 · 15.03.2015, 17:35

можете помочь с такой сортировкой массива? я просто не знаю что делать если одна из строк заканчивается. А вообще задание такое - реализовать н ленточное сбалансированное слияние на примере массива структур. Ключевое поле char, информационные - int и char[]

Добавлено через 3 минуты
для начала я решил это сделать на интовом массиве для простоты. Записываю массив в матрицу, где строки - ленты. Сортирую содержимое строк методом вставок. Теперь отсортированные строки нужно многопутевым слиянием слить в одномерный массив обратно. То же самое проделать со структурами

Добавлено через 20 секунд
буду очень признателен!

@Trombovoz 2 / 2 / 0 Регистрация: 29.12.2013 Сообщений: 81
	23.01.2015, 15:27 [ТС]	3
	Как-то непонятно и запутанно..... Боюсь объяснить алгоритм не смогу!..... 0

@Tordek 58 / 51 / 38 Регистрация: 22.01.2015 Сообщений: 176
	24.01.2015, 00:03	4
	По сути то же самое, только сразу всё вместе. 1

@Trombovoz 2 / 2 / 0 Регистрация: 29.12.2013 Сообщений: 81
	24.01.2015, 00:45 [ТС]	5
	Можешь, пожалуйста, показать как будет выглядеть полностью программа? А то я что то догнать не могу.... 0

@Trombovoz 2 / 2 / 0 Регистрация: 29.12.2013 Сообщений: 81
	24.01.2015, 23:30 [ТС]	7
	Спасибо! Очень выручили Я, правда, тоже пыхтел, и сделал немного другим вариантом. 0

@lex2148 0 / 0 / 0 Регистрация: 15.03.2015 Сообщений: 14
	15.03.2015, 10:24	8
	Tordek, а можно ваш алгоритм переделать так чтобы первые элементы строк записывались в промежуточный массив, из него наименьший элемент идёт в результат а на место него следующий элемент этой же строки (по сути сбалансированное н-ленточное слияние)? Добавлено через 9 минут Trombovoz, можешь скинуть свой вариант? делаю практически то же самое 0

@Tordek 58 / 51 / 38 Регистрация: 22.01.2015 Сообщений: 176
	15.03.2015, 15:04	9
	lex2148, можно, но получим совершенно иной результат, так как массив не будет отсортирован должным образом. 1

@lex2148 0 / 0 / 0 Регистрация: 15.03.2015 Сообщений: 14
	15.03.2015, 17:35	10
	можете помочь с такой сортировкой массива? я просто не знаю что делать если одна из строк заканчивается. А вообще задание такое - реализовать н ленточное сбалансированное слияние на примере массива структур. Ключевое поле char, информационные - int и char[] Добавлено через 3 минуты для начала я решил это сделать на интовом массиве для простоты. Записываю массив в матрицу, где строки - ленты. Сортирую содержимое строк методом вставок. Теперь отсортированные строки нужно многопутевым слиянием слить в одномерный массив обратно. То же самое проделать со структурами Добавлено через 20 секунд буду очень признателен! 0

Алгоритм перевода двумерного массива в одномерный

Решение