ďťż

Ładny brzuch

Witam, otóż od jakiegoś już czasu, szukam rozwiązania nurtującego mnie problemu, nie znalazłem jego rozwiązania w internecie, oraz w literaturze, choć być może tam ono jednak istnieje.
Przechodząc do meritum: mam do stworzenia klasę opierającą się na liście jednokierunkowej, oraz zaimplementowanie odpowiednich metod, jedną z nich jest połączenie dwóch list. Najlepiej zilustruje to kod:
#include <iostream> #include <string> #include <fstream> #include <sstream> using namespace std; struct wezel_t { string wartosc; struct wezel_t *nastepny; }; class Lista { public: struct wezel_t *pierwszy; public: Lista () { pierwszy = NULL; } ~Lista () { struct wezel_t *element = pierwszy; while(element) { struct wezel_t *nastepny = element->nastepny; delete element; element=nastepny; } } void Dodaj(string txt) { struct wezel_t *nowy = new struct wezel_t; nowy->wartosc = txt; nowy->nastepny=pierwszy; pierwszy=nowy; } void Dodaj(struct wezel_t *lista) { struct wezel_t *nowy = new struct wezel_t; nowy->wartosc = lista->wartosc; nowy->nastepny=pierwszy; pierwszy=nowy; } // Pozostałe metody jak sortuj, wypisz, szukaj, usun, zapisz, wczytaj, które działają poprawnie. int main() { Lista l; l.Wczytaj("plik1.txt"); l.sort_wstaw_ros(); l.Drukuj(); l.Zapisz("zapisz1.txt"); cout<<"Teraz wczytuje 2 liste"<<endl; Lista l2; l2.Wczytaj("plik2.txt"); l2.sort_wstaw_mal(); l2.Drukuj(); l2.Zapisz("zapisz2 .txt"); Lista t; //t.Polacz(); system("pause"); }
Mój pomysł na to łączenie to stworzenie 3 listy i wczytanie do niej po kolei pierwszej i drugiej listy, lub do pierwszej dodanie w jakiś sposób drugiej, jednak nie wiem w jaki sposób odwołać się do początków obu list tak aby móc na nich operować wewnątrz metody.



Proponuję utworzyć nową listę i kopiować kolejne elementy pierwszej i drugiej listy, iterując po nich, a następnie usunąć tamte dwie. Może niech będzie to metoda, która przyjmuje za argumenty wskaźniki do dwóch list, które ma połączyć?
Użytkownik Lupinek edytował ten post 29 maj 2009, 22:13
Utwórz nową metodę, która będzie przyjmowała wskaźnik na "wezel_t". Będziesz do niej przesyłał początek listy (wtedy skopiowane zostaną wszystkie elementy) lub dowolny element ze środka (wtedy skopiowane zostaną wszystkie od podanego do ostatniego). W metodzie przechodzisz przez kolejne elementy (podobnie jak w destruktorze) i każdy dodajesz do listy przy pomocy metody "Dodaj".

Zależy co dokładnie chcesz zrealizować poprzez połączenie dwóch list.
1) Jeżeli chcesz mieć w wyniku nową listę, która zawiera elementy o takich samych wartościach jak 2 poprzednie, bez modyfikacji tamtych (wersja Kozacka), to możesz robić jak on napisał. Ja bym jednak wziął jako argument tej funkcji "const Lista&", a nie "wezel_t*". Moim zdaniem połączenie list sugeruje, że bierzemy całe listy. Jeśli chcemy brać od środka, to można inną funkcję do tego zrobić.
2) Jeśli interesuje Cię tylko wynikowa lista, a 2 poprzednie już nie są potrzebne (wersja Lupinka) to wystarczy podłączyć koniec pierwszej listy do początku drugiej. Niczego nowego nie trzeba tworzyć, niczego nie trzeba również usuwać.
void Lista::append (const Lista& list) { wezel_t *tmp = pierwszy; wezel_t *next = tmp->nastepny; while (next != NULL) { tmp = next; next = tmp->nastepny; } tmp->nastepny = list.pierwszy; }Łatwo zauważyć, że gdybyś trzymał również ogon listy, to cała iteracja jest niepotrzebna i operację można zrobić w czasie stałym.


jednak nie wiem w jaki sposób odwołać się do początków obu list tak aby móc na nich operować wewnątrz metody.
Przecież początek listy się nazywa "pierwszy".



