Zamiana węzłów na jednej, połączonej liście

Question

Próbuję utworzyć funkcję swapNode, która może zająć dowolne dwa węzły i zamienić je. Zrobiłem algorytm, który działa, jeśli są oddalone o co najmniej 2 węzły, ale nie mogę wymyślić algorytmu, który zadziała, jeśli będą bliżej siebie.

Oto co napisałem do tej pory:

void swapNode(call * &head, call * &first, call * &second){ 
    call * firstPrev = NULL; 
    call * secPrev = NULL; 
    call * current = head; 

    //set previous for first 
    while((current->next != first)){ 
     current = current->next; 
    } 

    firstPrev = current; 
    current = head; 

    //set previous for second 
    while((current->next != second)){ 
     current = current->next; 
    } 

    secPrev = current; 
    current = second->next; 

    //set firstPrev-> next to second 
    firstPrev->next = second; 
    //set secPrev->next to first 
    secPrev->next = first; 
    //set second->next = first->next 
    second->next = first->next; 
    //set first->next to current 
    first->next = current; 

    current = head; 
    while(current->next != NULL){ 
     cout << current->number << endl; 
     current = current->next; 
    } 

    cout << current->number << endl; 
} 

EDIT: teraz mam to jako moją część wymiany, ale to wciąż nie wydają się działać poprawnie

//swap firstPrev-> next with second->next 
tmp = firstPrev->next; 
second->next = firstPrev->next; 
second->next = tmp; 
//swap swap first->next with second->next 
tmp = first->next; 
second->next = first->next; 
second->next = tmp; 

EDIT2: Ten też nie działa, dostaję błąd w seg.

//swap previous's->next 
    tmp =firstPrev->next; 
    secPrev->next = firstPrev->next; 
    secPrev->next = tmp; 
    //swap swap first->next with second->next 
    tmp = first->next; 
    second->next = first->next; 
second->next = tmp; 

Answer 1

Say mamy:

Node1 -> Node2 -> Node3 -> Node4 -> Node5 

Aby zamienić dwa węzły, należy zamienić wartości next z tych, przed każdym z nich, a także wartości next węzłów chcesz zamienić .

więc zamienić, powiedzmy, Node2 i Node3, skutecznie trzeba zamienić Node1->next z Node2->next i Node2->next z Node3->next. To zadziała, nawet jeśli są tuż obok siebie (lub nawet jeśli to ten sam węzeł). Na przykład:

Zmiennych Node1->next i Node2->next

Node1->next = Node3 
Node2->next = Node2 

Zmienne Node2->next z Node3->next

Node2->next = Node4 
Node3->next = Node2 

przychodzi to jako:

Node1 -> Node3 -> Node2 -> Node4 -> Node5 

Swapped!

Jak można zauważyć w sekcji komentarzy po odreagowaniu, jeśli zamienisz Węzeł 1 na cokolwiek, musisz ustawić nową głowę dla połączonej listy.

---

W odpowiedzi na pytania edit:

Twój kod do ciężkich prawie prawo. Musisz jednak zamienić pierwszyPrev na secPrev. Tak właśnie stało się w moim przykładzie, że dwukrotnie wymienialiśmy wartości jednego węzła: , ponieważ były one obok siebie. Logicznie rzecz biorąc, chcemy zamienić next z dwóch poprzednich, a następnie zamienić rzeczywiste węzły na next. Spróbuj tego:

//swap firstPrev-> next with secPrev->next 
tmp = firstPrev->next; 
secPrev->next = firstPrev->next; 
secPrev->next = tmp; 
//swap swap first->next with second->next 
tmp = first->next; 
second->next = first->next; 
second->next = tmp; 

Jeśli dostajesz segfault sprawdzić zmiennej TMP - może to być błąd alokacji lub usunięcia gdzieś. Gdzie dostaniesz segfault?

Answer 2

W większości rzeczywistych sytuacjach życiowych, zamiana wartości będzie najlepszym rozwiązaniem:

void swapNode(call * &head, call * &first, call * &second) { 
    // swap values, assuming the payload is an int: 
    int tempValue = first->value; 
    first->value = second->value; 
    second->value = tempValue; 
} 

jeśli nie jest to dozwolone, to chcesz zrobić swap podobnym stylu na -> obok zamiast -> składnik wartości. A następnie wykonaj kolejną zamianę na pierwszy komponent Prev-> next i secondPrev-> next. Uważaj na specjalny przypadek, w którym pierwsza lub druga głowa ==.

Answer 3

