Kami telah membahas solusi berulang untuk membalikkan daftar tertaut di posting sebelumnya. Dalam posting ini, kita akan membahas implementasi rekursifnya Show Berikut ini adalah implementasi rekursif sederhana yang bekerja dengan memperbaiki C1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 #include #include
// Node Daftar Tertaut struct Node { int data; struct Node* berikutnya; };
// Fungsi pembantu untuk mencetak daftar tertaut yang diberikan void printList(struct Node* head) { struct Node* ptr = head; sementara (ptr) { printf("%d —> ", ptr->data); ptr = ptr->next; }
printf("NULL\n")<; }
// Fungsi Helper untuk menyisipkan node baru di awal linked list void push(struct Node** head, int data) { struct Node* Node baru = (struct Node*)malloc(sizeof(struct Node)); Node baru->data = data; Node baru->berikutnya = *head;
*head = newNode; }
// Fungsi rekursif untuk membalikkan daftar tertaut yang diberikan. Ini membalikkan // diberikan daftar tertaut dengan memperbaiki penunjuk kepala dan kemudian `. selanjutnya` // pointer dari setiap node dalam urutan terbalik void recursiveReverse(struct Node* head, struct Node** headRef) { struct Node* pertama; struct Node* istirahat;
// kasus dasar daftar kosong jika (kepala == NULL) { kembalikan; }
pertama = kepala; // suppose first = {1, 2, 3} istirahat = pertama->next; // rest = {2, 3}
// kasus dasar. daftar hanya memiliki satu node jika (istirahat == NULL) { // perbaiki penunjuk kepala di sini *headRef = pertama; kembalikan; }
// secara rekursif membalik kasus {2, 3} yang lebih kecil // setelah. istirahat = {3, 2} recursiveReverse(istirahat, headRef);
// letakkan item pertama di akhir daftar istirahat->berikutnya = first; pertama->berikutnya = NULL; // (tricky step — make a drawing) }
// Balikkan daftar tertaut yang diberikan. Fungsi mengambil pointer // (referensi) ke penunjuk kepala void mundur(struct Node** head) { recursiveReverse(*head, head); }
int utama(batal) { // tombol masukan int kunci[] = { 1, 2, 3, 4, 5, 6 }; int n = sizeof(keys)/sizeof(keys[0]);
struct Node* head = NULL; untuk (int i = n - 1; i >=0; i--) { tekan(&kepala, keys[i]); }
terbalik(&kepala); printList(kepala);
kembalikan 0; } Unduh Jalankan Kode Keluaran C++1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 #include #include menggunakan namespace std;
// Node Daftar Tertaut struct Node { int data; Node* berikutnya; };
// Fungsi pembantu untuk mencetak daftar tertaut yang diberikan void printList(Node* head) { Node* ptr = head; sementara (ptr) { cout << ptr->data << " —> "; ptr = ptr->next; }
cout << "nullptr" <<< endl; }
// Fungsi Helper untuk menyisipkan node baru di awal linked list void push(Node* &headRef, int data) { Node* Node baru = new Node(); Node baru->data = data; Node baru->berikutnya = headRef;
headRef = Node baru; }
// Fungsi rekursif untuk membalikkan daftar tertaut yang diberikan. Ini membalikkan // diberikan daftar tertaut dengan memperbaiki penunjuk kepala dan kemudian `. selanjutnya` // pointer dari setiap node dalam urutan terbalik void recursiveReverse(Node* head, Node* &headRef) { Node* pertama; Node* istirahat;
// kasus dasar daftar kosong jika (kepala == nullptr) { kembalikan; }
pertama = kepala; // suppose first = {1, 2, 3} istirahat = pertama->next; // rest = {2, 3}
// kasus dasar. daftar hanya memiliki satu node jika (istirahat == nullptr) { // perbaiki penunjuk kepala di sini headRef = pertama; kembalikan; }
// secara rekursif membalik kasus {2, 3} yang lebih kecil // setelah. istirahat = {3, 2} recursiveReverse(istirahat, headRef);
// letakkan item pertama di akhir daftar istirahat->berikutnya = first; pertama->berikutnya = nullptr; // (tricky step — make a drawing) }
// Balikkan daftar tertaut yang diberikan. Fungsi mengambil pointer // (referensi) ke penunjuk kepala void terbalik(Node* &headRef) { recursiveReverse(headRef, headRef); }
int utama() { // tombol masukan vektor<int> keys = { 1, 2, 3, 4, 5, 6 };
Node* head = nullptr; untuk (int i = keys.ukuran() - 1; i >=0; i--) { tekan(kepala, keys[i]); }
terbalik(kepala); printList(kepala);
kembalikan 0; } Unduh Jalankan Kode Keluaran Jawa1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 // Node Daftar Tertaut kelas Node { int data; Node berikutnya;
Node(int data) { ini. data = data; } }
kelas Utama { // Fungsi pembantu untuk mencetak daftar tertaut tertentu publik statis batal printList(Node head) { Simpul ptr = kepala; sementara (ptr . = null) { Sistem. keluar. cetak(ptr. data + " —> "); ptr = ptr. selanjutnya; } Sistem. keluar. println("null"); }
// Fungsi pembantu untuk menyisipkan node baru di awal linked list publik statis Node push(Node head, int data) { Node node = baru Node(data); simpul. selanjutnya = kepala; kembalikan simpul; }
// Fungsi rekursif untuk membalikkan daftar tertaut yang diberikan. Ini membalikkan // diberikan daftar tertaut dengan memperbaiki penunjuk kepala lalu `. selanjutnya` // pointer setiap node dalam urutan terbalik publik statis Node terbalik(Node head, Node headRef) { Node pertama, istirahat;
// kasus dasar daftar kosong jika (kepala == null) { return headRef; }
pertama = kepala; // suppose first = {1, 2, 3} istirahat = pertama. berikutnya; // istirahat = {2, 3}
// kasus dasar. daftar hanya memiliki satu node jika (istirahat == null) { // perbaiki penunjuk kepala di sini headRef = pertama; return headRef; }
// membalikkan kasus {2, 3} yang lebih kecil // sesudahnya. istirahat = {3, 2} headRef = terbalik(rest, headRef);
// letakkan item pertama di akhir daftar istirahat. berikutnya = pertama; pertama. berikutnya = null; <// (tricky step — make a drawing)
return headRef; }
// Balikkan daftar tertaut tertentu. Fungsi mengambil referensi ke // node kepala publik statis Node terbalik(Node head) { kembali mundur(kepala, head); }
publik statis batal utama(String[] args) { // tombol masukan int[] kunci = { 1, 2, 3, 4, 5, 6 };
Node head = null; untuk (int i = keys.panjang - 1; i >=0; i--) { kepala = tekan(head, keys[i]); }
kepala = mundur(head); printList(head); } } Unduh Jalankan Kode Keluaran Piton1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 # Node Daftar Tertaut kelas Node. def __init__(diri, data, next=None): diri sendiri. data = data diri sendiri. berikutnya = berikutnya
# Fungsi untuk mencetak daftar tertaut yang diberikan def printList(head):
ptr = kepala sementara ptr. cetak(ptr. data, end=') ptr = ptr. selanjutnya cetak('Tidak Ada')
# Fungsi rekursif untuk membalikkan daftar tertaut yang diberikan. Ini membalikkan # diberikan daftar tertaut dengan memperbaiki penunjuk kepala dan kemudian `. selanjutnya` # pointer dari setiap node dalam urutan terbalik def terbalik(kepala, headRef):
# kasus dasar daftar kosong jika kepala adalah Tidak ada: return headRef
pertama = kepala # suppose first = [1, 2, 3] istirahat = pertama. selanjutnya # istirahat = [2, 3]
# kasus dasar. list hanya memiliki satu node jika sisa adalah Tidak ada: # perbaiki penunjuk kepala di sini headRef = pertama return headRef
# secara rekursif membalik kasus {2, 3} yang lebih kecil # setelahnya. istirahat = [3, 2] headRef = terbalik(rest, headRef)
# letakkan item pertama di akhir daftar istirahat. selanjutnya = pertama pertama. selanjutnya = Tidak ada # (
return headRef
# Balikkan daftar tertaut yang diberikan def reverseList(head): kembali mundur(kepala, head)
jika __nama__ == '__main__'.
kepala = Tidak ada untuk i di dibalik(range(6)): kepala = Simpul(i + 1, head)
head = reverseList(head) printList(head)
Unduh Jalankan Kode Keluaran Kita juga dapat mengatasi masalah ini dengan hanya mengirimkan referensi ke penunjuk kepala ke fungsi, seperti yang ditunjukkan di bawah ini C1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 #include #include
// Node Daftar Tertaut struct Node { int data; struct Node* berikutnya; };
// Fungsi pembantu untuk mencetak daftar tertaut yang diberikan void printList(struct Node* head) { struct Node* ptr = head; sementara (ptr) { printf("%d —> ", ptr->data); ptr = ptr->next; }
printf("NULL\n")<; }
// Fungsi Helper untuk menyisipkan node baru di awal linked list void push(struct Node** head, int data) { struct Node* Node baru = (struct Node*)malloc(sizeof(struct Node)); Node baru->data = data; Node baru->berikutnya = *head;
*head = newNode; }
// Fungsi rekursif untuk membalikkan linked list. Ini membalikkan yang diberikan // daftar tertaut dengan memperbaiki penunjuk kepala dan kemudian `. pointer` berikutnya // dari setiap node dalam urutan terbalik void mundur(struct Node** head) { struct Node* pertama; struct Node* istirahat;
// kasus dasar daftar kosong jika (*kepala == NULL) { kembalikan; }
pertama = *kepala; // suppose first = {1, 2, 3} istirahat = pertama->next; // rest = {2, 3}
// wadah basis istirahat kosong jika (istirahat == NULL) { kembalikan; }
terbalik(&istirahat); // recursively reverse the smaller {2, 3} case // setelah. istirahat = {3, 2}
pertama->berikutnya->next = first; // put the first item at the end of the list pertama->berikutnya = NULL; // (tricky step — make a drawing) *kepala = istirahat; // fix the head pointer }
int utama(batal) { // tombol masukan int kunci[] = { 1, 2, 3, 4, 5, 6 }; int n = sizeof(keys)/sizeof(keys[0]);
struct Node* head = NULL; untuk (int i = n - 1; i >=0; i--) { tekan(&kepala, keys[i]); }
terbalik(&kepala); printList(kepala);
kembalikan 0; } Unduh Jalankan Kode Keluaran C++1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 #include #include menggunakan namespace std;
// Node Daftar Tertaut struct Node { int data; Node* berikutnya; };
// Fungsi pembantu untuk mencetak daftar tertaut yang diberikan void printList(Node* head) { Node* ptr = head; sementara (ptr) { cout << ptr->data << " —> "; ptr = ptr->next; }
cout << "nullptr" <<< endl; }
// Fungsi Helper untuk menyisipkan node baru di awal linked list void push(Node* &headRef, int data) { Node* Node baru = new Node(); Node baru->data = data; Node baru->berikutnya = headRef;
headRef = Node baru; }
// Fungsi rekursif untuk membalikkan linked list. Ini membalikkan yang diberikan // daftar tertaut dengan memperbaiki penunjuk kepala dan kemudian `. pointer` berikutnya // dari setiap node dalam urutan terbalik // Fungsi mengambil referensi ke penunjuk kepala void terbalik(Node* &headRef) { Node* pertama; Node* istirahat;
// kasus dasar daftar kosong jika (headRef == nullptr) { kembalikan; }
pertama = headRef; // suppose first = {1, 2, 3} istirahat = pertama->next; // rest = {2, 3}
// wadah basis istirahat kosong jika (istirahat == nullptr) { kembalikan; }
terbalik(istirahat); // recursively reverse the smaller {2, 3} case // setelah. istirahat = {3, 2}
pertama->berikutnya->next = first; // put the first item at the end of the list pertama->berikutnya = nullptr; // (tricky step — make a drawing) headRef = istirahat; // fix the head pointer }
int utama() { // tombol masukan vektor<int> keys = { 1, 2, 3, 4, 5, 6 };
Node* head = nullptr; untuk (int i = keys.ukuran() - 1; i >=0; i--) { tekan(kepala, keys[i]); }
terbalik(kepala); printList(kepala);
kembalikan 0; } Unduh Jalankan Kode Keluaran Jawa1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 // Node Daftar Tertaut kelas Node { int data; Node berikutnya;
Node(int data) { ini. data = data; } }
kelas Utama { // Fungsi pembantu untuk menyisipkan node baru di awal linked list publik statis Node push(Node head, int data) { Node node = baru Node(data); simpul. selanjutnya = kepala; kembalikan simpul; }
// Fungsi pembantu untuk mencetak daftar tertaut tertentu publik statis batal printList(Node head) { Simpul ptr = kepala; sementara (ptr . = null) { Sistem. keluar. cetak(ptr. data + " —> "); ptr = ptr. selanjutnya; } Sistem. keluar. println("null"); }
// Fungsi rekursif untuk membalik daftar tertaut. // Ini membalikkan daftar tertaut yang diberikan dengan memperbaiki penunjuk kepala dan // kemudian `. pointer` berikutnya dari setiap node dalam urutan terbalik publik statis Node terbalik(Node head) { Node pertama, istirahat;
// kasus dasar daftar kosong jika (kepala == null) { kembalikan kepala; }
pertama = kepala; // suppose first = {1, 2, 3} istirahat = pertama. selanjutnya; // istirahat = {2, 3}
// wadah tempat istirahat kosong jika (istirahat == null) { kembalikan kepala; }
istirahat = mundur(rest); // recursively reverse the smaller {2, 3} case // sesudahnya. istirahat = {3, 2}
pertama. selanjutnya. berikutnya = pertama; <// put the first item at the end of the list pertama. selanjutnya = null; <// (tricky step — make a drawing) kepala = istirahat; // fix the head pointer
kembalikan kepala; }
publik statis batal utama(String[] args) { // tombol masukan int[] kunci = { 1, 2, 3, 4, 5, 6 };
Node head = null; untuk (int i = keys.panjang - 1; i >=0; i--) { kepala = tekan(head, keys[i]); }
kepala = mundur(head); printList(head); } } Unduh Jalankan Kode Keluaran Piton1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 # Node Daftar Tertaut kelas Node. def __init__(diri, data, next=None): diri sendiri. data = data diri sendiri. berikutnya = berikutnya
# Fungsi untuk mencetak daftar tertaut yang diberikan def printList(head):
ptr = kepala sementara ptr. cetak(ptr. data, end=') ptr = ptr. selanjutnya
cetak('Tidak Ada')
# Fungsi rekursif untuk membalikkan daftar tertaut # Ini membalikkan daftar tertaut yang diberikan dengan memperbaiki penunjuk kepala dan # kemudian `. pointer berikutnya dari setiap node dalam urutan terbalik def terbalik(kepala):
# kasus dasar daftar kosong jika kepala adalah Tidak ada: kembalikan kepala
pertama = kepala # suppose first = [1, 2, 3] istirahat = pertama. selanjutnya # istirahat = [2, 3]
# kotak basis istirahat kosong jika sisa adalah Tidak ada: kembalikan kepala
istirahat = mundur(rest) # recursively reverse the smaller {2, 3} case # setelahnya. istirahat = [3, 2]
pertama. selanjutnya. berikutnya = pertama # put pertama. selanjutnya = Tidak ada # ( kepala = istirahat # fix the head pointer
kembali kepala
jika __nama__ == '__main__'.
kepala = Tidak ada untuk i di dibalik(range(6)): kepala = Simpul(i + 1, head)
kepala = mundur(head) printList(head)
Unduh Jalankan Kode Keluaran Kita dapat menyederhanakan kode di atas dengan meneruskan informasi simpul sebelumnya ke fungsi. Berikut ini adalah implementasi rekursif sederhana di C, C++, Java, dan Python Bagaimana Anda membalikkan daftar menggunakan rekursi?Pendekatan rekursif untuk membalik daftar tertaut itu sederhana, hanya saja kita harus membagi daftar tertaut menjadi dua bagian dan saya. e node pertama dan sisa daftar tertaut, lalu panggil rekursi untuk bagian lain dengan mempertahankan koneksi .
Bagaimana cara membalikkan daftar dengan Python?Dengan Python, fungsi bawaan bernama reverse() digunakan untuk membalikkan daftar . Cara sederhana dan cepat untuk membalikkan daftar ini membutuhkan sedikit memori. Sintaksis. Daftar nama. reverse() Di sini, list_name berarti Anda harus menulis nama daftar, yang harus dibalik.
Bagaimana Anda membalik daftar dengan Python menggunakan for loop?3) Menggunakan for loop
. Buat daftar kosong untuk menyalin elemen terbalik. Pada perulangan for, tambahkan iterator sebagai elemen daftar di awal dengan elemen daftar baru. Jadi dengan cara itu, elemen daftar akan dibalik. |
Daftar terbalik menggunakan rekursi python
Pos Terkait
Copyright © 2024 apacode Inc.
