Programowanie w Visual C++ 2010

Spis treści

Błędy w kodzie cz. 4 – dynamiczne struktury danych

Do tej pory posługiwaliśmy się głównie podstawowymi typami danych, jakimi są int, double czy char. Stosując ciągi danych określonego typu (tablice), musieliśmy z góry (czy to statycznie, czy też dynamicznie, tzn. przy tworzeniu tablicy) ustalić ich rozmiar. W rezultacie zdarzało się, że część zarezerwowanego miejsca mogła "leżeć odłogiem". W tym samouczku przyjrzymy się bliżej dynamicznym strukturom danych.

Dynamiczne struktury danych

Stosowanie dynamicznych typów danych umożliwia łatwe zwiększanie/zmniejszanie liczby przechowywanych elementów w czasie działania programu. Wyobraźmy sobie zestaw takich danych jako zbiór/ciąg bez ograniczenia rozmiaru, do którego możemy coś wkładać, coś z niego wyjmować, czy też zwyczajnie przeglądać (formalnie rzecz biorąc, taką strukturę danych nazywamy słownikiem). Nadaje się on idealnie do zastosowania w programach, w których nie jesteśmy w stanie przewidzieć, ile danych będziemy musieli przechowywać. Najprostszą strukturą spełniającą takie wymogi jest lista jednokierunkowa i właśnie na jej przykładzie prześledzimy "życie" dynamicznej struktury danych.

Jeden element listy może zawierać takie same informacje, jak pojedyncza komórka tabeli, a zatem dowolne liczby, napisy itp. Czym zatem różni się lista od tabeli? Pojedynczy segment składa się z co najmniej dwóch pól - oprócz wspomnianej wartości przechowuje także wskaźnik na element znajdujący się bezpośrednio po nim. Mając zatem dostęp do pierwszego elementu, możemy z powodzeniem dostać się do każdego innego wchodzącego w skład naszej struktury. Dlatego używając listy, zawsze będziemy zapamiętywać bezpośrednio tylko jej początek (tzw. głowę).

Praktyka czyni mistrza – implementujemy listę

Na początku przygody z listą musimy ustalić, jak będzie wyglądać jej element. Wykorzystamy do tego celu poznane niedawno na wykładzie struktury. Załóżmy, że interesuje nas lista naszych obowiązków na dany dzień. Każdy obowiązek przechowywać będziemy w zmiennej typu char* (napisie), zatem nasza struktura (nazwijmy ją Duty) będzie wyglądała następująco:

struct Duty
{
	char* toDo;
	Duty *next;
};

Napis toDo będzie przechowywał treść zadania, a wskaźnik next będzie pokazywał kolejny obowiązek (jeśli takowy będzie istniał).

Powiedzieliśmy, że należy pamiętać "głowę" listy. Dlatego też w funkcji main() umieścimy zapis:

Duty *ToDoListHead = NULL;

Będzie to wskaźnik na początek listy. Zainicjowany jest wartością NULL, ponieważ na początku działania programu lista nie zawiera jeszcze żadnych elementów.

Powiedzieliśmy sobie, że chcemy, aby można było:

  • dodawać elementy do ciągu,
  • przeglądać elementy ciągu,
  • usuwać elementy.

Spróbujmy zatem napisać funkcje, które nam to umożliwią. Ponieważ bez dodawania elementów ciężko byłoby stworzyć listę, zaczniemy od tej właśnie funkcjonalności.

Dodawanie elementów

Zasadniczo elementy w liście można dodawać w różnych jej miejscach. My założymy, że chcemy, by każdy nowy element dodawany był na początek listy. Zastanówmy się, jakie argumenty powinna przyjmować funkcja, a co zwracać. Niewątpliwie musimy wiedzieć co dodawać – zatem przydatny będzie napis zawierający treść obowiązku. Przydałaby się również wiedza na temat listy, do której chcemy dołączyć nowy segment (może być ich przecież wiele w programie). Podkreślaliśmy wcześniej rolę "głowy" w dostępie do dowolnego elementu – i to właśnie wskaźnik na nią powinien być drugim argumentem. Co zwróci funkcja? Również wskaźnik na początek listy, ale już tej wzbogaconej o nowy element.

Ostatecznie nagłówek funkcji będzie przedstawiał się następująco:

Duty* addElement(Duty* head, char* newOne)

Wiemy już, co do czego, czas pomyśleć, jak. Ponieważ chcemy dołączać obowiązki na początku, za każdym razem będziemy podmieniać "głowę". Nie dajmy się zwieść narzucającemu się następującemu rozwiązaniu:

Duty* addElement(Duty* head, char* text)
{
	head = new Duty;
	head->toDo = new char[strlen(text)+1];
	strcpy(head->toDo, text);
	head->next = head;
	return head;
}

Owszem, pierwszy element listy zawiera w tym wypadku żądany napis, ale prześledźmy, jak zmienia się zawartość listy podczas działania takiego oto fragmentu kodu:

