Алгоритъм за сливане на две наредени редици

Описаният алгоритъм за сливане на две наредени редици е валиден за две предварително сортирани както във възходящ ред, така и в низходящ ред. Предварително се знаят броят на елементите във всяка от редиците P1, P2, както и вида на наредбата им. Броят на елементите в новата (третата) редица ще бъде P = P1 + P2. Използват се допълнително две променливи M1, M2 съдържащи поредния номер елемент за всяка от редиците. Стъпките на алгоритъма са следните:

1) Сравняват се поредните елементи от двете редици с номер M1 и M2.
2) Ако елементът с номер М1 е по-малък или равен от елементът с номер М2 в третата редица се записва елементът с номер М1. Променливата М1 увеличава стойността си с 1.
Ако елементът с номер М1 е по-голям от елементът с номер М2 в третата редица се записва елементът с номер М2. Променливата М2 увеличава стойността си с 1.
3) Проверява се дали М1<Р1. Ако е да отива на стъпка 5), ако е не на стъпка 1).
4) Проверява се дали М2<Р2. Ако е да отива на стъпка 6), ако е не на стъпка 1).
5) Прехвърлят се останалите елементи от редица 2 в редица 3. Отива на стъпка 7.
6) Прехвърлят се останалите елементи от редица 1 в редица 3. Отива на стъпка 7.
7) Край на алгоритъма.

Да се състави програма, която като входни данни има 2 едномерни сортирани масива, съдържащи естествени числа от интервала [-5000 + 5000]. В общия случай двата масива са с различен брой елементи.
Да се изведе на екрана резултата от обединението на 2-та масива като елементите на новообразувания масив са също сортирани.
Пример:
{1,3,5,7,9,11,113} и {2,4,6,8,10,12,14,16,18,20}
Изход:
1,2,3,4,5,6,7,8,9,10,11,12,14,16,18,20,113
Следващата примерна програма дава решена задача за сливане на две наредени редици. Редиците са представени като стойности в два едномерни масива.

#include <iostream>  
#include<math.h>  
using namespace std;  

int main()  
{ const int n1=7, n2=10;//konstanta za broq elementi w redica   
int mas1[n1]={1,3,5,7,9,11,113};  // naredeni elementi w 1-wa redica    
int mas2[n2]={2,4,6,8,10,12,14,16,18,20};// naredeni elementi wyw 2-ra redica   
int mas3[n1+n2];  
int i,n,b1,b2;  
  cout<<"Da se systawi programa, koqto kato whodni danni ima 2\n";  
  cout<<"sortirani ednomerni masiwa sydyrvashi celi chisla w\n";  
  cout<<"interwala [-5000 + 5000]. W obshiq sluchaj masiwite sa s\n";  
  cout<<"razlichen broj promenliwi. Da se izwede na ekrana rezultatyt\n";  
  cout<<"ot obedinqwane na dwata masiwa kato elementite sa sortirani\n";  
  cout<<"w ednomeren masiw - sliwane na dwe naredeni redici.\n";  
  cout<<"Primer: {1,3,5,7,9,11,113} i {2,4,6,8,10,12,14,16,18,20}\n";  
  cout<<"Izhod 1,2,3,4,5,6,7,8,9,10,11,12,14,16,18,20,113\n";  
  cout<<"Nachalno systoqnie na dwata masiwa - redici: \n";  
 for (i=0;i<n1;i++) {cout<<" "<<mas1[i];}  
  cout<< endl;  
  for (i=0;i<n2;i++) {cout<<" "<<mas2[i];}  
  cout<< endl;    
  n=n1+n2;//dylvinata na nowiq masiw - redica e sumarnata dylvina ot 2-ta masiwa  
  b1=b2=0;//poziciqta w dwata masiwa   
  for (i=0;i<n;i++)  
  { if (b1<n1 && b2<n2) //wse oshe ima newywedeni elementi i ot dwata masiwa  
    {if (mas1[b1]<mas2[b2])  
      {//koj ot dwata masiwa sydyrva po-malko chislo s tozi indeks  
       mas3[i]=mas1[b1];    b1++;}//broq weche wywedeni elementi   
       else  
       { mas3[i]=mas2[b2];   b2++;}//kraj na prowerkata   
     }//if (b1<n1 && b2<n2  
   else //edin ot dwata masiwa e weche izcqlo wyweden  
    { if (b1<n1) {mas3[i] = mas1[b1]; b1++;}  
     else   {mas3[i] = mas2[b2]; b2++;}  
    }//kraj na prowerka dali ediniq ot masiwite e izcqlo wyweden  
   } // kraj na pyrwiq cikyl  
  cout<<"Obedineniqt masiw sydyrva: "<<endl;  
  for (i=0;i<n;i++)  {cout<<" "<<mas3[i]; }  
  cout<<endl;//pechat na obedineniq masiw  
 system("pause");
 return 0; 
} //kraj na programa - sliwane na dwe naredeni redici

Обяснени и решени задачи с подобни алгоритми, функции и служебни думи са разгледани в страницата с електронни уроци по информатика - програмиране.
Илюстриране работата на характерни алгоритми можете да намерите в предоставените електронни помагала съдържащи решени задачи, примери.

Начало на страницата

Размер на шрифта

Търсене в сайта:

Спонсори

Изпълними приложения за

Алгоритъм за сливане на две наредени редици