Computer >> Máy Tính >  >> Lập trình >> C ++

Danh sách vòng tròn được liên kết gấp đôi trong C ++

Danh sách liên kết hình tròn là một biến thể của danh sách được liên kết trong đó phần tử đầu tiên trỏ đến phần tử cuối cùng và phần tử cuối cùng trỏ đến phần tử đầu tiên. Cả Danh sách liên kết đơn và Danh sách được liên kết kép đều có thể được tạo thành một danh sách liên kết vòng tròn.

Trong danh sách được liên kết kép, con trỏ tiếp theo của nút cuối cùng trỏ đến nút đầu tiên và con trỏ trước đó của nút đầu tiên trỏ đến nút cuối cùng tạo thành vòng tròn theo cả hai hướng.

Danh sách vòng tròn được liên kết gấp đôi trong C ++

Theo minh họa ở trên, sau đây là những điểm quan trọng cần được xem xét.

  • Liên kết tiếp theo của liên kết cuối cùng trỏ đến liên kết đầu tiên của danh sách trong danh sách được liên kết kép.

  • Liên kết trước của liên kết đầu tiên trỏ đến danh sách cuối cùng của danh sách được liên kết kép.

Thuật toán

displayForward():
Begin
      ptr := head
   while ptr := null, do
      print ptr ->key, ptr ->data
      ptr := ptr -> next
   done
End
displayBackward():
Begin
   ptr := last
   while ptr := null, do
      print ptr ->key, ptr ->data
      ptr := ptr -> prev
   done
End
insertFirst(key, data):
Begin
   create new node with key and data
   if list is empty, then
      last := node
   else
      head -> prev := node
   end if
   node -> next := head
   head := node
End
insertLast (key, data):
Begin
   create new node with key and data
   if list is empty, then
      last := node
   else
      last -> next := node
      node -> prev:= last
   end if
   last := node
End
insertAfter(key, newKey, data):
Begin
   current := head
   if head is null, then return false
   while key of current is not key, do
      if current -> next is not null, then
         return false
      else
         current := next of current
      end if
   done
   create new node with newKey and data
   if current = last, then
      next of node := null
      last := node
   else
      next of node := next of current
      prev of next of current := node
   end if
   prev of node := current
   next of current := node
   return true;
End
deleteFirst():
Begin
   tempNode := head
   if next of head is null, then
      last := null
   else
      prev of next of head := null
   end if
   head := next of head
   return tempNode
End
deleteLast():
Begin
   tempNode := last
   if next of head is null, then
      head := null
   else
      next of prev of last := null
   end if
   last := prev of last
   return tempNode
End
deleteNode(key):
Begin
   curr := head and prev := null
   if head is null, then
      return null
   end if
   while key of currr is not same as key, do
      if next of curr is null, then
         return null
      else
         prev := curr
         curr := next of curr
      end if
   done
   if curr is head, then head := next of head, otherwise next of prev of curr = next of curr
   if curr is last, then last := prev of curr, otherwise prev of next of curr = prev of curr
   return curr
End

Ví dụ