ToDoListHead = addElement(ToDoListHead, "umyj sie");
ToDoListHead = addElement(ToDoListHead, "zamiec podloge");
cout << "KONIEC" << endl;
Celem podejrzenia zawartości żądanej zmiennej posłużymy się naszym przyjacielem Debuggerem. Ustawmy breakpoint'y w każdej z powyższych trzech linijek i wywołajmy program w trybie Debug (przypomnienie podstaw debugowania - samouczek nr 5).

Przy każdym kroku rzućmy okiem na panel Locals:

Dodawanie elementu - błędy

Jak interpretować zawarte w nim informacje?

  1. Dla pierwszego breakpoint'a nasza lista jest pusta - wskaźnikowi przypisaliśmy wartość NULL. Obok nazwy zmiennej ToDoListHead widnieje adres i zawartość komórki, którą zmienna wskazuje. W języku C++ adres pustego znaku ma wartość 0, dlatego ToDoListHead wskazuje komórkę o adresie 0x00000000. W związku z tym toDo jest napisem pustym. Także pole next jest "nieobliczalne" - skoro zmienna nie istnieje, nie ma tak naprawdę pól.
  2. W drugim kroku wskaźnikowi przyporządkowany jest niezerowy adres (dla każdego wywołania programu może być on inny). Zawartość komórki wskazywanej to – zgodnie z naszym planem – napis "umyj sie". Schody zaczynają się przy polu next – lista powinna być jednoelementowa, zatem adres wskazywanej przezeń komórki winien być zerowy. Tymczasem okazuje się, że nasz nowy element wskazuje na samego siebie... i tak "w koło Macieju"!
  3. W tym kroku nasza implementacja dodawania elementu "sypie się" już zupełnie – nie dość, że końca listy nie widać, to jeszcze nigdzie nie ma poprzednio dodanego obowiązku "umyj sie". Zmienił się adres początkowej komórki, zmienił się napis, ale niestety zniknął poprzedni wpis.

Co zrobić z tym fantem? Pomoże nam debugowanie krok po kroku funkcji addElement() (przypominam – przechodzenie do kolejnego kroku klawiszem F10). Okazuje się, że w pierwszej linijce funkcji zmiennej head przyporządkowujemy nowy adres – rezerwujemy nowe miejsce w pamięci, po czym w liniach kolejnych wypełniamy je napisem text i wskaźnikiem na to miejsce. Błąd leży zatem już u podstaw naszego rozumowania – nie możemy przypisywać wskaźnikowi head nowej komórki pamięci, ponieważ skutkuje to utratą dotychczasowej zawartości listy. Musimy stworzyć zmienną pomocniczą, podobnie jak ma to miejsce podczas zamiany wartości dwóch zmiennych typu int. Oto poprawna wersja funkcji addElement():

Duty* addElement(Duty* head, char* text)
{
	Duty* temp = new Duty;
	temp->toDo = new char[strlen(text)+1];
	strcpy(temp->toDo, text);
	temp->next = head; // dotychczasowa glowa
	return temp; // "nowa" glowa
}

Teraz dodawanie nowego elementu przebiega następująco:

  • [3] Powstaje lokalna zmienna wskaźnikowa temp. Przyporządkowujemy jej komórkę pamięci.
  • [4-5] Do komórki wskazywanej przez temp wpisujemy nowy obowiązek.
  • [6] Wskaźnikowi zawartemu w nowej komórce przypisujemy adres dotychczasowego początku listy.
  • [7] Zwracamy adres komórki z nowym obowiązkiem, po którym następują wszystkie "poprzednie" obowiązki.

Usuwanie elementów

Po wykonaniu jakiegoś obowiązku będziemy z pewnością chcieli usunąć go z listy. Usuwanie będzie zatem polegało na odnalezieniu elementu odpowiadającego wykonanemu zadaniu, a następnie jego usunięciu. Argumenty funkcji oraz wartość zwracana będą więc takie same, jak w przypadku addElement(). Przyjrzyjmy się schematowi "właściwej" części algorytmu, czyli tej odpowiedzialnej za usunięcie już odnalezionego elementu:

Schemat usuwania elementu

Jak wynika z rysunku, musimy nie tylko usunąć dany element, ale także zmienić adres wskazywany przez jego poprzednika. Jak uzyskać dostęp do poprzednika? Najprostszym rozwiązaniem będzie wprowadzenie zmiennej pomocniczej prev, która będzie przechowywała adres elementu poprzedniego. Ponownie jednak może nam zaświtać w głowie niezbyt zdrowy pomysł, aby zaimplementować usuwanie w następujący sposób:

Duty* removeElement(Duty* head, char* text)
{
	Duty* prev = NULL;

	//przechodzimy po elementach listy
	//do napotkania jej konca lub usuwanego elementu
	while (head != NULL && strcmp(head->toDo, text)!=0)
	{
		prev = head;
		head = head->next;
	}

	//jezeli odnaleziono usuwany element
	if (head != NULL)
	{
      delete [] head->toDo;
		delete head;//usuwamy element

		if (prev == NULL)
		{
			//przypadek, gdy szukanym elementem jest glowa
			 head = head->next;
		}
		else
		{
			prev->next = head->next;
		}
	}
	return head;
}

