Предположим, что у вас есть массив из 5 символов и другой массив из 8 символов. Если эти два массива объединены в один, то оба массива были объединены. В новом массиве будет 13 символов (= 5 + 8). Порядок, в котором различные элементы массива расположены в новом массиве, не имеет значения; и это слияние двух массивов.
В C ++ существует техническая проблема в том смысле, что в результате получается три массива вместо одного нового объединенного массива. Было бы неплохо после слияния удалить два старых массива и освободить неиспользуемую память? В C ++ есть два способа объединения двух массивов: если два массива объединились, использовалась динамическая память, то их можно удалить, чтобы в итоге получился один массив; в противном случае программист получает три массива.
Слияние массивов путем простого размещения одного массива позади другого — это хорошо; но может быть лучше иметь минимальную сортировку по мере объединения массивов. Сортировка в целом — это целая тема в программировании. Сортировка в целом в этой статье не рассматривается. Однако рассматривается очень простая минимальная сортировка.
В этой статье объясняется, как объединить два массива, чтобы получить три массива, и как объединить два массива, чтобы получить один массив. Также рассматривается некоторая минимальная сортировка. Чтобы объединить два массива, они должны быть одного типа.
Процедура объединения двух массивов может быть расширена до более чем двух массивов.
Слияние массивов без бесплатного хранилища
Слияние без сортировки
Рассмотрим следующие два массива:
char arr1[] = {‘I’, ‘J’, ‘K’, ‘L’, ‘M’};
char arr2[] = {‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’, ‘H’};
В первом 5 элементов, а во втором 8 элементов. Если элементы второго массива каким-либо образом подогнать к задней части первого массива, будет сформирован массив из 13 элементов. Чтобы достичь этого без использования свободного хранилища (динамической памяти), сначала необходимо создать третий массив из 13 пустых значений. Затем 5 значений первого массива будут скопированы в первые 5 местоположений третьего массива. Затем 8 значений второго массива будут скопированы в оставшиеся 8 позиций третьего массива. Третий массив становится объединенным и желаемым массивом. Следующая программа иллюстрирует это:
#include <iostream>
using namespace std;
int main()
{
char arr1[] = {‘I’, ‘J’, ‘K’, ‘L’, ‘M’};char arr2[] = {‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’, ‘H’};
char arr3[13];
for (int i=0; i< 5; i++) {
arr3[i] = arr1[i];
}for (int i=5; i< 13; i++) {
arr3[i] = arr2[i—5];
}for (int i=0; i< 13; i++) {
cout<< arr3[i] << ‘ ‘;
}
cout<<endl;return 0;
}
Результат:
I J K L M A B C D E F G H
Обратите внимание на то, как индексация использовалась в циклах for. Проблема этой схемы в том, что первые два массива стали избыточными. Теперь они без надобности занимают память компьютера. Без свободного хранилища (динамической памяти) массивы не могут быть удалены из памяти, пока они не выйдут за пределы области видимости. Чтобы решить эту проблему, воспользуйтесь бесплатным магазином — см. Ниже.
Первый сегмент кода включает библиотеку iostream и объявляет об использовании стандартного пространства имен для остальной части программы. Остальная часть программы находится в функции main (). Первые три оператора в функции main () объявляют первый, второй и третий массивы. Следующий сегмент кода — это цикл for, который копирует все элементы из меньшего массива в третий массив. Первым можно было скопировать больший массив из первых двух; не важно.
Следующий сегмент кода использует цикл for для копирования большего массива в заднюю часть меньшего массива, уже находящегося в третьем массиве. Третий массив — это объединенный массив. Сумма количества элементов в первых двух массивах должна равняться количеству элементов в третьем массиве. Последний сегмент кода отображает значения третьего массива.
Слияние с некоторой сортировкой
При вставке элементов в третий массив вначале можно сравнивать первые элементы обоих массивов, а меньшее значение вставлять первым перед первым значением другого массива. Затем можно сравнить вторые элементы обоих массивов, и меньшее значение, вставленное в третий массив, перед вторым значением другого массива будет вставлено. Затем можно сравнить третьи элементы обоих массивов, а меньшее значение вставить перед третьим значением другого массива. Эта процедура продолжается до тех пор, пока все элементы более короткого массива не будут вставлены вместе с одинаковым количеством элементов более длинного массива. Остальные элементы более длинного массива можно просто вставить в третий массив в их порядке. Следующая программа иллюстрирует это:
#include <iostream>
using namespace std;
int main()
{
char arr1[] = {‘I’, ‘J’, ‘K’, ‘L’, ‘M’};char arr2[] = {‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’, ‘H’};
char arr3[13];
for (int i=0; i< 5; i++) {
if (arr1[i] < arr2[i]) {
arr3[i*2] = arr1[i];
arr3[i*2+1] = arr2[i];
}
else {
arr3[i*2] = arr2[i];
arr3[i*2+1] = arr1[i];
}
}for (int i=5; i< 8; i++) {
arr3[i+5] = arr2[i];
}for (int i=0; i< 13; i++) {
cout<< arr3[i] << ‘ ‘;
}
cout<<endl;return 0;
}
Результат:
A I B J C K D L E M F G H
Обратите внимание на арифметику, используемую в индексах.
Слияние массивов с использованием бесплатного хранилища
Слияние без сортировки
Свободное хранилище — это память, выделенная программе, которая будет использоваться, когда ей потребуется дополнительная память. Массив можно создавать и удалять в бесплатном хранилище с помощью оператора new [] и оператора delete [] соответственно. Две вышеуказанные программы будут повторены ниже. Первый и второй массивы будут создаваться динамически в свободном хранилище и удаляться после создания третьего объединенного массива. Третий массив будет создан в нормальной памяти (области).
Следующая программа иллюстрирует это для слияния без сортировки:
#include <iostream>
using namespace std;
int main()
{
char *arr1 = new char[5];
arr1[0] = ‘I’; arr1[1] = ‘J’; arr1[2] = ‘K’; arr1[3] = ‘L’; arr1[4] = ‘M’;char *arr2 = new char[8];
arr2[0] = ‘A’; arr2[1] = ‘B’; arr2[2] = ‘C’; arr2[3] = ‘D’; arr2[4] = ‘E’; arr2[5] = ‘F’; arr2[6] = ‘G’; arr2[7] = ‘H’;char arr3[13];
//merging
for (int i=0; i< 5; i++) {
arr3[i] = arr1[i];
}
for (int i=5; i< 13; i++) {
arr3[i] = arr2[i—5];
}delete[] arr1;
delete[] arr2;for (int i=0; i< 13; i++) {
cout<< arr3[i] << ‘ ‘;
}
cout<<endl;return 0;
}
Результат:
I J K L M A B C D E F G H
Имена массивов в бесплатном хранилище — указатели. Расположение элементов arr1 и arr2 было удалено после их использования в программе. Остальной код похож на предыдущий.
Слияние с некоторой сортировкой
Здесь повторяется предыдущая программа с некоторой сортировкой. Однако здесь первый и второй массивы создаются в бесплатном хранилище. Они удаляются после использования. Программа:
#include
с использованием пространства имен std ;
int main ( )
{
char * arr1 = новый символ [ 5 ] ;
arr1 [ 0 ] = «Я» ; arr1 [ 1 ] = ’J’ ; arr1 [ 2 ] = ’K’ ; arr1 [ 3 ] = ’L’ ; arr1 [ 4 ] = ’М’ ;символ * arr2 = новый символ [ 8 ] ;
arr2 [ 0 ] = ’А’ ; arr2 [ 1 ] = ’B’ ; arr2 [ 2 ] = ’C’ ; arr2 [ 3 ] = ’D’ ; arr2 [ 4 ] = ’E’ ; arr2 [ 5 ] = ’F’ ; arr2 [ 6 ] = ’G’; arr2 [ 7 ] = ’H’ ;char arr3 [ 13 ] ;
// объединение
для ( int i = 0 ; i < 5 ; i ++ ) {
if ( arr1 [ i ] < arr2 [ i ] ) {
arr3 [ i * 2 ] = arr1 [ i ] ;
arr3 [ я * 2 + 1 ] = arr2 [ i ] ;
}
еще {
arr3 [ i * 2 ] = arr2 [ i ] ;
arr3 [ я * 2 + 1 ] = arr1 [ i ] ;
}
}
для ( int i = 5 ; i < 8; i ++ ) {
arr3 [ i + 5 ] = arr2 [ i ] ;
}удалить [ ] arr1 ;
удалить [ ] arr2 ;для ( int я = 0 ; я < 13 ; я ++ ) {
cout << arr3 [ я ] << ’’ ;
}
cout << endl;возврат 0 ;
}
Результат:
A I B J C K D L E M F G H
Заключение
Слияние массивов на самом деле простая вещь. Просто в конечном итоге поместите один массив позади другого массива, и вы объедините два массива. Проблемы, с которыми сталкиваются программисты при объединении массивов, не связаны с размещением одного массива позади другого массива. Они связаны со стиранием двух предыдущих массивов и / или сортировкой объединенного массива. Для объединения массивы должны быть одного типа.
Если какой-либо из первых двух массивов больше не понадобится после слияния, его следует создать динамически в свободном хранилище, а затем удалить после использования, чтобы освободить память. Объединенный массив также можно создать в бесплатном магазине, но в этом нет необходимости.
Объединенный массив можно сортировать по разным размерам. Полная сортировка — это целая тема в компьютерном программировании. Полная сортировка осуществляется по разным схемам в компьютерном программировании. Есть схема, называемая сортировкой слиянием. Эта схема выполняет объединение и сортировку одновременно. Однако наиболее популярной схемой является быстрая сортировка.