sprawdź, czy w połączonej liście znajduje się pętla. Czy masz inne sposoby zamiast szybkiego wskaźnika i wolnego wskaźnika?
Odpowiedzi:
4 dla odpowiedzi № 1W zależności od sytuacji możesz to zrobić na wiele sposobów.
Po dotarciu do każdego węzła dodaj go do pewnego rodzaju zestawu. Przejdź przez listę, aż dojdziesz do końca lub znajdź węzeł już w Zestawie.
Jeśli masz wolne miejsce w węzłach, możesz oznaczyć każdy węzeł jako „odwiedzony” lub nie i przejść listę, aż znajdziesz taki, który już oznaczyłeś.
Wszystko to oczywiście ma wady (np. Użycie dużej ilości pamięci) lub sytuacje, w których nie są one użyteczne, podczas gdy metoda dwupunktowa nie wykorzystuje dodatkowej pamięci i jest stosowana praktycznie wszędzie.
1 dla odpowiedzi nr 2
Będziesz musiał oznaczyć każdy węzeł jako odwiedzony iwykrył już odwiedzony węzeł, który ma twój znak. Problem polega na tym, co należy zaznaczyć, więc nie musisz uruchamiać listy, aby zresetować wszystko przed lub po.
1 dla odpowiedzi nr 3
Jak mówią poprzednie rozwiązania, musisz zaznaczyćwęzeł odwiedzony w jakiś sposób. Właściwie w każdym węźle z listą pojedynczo połączonych masz co najmniej 3 bity dodatkowej przestrzeni (w „następnym” wskaźniku), ponieważ wszystkie adresy pamięci są wielokrotnością 8. Więc możesz zrobić trochę hacku i ustawić na przykład ostatni bit „następnego” wskaźnika na 1. Zauważ, że gdy przesuwasz się na połączonej liście, musisz zamaskować ostatni bit „następnego” wskaźnika, aby mieć prawidłowy adres pamięci.