PODPOWIEDZI do laboratorium nr 3.

1. W przypadku tworzenia list uporządkowanych można zastosować dwa podejścia:
      i) najpierw wczytać wszystkie dane a dopiero potem je posortować
      ii) sortować dane na bieżąco w trakcie wczytywania / usuwania /,
          tzn. od razu wstawiać nowe elementy listy na właściwe miejsce
          (np. poprawiając zawartość pól "następny" w elemencie wstawianym i poprzedzającym)
   
   Podejście (i) jest łatwiejsze do zaimplementowania dla standardowych tablic,
   tzn. dla list zajmujących spójne obszary pamięci
   z fizycznym umieszczeniem elementów w tablicy według kryterium porządkowania.
   
   W przypadku reprezentacji w postaci listy wiązanej (patrz ilustracja odnośnie 3 laboratorium)
   dużo łatwiejsze do oprogramowania jest podejście (ii).
   

2. W przypadku wybrania podejścia ( ii ) algorytm bieżącego wstawiania nowego elementu
   do listy uporządkowanej powinien mieć następującą postać (szkicowo):
   
   a) Przydziel miejsce w pamięci (w tablicy struktur) do zapamiętania nowych danych.
       W przypadku zadania laboratoryjnego sprowadzi się to
       do znalezienia pierwszego "wolnego" elementu.

   np. int numer_nowego = -1; for( int i=0; i< ROZMIAR_TABLICY; i++ )   if( baza[ i ].ZAJETY == 0 )      {       numer_nowego = i;       baza[ i ].ZAJETY = 1;   // zajmujemy !       break;      } if( numer_nowego== -1)   cout<<"Błąd przydziału pamięci";

   b) Wczytaj / zapisz nowe dane do elementu o indeksie "numer_nowego"
   
   c) Znalezienie indeksu elementu listy po którym należy wstawić nowy element.
       W tym miejscu trzeba rozważyć trzy przypadki:
        - czy lista jest pusta  >> wówczas należy dołączyć nowy element jako jedyny do listy
           a w jego polu "następny" umieścić wartość "-1" jako zaznaczenie końca listy

if( poczatek == -1 )   { // lista jest pusta     poczatek = numer_nowego;     baza[numer_nowego].NASTEPNY = -1;   }

     - lista zawiera tylko elementy "alfabetycznie większe"
        (łatwo to wykryć sprawdzając czy pierwsza osoba w uporządkowanej liście
          ma nazwisko alfabetycznie "większe" )
        wówczas nowy element należy wstawić do listy jako "pierwszy"
        a dotychczasowy "pierwszy" stanie się drugim.

if( poczatek != -1 ) // lista nie jest pusta   if( strcmp( baza[poczatek].nazwisko , baza [numer_nowego]. nazwisko ) > 0 )     { // pierwszy element uporządkowanej listy ma "większe" nazwisko       baza[numer_nowego].NASTEPNY = poczatek;       poczatek = numer_nowego;     }

     - pozostałe przypadki, gdy lista zawiera więcej elementów
        i pierwszy z nich ma nazwisko alfabetycznie wcześniejsze od nowego elementu
        >>  wówczas należy znaleźć indeks elementu listy
        który po wstawieniu powinien bezpośrednio poprzedzać nasz nowy element
        ( będzie to "największe" nazwisko z całej listy,
           które jednocześnie jest "nie większe" od nazwiska przechowywanego w nowym elemencie.)
         Po znalezieniu "numeru_poprzedzajacego" dołączamy nasz element zaraz po nim.

int numer_poprzedzajacego; // tutaj oprogramuj algorytm znajdujący indeks elementu // który powinien bezpośrednio poprzedzać nowy  ;-) //  .  .  . // Jeżeli już znalazłeś "numer_poprzedzajacego" to możesz dołączyć "nowy" do listy baza[numer_nowego].NASTEPNY = baza[numer_poprzedzajacego].NASTEPNY; baza[numer_poprzedzajacego].NASTEPNY = numer_nowego;