Написать программу слияния двух упорядоченных массивов в третий
Идея. Если имеется две упорядоченные последовательности, то из них можно составить общую упорядоченную последовательность путем выбора минимального двух очередных элементов массивов. После переноса выбранного элемента он "убирается" из входной последовательности. Заметим, что при слиянии один массив может закончится раньше, чем другой, тогда слияние продолжается из одного оставшегося.
Варианты "убирания" выбранного элемента:
- сдвигать элементы в массиве влево, записывая в конец "очень большое число", которое играет роль "затычки";
- использовать индексы текущего элемента.
Последовательное проектирование программы .
1. Заголовок функции.
void sleave(int in1[], int in2[], int out[], int n)
{
_ 2. слить массивы in1[] и in2[] размерности n
_ в массив out[] размерности 2*n
}
2. Последовательно сливать по одному элементу из массивов в выходной массив - Шаг 3 - выбор цикла for (){}.
3. Переменная цикла-индекс очередного элемента в выходном массиве out .
for (int i=0; i< 2*n; i++)
{
_ 4. Выбрать очередной элемент, исключить и "слить" в out[i]
}
4. Используем вариант извлечения элементов "со сдвигом". В этом случае сравниваются элементы in1[0] и in2[0]. Выбирается и исключается элемент в зависимости от сравнения - выбираем условную конструкцию .
if (in1[0] < in2[0])
_Выбрать in1[0], исключить и перенести в out[i]
else
_Выбрать in2[0], исключить и перенести в out[i]
5. Поскольку одно и то же действие выполняется над двумя разными массивами, то его можно оформить в виде функции (отдельного модуля), которая будет иметь вид :
int get(int in[], int m)
{
_Извлечь из массива in[] размерности m
_первый элемент (in[0]), сдвинуть содержимое
_влево, записать в конец "очень большое число"
_и возвратить в виде результата извлеченный элемент
}
6. С вызовом еще не написанной функции фрагмент будет иметь вид :
if (in1[0] < in2[0])
out[i]=get(in1,n);
else
out[i]=get(in2,n);
7. Тело функции-простая последовательность действий :
int get(int in[], int m)
{
_1. Запомнить in[0]
_2. Сдвинуть содержимое in[] влево
_3. Записать в конец "очень большое число"
_4. Возвратить в виде результата извлеченный элемент
}
8. Окончательный вид функции:
int get(int in[], int m)
{
int v=in[0];
for (int i=1; i<m; i++) in[i-1]=in[i];
in[m-1]=MAXINT;
return v;
}
9. Окончательный вид функции слияния :
void sleave(int in1[], int in2[], int out[], int n)
{
for (int i=0; i< 2*n; i++)
if (in1[0] < in2[0])
out[i]=get(in1,n);
else
out[i]=get(in2,n);
}
