Basic functions of link list - Add and print

// Function to add new nodes to the linked list
void add(node * head , int value)
{
   temp = (mynode *) malloc(sizeof(struct node));
   temp->next=(mynode *)0;
   temp->value=value;

   if(head==(mynode *)0)
   {
      head=temp;
      tail=temp;
   }
   else
   {
     tail->next=temp;
     tail=temp;
   }
}

// Function to print the linked list...
void print_list(struct node *head)
{
  mynode *temp;

  printf("\n[%s] -> ", listName);
  for(temp=head;temp!=NULL;temp=temp->next)
  {
    printf("[%d]->",temp->value);
  }

  printf("NULL\n");

}

Function to add node to double link list

2 struct pointers (Double link list)
typedef struct node
{
  int value;
  struct node *next;
  struct node *prev;
}mynode ;

// Function to add a node
void add_node(struct node **head, int value)
{
  mynode *temp, *cur;
  temp = (mynode *)malloc(sizeof(mynode));
  temp->next=NULL;
  temp->prev=NULL;

  if(*head == NULL)
  {
     *head=temp;
     temp->value=value;
  }
  else
  {
   for(cur=*head;cur->next!=NULL;cur=cur->next);
   cur->next=temp;
   temp->prev=cur;
   temp->value=value;
  }
}

Detecting a loop in a linked list (C program)

Brute force method

Have a double loop, where you check the node pointed to by the outer loop, with every node of the inner loop.


typedef struct node
{
  void *data;
  struct node *next;
}mynode;


mynode * find_loop(NODE * head)
{
  mynode *current = head;

  while(current->next != NULL)
  {
    mynode *temp = head;
    while(temp->next != NULL && temp != current)
    {
      if(current->next == temp)
      {
        printf("\nFound a loop.");
        return current;
      }
      temp = temp->next;
    }
    current = current->next;
  }
  return NULL;
}



Visited flag

Have a visited flag in each node of the linked list. Flag it as visited when you reach the node. When you reach a node and the flag is already flagged as visited, then you know there is a loop in the linked list.

Fastest method

Have 2 pointers to start of the linked list. Increment one pointer by 1 node and the other by 2 nodes. If there's a loop, the 2nd pointer will meet the 1st pointer somewhere. If it does, then you know there's one.

Here is some code


p=head;
q=head->next;

while(p!=NULL && q!=NULL)
{
  if(p==q)
  {
    //Loop detected!
    exit(0);
  }
  p=p->next;
  q=(q->next)?(q->next->next):q->next;
}

// No loop.


Examples of printf

19. main()
{
printf("\nab");
printf("\bsi");
printf("\rha");
}

Answer
hai

Explanation
\n - newline
\b - backspace
\r - linefeed 

Comparing floats

Problem
 int main()
{

float me = 1.1;
double you = 1.1;
if(me==you)
printf("I love U");
else
printf("I hate U");
}

Output - I hate U
Explanation
For floating point numbers (float, double, long double) the values cannot be predicted exactly. Depending on the number of bytes, the precession with of the value represented varies. Float takes 4 bytes & long double takes 10 bytes. So float stores 0.9 with less precision than long double. 

Solutions 

//compares if the float f1 is equal with f2 and 

//returns 1 if true and 0 if false
 int compare_float(float f1, float f2)
 {
  float precision = 0.00001;
  if (((f1 - precision) < f2) && 
      ((f1 + precision) > f2))
   {
    return 1;
   }
  else
   {
    return 0;
   }
 }

You can set the precision of the comparison between the 

floating point numbers by changing the "precision" variable.

Calling the function:

 //we compare our numbers
 if (compare_float(x1,x2))
 {
   //do something if equal
 }
 else
 {
   //do something if not equal
 }

Method2 - using fabs i.e.  epsilon absolute error
if (fabs(me - you) < 0.00001)
printf("I love U");
else
printf("I hate U"); 

Absolute error calculations have their place, but they aren’t what is most often used. When talking about experimental error it is more common to specify the error as a percentage. Absolute error is used less often because if you know, say, that the error is 1.0 that tells you very little. If the result is one million then an error of 1.0 is great. If the result is 0.1 then an error of 1.0 is terrible.

