• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

question-closed Problem ze zrozumieniem zadania - mile widziane wskazówki.

VPS Starter Arubacloud
0 głosów
273 wizyt
pytanie zadane 25 kwietnia 2018 w C i C++ przez Piotr_Minda Początkujący (380 p.)
zamknięte 29 kwietnia 2018 przez Piotr_Minda

Witam,  Mam problem ze zrozumieniem treści zadania, o co chodzi autorowi.

O to treść:

Zwróć uwagę, że dodajKoniec() używa funkcji ostatni(), a więc dodanie 1001. liczby wymaga przejścia przez 1000 węzłów tylko po to, by znaleźć koniec listy. Znajdź sposób na to, by dodawanie elementów na oba końce listy nie wymagało odwiedzania wszystkich węzłów.
Podpowiedź: Możesz potrzebować drugiego struct.

O to kod źródlowy programu który należy zmodyfikować/przeanalizować: 

#include <iostream>


struct Lista
{
    Lista * ogon;
    int liczba;
};

// Wypisz wszystkie elementy listy
void wypisz( Lista * lista )
{
    // Przechodzenie po liście *rekurencyjnie*
    if( lista )
    {
        std::cout << lista->liczba << ", ";
        wypisz( lista->ogon );
    }
}


// Zwróć: wskaźnik na ostatni element listy
Lista * ostatni( Lista * lista )
{
    // Przechodzenie po liście *iteracyjnie*
    if( lista )
    while( lista->ogon )
         lista = lista->ogon;
    
    return lista;
}


// Dodaj element na koniec listy
void dodajKoniec( Lista *& lista, int liczba )
{
    // Tworzymy nowy element listy
    Lista * nowy = new Lista;
    nowy->liczba = liczba;
    nowy->ogon = nullptr;
    
    // Dopisujemy na koniec
    if( lista )
         ostatni( lista )->ogon = nowy;
    else
         lista = nowy;
    
}


// Usuwa listę
void zniszcz( Lista *& lista )
{
    while( lista )
    {
        Lista * tmp = lista;
        lista = lista->ogon;
        delete tmp;
    }
    
    lista = nullptr;
}


int main()
{
    int liczba;
    Lista * lista = nullptr;
    std::cout << "Podaj liczby, 0 lub blad konczy:\n";
    
    while( std::cin >> liczba && liczba )
         dodajKoniec( lista, liczba );
    
    std::cout << "Koniec, oto liczby:\n";
    wypisz( lista );
    zniszcz( lista );
}

Czy Autorowi chodzi o listy dwu kierunkowe, czy o coś innego? Mile widziane wskazówki, serdecznie dziękuję za pomoc w rozwiązaniu zadania!

Btw zadanie pochodzi z serwisu CPP0x(tam bym zapytał, lecz nie chcę tworzyć setki nie potrzebnie kont)

 

komentarz zamknięcia: Otrzymałem wystarczająco dużo informacji na temat rozwiązania tego problemu, temat może byc też pomocny dla potomnych.

2 odpowiedzi

0 głosów
odpowiedź 25 kwietnia 2018 przez RafalS VIP (122,820 p.)
edycja 29 kwietnia 2018 przez RafalS

Zwróć uwagę że wskaźnik lista z maina, który jest przekazywany do wszystkich funkcji to tak na prawdę początek listy. Wystarczy dodać wskaźnik który będzie trzymał koniec listy. Z kolejna struktura chyba chodzi im o stworzenie struktury, ktora będzie miec dwa wskazniki do listy - poczatek i koniec listy. Ją bedziesz wysylal do funkcji i funkcja dodaj koniec skoezysta ze wskaznika do konca listy a funkcja wypisz tak jak jest - z wsk do początku listy.

EDIT:
Najprostsze rozwiązanie problemu przechodzenia przez wszystkie węzły, żeby dodać element na koniec to pamiętanie wskaźnika na koniec listy. Oto najprostsza implementacja:
 

#include <iostream>
struct Lista
{
	Lista * ogon;
	int liczba;
};

// Wypisz wszystkie elementy listy
void wypisz(Lista * lista)
{
	// Przechodzenie po liście *rekurencyjnie*
	if (lista)
	{
		std::cout << lista->liczba << ", ";
		wypisz(lista->ogon);
	}
}

// Dodaj element na koniec listy
void dodajKoniec(Lista *& lista, Lista *& koniec, int liczba)
{
	// Tworzymy nowy element listy
	Lista * nowy = new Lista;
	nowy->liczba = liczba;
	nowy->ogon = nullptr;

	// Dopisujemy na koniec
	if (lista) 
		koniec->ogon = nowy;
	else
		lista = nowy;

	koniec = nowy;
	//trzeba uaktualnic wskaznik koniec, dodalismy na koniec
	//wiec jes to banalne :P
}


// Usuwa listę
void zniszcz(Lista *& lista)
{
	while (lista)
	{
		Lista * tmp = lista;
		lista = lista->ogon;
		delete tmp;
	}

	lista = nullptr;
}


int main()
{
	int liczba;
	Lista * lista = nullptr;
	//najprostsze rozwiazanie problemu przechodzenia po wszystkich wezlach
	//przy dodaniu na koniec to oczywiscie dodanie wskaznika na koniec
	Lista * koniec = nullptr;
	std::cout << "Podaj liczby, 0 lub blad konczy:\n";

	while (std::cin >> liczba && liczba)
		dodajKoniec(lista, koniec, liczba);

	std::cout << "Koniec, oto liczby:\n";
	wypisz(lista);
	zniszcz(lista);
}

