Откријте петљу у повезаној листи у Ц++

Крајњи чвор повезане листе који има петљу ће се односити на други чвор на истој листи, а не на НУЛЛ. Ако постоји чвор на повезаној листи коме се може више пута приступити праћењем следећег показивача, за листу се каже да имају циклус.

Обично се последњи чвор повезане листе односи на НУЛЛ референцу која означава закључак листе. Међутим, у повезаној листи са петљом, крајњи чвор листе се односи на почетни чвор, унутрашњи чвор или самог себе. Стога, у таквим околностима, морамо идентификовати и прекинути петљу тако што ћемо поставити референцу следећег чвора на НУЛЛ. Део детекције петље на повезаној листи је објашњен у овом чланку.

У Ц++-у постоје бројни начини за проналажење петљи у повезаној листи:

Приступ заснован на хеш табели : Овај приступ чува адресе посећених чворова у хеш табели. Петља у повезаној листи постоји ако је чвор већ присутан у хеш табели када се поново посети.

Приступ Флојдовог циклуса : Алгоритам „корњача и зец“, опште познат као Флојдов алгоритам за проналажење циклуса: Ова техника користи два показивача, један се креће спорије од другог, а други брже. Бржи показивач ће на крају престићи спорији показивач ако постоји петља на повезаној листи, откривајући постојање петље.

Рекурзивна метода : Овај метод пролази кроз повезану листу позивајући себе изнова и изнова. Повезана листа садржи петљу ако је тренутни чвор претходно посећен.

Приступ заснован на стеку : Овај приступ чува адресе посећених чворова у стеку. Петља у повезаној листи је присутна ако је чвор већ тамо у стеку када се поново посети.

Хајде да детаљно објаснимо сваки приступ да бисмо разумели концепт.

Приступ 1: ХасхСет приступ

Коришћење хеширања је најједноставнији метод. Овде пролазимо кроз листу један по један, држећи хеш табелу са адресама чворова. Дакле, петља постоји ако икада налетимо на следећу адресу тренутног чвора која је већ садржана у хеш табели. У супротном, нема петље у повезаној листи ако наиђемо на НУЛЛ (тј. дођемо до краја повезане листе).

Биће прилично лако спровести ову стратегију.

Док прелазимо преко повезане листе, користићемо унордеред_хасхмап и наставити да јој додајемо чворове.

Сада, када наиђемо на чвор који је већ приказан на мапи, знаћемо да смо стигли на почетак петље.

• • Поред тога, држали смо два показивача на сваком кораку, хеадНоде показујући на тренутни чвор и ластНоде показујући на претходни чвор тренутног чвора, док се понавља.
  • Као наш хеадНоде сада показује на почетни чвор петље и као ластНоде је показивао на чвор на који је показивала глава (тј. односи се на ластНоде петље), наш хеадНоде тренутно показује на почетни чвор петље.
  • Петља ће бити прекинута постављањем л астНоде->нект == НУЛЛ .

Радећи ово, завршни чвор петље уместо да се односи на почетни чвор петље, почиње да показује на НУЛЛ.

Просечна временска и просторна сложеност методе хеширања је О(н). Читалац увек треба да буде свестан да ће имплементација уграђене структуре хеширања података у програмском језику одредити укупну временску сложеност у случају колизије у хеширању.

Имплементација Ц++ програма за горњи метод (ХасхСет):

Излаз:

Објашњење кода корак по корак је дато у наставку:

1. 1. Датотека заглавља битс/стдц++.х>, која садржи све уобичајене Ц++ библиотеке, је укључена у код.
   2. Структура која се зове „Чвор“ је конструисана и има два члана: референцу на следећи чвор на листи и цео број који се зове „вредност“.
   3. Са целобројном вредношћу као улазом и показивачем „нект“ постављеним на НУЛЛ, функција „невНоде“ креира нови чвор са том вредношћу.
   4. Функција ' фунцтионХасхМап’ је дефинисан, који као улаз узима показивач на главни чвор повезане листе.
   5. Унутар ' фунцтионХасхМап ‘, креира се унордеред_мап под називом ‘хасх_мап’, која се користи за имплементацију структуре података хеш мапе.
   6. Показивач на последњи чвор листе је иницијализован на НУЛЛ.
   7. Петља вхиле се користи за прелазак преко повезане листе, која почиње од главног чвора и наставља се све док главни чвор није НУЛЛ.
   8. Показивач последњег чвора се ажурира на тренутни чвор унутар вхиле петље ако тренутни чвор (хеадНоде) већ није присутан у хеш мапи.
   9. Ако је тренутни чвор пронађен на мапи, то значи да је петља присутна на повезаној листи. Да бисте уклонили петљу, следећи показивач на ластНоде је подешен на НУЛА а петља вхиле је прекинута.
   10. Главни чвор повезане листе се користи као улаз за функцију која се зове „приказ“, која даје вредност сваког чвора на листи од почетка до краја.
   11. У главни функција, стварајући петљу.
   12. Функција „фунцтионХасхМап“ се позива са показивачем хеадНоде као улазом, чиме се петља уклања са листе.
   13. Измењена листа се приказује помоћу функције „приказ“.

