PODPOWIEDZI do laboratorium nr 3.
Tablicowa implementacja dynamicznej
alokacji pamięci (przydziału elementu w tablicy) |
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).
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) |
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;