Jak wypisać listę jednokierunkową od końca w sposób iteracyjny?

Odpowiedz Nowy wątek
2018-12-25 13:56
0

Hej,
być może to banalne pytanie ale siedzę jakiś czas na kodem i nie mogę dojść do tego jak wypisać listę jednokierunkową od końca ale w sposób iteracyjny; rekurencyjnie jest to dużo łatwiejsze :

void wypiszOdKoncaRekurencyjnie(element * pHead)
{
    if (pHead)
    {
        wypiszOdKoncaRekurencyjnie(pHead->pNext);
        std::cout << pHead->wartosc << " ";  
    }
}

Byłabym bardzo wdzięczna za jakieś sugestie jak znaleźć poprzednika w liście jednokierunkowej doszłam do:

void wypiszOdKoncaIteracyjnie(element*&pHead)
{
    if (pHead)
    {
        element *p = pHead;

        while (p->pNext )
        {
            p = p->pNext;
        }
        //jestesmy na samym koncu listy i teraz chcemy zaczac wypisywac cofajac sie do poczatku
        std::cout << p>wartosc;

    }
}

Pozdrawiam i życzę Wesołych Świąt!

edytowany 3x, ostatnio: furious programming, 2018-12-25 15:12

Pozostało 580 znaków

2018-12-25 14:05
kq
3

Masz problem, bo lista jednokierunkowa - jak nazwa wskazuje - zezwala na iterację w jednym kierunku.

W tym miejscu standardowa regułka o tym, że lista to zły domyślny kontener (std::vector), ale jak już musisz jej użyć, to przynajmniej nie wymyślaj koła na nowo i użyj standardowych implementacji.


Pozostało 580 znaków

2018-12-25 14:11
0

To nie moje wymyślanie ale mojego prowadzącego zajęcia, każde operacje na liście jednokierunkowej robiliśmy w sposób iteracyjny jak i rekurencyjny ale, ponieważ nie udało się ich zrobić wszystkich na zajęciach to wypisywanie musieliśmy zrobić sami. Zastanawia mnie czy wypisywanie takiej listy od końca możemy zrobić tylko w sposób rekurencyjny aby było to przejrzyście i prosto czy może jednak da się w sposób iteracyjny ale ja nie jestem w stanie zauważyć w jaki sposób.

edytowany 1x, ostatnio: furious programming, 2018-12-25 15:12

Pozostało 580 znaków

2018-12-25 14:12
kq
1

Możesz zapisać sobie wskaźniki do elementów do osobnej tablicy i potem ją przeiterować od tyłu. Nie ma to sensu, ale działa ;​)


Pozostało 580 znaków

2018-12-25 14:17
0

Kurcze nie wpadłam na to , rzeczywiście! Oczywiście wolałabym nie deklarować kolejnej struktury danych ale skoro tak będzie najprościej i będzie działać to nie mam zamiaru wybrzydzać. Dzięki wielkie ;)

edytowany 1x, ostatnio: furious programming, 2018-12-25 15:12

Pozostało 580 znaków

2018-12-25 15:38
2

Możesz też w pierwszym przebiegu zmienić kierunek listy. I potem ją wypisać w normalny sposób ;)

HEAD -> HEAD.NEXT -> HEAD.NEXT.NEXT -> HEAD.NEXT.NEXT.NEXT -> NULL

Więc, żeby odwrócić listę robisz tak, że
1) HEAD.NEXT = NULL (pierwszy element jest ostatnim elementem, nie ma następnego)
2) W pętli, wskaźniki każdej pary zamieniasz miejscami, żeby następny element wskazywał na poprzedni.

PREV_PTR = NULL // pierwszy obrót pętli spełni założenia punktu 1)

WHILE_START
NEXT = CURRENT.NEXT // next będzie nadpisywany, więc musimy go sobie zapamiętać, żeby mieć odpowiedni CURRENT w następnym obrocie pętli

CURRENT.NEXT = PREV_PTR
PREV_PTR = CURRENT_PTR

CURRENT = NEXT
WHILE_END

