Spajanje dva sortirana polja

poruka: 6
|
čitano: 1.495
|
moderatori: Danny_HR, Lazarus Long, XXX-Man, vincimus
1
+/- sve poruke
ravni prikaz
starije poruke gore
10 godina
offline
Spajanje dva sortirana polja

Pozdrav,

 

trebalo bi spojiti dva sortirana polja, različitih veličina, uz uvjet da se elementi u novodobivenom polju NE smiju ponavljati. Moj je kôd:

 

void pospajajPolja (int polje1[], int polje2[], int n1, int n2, int spojeno[]) {
int a=0, b=0, c=0;

                           //polje1 je dakle prvo sortirano polje, polje2 drugo sortirano polje
while (a < n1 && b < n2) {                          //a je index prvog, b index drugog, a c index treceg (spojenog) polja
   if (polje1[a] < polje2[b])                         //n1 i n2 su velicine prvog, odnosno drugog polja
     spojeno[c++] = polje1[a++];                       //spojeno[] je polje nakon spajanja  
   else if (polje1[a] > polje2[b])
     spojeno[c++] = polje2[b++];
   else {
     spojeno[c++] = polje1[a++];
     b++;
   }
}

while (a < n1)
   spojeno[c++] = polje1[a++];

while (b < n2)
   spojeno[c++] = polje2[b++];

}

 

No ispisuje mi neke random brojeve, recimo na primjeru:

 

int polje1[6]={1,5,7,8,9,13};
int polje2[3]={4,5,8};

 

izlaz je: 1 4 5 7 8 9 13 0 985072304

 

Možete li pomoći, uputiti gdje sam se izgubio?

ZOTAC: It's Time to Play.
Poruka je uređivana zadnji put ned 1.2.2015 16:48 (DmL).
Moj PC  
0 0 hvala 0
8 godina
neaktivan
offline
Re: Spajanje dva sortirana polja

C ili C++? Smiješ koristiti kontejnere ili ne?

10 godina
offline
Re: Spajanje dva sortirana polja
TracerCPP kaže...

C ili C++? Smiješ koristiti kontejnere ili ne?

 Hvala na odgovoru, upravo sam shvatio gdje sam pogriješio. Ne smijem ništa drugo osim polja, radim u C-u.

 

Naime prilikom ispisa polja spojeno nisam išao do indeksa c, nego do zbroja duljine polja1 i polja2, od tuda takav čudan ispis, jer bi duljina polja spojeno bila naravno manja nego zbroj tih indeksa.

 

Inače, cijela funkcija je tu, u C-u. (nadam se da je ok, koliko sam testirao, radi):

 

void pospajajPolja (int polje1[], int polje2[], int n1, int n2, int spojeno[]) {
   int a=0, b=0, c=0;
   int i;

while (a < n1 && b < n2) {
   if (polje1[a] < polje2[b])
     spojeno[c++] = polje1[a++];
   else if (polje1[a] > polje2[b])
     spojeno[c++] = polje2[b++];
   else {
     spojeno[c++] = polje1[a++];
     b++;
   }
}

while (a < n1)
   spojeno[c++] = polje1[a++];

while (b < n2)
   spojeno[c++] = polje2[b++];

printf("Polje1:\n");
for (i=0; i<n1; i++)
printf("%d ", polje1[i]);

printf("\nPolje2:\n");
for (i=0; i<n2; i++)
   printf("%d ", polje2[i]);

printf("\nSpojeno polje:\n");
for (i=0; i<c; i++)
   printf("%d ", spojeno[i]);

}

 

 

U prvom slučaju NE radi, u drugom radi kako treba:

slika - primjer slika - primjer
 

 

 

EDIT: sada sam skužio da ne štima nešto... Valjda u slučaju kad su u prvom polju ili drugom polju duplicirani elementi ne radi, inače radi ako su različiti u prva dva, ali isti zajedno.

 

ZOTAC: It's Time to Play.
Poruka je uređivana zadnji put ned 1.2.2015 17:43 (DmL).
7 godina
offline
Re: Spajanje dva sortirana polja

Nisi dobro obradio slučaj polje[a] = polje[b]. Treba kopirati oba elementa u spojeno.

 

   ...
   else {
     spojeno[c++] = polje1[a++];
     spojeno[c++] = polje2[b++];
   }

 

Ti kopiraš samo polje1. Rezultat ima dva kopiranja manje (jer se nizovi poklapaju u brojevima 5 i 8) pa su zadnja dva elementa rezultata garbage.

Poruka je uređivana zadnji put ned 1.2.2015 18:48 (Bobobo-bo Bo-bobo).
10 godina
offline
Re: Spajanje dva sortirana polja
Bobobo-bo Bo-bobo kaže...

Nisi dobro obradio slučaj polje[a] = polje[b]. Treba kopirati oba elementa u spojeno.

 

   ...
   else {
     spojeno[c++] = polje1[a++];
     spojeno[c++] = polje2[b++];
   }

 

Ti kopiraš samo polje1. Rezultat ima dva kopiranja manje (jer se nizovi poklapaju u brojevima 5 i 8) pa su zadnja dva elementa rezultata garbage.

 Hmm. Ako stavim spojeno[c++] = polje2[b++], opet dobijem duplicirano polje u spojeno, a ne bi trebalo...

ZOTAC: It's Time to Play.
11 godina
neaktivan
offline
Spajanje dva sortirana polja

Trebaš provjeravati i novi niz da ti se ne ponavljaju elementi ako nizovi imaju duplikate ne samo među sobom.

 

 

 

#include<iostream>
using namespace std;


void pospajajPolja(int polje1[], int polje2[], int n1, int n2, int spojeno[]) {
   int a = 0, b = 0, c = 0;
   int i;
   if (polje1[a] < polje2[b])
      spojeno[c++] = polje1[a++];
   else if (polje1[a] > polje2[b])
      spojeno[c++] = polje2[b++];
   else
   {
      spojeno[c++] = polje1[a++];
      b++;
   }


   while (a < n1 && b < n2) {
      if (polje1[a] < polje2[b])
      {
         if (polje1[a] != spojeno[c-1])
            spojeno[c++] = polje1[a++];
         else a++;
      }
      else if (polje1[a] > polje2[b])
      {
         if (polje2[b] != spojeno[c-1])
            spojeno[c++] = polje2[b++];
         else b++;
      }
      else {
         if (polje1[a] != spojeno[c - 1])
         {
            spojeno[c++] = polje1[a++];
            b++;
         }
         else
         {
            a++;
            b++;
         }
      }
   }

      while (a < n1)
      if (polje1[a] != spojeno[c-1])
         spojeno[c++] = polje1[a++];
      else a++;

      while (b < n2)
      if (polje2[b] != spojeno[c-1])
         spojeno[c++] = polje2[b++];
      else b++;

   printf("Polje1:\n");
   for (i = 0; i<n1; i++)
      printf("%d ", polje1[i]);

   printf("\nPolje2:\n");
   for (i = 0; i<n2; i++)
      printf("%d ", polje2[i]);

   printf("\nSpojeno polje:\n");
   for (i = 0; i<c; i++)
      printf("%d ", spojeno[i]);

}

int main()
{
   int A[] = { 1, 1, 2, 4, 6, 6, 8, 9 };
   int B[] = { 1, 5, 5 };
   int C[30];
   pospajajPolja(A, B, 8, 3, C);

   return 0;
}

Poruka je uređivana zadnji put ned 1.2.2015 21:07 (Floki).
 
0 0 hvala 1
1
Nova poruka
E-mail:
Lozinka:
 
vrh stranice