dmilicev

lets_learn_single_linked_list_with_int_v1.c

Dec 21st, 2019
216
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 37.27 KB | None
  1. /*
  2.  
  3.     lets_learn_single_linked_list_with_int_v1.c
  4.  
  5.  
  6.     SSL - Single Linked List
  7.  
  8.     With global variables.
  9.  
  10.     With the meny.
  11.  
  12.  
  13.     https://en.wikipedia.org/wiki/Linked_list
  14.  
  15.     https://www.geeksforgeeks.org/linked-list-set-1-introduction/
  16.  
  17.     https://www.geeksforgeeks.org/data-structures/linked-list/singly-linked-list/
  18.  
  19.     https://www.c-lang.thiyagaraaj.com/data-structures/linked-list/singly-linked-list-example-program-in-c
  20.  
  21.     https://www.sanfoundry.com/c-program-implement-singly-linked-list/
  22.  
  23.     https://www.codesdope.com/blog/article/linked-lists-in-c-singly-linked-list/
  24.  
  25.     https://www.thecrazyprogrammer.com/2013/09/menu-driven-c-program-to-perform-insert.html
  26.  
  27.     https://www.learn-c.org/en/Linked_lists
  28.  
  29.     https://www.geeksforgeeks.org/generic-linked-list-in-c-2/
  30.  
  31.  
  32.     You can find all my C programs at Dragan Milicev's pastebin:
  33.  
  34.     https://pastebin.com/u/dmilicev
  35.  
  36.     https://www.facebook.com/dmilicev
  37.  
  38. */
  39.  
  40. #include <stdio.h>
  41. #include <stdlib.h>             // for malloc(), calloc(), realloc(), free()
  42.  
  43.  
  44. typedef struct node{
  45.     int data;
  46.     struct node *next;
  47. } Node;
  48.  
  49. Node *head, *newNode, *cur;
  50. // declare three global nodes:
  51. // head - start node, list start
  52. // newNode - auxiliary node, to create new nodes
  53. // cur - the current node, for scroll through the list
  54.  
  55.  
  56. /*
  57.  
  58. struct node {
  59.     int data;
  60.     struct node* next;          // now the data type is struct node
  61. };
  62.  
  63. typedef struct node NODE;       // now the data type instead of struct node becomes only NODE
  64.  
  65. typedef NODE* PNODE;            // PNODE is pointer to NODE
  66.  
  67. */
  68.  
  69.  
  70. // Returns 1 if the list is empty, otherwise returns 0.
  71. int IsListEmpty(void)
  72. {
  73.     if( head == NULL ){         // if there are no members in the list ie if the list is empty
  74.         printf(" List is empty.\n\n");
  75.         return 1;
  76.     }
  77.     else
  78.         return 0;
  79. } // IsListEmpty()
  80.  
  81.  
  82. /*
  83. Scroll through the list:
  84. When working with lists, it is often necessary to scroll through the list, from element to element.
  85. Most often it is about processing the data in the list, searching the list to find it
  86. the corresponding element or search for the end of the list.
  87. In all these cases the algorithm is similar.
  88. A helper pointer cur is introduced that is initially equal to the list's head,
  89. i.e. points to the first element of the list if it is not empty.
  90. After verifying that the pointer cur points to an element (has a value other than NULL),
  91. it processes the data in that element (print, compare, calculate ...).
  92. Upon completion of the data processing, the auxiliary pointer cur
  93. gets the value of the pointer to the next element,
  94. and the whole process is repeated until the helper pointer cur has a value other than NULL,
  95. that is, while pointing to an element.
  96. When the helper pointer cur gets NULL, it means we have reached the end of the list.
  97. */
  98.  
  99. // Goes through the entire list and counts the list elements.
  100. int count_list_elements()
  101. {
  102.     int counter=0;
  103.  
  104.     cur = head;                 // the current element is mounted on the head
  105.  
  106.     while( cur ){               // for all elements of the list (until the cur is NULL ie last)
  107.  
  108.         counter++;              // increase the number of elements of the list
  109.  
  110.         cur = cur->next;        // move on to the next element of the list
  111.     }
  112.  
  113.     return counter;
  114. } // count_list_elements()
  115.  
  116.  
  117. // Create a new node, the entry is done in node newNode
  118. void new_node(){
  119.  
  120.     newNode = (Node*)malloc( sizeof(Node) );    // reserve memory for node newNode
  121.     if( newNode == NULL ) {
  122.         printf("\n Memory allocation error! \n");
  123.         exit(1);
  124.     }
  125.  
  126.     printf("\n\n Enter newNode->data :  ");     // enter newNode->data ie the contents of the newNode node
  127.     scanf("%d", &newNode->data);                // check for integer input here !!!
  128.  
  129.     newNode->next = NULL;                       // newNode is the new node and points to NULL for now
  130. } // new_node()
  131.  
  132.  
  133. // Function to add a node at the beginning of linked list
  134. void add_at_begin(){
  135.  
  136.     new_node();                 // enter new node in newNode
  137.  
  138.     if( head == NULL ){         // if there are no members in the list ie if the list is empty
  139.         head=newNode;           // then the head is a new member (already pointing to NULL)
  140.     }
  141.     else{                       // if there are members in the list ie if the list is not empty
  142.         newNode->next=head;     // newNode points to old head
  143.         head=newNode;           // head becomes new member
  144.     }
  145. } // add_at_begin()
  146.  
  147.  
  148. // Displays the entire list, each list member in a new row,
  149. // and at the same time counts the list members.
  150. // For each node it displays the contents and the pointer to the next one.
  151. // Returns the number of members of the list.
  152. int print_list_with_pointers(){
  153.  
  154.     int counter=0;              // serves for counting list members
  155.  
  156.     printf("\n\n");
  157.  
  158.     if( head == NULL )          // if there are no members in the list ie if the list is empty
  159.         printf(" List is empty.\n\n");
  160.     else{                       // if there are members in the list ie if the list is not empty
  161.         cur = head;             // the current member is mounted on the head
  162.         printf("\t\t | cur->data - cur->next | \n\n");  // display the list header
  163.  
  164.         while( cur ){           // for all members of the list (until the cur is NULL ie last)
  165.  
  166.             counter++;          // increase the number of members of the list
  167.  
  168.             printf("\n \t %2d. \t | %5d     -  %p  | \n",
  169.                    counter, cur->data, cur->next ); // display the list member
  170.  
  171.             cur = cur->next;    // move on to the next member of the list
  172.  
  173.         } // while( cur )
  174.     } // else                   // if there are members in the list ie if the list is not empty
  175.  
  176.     //printf("\n\n List has %d elements. \n\n", counter );
  177.  
  178.     return( counter );
  179. } // print_list_with_pointers()
  180.  
  181.  
  182. // Displays only the contents of nodes in one row and
  183. // counts the members of the list at the same time.
  184. // Returns the number of members of the list.
  185. int print_list(void){
  186.  
  187.     int counter=0;              // serves for counting list members
  188.  
  189.     printf("\n\n");
  190.  
  191.     if( head == NULL )          // if there are no members in the list ie if the list is empty
  192.         printf(" List is empty. \n\n");
  193.     else{                       // if there are members in the list ie if the list is not empty
  194.         cur = head;             // the current member is mounted on the head
  195.  
  196.         while( cur ){           // for all members of the list (until the girl is NULL ie last)
  197.  
  198.             counter++;          // increase the number of members of the list
  199.  
  200.             printf("%4d", cur->data );  // display the contents of the current node
  201.  
  202.             cur = cur->next;    // move on to the next member of the list
  203.         }
  204.     }
  205.  
  206.     //printf("\n\n\n   List has %d elements. \n\n", counter );
  207.     printf("\n\n");
  208.  
  209.     return( counter );
  210. } // print_list()
  211.  
  212.  
  213. // Insert newNode after node whose contents are x
  214. int insert_after_x(){
  215.  
  216.     int x;
  217.  
  218.     printf("\n\n");
  219.  
  220.     printf("\n\n Enter the newNode after the node that has value, x = ");
  221.     scanf("%d", &x);
  222.  
  223.     new_node();                 // enter new node in newNode
  224.  
  225.     if( head == NULL ){         // if there are no members in the list
  226.         printf("\n\n List is empty !!! \n\n");
  227.         system("PAUSE");
  228.         return(0);
  229.     }
  230.     else{                       // if there are members in the list
  231.  
  232.         cur = head;             // let's get to the first member of the list
  233.                                 // to the end of the list or to a member whose contents are x
  234.         while( cur->data != x && cur->next != NULL ){
  235.             cur = cur->next;    // go to next node
  236.         }
  237.  
  238.         // now we are on a node whose content is x
  239.         // he was pointing to his next member
  240.         // and now it should point to newNode
  241.         // a newNode should point to the member to which node x was pointing so far
  242.         // or, more simply:
  243.         // x was pointing to the cur
  244.         // now x should point to newNode
  245.         // a newNode should point to cur
  246.  
  247.         newNode->next = cur->next;
  248.         cur->next = newNode;
  249.     }
  250. } // insert_after_x()
  251.  
  252.  
  253. // Add a newNode to the end of the list
  254. void add_to_end(){
  255.  
  256.     new_node();                 // enter new node in newNode
  257.  
  258.     if( head == NULL ){         // if there are no members in the list ie if the list is empty
  259.         head=newNode;           // then that newly entered member newNode becomes the start of the list (head)
  260.     }                           // (and is also the end of the list because it is the only one)
  261.     else{                       // if there are members in the list ie if the list is not empty
  262.         cur = head;             // let's get to the first member of the list
  263.  
  264.         while( cur->next != NULL ){ // until the last member of the list is reached
  265.             cur = cur->next;    // move on to the next member of the list
  266.         }
  267.                                 // now the current member (cur) is the last member of the list,
  268.         cur->next = newNode;    // and it should show the newly entered node newNode
  269.     }
  270. } // add_to_end()
  271.  
  272.  
  273. // Delete the initial (first) node in the list, delete the head
  274. void delete_first(){
  275.  
  276.     if( head == NULL ){         // if there are no members in the list ie if the list is empty
  277.         printf("\n\n List is empty! Unable to delete! \n\n");
  278.         system("PAUSE");
  279.     }
  280.     else{                       // if there are members in the list ie if the list is not empty
  281.         newNode = head;         // the initial member head is memorized into the auxiliary member newNode due to free memory
  282.         head = head->next;      // the second member becomes the first, ie the newNode starting member head becomes his (former) next member
  283.         free(newNode);          // free up memory that was reserved for helper member newNode
  284.     }                           // (this is where we remembered the former initial head member)
  285. } // delete_first()
  286.  
  287.  
  288. // Delete the last node in the list
  289. void delete_last(){
  290.  
  291.     if( head == NULL ) {        // if there are no members in the list ie if the list is empty
  292.         printf("\n\n List is empty! Unable to delete! \n\n");
  293.         system("PAUSE");
  294.     }
  295.     else{                       // if there are members in the list ie if the list is not empty
  296.         cur=head;               // let's get to the first member of the list
  297.  
  298.         if(cur->next != NULL){  // if next member exists
  299.  
  300.             while(cur->next->next != NULL){     // to the penultimate member
  301.                 cur=cur->next;                  // go to next member
  302.             }
  303.                                 // now the current member (cur) is the penultimate member of the list
  304.             newNode = cur->next;// in newNode we remember the address of the last member of the list
  305.                                 // due to free memory (we delete it)
  306.  
  307.             cur->next = NULL;   // penultimate member cur has no following and therefore points to NULL
  308.  
  309.             free(newNode);      // free up the memory occupied by the former last member of the list
  310.         }                       // because we deleted it and we don't need it anymore
  311.         else{                   // if there is no next member, ie cur is the only member in the list, both first and last
  312.             delete_first();     // then delete that single member of the list
  313.         }
  314.     }
  315. } // delete_last()
  316.  
  317.  
  318. // Deletes all the nodes of the list and frees up the memory that the nodes occupy
  319. void delete_all_nodes()
  320. {
  321.     while( ( cur = head ) != NULL ){    // while the head exists, we delete the head
  322.  
  323.         newNode = head;         // the initial member head is memorized into the auxiliary member newNode due to free memory
  324.         head = head->next;      // the second member becomes the first, ie the newNode starting member head becomes his (former) next member
  325.         free(newNode);          // free up memory that was reserved for helper member newNode
  326.     }
  327. } // delete_all_nodes()
  328.  
  329.  
  330. /*
  331. To delete an item from a list:
  332. To delete a particular element x from a list, we need to know its position in the list.
  333. We move through the list until the liquid element is the one we delete (cur-> data = x).
  334. We also need to know the pointer to the previous element in the list in order to find its link
  335. assigned a pointer to the element following the element we are deleting.
  336. After that we can delete the required element, that is, free up the memory it occupies.
  337. */
  338.  
  339. // Deletes the first node that has the contents of x and frees the memory occupied by that node.
  340. // Returns NumberOfDeleted nodes.
  341. int delete_first_with_value_x( int x )
  342. {
  343.     int NumberOfDeleted=0;
  344.  
  345.     if( head == NULL ) {        // if there are no members in the list ie if the list is empty
  346.         printf("\n\n Lista je prazna! Nemoguce brisanje!!! \n\n");
  347.         system("PAUSE");
  348.     }
  349.     else {                      // if there are members in the list ie if the list is not empty
  350.  
  351.         cur = head;             // let's get to the first member of the list
  352.  
  353.         if( cur->data == x ) {  // if the contents of the head is x
  354.             delete_first();
  355.         }
  356.         else {                  // if the contents of the head isn't x
  357.                                 // to the end of the list or to a member whose contents are x
  358.             while( cur->data != x && cur->next != NULL ){
  359.                 printf("\n\n while cur->data = %2d \n\n", cur->data );
  360.                 newNode = cur;  // in newNode we remember the previous of cur
  361.                 cur = cur->next;// go to next node
  362.             }
  363.  
  364.                                 // now is cur node whose value is x, newNode is previous from cur
  365.             if( cur->data == x ){   // if there is a node whose content is x
  366.  
  367.                 newNode->next = cur->next; // previous of cur points to next of cur (because cur is deleted)
  368.                 newNode = cur;  // in newNode we remember the cur for deleting and for freeing memory (deleting it)
  369.                 free(newNode);  // free up the memory occupied by the former last member of the list
  370.                 NumberOfDeleted++;
  371.             }
  372.             else {
  373.                 printf("\n\n There is no node in the list with contents %2d ! \n\n", x );
  374.                 system("PAUSE");
  375.             }
  376.         } // if the contents of the head isn't x
  377.     } // if there are members in the list ie if the list is not empty
  378.  
  379.     return NumberOfDeleted;
  380. } // delete_first_with_value_x()
  381.  
  382.  
  383. // Deletes all nodes that have x content and frees up the memory these nodes occupy.
  384. // Returns NumberOfDeleted nodes.
  385. int delete_all_with_value_x( int x ) {
  386.     Node *previous, *current;
  387.     int NumberOfDeleted=0;
  388.  
  389.     if( head == NULL ) {        // if there are no members in the list ie if the list is empty
  390.         printf("\n\n The list is empty! Impossible to delete! \n\n");
  391.         system("PAUSE");
  392.     }
  393.     else {                      // if there are members in the list ie if the list is not empty
  394.  
  395.             current = head;     // let's get to the first member of the list
  396.             previous = NULL;
  397.  
  398.             while( current != NULL ){ // for all members of the list (until the girl is NULL ie last)
  399.  
  400.                 previous = current;
  401.                 current = current->next;
  402.  
  403.                 if ( current->data == x ){
  404.                     current = current->next;
  405.                     previous->next = current;
  406.                     NumberOfDeleted++;
  407.                 }
  408.             }
  409.  
  410.     } // if there are members in the list ie if the list is not empty
  411.  
  412.     if( NumberOfDeleted == 0 ){
  413.         printf("\n\n There is no node in the list with contents %2d ! \n\n", x );
  414.         system("PAUSE");
  415.     }
  416.  
  417.     return NumberOfDeleted;
  418. } // delete_all_with_value_x()
  419.  
  420.  
  421. // Delete an node by ordinal number in the list
  422. Node *delete_node_with_ordinal_number_k( Node *p, int ordinal_number )
  423. {
  424.     Node *previous, *current;
  425.     int i;
  426.  
  427.     if (p == NULL ){            // if the list is empty
  428.         printf("List is empty. \n");
  429.         system("PAUSE");
  430.     }
  431.     else                        // if the list is not empty
  432.     {
  433.         if ( ordinal_number > count_list_elements(p) ){
  434.             printf("\n\n Ordinal number %d is greater than the number of list elements %d ! \n\n",
  435.                    ordinal_number, count_list_elements(p) );
  436.             system("PAUSE");
  437.         }
  438.         else{
  439.             previous = NULL;
  440.             current = p;
  441.             i = 1;
  442.  
  443.             while ( i < ordinal_number ){
  444.                 previous = current;
  445.                 current = current->next;
  446.                 i = i+1;
  447.             }
  448.  
  449.             if ( previous == NULL ){
  450.                 p = current->next;
  451.                 free( current );
  452.             }
  453.             else{
  454.                 previous->next = current->next;
  455.                 free( current );
  456.             }
  457.         } // else   // ( ordinal_number <= count_list_elements(p) )
  458.     } // else   // if the list is not empty
  459.     return( p );
  460. } // delete_node_with_ordinal_number_k()
  461.  
  462.  
  463. /*
  464. Sort the list in ascending order:
  465. To sort the list, we first scroll through it to find the element
  466. with the lowest data value. We then remove that element from the list i
  467. we add it to the end of the second list, which was initially blank.
  468. We repeat this process until the initial list is empty.
  469. In the end, all that remains is for the function to return a cursor
  470. to a list in which all the elements have been moved.
  471. */
  472.  
  473. // Sorts the list in ascending order
  474. Node *sort_list_in_ascending_order( Node *p )
  475. {
  476.     Node *auxiliary1, *auxiliary2, *min, *previous, *q;
  477.  
  478.     q = NULL;                   // new auxiliary list
  479.  
  480.     while( p != NULL )          // to the end of the list
  481.     {
  482.         previous = NULL;
  483.         min = auxiliary1 = p;   // assume that the smallest is the first element (head)
  484.         auxiliary2 = p->next;
  485.  
  486.         while ( auxiliary2 != NULL )
  487.         {
  488.             if( auxiliary2->data < min->data )
  489.             {
  490.                 min = auxiliary2;
  491.                 previous = auxiliary1;
  492.             }
  493.  
  494.             auxiliary1 = auxiliary2;
  495.             auxiliary2 = auxiliary2->next;
  496.         }
  497.         if(previous == NULL)
  498.             p = min->next;
  499.         else
  500.             previous->next = min->next;
  501.  
  502.         min->next = NULL;
  503.  
  504.         if( q == NULL )
  505.             q = min; // moves the element with the least value of data from list p to the beginning of list q
  506.         else
  507.         {
  508.             auxiliary1 = q;
  509.                     // goes through list q to find its last element
  510.             while( auxiliary1->next != NULL )
  511.                 auxiliary1 = auxiliary1->next;
  512.                     // moves the element with the lowest data value from list p to the end of list q
  513.             auxiliary1->next = min;
  514.         }
  515.     }
  516.     return ( q );
  517. } // sort_list_in_ascending_order()
  518.  
  519.  
  520. /*
  521. Sort the list in descending order:
  522. To sort the list, we first scroll through it to find the element
  523. with the highest data value. We then remove that element from the list i
  524. we add it to the beginning of the second list, which was initially blank.
  525. We repeat this process until the initial list is empty.
  526. In the end, all that remains is for the function to return a cursor
  527. to a list in which all the elements have been moved.
  528. */
  529.  
  530. // Sorts the list in descending order
  531. Node *sort_list_in_descending_order( Node *p )
  532. {
  533.     Node *auxiliary1, *auxiliary2, *max, *previous, *q;
  534.  
  535.     q = NULL;                   // new auxiliary list
  536.  
  537.     while( p != NULL )          // to the end of the list
  538.     {
  539.         previous = NULL;
  540.         max = auxiliary1 = p;   // assume that the largest is the first element (head)
  541.         auxiliary2 = p->next;
  542.  
  543.         while ( auxiliary2 != NULL )
  544.         {
  545.             if( auxiliary2->data > max->data )
  546.             {
  547.                 max = auxiliary2;
  548.                 previous = auxiliary1;
  549.             }
  550.  
  551.             auxiliary1 = auxiliary2;
  552.             auxiliary2 = auxiliary2->next;
  553.         }
  554.         if( previous == NULL )
  555.             p = max->next;
  556.         else
  557.             previous->next = max->next;
  558.  
  559.         max->next = NULL;
  560.  
  561.         if( q == NULL )
  562.             q = max; // moves the element with the highest data value from list p to the beginning of list q
  563.         else
  564.         {
  565.             auxiliary1 = q;
  566.                     // goes through list q to find its last element
  567.             while( auxiliary1->next != NULL )
  568.                 auxiliary1 = auxiliary1->next;
  569.                     // moves the element with the highest data value from list p to the end of list q
  570.             auxiliary1->next = max;
  571.         }
  572.     }
  573.     return ( q );
  574. } // sort_list_in_descending_order()
  575.  
  576.  
  577. // Creates a list of 10 nodes to avoid individually entering nodes (list elements)
  578. void make_list_of_n_int( int n )
  579. {
  580.     int i;
  581.  
  582.     delete_all_nodes();         // Deletes all the nodes of the list and frees up the memory that the nodes occupy
  583.                                 // next if needed only if we don't call delete_all_nodes() first
  584.     if( head == NULL ){         // if there are no members in the list ie if the list is empty
  585.         for( i=1; i<=n; i++ ){
  586.  
  587.             newNode=(Node*)malloc(sizeof(Node));    // reserve memory for newNode
  588.             if( newNode == NULL ) {
  589.                 printf("\n Memory allocation error! \n");
  590.                 exit(2);
  591.             }
  592.  
  593.             newNode->data = i;
  594.             newNode->next = NULL;   // newNode is the new node and points to NULL for now
  595.  
  596.                                 // add the formed i-th node to the end of the list
  597.             if( head == NULL ){ // if there are no members in the list ie if the list is empty
  598.                 head=newNode;   // then that newly entered member newNode becomes the start of the list (head)
  599.             }                   // (and is also the end of the list because it is the only one)
  600.             else{               // if there are members in the list ie if the list is not empty
  601.                 cur=head;       // let's get to the first member of the list
  602.  
  603.                 while(cur->next!=NULL){ // until the last member of the list is reached
  604.                     cur=cur->next;      // move on to the next member of the list
  605.                 }
  606.                                 // now the current member (cur) is the last member of the list,
  607.                 cur->next=newNode;  // and he should point to the newly added node newNode
  608.             } // if( head == NULL )
  609.         } // for( i=1; i<=n; i++ )
  610.     } // if( head == NULL )
  611.     else {
  612.         printf("\n\n The list is not empty. Delete all members of the list first! \n\n");
  613.         system("PAUSE");
  614.     }
  615. } // make_list_of_n_int()
  616.  
  617.  
  618. /*
  619. We move around the list from head to right.
  620. First is the current element head and the previous element is NULL.
  621. Then, at the end of the list, we repeat:
  622.               next = current-> next; // next is the one shown by current
  623.     current-> next = previous; // current points to the previous one
  624.           previous = current; // previous becomes current
  625.            current = next; // current becomes next (go to next element)
  626. Rotate the list order:
  627. In order to rotate the order in the list, it is necessary that
  628. for each element we know the pointers to its predecessor and follower.
  629. We then declare the current element a precursor,
  630. and his follower for current.
  631. */
  632.  
  633. // Reverse the list node order
  634. Node *reverse_order( Node *p )
  635. {
  636.     Node *previous, *current, *next;
  637.  
  638.     current = p;                // current is head, the first element in the list
  639.     previous = NULL;            // initial value for previous
  640.  
  641.     while( current != NULL )    // from head to end of list
  642.     {
  643.         next = current->next;   // next is the one shown by current
  644.         current->next = previous;   // current now points to the previous one
  645.         previous = current;     // previous becomes current
  646.         current = next;         // current becomes next (go to next element)
  647.     }
  648.  
  649.     return previous;            // returns previous because it is now the head (first element) of the list
  650. } // reverse_order()
  651.  
  652.  
  653. /*
  654. To insert a new element into a ascending (growing) sorted list:
  655. To insert a new element into a previously sorted sheet,
  656. we compare in sequence the data in the list with the data value of the newNode element.
  657. This process is repeated until we get a pointer to the element
  658. which is in front of an element whose data is larger than the data in the newNode element.
  659. */
  660. // Inserts a new element into the ascending (growing) sorted list
  661. Node *insert_in_ascending_sorted_list( Node *p, int x )
  662. {
  663.     Node *current, *previous, *auxilary;
  664.  
  665.     current = p;
  666.     previous = NULL;
  667.  
  668.     while( current->data < x )
  669.     {
  670.         previous = current;
  671.  
  672.         if ( current->next != NULL )
  673.                 current = current->next;
  674.         else
  675.             break;
  676.     }
  677.  
  678.     auxilary = (Node *) malloc( sizeof(Node) );
  679.     if( auxilary == NULL )
  680.     {
  681.         printf("\n Memory allocation error! \n");
  682.         exit(3);
  683.     }
  684.  
  685.     if ( previous == NULL )     // the element x will be inserted at the beginning of the list
  686.     {
  687.         auxilary->data = x;
  688.         auxilary->next = p;
  689.         p = auxilary;
  690.     }
  691.     else
  692.     {
  693.         auxilary->data = x;
  694.         auxilary->next = previous->next;
  695.         previous->next = auxilary;
  696.     }
  697.     return( p );
  698. } // insert_in_ascending_sorted_list
  699.  
  700.  
  701. /*
  702. Inserting a new element in a descending sorted list:
  703. To insert a new element into a previously sorted list,
  704. we compare in sequence the data in the list with the data value of the newNode element.
  705. This process is repeated until we get a pointer to the element
  706. which is behind an element whose data is larger than the data in the newNode element.
  707. */
  708. // Inserts a new element into the descending sorted list
  709. Node *insert_in_descending_sorted_list( Node *p, int x )
  710. {
  711.     Node *current, *previous, *auxilary;
  712.  
  713.     current = p;
  714.     previous = NULL;
  715.  
  716.     while( current->data > x )
  717.     {
  718.         previous = current;
  719.  
  720.         if ( current->next != NULL )
  721.                 current = current->next;
  722.         else
  723.             break;
  724.     }
  725.  
  726.     auxilary = (Node *) malloc( sizeof(Node) );
  727.     if( auxilary == NULL )
  728.     {
  729.         printf("Memory allocation error! \n");
  730.         exit(4);
  731.     }
  732.  
  733.     if ( previous == NULL )     // the element x will be inserted at the beginning of the list
  734.     {
  735.         auxilary->data = x;
  736.         auxilary->next = p;
  737.         p = auxilary;
  738.     }
  739.     else
  740.     {
  741.         auxilary->data = x;
  742.         auxilary->next = previous->next;
  743.         previous->next = auxilary;
  744.     }
  745.     return( p );
  746. } // insert_in_descending_sorted_list()
  747.  
  748.  
  749. // Meny for node sorting
  750. int node_sorting_meny(void)
  751. {
  752.     int choice, x, y;
  753.  
  754.     while(1){
  755.         system("CLS");
  756.         print_list();
  757.  
  758.     printf("\n\n +-------------------------------------------------------+ \n");
  759.         printf(" |                                                       | \n");
  760.         printf(" |      SORTING THE LIST that has %2d nodes                \n", count_list_elements() );
  761.         printf(" |                                                       | \n");
  762.         printf(" +-------------------------------------------------------+ \n");
  763.         printf(" |                                                       | \n");
  764.         printf(" |  1 - Sort the list in ascending order                 | \n");
  765.         printf(" |                                                       | \n");
  766.         printf(" |  2 - Sort the list in descending order                | \n");
  767.         printf(" |                                                       | \n");
  768.         printf(" |  3 - Inserting a new node into ascending sorted list  | \n");
  769.         printf(" |                                                       | \n");
  770.         printf(" |  4 - Inserting a new node into descending sorted list | \n");
  771.         printf(" |                                                       | \n");
  772.         printf(" |  0 - Exit                                             | \n");
  773.         printf(" |                                                       | \n");
  774.         printf(" +-------------------------------------------------------+ \n");
  775.  
  776.         printf("\n\t Choice (0-4): ");
  777.         scanf("%d", &choice);
  778.  
  779.         switch(choice){
  780.             case  1:                    // Sort the list in ascending order
  781.                      head = sort_list_in_ascending_order( head );
  782.                     break;
  783.             case  2:                    // Sort the list in descending order
  784.                      head = sort_list_in_descending_order( head );
  785.                     break;
  786.             case  3:                    // Inserting a new node into ascending sorted list
  787.                     printf("\n\n Enter the value of the new element: x = ");
  788.                     scanf("%d",&x);
  789.                     head = insert_in_ascending_sorted_list( head, x );
  790.                     break;
  791.             case  4:                    // Inserting a new node into descending sorted list
  792.                     printf("\n\n Enter the value of the new element: x = ");
  793.                     scanf("%d",&x);
  794.                     head = insert_in_descending_sorted_list( head, x );
  795.                     break;
  796.             case  0:                    // Exit
  797.                     return 0;
  798.                     break;
  799.             default :
  800.                     printf("\n\n \t You have to choose (0-4) ! \n\n");
  801.                     break;
  802.         } // switch(choice)
  803.     } // while(1)
  804. } // node_sorting_meny()
  805.  
  806.  
  807. // Meny for deleting nodes
  808. int node_deleting_meny(void)
  809. {
  810.     int choice, x, y;
  811.  
  812.     while(1){
  813.         system("CLS");
  814.         print_list();
  815.  
  816.     printf("\n\n +-------------------------------------------------------+ \n");
  817.         printf(" |                                                       | \n");
  818.         printf(" |      DELETE NODES OF LIST that has %2d elements         \n", count_list_elements() );
  819.         printf(" |                                                       | \n");
  820.         printf(" +-------------------------------------------------------+ \n");
  821.         printf(" |                                                       | \n");
  822.         printf(" |  1 - full list (all nodes in the list)                | \n");
  823.         printf(" |                                                       | \n");
  824.         printf(" |  2 - head       (first in the list)                   | \n");
  825.         printf(" |                                                       | \n");
  826.         printf(" |  3 - tail       (last in the list)                    | \n");
  827.         printf(" |                                                       | \n");
  828.         printf(" |  4 - first with value x                               | \n");
  829.         printf(" |                                                       | \n");
  830.         printf(" |  5 - first k with the value x                         | \n");
  831.         printf(" |                                                       | \n");
  832.         printf(" |  6 - all with the value x                             | \n");
  833.         printf(" |                                                       | \n");
  834.         printf(" |  7 - all bigger than x                                | \n");
  835.         printf(" |                                                       | \n");
  836.         printf(" |  8 - all less than x                                  | \n");
  837.         printf(" |                                                       | \n");
  838.         printf(" |  9 - all in interval [x,y]                            | \n");
  839.         printf(" |                                                       | \n");
  840.         printf(" | 10 - element with order number k                      | \n");
  841.         printf(" |                                                       | \n");
  842.         printf(" | 11 - all even                                         | \n");
  843.         printf(" |                                                       | \n");
  844.         printf(" | 12 - all odd                                          | \n");
  845.         printf(" |                                                       | \n");
  846.         printf(" |  0 - Exit                                             | \n");
  847.         printf(" |                                                       | \n");
  848.         printf(" +-------------------------------------------------------+ \n");
  849.  
  850.         printf("\n\t Choice (0-12): ");
  851.         scanf("%d", &choice);
  852.  
  853.         switch(choice){
  854.             case  1:                    // full list (all nodes in the list)
  855.                     delete_all_nodes();
  856.                     break;
  857.             case  2:                    // head       (first in the list)
  858.                     delete_first();
  859.                     break;
  860.             case  3:                    // tail       (last in the list)
  861.                     delete_last();
  862.                     break;
  863.             case  4:                    // first with value x
  864.                     printf("\n\n Enter the value of the node whose first occurrence you are deleting: ");
  865.                     scanf("%d", &x );
  866.                     delete_first_with_value_x( x );
  867.                     break;
  868.             case  5:                    // first k with the value x
  869.  
  870.                     break;
  871.             case  6:                    // all with the value x
  872.                     printf("\n\n Enter the value of the node whose all occurrences will be deleted: ");
  873.                     scanf("%d", &x );
  874.                     delete_all_with_value_x( x );
  875.                     break;
  876.             case  7:                    // all bigger than x
  877.  
  878.                     break;
  879.             case  8:                    // all less than x
  880.  
  881.                     break;
  882.             case  9:                    // all in interval [x,y]
  883.  
  884.                     break;
  885.             case 10:                    // element with order number k
  886.                     printf("\n\n Enter the number of the item you are deleting, k = ");
  887.                     scanf ("%d",&x);
  888.                     head = delete_node_with_ordinal_number_k( head , x );
  889.                     break;
  890.             case 11:                    // all even
  891.  
  892.                     break;
  893.             case 12:                    // all odd
  894.  
  895.                     break;
  896.             case  0:                    // Exit
  897.                     return 0;
  898.                     break;
  899.             default :
  900.                     printf("\n\n \t You have to choose (0-12) ! \n\n");
  901.                     break;
  902.         } // switch(choice)
  903.     } // while(1)
  904. } // node_deleting_meny()
  905.  
  906.  
  907.  
  908.  
  909. // Main meny
  910. int main(void)
  911. {
  912.     int choice, x;
  913.  
  914.     make_list_of_n_int(10);
  915.  
  916.     while(1){
  917.         system("CLS");
  918.         //print_list_with_pointers();
  919.         print_list();
  920.  
  921.     printf("\n\n +-------------------------------------------------------+ \n");
  922.         printf(" |                                                       | \n");
  923.         printf(" |      WORK WITH LIST that has %2d elements               \n", count_list_elements() );
  924.         printf(" |                                                       | \n");
  925.         printf(" +-------------------------------------------------------+ \n");
  926.         printf(" |                                                       | \n");
  927.         printf(" |  1 - New node at the beginning of the list            | \n");
  928.         printf(" |                                                       | \n");
  929.         printf(" |  2 - New node after node whose value is x             | \n");
  930.         printf(" |                                                       | \n");
  931.         printf(" |  3 - New node at the end of the list                  | \n");
  932.         printf(" |                                                       | \n");
  933.         printf(" |  4 - Delete nodes ( meny )                            | \n");
  934.         printf(" |                                                       | \n");
  935.         printf(" |  5 - Reverse the list node order                      | \n");
  936.         printf(" |                                                       | \n");
  937.         printf(" |  6 - Sorting nodes ( meny )                           | \n");
  938.         printf(" |                                                       | \n");
  939.         printf(" |  7 - Make a new list                                  | \n");
  940.         printf(" |                                                       | \n");
  941.         printf(" |  0 - End of work                                      | \n");
  942.         printf(" |                                                       | \n");
  943.         printf(" +-------------------------------------------------------+ \n");
  944.  
  945.         printf("\n\t Choice: (0-7): ");
  946.         scanf("%d", &choice);
  947.  
  948.         switch(choice){
  949.             case 1: add_at_begin();                 // New node at the beginning of the list
  950.                     break;
  951.             case 2: insert_after_x();               // New node after node whose value is x
  952.                     break;
  953.             case 3: add_to_end();                   // New node at the end of the list
  954.                     break;
  955.             case 4: node_deleting_meny();           // Delete nodes ( meny )
  956.                     break;
  957.             case 5: head = reverse_order( head );   // Reverse the list node order
  958.                     break;
  959.             case 6: node_sorting_meny();            // Sorting nodes ( meny )
  960.                     break;
  961.             case 7: make_list_of_n_int(10);         // Make a new list
  962.                     break;
  963.             case 0:                                 // End of work
  964.                     return(0);
  965.                     break;
  966.             default :
  967.                     printf("\n\n \t Morate izabrati (0-7) ! \n\n");
  968.                     break;
  969.         } // switch(choice)
  970.     } // while(1)
  971.  
  972.     printf("\n\n");
  973.     return 0;
  974.  
  975. } // main())
RAW Paste Data Copied