Adakah Algoritma Pencarian Kitaran Floyd Berkesan Mengesan Gelung dalam Senarai Terpaut?

Mengesan Gelung dalam Senarai Terpaut menggunakan Algoritma Pencarian Kitaran Floyd

Senarai terpaut, struktur data asas dalam sains komputer, sering digunakan untuk mewakili jujukan elemen. Dalam senario tertentu, senarai terpaut mungkin mengandungi gelung, di mana nod terakhir menghala kembali ke nod sebelumnya, mewujudkan struktur bulat. Mengenal pasti kehadiran gelung sedemikian adalah tugas penting untuk pelbagai operasi yang melibatkan senarai terpaut.

Algoritma Pencarian Kitaran Floyd

Algoritma pencarian kitaran Floyd, juga dikenali sebagai algoritma kura-kura dan arnab, menyediakan cara yang cekap untuk mengesan gelung dalam senarai terpaut. Algoritma beroperasi berdasarkan prinsip menggerakkan dua penunjuk (rujukan) pada kelajuan berbeza melalui senarai:

1. Kura-kura (Penunjuk Perlahan): Bergerak ke hadapan satu nod pada satu masa.
2. Hare (Penunjuk Pantas): Bergerak ke hadapan dua nod pada satu masa.

Prinsip:

• Hadir Gelung: Jika terdapat gelung dalam senarai, kura-kura dan arnab akhirnya akan bertemu pada nod yang sama, menunjukkan kehadiran gelung.
• Tiada Gelung : Jika senarai tidak mengandungi gelung, sama ada kura-kura atau arnab akan sampai ke penghujung senarai (penunjuk nol), menandakan ketiadaan gelung.

Pelaksanaan Java

Fungsi Java berikut melaksanakan algoritma pencarian kitaran Floyd:

<code class="java">boolean hasLoop(Node first) {

    if(first == null) // list does not exist..so no loop either
        return false;

    Node slow, fast; // create two references.

    slow = fast = first; // make both refer to the start of the list

    while(true) {

        slow = slow.next;          // 1 hop

        if(fast.next != null)
            fast = fast.next.next; // 2 hops
        else
            return false;          // next node null => no loop

        if(slow == null || fast == null) // if either hits null..no loop
            return false;

        if(slow == fast) // if the two ever meet...we must have a loop
            return true;
    }
}</code>

Kelebihan

Algoritma pencarian kitaran Floyd menawarkan kelebihan berikut:

• Kerumitan Ruang Malar: Ia hanya memerlukan dua penuding (rujukan), menjadikan kerumitan ruangnya malar (O(1)).
• Kerumitan Masa Linear: The kerumitan masa algoritma ialah O(n), dengan n ialah bilangan nod dalam senarai terpaut.

Atas ialah kandungan terperinci Adakah Algoritma Pencarian Kitaran Floyd Berkesan Mengesan Gelung dalam Senarai Terpaut?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!