Działania na liście jednokierunkowej

0

Witam!

Jestem w trakcie pisania programu, który jako lista jednokierunkowa ma zawierać dane: nazwisko, rok urodzenia, rok studiów. Operacje jakie ma wykonywać:

  1. dodawanie tak, że nazwiska są ułożone rosnąco alfabetycznie (działa)
  2. usuwanie pierwszego (działa)
  3. usuwanie ostatniego (nie działa, problem z napisaniem właściwego kodu)
  4. usuwanie elementu o określonym nazwisku (działa)
  5. wyszukanie elementu o określonym nazwisku (działa)
  6. sortowanie wg roku urodzenia (działa)
  7. wyświetlanie całej listy (wyświetla, ale tylko raz, tak jakby usuwa listę po jej wyświetleniu)
  8. usuwanie całej listy (działa)
  • Problemem jest pierwszy element z listy, który staje się "nietykalny", omija go sortowanie, a dodatkowo program przypisuje mu dziwną wartość do parametru: rok studiów.
  • Dalej z punktem 3: nie jestem w stanie napisać działającego kodu na usunięcie ostatniego elementu z listy, przy wielu próbach udało mi się tylko dojść do momentu, gdy wyrzucał mi ciągle komunikat o pustej liście. Z powodu braku kodu tej procedury zakomentowałem ją w głównym menu.
  • Przy sortowaniu listy wg roku urodzenia, nie potrafię wstawić komunikatów: lista jest pusta, brak elementów do posortowania i lista została posortowana. W którym miejscu to powinno się znaleźć?
  • Problem z punktem 7: po dodaniu kilku elementów do listy, możliwe jest jej jednokrotne wyświetlenie, po nim tak jakby zostaje ona usunięta i każda następna próba kończy się powiadomieniem o pustej liście.
  • Chciałbym jeszcze aby w konsoli ENTER bez wprowadzenia wybranej opcji programu(lub wpisania żądanej wartości) nie przeskakiwał do nowej linii. Da się to jakoś zrobić?
    Jeszcze niby podstawa i banał (ale też mi odmawia posłuszeństwa), czyli kontrola wprowadzanych danych przez użytkownika. W polach nazwisko zakaz wprowadzania cyfr, a w polach rok urodzenia i rok studiów możliwość stosowania tylko znaków cyfrowych. Wiem wiem.. użyj funkcji VAL, ale jak dokładnie, żeby to działało? Nie da się inaczej, jakąś prostą pętlą?

Kodzik:

program L1;
USES Crt;

type
  Pstudent = ^student;
  student = record
    nazwisko : string[30];
    rurodzenia: integer;
    rstudiow: integer;
    next : Pstudent;
  end;


procedure dodaj_sortujac(var head : Pstudent);
var
  tmp, pom : Pstudent;
begin
  new(tmp);
  write('Nazwisko: ');
  readln(tmp^.nazwisko);

  write('Rok urodzenia: ');
  readln(tmp^.rurodzenia);

  write('Rok studiow: ');
  readln(tmp^.rstudiow);

  if (head = nil) or (head^.nazwisko > tmp^.nazwisko) then
    begin

      	tmp^.next := head;
      head := tmp;
    end
  else begin
       pom := head;
       while (pom^.next <> nil) and (pom^.next^.nazwisko < tmp^.nazwisko) do
             pom := pom^.next;
       tmp^.next := pom^.next;
       pom^.next := tmp;
  end;

end;


 procedure usun_pierwszego(var head : Pstudent);
var
  pom, tmp : Pstudent;
begin
  tmp := head;
  if tmp = nil then write('Lista jest pusta. Brak elementu do usuniecia. ')
  else
     begin
        if tmp = head then
          begin
             head := head^.next;
             dispose(tmp);
          end
        else
            begin
                 pom := head;
                 while pom^.next <> tmp do
                       pom := pom^.next;
                 pom^.next := tmp^.next;
                 dispose(tmp);
            end;
            writeln('Usunieto pierwszego studenta z listy. ');
     end;
   readln;
 end;


procedure wyswietl_liste(var head : Pstudent);
begin
  //clrscr;
  writeln('Lista studentow prezentuje sie nastepujaco: ');

  if head = nil then
     write('Lista jest pusta. ')
  else begin
    while head <> nil do
    begin
         writeln(head^.nazwisko, ' ', head^.rurodzenia, ' ', head^.rstudiow);
         head := head^.next;

    end;
  end;
  readln;
end;

procedure usun_liste(var head : Pstudent);
var
  pom: Pstudent;
begin
  if head = nil then begin
    write('Lista jest pusta. Brak elementow do usuniecia.');
    readln;
  end
  else
    begin
      while head <> nil do
            begin
                 pom:=head;
                 head := head^.next;
                 dispose(pom);
                 ;
            end;
      writeln('Lista zostala usunieta. ');
      readln;
    end;
end;



function szukaj(head : Pstudent; nazwisko : string) : Pstudent;
begin
    while (head <> nil) and (head^.nazwisko <> nazwisko) do
          head := head^.next;
    szukaj := head;
