Duomenų struktūros ir algoritmai programoje „Java“. 4 dalis. Vieno susieto sąrašai

Kaip ir masyvai, kurie buvo pristatyti šios vadovėlių serijos 3 dalyje, susieti sąrašai yra pagrindinė duomenų struktūros kategorija, kuria galima remtis sudėtingesnėmis duomenų struktūromis. Skirtingai nuo elementų sekos, a susietas sąrašas yra mazgų seka, kur kiekvienas mazgas yra susietas su ankstesniu ir sekančiu sekos mazgu. Prisiminkime, kad a mazgas yra objektas, sukurtas iš autoreferencinės klasės, ir a savireferencinė klasė turi bent vieną lauką, kurio nuorodos tipas yra klasės pavadinimas. Susietame sąraše esantys mazgai yra susieti naudojant mazgo nuorodą. Štai pavyzdys:

 klasė Darbuotojas {private int empno; asmeninės eilutės pavadinimas; privatus dvigubas atlyginimas; valstybės darbuotojas kitas; // Kiti nariai. }

Šiame pavyzdyje Darbuotojas yra savarankiška klasė, nes jos Kitas laukas turi tipą Darbuotojas. Šis laukas yra a nuorodos laukas nes jis gali išsaugoti nuorodą į kitą savo klasės objektą - šiuo atveju kitą Darbuotojas objektas.

Šioje pamokoje pristatomi „Java“ programavimo atskirai susietų sąrašų trūkumai. Išmoksite operacijų, kaip sukurti atskirai susietą sąrašą, įterpti mazgus į atskirai susietą sąrašą, ištrinti mazgus iš susieto sąrašo, susieti atskirai susietą sąrašą su kitu atskirai susietu sąrašu ir apversti atskirai susietą sąrašą. Mes taip pat ištirsime algoritmus, dažniausiai naudojamus rūšiuojant atskirai susietus sąrašus, ir baigsime pavyzdžiu, rodančiu įterpimo rūšiavimo algoritmą.

atsisiųsti Gauti kodą Atsisiųskite tris šio straipsnio programų pavyzdžius. Sukūrė Jeffas Friesenas, skirtas „JavaWorld“.

Kas yra atskirai susietas sąrašas?

A atskirai susietas sąrašas yra susietas mazgų sąrašas, kuriame kiekvienas mazgas turi vieną nuorodos lauką. Šioje duomenų struktūroje pamatiniame kintamajame yra nuoroda į pirmąjį (arba viršutinį) mazgą; kiekvienas mazgas (išskyrus paskutinį ar apatinį mazgą) susieja su kitu; ir paskutinio mazgo nuorodos lauke yra nulinė nuoroda, nurodanti sąrašo pabaigą. Nors paprastai vadinamas kintamasis kintamasis viršuje, galite pasirinkti bet kokį norimą vardą.

1 paveiksle pateiktas atskirai susietas sąrašas su trimis mazgais.

Žemiau yra pseudokodas, skirtas atskirai susietam sąrašui.

 DECLARE CLASS Node DECLARE STRING name DECLARE Node next END DECLARE DECLARE Node top = NULL

Mazgas yra savireguliacinė klasė su a vardas duomenų laukas ir a Kitas nuorodos laukas. viršuje yra tipinis kintamasis Mazgas kad turi nuorodą į pirmąjį Mazgas objektas atskirai susietame sąraše. Kadangi sąrašo dar nėra, viršujepradinė vertė yra NULL.

Vieno susieto sąrašo kūrimas „Java“

Sukuriate atskirai susietą sąrašą, pridėdami vieną Mazgas objektas. Šis pseudokodas sukuria a Mazgas objektą, priskiria jo nuorodą viršuje, inicijuoja savo duomenų lauką ir priskiria NULL į savo nuorodų lauką:

 top = NEW mazgas top.name = "A" top.next = NULL

2 paveiksle parodytas pradinis atskirai susietas sąrašas, atsirandantis iš šio pseudokodo.

Ši operacija turi laiko (0) sudėtingumą - pastovi. Prisiminkime, kad O (1) tariama „Big Oh of 1“. (Žr. 1 dalį, norėdami priminti, kaip laiko ir erdvės sudėtingumo matavimai naudojami duomenų struktūroms įvertinti.)

Mazgų įterpimas į atskirai susietą sąrašą

Mazgo įterpimas į atskirai susietą sąrašą yra šiek tiek sudėtingesnis nei sukuriant atskirai susietą sąrašą, nes reikia apsvarstyti tris atvejus:

Įterpimas prieš pirmąjį mazgą.
Įterpimas po paskutinio mazgo.
Įterpimas tarp dviejų mazgų.

Įterpimas prieš pirmąjį mazgą

Naujas mazgas įterpiamas prieš pirmąjį mazgą, priskiriant viršutinio mazgo nuorodą į naujo mazgo nuorodos lauką ir priskiriant naujo mazgo nuorodą viršuje kintamasis. Šią operaciją parodo šis pseudokodas:

 DECLARE mazgo temp temp = NEW mazgo temp.name = "B" temp.next = top top = temp

Gauti dviejųMazgas sąrašas pateikiamas 3 paveiksle.

Ši operacija turi laiko sudėtingumą O (1).

Įterpimas po paskutinio mazgo

Naujas mazgas įterpiamas po paskutinio mazgo priskiriant niekinis į naujo mazgo nuorodos lauką, pereidami atskirai susietą sąrašą, norėdami rasti paskutinį mazgą, ir priskirdami naujo mazgo nuorodą paskutinio mazgo nuorodos laukui, kaip parodo šis pseudokodas:

 temp = NAUJAS mazgas temp.name = "C" temp.next = NULL DECLARE Node temp2 temp2 = top // Manome, kad top (ir temp2) nėra NULL // dėl ankstesnio pseudokodo. WHILE temp2.next NE NULL temp2 = temp2.next END WHILE // temp2 dabar nurodo paskutinį mazgą. temp2.next = temp

4 paveiksle pateikiamas sąrašas po įterpto Mazgas C po Mazgas A.

Ši operacija turi laiko sudėtingumą O (n)--linijinis. Jo laiko sudėtingumą galima pagerinti iki O (1) išlaikant nuorodą į paskutinį mazgą. Tokiu atveju nereikėtų ieškoti paskutinio mazgo.

Įterpimas tarp dviejų mazgų

Mazgo įterpimas tarp dviejų mazgų yra pats sudėtingiausias atvejis. Naują mazgą įterpiate tarp dviejų mazgų, eidami per sąrašą, kad surastumėte mazgą, kuris yra prieš naują mazgą, priskirdami surasto mazgo nuorodos lauke esančią nuorodą naujo mazgo nuorodos laukui ir priskirdami naujo mazgo nuorodą į surasto mazgo nuorodą. srityje. Šis pseudokodas rodo šias užduotis:

 temp = NEW Mazgas temp.name = "D" temp2 = top // Manome, kad naujai sukurtas mazgas įterpiamas po Mazgo // A ir kad mazgas A egzistuoja. Realiame pasaulyje nėra jokios // garantijos, kad koks nors mazgas egzistuoja, todėl turėtume patikrinti, ar temp2, kuriame yra NULL, tiek WHILE kilpos antraštėje //, tiek užbaigus WHILE kilpą. WHILE temp2.name NE "A" temp2 = temp2.next END WHILE // temp2 dabar nurodo mazgą A. temp.next = temp2.next temp2.next = temp

5 paveiksle pateiktas sąrašas po įterpimo Mazgas D tarp Mazgass A ir C.

Ši operacija turi laiko sudėtingumą O (n).

Mazgų ištrynimas iš atskirai susieto sąrašo

Mazgo ištrynimas iš atskirai susieto sąrašo taip pat yra šiek tiek sudėtingesnis nei kuriant atskirai susietą sąrašą. Tačiau reikia apsvarstyti tik du atvejus:

Pirmojo mazgo ištrynimas.
Bet kurio mazgo, išskyrus pirmąjį mazgą, ištrynimas.

Pirmojo mazgo ištrynimas

Ištrynus pirmąjį mazgą, nuoroda priskiriama pirmo mazgo nuorodos lauke kintamajam, kuris nurodo pirmąjį mazgą, bet tik tada, kai yra pirmasis mazgas:

 JEI viršuje NE NULL TAD top = top. Next; // Nurodykite antrąjį mazgą (arba NULL, kai yra tik vienas mazgas). PABAIGA

6 paveiksle pateikiamas prieš ir po sąrašo rodinių, kur pirmasis Mazgas buvo ištrintas. Mazgas B dingsta ir Mazgas A tampa pirmuoju Mazgas.

Ši operacija turi laiko sudėtingumą O (1).

Bet kurio mazgo, išskyrus pirmąjį mazgą, ištrynimas

Ištrinant bet kurį mazgą, išskyrus pirmąjį, reikia surasti mazgą, kuris yra prieš ištrintiną mazgą, ir priskirti nuorodą ištrintino mazgo nuorodos lauke į ankstesnio mazgo nuorodos lauką. Apsvarstykite šį pseudokodą:

 JEI viršų NEBŪNA Tuomet temp = viršuje, kol temp.pavadinimas NE "A" temp = temp.next END WHILE // Manome, kad temp nuorodos Node A. temp.next = temp.next.next // Mazgo D nebėra. PABAIGA

7 paveiksle pateikiamas prieš ir po sąrašo, kuriame yra tarpinis rodinys, rodiniai Mazgas yra ištrintas. Mazgas Dingsta.

Ši operacija turi laiko sudėtingumą O (n).

1 pavyzdys: sukurkite, įterpkite ir ištrinkite į susietą sąrašą

Aš sukūriau „Java“ programą pavadinimu SLLDemo tai parodo, kaip sukurti, įterpti ir ištrinti mazgus atskirai susietame sąraše. 1 sąraše pateikiamas šios programos šaltinio kodas.

Sąrašas 1. „Java“ programos demonstracija atskirai susietiems sąrašams (SSLDemo.java, 1 versija)

 public final class SLLDemo {private static class Node {String name; Kitas mazgas; } public static void main (String [] args) {Mazgo viršus = nulis; // 1. Vieno susieto sąrašo nėra. viršuje = naujas mazgas (); top.name = "A"; top.next = null; sąvartynas („1 atvejis“, viršuje); // 2. Atskirai susietas sąrašas egzistuoja ir mazgas turi būti įterptas // prieš pirmąjį mazgą. Mazgo temp; temp = naujas mazgas (); temp.pavadinimas = "B"; temp.next = viršuje; viršuje = temp; sąvartynas („2 atvejis“, viršuje); // 3. Egzistuoja atskirai susietas sąrašas ir mazgas turi būti įterptas // po paskutinio mazgo. temp = naujas mazgas (); temp.pavadinimas = "C"; temp.next = null; Mazgo temp2; temp2 = viršuje; while (temp2.next! = null) temp2 = temp2.next; temp2.next = temp; sąvartynas („3 byla“, viršuje); // 4. Egzistuoja atskirai susietas sąrašas ir mazgas turi būti įterptas // tarp dviejų mazgų. temp = naujas mazgas (); temp.name = "D"; temp2 = viršuje; while (temp2.name.equals ("A") == false) temp2 = temp2.next; temp.next = temp2.next; temp2.next = temp; sąvartynas („4 atvejis“, viršuje); // 5. Ištrinkite pirmąjį mazgą. viršuje = viršuje.kitas; dump („Po pirmojo mazgo ištrynimo“, viršuje); // 5.1 Atkurti mazgą B. temp = new Node (); temp.pavadinimas = "B"; temp.next = viršuje; viršuje = temp; // 6. Ištrinkite bet kurį mazgą, išskyrus pirmąjį. temp = viršuje; while (temp.pavadinimas yra lygus ("A") == klaidingas) temp = temp.kitas; temp.next = temp.next.next; dump („Po D mazgo ištrynimo“, viršuje); } private static void dump (String msg, Node topNode) {System.out.print (msg + ""); while (topNode! = null) {System.out.print (topNode.name + ""); topNode = topNode.next; } System.out.println (); }}

Sudarykite 1 sąrašą taip:

 javac SLLDemo.java

Paleiskite gautą programą taip:

 java SLLDemo

Turėtumėte stebėti šį rezultatą:

 1 atvejis A atvejis 2 B A atvejis 3 B A C 4 atvejis B A D C pašalinus pirmąjį mazgą A D C po to, kai ištrintas D mazgas B A C

Sujungiami atskirai susieti sąrašai

Kartais gali tekti susieti atskirai susietą sąrašą su kitu atskirai susietu sąrašu. Pvz., Tarkime, kad turite žodžių, prasidedančių raidėmis A – M, sąrašą ir kitą žodžių, prasidedančių raidėmis N – Z, sąrašą ir norite sujungti šiuos sąrašus į vieną sąrašą. Šis pseudokodas apibūdina vieno susieto sąrašo sujungimo su kitu algoritmą:

 DECLARE Node top1 = NULL DECLARE Node top2 = NULL // Tarkime, kad kodas sukuria top1 nurodytą atskirai susietą sąrašą. // Tarkime, kad kodas sukuria „top2“ nurodytą atskirai susietą sąrašą. // Susieju top2 nuorodų sąrašą su top1 nuorodų sąrašu. IF top1 EQ NULL top1 = top2 END END IF // Raskite galutinį mazgą top1 nurodytame sąraše. DEKLARUOKITE Mazgo temp = top1 KAI temp.next NE NULL temp = temp.next END WHILE // Sujunkite top2 iki top1. temp.next = top2 END

Menkaverčiu atveju nėra top1nurodomas sąrašas ir t top1 yra priskirtas top2vertė, kuri būtų NULL jei nebūtų top2nurodomas sąrašas.

Ši operacija turi O (1) laiko sudėtingumą trivialiu atveju ir O (n) kitaip. Tačiau, jei išlaikote nuorodą į paskutinį mazgą, šio mazgo sąraše ieškoti nereikia; laiko sudėtingumas pasikeičia į O (1).

Vieno susieto sąrašo apvertimas

Kita naudinga operacija atskirai susietame sąraše yra inversija, kuris panaikina sąrašo nuorodas ir leidžia jums kirsti jo mazgus priešinga kryptimi. Šis pseudokodas pakeičia top1nuorodų sąrašo nuorodos:

 DECLARE mazgas p = top1 // Originalaus atskirai susieto sąrašo viršus. DECLARE mazgas q = NULL // Vienkartinio susieto sąrašo viršus. DECLARE Node r // Laikinas mazgo nuorodinis kintamasis. KAI P NE NULL // Kiekvienam mazgui originaliame atskirai susietame sąraše ... r = q // Išsaugoti būsimo įpėdinio mazgo nuorodą. q = p // Būsimo pirmtako nuoroda. p = p.next // Kitas nuorodos mazgas pirminiame atskirai susietame sąraše. q.next = r // Susiekite būsimo pirmtako mazgą su būsimu įpėdiniu mazgu. END WHILE top1 = q // Pirmiausia pateikite top1 nuorodą Mazgas pakeistame atskirai susietame sąraše. GALAS

Ši operacija turi laiko sudėtingumą O (n).