C++'da Bağlantılı Listede Döngü Algılama

Döngüye sahip bağlantılı bir listenin son düğümü, NULL yerine aynı listedeki başka bir düğüme atıfta bulunacaktır. Bağlantılı bir listede, bir sonraki işaretçiyi izleyerek tekrar tekrar erişilebilen bir düğüm varsa, listeye denir. döngüsü var.

Tipik olarak, Bağlantılı Listenin son düğümü, listenin sonucunu belirtmek için bir NULL referansına atıfta bulunur. Ancak, döngü içeren bağlantılı bir listede, listenin son düğümü bir başlangıç ​​düğümüne, dahili bir düğüme veya kendisine atıfta bulunur. Bu nedenle, bu gibi durumlarda, sonraki düğümün referansını NULL olarak ayarlayarak döngüyü tanımlamalı ve sonlandırmalıyız. Bağlantılı bir listedeki döngünün algılama kısmı bu makalede açıklanmaktadır.

C++'da bağlantılı bir listede döngüler bulmanın çok sayıda yolu vardır:

Karma tablo tabanlı yaklaşım : Bu yaklaşım, ziyaret edilen düğümlerin adreslerini bir karma tabloda saklar. Bağlantılı listede bir döngü, yeniden ziyaret edildiğinde hash tablosunda zaten bir düğüm varsa mevcut demektir.

Floyd'un döngü yaklaşımı : Yaygın olarak Floyd'un döngü bulma algoritması olarak bilinen 'kaplumbağa ve tavşan' algoritması: Bu teknik, biri diğerinden daha yavaş hareket eden ve diğeri daha hızlı hareket eden iki işaretçi kullanır. Bağlantılı listede döngünün varlığını ortaya çıkaran bir döngü varsa, daha hızlı işaretçi nihayetinde daha yavaş işaretçiyi geçecek.

özyinelemeli yöntem : Bu metot kendisini tekrar tekrar çağırarak bağlantılı listeyi gözden geçirir. Mevcut düğüm daha önce ziyaret edilmişse bağlantılı liste bir döngü içerir.

Yığın tabanlı yaklaşım : Bu yaklaşım, ziyaret edilen düğümlerin adreslerini bir yığında saklar. Tekrar ziyaret edildiğinde yığında zaten bir düğüm varsa, bağlantılı listedeki bir döngü mevcuttur.

Konsepti anlamak için her yaklaşımı ayrıntılı olarak açıklayalım.

Yaklaşım 1: HashSet Yaklaşımı