Wszystko działa, ale chcemy to napisać ładniej. Wskaznik lista i koniec nie są ze sobą w żaden sposób powiązane. Nie łączy ich nic, a powinno bo razem tworzą naszą listę. To jest brzydkie, bo gdybyśmy musieli korzystać z kilku list w mainie, to musielibyśmy łączyć te dwa wskaźniki przy pomocy nazewnictwa w stylu lista1, koniec1, lista2, koniec2 ... A to jest brzydkie, oczywiscie mozna by je do tablicy wrzucić, ale i tak musiałyby być dwie tablice. Dodajemy zatem strukture, która połączy te dwa wskaźniki.

#include <iostream>

//nie podoba mi sie ta nazwa, to sie powinno nazywac Lista,
//ale ze ktos nazwał w ten sposób strukture, ktora powinna nazywac sie
//wierzcholek albo wezel wiec nic nie poradze
struct WspolrzedneListy
{
	Lista* poczatek;
	Lista* koniec;
};

struct Lista
{
	Lista * ogon;
	int liczba;
};

// Wypisz wszystkie elementy listy
void wypisz(Lista * lista)
{
	// Przechodzenie po liście *rekurencyjnie*
	if (lista)
	{
		std::cout << lista->liczba << ", ";
		wypisz(lista->ogon);
	}
}

// Dodaj element na koniec listy
void dodajKoniec(Lista *& lista, Lista *& koniec, int liczba)
{
	// Tworzymy nowy element listy
	Lista * nowy = new Lista;
	nowy->liczba = liczba;
	nowy->ogon = nullptr;

	// Dopisujemy na koniec
	if (lista)
		koniec->ogon = nowy;
	else
		lista = nowy;

	koniec = nowy;
	//trzeba uaktualnic wskaznik koniec, dodalismy na koniec
	//wiec jes to banalne :P
}


// Usuwa listę
void zniszcz(Lista *& lista)
{
	while (lista)
	{
		Lista * tmp = lista;
		lista = lista->ogon;
		delete tmp;
	}

	lista = nullptr;
}


int main()
{
	int liczba;
	WspolrzedneListy lista = { nullptr, nullptr };
	std::cout << "Podaj liczby, 0 lub blad konczy:\n";

	while (std::cin >> liczba && liczba)
		dodajKoniec(lista.poczatek, lista.koniec, liczba);

	std::cout << "Koniec, oto liczby:\n";
	wypisz(lista.poczatek);
	zniszcz(lista.poczatek);
}

Oczywiście zamiast wysylać do funkcji wskaźniki do listy moglibyśmy przesłać referencje do tej nowej struktury i w funkcjach wyciagac sobie wskaźniki, które akurat są nam potrzebne (poczatek lub koniec). To kwestia wyboru. Ale to dalej jest brzydkie jak dla mnie. Jeśli już piszemy w języku obiektowym jakim jest C++ to możemy zastosować podejście obiektowe i połączyć zachowanie (funkcje) ze stanem (zmiennymi) w postaci metod, składowych oraz modyfikatorów dostępu. Można by też wrzucić strukture lista do środka klasy. Nie wiem czy przerabiałeś już takie rzeczy, więc sobie odpuszcze.

 

komentarz 25 kwietnia 2018 przez Piotr_Minda Początkujący (380 p.)
Bo jeszcze była pierwsza część zadania, która polegała na dopisaniu funkcji void dodaj początek. I z tym sobie poradziłem. Program zadziałał jak trzeba. Natomiast tutaj jest problem. Można prosić o przykładowy kod opisujący twoje przemyślenia. Bardzo by mi to ułatwiło dalsze borykanie się ze wskaźnikami oraz strukturą. Pozdrawiam serdecznie Piotr
komentarz 25 kwietnia 2018 przez RafalS VIP (122,820 p.)
Moge rozpisac, ale nie wiem kiedy bd przed lapkiem, dzis wieczorem albo jutro
komentarz 25 kwietnia 2018 przez Piotr_Minda Początkujący (380 p.)
edycja 26 kwietnia 2018 przez Piotr_Minda
Serdecznie dziękuję, jeśli mógł byś. To bardzo pomoże mi w rozwiązaniu tego zadania. Są jeszcze ludzie na tym świecie, Szacunek Dla takich jak ty!

Gdyby ktoś inny z userów miałby ochotę pomóc, pomóc, podpowiedzieć jak rozwiązać to zadanie, to bardzo pomogło by mi zrozumieć treść. Serdecznie dziękuję za wsparcie, i chęć!
0 głosów
odpowiedź 28 kwietnia 2018 przez Piotr_Minda Początkujący (380 p.)
Up.
komentarz 29 kwietnia 2018 przez RafalS VIP (122,820 p.)
rozpisałem
komentarz 29 kwietnia 2018 przez Piotr_Minda Początkujący (380 p.)
Dzięki serdeczne, za tak obszerne zilustrowanie tejże zagwostki. Męczę się z tym drugi dzień i nic, a tu prosze wszystko ładnie potrafiłeś mnie laikowi podpowiedzieć, jak to ugryźć pewnie bym sam doszedł do tego, ale wolałem zyskać na czasie i wspólną pomocą utrwalić sobie temat. Jeszcze raz serdecznie dziękuję!. To forum ma jednak to coś!

Podobne pytania

+2 głosów
2 odpowiedzi 481 wizyt
pytanie zadane 24 czerwca 2017 w C i C++ przez XYZ1234 Użytkownik (620 p.)
+2 głosów
5 odpowiedzi 412 wizyt
pytanie zadane 11 maja 2015 w Nasze projekty przez CzlowiekSkrypt Nałogowiec (26,340 p.)
0 głosów
1 odpowiedź 769 wizyt

92,455 zapytań

141,263 odpowiedzi

319,099 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...