Programovanie

Dátové štruktúry a algoritmy v Jave, časť 4: Jednotlivé zoznamy

Rovnako ako polia, ktoré boli predstavené v časti 3 tejto série tutoriálov, sú aj prepojené zoznamy základnou kategóriou dátových štruktúr, na ktorej je možné zakladať zložitejšie dátové štruktúry. Na rozdiel od postupnosti prvkov však a prepojený zoznam je postupnosť uzlov, kde každý uzol je prepojený s predchádzajúcim a nasledujúcim uzlom v poradí. Pripomeňme, že a uzol je objekt vytvorený zo sebareferenčnej triedy a a autoreferenčná trieda má aspoň jedno pole, ktorého referenčným typom je názov triedy. Uzly v prepojenom zozname sú prepojené prostredníctvom odkazu na uzol. Tu je príklad:

 trieda Zamestnanec {private int empno; súkromné ​​meno reťazca; dvojitý súkromný plat; ďalší verejný zamestnanec; // Ostatní členovia. }

V tomto príklade Zamestnanec je sebareferenčná trieda, pretože je Ďalšie pole má typ Zamestnanec. Toto pole je príkladom a pole odkazu pretože môže uložiť odkaz na iný objekt svojej triedy - v tomto prípade iný Zamestnanec objekt.

Tento tutoriál predstavuje vstupy a výstupy jednotlivo prepojených zoznamov v programovaní Java. Naučíte sa operácie na vytvorenie jednotlivo prepojeného zoznamu, vkladanie uzlov do jednotlivo prepojeného zoznamu, mazanie uzlov zo samostatne prepojeného zoznamu, zreťazenie jednotlivo prepojeného zoznamu do iného samostatne prepojeného zoznamu a invertovanie jednotlivo prepojeného zoznamu. Preskúmame tiež algoritmy, ktoré sa najčastejšie používajú na triedenie jednotlivo prepojených zoznamov, a zakončíme príkladom demonštrujúcim algoritmus triedenia vloženia.

stiahnuť Získajte kód Stiahnite si tri ukážkové aplikácie pre tento článok. Vytvoril Jeff Friesen pre JavaWorld.

Čo je jednotlivo prepojený zoznam?

A jednotlivo prepojený zoznam je prepojený zoznam uzlov, kde každý uzol má jedno pole odkazu. V tejto dátovej štruktúre obsahuje referenčná premenná odkaz na prvý (alebo horný) uzol; každý uzol (okrem posledného alebo dolného uzla) odkazuje na ďalší; a pole odkazu na posledný uzol obsahuje nulový odkaz, ktorý označuje koniec zoznamu. Aj keď sa referenčná premenná bežne nazýva hore, môžete si zvoliť ľubovoľné meno, ktoré chcete.

Obrázok 1 predstavuje jednotlivo prepojený zoznam s tromi uzlami.

Nižšie je uvedený pseudokód pre jednotlivo prepojený zoznam.

 VYHLASOVAŤ TRIEDU Uzol VYHLASOVAŤ STRING názov VYHLASOVAŤ Uzol ďalší KONIEC VYHLASOVAŤ VYHLASOVAŤ Uzol hore = NULL 

Uzol je sebareferenčná trieda s a názov dátové pole a a Ďalšie pole odkazu. hore je referenčná premenná typu Uzol ktorý obsahuje odkaz na prvý Uzol objekt v jednotlivo prepojenom zozname. Pretože zoznam zatiaľ neexistuje, horepočiatočná hodnota je NULOVÝ.

Vytvorenie jednotlivo prepojeného zoznamu v prostredí Java

Zoznam, ktorý je zvlášť prepojený, vytvoríte pripojením jedného Uzol objekt. Nasledujúci pseudokód vytvára a Uzol objektu, priradí jeho referenciu hore, inicializuje svoje dátové pole a priradí NULOVÝ do jeho poľa odkazu:

 top = NOVÝ uzol top.name = "A" top.next = NULL 

Obrázok 2 zobrazuje počiatočný jednotlivo prepojený zoznam, ktorý vyplýva z tohto pseudokódu.

Táto operácia má časovú zložitosť O (1) - konštantnú. Pripomeňme, že O (1) sa vyslovuje ako „Big Oh of 1.“ (V časti 1 je potrebné pripomenúť, ako sa na vyhodnotenie dátových štruktúr používajú merania časovej a priestorovej zložitosti.)

Vkladanie uzlov do jednotlivo prepojeného zoznamu

Vloženie uzla do jednotlivo prepojeného zoznamu je o niečo komplikovanejšie ako vytváranie jednotlivo prepojeného zoznamu, pretože je potrebné brať do úvahy tri prípady:

  • Vloženie pred prvý uzol.
  • Vloženie za posledný uzol.
  • Vloženie medzi dva uzly.

Vloženie pred prvý uzol

Nový uzol sa vloží pred prvý uzol priradením odkazu horného uzla k poli odkazu nového uzla a priradením odkazu nového uzla k hore premenná. Túto operáciu demonštruje nasledujúci pseudokód:

 DECLARE Uzol temp temp = NOVINKA Uzol tempname = "B" temp.next = top top = temp 

Výsledné dvaUzol zoznam sa zobrazuje na obrázku 3.

Táto operácia má časovú zložitosť O (1).

Vloženie za posledný uzol

Priradením sa za posledný uzol vloží nový uzol nulový do poľa odkazu nového uzla, prechádzanie jednotlivo prepojeného zoznamu a nájdenie posledného uzla a priradenie odkazu nového uzla k poli odkazu posledného uzla, ako ukazuje nasledujúci pseudokód:

 temp = NOVÝ Uzol temp.name = "C" temp.next = NULL DECLARE Uzol temp2 temp2 = top // Predpokladáme, že top (a temp2) nie sú NULL // kvôli predchádzajúcemu pseudokódu. WHILE temp2.next NE NULL temp2 = temp2.next END WHILE // temp2 teraz odkazuje na posledný uzol. temp2.next = temp 

Obrázok 4 odhaľuje zoznam nasledujúci po vložení Uzol C po Uzol A.

Táto operácia má časovú zložitosť O (n) - lineárny. Jeho časovú zložitosť je možné vylepšiť na O (1) udržiavaním odkazu na posledný uzol. V takom prípade by nebolo potrebné hľadať posledný uzol.

Vloženie medzi dva uzly

Vloženie uzla medzi dva uzly je najkomplexnejší prípad. Medzi dva uzly vložíte nový uzol prechádzaním zoznamu, aby ste našli uzol, ktorý sa nachádza pred novým uzlom, priradením odkazu v poli odkazu nájdeného uzla k poli odkazu nového uzla a priradením odkazu nového uzla k odkazu nájdeného uzla lúka. Nasledujúci pseudokód demonštruje tieto úlohy:

 temp = NOVÝ Uzol temp.name = "D" temp2 = top // Predpokladáme, že novovytvorený Uzol sa vloží za Uzol // A a že Uzol A existuje. V skutočnom svete neexistuje // záruka, že nejaký Uzol existuje, takže by sme potrebovali // skontrolovať, či obsahuje // temp2 obsahujúci NULL v hlavičke // počas cyklu WHILE a po dokončení cyklu WHILE. WHILE temp2.name NE "A" temp2 = temp2.next KONIEC WHILE // temp2 teraz odkazuje na uzol A. temp.next = temp2.next temp2.next = temp 

Obrázok 5 predstavuje zoznam nasledujúci po vložení Uzol D medzi Uzols A a C.

Táto operácia má časovú zložitosť O (n).

Odstránenie uzlov zo zoznamu, ktorý je zvlášť prepojený

Vymazanie uzla zo zoznamu, ktorý je zvlášť prepojený, je tiež o niečo komplikovanejšie ako vytváranie zoznamu, ktorý je zvlášť prepojený. Zvážiť však možno iba dva prípady:

  • Vymazanie prvého uzla.
  • Vymazanie ktoréhokoľvek uzla okrem prvého uzla.

Vymazanie prvého uzla

Vymazanie prvého uzla zahŕňa priradenie odkazu v poli odkazu prvého uzla k premennej, ktorá odkazuje na prvý uzol, ale iba ak existuje prvý uzol:

 AK top NE NULL POTOM top = top.next; // Odkaz na druhý uzol (alebo NULL, ak je iba jeden uzol). KONIEC AK 

Obrázok 6 predstavuje pohľady pred a za na zoznam, kde je prvý Uzol bolo vymazané. Uzol B zmizne a Uzol A sa stáva prvým Uzol.

Táto operácia má časovú zložitosť O (1).

Vymazanie ktoréhokoľvek uzla okrem prvého uzla

Odstránenie ktoréhokoľvek uzla okrem prvého uzla zahŕňa vyhľadanie uzla, ktorý predchádza uzlu, ktorý sa má vymazať, a priradenie odkazu v poli odkazu uzol, ktorý sa má vymazať, k poli odkazu predchádzajúceho uzla. Zvážte nasledujúci pseudokód:

 AK top NE NULL POTOM temp = top WHILE temp.name NE "A" temp = temp.next END WHILE // Predpokladáme, že temp odkazuje na uzol A. temp.next = temp.next.next // Uzol D už neexistuje. KONIEC AK 

Obrázok 7 predstavuje pohľady pred a po zozname, kde je medziprodukt Uzol sa vypúšťa. Uzol D zmizne.

Táto operácia má časovú zložitosť O (n).

Príklad č. 1: Vytváranie, vkladanie a mazanie v jednotlivo prepojenom zozname

Vytvoril som Java aplikáciu s názvom SLLDemo ktorý ukazuje, ako vytvárať, vkladať a mazať uzly v jednotlivo prepojenom zozname. Výpis 1 predstavuje zdrojový kód tejto aplikácie.

Výpis 1. Ukážka aplikácií Java pre jednotlivé prepojené zoznamy (SSLDemo.java, verzia 1)

 verejná konečná trieda SLLDemo {súkromná statická trieda Uzol {názov reťazca; Uzol ďalej; } public static void main (String [] args) {Uzol top = null; // 1. Zoznam, ktorý je zvlášť prepojený, neexistuje. top = nový uzol (); top.name = "A"; top.next = null; skládka („Prípad 1“ hore); // 2. Existuje jednotlivo prepojený zoznam a uzol musí byť vložený // pred prvý uzol. Teplota uzla; temp = new Node (); temp.name = "B"; temp.next = top; top = teplota; skládka („Prípad 2“ hore); // 3. Samostatne prepojený zoznam existuje a uzol musí byť vložený // za posledný uzol. temp = new Node (); temp.name = "C"; temp.next = null; Uzol temp2; temp2 = top; while (temp2.next! = null) temp2 = temp2.next; temp2.next = temp; skládka („Prípad 3“ hore); // 4. Existuje jednotlivo prepojený zoznam a uzol musí byť vložený // medzi dva uzly. temp = new Node (); temp.name = "D"; temp2 = top; while (temp2.name.equals ("A") == false) temp2 = temp2.next; temp.next = temp2.next; temp2.next = temp; skládka („Prípad 4“ hore); // 5. Odstráňte prvý uzol. top = top.next; dump ("Po prvom odstránení uzla", hore); // 5.1 Obnoviť uzol B. temp = new Node (); temp.name = "B"; temp.next = top; top = teplota; // 6. Vymažte akýkoľvek uzol okrem prvého uzla. temp = top; while (temp.name.equals ("A") == false) temp = temp.next; temp.next = temp.next.next; dump ("Po odstránení uzla D", hore); } výpis súkromných statických void (String msg, Node topNode) {System.out.print (msg + ""); while (topNode! = null) {System.out.print (topNode.name + ""); topNode = topNode.next; } System.out.println (); }} 

Zostavte zoznam 1 takto:

 javac SLLDemo.java 

Výslednú aplikáciu spustite nasledujúcim spôsobom:

 java SLLDemo 

Mali by ste dodržiavať nasledujúci výstup:

 Prípad 1 A Prípad 2 B A Prípad 3 B A C Prípad 4 B A D C Po odstránení prvého uzla A D C Po odstránení D uzla B A C 

Zreťazenie jednotlivo prepojených zoznamov

Možno budete občas musieť zreťaziť jednotlivo prepojený zoznam s iným samostatne prepojeným zoznamom. Predpokladajme napríklad, že máte zoznam slov, ktoré sa začínajú písmenami A až M, a ďalší zoznam slov, ktorý sa začína písmenami N až Z, a chcete tieto zoznamy spojiť do jedného zoznamu. Nasledujúci pseudokód popisuje algoritmus zreťazenia jedného jednotlivo prepojeného zoznamu do druhého:

 VYHLASOVAŤ uzol top1 = NULL VYHLASOVAŤ uzol top2 = NULL // Predpokladajme kód, ktorý vytvorí zoznam jednotlivo prepojených odkazov na top1. // Predpokladajme kód, ktorý vytvorí zoznam jednotlivo prepojených top2 odkazov. // Zreťazí zoznam odkazovaných na top2 do zoznamu odkazovaných na top1. IF top1 EQ NULL top1 = top2 END END IF // Vyhľadajte konečný uzol v zozname odkazovanom na top1. DECLARE Uzol temp = top1 WHILE temp.next NE NULL temp = temp.next END WHILE // Zreťaziť top2 na top1. temp.next = top2 END 

V malichernom prípade neexistuje top1-zmienený zoznam atď top1 je pridelený top2hodnota, ktorá by bola NULOVÝ keby nebolo top2-zmienený zoznam.

Táto operácia má časovú zložitosť O (1) v triviálnom prípade a časovú zložitosť O (1)n) inak. Ak však zachovávate odkaz na posledný uzol, nie je potrebné hľadať tento uzol v zozname; časová zložitosť sa zmení na O (1).

Inverzia jednotlivo prepojeného zoznamu

Ďalšou užitočnou operáciou na jednotlivo prepojenom zozname je inverzia, ktorý obráti odkazy v zozname a umožní vám prechádzať jeho uzlami v opačnom smere. Nasledujúci pseudokód obracia znak top1- odkazy na uvedený zoznam:

 DECLARE Uzol p = top1 // Horná časť pôvodného jednotlivo prepojeného zoznamu. DECLARE Uzol q = NULL // Horná časť obráteného jednotlivo prepojeného zoznamu. DECLARE Node r // Referenčná premenná dočasného uzla. WHILE p NE NULL // Pre každý uzol v pôvodnom jednotlivo prepojenom zozname ... r = q // Uložiť odkaz na budúci nástupca uzla. q = p // Referenčný budúci predchodca Uzol. p = p.next // Odkaz na ďalší uzol v pôvodnom jednotlivo prepojenom zozname. q.next = r // Prepojí budúci predchodca Node s budúcim následným uzlom. END WHILE top1 = q // Najprv urobí odkaz na top1 Uzol v obrátenom jednotlivo prepojenom zozname. KONIEC 

Táto operácia má časovú zložitosť O (n).

Príklad č. 2: Zreťazenie a obrátenie jednotlivo prepojeného zoznamu

Vytvoril som druhú verziu SLLDemo Aplikácia Java, ktorá demonštruje zreťazenie a inverziu. Výpis 2 predstavuje zdrojový kód tejto aplikácie.

$config[zx-auto] not found$config[zx-overlay] not found