#include <iostream<
using namespace std;
class node {
   public:
      int data;
      int key;
      node *next;
   node *prev;
};
//this link always point to first Link
node *head = NULL;
//this link always point to last Link
node *last = NULL;
node *current = NULL;
//is list empty
bool isEmpty() {
   return head == NULL;
}
int length() {
   int length = 0;
   node *current;
   for(current = head; current != NULL; current = current->next){
      length++;
   }
   return length;
}
//display the list in from first to last
void displayForward() {
   //start from the beginning
   node *ptr = head;
   //navigate till the end of the list
   printf("\n[ ");
   while(ptr != NULL) {
      printf("(%d,%d) ",ptr->key,ptr->data);
      ptr = ptr->next;
   }
   printf(" ]");
}
//display the list from last to first
void displayBackward() {
   //start from the last
   node *ptr = last;
   //navigate till the start of the list
   printf("\n[ ");
   while(ptr != NULL) {
      //print data
      printf("(%d,%d) ",ptr->key,ptr->data);
      //move to next item
      ptr = ptr ->prev;
   }
}
//insert link at the first location
void insertFirst(int key, int data) {
   //create a link
   node *link = new node();
   link->key = key;
   link->data = data;
   if(isEmpty()) {
      //make it the last link
      last = link;
   }
   else {
      //update first prev link
      head->prev = link;
   }
   //point it to old first link
   link->next = head;
   //point first to new first link
   head = link;
}
//insert link at the last location
void insertLast(int key, int data) {
   //create a link
   node *link = new node();
   link->key = key;
   link->data = data;
   if(isEmpty()) {
      //make it the last link
      last = link;
   }
   else {
      //make link a new last link
      last->next = link;
      //mark old last node as prev of new link
      link->prev = last;
   }
   //point last to new last node
   last = link;
}
//delete first item
node* deleteFirst() {
   //save reference to first link
   node *tempLink = head;
   //if only one link
   if(head->next == NULL){
      last = NULL;
   }
   else {
      head->next->prev = NULL;
   }
   head = head->next;
   //return the deleted link
   return tempLink;
}
//delete link at the last location
node* deleteLast() {
   //save reference to last link
   node *tempLink = last;
   //if only one link
   if(head->next == NULL) {
      head = NULL;
   }
   else {
      last->prev->next = NULL;
   }
   last = last->prev;
   //return the deleted link
   return tempLink;
}
//delete a link with given key
node* del(int key) {
   //start from the first link
   node* current = head;
   node* previous = NULL;
   //if list is empty
   if(head == NULL) {
      return NULL;
   }
   //navigate through list
   while(current->key != key) {
      //if it is last node
      if(current->next == NULL) {
         return NULL;
      }
      else {
         //store reference to current link
         previous = current;
         //move to next link
         current = current->next;
      }
   }
   //found a match, update the link
   if(current == head) {
      //change first to point to next link
      head = head->next;
   }
   else {
      //bypass the current link
      current->prev->next = current->next;
   }
   if(current == last) {
      //change last to point to prev link
      last = current->prev;
   }
   else {
      current->next->prev = current->prev;
   }
   return current;
}
bool insertAfter(int key, int newKey, int data) {
   //start from the first link
   node *current = head;
   //if list is empty
   if(head == NULL) {
      return false;
   }
   //navigate through list
   while(current->key != key) {
      //if it is last node
      if(current->next == NULL) {
         return false;
      }
      else {
         //move to next link
         current = current->next;
      }
   }
   //create a link
   node *newLink = new node();
   newLink->key = newKey;
   newLink->data = data;
   if(current == last) {
      newLink->next = NULL;
      last = newLink;
   }
   else {
      newLink->next = current->next;
      current->next->prev = newLink;
   }
   newLink->prev = current;
   current->next = newLink;
   return true;
}
main() {
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56);
   printf("\nList (First to Last): ");
   displayForward();
   printf("\n");
   printf("\nList (Last to first): ");
   displayBackward();
   printf("\nList , after deleting first record: ");
   deleteFirst();
   displayForward();
   printf("\nList , after deleting last record: ");
   deleteLast();
   displayForward();
   printf("\nList , insert after key(4) : ");
   insertAfter(4,7, 13);
   displayForward();
   printf("\nList , after delete key(4) : ");
   del(4);
   displayForward();
}

Đầu ra

List (First to Last):
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
List (Last to first):
[ (1,10) (2,20) (3,30) (4,1) (5,40) (6,56)
List , after deleting first record:
[ (5,40) (4,1) (3,30) (2,20) (1,10) ]
List , after deleting last record:
[ (5,40) (4,1) (3,30) (2,20) ]
List , insert after key(4) :
[ (5,40) (4,1) (7,13) (3,30) (2,20) ]
List , after delete key(4) :
[ (5,40) (7,13) (3,30) (2,20) ]