splash365

Tower of Hanoi (linked list)

Jan 8th, 2021 (edited)
157
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.30 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct Stack
  6. {
  7.     int data;
  8.     Stack *next;
  9. };
  10.  
  11. Stack *StackNode(int val)
  12. {
  13.     Stack *newNode = new Stack();
  14.     newNode->data = val;
  15.     newNode->next = NULL;
  16.     return newNode;
  17. }
  18.  
  19. bool isEmpty(Stack *ptr)
  20. {
  21.     if(ptr == NULL) return true;
  22.     return false;
  23. }
  24.  
  25. void push(Stack **ptr, int val)
  26. {
  27.     Stack *newNode = StackNode(val);
  28.     if(isEmpty(*ptr)) *ptr = newNode;
  29.     else
  30.     {
  31.         newNode->next = *ptr;
  32.         *ptr = newNode;
  33.     }
  34. }
  35.  
  36. void pop(Stack **ptr)
  37. {
  38.     if(isEmpty(*ptr)) return;
  39.     else
  40.     {
  41.         Stack *cur = *ptr;
  42.         *ptr = (*ptr)->next;
  43.         free(cur);
  44.     }
  45. }
  46.  
  47. int Top(Stack *ptr)
  48. {
  49.     if(isEmpty(ptr)) {
  50.         return -1;
  51.     }
  52.     else
  53.     {
  54.         return ptr->data;
  55.     }
  56. }
  57.  
  58. void PrintMovement(string from, string to, int disk)
  59. {
  60.     cout<<"Move the disk "<<disk<<" from "<<from<<" to "<<to<<endl;
  61. }
  62.  
  63. void moveDisk(Stack **from, Stack **to, string s, string d)
  64. {
  65.     if(isEmpty(*from))
  66.     {
  67.         push(&(*from), Top(*to));
  68.         PrintMovement(d,s,Top(*to));
  69.         pop(&(*to));
  70.     }
  71.     else if(isEmpty(*to))
  72.     {
  73.         push(&(*to), Top(*from));
  74.         PrintMovement(s,d,Top(*from));
  75.         pop(&(*from));
  76.     }
  77.     else if(Top(*from) > Top(*to))
  78.     {
  79.         push(&(*from), Top(*to));
  80.         PrintMovement(d,s,Top(*to));
  81.         pop(&(*to));
  82.     }
  83.     else
  84.     {
  85.         push(&(*to), Top(*from));
  86.         PrintMovement(s,d,Top(*from));
  87.         pop(&(*from));
  88.     }
  89. }
  90.  
  91. void AllMoves(int n, Stack *src, Stack *dest, Stack *aux)
  92. {
  93.     int t_moves = pow(2,n) - 1;
  94.  
  95.     string s = "Source";
  96.     string d = "Destination";
  97.     string a = "Auxiliary";
  98.  
  99.     if(n%2 == 0)
  100.     {
  101.         string temp = d;
  102.         d = a;
  103.         a = temp;
  104.     }
  105.  
  106.     for(int i=1; i<=t_moves ; i++)
  107.     {
  108.         if(i%3 == 1) moveDisk(&src, &dest, s, d);
  109.         else if(i%3 == 2) moveDisk(&src, &aux, s, a);
  110.         else if(i%3 == 0) moveDisk(&aux, &dest, a, d);
  111.     }
  112.  
  113. }
  114.  
  115.  
  116. int main()
  117. {
  118.     cout<<"Enter the number of disks : ";
  119.     int n;
  120.     cin>>n;
  121.  
  122.     Stack *src = NULL;
  123.     Stack *dest = NULL;
  124.     Stack *aux = NULL;
  125.  
  126.     for(int i=n; i>0; i--)
  127.     {
  128.         push(&src, i);
  129.     }
  130.  
  131.     AllMoves(n,src,dest,aux);
  132.  
  133. }
  134.  
  135.  
  136.  
  137.  
  138.  
  139.  
  140.  
  141.  
  142.  
Add Comment
Please, Sign In to add comment