Reverse Linked List - Recursion

2 weeks back I was asking someone to write a code for Reversing a Linked List. I just tried one with Recursion:

 #include <iostream>
 
 using namespace std;
 
 struct node {
     int data;
     struct node *next;
 };
 
 typedef struct node NODE;
 
 class linklist {
     private:
         NODE *head;    
     public:
         linklist():head(NULL) {}
         void push(int);
         void display();
         void reverse();
         NODE* reverse_driver(NODE*, NODE*);
 };
 
 void linklist::push(int data) {
     NODE *tmp = new NODE;
     tmp->data = data;
     tmp->next = NULL;
 
     if (head == NULL) {
         head = tmp;
     } else {
         NODE *curr = head;
         while (curr->next != NULL) {
             curr = curr->next;
         }
         curr->next = tmp;
     }
 }
 
 void linklist::display() {
     NODE *curr = head;
     cout<<"HEAD: ";
     while (curr != NULL) {
         cout<<curr->data<<"->";
         curr = curr->next;
     }
     cout<<"NULL\n";
 }
 
 void linklist::reverse() {
     if (head != NULL) {
         NODE *last = reverse_driver(head, head->next);
         // make the last_node->next to NULL
         head->next = NULL;
 
         // change the head to the last
         head = last;
     } 
 }
 
 NODE* linklist::reverse_driver(NODE *currnode, NODE *nextnode) {
     if (nextnode != NULL) {
         NODE *last = reverse_driver(nextnode, nextnode->next);
         nextnode->next = currnode;
         return last;
     } else {
         // Last Node - to be set as Head node
         return currnode;
     }
 }
 
 int main () {
     linklist ll;
 
     ll.push(10);
     ll.push(20);
     ll.push(30);
     ll.push(40);
 
     ll.display();
     ll.reverse();
     ll.display();
     return 0;
 }
 

Convert Code to HTML - Perl

Convert the Code into HTML - Perl:

 #! /usr/bin/perl
 use warnings;
 use strict;
 
 my $lineno=0;
 
 print "<pre>";
 foreach my $strline (<STDIN>) {
     print "<a name=\"line$lineno\">";
     printf "%3d", $lineno;
     print "</a>";
     print " <font color=\"#0000FF\">";
     chomp($strline);
     $strline =~ s/&/&amp/g;
     $strline =~ s/</&lt/g;
     $strline =~ s/>/&gt/g;
     $strline =~ s/\t/    /g;
     print $strline;
     print "</font>";
     print "<br>";
     $lineno++;    
 }
 
 print "</pre>\n";
 

If you swap the substitutions statements are shuffled, you will not get the desired output.

Bignum For C++

Sometime back I was solving problems from Project Euler(http://projecteuler.net/). I was using an array of tools like Sage, Mathematica, bc (arbitrary precision calculator - yet powerful)..

But, most of the problems needs a bit of computation(programming). So, I started searching for a BigNum library for my favorite programming language C++. Eventually, I found one GMP (GNU Multi Precision) library. Later on I found that GMP is one of the fastest BigNum library available and it is also the backbone for most of the tools I was using for solving Euler problems.

GMP library can be got from http://gmplib.org/. If you need C++ extension for the GMP library, you configure it with the following command:

./configure --prefix=/usr/local --enable-cxx

This command will create 2 library files (libgmp.so and libgmpxx.so) and copy it to the /usr/local/lib location.

Don't forget to add the path to your LD_LIBRARY_PATH. Enjoy BigNUm computing :-)

Trailing Zeros of a Factorial

 /*
  * Problem: To find the number of trailing zeros in a factorial (n)
  * URL: http://www.codechef.com/problems/FCTRL/
  * Input: n
  * Output: No. of Trailing Zeroes
  * Formula: E(sigma) limit (i=1..k) = [n/5^i]
  * k is chosen such that 5^k+1 < n
  * Execution Time: 1.49 (Alloted 8 Sec)
  */
 
 #include <iostream>
 
 using namespace std;
 
 int main() {
     int n, trail_zeros;
     long factor5, num;
     
     cin>>n;
     for (int i=0; i<n; i++) {
         trail_zeros = 0;
         factor5 = 5;
         cin>>num;
         while (factor5 <= num) {
             trail_zeros += num / factor5;
             factor5 *= 5;
         }
         cout<<trail_zeros<<endl;
         trail_zeros = 0;
     }
     return 0;
 }
 

The Program in bc (An arbitrary precision calculator language):

 define f(x) {
   if (x>1) {
     return (x * f (x-1))
   }
   return (1)
 }
 
 define z(x) {
   if (0 == x) return 0;
   if (0 == x%10) {
     return 1+z(x/10)
   }
   return 0
 }
 
 define trial_zero(x) {
   return z(f(x))
 }
 

Programming Quotes

"Programming is art of expressing solutions to problems so that a computer can execute the solutions." - Bjarne Stroustroup

"Clearly, I reject the view that there is one way that is right for everyone and for every problem." - Bjarne Stroustrup

"Your Quote Here." - Bjarne Stroustrup (Templates Chapter - The C++ Programming Language Book).

Makefile Explained - Part-1

Sorry for a long delay. I was held up tight in my previous project. Now, I have time to breathe, and enjoy the blue sky.

Let is say I have a file hello.cpp, now how we compile it:
c++ -o hello hello.cpp

if you have installed g++:
g++ -o hello hello.cpp

Generic format:

{compiler name} -o {output file} {source file}

-o - option to specify output filename. If we don't specify {output file}, by default the output will be written to "a.out" file.

"a.out" - assembler output

A Simple Makefile:

hello: hello.cpp
{tabspace}g++ -o hello hello.cpp

Output:
$make hello
g++ -o hello hello.cpp
$

Look at the output, when I give "make hello" command, the make command searches the "hello" target in the makefile and executes the command given for "hello" target.

This makefile make our life easier, we don't need to type "g++ -o hello hello.cpp" everytime, instead we can just give "make hello" which will take care of compiling it.

In my next post, we will see how Make utility can make our life more easier.

Pthread Part-1

A Simple Pthread Program:

 #include <stdio.h>
 #include <unistd.h>
 #include <pthread.h>
 
 void *fun(void *args) {
     int i;
 
     for (i=0; i<10; i++) {
         printf("hello world\n");
         sleep(1);
     }
     pthread_exit(NULL);
 }
 
 int main() {
     pthread_t pt_id;
     
     printf("Main: Before Create\n");
     pthread_create(&pt_id, NULL, fun, NULL);
     printf("Main: After Create\n");
     pthread_join(pt_id, NULL);
     printf("Main: After Join\n");
     pthread_exit(NULL);
     return 0;
 }
 

Output:

  
$./pthread1
Main: Before Create
Main: After Create
hello world
hello world
hello world
hello world
hello world
hello world
hello world
hello world
hello world
hello world
Main: After Join
$