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

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!

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.

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.

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 ;​)

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 ;)

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
  1. 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 ;)

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";
}
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!

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.

0

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

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