Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1.5.Podstawowestrukturydanych
1.5.1.
Lista
27
Lista2)toskończonyciągelementów:q=[x
1,x
2,...,x
n].Skrajneelementylistyx
1ix
n
nazywająsiękońcamilisty(odpowiednio-lewymiprawym),awielkość|q|=n-długo-
ścią(lubrozmiarem)listy.Szczególnymprzypadkiemlistyjestlistapusta:q=[].
Weźmydwielisty:q=[x
1,x
2,...,x
n]ir=[y
1,y
2,...,y
m],iniech0≤i≤j≤n:
Podstawowymiabstrakcyjnymioperacjaminalistachsą:
•dostępdoelementulisty-q[i]=xi;
•podlista-q[i..j]=[xi,xi+1,...,xj];
•złożenie–q&r=[x1,...,xn,y1,...,ym].
Zapomocątychtrzechpodstawowychoperacjimożnadefiniowaćinneoperacjenalistach,
naprzykładwstawianieelementuxzaelementx
inaliścieq:q[1..i]&[x]&q[i+1..|q|].
Listyużywasięzwyklewspecjalnysposób,ograniczającsiędozmianjejkońców:
(a)front(q)=q[1]
(pobieranielewegokońcalisty);
(b)push(q,x)=[x]&q
(wstawienieelementuxnalewykonieclisty);
(c)pop(q)=q[2..|q|]
(usunięciebieżącegolewegokońcalisty);
(d)rear(q)=q[|q|]
(e)inject(q,x)=q&[x]
(f)eject(q)=q[1..|q|-1]
(pobieranieprawegokońcalisty);
(wstawienieelementuxnaprawykonieclisty);
(usunięciebieżącegoprawegokońcalisty).
Listę,naktórejmożnawykonaćwszystkichsześćoperacji,nazywasiękolejkąpodwójną.
Wszczególnychprzypadkach,tzn.kiedyuwzględniasiętylkooperacjefront,pushipop,
nazywasięjąstosem,akiedyuwzględniasiętylkooperacjefront,popiinject-kolejką.
(Operacjenaabstrakcyjnejstrukturzedanychmogąbyćrealizowanezapomocąfunkcjialbo
procedur).
Dwiepodstawoweimplementacje(reprezentacje)listyq=[x
1,x
2,...,x
n]to:
•tablicowa–q[i]=xi,gdzie1≤i≤n,
•dowiązaniowa–różnewariantysąprzedstawionenarysunku1.1.
Wimplementacjachpojedynczejliniowejipodwójnejliniowejdowiązanieprowadzącedo
listywskazujenapierwszyelementnaliście,awimplementacjipojedynczejcyklicznej
ipodwójnejcyklicznęjnaostatni.Abymiećgwarancję,żestrukturadowiązaniowanigdy
niebędziepusta,dodajesięnapoczątkulistyelementpusty,nazywanygłowąlubwartow-
nikiemlisty.
2)Wtymsensielistajesttymsamymcowmatematyceciąg.
