Tworzenie własnej listy dwukierunkowej

Autor podstrony: Krzysztof Zajączkowski

Stronę tą wyświetlono już: 25594 razy

Na podstawie informacji omówionych na stronie Programowanie → Podstawy C++ → Struktury można już stworzyć pierwszą konstrukcję listy dwukierunkowej, która umożliwia w znacznie szybszy sposób dynamiczne dodawanie i usuwanie nowych elementów listy. Na początek wykorzystam strukturę typu student, która była już wcześniej wykorzystywana:

struct student { char Nazwisko[100]; char Imie[100]; float MatematykaOcena; float FizykaOcena; };

Potrzebna będzie jeszcze jedna klasa, która wykorzysta strukturę typu student do przechowywania informacji dotyczących studenta oraz będzie miała dwa pola wskaźników do struktury tego samego typu. Pierwszy wskaźnik s_up będzie wskazywał na element znajdujący się powyżej bieżącego elementu listy, drugi s_dwon będzie wskazywał na element znajdujący się poniżej bieżącego elementu listy. Teraz gdy dany element listy nie ma pod sobą żadnego elementu to jego wskaźnik s_down będzie równy 0. Ogólna definicja klasy jest więc taka:

struct lista_studentow { lista_studentow *s_up; // Wskaźnik na górny element listy (gdy elementu nie ma równe 0) student s; // Dane studenta lista_studentow *s_down;// Wskaźnik na dolny element listy (gdy elementu nie ma równe 0) };

Do wykonywania poszczególnych operacji przyda się funkcja wczytująca dane dodawanego studenta:

void UstawStudenta(lista_studentow &st){ // funkcja ustawiająca elementy listy cout<<"Podaj nazwisko studenta: "; cin>>st.s.Nazwisko; cout<<"Podaj imie studenta: "; cin>>st.s.Imie; cout<<"Ocena koncowa z matematyki: "; cin>>st.s.MatematykaOcena; cout<<"Ocena koncowa z fizyki: "; cin>>st.s.FizykaOcena; }

Teraz wypadałoby utworzyć funkcję dodającą elementy do listy studenta:

void DodajStudenta(lista_studentow **s /*pobiera wskaźnik do adresu pierwszego elementu listy dwukierunkowej*/){ lista_studentow* t = *s; // tymczasowa zmienna pomocnicza, do której przypisany zostanie adres pierwszego elementu listy if(*s){ // jeżeli adres pierwszego elementu listy nie jest równy 0 to lista_studentow* st = new lista_studentow; // utwórz nowy element listy UstawStudenta(*st); // ustaw jego wartości while(t->s_down){ // tutaj znajdowanie ostatniego elementu listy t = t->s_down; } st->s_up = t; // przypisanie polu s_up nowego elementu listy adresu ostatniego elementu listy st->s_down = 0; // przypisanie polu s_down nowego elementu listy wartości zero (ponieważ stanie się on ostatnim elementem listy) t->s_down = st; // przypisanie staremu ostatniemu elementowi listy adresu nowego ostatniego elementu listy }else{ // w przeciwnym przypadku, gdy lista jest pusta to *s = new lista_studentow; // utwórz nowy element listy UstawStudenta(**s); // ustaw go (*s)->s_up = NULL; // wyzerowanie adresu wskaźnika s_up (*s)->s_down = NULL; // wyzerowanie adresu wskaźnika s_down } }

Funkcja usuwająca dany element listy:

void UsunStudenta(lista_studentow **s/*wskaźnik na adres pierwszego elementu listy*/, int index /*numer elementu usuwanego*/){ if(*s && index > -1){ // jeżeli index jest większy od zera i wskaźnik na pierwszy element listy nie jest zerowy to lista_studentow *indx = *s; // tworzę kopię adresu wskazania na pierwszy element listy for(int i = 1; i <=index; i++){ // tutaj szukam indeksu o podanym numerze indx = indx->s_down; } if(!indx->s_up && !indx->s_down){ // jeżeli oba wskaźniki s_up i s_down są zerowe to delete indx; // usuwam index *s = 0; // przypisuję zerowy adres wskazania do listy (lista pusta) }else if(index == 0){ // gdy index usuwanego elementu równy 0 to *s = (*s)->s_down; // przypisanie adresu wskazania na element znajdujący się pod wskaźnikiem s_down delete indx; // zwolnienie pamięci indx = 0; }else if(indx->s_up && indx->s_down){ // gdy dany element listy ma nad i pod sobą elementy listy to indx->s_up->s_down = indx->s_down; // przypisywanie adresu dla górnego elementu indx->s_down->s_up = indx->s_up; // przypisywanie adresu dla dolnego elementu delete indx; // zwalnianie pamięci indx = 0; }else if(!indx->s_down){ // gdy element listy nie ma pod sobą żadnego elementu listy to indx->s_up->s_down = 0; // element górny musi mieć przypisany adres zerowy delete indx; // zwalniam pamięć indx = 0; } } }

Przydałaby się jeszcze funkcja, która wypisze wszystkie elementy listy na ekranie:

void WypiszStudentow(lista_studentow *s){ if(s){ cout<<"=========================================================\n"; do{ cout<<"Podaj nazwisko studenta: "<<s->s.Nazwisko<<endl; cout<<"Podaj imie studenta: "<<s->s.Imie<<endl; cout<<"Ocena koncowa z matematyki: "<<s->s.MatematykaOcena<<endl; cout<<"Ocena koncowa z fizyki: "<<s->s.FizykaOcena<<endl; cout<<"=========================================================\n"; s = s->s_down; }while(s); } }

Ostania funkcja do zwalniania całej pamięci (czyli usuwania wszystkich elementów listy):

void ZwolnijPamiec(lista_studentow **s/*wskaźnik do adresu pierwszego elementu listy*/){ lista_studentow *temp; // zmienna pomocnicza while(*s){ // dopóki s nie wskazuje na zerowy adres pamięci temp = (*s)->s_down; // przepisywanie pamięci elementu o 1 pozycję niżej niż *s delete (*s); // zwalnianie pamięci *s = temp; // przypisywanie adresu poprzednio zapamiętanej } }

Pora zrobić coś z tym i utworzyć sobie przykładową listę dwukierunkową:

int main(){ lista_studentow *s = 0; // wskaźnik na pierwszy element listy DodajStudenta(&s); // dodawanie pierwszego studenciaka DodajStudenta(&s); // drugiego DodajStudenta(&s); // trzeciego WypiszStudentow(s); // wypisywanie studenciaków cout<<endl<<"Usuwanie studenta"<<endl; UsunStudenta(&s,1); // usuwanie studenciaka o indeksie 1 WypiszStudentow(s); // znów wypisywanie ZwolnijPamiec(&s); // zwalnianie pamięci WypiszStudentow(s); // wypisywanie (żeby sprawdzić czy zwolniło) if(!s) // to też oznacza zwolnienie pamięci cout<<"Zwolniono pamiec"; cout<<"Wcisnij enter, aby zamknac program..."; cin.get(); return 0; }

Na koniec warto by było jeszcze funkcję napisać, która oblicza liczbę elementów w liście, dodaje element do listy w wskazanym jej miejscu. Zadania te pozostawiam do rozwiązania czytelnikowi.

Propozycje książek