Karma kullanmak en basit yöntemdir. Burada, düğüm adresleriyle bir hash tablosu tutarken listeyi tek tek inceliyoruz. Bu nedenle, halihazırda hash tablosunda bulunan mevcut düğümün bir sonraki adresi üzerinden geçersek bir döngü oluşur. Aksi takdirde, NULL ile karşılaşırsak (yani, Bağlantılı Liste'nin sonuna ulaşırsak) Bağlantılı Listede döngü olmaz.

Bu stratejiyi uygulamak oldukça kolay olacaktır.

Bağlantılı listede gezinirken, bir unordered_hashmap kullanacağız ve ona düğümler eklemeye devam edeceğiz.

Şimdi, haritada zaten gösterilen bir düğümle karşılaştığımızda, döngünün başlangıcına geldiğimizi bileceğiz.

• • Ek olarak, her adımda iki işaretçi tuttuk, kafa Düğümü geçerli düğümü işaret ederek ve son Düğüm yineleme yaparken geçerli düğümün önceki düğümünü işaret ediyor.
  • bizim gibi kafa Düğümü şimdi döngünün başlangıç ​​düğümünü işaret ediyor ve son Düğüm başın işaret ettiği düğümü işaret ediyordu (yani, son Düğüm döngü), bizim kafa Düğümü şu anda döngünün başlangıç ​​düğümünü işaret ediyor.
  • Döngü, l ayarlanarak kırılacaktır. astNode->sonraki == BOŞ .

Bunu yaparak, döngünün ilk düğümüne başvurmak yerine biten döngü düğümü NULL'u göstermeye başlar.

Karma yönteminin ortalama zaman ve alan karmaşıklığı O(n)'dir. Okuyucu, yerleşik Hashing DataStructure'ın programlama dilinde uygulanmasının, karma oluşturmada bir çarpışma olması durumunda toplam zaman karmaşıklığını belirleyeceğinin her zaman farkında olmalıdır.

Yukarıdaki yöntem için C++ program uygulaması (HashSet):

Çıktı:

Kodun adım adım açıklaması aşağıda verilmiştir:

1. 1. Tüm ortak C++ kitaplıklarını içeren bits/stdc++.h> başlık dosyası koda dahil edilmiştir.
   2. 'Düğüm' adlı bir yapı oluşturulur ve iki üyesi vardır: listedeki bir sonraki düğüme referans ve 'değer' adı verilen bir tamsayı.
   3. Girişi olarak bir tamsayı değeri ve NULL olarak ayarlanan 'sonraki' işaretçi ile, 'newNode' işlevi bu değerle yeni bir düğüm oluşturur.
   4. İşlev ' functionHashMap' bağlantılı listenin baş düğümüne bir işaretçiyi girdi olarak alan tanımlanır.
   5. İçinde ' işlevHashMap ' işlevi, bir karma harita veri yapısı uygulamak için kullanılan 'hash_map' adlı bir unordered_map oluşturulur.
   6. Listenin son düğümüne bir işaretçi NULL olarak başlatılır.
   7. Ana düğümden başlayan ve ana düğüm NULL olana kadar devam eden bağlantılı listede gezinmek için bir while döngüsü kullanılır.
   8. Geçerli düğüm (headNode) hash haritasında mevcut değilse, lastNode işaretçisi while döngüsü içindeki geçerli düğüme güncellenir.
   9. Geçerli düğüm haritada bulunursa, bağlantılı listede bir döngü olduğu anlamına gelir. Döngüyü kaldırmak için, döngünün bir sonraki işaretçisi son Düğüm ayarlandı HÜKÜMSÜZ ve while döngüsü bozulur.
   10. Bağlantılı listenin ana düğümü, listedeki her bir düğümün değerini baştan sona veren 'göster' adlı bir işlev için girdi olarak kullanılır.
   11. İçinde ana işlev, bir döngü oluşturma.
   12. 'functionHashMap' işlevi, döngüyü listeden kaldıran girdi olarak headNode işaretçisiyle çağrılır.
   13. Değiştirilen liste, 'göster' işlevi kullanılarak görüntülenir.

Yaklaşım 2: Floyd Döngüsü

Genellikle kaplumbağa ve tavşan algoritması olarak bilinen Floyd'un döngü algılama algoritması, döngüleri bağlantılı bir listede bulma yönteminin temelini oluşturur. Listede çeşitli hızlarda dolaşan 'yavaş' işaretçi ve 'hızlı' işaretçi, bu teknikte kullanılan iki işaretçidir. Hızlı işaretçi iki adım ilerlerken, yavaş işaretçi her yinelemede bir adım ilerler. İki nokta karşı karşıya gelirse, bağlantılı listede bir döngü vardır.

1. Bağlantılı listenin baş düğümü ile hızlı ve yavaş olarak adlandırılan iki işaretçiyi başlatıyoruz.

2. Şimdi bağlantılı listede ilerlemek için bir döngü çalıştırıyoruz. Hızlı işaretçi, her yineleme adımında yavaş işaretçinin önünde iki konuma taşınmalıdır.

3. Hızlı işaretçi listenin sonuna ulaşırsa (fastPointer == NULL veya fastPointer->next == NULL) bağlantılı listede bir döngü olmayacaktır. Değilse, hızlı ve yavaş işaretçiler sonunda buluşacak, bu da bağlantılı listenin bir döngüsü olduğu anlamına gelir.

Yukarıdaki yöntem için C++ program uygulaması (Floyd's Cycle):

Çıktı:

Açıklama:

1. 1. Önce 'bits/stdc++.h' ve 'std::cout' gibi ilgili başlıklar dahil edilir.
   2. Bağlantılı listede bir düğümü temsil eden “Node” yapısı daha sonra bildirilir. Listede bir sonraki düğüme götüren bir sonraki işaretçi, her düğümde bir tamsayı veri alanıyla birlikte dahil edilir.
   3. Ardından, 'deleteLoop' ve 'detectAndDeleteLoop' adlı iki işlevi tanımlar. İlk yöntem kullanılarak bağlantılı bir listeden bir döngü kaldırılır ve ikinci işlev kullanılarak listede bir döngü algılanır ve ardından döngüyü kaldırmak için ilk yordamı çağırır.
   4. Ana fonksiyonda beş düğümlü yeni bir bağlantılı liste oluşturulur ve son düğümün bir sonraki işaretçisi üçüncü düğüme ayarlanarak bir döngü oluşturulur.
   5. Daha sonra bağlantılı listenin baş düğümünü argüman olarak geçirirken “detectAndDeleteLoop” metoduna çağrı yapar. Döngüleri tanımlamak için bu işlev 'Yavaş ve Hızlı İşaretçiler' yaklaşımını kullanır. Listenin en üstünde başlayan iki işaretçi kullanır, yavaşPTR ve hızlıPTR. Hızlı işaretçi aynı anda iki düğümü hareket ettirirken, yavaş işaretçi her seferinde yalnızca bir düğümü hareket ettirir. Liste bir döngü içeriyorsa, hızlı işaretçi eninde sonunda yavaş işaretçiyi geçecek ve iki nokta aynı düğümde çarpışacak.
   6. İşlev, listenin baş düğümünü ve yavaş ve hızlı işaretçilerin kesişimini girdi olarak sağlayan bir döngü bulursa 'deleteLoop' işlevini çağırır. Bu prosedür, listenin ana düğümüne ptr1 ve ptr2 olmak üzere iki işaretçi kurar ve döngüdeki düğüm sayısını sayar. Bunu takiben, bir işaretçi k ​​düğümü ilerletir; burada k, döngüdeki toplam düğüm sayısıdır. Ardından, döngünün başlangıcında buluşana kadar her iki noktayı da birer birer ilerletir. Döngü daha sonra döngünün sonundaki düğümün bir sonraki işaretçisini NULL olarak ayarlayarak bozulur.
   7. Döngüyü kaldırdıktan sonra, son adım olarak bağlantılı listeyi görüntüler.

Yaklaşım 3: Özyineleme

Özyineleme, sorunları daha küçük, daha kolay alt problemlere bölerek çözmek için kullanılan bir tekniktir. Listenin sonuna ulaşılana kadar listedeki bir sonraki düğüm için sürekli bir işlev çalıştırılarak bir döngü bulunması durumunda tek bağlantılı bir listeyi geçmek için özyineleme kullanılabilir.

Tek bağlantılı bir listede, bir döngü bulmak için özyinelemeyi kullanmanın ardındaki temel ilke, listenin başından başlamak, mevcut düğümü her adımda ziyaret edildiği gibi işaretlemek ve ardından yinelemeli olarak for işlevini çağırarak bir sonraki düğüme gitmektir. o düğüm Yöntem, yinelemeli olarak çağrıldığından, tam bağlantılı liste üzerinde yinelenir.

İşlev tarafından daha önce ziyaret edildi olarak işaretlenmiş bir düğümle karşılaşılırsa, liste bir döngü içerir; bu durumda işlev true değerini döndürebilir. Yöntem, ziyaret edilen bir düğümde çalışmadan listenin sonuna ulaşırsa, döngü olmadığını gösteren false döndürebilir.

Tek bir bağlantılı listede bir döngü bulmak için özyinelemeyi kullanan bu tekniğin kullanımı ve kavranması basit olsa da, zaman ve mekan karmaşıklığı açısından en etkili teknik olmayabilir.

Yukarıdaki yöntem için C++ program uygulaması (Yineleme):

Çıktı:

Açıklama:

1. 1. İşlev DetectLoopLinkedList() bu programda bağlantılı listenin başını girdi olarak kabul eder.
   2. Özyineleme, işlev tarafından bağlantılı listede yineleme yapmak için kullanılır. Özyineleme için temel durum olarak, geçerli düğümün NULL olup olmadığını belirleyerek başlar. Eğer öyleyse, yöntem false döndürür ve döngü olmadığını belirtir.
   3. Geçerli düğümün 'ziyaret edilen' özelliğinin değeri, daha önce ziyaret edilip edilmediğini görmek için kontrol edilir. Ziyaret edilmişse, bir döngü bulunduğunu öne sürerek true değerini döndürür.
   4. İşlev, 'ziyaret edilen' özelliğini true olarak değiştirerek zaten ziyaret edilmişse, geçerli düğümü ziyaret edilmiş olarak işaretler.
   5. Ziyaret edilen değişkenin değeri daha sonra mevcut düğümün daha önce ziyaret edilip edilmediğini görmek için kontrol edilir. Daha önce kullanılmışsa, bir döngü olmalıdır ve işlev true değerini döndürür.
   6. Son olarak işlev kendisini listedeki bir sonraki düğüme geçerek çağırır. headNode->sonraki bir argüman olarak. Tekrarlı , bu, bir döngü bulunana veya tüm düğümler ziyaret edilene kadar gerçekleştirilir. Şu anlama gelir: Geçerli düğüm, bağlantılı listede kendisini takip eden düğüm için yinelemeli olarak çağırmadan önce hiç ziyaret edilmemişse, işlev ziyaret edilen değişkeni true olarak ayarlar.
   7. Kod, üç düğüm oluşturur ve bunları bir bağlantılı liste oluşturmak için birleştirir. ana işlev . yöntem DetectLoopLinkedList() daha sonra listenin baş düğümünde çağrılır. program üretir ' Bağlantılı listede döngü çıkarıldı ' eğer DetectLoopLinkedList() doğru döndürür; aksi takdirde, ' Bağlantılı listede döngü algılanmadı “.
   8. Kod daha sonra, son düğümün sonraki işaretçisini ikinci düğüme ayarlayarak bağlantılı listeye bir döngü ekler. Ardından, işlevin sonucuna bağlı olarak çalışır DetectLoopLinkedList() tekrar ve üretir ya “ Bağlantılı listede döngü çıkarıldı ' veya ' Bağlantılı listede döngü algılanmadı ”

Yaklaşım 4: Yığın Kullanma

Bağlantılı bir listedeki döngüler, bir yığın ve 'önce derinlik arama' (DFS) yöntemi kullanılarak bulunabilir. Temel kavram, bağlantılı listeyi yineleyerek, daha önce ziyaret edilmemişse her düğümü yığına itmektir. Zaten yığında olan bir düğümle tekrar karşılaşılırsa bir döngü tanınır.

İşte prosedürün kısa bir açıklaması:

1. 1. Ziyaret edilen düğümleri kaydetmek için boş bir yığın ve bir değişken oluşturun.
   2. Bağlantılı listeyi en baştan başlayarak yığının üzerine itin. Başın ziyaret edildiğini not edin.
   3. Listedeki bir sonraki düğümü yığına itin. Bu düğüme bir ziyaret işareti ekleyin.
   4. Listede gezinirken, ziyaret edildiğini belirtmek için her yeni düğümü yığına itin.
   5. Daha önce ziyaret edilmiş bir düğümle karşılaşıldığında yığının en üstünde olup olmadığını kontrol edin. Öyleyse, bir döngü bulunmuştur ve döngü, yığındaki düğümler tarafından tanımlanır.
   6. Düğümleri yığından çıkarın ve döngü bulunmazsa listede gezinmeye devam edin.

Yukarıdaki yöntem için C++ program uygulaması (Yığın)

Çıktı:

Açıklama:

Bu program, tek başına bağlantılı bir listenin bir döngüye sahip olup olmadığını öğrenmek için bir yığın kullanır.

• 1. Giriş/çıkış akış kitaplığı ve yığın kitaplığının her ikisi de ilk satırda bulunur.

  2. Standart ad alanı ikinci satırda yer alır ve girdi/çıktı akışı kitaplığının işlevlerine 'std::' öneki koymadan erişmemize olanak tanır.

  3. Aşağıdaki satır, iki üyeden oluşan yapı Düğümünü tanımlar: 'data' adlı bir tamsayı ve 'sonraki' adlı başka bir Düğüme işaretçi.

  4. Bağlantılı listenin başı, bir sonraki satırda tanımlanan DetectLoopLinkedList() yöntemi için bir girdidir. İşlev, bir döngünün bulunup bulunmadığını gösteren bir boole değeri üretir.

  5. İşlevin içinde 'yığın' adı verilen bir Düğüm işaretçileri yığını ve 'tempNode' adlı bir Düğüme işaret eden ve headNode'un değeriyle başlatılan bir işaretçi oluşturulur.

  6. Daha sonra tempNode bir null işaretçisi olmadığı sürece bir while döngüsüne giriyoruz.

  (a) Yığının boş olmadığını belirleyebilmemiz için, yığının en üstteki elemanı mevcut düğümle eşleşmelidir. Bir döngü bulunduğu için durum buysa true döndürürüz.

  (b) Yukarıda belirtilen koşul yanlışsa, geçerli düğüm işaretçisi yığına itilir ve tempNode, bağlantılı listede bir sonraki düğüme ayarlanır.

  7. Döngü gözlemlenmediği için while döngüsünden sonra false döndürürüz.

  8. Üç Düğüm nesnesi oluşturuyoruz ve bunları main() işlevinde başlatıyoruz. İlk örnekte döngü olmadığı için her Düğümün “sonraki” işaretçilerini uygun şekilde ayarlıyoruz.

Çözüm:

Sonuç olarak, bağlantılı bir listedeki döngüleri tespit etmenin en iyi yöntemi, belirli kullanım durumuna ve sorunun kısıtlamalarına bağlıdır. Hash Table ve Floyd'un döngü bulma algoritması etkili yöntemlerdir ve pratikte yaygın olarak kullanılmaktadır. Yığın ve özyineleme daha az verimli yöntemlerdir ancak daha sezgiseldirler.