Dalam soalan ini, kami diberi senarai pautan. Tugas kami ialah mencipta program untuk membalikkan senarai terpaut.
Program ini akan membalikkan senarai pautan yang diberikan dan mengembalikan senarai pautan terbalik.
Senarai terpaut ialah urutan terpaut yang mengandungi item. Setiap pautan mengandungi sambungan ke pautan lain.
9 -> 32 -> 65 -> 10 -> 85 -> NULL
Senarai terpaut terbalik ialah membuat senarai terpaut dengan menterbalikkan pautan senarai terpaut. Nod kepala senarai terpaut akan menjadi nod terakhir senarai terpaut, dan nod terakhir akan menjadi nod kepala.
Senarai terpaut terbalik terbentuk daripada senarai terpaut di atas −
85 -> 10 -> 65 -> 32 -> 9 -> NULL
Untuk membalikkan senarai terpaut yang diberikan, kami akan menggunakan tiga petunjuk tambahan untuk memproses. Penunjuk ini adalah sebelumnya, selepas dan semasa.
Kami pada mulanya akan menetapkan kedua-dua sebelumnya dan selepas kepada NULL, dan menetapkan semasa ke kepala senarai terpaut.
Selepas ini, kami mengulangi sehingga kami mencapai NULL senarai pautan awal. Kemudian lakukan perkara berikut:
after = current -> next current -> next = previous previous = current current = after
Sekarang mari buat program untuk membalikkan senarai terpaut. Terdapat dua cara untuk mencipta program ini, satu adalah berulang dan satu lagi adalah rekursif.
Program untuk menterbalikkan senarai terpaut (kaedah ekor-rekursif)
Demonstrasi
#include <stdio.h> struct Node { int data; struct Node* next; }; Node* insertNode(int key) { Node* temp = new Node; temp->data = key; temp->next = NULL; return temp; } void tailRecRevese(Node* current, Node* previous, Node** head){ if (!current->next) { *head = current; current->next = previous; return; } Node* next = current->next; current->next = previous; tailRecRevese(next, current, head); } void tailRecReveseLL(Node** head){ if (!head) return; tailRecRevese(*head, NULL, head); } void printLinkedList(Node* head){ while (head != NULL) { printf("%d ", head->data); head = head->next; } printf("</p><p>"); } int main(){ Node* head1 = insertNode(9); head1->next = insertNode(32); head1->next->next = insertNode(65); head1->next->next->next = insertNode(10); head1->next->next->next->next = insertNode(85); printf("Linked list : \t"); printLinkedList(head1); tailRecReveseLL(&head1); printf("Reversed linked list : \t"); printLinkedList(head1); return 0; }
Linked list : 9 32 65 10 85 Reversed linked list : 85 10 65 32 9
Program untuk menterbalikkan senarai kaedah terpaut)(Iterative method)
#include <stdio.h> struct Node { int data; struct Node* next; Node(int data){ this->data = data; next = NULL; } }; struct LinkedList { Node* head; LinkedList(){ head = NULL; } void interReverseLL(){ Node* current = head; Node *prev = NULL, *after = NULL; while (current != NULL) { after = current->next; current->next = prev; prev = current; current = after; } head = prev; } void print() { struct Node* temp = head; while (temp != NULL) { printf("%d ", temp-> data); temp = temp->next; } printf("</p><p>"); } void push(int data){ Node* temp = new Node(data); temp->next = head; head = temp; } }; int main() { LinkedList linkedlist; linkedlist.push(85); linkedlist.push(10); linkedlist.push(65); linkedlist.push(32); linkedlist.push(9); printf("Linked List : \t"); linkedlist.print(); linkedlist.interReverseLL(); printf("Reverse Linked List : \t"); linkedlist.print(); return 0; }
Output
Linked List : 9 32 65 10 85 Reverse Linked List : 85 10 65 32 9
Atas ialah kandungan terperinci Program C untuk membalikkan senarai terpaut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!