Datové struktury a algoritmy v Javě, část 4: Jednotlivé odkazy

Stejně jako pole, která byla představena v části 3 této série kurzů, jsou propojené seznamy základní kategorií datových struktur, na nichž lze zakládat složitější datové struktury. Na rozdíl od sledu prvků však a spojový seznam je posloupnost uzlů, kde je každý uzel propojen s předchozím a následujícím uzlem v posloupnosti. Připomeňme, že a uzel je objekt vytvořený ze sebereferenční třídy a autoreferenční třída má alespoň jedno pole, jehož referenčním typem je název třídy. Uzly v propojeném seznamu jsou propojeny prostřednictvím odkazu na uzel. Zde je příklad:

 třída Zaměstnanec {private int empno; soukromé jméno řetězce; dvojitý soukromý plat; další veřejný zaměstnanec; // Ostatní členové. }

V tomto příkladu Zaměstnanec je sebereferenční třída, protože její další pole má typ Zaměstnanec. Toto pole je příkladem a pole odkazu protože může uložit odkaz na jiný objekt své třídy - v tomto případě jiný Zaměstnanec objekt.

Tento kurz představuje vstupy a výstupy jednotlivě propojených seznamů v programování Java. Naučíte se operace pro vytváření jednotlivě propojeného seznamu, vkládání uzlů do jednotlivě propojeného seznamu, mazání uzlů z jednotlivě propojeného seznamu, zřetězení jednotlivě propojeného seznamu do jiného jednotlivě propojeného seznamu a invertování jednotlivě propojeného seznamu. Prozkoumáme také algoritmy, které se nejčastěji používají pro třídění jednotlivě propojených seznamů, a zakončíme příkladem, který ukazuje algoritmus třídění vložení.

stáhnout Získat kód Stáhněte si tři ukázkové aplikace pro tento článek. Vytvořil Jeff Friesen pro JavaWorld.

Co je jednotlivě propojený seznam?

A jednotlivě propojený seznam je propojený seznam uzlů, kde každý uzel má jedno pole odkazu. V této datové struktuře obsahuje referenční proměnná odkaz na první (nebo horní) uzel; každý uzel (s výjimkou posledního nebo dolního uzlu) odkazuje na další; a pole odkazu posledního uzlu obsahuje nulový odkaz, který označuje konec seznamu. I když je referenční proměnná běžně pojmenována horní, můžete si vybrat libovolné jméno, které chcete.

Obrázek 1 představuje jednotlivě propojený seznam se třemi uzly.

Níže je uveden pseudokód pro jednotlivě propojený seznam.

 DEKLAROVAT TŘÍDU Uzel DEKLAROVAT STRING název VYHLEDAT uzel další KONEC VYHLEDAT PROHLÁŠIT Uzel nahoru = NULL

Uzel je samoreferenční třída s a název datové pole a další pole odkazu. horní je referenční proměnná typu Uzel který obsahuje odkaz na první Uzel objekt v jednotlivě propojeném seznamu. Protože seznam dosud neexistuje, horníPočáteční hodnota je NULA.

Vytvoření jednotlivě propojeného seznamu v Javě

Můžete vytvořit jednotlivě propojený seznam připojením jednoho Uzel objekt. Následující pseudokód vytvoří a Uzel objektu, přiřadí jeho odkaz horní, inicializuje své datové pole a přiřadí NULA do pole odkazu:

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

Obrázek 2 ukazuje počáteční jednotlivě propojený seznam, který vyplývá z tohoto pseudokódu.

Tato operace má časovou složitost O (1) - konstantní. Připomeňme, že O (1) se vyslovuje „Big Oh of 1.“ (Viz část 1 pro připomenutí toho, jak se měření složitosti času a prostoru používají k vyhodnocení datových struktur.)

Vkládání uzlů do jednotlivě propojeného seznamu

Vložení uzlu do jednotlivě propojeného seznamu je poněkud komplikovanější než vytváření jednotlivě propojeného seznamu, protože je třeba vzít v úvahu tři případy:

Vložení před první uzel.
Vložení za poslední uzel.
Vložení mezi dva uzly.

Vložení před první uzel

Nový uzel se vloží před první uzel přiřazením odkazu horního uzlu k poli odkazu nového uzlu a přiřazením odkazu nového uzlu k horní proměnná. Tuto operaci demonstruje následující pseudokód:

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

Výsledné dva-Uzel seznam se zobrazí na obrázku 3.

Tato operace má časovou složitost O (1).

Vložení za poslední uzel

Přiřazením se za poslední uzel vloží nový uzel nula do pole odkazu nového uzlu, procházení jednotlivě spojeným seznamem k nalezení posledního uzlu a přiřazení odkazu nového uzlu k poli odkazu posledního uzlu, jak ukazuje následující pseudokód:

 temp = NOVÝ Uzel temp.name = "C" temp.next = NULL DECLARE Uzel temp2 temp2 = top // Předpokládáme, že top (a temp2) nejsou NULL // kvůli předchozímu pseudokódu. WHILE temp2.next NE NULL temp2 = temp2.next END WHILE // temp2 nyní odkazuje na poslední uzel. temp2.next = temp

Obrázek 4 ukazuje seznam následující po vložení Uzel C po Uzel A.

Tato operace má časovou složitost O (n)--lineární. Jeho časová složitost by mohla být vylepšena na O (1) udržováním odkazu na poslední uzel. V takovém případě by nebylo nutné hledat poslední uzel.

Vložení mezi dva uzly

Vložení uzlu mezi dva uzly je nejsložitější případ. Mezi dva uzly vložíte nový uzel procházením seznamu, abyste našli uzel, který je před novým uzlem, přiřazením odkazu v poli odkazu nalezeného uzlu k poli odkazu nového uzlu a přiřazením odkazu nového uzlu k odkazu nalezeného uzlu pole. Následující úkoly předvádí tyto úkoly:

 temp = NOVÝ Uzel temp.name = "D" temp2 = top // Předpokládáme, že nově vytvořený Uzel se vloží za Uzel // A a že Uzel A existuje. V reálném světě neexistuje žádná // záruka, že nějaký uzel existuje, takže bychom museli // zkontrolovat // pro temp2 obsahující NULL v hlavičce WHILE smyčky // a po dokončení WHILE smyčky. WHILE temp2.name NE "A" temp2 = temp2.next KONEC WHILE // temp2 nyní odkazuje na uzel A. temp.next = temp2.next temp2.next = temp

Obrázek 5 představuje seznam následující po vložení Uzel D mezi Uzels A a C.

Tato operace má časovou složitost O (n).

Odstranění uzlů ze samostatně propojeného seznamu

Odstranění uzlu ze samostatně propojeného seznamu je také poněkud komplikovanější než vytvoření jednotlivě propojeného seznamu. Je však třeba vzít v úvahu pouze dva případy:

Vymazání prvního uzlu.
Odstranění libovolného uzlu kromě prvního uzlu.

Vymazání prvního uzlu

Odstranění prvního uzlu zahrnuje přiřazení odkazu v poli odkazu prvního uzlu k proměnné, která odkazuje na první uzel, ale pouze v případě, že existuje první uzel:

 IF top NE NULL THEN top = top.next; // Odkaz na druhý uzel (nebo NULL, pokud existuje pouze jeden uzel). END IF

Obrázek 6 představuje pohledy před a po seznamu, kde je první Uzel byl smazán. Uzel B zmizí a Uzel A se stane prvním Uzel.

Tato operace má časovou složitost O (1).

Odstranění libovolného uzlu kromě prvního uzlu

Odstranění libovolného uzlu kromě prvního uzlu zahrnuje vyhledání uzlu, který předchází uzlu, který má být odstraněn, a přiřazení odkazu v poli odkazu uzlu k odstranění k poli odkazu předchozího uzlu. Zvažte následující pseudokód:

 IF top NE NULL THEN temp = top WHILE temp.name NE "A" temp = temp.next END WHILE // Předpokládáme, že temp odkazuje na uzel A. temp.next = temp.next.next // Uzel D již neexistuje. END IF

Obrázek 7 představuje zobrazení před a po seznamu, kde je meziprodukt Uzel je smazán. Uzel D zmizí.

Tato operace má časovou složitost O (n).

Příklad č. 1: Vytváření, vkládání a mazání v jednotlivě propojeném seznamu

Vytvořil jsem aplikaci Java s názvem SLL Demo který ukazuje, jak vytvořit, vložit a odstranit uzly v jednotlivě propojeném seznamu. Výpis 1 představuje zdrojový kód této aplikace.

Výpis 1. Ukázka aplikace Java pro jednotlivě propojené seznamy (SSLDemo.java, verze 1)

 veřejná finální třída SLLDemo {soukromá statická třída Uzel {Název řetězce; Uzel další; } public static void main (String [] args) {Node top = null; // 1. Samostatně propojený seznam neexistuje. top = new Node (); top.name = "A"; top.next = null; výpis ("Případ 1", nahoře); // 2. Existuje jednotlivě propojený seznam a uzel musí být vložen // před první uzel. Teplota uzlu; temp = new Node (); temp.name = "B"; temp.next = top; top = temp; výpis ("Případ 2", nahoře); // 3. Existuje jednotlivě propojený seznam a uzel musí být vložen // za poslední uzel. temp = new Node (); temp.name = "C"; temp.next = null; Uzel temp2; temp2 = top; while (temp2.next! = null) temp2 = temp2.next; temp2.next = temp; výpis ("Případ 3", nahoře); // 4. Existuje jednotlivě propojený seznam a uzel musí být vložen // mezi 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; výpis ("Případ 4", nahoře); // 5. Odstraňte první uzel. top = top.next; dump ("Po vymazání prvního uzlu", nahoře); // 5.1 Obnovit uzel B. temp = new Node (); temp.name = "B"; temp.next = top; top = temp; // 6. Odstranit libovolný uzel kromě prvního uzlu. temp = top; while (temp.name.equals ("A") == false) temp = temp.next; temp.next = temp.next.next; dump ("Po odstranění D uzlu", nahoře); } výpis soukromého statického void (String msg, Node topNode) {System.out.print (msg + ""); while (topNode! = null) {System.out.print (topNode.name + ""); topNode = topNode.next; } System.out.println (); }}

Kompilace výpisu 1 následovně:

 javac SLLDemo.java

Výslednou aplikaci spusťte následovně:

 java SLLDemo

Měli byste dodržovat následující výstup:

 Případ 1 A Případ 2 B A Případ 3 B A C Případ 4 B A D C Po vymazání prvního uzlu A D C Po vymazání uzlu D B A C

Zřetězení jednotlivě propojených seznamů

Možná budete muset zřetězit jednotlivě propojený seznam do jiného samostatně propojeného seznamu. Předpokládejme například, že máte seznam slov, která začínají písmeny A až M a další seznam slov začínající písmeny N až Z, a chcete tyto seznamy spojit do jednoho seznamu. Následující pseudokód popisuje algoritmus pro zřetězení jednoho jednotlivě propojeného seznamu do druhého:

 DECLARE Node top1 = NULL DECLARE Node top2 = NULL // Předpokládejme kód, který vytvoří seznam jednotlivě propojených seznamů top1. // Předpokládejme kód, který vytvoří seznam nejlépe odkazovaných na top2. // Zřetězit seznam odkazovaných na top2 do seznamu odkazovaných na top1. IF top1 EQ NULL top1 = top2 END END IF // Vyhledejte konečný uzel v seznamu odkazovaném na top1. DECLARE Uzel temp = top1 WHILE temp.next NE NULL temp = temp.next END WHILE // Zřetězit top2 na top1. temp.next = top2 END

V triviálním případě neexistuje top1-referencovaný seznam atd top1 je přidělen top2hodnota, která by byla NULA kdyby nebylo top2-referencovaný seznam.

Tato operace má časovou složitost O (1) v triviálním případě a časovou složitost O (n) v opačném případě. Pokud však zachováte odkaz na poslední uzel, není třeba tento seznam prohledávat; časová složitost se změní na O (1).

Invertování jednotlivě propojeného seznamu

Další užitečná operace na jednotlivě propojeném seznamu je inverze, který obrátí odkazy v seznamu a umožní vám procházet jeho uzly v opačném směru. Následující pseudokód obrací znak top1-referencované odkazy na seznam:

 DECLARE Uzel p = top1 // Začátek původního jednotlivě propojeného seznamu. DECLARE Uzel q = NULL // Začátek obráceného jednotlivě propojeného seznamu. DECLARE Node r // Dočasná referenční proměnná uzlu. WHILE p NE NULL // Pro každý uzel v originálním jednotlivě propojeném seznamu ... r = q // Uloží odkaz na budoucí uzel uzlu. q = p // Referenční budoucí předchůdce Uzel. p = p.next // Odkaz na další uzel v původním jednotlivě propojeném seznamu. q.next = r // Propojení budoucího předchůdce uzlu s budoucím následníkem uzlu. END WHILE top1 = q // Nejprve vytvořit odkaz na top1 Uzel v obráceném jednotlivě propojeném seznamu. KONEC

Tato operace má časovou složitost O (n).