Nod akhir senarai terpaut yang mempunyai gelung akan merujuk kepada nod lain dalam senarai yang sama dan bukannya NULL. Jika terdapat nod dalam senarai terpaut yang boleh diakses berulang kali dengan mengikut penuding seterusnya, senarai itu dikatakan mempunyai kitaran.
Biasanya, nod terakhir Senarai Terpaut merujuk kepada rujukan NULL untuk menandakan kesimpulan senarai. Walau bagaimanapun, dalam senarai terpaut dengan gelung, nod akhir senarai merujuk kepada nod permulaan, nod dalaman atau dirinya sendiri. Oleh itu, dalam keadaan sedemikian, kita mesti mengenal pasti dan menamatkan gelung dengan menetapkan rujukan nod seterusnya kepada NULL. Bahagian pengesanan gelung dalam senarai terpaut diterangkan dalam artikel ini.
Dalam C++, terdapat banyak cara untuk mencari gelung dalam senarai terpaut:
Pendekatan berasaskan jadual hash : Pendekatan ini menyimpan alamat nod yang dilawati dalam jadual cincang. Gelung dalam senarai terpaut wujud jika nod sudah ada dalam jadual cincang apabila ia dilawati semula.
Pendekatan kitaran Floyd : Algoritma 'kura-kura dan arnab', biasanya dikenali sebagai algoritma pencarian kitaran Floyd: Teknik ini menggunakan dua penunjuk, satu bergerak lebih perlahan daripada yang lain dan satu lagi bergerak lebih cepat. Penunjuk yang lebih pantas akhirnya akan mengatasi penuding yang lebih perlahan jika terdapat gelung dalam senarai terpaut, mendedahkan kewujudan gelung.
Kaedah rekursif : Kaedah ini melalui senarai terpaut dengan memanggil dirinya berulang kali. Senarai terpaut mengandungi gelung jika nod semasa telah dilawati sebelum ini.
Pendekatan berasaskan timbunan : Pendekatan ini menyimpan alamat nod yang dilawati dalam timbunan. Gelung dalam senarai terpaut hadir jika nod sudah ada dalam tindanan apabila ia dilawati semula.
Mari jelaskan setiap pendekatan secara terperinci untuk memahami konsep.
Pendekatan 1: Pendekatan HashSet
Menggunakan pencincangan adalah kaedah yang paling mudah. Di sini, kami meneliti senarai satu demi satu sambil menyimpan jadual cincang dengan alamat nod. Oleh itu, gelung wujud jika kita pernah merentasi alamat seterusnya nod semasa yang sudah terkandung dalam jadual cincang. Jika tidak, tiada gelung dalam Senarai Terpaut jika kita menghadapi NULL (iaitu, mencapai penghujung Senarai Terpaut).
Ia akan menjadi agak mudah untuk melaksanakan strategi ini.
Semasa merentasi senarai terpaut, kami akan menggunakan unordered_hashmap dan terus menambah nod padanya.
Sekarang, sebaik sahaja kita menjumpai nod yang telah ditunjukkan dalam peta, kita akan tahu bahawa kita telah tiba di permulaan gelung.
-
- Di samping itu, kami menyimpan dua penunjuk pada setiap langkah, headNode menunjuk ke nod semasa dan lastNode menunjuk ke nod sebelumnya nod semasa, sambil lelaran.
- Sebagai kami headNode kini menunjuk ke nod permulaan gelung dan sebagai lastNode sedang menunjuk ke nod yang ditunjuk oleh kepala (iaitu, ia merujuk kepada lastNode daripada gelung), kami headNode sedang menunjuk ke nod permulaan gelung.
- Gelung akan dipecahkan dengan menetapkan l astNode->next == NULL .
Dengan melakukan ini, nod gelung berakhir dan bukannya merujuk kepada nod awal gelung, mula menunjuk ke NULL.
Purata masa dan kerumitan ruang kaedah pencincangan ialah O(n). Pembaca harus sentiasa sedar bahawa pelaksanaan Struktur Data Hashing terbina dalam dalam bahasa pengaturcaraan akan menentukan jumlah kerumitan masa sekiranya berlaku perlanggaran dalam pencincangan.
Pelaksanaan program C++ untuk kaedah di atas (HashSet):
#include
menggunakan ruang nama std;
struct Nod {
nilai int;
struct Nod * seterusnya;
} ;
Nod * newNode ( nilai int )
{
Nod * tempNode = Nod baharu;
tempNode- > nilai = nilai;
tempNode- > seterusnya = NULL;
kembali tempNode;
}
// Kenal pasti dan hapuskan sebarang kemungkinan gelung
// dalam senarai terpaut dengan fungsi ini.
void functionHashMap ( Nod * headNode )
{
// Mencipta unordered_map untuk melaksanakan peta Hash
peta_tak tersusun < Nod * , int > hash_map;
// penunjuk ke lastNode
Nod * lastNode = NULL;
sementara ( headNode ! = NULL ) {
// Jika nod tiada daripada peta, tambahkannya.
jika ( hash_map.cari ( headNode ) == hash_map.end ( ) ) {
hash_map [ headNode ] ++;
lastNode = headNode;
headNode = headNode- > seterusnya;
}
// Jika ada kitaran, ditetapkan nod akhir Penunjuk seterusnya kepada NULL.
lain {
lastNode->next = NULL;
pecah;
}
}
}
// Paparkan senarai terpaut
paparan kosong (Nod* headNode)
{
manakala (headNode != NULL) {
cout << headNod->nilai << ' ';
headNode = headNode->next;
}
cout << endl;
}
/* Fungsi utama*/
int utama()
{
Nod* headNode = newNode(48);
headNode->next = headNode;
headNode->next = newNode(18);
headNode->next->next = newNode(13);
headNode->next->next->next = newNode(2);
headNode->next->next->next->next = newNode(8);
/* Buat gelung dalam linkedList */
headNode->next->next->next->next->next = headNode->next->next;
functionHashMap(headNode);
printf('Senarai Terpaut tanpa gelung \n');
paparan(headNode);
pulangan 0;
}
Pengeluaran:
Senarai Terpaut tanpa gelung
48 18 13 2 8
Penjelasan langkah demi langkah kod disediakan di bawah:
-
- Fail pengepala bits/stdc++.h>, yang mengandungi semua perpustakaan C++ biasa, disertakan dalam kod.
- Struktur yang dipanggil 'Nod' dibina, dan ia mempunyai dua ahli: rujukan kepada nod seterusnya dalam senarai dan integer dipanggil 'nilai.'
- Dengan nilai integer sebagai inputnya dan penunjuk 'seterusnya' ditetapkan kepada NULL, fungsi 'newNode' mencipta nod baharu dengan nilai tersebut.
- Fungsinya ' functionHashMap' ditakrifkan, yang mengambil penuding ke nod kepala senarai terpaut sebagai input.
- Di dalam ' functionHashMap ' fungsi, unordered_map bernama 'hash_map' dicipta, yang digunakan untuk melaksanakan struktur data peta hash.
- Penunjuk ke nod terakhir senarai dimulakan kepada NULL.
- Gelung sementara digunakan untuk melintasi senarai terpaut, yang bermula dari nod kepala dan berterusan sehingga nod kepala adalah NULL.
- Penunjuk lastNode dikemas kini kepada nod semasa di dalam gelung while jika nod semasa (headNode) belum ada dalam peta cincang.
- Jika nod semasa ditemui dalam peta, ini bermakna gelung hadir dalam senarai terpaut. Untuk mengalih keluar gelung, penunjuk seterusnya bagi lastNode ditetapkan kepada NULL dan gelung while patah.
- Nod kepala senarai terpaut digunakan sebagai input untuk fungsi yang dipanggil 'paparan', yang mengeluarkan nilai setiap nod dalam senarai dari awal hingga akhir.
- Di dalam utama fungsi, mencipta gelung.
- Fungsi 'functionHashMap' dipanggil dengan penuding headNode sebagai input, yang mengalih keluar gelung daripada senarai.
- Senarai yang diubah suai dipaparkan menggunakan fungsi 'paparan'.
Pendekatan 2: Kitaran Floyd
Algoritma pengesanan kitaran Floyd, sering dikenali sebagai algoritma kura-kura dan arnab, menyediakan asas untuk kaedah mencari kitaran dalam senarai terpaut ini. Penunjuk 'perlahan' dan penunjuk 'cepat', yang melintasi senarai pada pelbagai kelajuan, ialah dua penunjuk yang digunakan dalam teknik ini. Penunjuk pantas memajukan dua langkah manakala penuding perlahan mendahului satu langkah setiap lelaran. Kitaran dalam senarai terpaut wujud jika kedua-dua titik itu pernah bersemuka.
1. Dengan nod kepala senarai terpaut, kami memulakan dua penunjuk yang dipanggil cepat dan perlahan.
2. Sekarang kita menjalankan gelung untuk bergerak melalui senarai terpaut. Penunjuk pantas harus dialihkan dua lokasi di hadapan penuding perlahan pada setiap langkah lelaran.
3. Tidak akan ada gelung dalam senarai terpaut jika penuding pantas mencapai penghujung senarai (fastPointer == NULL atau fastPointer->next == NULL). Jika tidak, penunjuk cepat dan perlahan akhirnya akan bertemu, yang bermaksud senarai terpaut mempunyai gelung.
Pelaksanaan program C++ untuk kaedah di atas (Kitaran Floyd):
#include
menggunakan ruang nama std;
/* Nod senarai pautan */
struct Nod {
data int;
struct Nod * seterusnya;
} ;
/* Berfungsi untuk mengeluarkan gelung. */
batal deleteLoop ( struct Nod * , struct Node * ) ;
/* ini fungsi mencari dan menghapuskan gelung senarai. Ia membuahkan hasil 1
jika terdapat gelung dalam senarai; lain , ia kembali 0 . */
int detectAndDeleteLoop ( struct Nod * senarai )
{
struct Nod * slowPTR = senarai, * fastPTR = senarai;
// Ulang untuk menyemak jika gelung itu ada.
sementara ( slowPTR && cepatPTR && cepatPTR- > seterusnya ) {
slowPTR = slowPTR- > seterusnya;
cepatPTR = cepatPTR- > seterusnya- > seterusnya;
/* Jika slowPTR dan fastPTR bertemu pada satu ketika kemudian di sana
ialah gelung */
jika ( slowPTR == fastPTR ) {
deleteLoop ( slowPTR, senarai ) ;
/* Kembali 1 untuk menunjukkan bahawa gelung telah ditemui. */
kembali 1 ;
}
}
/* Kembali 0 untuk menunjukkan bahawa tiada gelung telah ditemui. */
kembali 0 ;
}
/* Berfungsi untuk memadam gelung daripada senarai terpaut.
loopNode menunjuk ke salah satu nod gelung dan headNode menunjuk
ke nod permulaan senarai terpaut */
batal deleteLoop ( struct Nod * loopNode, struct Node * headNode )
{
struct Nod * ptr1 = loopNode;
struct Nod * ptr2 = loopNode;
// Kira berapa banyak nod dalam gelung.
unsigned int k = 1 , i;
sementara ( ptr1- > seterusnya ! = ptr2 ) {
ptr1 = ptr1- > seterusnya;
k++;
}
// Betulkan satu penunjuk ke headNode
ptr1 = headNod;
// Dan penunjuk lain kepada k nod selepas headNode
ptr2 = headNod;
untuk ( i = 0 ; i < k; i++ )
ptr2 = ptr2- > seterusnya;
/* Apabila kedua-dua titik digerakkan secara serentak,
mereka akan berlanggar di gelung nod permulaan. */
manakala (ptr2 != ptr1) {
ptr1 = ptr1->seterusnya;
ptr2 = ptr2->seterusnya;
}
// Dapatkan nod' s terakhir penunjuk.
sementara ( ptr2- > seterusnya ! = ptr1 )
ptr2 = ptr2- > seterusnya;
/* Untuk menutup gelung, ditetapkan yang seterusnya
nod ke gelung nod penamat. */
ptr2->seterusnya = NULL;
}
/* Fungsi untuk memaparkan senarai terpaut */
void displayLinkedList(struct Node* nod)
{
// paparkan senarai terpaut selepas memadam gelung
manakala (nod != NULL) {
cout << nod->data << ' ';
nod = nod->next;
}
}
struct Node* newNode(int key)
{
struct Nod* temp = new Node();
temp->data = kunci;
temp->next = NULL;
suhu pulangan;
}
// Kod Utama
int utama()
{
struct Nod* headNode = newNode(48);
headNode->next = newNode(18);
headNode->next->next = newNode(13);
headNode->next->next->next = newNode(2);
headNode->next->next->next->next = newNode(8);
/* Buat gelung */
headNode->next->next->next->next->next = headNode->next->next;
// paparkan gelung dalam senarai terpaut
//displayLinkedList(headNode);
detectAndDeleteLoop(headNode);
cout << 'Senarai Terpaut selepas tiada gelung \n';
displayLinkedList(headNode);
pulangan 0;
}
Pengeluaran:
Senarai Terpaut selepas tiada gelung
48 18 13 2 8
Penjelasan:
-
- Pengepala yang berkaitan, seperti 'bits/stdc++.h' dan 'std::cout,' disertakan dahulu.
- Struktur 'Nod', yang bermaksud nod dalam senarai terpaut, kemudiannya diisytiharkan. Penunjuk seterusnya yang membawa kepada nod berikut dalam senarai disertakan bersama dengan medan data integer dalam setiap nod.
- Kemudian, ia mentakrifkan 'deleteLoop' dan 'detectAndDeleteLoop,' dua fungsi. Gelung dialih keluar daripada senarai terpaut menggunakan kaedah pertama, dan gelung dikesan dalam senarai menggunakan fungsi kedua, yang kemudiannya memanggil prosedur pertama untuk mengalih keluar gelung.
- Senarai terpaut baharu dengan lima nod dibuat dalam fungsi utama, dan gelung diwujudkan dengan menetapkan penuding seterusnya nod terakhir ke nod ketiga.
- Ia kemudian membuat panggilan ke kaedah 'detectAndDeleteLoop' sambil menghantar nod kepala senarai terpaut sebagai hujah. Untuk mengenal pasti gelung, fungsi ini menggunakan pendekatan 'Penunjuk Perlahan dan Pantas'. Ia menggunakan dua petunjuk yang bermula di bahagian atas senarai, slowPTR dan fastPTR. Walaupun penunjuk pantas menggerakkan dua nod serentak, penunjuk perlahan hanya menggerakkan satu nod pada satu masa. Penunjuk pantas akhirnya akan memintas penunjuk perlahan jika senarai mengandungi gelung, dan dua titik akan bertembung pada nod yang sama.
- Fungsi ini menggunakan fungsi 'deleteLoop' jika ia menjumpai gelung, membekalkan nod kepala senarai dan persilangan penunjuk perlahan dan pantas sebagai input. Prosedur ini menetapkan dua penunjuk, ptr1 dan ptr2, ke nod kepala senarai dan mengira bilangan nod dalam gelung. Selepas itu, ia memajukan satu nod k penuding, dengan k ialah jumlah bilangan nod dalam gelung. Kemudian, sehingga mereka bertemu pada permulaan gelung, ia memajukan kedua-dua mata satu nod pada satu masa. Gelung kemudiannya dipecahkan dengan menetapkan penuding seterusnya nod pada penghujung gelung kepada NULL.
- Selepas mengalih keluar gelung, ia memaparkan senarai terpaut sebagai langkah terakhir.
Pendekatan 3: Rekursi
Rekursi ialah teknik untuk menyelesaikan isu dengan membahagikannya kepada submasalah yang lebih kecil dan lebih mudah. Rekursi boleh digunakan untuk melintasi senarai terpaut tunggal sekiranya gelung ditemui dengan terus menjalankan fungsi untuk nod seterusnya dalam senarai sehingga penghujung senarai dicapai.
Dalam senarai terpaut tunggal, prinsip asas di sebalik penggunaan rekursi untuk mencari gelung ialah bermula di kepala senarai, tandai nod semasa sebagai dilawati pada setiap langkah, dan kemudian pergi ke nod seterusnya dengan menggunakan fungsi secara rekursif untuk nod itu. Kaedah ini akan berulang ke atas senarai pautan penuh kerana ia dipanggil secara rekursif.
Senarai mengandungi gelung jika nod yang sebelum ini telah ditandakan sebagai dilawati ditemui oleh fungsi; dalam kes ini, fungsi boleh kembali benar. Kaedah ini boleh mengembalikan palsu jika ia mencapai penghujung senarai tanpa berjalan merentasi nod yang dilawati, yang menunjukkan bahawa tiada gelung.
Walaupun teknik untuk menggunakan rekursi untuk mencari gelung dalam senarai terpaut tunggal adalah mudah untuk digunakan dan difahami, teknik ini mungkin bukan yang paling berkesan dari segi kerumitan masa dan ruang.
Pelaksanaan program C++ untuk kaedah di atas (Rekursi):
#include
menggunakan ruang nama std;
struct Nod {
data int;
Nod * seterusnya;
bool dilawati;
} ;
// Pengesanan gelung senarai terpaut fungsi
bool detectLoopLinkedList ( Nod * headNode ) {
jika ( headNode == NULL ) {
kembali salah ; // Jika senarai terpaut kosong, asasnya kes
}
// Terdapat gelung jika nod semasa mempunyai
// sudah dilawati.
jika ( headNode- > dilawati ) {
kembali benar ;
}
// Tambahkan tanda lawatan pada nod semasa.
headNode- > dilawati = benar ;
// Memanggil kod untuk nod seterusnya berulang kali
kembali detectLoopLinkedList ( headNode- > seterusnya ) ;
}
int utama ( ) {
Nod * headNode = Nod baharu ( ) ;
Nod * secondNode = Nod baharu ( ) ;
Nod * thirdNode = Nod baharu ( ) ;
headNode- > data = 1 ;
headNode- > seterusnya = secondNode;
headNode- > dilawati = salah ;
secondNode- > data = 2 ;
secondNode- > seterusnya = thirdNode;
secondNode- > dilawati = salah ;
thirdNode- > data = 3 ;
thirdNode- > seterusnya = NULL; // Tiada gelung
thirdNode- > dilawati = salah ;
jika ( detectLoopLinkedList ( headNode ) ) {
cout << 'Gelung dikesan dalam senarai terpaut' << endl;
} lain {
cout << 'Tiada gelung dikesan dalam senarai terpaut' << endl;
}
// Mencipta gelung
thirdNode- > seterusnya = secondNode;
jika ( detectLoopLinkedList ( headNode ) ) {
cout << 'Gelung dikesan dalam senarai terpaut' << endl;
} lain {
cout << 'Tiada gelung dikesan dalam senarai terpaut' << endl;
}
kembali 0 ;
}
Pengeluaran:
Tiada gelung dikesan dalam senarai terpaut
Gelung dikesan dalam senarai terpaut
Penjelasan:
-
- Fungsinya detectLoopLinkedList() dalam program ini menerima ketua senarai terpaut sebagai input.
- Rekursi digunakan oleh fungsi untuk lelaran merentasi senarai terpaut. Sebagai kes asas untuk rekursi, ia bermula dengan menentukan sama ada nod semasa adalah NULL. Jika ya, kaedah mengembalikan palsu, menunjukkan bahawa tiada gelung wujud.
- Nilai sifat 'dilawati' nod semasa kemudiannya diperiksa untuk melihat sama ada ia telah dilawati sebelum ini. Ia kembali benar jika ia telah dilawati, menunjukkan bahawa gelung telah ditemui.
- Fungsi ini menandakan nod semasa sebagai dilawati jika ia telah dilawati dengan menukar sifat 'dilawati' kepada benar.
- Nilai pembolehubah yang dilawati kemudiannya disemak untuk melihat sama ada nod semasa telah dilawati sebelum ini. Jika ia telah digunakan sebelum ini, gelung mesti wujud, dan fungsi itu kembali benar.
- Akhir sekali, fungsi memanggil dirinya dengan nod seterusnya dalam senarai dengan lulus headNode->seterusnya sebagai hujah. Secara rekursif , ini dijalankan sehingga sama ada gelung ditemui atau semua nod telah dilawati. Bermaksud, fungsi menetapkan pembolehubah yang dilawati kepada benar jika nod semasa tidak pernah dilawati sebelum secara rekursif memanggil dirinya sendiri untuk nod berikut dalam senarai terpaut.
- Kod membina tiga nod dan bergabung dengannya untuk menghasilkan senarai terpaut dalam fungsi utama . Cara detectLoopLinkedList() kemudiannya dipanggil pada nod kepala senarai. Program ini menghasilkan “ Gelung ditolak dalam senarai terpaut ” jika detectLoopLinkedList() kembali benar; jika tidak, ia mengeluarkan ' Tiada gelung dikesan dalam senarai terpaut “.
- Kod itu kemudian memasukkan gelung ke dalam senarai terpaut dengan menetapkan penuding seterusnya nod terakhir ke nod kedua. Kemudian, bergantung pada hasil fungsi, ia berjalan detectLoopLinkedList() sekali lagi dan menghasilkan sama ada ' Gelung ditolak dalam senarai terpaut ” atau “ Tiada gelung dikesan dalam senarai terpaut .”
Pendekatan 4: Menggunakan Stack
Gelung dalam senarai terpaut boleh didapati menggunakan timbunan dan kaedah 'carian pertama mendalam' (DFS). Konsep asas adalah untuk mengulangi senarai terpaut, menolak setiap nod ke dalam timbunan jika ia belum pernah dilawati. Gelung dikenali jika nod yang sudah ada pada timbunan ditemui semula.
Berikut adalah penerangan ringkas mengenai prosedur:
-
- Buat timbunan kosong dan pembolehubah untuk merekodkan nod yang telah dilawati.
- Tolak senarai terpaut ke tindanan, bermula dari bahagian atas. Buat nota bahawa ketua telah dilawati.
- Tolak nod seterusnya dalam senarai ke tindanan. Tambahkan tanda lawatan pada nod ini.
- Semasa anda melintasi senarai, tolak setiap nod baharu pada timbunan untuk menunjukkan bahawa ia telah dilawati.
- Semak untuk melihat sama ada nod yang telah dilawati sebelum ini berada di bahagian atas tindanan jika ia ditemui. Jika ya, gelung telah ditemui, dan gelung dikenal pasti oleh nod dalam timbunan.
- Keluarkan nod dari timbunan dan terus melintasi senarai jika tiada gelung ditemui.
Pelaksanaan program C++ untuk kaedah di atas (Timbunan)
#include
#include
menggunakan ruang nama std;
struct Nod {
data int;
Nod * seterusnya;
} ;
// Berfungsi untuk mengesan gelung dalam senarai terpaut
bool detectLoopLinkedList ( Nod * headNode ) {
timbunan < Nod *> timbunan;
Nod * tempNode = headNode;
sementara ( tempNode ! = NULL ) {
// jika elemen atas timbunan sepadan
// nod semasa dan timbunan tidak kosong
jika ( ! timbunan.kosong ( ) && timbunan.atas ( ) == tempNode ) {
kembali benar ;
}
susun.tolak ( tempNode ) ;
tempNode = tempNode- > seterusnya;
}
kembali salah ;
}
int utama ( ) {
Nod * headNode = Nod baharu ( ) ;
Nod * secondNode = Nod baharu ( ) ;
Nod * thirdNode = Nod baharu ( ) ;
headNode- > data = 1 ;
headNode- > seterusnya = secondNode;
secondNode- > data = 2 ;
secondNode- > seterusnya = thirdNode;
thirdNode- > data = 3 ;
thirdNode- > seterusnya = NULL; // Tiada gelung
jika ( detectLoopLinkedList ( headNode ) ) {
cout << 'Gelung dikesan dalam senarai terpaut' << endl;
} lain {
cout << 'Tiada gelung dikesan dalam senarai terpaut' << endl;
}
// Mencipta gelung
thirdNode- > seterusnya = secondNode;
jika ( detectLoopLinkedList ( headNode ) ) {
cout << 'Gelung dikesan dalam senarai terpaut' << endl;
} lain {
cout << 'Tiada gelung dikesan dalam senarai terpaut' << endl;
}
Pengeluaran:
Tiada gelung dikesan dalam senarai terpaut
Gelung dikesan dalam senarai terpaut
Penjelasan:
Program ini menggunakan timbunan untuk mengetahui sama ada senarai pautan tunggal mempunyai gelung.
- 1. Pustaka aliran input/output dan perpustakaan tindanan kedua-duanya hadir dalam baris pertama.
2. Ruang nama standard disertakan dalam baris kedua, membolehkan kami mengakses fungsi perpustakaan aliran input/output tanpa perlu memberi awalan dengan 'std::.'
3. Baris berikut mentakrifkan Nod struktur, yang terdiri daripada dua ahli: integer dipanggil 'data' dan penunjuk ke Nod lain dipanggil 'seterusnya.'
4. Kepala senarai terpaut ialah input untuk kaedah detectLoopLinkedList(), yang ditakrifkan pada baris seterusnya. Fungsi ini menghasilkan nilai boolean yang menunjukkan sama ada gelung ditemui atau tidak.
5. Timbunan penunjuk Nod dipanggil 'tindanan' dan penuding kepada Nod bernama 'tempNode' yang dimulakan dengan nilai headNode kedua-duanya dicipta di dalam fungsi.
6. Kemudian, selagi tempNode bukan penunjuk nol, kita masukkan gelung sementara.
(a) Elemen atas timbunan mesti sepadan dengan nod semasa untuk kita menentukan bahawa ia tidak kosong. Kami kembali benar jika ini berlaku kerana gelung telah ditemui.
(b) Jika syarat yang dinyatakan di atas adalah palsu, penuding nod semasa ditolak ke tindanan, dan tempNode ditetapkan kepada nod berikut dalam senarai terpaut.
7. Kami mengembalikan palsu selepas gelung sementara kerana tiada gelung diperhatikan.
8. Kami membina tiga objek Nod dan memulakannya dalam fungsi main(). Oleh kerana tiada gelung dalam contoh pertama, kami menetapkan penunjuk 'seterusnya' bagi setiap Nod dengan betul.
Kesimpulan:
Kesimpulannya, kaedah terbaik untuk mengesan gelung dalam senarai terpaut bergantung pada kes penggunaan khusus dan kekangan masalah. Hash Table dan algoritma pencarian kitaran Floyd adalah kaedah yang cekap dan ia digunakan secara meluas dalam amalan. Timbunan dan rekursi adalah kaedah yang kurang cekap tetapi ia lebih intuitif.