Algorithms

Count number of nodes in Linked List

http://install4install.com

Counting refers to calculating number of nodes present in linked list.

Counting

Counting

Program

#include<stdio.h>
struct node
{
    int item;
    struct node *next
};
int main()
{
    struct node *start,*list,*temp;
    int i;

    start = (struct node *)malloc(sizeof(struct node));
    list = start;
    start->next = NULL;
    for(i=1;i<5;i++)
    {   
        list->item = i;
        list->next = (struct node *)malloc(sizeof(struct node));
        list = list->next;
       }
    list->next = NULL;
    temp = start;
    int length =0;
    while(temp!=NULL)//Fig 2
    {

    	if (temp->next == NULL) 
    	  {
           break;
    	  }
         else
        {
        length++;
        temp=temp->next;
        }
    }    

printf("Length of Linked List : %d \n",length);
printf("Elements of linked lists are :\n");
   while(start != NULL)
    {   
    	if (start->next == NULL) 
    	  {
           break;
    	  }
        printf("%d\n",start->item);
        start = start->next;
    } 
return 0;
}

Run

Illustration of Program

  • Refer Linked Lists for creation and display of linked list.
  • temp = start which means temp =140(Fig 1)
Screen Shot 2014-04-07 at 1.48.39 PM

Fig 1 : Linked List

Screen Shot 2014-04-07 at 2.14.02 PM

Fig 2 : Working of Program


Short URL: http://tinyit.cc/e0eb10

Deletion of element from array

Deleting  an  element means to remove element from the array.It is quite easy to delete the element from the end of array.On the controversial side,what is needed to delete the element from our  desired location  like somewhere in the middle of array .Deleting an element requires that all the subsequent elements must be moved one location up to keep the order of array.

The following program is to delete element from the end of array.

Program

#include <stdio.h>

int main()
{
   int arr[10] = {10,20,30,40,50};
   int pos;
   int i;
   printf("Enter the location where you wish to delete element\n");
   scanf("%d", &pos);
   if ( pos > 4 )
      printf("Deletion not possible.\n");
   else
   {
     for ( i = pos  ; i < 4 ; i++ )
     {
     a[i] = a[i + 1];
     }
     printf("Resultant array is\n");
     for( i = 0 ; i < 4 ; i++ )
     {
      printf("%d\t", arr[i]);
      }
   }  

return 0;
}
Run

Illustration of Program

  • Array arr  of  integer type and size 10 is initialized with values 10,20,30,40,50.(Fig 1)
  • pos is the location from where user wants to delete the element.Say user enters 2.
  • The location of elements varies from 0 to 4 as 5 values are initialized.If user enters any location greater than 5,then deletion is not possible since element is not present at that location.
  • Working of for loops is explained in Fig 2.
Fig 1 : Elements of array before deletion.

Fig 1 : Elements of array before deletion.

Fig 2 : Working of for loops

Fig 2 : Working of for loops

Fig 3 :Elements after deletion of 30 at 2 position.

Fig 3 :Elements after deletion of 30 at 2 position.

 

 


Short URL: http://tinyit.cc/94100c

Insertion of element in an array

Inserting an element means to embed element in the array.It is quite easy to insert the element in the end of array provided sufficient memory locations are present to accommodate the additional element.On the controversial side,what is needed to insert the element at our desired location like somewhere in the middle of array .All the elements( after insertion at requisite location) must be moved downwards to welcome new element and to keep their order.By the word downward I mean moving to larger subscripts.

Ways to insert an element in the array

  • In the beginning of array
  • In the end of array
  • At any location of user choice

In the beginning of array

The following program is to insert element in the beginning of array.

Program

#include<stdio.h>

 int main()
 {
 int a[10];
 int i,k;
 int element;
 //printf("enter array elements:");
 for(i=0;i<5;i++)
 {
 scanf("%d",&a[i]);
 }
 //printf("enter the element you want to insert:");
 scanf("%d",&element);
 for(k=5;k>0;k--)
 a[k]=a[k - 1];
 a[0]=element;//Fig 3
  printf("\n");
 for(i=0;i<6;i++)//display the result
 printf("%d \t",a[i]);
return 0;
 }

Run

Illustration of Program

  • Array a of integer type and size 10 is declared.
  • i is set to 0 and condition of for loop is i <5 which means that we can enter up to 5 values in array.The remaining memory locations are to adjust the new elements if user wants to insert at later stage.
  • scanf reads 5 values  from the user .If user gives more than 5 values then those will be simply discarded as loop runs only 5 times.Control exits the loop when i becomes equal to 5. Say user enters 10,20,30,40,50(Fig 1)
  • Say user want to insert 45 in the beginning of array.
  • Working of for loop is explained in the Fig 2.
Screen Shot 2014-03-20 at 3.31.20 PM

Fig 1 : Elements of array before insertion

Screen Shot 2014-03-20 at 3.32.56 PM

Fig 2 : Working of Program.

Screen Shot 2014-03-20 at 3.33.11 PM

Fig 3 : Insertion at the beginning of array.

 

In the end of array

The following program is to insert element in the end of array.

Program

#include<stdio.h>

 int main()
 {
 int a[10];
 int i;
 int element;
 //printf("enter array elements:");
 for(i=0;i<5;i++)
 scanf("%d",&a[i]);
 //printf("enter the element you want to insert:");
 scanf("%d",&element);
 a[5]=element;//Fig 4
 for(i=0;i<6;i++)
 printf(" %d",a[i]);
 return 0;
 }

