Basic question -3 (simple recursion)

This time  we are going to discuss simple recursion .
  what is recursion : It is simply a solving technique to solve function which uses its previous volue.
                         example : Xn = Xn-1 + 2.

recursion

 It is very  basic example.we can use this technique  in computer science to solve such type of problem very effectivelly . example traversal of tree, find factorial etc.

So your Today's challenge is : Make a program to take integer with any no of digits as input & find sum of digits of that integer using  :  2 method

Merge sort

Suppose the array A containing  8 elements {5, 2, 4, 7, 1, 3, 2, 6 }.
How it will be sorted see this image.

Merge Sort

download this PPT for all type of sorting : sorting.ppt

Time complexity = Q(n log n)

C program :

Simple binary tree (recursive)

the following program uses recursion to input nodes and also displays inorder preorder and postorder forms in the output .
 Procedure of insertion is simple first input a node and then ask the user whether the tree has left and right child
 if yes call the function again with pointer to left or right child of the inserted node.

OUTPUT come LIKE this :

C program :

Traverse tree without recursion

IT is tough to traverse tree without recursion . It needed strong concept that how things going on during traversal. Anyway you can easily dit using stack. see this video .......

 I your doubt is steel not clear ..see program carefully & do all operation of program step by step

C program :

Binary Search Tree

Binary search Tree

In Binary Search Tree & Left child of each node is smaller than parent node.& right child of each node is bigger than root node.And it is applicable to each node of tree.

TRAVERSAL :-

INORDER : It traverse as Left then Node then Right (LNR).

PREORDER: It traverse as NODE then LEFT then RIGHT (NLR). 

POSTORDER: It traverse as Left then Right then Node (LNR).

                      C PRogram :

Input restricted Dequeue in One Way link list

Dequeue is basically queue .there is one difference b/w dequeue  & queue .

In queue insertion take place at end & deletion at beginning But in dequeue Insertion & deletion can take place at both end 

BUT here we wan't to create input restricted dequeue .
what it means : Dequeue with input restricted to only one end . at beginning or at end.
In this we make a dequeue with input restricted at end only.

     C program :

Priority queue IN array

 a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.(wiki/Priority_queue).

For better understanding . we provide you power point presentation.

PPT. presentation for queue

concept :-

 make a globle array with all data = -1   
 each row represent priority i.e 1st row contain element with priority 1  
 & empty node have volue = -1
 

Check Palindrome using double link list

Palindrome  is A palindrome is a word, phrase, number, or other sequence of symbols or elements, whose meaning may be interpreted the same way in either forward or reverse direction.(wiki answer).
Two check given string is palindrome or not.It is very easy if we use double link list.

Procedure :-

::-  insert each char of string in double link list with each node contain only one char.

::- intialise "HEAD" to first node & "TELL" to last node.

::- check data at first node & last node then increment head & decrement in tell than check     again untill any mismatch found or they reaches to mid of list

How to reverse one way link list

Reversing link one way list is also a tough job for beginners. So to make it easy to understand we provide you A Flash.. IT mention each steps to followed to do this.
Download This flash tutorial

            C program :-

Double link list

Double link list is also just modified form of one way link list. In one way list we can travel in one direction only but in double link list we can travel in both direction front & back. To make it possible each  node point to next node & also node just before that node.
Back of first node & front of last node is initialise To NULL.

double link list

                                              C code :-

Circular Link list

Circular link list is special case of  normal (one way link list) in this last node point to first node.whether in one way link list last node point to NULL.
This special property make one way link list circular.
About all operation of circular link list is similar to one way list .only few changes occurred . You can see this in C code.

circular link list

                                           C code :-

Generate random no & push it stack

This is very basic program .We have to generate few random no. & check no is even or odd. If even than push it to stack 1 else IF no is odd push it to stack 2. Than print stack 1 & stack 2.

             C Program :

We use pointer to pass array & for push operation.

Creating dynamic array

    In this programm we Creating array of given size dynamically   & doing operation of insertion & deletion

 Must include header " malloc.h ".

     For better description see " C program " carefully.

                                                            C code :

Implementing 2 stack in single link list

   We can Implement 2 stack in single array . Take TOP1 at beginning of array. Take TOP2 at end of array.

                                                                 C code :

Stack implementation in array

 Stack is a data structure in which addition of new element (PUSH operation) or deletion (POP operation)
of an existing element always takes place at the same END. This end is often known as TOP of stack.

stack use First in First Out principal . i.e. each new element inserted at end of list (i.e. at TOP). & deletion also occurred ot end of  List (i.e at TOP).

C code ::

Operation on One way link list

In one way Link List we can travel only along forward direction.

operation on one way link list done in this program:-

INSERTION :- we can insert data at end of list (append) or at beginning of list or at given postion

DELETION :- similarly like insertion deletion can take place at beginning ,at end ,at given position or delete a particular data from the list (in this program we use only last one)

NOTE : to understand algorithm much better download this flash tutorial data_structure

C code :

Create link list in sorted order

    This is a link list which take input from user & put in list in such a way that list after each insertion remain     sorted.
    for this simply we insert each input at appropriate postion. such that data remain sorted.
    i.e if we insert data (let sey "KEY") it will inserted at postion such that data just after that is bigger than KEY & data just before key is smaller than KEY

C code ::

Bubble sort in c

Bubble sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort. Although the algorithm is simple, most of the other sorting algorithms are more efficient for large lists.

C code ::