end;

procedure usun_nazwisko(var head : Pstudent);
var
  pom, tmp : Pstudent;
  nazwisko : string[30];
begin
  write('Podaj nazwisko studenta, ktorego chcesz usunac z listy: ');
  readln(nazwisko);
  tmp := szukaj(head, nazwisko);
  if tmp = nil then
    write('Nie ma takiego studenta na liscie. ')
  else
    begin
       if tmp = head then
         begin
            head := head^.next;
            dispose(tmp);
         end
       else
           begin
                pom := head;
                while pom^.next <> tmp do
                      pom := pom^.next;
                pom^.next := tmp^.next;
                dispose(tmp);
           end;
           writeln('Student o nazwisku: "', nazwisko, '" zostal usuniety z listy.');
    end;
  readln;
end;


 procedure szukaj_nazwisko(var head : Pstudent);
var
   tmp : Pstudent;
   nazwisko : string[30];
begin
  write('Podaj nazwisko studenta, ktorego chcesz znalezc: ');
  readln(nazwisko);
  tmp := szukaj(head, nazwisko);
  if tmp = nil then
    write('Nie ma takiego studenta na liscie. ')
  else
    begin
      writeln('Znaleziono studenta o nazwisku: "', nazwisko, '": ');
      writeln;
      writeln(head^.nazwisko, ' ', head^.rurodzenia, ' ', head^.rstudiow);
      writeln;

      end;
  readln;
    end;



procedure sortuj_rurodzenia (var head : Pstudent);
var
  sort, tmp, pom : Pstudent;
begin
  sort := nil;
  while head <> nil do
    begin
       new(tmp);
       tmp^.nazwisko := head^.nazwisko;
       tmp^.rurodzenia := head^.rurodzenia;
       if sort = nil then
         begin
            tmp^.next := nil;
            sort := tmp;
         end
       else
         begin
           pom := sort;
           while (pom^.next <> nil) and (pom^.next^.rurodzenia > tmp^.rurodzenia) do
             pom := pom^.next;
           tmp^.next := pom^.next;
           pom^.next := tmp;
         end;
       dispose(head);
       head := head^.next;
    end;
  head := sort;
  write('Ukonczono. ');
  readln;
end;




var
  i    : integer;
  tmp  : Pstudent;

BEGIN

 repeat
  Clrscr;
  Writeln('Lista jednokierunkowa operujaca na danych: Nazwisko, Rok urodzenia, Rok studiow.');
  Writeln;
  Writeln('+1. Dodaj studenta do listy.');
  Writeln('+2. Usun pierwszego studenta z listy.');
  Writeln('3. Usun ostatniego studenta z listy.');
  Writeln('+4. Usun studenta o wskazanym nazwisku.');
  Writeln('+5. Wyszukaj studenta o wskazanym nazwisku.');
  Writeln('6. Sortuj liste wg roku urodzenia.');
  Writeln('7. Wyswietl cala liste.');
  Writeln('+8. Usun cala liste.');
  Writeln('+0. Zakoncz prace.');
  Writeln;
  Write('Wybierz opcje: ');

  readln(i);
  writeln;
  writeln;
  if i = 1 then dodaj_sortujac(tmp);
  if i = 2 then usun_pierwszego(tmp);
  //if i = 3 then usun_ostatniego(tmp);
  if i = 4 then usun_nazwisko(tmp);
  if i = 5 then szukaj_nazwisko(tmp);
  if i = 6 then sortuj_rurodzenia(tmp);
  if i = 7 then wyswietl_liste(tmp);
  if i = 8 then usun_liste(tmp);

     until i = 0;
 writeln;

END.
 
2

Jeśli używać listy jednokierunkowej i chcesz mieć uniwersalną funkcję szukania elementu, zwracającą wskaźnik na dany węzeł - musisz tę funkcję napisać tak, aby zwracała dwa węzły, szukany oraz poprzedni względem szukanego; Czyli w sumie zamienić funkcję na procedurę i zwracać dwa pointery w parametrach (przez Var lub Out);

Dzięki temu w każdej głównej procedurze wykorzystującej mechanizm wyszukiwania, od razu dostaniesz dwa wskaźniki i np. usunięcie szukanego elementu będzie się sprowadzać do zaktualizowania pól Next;

Przykład takiej procedurki (w postaci metody klasy) znajduje się tutaj - Lista jednokierunkowa - GetElementByIndex; Pętla szuka elementu o zadanym indeksie, a Ty potrzebujesz znaleźć węzeł z danym nazwiskiem, więc wykorzystaj pętlę z tamtego artykułu (oraz zapamiętywania dwóch wskaźników), natomiast użyj dodatkowo warunku porównującego nazwiska:

PS: Końcową dwabinkę Ifów zamień na instrukcję wyboru (Case Of):

case i of
  1: dodaj_sortujac(tmp);
  2: usun_pierwszego(tmp);
  3: {usun_ostatniego(tmp)};
  4: usun_nazwisko(tmp);
  5: szukaj_nazwisko(tmp);
  6: sortuj_rurodzenia(tmp);
  7: wyswietl_liste(tmp);
  8: usun_liste(tmp);