C aptitude 1

void main()

{

int const * p=5;

printf("%d",++(*p));

}

Answer:
Compiler error: Cannot modify a constant value.
Explanation:
p is a pointer to a "constant integer". But we tried to change the value of the "constant integer".


 

Solution - #104 Project Euler

//p104
// Find the Fibonacci sequence for which the first nine digits and the last nine digits are 1-9 pandigital

#include
#include

char number_string[100000];

char isPandigital( unsigned long int num )
{
   if ( num < 123456789 )
   {
      return 0;
   }

   char num_of_unique_digits = 0;

   char number_array[9];

   unsigned long int temp = num;

   int i;
   int j;

   for ( i = 0; i < 9; i++ )
   {
      number_array[i] = temp - ((temp / 10) * 10);
      if ( number_array[i] == 0 )
      {
         return 0;
      }

      temp /= 10;
   }

   char is_unique = 1;

   for ( i = 0; i < 9; i++ )
   {
      for ( j = 0; j < 9; j++ )
      {
         if ( i != j )
         {
            if ( number_array[i] == number_array[j] )
            {
               is_unique = 0;
            }
         }
      }

      if ( is_unique )
      {
         num_of_unique_digits++;
      }

      is_unique = 1;
   }

   if ( num_of_unique_digits == 9 )
   {
      return 1;
   }
   else
   {
      return 0;
   }
}

int numOfDigits( mpz_t num )
{
   int num_of_digits = 0;

   char *number_pointer;
   mpz_get_str( number_string, 10, num );

   number_pointer = number_string;

   while( *number_pointer != '\0' )
   {
      num_of_digits++;
      number_pointer++;
   }

   return num_of_digits;
}

char areBothSidesPandigital( mpz_t num )
{
   mpz_t mod;
   mpz_init_set_str( mod, "1000000000", 10 );

   mpz_t temp;
   mpz_init( temp );

   unsigned long int number_group = 0;

   mpz_mod( temp, num, mod );

   number_group = mpz_get_ui( temp );

   if ( isPandigital( number_group ) )
   {
      mpz_ui_pow_ui( temp, 10, (numOfDigits( num ) - 9) );

      mpz_tdiv_q( temp, num, temp );

      number_group = mpz_get_ui( temp );

      if ( isPandigital( number_group ) )
      {
         mpz_clear( temp );
         mpz_clear( mod );

         return 1;
      }
   }

   mpz_clear( temp );
   mpz_clear( mod );

   return 0;
}

int main()
{
   mpz_t num1;
   mpz_init_set_str( num1, "1", 10 );

   mpz_t num2;
   mpz_init_set_str( num2, "1", 10 );

   char add_to_first = 1;
   char are_we_up_to_ten_digits = 0;
   int current_sequence = 2;

   while( 1 )
   {
      current_sequence++;

      if ( add_to_first )
      {
         mpz_add( num1, num1, num2 );
         add_to_first = 0;
      }
      else
      {
         mpz_add( num2, num1, num2 );
         add_to_first = 1;
      }

      if ( add_to_first )
      {
   //      printf( "\nNumber of digits: %d\n", numOfDigits( num2 ) );
         if ( areBothSidesPandigital( num2 ) )
         {
            printf( "\n\nThe double pandigital Fibonacci sequence was found at: %d\n\n", current_sequence );
            return 0;
         }
      }
      else
      {
         //printf( "\nNumber of digits: %d\n", numOfDigits( num1 ) );
         if ( areBothSidesPandigital( num1 ) )
         {
            printf( "\n\nThe double pandigital Fibonacci sequence was found at: %d\n\n", current_sequence );
            return 0;
         }
      }
   }

   //mpz_ui_pow_ui( temp, base, exp );

   //mpz_out_str( out_file, 10, temp );

   //printf("\n");
   //mpz_out_str( stdout, 10, temp );
   //printf("\n\n");

   printf("\n\n");

   return 0;
}