Tworzenie własnej listy dwukierunkowej

Stronę tą wyświetlono już: 3818 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:

Listing 1
  1. struct student
  2. {
  3. char Nazwisko[100];
  4. char Imie[100];
  5. float MatematykaOcena;
  6. float FizykaOcena;
  7. };

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:

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

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

Listing 3
  1. void UstawStudenta(lista_studentow &st){ // funkcja ustawiająca elementy listy
  2. cout<<"Podaj nazwisko studenta: ";
  3. cin>>st.s.Nazwisko;
  4. cout<<"Podaj imie studenta: ";
  5. cin>>st.s.Imie;
  6. cout<<"Ocena koncowa z matematyki: ";
  7. cin>>st.s.MatematykaOcena;
  8. cout<<"Ocena koncowa z fizyki: ";
  9. cin>>st.s.FizykaOcena;
  10. }

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

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

Funkcja usuwająca dany element listy:

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

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

Listing 6
  1. void WypiszStudentow(lista_studentow *s){
  2. if(s){
  3. cout<<"=========================================================\n";
  4. do{
  5. cout<<"Podaj nazwisko studenta: "<<s->s.Nazwisko<<endl;
  6. cout<<"Podaj imie studenta: "<<s->s.Imie<<endl;
  7. cout<<"Ocena koncowa z matematyki: "<<s->s.MatematykaOcena<<endl;
  8. cout<<"Ocena koncowa z fizyki: "<<s->s.FizykaOcena<<endl;
  9. cout<<"=========================================================\n";
  10. s = s->s_down;
  11. }while(s);
  12. }
  13. }

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

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

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

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

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.

Tematy powiązane

Komentarze