Tāpat kā masīvi, kas tika ieviesti šīs apmācību sērijas 3. daļā, arī saistītie saraksti ir pamata datu struktūras kategorija, uz kuras var balstīties sarežģītākas datu struktūras. Atšķirībā no elementu secības a saistīto sarakstu ir mezglu secība, kur katrs mezgls ir saistīts ar iepriekšējo un nākamo mezglu secībā. Atgādinām, ka a mezgls ir objekts, kas izveidots no pašreferenciālās klases, un a pašreferences klase ir vismaz viens lauks, kura atsauces tips ir klases nosaukums. Saistītā saraksta mezgli ir saistīti, izmantojot mezglu atsauci. Lūk, piemērs:
klase Darbinieks {private int empno; privāts virknes nosaukums; privātā dubultā alga; valsts Darbinieks nākamais; // Citi dalībnieki. }Šajā piemērā Darbinieks ir pašreferenciāla klase, jo tā Nākamais laukam ir tips Darbinieks. Šis lauks ir a saites lauks jo tas var saglabāt atsauci uz citu savas klases objektu - šajā gadījumā citu Darbinieks objekts.
Šī apmācība iepazīstina ar Java saistīto sarakstu nepilnībām Java programmēšanā. Jūs uzzināsiet darbības, kā izveidot atsevišķi saistītu sarakstu, mezglu ievietošanu atsevišķi saistītā sarakstā, mezglu dzēšanu no atsevišķi saistītā saraksta, atsevišķu saistīto sarakstu sasaistīšanu ar citu atsevišķi saistītu sarakstu un apgrieztu vienotu sarakstu. Mēs arī izpētīsim algoritmus, kurus visbiežāk izmanto atsevišķi saistītu sarakstu kārtošanai, un nobeigsim ar piemēru, kas parāda ievietošanas algoritmu.
lejupielādēt Iegūt kodu Lejupielādējiet trīs šī raksta lietojumprogrammu piemērus. Izveidoja Jeff Friesen JavaWorld.Kas ir atsevišķi saistīts saraksts?
A atsevišķi saistīts saraksts ir saistīts mezglu saraksts, kur katram mezglam ir viens saites lauks. Šajā datu struktūrā atsauces mainīgais satur atsauci uz pirmo (vai augšējo) mezglu; katrs mezgls (izņemot pēdējo vai apakšējo) savieno ar nākamo; un pēdējā mezgla saites laukā ir atsauce uz nulli, kas apzīmē saraksta beigas. Lai gan atsauces mainīgo parasti sauc tops, jūs varat izvēlēties jebkuru vēlamo vārdu.
1. attēlā parādīts atsevišķi saistīts saraksts ar trim mezgliem.
Zemāk ir atsevišķi saistītā saraksta pseidokods.
DECLARE CLASS Node DECLARE STRING nosaukums DECLARE Node next END DECLARE DECLARE Mezgls top = NULL Mezgls ir pašreferenciāla klase ar a nosaukums datu lauks un a Nākamais saites lauks. tops ir tipa atsauces mainīgais Mezgls kurā ir atsauce uz pirmo Mezgls objekts atsevišķi saistītā sarakstā. Tā kā saraksts vēl nepastāv, topssākotnējā vērtība ir NULL.
Atsevišķi saistītu sarakstu izveide Java
Jūs izveidojat atsevišķi saistītu sarakstu, pievienojot vienu Mezgls objekts. Šis pseidokods rada a Mezgls objektu, piešķir atsauci uz tops, inicializē datu lauku un piešķir NULL uz tās saites lauku:
top = NEW Mezgls top.name = "A" top.next = NULL 2. attēlā parādīts sākotnējais atsevišķi saistīto saraksts, kas rodas no šī pseidokoda.
Šai operācijai ir laika sarežģītība O (1) - nemainīga. Atgādinām, ka O (1) izrunā "Big Oh of 1". (Skatiet 1. daļu, lai atgādinātu, kā laika un telpas sarežģītības mērījumi tiek izmantoti datu struktūru novērtēšanai.)
Mezglu ievietošana atsevišķi saistītā sarakstā
Mezgla ievietošana atsevišķi saistītā sarakstā ir nedaudz sarežģītāka nekā izveidojot atsevišķi saistītu sarakstu, jo ir jāapsver trīs gadījumi:
- Ievietošana pirms pirmā mezgla.
- Ievietošana aiz pēdējā mezgla.
- Ievietošana starp diviem mezgliem.
Ievietošana pirms pirmā mezgla
Jauns mezgls tiek ievietots pirms pirmā mezgla, piešķirot augšējā mezgla atsauci uz jaunā mezgla saites lauku un piešķirot jaunā mezgla atsauci uz tops mainīgais. Šo darbību parāda šāds pseidokods:
DECLARE mezgla temp temp = NEW mezgla temp.name = "B" temp.next = top top = temp Rezultātā diviMezgls saraksts parādīts 3. attēlā.
Šai operācijai ir laika sarežģītība O (1).
Ievietošana aiz pēdējā mezgla
Jauns mezgls tiek ievietots aiz pēdējā mezgla, piešķirot nulle uz jaunā mezgla saites lauku, šķērsojot atsevišķi saistīto sarakstu, lai atrastu pēdējo mezglu, un piešķirot jaunā mezgla atsauci pēdējā mezgla saites laukam, kā parāda šāds pseidokods:
temp = NEW Mezgls temp.name = "C" temp.next = NULL DECLARE Mezgls temp2 temp2 = top // Mēs pieņemam, ka top (un temp2) nav NULL // iepriekšējā pseidokoda dēļ. KAMĒR temp2.next NE NULL temp2 = temp2.next END WHILE // temp2 tagad atsaucas uz pēdējo mezglu. temp2.next = temp 4. attēlā ir parādīts saraksts pēc teksta ievietošanas Mezgls C pēc Mezgls A.
Šai operācijai ir laika sarežģītība O (n) - lineāra. Tās laika sarežģītību varētu uzlabot līdz O (1), saglabājot atsauci uz pēdējo mezglu. Tādā gadījumā nebūtu nepieciešams meklēt pēdējo mezglu.
Ievietošana starp diviem mezgliem
Mezgla ievietošana starp diviem mezgliem ir vissarežģītākais gadījums. Jauno mezglu ievietojat starp diviem mezgliem, šķērsojot sarakstu, lai atrastu mezglu, kas atrodas pirms jaunā mezgla, piešķirot atsauci atrastā mezgla saites laukā jaunā mezgla saites laukam un piešķirot jaunā mezgla atsauci uz atrastā mezgla saiti laukā. Šis pseidokods parāda šos uzdevumus:
temp = NEW Mezgls temp.name = "D" temp2 = top // Mēs pieņemam, ka jaunizveidotais mezgls ievieto aiz mezgla // A un ka mezgls A pastāv. Reālajā pasaulē nav // garantijas, ka kāds mezgls eksistē, tāpēc mums būtu jāpārbauda //, vai temp2 satur NULL gan WHILE cilpas galvenē //, gan pēc tam, kad WHILE cilpa ir pabeigta. KAMĒR temp2.name NE "A" temp2 = temp2.next END WHILE // temp2 tagad atsauces mezgls A. temp.next = temp2.next temp2.next = temp 5. attēlā parādīts saraksts pēc teksta ievietošanas Mezgls D starp Mezglss A un C.
Šai operācijai ir laika sarežģītība O (n).
Mezglu dzēšana no atsevišķi saistītā saraksta
Mezgla dzēšana no atsevišķi saistītā saraksta ir arī nedaudz sarežģītāka nekā atsevišķa saites saraksta izveide. Tomēr jāapsver tikai divi gadījumi:
- Pirmā mezgla dzēšana.
- Dzēš jebkuru mezglu, izņemot pirmo.
Pirmā mezgla dzēšana
Pirmā mezgla dzēšana nozīmē saites piešķiršanu pirmā mezgla saites laukā mainīgajam, kas atsaucas uz pirmo mezglu, bet tikai tad, ja ir pirmais mezgls:
JA top augšpusē NULL TAD top = top.next; // Atsauciet otro mezglu (vai NULL, ja ir tikai viens mezgls). BEIGT, JA 6. attēlā parādīts pirms un pēc saraksta skatiem, kur pirmais Mezgls ir izdzēsts. Mezgls B pazūd un Mezgls A kļūst par pirmo Mezgls.
Šai operācijai ir laika sarežģītība O (1).
Dzēš jebkuru mezglu, izņemot pirmo
Jebkura mezgla dzēšana, bet pirmais mezgls ietver mezgla, kas atrodas pirms dzēšamā mezgla, atrašanu un atsauces piešķiršanu dzēšamā mezgla saites laukā iepriekšējā mezgla saites laukam. Apsveriet šādu pseidokodu:
JA top top NULL TAD temp = top WHILE temp.name NE "A" temp = temp.next END WHILE // Mēs pieņemam, ka temp atsauces mezgls A. temp.next = temp.next.next // mezgls D vairs nepastāv. BEIGT, JA 7. attēlā parādīts pirms un pēc saraksta skatiem, kur ir starpposms Mezgls tiek izdzēsts. Mezgls D pazūd.
Šai operācijai ir laika sarežģītība O (n).
1. piemērs: izveidojiet, ievietojiet un izdzēsiet atsevišķi saistītā sarakstā
Esmu izveidojis Java lietojumprogrammu ar nosaukumu SLLDemo kas parāda, kā izveidot, ievietot un dzēst mezglus atsevišķi saistītā sarakstā. 1. saraksts parāda šīs lietojumprogrammas pirmkodu.
Saraksts 1. Java lietojumprogrammas demonstrācija atsevišķi saistītu sarakstu sarakstiem (SSLDemo.java, 1. versija)
public final class SLLDemo {private static class Mezgls {Stīgas nosaukums; Nākamais mezgls; } public static void main (String [] args) {Mezgls top = null; // 1. Vienīgi saistīto sarakstu nav. top = jauns mezgls (); top.name = "A"; top.next = null; dump ("1. gadījums", augšpusē); // 2. Vienīgi piesaistītais saraksts pastāv, un mezgls jāievieto // pirms pirmā mezgla. Mezgla temp; temp = jauns Mezgls (); temp.nosaukums = "B"; temp.next = top; top = temp; dump ("2. gadījums", augšpusē); // 3. Atsevišķi saistīts saraksts pastāv, un mezgls jāievieto // aiz pēdējā mezgla. temp = jauns Mezgls (); temp.nosaukums = "C"; temp.next = null; Mezgla temp2; temp2 = augšdaļa; while (temp2.next! = null) temp2 = temp2.next; temp2.next = temp; dump ("lieta 3", augšdaļa); // 4. Pastāv atsevišķi piesaistītais saraksts, un mezgls jāievieto // starp diviem mezgliem. temp = jauns Mezgls (); temp.name = "D"; temp2 = augšdaļa; while (temp2.nosaukums ir vienāds ("A") == false) temp2 = temp2.next; temp.next = temp2.next; temp2.next = temp; dump ("4. gadījums", augšpusē); // 5. Dzēsiet pirmo mezglu. top = top.next; dump ("Pēc pirmā mezgla dzēšanas", augšā); 5.1. Atjaunot mezglu B. temp = new Node (); temp.nosaukums = "B"; temp.next = top; top = temp; // 6. Dzēsiet jebkuru mezglu, izņemot pirmo. temp = top; while (temp.name.equals ("A") == false) temp = temp.next; temp.next = temp.next.next; dump ("Pēc D mezgla dzēšanas", augšā); } 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 (); }} Apkopojiet 1. sarakstu šādi:
javac SLLDemo.java Palaidiet iegūto lietojumprogrammu šādi:
java SLLDemo Jums jāievēro šāda izeja:
1. lieta A lieta 2. B A lieta 3. B A C 4. gadījums B A D C pēc pirmā mezgla dzēšanas A D C pēc D mezgla dzēšanas B A C Sasaistītie atsevišķi saistītie saraksti
Reizēm var būt nepieciešams sasaistīt atsevišķi saistītu sarakstu ar citu atsevišķi saistītu sarakstu. Piemēram, pieņemsim, ka jums ir vārdu saraksts, kas sākas ar burtiem A līdz M, un cits vārdu saraksts, kas sākas ar burtiem N līdz Z, un jūs vēlaties apvienot šos sarakstus vienā sarakstā. Šis pseidokods apraksta algoritmu viena atsevišķi saista saraksta sasaistīšanai ar citu:
DECLARE Mezgls top1 = NULL DECLARE Mezgls top2 = NULL // Pieņemsim kodu, kas izveido ar top1 atsaucēm pievienotu atsevišķi saistītu sarakstu. // Pieņemsim kodu, kas izveido ar top2 atsaucēm saistītu vienreizēju sarakstu. // Saīsiniet top2 atsauces sarakstu ar top1 atsauces sarakstu. IF top1 EQ NULL top1 = top2 END END IF // Atrodiet gala mezglu top1 atsauces sarakstā. DEKLARĒT Mezgls temp = top1 KAMĒR temp.next NE NULL temp = temp.next END WHILE // Saīsiniet top2 līdz top1. temp.next = top2 END Triviālajā gadījumā nav top1- atsauces saraksts, un tā top1 tiek piešķirts top2vērtība, kas būtu NULL ja nebūtu top2- atsauces saraksts.
Šai operācijai ir O (1) laika sarežģītība triviālā gadījumā un O (n) citādi. Tomēr, ja saglabājat atsauci uz pēdējo mezglu, nav nepieciešams meklēt šo mezglu sarakstā; laika sarežģītība mainās uz O (1).
Atsevišķi saistītā saraksta apgriešana
Vēl viena noderīga darbība atsevišķi saistītā sarakstā ir inversija, kas apgriež saraksta saites, lai ļautu jums šķērsot tā mezglus pretējā virzienā. Šis pseidokods mainīs top1-referencētā saraksta saites:
DECLARE Mezgls p = top1 // Sākotnējā atsevišķi saistītā saraksta augšdaļa. DECLARE Mezgls q = NULL // Apgrieztā, atsevišķi saistītā saraksta augšdaļa. DECLARE Node r // Pagaidu mezgla atsauces mainīgais. KAMĒR P NE NULL // Katram mezglam sākotnējā atsevišķi saistītā sarakstā ... r = q // Saglabājiet nākamā pēcteces mezgla atsauci. q = p // Atsauce uz nākamo priekšgājēju. p = p.next // Atsauce uz nākamo mezglu sākotnēji atsevišķi saistītā sarakstā. q.next = r // Saistiet nākamo priekšgājēju Node ar nākamo pēcteci Mezglu. END WHILE top1 = q // Vispirms izveidojiet top1 atsauci Mezgls apgrieztā atsevišķi saistītā sarakstā. BEIGT Šai operācijai ir laika sarežģītība O (n).
2. piemērs: Atsevišķi saistītā saraksta apvienošana un apgriešana
Esmu izveidojis otro versiju SLLDemo Java lietojumprogramma, kas demonstrē savienošanu un inversiju. 2. sarakstā tiek parādīts šīs lietojumprogrammas pirmkods.
