ALG4

124 Rozdział 5. Struktury danych

Co jednak z dołączaniem elementów do listy? Poniżej są omówione dwie wersje odpowiedniej funkcji: pierwsza wstawia na koniec listy , druga na A:-tą jej pozycję. Oczywiście w przypadku tej drugiej funkcji niezbędne jest dokonanie odpowiedniego przesunięcia zawartości tablicy, podobnie jak w metodzie U.sunF.lenienl:

void ListaTab::WstawElement!int x)

I

// wstawiamy element x na koniec listy if(tab[0]<MaxTab-l) tab[++tab[0]]=x;

I

void ListaTab::WstawElementiint x, int k)

(//wstawiamy element x na k-ta pozycję listy: if((k>=l) &S (k<=tab[0]+1) 4& (tab(01<MaxTab-l))

{

for(int i=tab[01;i>=k;i —)

tab[i+1]-tab[i];// robimy miejsce tab (kj =x; tab(0]++;

)

)

Zasady posługiwania się takąpseudolistą sąjuż po stworzeniu wszystkich metod identyczne z „prawdziwą” listą jednokierunkową, dlatego też darujemy sobie cytowanie funkcji main.

Możliwe jest oczywiście takie zdefiniowanie klasy ListaTab, aby dołączanie elementów następowało już w porządku malejącym, rosnącym, czy też wedle jakiegoś innego klucza - Czytelnik może odpowiednio rozbudować funkcje i metody w ramach nieskomplikowanego ćwiczenia.

5.2.2.Metoda tablic równoległych

W poprzednio poznanej implementacji list przy pomocy zwykłej tablicy przypisaliśmy na sztywno /-temu elementowi tablicy i-ty element listy. W prostych zastosowaniach może to wystarczyć w zupełności, jednak rozwiązanie takie o wiele bardziej jest zbliżone ideowo do tablicy niż do listy. „Prawdziwa” lista powinna umożliwiać dość dowolne układanie elementów i sortowanie ich przy użyciu tylko i wyłącznie wskaźników. Chcieliśmy jednak od wskaźników, przydziałów pamięci, procedur new i delele uciec jak najdalej! Czyżby ich użycie było nieuchronne?

Odpowiedź na szczęście brzmi NIE! Wszystko można w końcu zasymulować, więc czemu nie wskaźniki?! Popularna metoda polega na zadeklarowaniu tablicy rekordów składających się z pola informacyjnego info i pola typu całkowitego następny, które służy do odszukiwania elementu „następnego” na liście. Dobrze znane i klasyczne wręcz rozwiązanie. Idea jest przedstawiona na rysunku