3) Jeśli NEXT == NULL, to HEAD = CURRENT (jeśli dotarliśmy do ostatniego elementu - bo tylko jego NEXT jest równy NULL - to ten element staje się pierwszym - HEAD).

Pewnie trochę porąbałem z oznaczeniami wskaźników, ale logicznie raczej wszystko działa ;)

edytowany 3x, ostatnio: Spine, 2018-12-25 15:42

Pozostało 580 znaków

2018-12-25 16:13
1

Jeśli nie można używać innych struktur danych, to Przeiteruj po odwrotnej liście, do tego trzeba parę nowych (banalnych) funkcji:

size_t len(node * head) {
    node * tmp = head;
    size_t n{0};
    while (tmp) {
        n++;
        tmp = tmp->nextptr;
    }
    return n;
}

node * cons(int elem, node * head) { // zwraca listę z dołączonym na poczatku elem
    if (head) {
        node * temp = new node();
        temp->data = elem;
        temp->nextptr = head;
        return temp;
        }

    else {
    node * tmp = new node();
    tmp->data = elem;
    return tmp; 
    }
}

node * rest(node * head) {
    return head->nextptr;
}

int first(node * head) {
    return head->data;
}
node * reverse(node * head) {
    node * empty;
    return _reverse(head, empty);
}

node * _reverse(node * lst1, node  * lst2) { // helper iteracyjny
    node * tmp = lst1;
    size_t n = len(lst1);
    while (n > 0) {
        lst2 = cons( first(tmp), lst2);
        tmp = rest(tmp);
        n--;
    }
    return lst2;
}

I, finalnie, mamy wypisanie od ostatniego:

void reverse_print(node * head) {
    node * tmp = reverse(head);
    while (tmp) {
        std::cout << tmp->data << " ";
        tmp = tmp->nextptr;
    }
    std::cout << "\n";
}

Pozostało 580 znaków

2018-12-25 16:55
0

Bardzo Wam dziękuję za wskazówki, z dodatkową tablicą wskaźników działa ale to kolejna struktura więc pomysł z zamianą kierunku samej listy super!

edytowany 2x, ostatnio: hauleth, 2018-12-25 16:58
Nie cytuj całego posta, to strasznie zaciemnia treść. - hauleth 2018-12-25 16:58

Pozostało 580 znaków

2018-12-25 23:30
cs
2

Z doświadczenia wiem, że "prowadzący", choć mając dziwne pomysły, to oczekują rozwiązań zazwyczaj prostych. Początkowo pomyślałem o stosie, ale to wymagałoby nowej struktury, więc można zrobić stos na "piechotę". Możesz iterując po liście w jedynie słusznym kierunku, robić listę odwrotną, umieszczając kolejne elementy "starej' listy zawsze na początku nowej, dokładnie tak jak na stosie. Nie musisz elementów kopiować, po prostu zmienisz porządek listy:

void wypiszOdKoncaIteracyjnie(element*&pHead)
{
    if (pHead) {
        element *p = pHead;
        element *list = NULL;   // wskaźnik do "starej" listy
        element *stack = NULL;  // wskaźnik do stosu - "nowej" listy, która ma odwrócony porządek

        while (p->pNext){
            list = p->next;     //zapamiętujemy pozostałą część "starej" listy
            p->next = stack;    //do bieżącego węzła doczepiamy resztę stosu
            stack = p;          //bieżący element jest pierwszy na stosie i jest jednocześnie pierwszy na "nowej" liście
            p = list;           //bieżący element to teraz pierwszy element "starej" listy
        }

        p = stack;
        //wyświetlenie listy w odwróconym porządku
        while(p->pNext){
            std::cout << p->wartosc;
            p = p->pNext;
        }
    }
}

W drugiej pętli, która wyświetla odwróconą listę, możesz znowu odwrócić porządek i dostaniesz listę w nienaruszonym stanie.
PS.
Jest to chyba rozwiązanie podobne do @Spine, ale to zauważyłem dopiero po napisaniu posta.

edytowany 1x, ostatnio: cs, 2018-12-25 23:37

Pozostało 580 znaków

2018-12-29 13:17
0

Bardzo dziękuję @cs ! Dobrych rozwiązań nigdy za wiele ;)

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0