Run

Illustration of Program

  • Array a of integer type and size 10 is declared.
  • i is set to 0 and condition of for loop is i <5 which means that we can enter up to 5 values in array.The remaining memory locations are to adjust the new elements if user wants to insert at later stage.
  • scanf reads 5  values  from the user .If user gives more than 5 values then those will be simply discarded as loop runs only 5 times.Control exits the loop when i becomes equal to 5. Say user enters 10,20,30,40,50(Fig 3)
  • Say user wants to insert 65 at the end of array.
  • The elements are located till 4 index.
  • In order to insert element at the last,we give value of element to value of  5th index.(a[5] = element).(Fig 4)
  • All the elements are displayed through printf.
Screen Shot 2014-03-20 at 3.31.20 PM

Fig 3: Elements of array before insertion

Fig 4 : Insertion in the end of array

Fig 4 : Insertion at the end of array

 

At any location of user choice

The following program is to insert element at any location.

Program

#include<stdio.h>

 int main()
 {
 int a[6];
 int i,k;
 int element_choice;
 int element;
 //printf("enter array elements:");
 for(i=0;i<5;i++)
 {
  scanf("%d",&a[i]);
 }
 //printf("enter the element:");
 scanf("%d",&element);
 //printf("enter the element after which the number has to be inserted:");
 scanf("%d",&element_choice);
 for(i=0;i<5;i++)
 {
 if(a[i]==element_choice)//finding the element
 break;
 }
 for(k=5;k>i;k--)
{
  a[k]=a[k -1];//shifting the element
}
 a[i+1]=element;
 printf("\n");
 for(i=0;i<6;i++)
{ 
 printf("%d \t",a[i]);
}
 return 0;
 }

Run

Illustration of Program

  • Array a of  integer type  and  size 10 is declared.
  •  is set to 0 and condition of for loop is i <5 which means that we can enter up to 5 values in array.The remaining memory locations are to adjust the new elements if user wants to insert at later stage.
  • scanf reads 5 values  from the user .If user gives more than 5 values then those will be simply discarded as loop runs only 5 times.Control exits the loop when i becomes equal to 5. Say user enters 10,20,30,40,50(Fig 5)
  • Say user wants to insert 90 after 30 in array.(Fig 6)
Screen Shot 2014-03-20 at 3.31.20 PM

Fig 5 : Elements of array before insertion

Screen Shot 2014-03-20 at 4.54.13 PM

Fig 6 :Working of Program

Screen Shot 2014-03-20 at 4.54.22 PM

Fig 7 : Insertion at any location of user choice.

 


Short URL: http://tinyit.cc/4088dc

Linear Search

Searching in an array refers to finding the location of a particular element in the given array. It can be done in two ways :

  • Linear Search
  • Binary Search

Linear Search

Searching

Searching

It is done by comparing each and every element of array with the data item for which index needs to be found.The data item is compared with the items from 0 index till the last element of array.If the match is found then the index where items matched is returned to user.

Program

#include <stdio.h>

int main()
{
	int arr[5];
	int i;
	int element;
        //printf("enter the elements of array");	
	for(i=0;i<5;i++)
	{
		scanf("%d \t",&arr[i]);//Fig 1
	}
	// printf("Enter the element for which you want the search the respective index");
	scanf("%d",&element);
	for(i=0;i<5;i++)
	{
		if(arr[i] == element)

		printf("Location of this element is %d",i);
	}

	return 0;
}

Run

Explanation of above Program

  1. arr[5] is declared as an integer array.
  2. i is a variable to be used in for loop.
  3. element is the data item of int type which needs to be searched in array.
  4. scanf inside for loop is used to read all the values of array from user.Say user enters  100 200 130 140 150(Fig 1)
  5. User enters the element to be searched for in the array.Say 140.
  6. for loop starts and the initial value of i is 0,it will enter the loop as it less than 5(Condition is true).For further explanation refer Fig 2.

Fig 1 : An Array

Fig 3 :

Fig 2 :Explanation of Linear Search Program

TipIf element is present at two or more locations,then the respective indices will be returned to user.


Short URL: http://tinyit.cc/0d4829

Traversing an Array

The various operations that are performed on arrays are :

  • Traversal
  • Searching
  • Insertion
  • Deletion
  • Sorting and Merging

Traversing in array

This article explains about how to traverse in an array.

Traversing means to visit/to go/travel across each and every element of an array.

Program

#include<stdio.h>

int main()
{
 int rank[5] = {10,20,30,13,15};
 int i;
 printf("\nThe elements of array are :");
 for(i=0; i<5; i++)
 {
  printf("%d \t", rank[i]); 
 }
return 0;
}

Run

Illustration

  • Integer type array of size 5 is declared with values 10,20,30,13,15(Fig 2).
  • Variable i of int type is declared which is to be used in for loop.
  • The initial value of i=0,rank[0] which is 10 gets traversed.i is incremented by 1.
  • Now i=1,rank[1] = 20 gets traversed.
  • Now i = 2,rank[2] = 30 gets traversed.
  • i = 3,rank[3] = 13 gets traversed.
  • i=4,rank[4] = 15 gets traversed.
  • All the elements of array get displayed on the screen.
Fig 2 : Traversing an Array

Fig 2 : Traversing an Array


Short URL: http://tinyit.cc/c48dd8