Idanref

4+5 Advanced C Ass. 1

Apr 22nd, 2021 (edited)
269
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <assert.h>
  4.  
  5. typedef struct Node
  6. {
  7.     int value;
  8.     struct Node* next;
  9. } node;
  10.  
  11. node* create_node(int data)
  12. {
  13.     node* temp = (node*)malloc(sizeof(node));
  14.  
  15.     temp->value = data;
  16.     temp->next = NULL;
  17.  
  18.     return temp;
  19. }
  20.  
  21. void insert(node** head, int value)
  22. {
  23.     node* link = create_node(value);
  24.  
  25.     if (*head == NULL)
  26.     {
  27.         *head = link;
  28.         return;
  29.     }
  30.  
  31.     node* temp = *head;
  32.  
  33.     while (temp->next != NULL)
  34.     {
  35.         temp = temp->next;
  36.     }
  37.  
  38.     temp->next = link;
  39. }
  40.  
  41. void print_list(node* head)
  42. {
  43.     node* temp = head;
  44.  
  45.     if (head == NULL)
  46.     {
  47.         printf("List is empty.\n");
  48.         return;
  49.     }
  50.  
  51.     while (temp != NULL)
  52.     {
  53.         printf("%d-> ", temp->value);
  54.         temp = temp->next;
  55.     }
  56.     printf("\n");
  57. }
  58.  
  59. void delete_after(node* temp)
  60. {
  61.     node* delete_node = temp->next;
  62.     temp->next = temp->next->next;
  63.     free(delete_node);
  64. }
  65.  
  66. void delete_head(node** head)
  67. {
  68.     if ((*head) && (*head)->next == NULL)
  69.     {
  70.         free(*head);
  71.         return;
  72.     }
  73.  
  74.     node* delete_node = *head;
  75.     *head = (*head)->next;
  76.     free(delete_node);
  77. }
  78.  
  79. node* createList(node** head)
  80. {
  81.     node* temp = *head;
  82.     node* head2 = NULL;
  83.     node* new_node;
  84.  
  85.     if (*head == NULL) // no items
  86.     {
  87.         return head2;
  88.     }
  89.  
  90.     if (*head && (*head)->next == NULL) // 1 item in the list
  91.     {
  92.         insert(&head2, (*head)->value);
  93.         delete_head(head);
  94.         return head2;
  95.     }
  96.  
  97.     if (temp->value > temp->next->value) // first item bigger
  98.     {
  99.         insert(&head2, (*head)->value);
  100.         delete_head(head);
  101.         temp = *head;
  102.     }
  103.  
  104.     while (temp->next->next != NULL && temp->next != NULL)
  105.     {
  106.         if (temp->value < temp->next->value && temp->next->value > temp->next->next->value)
  107.         {
  108.             insert(&head2, temp->next->value);
  109.             delete_after(temp);
  110.         }
  111.  
  112.         if(temp->next)
  113.             temp = temp->next;
  114.     }
  115.  
  116.     if (temp->next->value > temp->value) // last item
  117.     {
  118.         insert(&head2, temp->next->value);
  119.         delete_after(temp);
  120.     }
  121.  
  122.     return head2;
  123. }
  124.  
  125. node* createList2(node** head) // second without memory allocation and free
  126. {
  127.     node* temp = *head;
  128.     node* head2 = NULL;
  129.     node* new_node;
  130.     node* temp2;
  131.  
  132.  
  133.     if (*head == NULL) // no items
  134.     {
  135.         return head2;
  136.     }
  137.  
  138.     if (*head && (*head)->next == NULL) // 1 item in the list
  139.     {
  140.         head2 = *head;
  141.         return head2;
  142.     }
  143.  
  144.  
  145.     // look for head
  146.  
  147.     if (temp->value > temp->next->value) // first item bigger
  148.     {
  149.         head2 = temp;
  150.         temp2 = head2;
  151.         temp = temp->next;
  152.         temp2->next = NULL;
  153.     }
  154.  
  155.  
  156.     if (head2 == NULL)
  157.     {
  158.         while (temp->next->next != NULL && temp->next != NULL)
  159.         {
  160.             if (temp->value < temp->next->value && temp->next->value > temp->next->next->value)
  161.             {
  162.                 head2 = temp->next;
  163.                 temp->next = temp->next->next;
  164.                 break;
  165.             }
  166.  
  167.             else temp = temp->next;
  168.         }
  169.     }
  170.  
  171.  
  172.     if (head2 == NULL) // no head found
  173.         return head2;
  174.  
  175.     else // head2 is not empty
  176.     {
  177.         temp2 = head2; // to not lose head2
  178.  
  179.         if (temp->next) // after search for head
  180.             temp = temp->next;
  181.  
  182.         else // if next node is null
  183.             return head2;
  184.  
  185.  
  186.         while (temp->next->next != NULL && temp->next != NULL) // start algorithm
  187.         {
  188.             if (temp->value < temp->next->value && temp->next->value > temp->next->next->value) // success finding
  189.             {
  190.                 temp2->next = temp->next;
  191.                 temp2 = temp2->next;
  192.                 temp->next = temp->next->next;
  193.                 temp2->next = NULL; // very important!! disconnect from next node
  194.             }
  195.  
  196.             if (temp->next)
  197.                 temp = temp->next;
  198.         }
  199.  
  200.         if (temp->next->value > temp->value) // last item
  201.         {
  202.             temp2->next = temp->next;
  203.             temp2 = temp2->next;
  204.             temp->next = temp->next->next;
  205.             temp2->next = NULL;
  206.         }
  207.     }
  208.  
  209.     return head2;
  210. }
  211.  
  212. void main()
  213. {
  214.     node* head = NULL;
  215.  
  216.     insert(&head, 3);
  217.     insert(&head, 6);
  218.     insert(&head, 1);
  219.     insert(&head, 9);
  220.     insert(&head, 8);
  221.     insert(&head, 4);
  222.     insert(&head, 5);
  223.  
  224.     print_list(head);
  225.  
  226.     node* temp = head;
  227.  
  228.     node* head2 = createList2(&head);
  229.  
  230.     print_list(head2);
  231.     print_list(head);
  232. }
  233.  
RAW Paste Data