end;

PPS: Kod jest nawet dobry (nie używasz zmiennych globalnych, deklarowanych na samej górze modułu), jednak popraw kod, bo nie trzymasz się przyjętej konwencji nazewnictwa i wykorzystujesz randomowe wcięcia.

1

Ad 3. Nic dziwnego bo nic takiego nie masz w kodzie.
Ad 7. procedure wyswietl_liste(var head : Pstudent); - var head, while head <> nil do, head := head^.next; - już rozumiesz?

0

Żeby nie wymyślać koła na nowo, użyj kod z pod adresu, z końca tego artykułu http://4programmers.net/Delphi/Lista_jednokierunkowa - polecam.

0

Dziękuję wam za wypowiedzi i szybką reakcję. Przyznaję się bez bicia, że kod nie jest w 100% pisany przeze mnie. Korzystam z materiałów, które znalazłem w internecie, edytuję je pod siebie, przerabiam i sklejam jak trzeba, stąd błędy. Dlaczego nie robię tego sam? Dopiero zaczynam przygodę zwaną "studiami", programowania nie ogarniam tak jak bym chciał, co nie znaczy, że nie próbuję. Niestety zajęcia prowadzone są w taki sposób, że ciężko jest mi coś przyswoić, sporo rzeczy nie rozumiem, większość dowiaduję się działając na gotowcach i analizując ich pracę.

_13th_Dragon napisał(a):

Ad 3. Nic dziwnego bo nic takiego nie masz w kodzie.
Ad 7. procedure wyswietl_liste(var head : Pstudent); - var head, while head <> nil do, head := head^.next; - już rozumiesz?

Niestety dalej nie rozumie istoty błędu w punkcie 7? Może już zbyt długo przy tym siedzę i tego nie widzę... Mogę prosić o bezpośrednią popraw błędu, najlepiej z wytłumaczeniem?

1

@DudziK - może tego nie widzisz, ale @_13th_Dragon próbował Ci przekazać, że podajesz do procedury wskaźnik na pierwszy węzeł listy (czyli head) przez referencję (słówko Var), czego efektem jest modyfikacja adresu węzła w podawanym do procedury wskaźniku; Usuń to słówko, bo po wykonaniu pętli wyświetlającej, zmienna podana w parametrze head przyjmie wartość Nil i kolejne wyświetlenia listy będą niemożliwe;

Co więcej - wykonanie kodu procedury wyświetlającej przyczyni się do wycieków pamięci, dlatego że utracisz referencję do istniejących w liście węzłów przez wyświetleniem zawartości listy.

0

Więc ten błąd dotyczy też procedury sortowania, prawda? Dlatego pierwszy element nie jest sortowany i zmienia się wartość ostatniego parametru data urodzenia?

Po samym usunięciu słówka VAR kasuje dodatkowo dwa pierwszy i ostatni element. Eh, zaczynam się w tym gubić.

*EDIT:
Dziwne, przy kolejnej próbie działania programu nic nie usnięto, ale pierwszy alfabetycznie ustawiony wpis jest "nietykalny". Nie bierze udziału w sortowaniu. Co więcej, wartość jego parametru: data urodzenia dostaje jakiejś dziwnej ujemnej wartości(to jest ten wyciek?), ale po każdym ponownym użyciu opcji sortuj, ta dziwna wartość przechodzi do następnej zmiennej, a poprzednia przyjmuje właściwą postać. Po takim przejściu wszystko jest git, tylko ta pierwsza alfabetycznie ciągle siedzi u góry...

0

Wyciek pamięci to niezwolnienie zaalokowanego dynamicznie bloku pamięci; Ty używasz procedur New, więc alokujesz pamięć dla węzłów listy; Jeśli zgubisz adres któregokolwiek węzła to nie będziesz go mógł zwolnić z pamięci i on tam pozostanie;

Spróbuj użyć debugera - postaw break-pointy i użyj modułu podglądania zawartości zmiennych (okienko Watches); Po zatrzymaniu programu na danym break-point, używaj klawiszy F7 i F8 do śledzenia działania programu; Więcej o debugowaniu możesz poczytać w artykułach z sieci.

1

W sortowaniu przyczyna jest inna, tam nigdy nie porównujesz kolejnego rekordu z pierwszym, zaczynasz od następnego: pom^.next^.rurodzenia > tmp^.rurodzenia
No i kolejna rzecz która wcześniej czy później spowoduje wywalenie się programu: dispose(head); head := head^.next; - nie możesz sięgać do pamięci po dispose.

0

Więc żeby porównać kolejny rekord z pierwszym muszę dodać jeszcze jedną pętlę while? Czy mogę wstawić dodatkowy warunek do obecnej? A może ten obecny jest zły i powinienem go zmienić?

Wstawiając go przed dispose, stracę to co tam miałem. Więc jak to powinienem zadeklarować? Bo w tym miejscu chodzi o przepisanie tej listy z tymczasowej na główną.

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