PODPOWIEDZI do laboratorium nr 3.

Tablicowa implementacja dynamicznej alokacji pamięci (przydziału elementu w tablicy)
oraz "dynamicznej" listy jednokierunkowej wiązanej za pomocą indeksów
.

  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;