Właśnie miałem 2 takie koncepcje, jednak problemem było: const Lista& list - nie wiedziałem jak przesłać do metody obiekt( teraz będę wiedział jak wykonać kolejne zadanie - operacje na zbiorach).
Dziękuję panowie za tak szybkie odpowiedzi, pozdrawiam :)
Zgodnie z sugestią twono, problem rozwiązałem za pomocą:
// l.Polacz(l2); l.sort_wstaw_ros(); l.Drukuj();
Użytkownik gorbix edytował ten post 30 maj 2009, 09:14
@twono

Po wykonaniu Twojej metody ("wystarczy podłączyć koniec pierwszej listy do początku drugiej") w drugiej liście znajdą się elementy pierwszej i drugiej, a pierwsza pozostanie bez zmian. Powinna być pusta. Dlaczego? Jeśli usuniesz pierwszą listę, to zostaną skasowane elementy znajdujące się zarówno w pierwszej jak i drugiej. Nawet jeśli wykona się to bez błędów, to takie działanie nie jest zbyt poprawne. Twoja metoda musi ustawić pierwszy element listy, która została do niej przekazana na zero.


Po wykonaniu Twojej metody ("wystarczy podłączyć koniec pierwszej listy do początku drugiej") w drugiej liście znajdą się elementy pierwszej i drugiej, a pierwsza pozostanie bez zmian. Powinna być pusta. Dlaczego? Jeśli usuniesz pierwszą listę, to zostaną skasowane elementy znajdujące się zarówno w pierwszej jak i drugiej. Nawet jeśli wykona się to bez błędów, to takie działanie nie jest zbyt poprawne. Twoja metoda musi ustawić pierwszy element listy, która została do niej przekazana na zero.
Prawdą jest, że ta metoda nie jest zbyt bezpieczna w użyciu, bo zakłada, że po wywołaniu nie będziemy używać (ani usuwać poprzez wywołanie destruktora) tej drugiej listy (tej, która została przekazana jako argument). Ale w sumie Twoja modyfikacja zapewni bezpieczeństwo na wypadek usuwania (ale nadal nie możemy jej używać, bo jej już nie ma). Trzeba tylko usunąć "const".
void Lista::append (Lista& list) { ... tmp->nastepny = list.pierwszy; list.pierwszy = NULL; }

Jak chcesz zrealizować założenie o nie usuwaniu listy? Destruktor kasuje elementy listy. Musiałbyś przenieść jego kod do metody i wywoływać ją ręcznie. Tylko czy to ma sens? Programista ma pamiętać, które listy zostały dołączone, a które nie, aby poprawnie zwolnić pamięć?

"ale nadal nie możemy jej używać, bo jej już nie ma" - mam rozumieć, że nie możemy używać drugiej listy (przekazanej jako argument), ponieważ jej nie ma? Przecież lista nadal istnieje. Nie ma w niej elementów (może o to Ci chodziło), ale to nie przeszkadza w dodawaniu do niej nowych wartości, a nawet łączenia z innymi listami ;)


Jak chcesz zrealizować założenie o nie usuwaniu listy? Destruktor kasuje elementy listy. Musiałbyś przenieść jego kod do metody i wywoływać ją ręcznie. Tylko czy to ma sens? Programista ma pamiętać, które listy zostały dołączone, a które nie, aby poprawnie zwolnić pamięć?
Wyszedłem z założenia, że program jest ćwiczeniem na implementację listy, więc nie musi spełniać pewnych wymogów bezpieczeństwa kodu. A założenie o nieusuwaniu listy wyobrażałem sobie tak: w mainie ktoś tworzy sobie listę statycznie, coś tam z nią robi, potem dołączy do innej, i po wyjściu z maina wszystko jest ładnie usuwane :P


"ale nadal nie możemy jej używać, bo jej już nie ma" - mam rozumieć, że nie możemy używać drugiej listy (przekazanej jako argument), ponieważ jej nie ma? Przecież lista nadal istnieje. Nie ma w niej elementów (może o to Ci chodziło), ale to nie przeszkadza w dodawaniu do niej nowych wartości, a nawet łączenia z innymi listami ;)
No tu jest niejednoznaczność słowa "lista". W tym konkretnym przypadku rozumiałem listę jako jej elementy, aczkolwiek 2 posty wyżej chyba używałem tego słowa jako obiektu klasy Lista :D

  • zanotowane.pl
  • doc.pisz.pl
  • pdf.pisz.pl
  • zsf.htw.pl
  •