Chociaż nie jestem w 100% pewny, że odpowiedź powinna dotyczyć odniesień do wskaźnika węzła (lub wskaźników do wskaźników), a to powinno obsługiwać przypadek, gdy jeden z węzłów jest również nagłówkiem listy.

void swapNodes(node *&first, node *&second) 
{ 
    node *t = second->next; 
    second->next = first->next; 
    first->next = t; 
    t = second; 
    second = first; 
    first = t; 
} 

Następnie można nazwać na przykład:

swapNodes(head, secPrev->next); 

lub

swapNodes(firstPrev->next, head); 

lub

swapNodes(firstPrev->next, secPrev->next) 

i powinno działać automagicznie.

EDIT:

swapNodes może być jeszcze bardziej czytelny:

void swapNodes(node *&first, node *&second) 
{ 
    std::swap(first->next, second->next); 
    std::swap(first, second); 
} 

Answer 4

Zasada: "Zawsze oddzielne dane ze wskaźnikami i nigdy zamienić wskazówek, tylko dane". Dokonaj swap explicite bez użycia memcpy(), dzięki czemu unikniesz problemów z wyrównaniem. Nie powoduje to obniżenia wydajności pod względem algorytmicznej złożoności, ale czyni twój kod bardziej czytelnym i bezpiecznym.

Answer 5

Jeśli chcesz poznać wszystkie metody swapping dwa węzły w powiązanych wykazów w prosty C tylko wtedy odwiedzić ten link:

http://sahilalipuria.wordpress.com/2013/01/21/swapping-two-nodes-of-a-singly-linked-lists-set-2/

Answer 6

void swap() 
{ 
struct node *temp=0,*nxt,*ptr; 
ptr=head; 
int count=0; 
while(ptr) 
{ 
    nxt=ptr->link; 
    if(nxt) 
{ 
    if(count==0) 
    head=nxt; 
    count++; 
    ptr->link=nxt->link; 
    nxt->link=ptr; 
    if(temp!=NULL) 
    temp->link=nxt; 
    temp=ptr; 
    if(ptr->link==NULL) 
    break; 
    ptr=nxt->link->link; 
} 

} }

Answer 7

Tu P1 pierwszy węzeł do zamiany, p2 to drugi węzeł do zamiany. I prevnode jest węzeł, który jest poprzedni P2

 temp=head; 
     while(temp!=NULL){ 
     if(temp->link==p1){ 
      temp->link=p2; 

      prevnode->link=p2->link; 
      p2->link=p1->link; 
      t=p1->link; 
      while(t!=prevnode) 
       t=t->link; 
       cout<<" YES"; 
      cout<<"["<<t->num<<"] "; 
      p1->link=prevnode->link; 
      prevnode->link=p1; 

      temp=p1; 
     }//if_ 

     cout<<" "<<temp->num;    
     temp=temp->link; 
    } 

Answer 8

Trzeba będzie również zamienić element poprzedniego węzła next, inaczej powiązana lista nie pozostaną połączone. Zauważ, że moja struktura nazywa się node.

int swapNode(node *&head * &first, node * &second) 
{ 
    //first we will declare the 
    //previous of the swapping nodes 
    node *firstprev=NULL; 
    node*secprev=NULL; 
    node*current=head; 
    //set previous first 
    while(current->next!=first) 
    { 
     current=current->next; 
    } 
    firstprev=current; 
    //seting 2nd previous 
    while(current->next!=second) 
    { 
     current=current->next; 
    } 

    // swap values, assuming the payload is an int: 
    int tempValue = first->value; 
    first->value = second->value; 
    second->value = tempValue; 
    //swaping next of the nodes 
    firstprev->next=second; 
    secprev->next=first; 
    return; 
} 

Answer 9

Dziękuję wszystkim za odpowiedzi! Zdaję sobie sprawę, że to pytanie zostało zadane prawie dwa lata temu i odpowiedź od dawna została przyjęta, ale jestem nieco zdezorientowany przez odpowiedzi. Tak więc, mimo że pytający prawdopodobnie nie dba o nowe odpowiedzi, chciałbym dodać moją wersję, na wypadek, gdyby inni czytelnicy również byli zdezorientowani i udokumentowali moje własne podejście. Niektóre z nich mogły być bardziej odpowiednie jako komentarze, ale nie mam jeszcze reputacji do komentowania.

