[C++] połączenie list jednokierunkowych

[anilahcim]

Proszę o pomoc w zadaniu:


/*
Wstaw kopię podanej listy "fragment" do danej listy jednokierunkowej
"glowa" pomiędzy każdymi dwoma elementami

Przykład:
jeżeli funkcja zostanie wywołana dla listy (4, 7, 1, 3) z argumentem
fragment=(3, 2, 1), w wyniku otrzymamy listę
(4, 3, 2, 1, 7, 3, 2, 1, 1, 3, 2, 1, 3)

*/

Kod: Zaznacz cały

void wstaw_pomiedzy_dwa(wezel*& glowa, wezel* fragment)
{
	if (glowa==NULL || glowa->nast==NULL || fragment==NULL)
		return;
	
	wezel* w = glowa;
	wezel* w2 = glowa->nast;
	
	while (w2!=NULL)
	{
		w->nast = fragment;
		w = w->nast;
		while (w->nast!=NULL)
			w = w->nast;
		w->nast = w2;
		w = w2;
		w2 = w->nast;
	}
}

Przy pierwszym przejściu pętli wszystko jest ok, ale już przy drugim pętla

Kod: Zaznacz cały

		while (w->nast!=NULL)
			w = w->nast;

działa w nieskończoność. Nie rozumiem, dlaczego tak się dzieje. Dlaczego 'w->nast' nigdy nie jest nullem? Przecież 'w' wskazuje na 'fragment', który w końcu kończy się nullem...
Sprawdzałam, czy kod działa, jeśli fragment wkleić tylko raz (czyli bez tego zewnętrznego whila) i wtedy wszystko jest ok.

[Tulio]

Na pewno pętla wewnętrzna działa w nieskończoność?
Zrób tak... wklei kod od linii 11 do 17 trzy razy (czy ile przewidujesz, że ma się wykonać dla przykładu) i wywal zewnętrzną pętlę. Sprawdź czy przejdzie. Mnie właśnie zastanawia czy w2 będzie kiedyś nullem, ale nie mogę sobie tego wyobrazić.

[royas]

Masz wstawiać kopie listy fragment, nie widzę, żebyś tworzyła kopię, a po prostu wstawiasz ją.
Przez co w drugim przebiegu pętli w linii 11 zapętlasz listę.

[anilahcim]

Nawet nie wiem do końca jak zrobić kopię listy...

Czy chodzi o coś takiego (pewnie nie, bo nadal nie działa)?

Kod: Zaznacz cały

	wezel* f = new wezel;
   f->wartosc = fragment->wartosc;
   f->nast = fragment->nast;

Tylko ciągle nie rozumiem: dlaczego lista się zapętla, jeśli wstawiam 'fragment', a nie kopię?

[royas]

Kopiowanie prawie dobrze, ale musisz skopiować całą listę a nie tylko pierwszy element.
Teraz masz tak: ->! to wskaźnik na null., W - w, X - w2.
Przed pierwszym wejściem w pętlę.

Kod: Zaznacz cały

W  X
1->2->3->!

F
a->b->!

Po pierwszym przejściu pętli:

Kod: Zaznacz cały

1->a->b->2->3->!
   F     W  X

I w drugim obiegu pętli w linii 11 przepisznasz wskaźnik z 2 na a (wskazywane przez F) i masz pętlę.

[anilahcim]

Czy kopiowanie listy powinno wyglądać tak?

Kod: Zaznacz cały

wezel* f = new wezel;
	f->wartosc = fragment->wartosc;
	f->nast = fragment->nast;
	wezel* k = f;
	while(fragment!=0)
	{
		f->wartosc = fragment->wartosc;
		f->nast = fragment->nast;
		f = f->nast;
		fragment = fragment->nast;
	}
	f = k;

Da się to prościej napisać? Czy pierwszy element trzeba zrobić oddzielnie, żeby zapamiętać na niego wskaźnik?

A dalej, w pętli, próbowałam wcisnąć tam gdzieś jeszcze wskaźnik na NULL, żeby pętla się kończyła - czy to dobra droga? Tylko jeszcze nie doszłam do końca do tego gdzie i jak go wcisnąć...

[royas]

A ile nowych węzłów tworzysz jeśli fragment ma ich np. 4?

Myślę, że to powinno być coś w tym stylu:

Ukryta treść:    

wklejamy kopię listy f po węźle w:

Kod: Zaznacz cały

t=f;
w2=w->n;
while (t!=NULL) {
    w->n=new wezel;
    w=w->n;
    w->v=t->v;
    t=t->n;
}
w->n=w2;

[anilahcim]

Ok, bardzo dziękuję. Nie wpadłam na to, że trzeba tworzyć nowe węzły