API tools faq
paste
Advertisement
fsoc131y

the four

fsoc131y
Apr 24th, 2023 (edited)
202
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 15.49 KB | None | 0 0
raw download clone embed print report
  1. 1. QUEUE USING LINKED LISTS
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. struct node {
  6.     int data;
  7.     struct node* next;
  8. };
  9.  
  10. struct node* front = NULL;
  11. struct node* rear = NULL;
  12.  
  13. void enqueue(int x) {
  14.     struct node* temp = (struct node*)malloc(sizeof(struct node));
  15.     temp->data = x;
  16.     temp->next = NULL;
  17.     if (front == NULL && rear == NULL) {
  18.         front = rear = temp;
  19.         return;
  20.     }
  21.     rear->next = temp;
  22.     rear = temp;
  23. }
  24.  
  25. void dequeue() {
  26.     struct node* temp = front;
  27.     if (front == NULL) {
  28.         printf("Queue is empty\n");
  29.         return;
  30.     }
  31.     if (front == rear) {
  32.         front = rear = NULL;
  33.     }
  34.     else {
  35.         front = front->next;
  36.     }
  37.     printf("Dequeued element: %d\n", temp->data);
  38.     free(temp);
  39. }
  40.  
  41. void display() {
  42.     struct node* temp = front;
  43.     if (front == NULL) {
  44.         printf("Queue is empty\n");
  45.         return;
  46.     }
  47.     while (temp != NULL) {
  48.         printf("%d ", temp->data);
  49.         temp = temp->next;
  50.     }
  51.     printf("\n");
  52. }
  53.  
  54. int main() {
  55.     int choice, x;
  56.     do {
  57.         printf("1. Enqueue\n");
  58.         printf("2. Dequeue\n");
  59.         printf("3. Display\n");
  60.         printf("4. Exit\n");
  61.         printf("Enter your choice: ");
  62.         scanf("%d", &choice);
  63.         switch (choice) {
  64.             case 1:
  65.                 printf("Enter the element to enqueue: ");
  66.                 scanf("%d", &x);
  67.                 enqueue(x);
  68.                 break;
  69.             case 2:
  70.                 dequeue();
  71.                 break;
  72.             case 3:
  73.                 display();
  74.                 break;
  75.             case 4:
  76.                 exit(0);
  77.             default:
  78.                 printf("Invalid choice\n");
  79.         }
  80.     } while (choice != 4);
  81.     return 0;
  82. }
  83.  
  84. --------------------------------------------------------------------------------------------------------
  85. 2. BINARY SEARCH TREE
  86. #include <stdio.h>
  87. #include <stdlib.h>
  88.  
  89. // Binary Search Tree node structure
  90. struct node {
  91.     int data;
  92.     struct node* left;
  93.     struct node* right;
  94. };
  95.  
  96. // Function prototypes
  97. void insert(struct node** root, int data);
  98. void inorder(struct node* root);
  99. void preorder(struct node* root);
  100. void postorder(struct node* root);
  101.  
  102. // Main function
  103. int main() {
  104.     struct node* root = NULL;
  105.     int choice, data;
  106.  
  107.     do {
  108.         printf("\nBinary Search Tree Operations\n");
  109.         printf("----------------------------\n");
  110.         printf("1. Insert\n");
  111.         printf("2. Inorder Traversal\n");
  112.         printf("3. Preorder Traversal\n");
  113.         printf("4. Postorder Traversal\n");
  114.         printf("5. Exit\n");
  115.         printf("Enter your choice: ");
  116.         scanf("%d", &choice);
  117.  
  118.         switch(choice) {
  119.             case 1:
  120.                 printf("Enter the data to insert: ");
  121.                 scanf("%d", &data);
  122.                 insert(&root, data);
  123.                 break;
  124.             case 2:
  125.                 printf("Inorder Traversal: ");
  126.                 inorder(root);
  127.                 printf("\n");
  128.                 break;
  129.             case 3:
  130.                 printf("Preorder Traversal: ");
  131.                 preorder(root);
  132.                 printf("\n");
  133.                 break;
  134.             case 4:
  135.                 printf("Postorder Traversal: ");
  136.                 postorder(root);
  137.                 printf("\n");
  138.                 break;
  139.             case 5:
  140.                 printf("Exiting...\n");
  141.                 break;
  142.             default:
  143.                 printf("Invalid choice! Try again.\n");
  144.                 break;
  145.         }
  146.     } while(choice != 5);
  147.  
  148.     return 0;
  149. }
  150.  
  151. // Function to insert data into the binary search tree
  152. void insert(struct node** root, int data) {
  153.     struct node* newNode = (struct node*)malloc(sizeof(struct node));
  154.     newNode->data = data;
  155.     newNode->left = NULL;
  156.     newNode->right = NULL;
  157.  
  158.     if (*root == NULL) {
  159.         *root = newNode;
  160.     } else {
  161.         struct node* curr = *root;
  162.         while (1) {
  163.             if (data < curr->data) {
  164.                 if (curr->left == NULL) {
  165.                     curr->left = newNode;
  166.                     break;
  167.                 } else {
  168.                     curr = curr->left;
  169.                 }
  170.             } else {
  171.                 if (curr->right == NULL) {
  172.                     curr->right = newNode;
  173.                     break;
  174.                 } else {
  175.                     curr = curr->right;
  176.                 }
  177.             }
  178.         }
  179.     }
  180. }
  181.  
  182. // Function to perform inorder traversal of the binary search tree
  183. void inorder(struct node* root) {
  184.     if (root != NULL) {
  185.         inorder(root->left);
  186.         printf("%d ", root->data);
  187.         inorder(root->right);
  188.     }
  189. }
  190.  
  191. // Function to perform preorder traversal of the binary search tree
  192. void preorder(struct node* root) {
  193.     if (root != NULL) {
  194.         printf("%d ", root->data);
  195.         preorder(root->left);
  196.         preorder(root->right);
  197.     }
  198. }
  199.  
  200. // Function to perform postorder traversal of the binary search tree
  201. void postorder(struct node* root) {
  202.     if (root != NULL) {
  203.         postorder(root->left);
  204.         postorder(root->right);
  205.         printf("%d ", root->data);
  206.     }
  207. }
  208. --------------------------------------------------------------------------------------------------------
  209. 3. QUEUE IMPLEMENTATION USING STACKS & LL
  210. #include <stdio.h>
  211. #include <stdlib.h>
  212. #include <stdbool.h>
  213.  
  214. #define MAX_SIZE 100
  215.  
  216. // Node struct for linked list implementation
  217. typedef struct Node {
  218.     int data;
  219.     struct Node* next;
  220. } Node;
  221.  
  222. // Queue struct for both array and linked list implementations
  223. typedef struct Queue {
  224.     int front;
  225.     int rear;
  226.     int size;
  227.     int arr[MAX_SIZE];
  228.     Node* head;
  229. } Queue;
  230.  
  231. // Initialize the queue
  232. void init(Queue* q) {
  233.     q->front = -1;
  234.     q->rear = -1;
  235.     q->size = 0;
  236.     q->head = NULL;
  237. }
  238.  
  239. // Check if the queue is empty
  240. bool is_empty(Queue* q) {
  241.     return (q->front == -1 && q->rear == -1 && q->head == NULL);
  242. }
  243.  
  244. // Check if the queue is full
  245. bool is_full(Queue* q) {
  246.     return (q->rear == MAX_SIZE - 1);
  247. }
  248.  
  249. // Enqueue an element into the queue (array implementation)
  250. void enqueue_array(Queue* q, int data) {
  251.     if (is_full(q)) {
  252.         printf("Queue overflow! Cannot enqueue element.\n");
  253.         return;
  254.     }
  255.  
  256.     if (is_empty(q)) {
  257.         q->front = 0;
  258.         q->rear = 0;
  259.     } else {
  260.         q->rear++;
  261.     }
  262.  
  263.     q->arr[q->rear] = data;
  264.     q->size++;
  265.     printf("Enqueued element: %d\n", data);
  266. }
  267.  
  268. // Dequeue an element from the queue (array implementation)
  269. void dequeue_array(Queue* q) {
  270.     if (is_empty(q)) {
  271.         printf("Queue underflow! Cannot dequeue element.\n");
  272.         return;
  273.     }
  274.  
  275.     int data = q->arr[q->front];
  276.     q->front++;
  277.     q->size--;
  278.     printf("Dequeued element: %d\n", data);
  279.  
  280.     if (q->front > q->rear) {
  281.         q->front = -1;
  282.         q->rear = -1;
  283.     }
  284. }
  285.  
  286. // Display the contents of the queue (array implementation)
  287. void display_array(Queue* q) {
  288.     if (is_empty(q)) {
  289.         printf("Queue is empty!\n");
  290.         return;
  291.     }
  292.  
  293.     printf("Queue contents: ");
  294.     for (int i = q->front; i <= q->rear; i++) {
  295.         printf("%d ", q->arr[i]);
  296.     }
  297.     printf("\n");
  298. }
  299.  
  300. // Enqueue an element into the queue (linked list implementation)
  301. void enqueue_linked_list(Queue* q, int data) {
  302.     Node* new_node = (Node*)malloc(sizeof(Node));
  303.     new_node->data = data;
  304.     new_node->next = NULL;
  305.  
  306.     if (is_empty(q)) {
  307.         q->head = new_node;
  308.         q->front = 0;
  309.         q->rear = 0;
  310.     } else {
  311.         q->rear++;
  312.         Node* curr = q->head;
  313.         while (curr->next != NULL) {
  314.             curr = curr->next;
  315.         }
  316.         curr->next = new_node;
  317.     }
  318.  
  319.     q->size++;
  320.     printf("Enqueued element: %d\n", data);
  321. }
  322.  
  323. // Dequeue an element from the queue (linked list implementation)
  324. void dequeue_linked_list(Queue* q) {
  325.     if (is_empty(q)) {
  326.         printf("Queue underflow! Cannot dequeue element.\n");
  327.         return;
  328.     }
  329.  
  330.     int data = q->head->data;
  331.     Node* temp = q->head;
  332.     q->head = q->head->next;
  333.     free(temp);
  334.     q->size--;
  335.     printf("Dequeued element: %d\n", data);
  336.    
  337.     if (q->size == 0) {
  338.         q->front = -1;
  339.         q->rear = -1;
  340. }
  341. }
  342.  
  343. // Display the contents of the queue (linked list implementation)
  344. void display_linked_list(Queue* q) {
  345. if (is_empty(q)) {
  346. printf("Queue is empty!\n");
  347. return;
  348. }
  349.  
  350. printf("Queue contents: ");
  351. Node* curr = q->head;
  352. while (curr != NULL) {
  353.     printf("%d ", curr->data);
  354.     curr = curr->next;
  355. }
  356. printf("\n");
  357. }
  358.  
  359. int main() {
  360. Queue q;
  361. init(&q);
  362. int choice, data;
  363.  
  364. do {
  365.     printf("\nQueue Operations:\n");
  366.     printf("1. Enqueue (Array Implementation)\n");
  367.     printf("2. Dequeue (Array Implementation)\n");
  368.     printf("3. Display (Array Implementation)\n");
  369.     printf("4. Enqueue (Linked List Implementation)\n");
  370.     printf("5. Dequeue (Linked List Implementation)\n");
  371.     printf("6. Display (Linked List Implementation)\n");
  372.     printf("7. Exit\n");
  373.     printf("Enter your choice: ");
  374.     scanf("%d", &choice);
  375.  
  376.     switch (choice) {
  377.         case 1:
  378.             printf("Enter element to enqueue: ");
  379.             scanf("%d", &data);
  380.             enqueue_array(&q, data);
  381.             break;
  382.         case 2:
  383.             dequeue_array(&q);
  384.             break;
  385.         case 3:
  386.             display_array(&q);
  387.             break;
  388.         case 4:
  389.             printf("Enter element to enqueue: ");
  390.             scanf("%d", &data);
  391.             enqueue_linked_list(&q, data);
  392.             break;
  393.         case 5:
  394.             dequeue_linked_list(&q);
  395.             break;
  396.         case 6:
  397.             display_linked_list(&q);
  398.             break;
  399.         case 7:
  400.             printf("Exiting...\n");
  401.             exit(0);
  402.         default:
  403.             printf("Invalid choice!\n");
  404.             break;
  405.     }
  406. } while (choice != 7);
  407.  
  408. return 0;
  409. }
  410.  
  411. --------------------------------------------------------------------------------------------------------
  412. 4. QUEUE W/ LL loop
  413. #include <stdio.h>
  414. #include <stdlib.h>
  415.  
  416. struct node {
  417.     int data;
  418.     struct node* next;
  419. };
  420.  
  421. struct node* front = NULL;
  422. struct node* rear = NULL;
  423.  
  424. void enqueue(int x) {
  425.     struct node* temp = (struct node*)malloc(sizeof(struct node));
  426.     temp->data = x;
  427.     temp->next = NULL;
  428.     if (front == NULL && rear == NULL) {
  429.         front = rear = temp;
  430.         return;
  431.     }
  432.     rear->next = temp;
  433.     rear = temp;
  434. }
  435.  
  436. void dequeue() {
  437.     struct node* temp = front;
  438.     if (front == NULL) {
  439.         printf("Queue is empty\n");
  440.         return;
  441.     }
  442.     if (front == rear) {
  443.         front = rear = NULL;
  444.     }
  445.     else {
  446.         front = front->next;
  447.     }
  448.     printf("Dequeued element: %d\n", temp->data);
  449.     free(temp);
  450. }
  451.  
  452. void display() {
  453.     struct node* temp = front;
  454.     if (front == NULL) {
  455.         printf("Queue is empty\n");
  456.         return;
  457.     }
  458.     while (temp != NULL) {
  459.         printf("%d ", temp->data);
  460.         temp = temp->next;
  461.     }
  462.     printf("\n");
  463. }
  464.  
  465. int main() {
  466.     int n, x, i;
  467.     printf("Enter the number of items to be entered: ");
  468.     scanf("%d", &n);
  469.     for (i = 0; i < n; i++) {
  470.         printf("Enter the element to enqueue: ");
  471.         scanf("%d", &x);
  472.         enqueue(x);
  473.     }
  474.     printf("Queue: ");
  475.     display();
  476.     while (1) {
  477.         int choice;
  478.         printf("1. Enqueue\n");
  479.         printf("2. Dequeue\n");
  480.         printf("3. Display\n");
  481.         printf("4. Exit\n");
  482.         printf("Enter your choice: ");
  483.         scanf("%d", &choice);
  484.         switch (choice) {
  485.             case 1:
  486.                 printf("Enter the element to enqueue: ");
  487.                 scanf("%d", &x);
  488.                 enqueue(x);
  489.                 printf("Queue: ");
  490.                 display();
  491.                 break;
  492.             case 2:
  493.                 dequeue();
  494.                 printf("Queue: ");
  495.                 display();
  496.                 break;
  497.             case 3:
  498.                 printf("Queue: ");
  499.                 display();
  500.                 break;
  501.             case 4:
  502.                 exit(0);
  503.             default:
  504.                 printf("Invalid choice\n");
  505.         }
  506.     }
  507.     return 0;
  508. }
  509. ------------------------------------------------------------------------------------------------------------------
  510. 5. BST W/ loop
  511. #include <stdio.h>
  512. #include <stdlib.h>
  513.  
  514. // Binary Search Tree node structure
  515. struct node {
  516.     int data;
  517.     struct node* left;
  518.     struct node* right;
  519. };
  520.  
  521. // Function prototypes
  522. void insert(struct node** root, int data);
  523. void inorder(struct node* root);
  524. void preorder(struct node* root);
  525. void postorder(struct node* root);
  526.  
  527. // Main function
  528. int main() {
  529.     struct node* root = NULL;
  530.     int choice, data, n;
  531.  
  532.     printf("Enter the number of terms to be entered: ");
  533.     scanf("%d", &n);
  534.  
  535.     for (int i = 0; i < n; i++) {
  536.         printf("Enter term %d: ", i + 1);
  537.         scanf("%d", &data);
  538.         insert(&root, data);
  539.     }
  540.  
  541.     do {
  542.         printf("\nBinary Search Tree Operations\n");
  543.         printf("----------------------------\n");
  544.         printf("1. Inorder Traversal\n");
  545.         printf("2. Preorder Traversal\n");
  546.         printf("3. Postorder Traversal\n");
  547.         printf("4. Exit\n");
  548.         printf("Enter your choice: ");
  549.         scanf("%d", &choice);
  550.  
  551.         switch(choice) {
  552.             case 1:
  553.                 printf("Inorder Traversal: ");
  554.                 inorder(root);
  555.                 printf("\n");
  556.                 break;
  557.             case 2:
  558.                 printf("Preorder Traversal: ");
  559.                 preorder(root);
  560.                 printf("\n");
  561.                 break;
  562.             case 3:
  563.                 printf("Postorder Traversal: ");
  564.                 postorder(root);
  565.                 printf("\n");
  566.                 break;
  567.             case 4:
  568.                 printf("Exiting...\n");
  569.                 break;
  570.             default:
  571.                 printf("Invalid choice! Try again.\n");
  572.                 break;
  573.         }
  574.     } while(choice != 4);
  575.  
  576.     return 0;
  577. }
  578.  
  579. // Function to insert data into the binary search tree
  580. void insert(struct node** root, int data) {
  581.     struct node* newNode = (struct node*)malloc(sizeof(struct node));
  582.     newNode->data = data;
  583.     newNode->left = NULL;
  584.     newNode->right = NULL;
  585.  
  586.     if (*root == NULL) {
  587.         *root = newNode;
  588.     } else {
  589.         struct node* curr = *root;
  590.         while (1) {
  591.             if (data < curr->data) {
  592.                 if (curr->left == NULL) {
  593.                     curr->left = newNode;
  594.                     break;
  595.                 } else {
  596.                     curr = curr->left;
  597.                 }
  598.             } else {
  599.                 if (curr->right == NULL) {
  600.                     curr->right = newNode;
  601.                     break;
  602.                 } else {
  603.                     curr = curr->right;
  604.                 }
  605.             }
  606.         }
  607.     }
  608. }
  609.  
  610. // Function to perform inorder traversal of the binary search tree
  611. void inorder(struct node* root) {
  612.     if (root != NULL) {
  613.         inorder(root->left);
  614.         printf("%d ", root->data);
  615.         inorder(root->right);
  616.     }
  617. }
  618.  
  619. // Function to perform preorder traversal of the binary search tree
  620. void preorder(struct node* root) {
  621.     if (root != NULL) {
  622.         printf("%d ", root->data);
  623.         preorder(root->left);
  624.         preorder(root->right);
  625.     }
  626. }
  627.  
  628. // Function to perform postorder traversal of the binary search tree
  629. void postorder(struct node* root) {
  630.     if (root != NULL) {
  631.         postorder(root->left);
  632.         postorder(root->right);
  633.         printf("%d ", root->data);
  634.     }
  635. }
  636.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!