Po pierwsze, bez względu na to, jak często na nią patrzę - na tablicy lub w debugerze - nie mogę sobie pozwolić na rezygnację z pętli w pierwszym węźle, tj.wskazując na siebie, jeśli nie używam warunkowego rozróżnienia między przypadkami sąsiednich węzłów a nie, nawet z abstrakcyjnymi krokami lub konkretnym kodem z obecnie akceptowanej odpowiedzi Smashery'ego. Rozglądałem się trochę po Internecie, aby znaleźć kod w stylu aktualnie akceptowanej odpowiedzi, aby uniknąć takiego warunku, ale dla mnie jest to zaskakująco trudne, a moje wyszukiwania nie znalazły takiego rozwiązania (chyba, że ​​się mylę o proponowanym, który prawdopodobnie jest nieprawidłowy). Jeśli istniało jakieś sprytne wyrażenie, które dawałoby adres pierwszego węzła, gdy sąsiadują z nim, oraz adres następcy pierwszego węzła, gdy nie są, to warunkowe nie byłoby potrzebne, ponieważ znalezienie nowego następcy węzła to, co (widocznie) wymusza to warunkowe.

Po drugie, mam to samo pytanie o kolejne przypisania do tych samych zmiennych w zaakceptowanej odpowiedzi, co inni komentatorzy. Mam nadzieję, że nie jestem tutaj wyjątkowo gęsty, ale przypisuję różne wartości tej samej zmiennej w sekwencji, chyba że w przypadku efektów ubocznych, dla mnie nigdy nie wydaje się, że zostawiam zmienną o innej wartości niż ostatnie zadanie, bez znaczenia jaka konfiguracja węzłów biorę pod uwagę, a tym samym sprawia, że ​​poprzednie zadania wydają się nadmiarowe. Jeśli się mylę i to podejście faktycznie rozwiązałoby ten problem, to byłbym w stanie wyeliminować ostatnie warunkowe w kodzie poniżej, który starałem się pozbyć, gdy po raz pierwszy spojrzałam w Internecie na rozwiązanie problemu. przełączanie węzłów bez specjalnych obudów sąsiednich węzłów. Nie jestem do końca pewny, ale brzmiało to tak, jak Smashery celowo zostawił te powtarzające się zadania z logicznego rygoru i lepiej zilustrował procedurę - być może mnie jednak źle zrozumiałem.

Po trzecie, na tej i innych stronach często widziałem, że stwierdzenie z innych odpowiedzi powtarzało, że lepiej jest zamienić zawartość węzłów, niż wskaźniki. Oczywiście w przypadku zwykłych liczb całkowitych, jak w przykładach do tej pory, to oczywiście daje krótszy, prostszy kod. Jednakże, gdy omawiamy połączone listy z węzłami zawierającymi liczby całkowite, zwykle jest to stand-in dla struktury danych zabezpieczających bardziej złożonego i generycznego kontenera. W związku z tym nie sądzę, że zamiana zawartości węzłów jest naprawdę łatwa, przynajmniej jeśli implementacja struktury danych nie może przyjąć założeń dotyczących semantyki kopiowania elementów kontenera. Ponadto możliwość zamiany zawartości takich węzłów oznacza dla mnie, że połączona lista ma własność zawartości tych węzłów, ponieważ w przeciwnym razie kod spoza metody listy połączonej może zawierać odniesienia do obiektów w tych węzłach, których wartości nagle zmieniają się pod nimi.

Przyznam jednak, że może to zależeć od semantyki kontenera. W przypadku tablicy można oczekiwać, że metoda wymiany zmieni wartość pod odnośnikami do określonego indeksu tej tablicy. Oznaczałoby to, że odniesienia nie mają odnosić się do konkretnego obiektu, ale do pozycji w pojemniku, który można indeksować. Jeśli uznamy listę połączoną za środek do zamawiania tylko zestawu obiektów, które mają swoje zastosowanie poza połączoną listą, użytkownik prawdopodobnie oczekiwałby, że operacja wymiany będzie tylko wymieniać pozycję, a nie zawartość.

Wyobraź sobie na przykład, że połączona lista reprezentuje obiekty typu "samochód". Każdy samochód ma właściciela i ten właściciel odwołuje się do samochodu za pomocą wskaźnika do niego. Przypuśćmy teraz, że połączona lista reprezentuje porządek, w którym zestaw samochodów ma być obsługiwany do wglądu u dealera samochodowego. Gdybyśmy wymienili zawartość dwóch węzłów, w celu wymiany miejsc na dwa samochody i dokonali tego poprzez wymianę ich zawartości, to obsługa w rzeczywistości odbyłaby się w nowej, właściwej kolejności - ale ludzie również nagle otrzymaliby różne samochody! (Nie miałbym nic przeciwko zamianie Tesli, ponieważ jeżdżę tylko Corollą.)