Będąc nieuważnym, można stwierdzić, że tak napisany algorytm powinien usuwać żądany element. Nic bardziej mylnego! Sprawdźmy, jak wygląda lista po wykonaniu następujących operacji:

ToDoListHead = addElement(ToDoListHead, "umyj sie");
ToDoListHead = addElement(ToDoListHead, "zamiec podloge");
ToDoListHead = addElement(ToDoListHead, "poglaszcz kota");
ToDoListHead = addElement(ToDoListHead, "poucz sie aipp");

ToDoListHead = removeElement(ToDoListHead, "poglaszcz kota");
ToDoListHead = addElement(ToDoListHead, "poczaruj");

Zgodnie z panelem Locals funkcja removeElement() działa "aż za dobrze" ;-) – nie tylko usuwa żądany element, ale czyści całą listę! Jest jeszcze jeden problem – następująca po jej zastosowaniu próba dodania elementu do listy kończy się zapętleniem dodawanego elementu. Czyżby powtórka z rozrywki?

Nie pozostaje nam nic innego, jak debugować removeElement() krok po kroku. Zauważamy błąd w linii 23. – za komórkę wskazywaną przez prev nie dołącza się część listy następująca po usuwanym elemencie. Dlaczego tak się dzieje? Dostęp do tej części odbieramy sobie już w linijce 16., czyszcząc komórkę wskazywaną przez head. Co to dla nas oznacza? Element usunąć możemy dopiero po dopisaniu jego następnika do listy wynikowej. Wystarczy zatem, że instrukcję delete head; przeniesiemy na koniec zewnętrznej instrukcji warunkowej:

if (head->toDo == text)
{
	if (prev == NULL)
	{
		//przypadek, gdy szukanym elementem jest glowa
		 head = head->next;
	}
	else
	{
		prev->next = head->next;
	}
	delete [] head->toDo;
	delete head;//usuwamy element
}

Niestety algorytm nadal nie działa tak, jak byśmy chcieli. Funkcja removeElement() nadal zwraca pustą listę. Debugujemy dalej! No tak, okazuje się, że zwracamy head, czyli zasadniczo to, co parę linijek wcześniej usuwamy. Jak sobie z tym poradzić? Możemy wprowadzić kolejny pomocniczy wskaźnik. Nazwijmy go toDelete, jako że będzie reprezentował element, który zamierzamy usunąć. Ostatecznie powinniśmy więc otrzymać funkcję takiej postaci:

Duty* removeElement(Duty* head, string text)
{
	Duty* prev = NULL;
	Duty* toDelete = head;

	while (toDelete != NULL && strcmp(toDelete->toDo, text)!=0)
	{
		prev = toDelete;
		toDelete = toDelete->next;
	}

	if (toDelete != NULL)
	{
		if (prev == NULL)
		{
			head=head->next;
		}
		else
		{
			prev->next = toDelete->next;
		}

		delete [] toDelete->toDo;
		delete toDelete;
	}
	return head;
}

Sprawdźmy, jak teraz radzi sobie nasz algorytm. Ha! Tym razem pięknie wykonał to, o co go poprosiliśmy. Sprawdźmy jeszcze na wszelki wypadek, jak zareaguje, kiedy zechcemy usunąć głowę... Wystarczy, że dla removeElement() zmienimy drugi argument na "poucz sie aipp".

Wygląda na to, że wszystko jest w najlepszym porządku. :-)

Wiesz już, jak poruszać się po liście. Spróbuj zaimplementować funkcję
Duty* addElement2(Duty* head, char* text)
dodającą element na koniec listy.

Przeglądanie listy

Przez przeglądanie listy rozumiemy wypisanie jej zawartości na konsolę. Aby to osiągnąć, musimy przejść po wszystkich jej elementach i zwyczajnie wypisać napisy z poszczególnych segmentów. Jak nietrudno zauważyć, funkcja będzie dość podobna do pierwszej części algorytmu usuwającego element. :-)

Prześledź przy użyciu debuggera stan listy podczas jej przeglądania przy użyciu poniższej funkcji.
void write(Duty* head)
{
	cout << "Obowiazki na dzis: "<< endl;
	while (head != NULL)
	{
		cout << head->toDo << endl;
		head = head->next;
	}
}
Czy podana implementacja jest prawidłowa?

Podsumowanie

Nauczyliśmy się, jak interpretować zawarte w panelu Locals dane dotyczące dynamicznej struktury danych na przykładzie listy jednokierunkowej. Wiemy też, jak radzić sobie z niektórymi problemami czyhającymi na nas podczas implementacji takich struktur danych. Może warto poćwiczyć teraz przyswojoną wiedzę, implementując stos? Powodzenia! :-)

CC By 3.0
Copyright © 2011-2016 by Jowita Hącia [Last update: 2017-02-01 17:17:10]
This work is licensed under a Creative Commons Attribution 3.0 Unported License