Prikaži potpunu verziju : JS i DS liste
Je l' može neko da napiše sortiranje ovih listi u opadajućem odnosno rastućem redosledu?
Hvala.
Geomaster
10.9.2011, 22:34
Ja stvarno ne znam šta su JS i DS liste, od čega su to akronimi?
jednostruko spregnuto liste i dvostruko spregnute liste.
druže hvala, ali je l' može na prostiji način, imam to za ispit a nigde ne mogu da nađem?
Geomaster
10.9.2011, 23:25
druže hvala, ali je l' može na prostiji način, imam to za ispit a nigde ne mogu da nađem?
Obrisao sam poruku pošto je bila jedna greška, sad žurim pa ne mogu da isrpavljam. Za 20ak minuta ću da napišem za duple.
Ovo je za jednostruko povezane liste
#include <cstdlib>
#include <cstdio>
class Node
{
public:
int data;
Node* next;
};
inline void swapNodes(Node* n1, Node* n2)
{
Node tmp = *n1;
n1->data = n2->data;
n2->data = tmp.data;
}
int main(int argc, char** argv)
{
// Ovde pravimo listu tako što definišemo 5 elemenata,
// a zatim ih lančamo
Node a, b, c, d, e;
a.data = 7;
a.next = &b; // next pokazuje na sledeći element u listi
b.data = 3;
b.next = &c;
c.data = 8;
c.next = &d;
d.data = 4;
d.next = &e;
e.data = 16;
e.next = NULL;
// Završili smo pravljenje liste, ovde počinjemo sortiranje
bool hasSwapped; // da li smo u iteraciji izvršili zamenu elemenata
do
{
hasSwapped = false; // u ovoj iteraciji nismo još zamenili
Node* n = &a; // pokazivač ka trenutnom elementu, počinje od prvog
while (n->next) // idemo do pretposlednjeg elementa
{
if (n->data > n->next->data) // ako je trenutni veći od sledećeg, samo ih zamenimo i zapamtimo da smo izvršili menjanje
swapNodes(n, n->next), hasSwapped = true;
n = n->next; // idemo na sledeći
}
} while (hasSwapped); // ponavljamo sve dok smo izvršili bar jednu zamenu
// sad je lista sortirana, ispisujemo rezultat
Node* n = &a;
while (n)
printf("%d ", n->data), n = n->next;
return 0;
}
Naravno, sigurno bi učitavao listu odnegde, ja sam stavio bezveze neku čisto da imamo neke podatke sa kojima radimo.
Za dvostruko povezane liste bio bi samo malo drugačiji kôd:
#include <cstdlib>
#include <cstdio>
class Node
{
public:
int data;
Node* previous;
Node* next;
};
inline void swapNodes(Node* n1, Node* n2)
{
Node tmp = *n1;
n1->data = n2->data;
n2->data = tmp.data;
}
int main(int argc, char** argv)
{
// Ovde pravimo listu tako što definišemo 5 elemenata,
// a zatim ih lančamo
Node a, b, c, d, e;
a.data = 7;
a.previous = NULL; // previous pokazuje na prethodni element u listi
a.next = &b; // next pokazuje na sledeći element u listi
b.data = 3;
b.previous = &a;
b.next = &c;
c.data = 8;
c.previous = &b;
c.next = &d;
d.data = 4;
d.previous = &c;
d.next = &e;
e.data = 16;
e.previous = &d;
e.next = NULL;
// Završili smo pravljenje liste, ovde počinjemo sortiranje
bool hasSwapped; // da li smo u iteraciji izvršili zamenu elemenata
do
{
hasSwapped = false; // u ovoj iteraciji nismo još zamenili
Node* n = &a; // pokazivač ka trenutnom elementu, počinje od prvog
while (n->next) // idemo do pretposlednjeg elementa
{
if (n->data > n->next->data) // ako je trenutni veći od sledećeg, samo ih zamenimo i zapamtimo da smo izvršili menjanje
swapNodes(n, n->next), hasSwapped = true;
n = n->next; // idemo na sledeći
}
} while (hasSwapped); // ponavljamo sve dok smo izvršili bar jednu zamenu
// sad je lista sortirana, ispisujemo rezultat
Node* n = &a;
while (n)
printf("%d ", n->data), n = n->next;
return 0;
}Ukoliko ti treba opadajući redosled, operator < menjaš u operator >. Nisam sigurno oko uprošćavanja, ovo izgleda minimalno, mislim na deo sa sortiranjem. Eventualno bi mogao da uradiš običan bruteforce O(scary) sorting.
@makky
Prostije od ovoga sto je Geo napisao ne moze, moze da se ispise daleko kraci kod ali onda to nece biti prosto za razumevanje pa mozda postane sumnjivo. :D
Geomaster
11.9.2011, 12:41
mmmmm da.
totalno si moderan majke mi.
To je bilo upućeno...?
O ovome je ovde već pisano, čini mi se, u ovoj temi http://www.sk.rs/forum/showthread.php?t=73595
Tu sam se ja lepo nalupao (slobodan stek umesto slobodno skladište :)), ali je poenta da se problem rešavao preko pokazivača. Kada u sortiranju menjamo data to može da nam se obije od glavu kad je objekat težak desetine ili stotine kilobajta. Ipak ćeš morati malo više da se pomučiš oko ovoga ako misliš da ti rešenje bude funkcionalno.
EDIT:
Naravno, mi možemo da stavimo da nam data u stvari bude pokazivač na neki objekat, ali to kad radimo program za sebe.
Pošto se ovde radi o ispitu ne verujem da se mislilo na prostu zamenu data već na manipulaciju sa pokazivačima. U suprotnom bi zadatak glasio sortiranje običnog niza a ne link liste.
Geomaster
11.9.2011, 13:49
Moje prvo rešenje je bilo sa zamenom pokazivača, ali je lik pitao da li može prostije i ja sam napisao prostije, sa zamenom podataka. Zamena sa pokazivačima u linked listi je malo čudna zato što moramo da znamo prethodnika odnosno moramo da čuvamo prethodni element negde.
@Geomaster u potpunosti se slažem sa tobom. Ja bi uradio isto sa zamenom data i, ko što sam i napisao, ako bi imao glomazne objekte data bi bila pokazivač na njih. Moj post je bio upućen makky_90 jer sam video da traži prostije rešenje a pošto se radi o ispitu ja mislim da će tu morati da ide komplikovanija varijanta sa zamenom pokazivača. Mada ... ko zna, možda mu prođe i ova varijanta.
vBulletin® v3.8.7, Copyright ©2000-2024, vBulletin Solutions, Inc.