Jeśli połączona lista była, jak w przykładzie tablicy, na podstawie semantyki indeksowania, to pozycja w węźle może po prostu reprezentować kolejność, w jakiej samochody są ładowane na statek do transportu. W tym momencie samochody nie mają żadnych właścicieli, a my naprawdę tylko dbają o to, w jakim są gnieździe. Wtedy, przypuszczam, że naprawdę nie zaszkodzi wymieniać samochody, tj. Zawartość obiektów przywoływanych przez węzły.

Wreszcie do kodu. Jak już wspomniałem powyżej, nie udało mi się uniknąć specjalnej obudowy dla sąsiednich węzłów.

pierwsze, określenie metody pomocnicze:

int find_node(int v, node* root, node** n, node** pn) { 
    int i = 0; 
    for (*n = root; *n != NULL && (*n)->v != v; ++i) { 
     *pn = *n; 
     *n = (*n)->next; 
    } 
    return i; 
} 

ten sposób znajduje się węzeł, od jego wartości. Zwrócona liczba całkowita jest pozycją zerową (nazwij ją indeksem, jeśli chcesz) węzła na liście połączonej. Zauważyłem, że wykrywanie sąsiedztwa za pomocą pozycji, a nie porównania wskaźnika, jest bardziej czytelne. Początkiem listy jest root. Metoda ustawia n, aby wskazywało węzeł zawierający przekazaną wartość. W pn, metoda przechowuje poprzednika n.

co następuje faktyczna zamiana:

void swap_nodes(node **root, int v1, int v2) { 
    if (v1 == v2) return; 

    node *n1, *n2, *pn1, *pn2; 

    int p1 = find_node(v1, *root, &n1, &pn1); 
    int p2 = find_node(v2, *root, &n2, &pn2); 

    if (p1 > p2) { 
     std::swap(n1, n2); 
     std::swap(pn1, pn2); 
     std::swap(p1, p2); 
    } 

    if (p1 == 0) *root = n2; 
    else pn1->next = n2; 

    node* nn1 = n1->next; 
    n1->next = n2->next; 

    if (p2 - p1 > 1) { 
     n2->next = nn1; 
     pn2->next = n1; 
    } else { 
     n2->next = n1; 
    } 
} 

przykro mi, że zmieniłem podpis metody PO trochę. Zauważyłem, że wygodniej jest przekazywać wartości węzłów do zamiany, w przeciwieństwie do wskaźników węzłów. Jeśli przekażesz wskaźniki węzłów tylko do odpowiednich węzłów, będziesz musiał wykonać kolejne przejście, aby znaleźć poprzedników za pomocą tego rozwiązania, co było dla mnie nieco kłopotliwe. Jeśli nie możemy rozróżnić węzłów według tych wartości, np. wartości nie są unikalne, ale potrzebujemy wskaźników do węzłów.

Podobnie jak w przypadku wyjaśnienia dla powyższego find_node, najpierw znajdujemy pozycje, węzły i poprzedniki dla wartości węzłów przekazanych do swap_nodes poprzez v1 i v2. Wartości dla pierwszego i drugiego węzła są zamieniane, gdy drugi węzeł do zamiany pojawia się przed pierwszym. Nie ma w tym wiele kodu, redukuje się specjalne obudowy i sprawia, że ​​wizualizacja jest nieco łatwiejsza.

Teraz pozostało nam jeszcze tylko dwa warianty, z których żaden nie wydawał się banalny. Jeśli pierwszy węzeł znajduje się na czele listy połączonej, tj. W pozycji zero, to root musi wskazywać na drugi węzeł. W przeciwnym razie poprzednik pierwszego węzła wskaże drugi węzeł.

Poprzednia wartość pierwszego następcy węzła musi zostać zapamiętana, na wypadek, gdyby węzły nie byłysiadowały ze sobą. Następnie następca pierwszego węzła jest ustawiony na bieżącego następcę drugiego węzła. Jest to jedyna zmiana, która ma zastosowanie do wszystkich przypadków: nowy następca pierwszego węzła będącego starym następcą drugiego węzła jest jedyną pewną i pomocną w rozpoczęciu w celu zapamiętania operacji wskaźnika i ich sekwencji podczas wdrażania tego zamiany .

Wreszcie, jeśli pozycje węzłów różnią się o więcej niż jeden, nie sąsiadują ze sobą. Następnie nowy następca drugiego węzła staje się starym następcą pierwszego węzła - zapisanym powyżej - a poprzednik drugiego węzła wskazuje teraz na pierwszy węzeł. Jeśli sąsiadują ze sobą, nie ma węzłów między węzłami do zamiany, które wymagają aktualizacji, więc wystarczy połączyć drugi węzeł z pierwszym, aby to zrobić.