senarai terpaut: Ini ialah senarai terpaut yang ingin kami undurkan.
Selepas senarai pautan terbalik: Di bawah akan menjadi keputusan selepas membalikkan senarai yang dipautkan di atas.
Dalam contoh rajah di atas, kita dapat melihat bahawa nod kepala dan nod ekor menukar kedudukannya apabila kita membalikkan senarai terpaut. Nod kepala, yang kini menjadi nod ekor, menghala ke nod nol kerana ia kini menjadi nod ekor.
Langkah-langkah Algoritma
- Kami mencipta kaedah utama dan mengisytiharkan beberapa pembolehubah yang diperlukan.
- Kemudian, langkah seterusnya ialah mencipta kaedah yang boleh membuat senarai terpaut. Kaedah ini membantu kami membuat senarai terpaut.
- Langkah seterusnya ialah mencipta kaedah untuk membalikkan senarai terpaut. Dalam kaedah ini, kami melepasi keseluruhan senarai terpaut, dan kaedah ini akan membalikkan senarai terpaut.
- Sekarang, kami memerlukan kaedah lain untuk memaparkan hasil kami selepas membalikkannya.
- Kami akan menggabungkan semua kaedah di atas ke dalam kaedah utama kami.
Kami akan menerangkan senarai pautan terbalik menggunakan beberapa bentuk bergambar untuk memudahkan pemahaman. Jadi mari kita mulakan dengan contoh.
Di bawah ialah senarai terpaut yang ingin kami undurkan.
Langkah 1 . Nod berwarna hijau ialah nod kepala, yang menghala ke nod pertama dalam permulaan.
Langkah 2. Dalam langkah seterusnya, kami akan melintasi keseluruhan senarai terpaut sehingga kami tidak mendapat penuding nol di sebelah nod pengepala. Untuk itu, kami akan memberikan nod seterusnya nama sementara, seperti yang ditunjukkan dalam rajah di bawah.
Langkah 3. Memandangkan kami mempunyai nod rujukan baharu bernama 'sementara,' yang boleh membantu kami melintasi keseluruhan senarai terpaut sehingga kami tidak mendapat penuding nol, Jadi kami boleh menetapkan pautan seterusnya nod pengepala sebagai nol, yang tidak akan menjejaskan yang dipautkan senaraikan seperti yang ditunjukkan di bawah dalam rajah. Penunjuk nol di sebelah nod semasa dipanggil nod sebelumnya.
Langkah 4. Sekarang, kita mengalihkan nod sementara ke nod seterusnya dan nod semasa ke nod sementara sebelumnya. Jadi sekarang kita telah berpindah ke nod seterusnya. Kami juga menukar nod sebelumnya daripada nod kepada hanya nod sebelumnya bagi nod semasa. Jadi sekarang nod sementara akan menjaga semua lintasan sehingga penuding nol supaya kita boleh menetapkan pautan nod semasa ke nod sebelumnya, dan kini ia menunjuk ke nod sebelumnya, seperti yang ditunjukkan dalam rajah di bawah.
Jadi kami mengikuti langkah yang sama dan, akhirnya, kami akan mendapat senarai terpaut terbalik.
Langkah 5 .
Langkah 6.
Langkah 7.
Langkah 8.
Langkah 9.
Langkah 10.
Langkah 11.
Langkah 12.
Langkah 13.
Langkah 14. Pada langkah ini, senarai terpaut kami terbalik.
Program C++ untuk membalikkan senarai terpaut
#includemenggunakan ruang nama std ;
// Kaedah untuk mencipta nod
struct nod {
int nilai ;
nod * seterusnyaNodePtr ;
} * nodeObject ;
batal createLinkedList ( int n ) ;
batal reverseLinkedList ( nod ** nodeObject ) ;
batal paparan ( ) ;
int utama ( ) {
int n, nilai, item ;
cout << 'Berapa banyak nod yang anda ingin buat =>: ' ;
makan >> n ;
createLinkedList ( n ) ;
cout << ' \n Maklumat dalam senarai terpaut: \n ' ;
paparan ( ) ;
cout << ' \n Senarai terpaut selepas diterbalikkan \n ' ;
reverseLinkedList ( & nodeObject ) ;
paparan ( ) ;
kembali 0 ;
}
// Kaedah ini akan mencipta senarai terpaut
batal createLinkedList ( int n ) {
struct nod * frontNode, * tempNode ;
int nilai, i ;
nodeObject = ( struct nod * ) malloc ( saiz ( struct nod ) ) ;
jika ( nodeObject == NULL )
cout << 'Tidak cukup untuk menambah ingatan' ;
lain {
cout << 'Sila masukkan maklumat nod 1 (nombor sahaja): ' ;
makan >> nilai ;
nodeObject - > nilai = nilai ;
nodeObject - > seterusnyaNodePtr = NULL ;
tempNode = nodeObject ;
untuk ( i = dua ; i <= n ; i ++ ) {
frontNode = ( struct nod * ) malloc ( saiz ( struct nod ) ) ;
// Apabila tiada sebarang nod dalam senarai terpaut
jika ( frontNode == NULL ) {
cout << 'Memori tidak boleh diperuntukkan' ;
rehat ;
}
lain {
cout << 'Sila masukkan maklumat nod ' << i << ':' ;
makan >> nilai ;
frontNode - > nilai = nilai ;
frontNode - > seterusnyaNodePtr = NULL ;
tempNode - > seterusnyaNodePtr = frontNode ;
tempNode = tempNode - > seterusnyaNodePtr ;
}
}
}
}
batal reverseLinkedList ( nod ** nodeObject ) {
struct nod * tempNode = NULL ;
struct nod * nod sebelumnya = NULL ;
struct nod * nod semasa = ( * nodeObject ) ;
sementara ( nod semasa ! = NULL ) {
tempNode = nod semasa - > seterusnyaNodePtr ;
nod semasa - > seterusnyaNodePtr = nod sebelumnya ;
nod sebelumnya = nod semasa ;
nod semasa = tempNode ;
}
( * nodeObject ) = nod sebelumnya ;
}
batal paparan ( ) {
struct nod * tempNode ;
jika ( nodeObject == NULL ) {
cout << 'Senarai pautan kosong' ;
}
lain {
tempNode = nodeObject ;
sementara ( tempNode ! = NULL )
{
cout << tempNode - > nilai << ' \t ' ;
tempNode = tempNode - > seterusnyaNodePtr ;
}
}
cout << endl ;
}
Pengeluaran
Berapa banyak nod yang anda ingin buat =>: 6Sila masukkan maklumat nod 1 (nombor sahaja): 101
Sila masukkan maklumat nod 2: 95
Sila masukkan maklumat nod 3: 61
Sila masukkan maklumat nod 4: 19
Sila masukkan maklumat nod 5: 12
Sila masukkan maklumat nod 6: 11
Maklumat dalam senarai terpaut:
101 95 61 19 12 11
Senarai terpaut selepas diterbalikkan
11 12 19 61 95 101
Kesimpulan
Artikel LinuxHint ini telah menyemak cara membalikkan senarai terpaut dalam C++. Terdapat beberapa kaedah lain untuk menterbalikkan senarai terpaut, tetapi ini adalah kaedah yang sangat biasa untuk membalikkan senarai terpaut. Terpulang kepada anda untuk memutuskan cara anda mahu menyelesaikan masalah anda, tetapi secara amnya fungsi senarai terpaut terbalik haruslah gelung mudah dengan pertukaran penunjuk.