Приступ 2: Флојдов циклус

Флојдов алгоритам за детекцију циклуса, често познат као алгоритам корњаче и зеца, пружа основу за овај метод лоцирања циклуса на повезаној листи. „Споро“ показивач и „брзи“ показивач, који прелазе листу различитим брзинама, су два показивача која се користе у овој техници. Брзи показивач напредује два корака, док спори показивач напредује за један корак у свакој итерацији. Циклус у повезаној листи постоји ако се две тачке икада сретну лицем у лице.

1. Са главним чвором повезане листе, иницијализујемо два показивача који се називају брз и спор.

2. Сада покрећемо петљу да се крећемо кроз повезану листу. Брзи показивач треба да се помери на две локације испред спорог показивача у сваком кораку итерације.

3. Неће бити петље у повезаној листи ако брзи показивач дође до краја листе (фастПоинтер == НУЛЛ или фастПоинтер->нект == НУЛЛ). Ако не, брзи и спори показивачи ће се на крају срести, што значи да повезана листа има петљу.

Имплементација Ц++ програма за горњи метод (Флојдов циклус):

Излаз:

Објашњење:

1. 1. Прво су укључена релевантна заглавља, као што су „битс/стдц++.х“ и „стд::цоут“.
   2. Структура „Чвор“, која означава чвор на повезаној листи, се затим декларише. Следећи показивач који води до следећег чвора на листи је укључен заједно са целобројним пољем података у сваком чвору.
   3. Затим дефинише „делетеЛооп“ и „детецтАндДелетеЛооп“, две функције. Петља се уклања са повезане листе користећи први метод, а петља се детектује на листи помоћу друге функције, која затим позива прву процедуру за уклањање петље.
   4. Нова повезана листа са пет чворова креира се у главној функцији, а петља се успоставља постављањем следећег показивача последњег чвора на трећи чвор.
   5. Затим позива методу „детецтАндДелетеЛооп“ док као аргумент прослеђује главни чвор повезане листе. За идентификацију петљи, ова функција користи приступ „Споро и брзо показиваче“. Користи два показивача који почињу на врху листе, словПТР и фастПТР. Док брзи показивач помера два чвора одједном, спори показивач помера само један по један чвор. Брзи показивач ће на крају престићи спори показивач ако листа садржи петљу, а две тачке ће се сударити у истом чвору.
   6. Функција позива функцију „делетеЛооп“ ако пронађе петљу, обезбеђујући главни чвор листе и пресек спорог и брзог показивача као улазе. Ова процедура успоставља два показивача, птр1 и птр2, на главни чвор листе и броји број чворова у петљи. Након тога, напредује за један показивач к чворова, где је к укупан број чворова у петљи. Затим, док се не сретну на почетку петље, она помера обе тачке један по чвор. Петља се затим прекида постављањем следећег показивача чвора на крају петље на НУЛЛ.
   7. Након уклањања петље, она приказује повезану листу као последњи корак.

Приступ 3: Рекурзија

Рекурзија је техника за решавање проблема тако што се они поделе на мање, лакше подпроблеме. Рекурзија се може користити за прелазак преко једноструко повезане листе у случају да се петља пронађе континуираним покретањем функције за следећи чвор на листи све док се не достигне крај листе.

У једноструко повезаној листи, основни принцип коришћења рекурзије за проналажење петље је да почнете на челу листе, означите тренутни чвор као посећен у сваком кораку, а затим пређете на следећи чвор рекурзивним позивањем функције за тај чвор. Метода ће се понављати преко целе повезане листе јер се позива рекурзивно.

Листа садржи петљу ако функција наиђе на чвор који је претходно био означен као посећен; у овом случају, функција може да врати труе. Метод може да врати фалсе ако дође до краја листе без преласка преко посећеног чвора, што указује да не постоји петља.

Иако је ова техника за коришћење рекурзије за проналажење петље у једној повезаној листи једноставна за коришћење и разумевање, можда није најефикаснија у смислу временске и просторне сложености.

Имплементација Ц++ програма за горњи метод (рекурзија):

Излаз:

Објашњење:

