ALG2

122 Rozdział 5. Struktury danych

Czerniak zarabia 3000zl

Wynik usunięcia rekordu pracownika zarabiającego 2000zł=l *"* * 3aza danych posortowana alfabetyczne ***

Bec zarabia IJOOzł Becki zarabia lOOOzł Czerniak zarabia 3000zł Fikus zarabia IJOOzł

*** Baza danych posortowana wy zarobków ***

Becki zarabia lOOCzł Fikus zarabia 120Czł Bec zarabia UOCzl Czerniak zarabia 3C00zł

5.2. Tablicowa implementacja list

Programowanie w C++ zmusza niejako programistę do dobrego poznania operacji na dynamicznych strukturach danych, sprawnego żonglowania wskaźnikami etc. To jest uwaga natury ogólnej, natomiast trzeba zauważyć również, iż nie wszyscy wskaźniki lubią. Przyczyn tej niechęci należy upatrywać głównie w próbach programowania na przykład struktur listowych bez pełnego zrozumienia lego. co się chce zrobić. Efekty najczęściej są opłakane, a winę w takich przypadkach rzecz jasna ponosi „chłopiec do bicia”, czyli sam język programowania. Tymczasem, podobnie zresztą jak i w życiu, to samo można zrobić wieloma sposobami — o czym niejednokrotnie zapominamy.

Tak też jest i z listami. Okazuje się. że istnieje kilka sposobów tablicowej implementacji list, niektóre z nich charakteryzują się nawet dość istotnymi zaletami, niemożliwymi do uzyskania w realizacji „klasycznej” (czyli tej, którą mieliśmy okazję poznać wcześniej). Olbrzymią wadą tablicowych wersji struktur listowych jest marnotrawstwo pamięci - przydzielamy przecież na stale pewien obszar pamięci, powiedzmy dla 1000 elementów - bo tyle w „porywach” będziemy potrzebowali miejsca. Gdyby natomiast nasz program używał listy o długości 200 elementów, to i tak obszar realnie zajmowany wynosiłby 10001 Jest to jednak cena nie do uniknięcia, płacimy ją za prostotę realizacji.

5.2.1.Klasyczna reprezentacja tablicowa

Jedną z najprostszych metod zamiany tablicy na listę jest umówienie się co do sposobu interpretacji jej zawartości. Jeśli powiemy sobie głośno (i nie zapomnimy zbyt szybko o tym), że /-temu indeksowi tablicy będzie odpowiadać i-ty element listy, to problem mamy prawie z głowy. To „prawie” wynika z tego, że trzeba się umówić, ile maksymalnie elementów zechcemy zapamiętać na liście. Oprócz