1. 1. Функција детектујеЛоопЛинкедЛист() у овом програму прихвата главу повезане листе као улаз.
   2. Функција користи рекурзију за понављање преко повезане листе. Као основни случај за рекурзију, она почиње одређивањем да ли је тренутни чвор НУЛЛ. Ако је тако, метода враћа нетачно, што указује да не постоји петља.
   3. Затим се проверава вредност својства „посећено“ тренутног чвора да би се видело да ли је претходно посећено. Враћа тачно ако је посећена, што сугерише да је петља пронађена.
   4. Функција означава тренутни чвор као посећен ако је већ посећен променом његове особине „посетио“ у труе.
   5. Вредност посећене променљиве се затим проверава да би се видело да ли је тренутни чвор претходно посећен. Ако је раније коришћена, петља мора постојати, а функција враћа труе.
   6. На крају, функција позива себе са следећим чвором на листи пропуштањем хеадНоде->нект као аргумент. Рекурзивно , ово се изводи све док се не пронађе петља или док се не посете сви чворови. Значи, функција поставља посећену променљиву на тачно ако тренутни чвор никада није посећен пре него што је рекурзивно позвала себе за следећи чвор на повезаној листи.
   7. Код гради три чвора и спаја их да би произвео повезану листу у основна функција . Метода детектујеЛоопЛинкедЛист() се затим позива на главни чвор листе. Програм производи „ Петља је одузета у повезаној листи ' ако детектујеЛоопЛинкедЛист() враћа труе; у супротном, излази „ На повезаној листи није откривена петља “.
   8. Код затим убацује петљу у повезану листу постављањем следећег показивача последњег чвора на други чвор. Затим, у зависности од исхода функције, она се покреће детектујеЛоопЛинкедЛист() поново и производи или ' Петља је одузета у повезаној листи ” или “ На повезаној листи није откривена петља .”

Приступ 4: Коришћење стека

Петље у повезаној листи могу се пронаћи помоћу стека и методе „претраге у дубину“ (ДФС). Основни концепт је итерација кроз повезану листу, гурајући сваки чвор у стек ако већ није посећен. Петља се препознаје ако се поново наиђе на чвор који је већ на стеку.

Ево кратког описа процедуре:

1. 1. Креирајте празан стек и променљиву за снимање чворова који су посећени.
   2. Гурните повезану листу на стог, почевши од врха. Забележите да је глава посећена.
   3. Гурните следећи чвор на листи на стек. Додајте ознаку посете овом чвору.
   4. Док прелазите преко листе, гурните сваки нови чвор на стек да бисте показали да је посећен.
   5. Проверите да ли је чвор који је претходно посећен на врху стека ако се наиђе. Ако јесте, петља је пронађена, а петља је идентификована чворовима у стеку.
   6. Уклоните чворове са стека и наставите да прелазите преко листе ако није пронађена петља.

Имплементација Ц++ програма за горњи метод (Стацк)

Излаз:

Објашњење:

Овај програм користи стек да открије да ли једноструко повезана листа има петљу.

• 1. Библиотека улазно/излазног тока и библиотека стека су обе присутне у првом реду.

  2. Стандардни простор имена је укључен у други ред, омогућавајући нам да приступимо функцијама библиотеке улазно/излазног тока без потребе да им додамо префикс са „стд::“.

  3. Следећи ред дефинише чвор структуре, који се састоји од два члана: целог броја који се зове „подаци“ и показивача на други чвор који се зове „следећи“.

  4. Глава повезане листе је улаз за метод детектујеЛоопЛинкедЛист(), који је дефинисан у следећем реду. Функција производи логичку вредност која показује да ли је петља пронађена или не.

  5. Стог показивача чвора који се зове „стацк“ и показивач на чвор под називом „темпНоде“ који је иницијализован вредношћу хеадНоде-а се креирају унутар функције.

  6. Затим, све док темпНоде није нулти показивач, улазимо у вхиле петљу.

  (а) Горњи елемент стека мора да одговара тренутном чвору да бисмо утврдили да није празан. Враћамо труе ако је то случај јер је петља пронађена.

  (б) Ако је горе поменути услов нетачан, показивач тренутног чвора се гура на стек, а темпНоде се поставља на следећи чвор на повезаној листи.

  7. Враћамо фалсе после вхиле петље јер није примећена петља.

  8. Правимо три Ноде објекта и иницијализујемо их у функцији маин(). Пошто у првом примеру нема петље, исправно смо поставили „следеће“ показиваче сваког чвора.

Закључак:

У закључку, најбољи метод за откривање петљи у повезаној листи зависи од специфичног случаја употребе и ограничења проблема. Хаш табела и Флојдов алгоритам за проналажење циклуса су ефикасне методе и широко се користе у пракси. Стацк и рекурзија су мање ефикасне методе, али су интуитивније.