C Data Structure

Binary Search Using C Language - It’s Time Complexity And Algorithm

2012-02-27T06:17:00.001+05:30

Here is the Binary search program using C Language

#include < stdio.h>

void bS(int target,int value[],int low,int high)

{

int mid;

if (value[mid]==target)

{

printf("\nValue found.");

return;

}

else if(high< low)

{

printf("\nNot found.");

return;

}

else

{

mid=(low+high)/2;

if(target > value[mid])

low=mid+1;

else if(target< value[mid])

high=mid-1;

bS(target,value,low,high);

}

void main()

{

int array[10] = {2,5,8,12,14,34,36,39,49,59},x,i,low,high;

clrscr();

low=0;

high=9;

printf("\nThe values are:-\n");

for(x=0;x<10;x++)

{

printf( "%d ",array[x]);

}

printf("\nEnter the value to be searched:-");

scanf("%d",&i);

bS(i,array,low,high);

getch();

}

If an array is unsorted and haphazardly constructed then it is better to go for sequential search. But when the array is sorted then binary search will give the best result. The basic conditions for binary searching is that the list must be sorted and the middle element of the list can be directly accessed. In array this is possible, but in case of linked list, the middle element cannot be accessed directly.So in linked list searching binary search cannot be applied.

Algorithm for Binary Search :-

ARR is the array where the values are stored. N is the number elements in the array.VAL is the element to be searched. LOW and HI are two variables storing the lower bound (0) and the upper bound (N-1) of the array.MID is another variable which will hold the middle position of the array and sub-array.

Repeat the following steps while (LOW<=HI)

Set MID=(LOW+HI)/2

If VAL < ARR[MID]

Set HI=MID-1

Else If VAL>ARR[MID]

Set LOW=MID+1

Else

Break the loop

[End of loop]

If VAL=ARR[MID]

Retrun True

Else

Return False

End

Complexity of binary search :-

The complexity of binary search is measured by the number of comparisons to locate an item from a number of elements; say N.I n binary search after each comparison, the size is reduced to half. Suppose we need maximum T comparisons to locate the element from the array, so 2T > N or 2T=N+1.so T=log2N+1.Ignoring the constant 1 ,we can say that T=log2N.So the complexity is O(log2N)

Link List using C

2012-02-16T14:16:00.000+05:30

Traversing a linked list using C Programming Language

In this program we will create five nodes and then the linked list will be traversed one after another to display the value stored within the node.
Our next program will create a linked list ( size depends on the user ) and each node will contain the Name , Surname , Address and Telephone number .Then the user has to enter a Name which will be searched in the linked list. If found the details record against the name will be displayed, otherwise a not found message will be displayed.

# include < stdio.h >
# include < malloc.h >
struct link
{
char name[100];
char surname[100];
char add[100];
long ph;
struct link *next;
};
int x=0;
struct link *node;
void search(char ch[],struct link *n)
{
node=n - > next;
for(; node != NULL; node = node->next)
{
if(strcmp(node-> name,ch)==0)
{
x++;
printf("Surname is %s \n", node->surname);
printf("Address is %s \n",node-> add);
printf("Phone number is %ld \n",node->ph);
}
}
if(x == 0)
printf("Item not found in the list \n");
}
void get(struct link *n)
{
char ch='y';
node=n;
while(ch !='n')
{
node->next = (struct link* ) malloc (sizeof (struct link));
node = node->next;
node->next =NULL;
printf("\n Enter the name: -");
scanf("%s",node->name);
printf("\n Enter the surname: -");
scanf("%s",node->surname);
printf("\n Enter the address: -");
scanf("%s",node->add);
printf("\n Enter the Telephone number: -");
scanf("%ld",&node->ph);
printf("\n Input choice n for break: ");
ch = getche();
}
}
void main()
{
struct link *start=NULL;
char name[15];
clrscr();
get(start);
printf("\nEnter the name to search :");
scanf("%s",name);
search(name,start);
getch();
}

Insertion in a linked list using C Programming Language

A linked list is a dynamic data structure. The number of nodes in a linked list may vary dramatically as elements are inserted or removed from a list. If a list grows ,there must be some mechanism for obtaining empty node. Unlike array , list does not come with a pre supplied set of storage locations.

# include < stdio.h >
# include < malloc.h >
struct link
{
int info;
struct link *next;
};
int i;
int number;
struct link *list=NULL, *P=NULL, *new1;
void create(struct link *n)
{
char ch;
list=n;
printf("\nEnter the value :-");
scanf("%d",&list->info);
list->next=NULL;
printf("\n Input choice n for break: ");
ch = getche();
i = 1;
while(ch != 'n')
{
list->next = (struct link* ) malloc(sizeof(struct link));
list = list->next;
printf("\n Input the node: %d: ", (i+1));
scanf("%d", &list->info);
list->next = NULL;
printf("\n Input choice n for break: ");
ch = getche();
i++;
}
}
void insertion(struct link *n)
{
list=n;
new1 = (struct link* ) malloc(sizeof(struct link));
printf("\n Input the fisrt node value: ");
scanf("%d", &new1->info);
P=new1;
new1->next=n;
list=P;
printf("\nNow displaying the current linked list:-\n");
while(list)
{
printf("%d\n",list->info);
list=list->next;
}
}
void main()
{
struct link *node = (struct link *) malloc(sizeof(struct link));
clrscr();
create(node);
insertion(node);
getch();
}

Binary Search Using C Language

2012-02-10T05:20:00.000+05:30

If in an array, the elements are placed in some order, for example a dictionary then there is an efficient searching algorithm, Binary search. In binary search the array will be reduced to small sub arrays while searching the element. Suppose we are searching an element N from an array ARR. First search for N at the middle of the array. If found then your searching is completed, otherwise check whether N is greater than or less than the middle value of the array. If less, then repeat the above process with first half the array otherwise repeat with the right half the array. This process will continue.

#include < stdio.h>

int bS(int target,int value[],int size)

{

int mid,low=0,hi=size-1;

while(low<=hi)

{

mid=(low+hi)/2;

if(target > value [mid])

low=mid+1;

else if(target< value[mid])

hi=mid-1;

else

break;

}

printf("\After executing the loop , mid=%d, value=%d, targer=%d",mid,value[mid],target);

if(target==value[mid])

return mid;

else

return -1;

}

void main(void)

{

int array[10] = {2,5,8,12,14,34,36,39,49,59},x,i;

clrscr();

printf("\nThe values are:-\n");

for(x=0;x<10;x++)

{

printf( "%d ",array[x]);

}

printf("\nEnter the value to be searched:-");

scanf("%d",&i);

x=bS(i,array,10);

if(x!=-1)

printf("\nSearch success,location is %d.",x);

else

printf("\nSearch not successful.");

getch();

}

Inserting Sort in C Language – Program, Algorithm and Time Complexity

2012-01-28T06:20:00.002+05:30

In this sorting technique, the elements are scanned from left to right and insert each element in its proper location in the previously sorted list. So in an array Arr of n number of elements Arr[1] is assumed to be sorted. Then in the second iteration Arr[2] is inserted either before Arr[1] or after Arr[1] so that Arr[1] and Arr[2] are sorted. Similarly Arr[3] will be inserted either before Arr[1] , after Arr[3] or between Arr[1] and Arr[2] and so on. Now the problem is , where to insert Arr[x] in an sorted sub-array. This can be achieved by comparing Arr[x] with Arr[x-1] , Arr[x-2],Arr[x-3] and so on until it meets a value that less than or equal to Arr[x].Suppose Arr[j] is such value. Then Arr[x] will be positioned at Arr[j+1] location and all elements with which Arr[x] was compared will move forward by one location. From the above it is clear that there must be always an element Arr[j] such that Arr[j]<=Arr[x].So always put some small number say 0 in Arr[0] so that the above condition will be useful.

# include < stdio.h>

#define number 10

/* actually 11 values will be inserted in this array, value in the 0 index being a small value (0)*/

void iS(int arr[], int n)

{

int p,temp,i,k,x;

arr[0] = 0;

for(i = 1 ; i <= n; i++)

{

x=0;

p= i -1;

temp = arr[i];

/* In the iteration of the loop 'p' is 0 and 'i' is 1.So 'temp' will be the second element of the array , means the first valid value of the array while 'arr[p]' will be the smallest value (-0).So in the first iteration there will be no interchange of values. */

while(temp < arr[p])

{

arr[p+1] = arr[p];

p --;

x++;

/* In the second iteration,'arr[i]' means the second valid value while 'arr[p]' is the value of the previous location.The loop will continue to search the location for 'temp' if 'temp' is less than its previous value and during this process the greater values will be shifted one location right until the specific value 'temp' becomes equal to or greater than its previous value. At the end set 'temp' in its proper location with the statement 'arr[p+1]=temp' */

}

arr[p+1] = temp;

printf("Step(%d):-", i);

for(k = 1; k <= n; k++)

printf(" %d", arr[k]);

if(x!=0)

printf("-- took %d comparisions to place %d.",x,temp);

else

printf("--No interchange of position for %d.",temp);

printf("\n");

}

void display(int arr[], int n)

{

int i;

printf("\n Sorted list is as follows\n");

for(i = 1; i <= n; i++)

printf(" %d", arr[i]);

}

void main()

{

int list[20];

int i;

clrscr();

printf("\n Number of elements in the list: %i", number);

printf("\n Enter ten values:-\n");

for(i = 1; i <= number; i++)

{

scanf("%d",&list[i]);

}

printf("\n Step wise result is as follows \n\n");

iS(list,number);

display(list, number);

getch();

}

Insertion sort program without any extra location

#include

void ins(int arr[],int n)

{

int i,j,k,t,flag;

for(i=1;i< n;i++)

{

k=0;

flag=0;

while(1)

{

if(i< k)

break;

/* means there is no smaller value at left side of the value positioned at location 'i'*/

if(arr[i]< arr[k])

{

t=arr[k];

arr[k]=arr[i];

/* take the value to be shifted right side in 't' and insert the value of location 'i' at the location 'k' */

flag=1;

}

if(flag==1)

{

for(j=i;j>k+1;j--)

{

arr[j]=arr[j-1];

/* this shifts the values in the right ward direction */

}

arr[j]=t;

/* positioning the value lifted from the left side to just right of it */

}

else

k++;

/* trying with next value */

if(flag==1)

break;

/* in case of shifting, try with another value */

}

void main()

{

int i,arr[10];

clrscr();

for(i=0;i<10;i++)

{

printf("\nValue=");

scanf("%d",&arr[i]);

}

printf("\nBEFORE SORTING\n");

for(i=0;i<10;i++)

printf("%4d",arr[i]);

ins(arr,10);

printf("\nAFTER SORTING\n");

for(i=0;i<10;i++)

printf("%4d",arr[i]);

getch();

}

Algorithm of Insertion Sort :- ARR is an array which holds N+1 number of values.ARR[0] is made to store a very small value , so actual values stored in the array is N.TEMP is a variable which will help to interchange values while required. I is loop control variable. P is another variable.

Repeat the following steps for I=1,2,3…N

Set TEMP=ARR[I]

Set P=I-1

While TEMP < ARR[P]

Set ARR[P+1]=ARR[P]

Set P=P-1

[End of inner loop]

Set ARR[P]=TEMP

[End of outer loop]

End

Complexity of insertion sort:

In worst case while the list is arranged in reversed order, the inner loop will make k-1 comparisons to set the value of kth position in its actual location. So the time complexity f(x)=1+2+3+….+(n-1)

=n(n-1)/2

=O(n2)

In average case, there will be approximately (k-1)/2 comparisons for each element to set the value in its position. So f(x)=1/2+2/2+3/2+……(n-1)/2

= n(n-1)/4

=O(n2)

Selection Sort Using C Language and Its’ Algorithm & Complexity

2012-01-13T04:08:00.000+05:30

In selection sort the list is traversed first time from the start to end and the lowest value is positioned in the first position. So that A[0]<=A[1].After that the list is traversed from A[1] to A[N] and the second lowest value is placed in A[1] so that the list will be A[0]<=A[1]<=A[2] and so on. N number of values will be sorted after (N-1) number of passes.

If the series is :- 77 33 44 11 88 22 66 55

After 1st pass 11 77 44 33 88 22 66 55

After 2nd pass 11 22 77 44 88 33 66 55

After 3nd pass 11 22 33 77 88 44 66 55

After 4rth pass 11 22 33 44 88 77 66 55

After 5th Pass 11 22 33 44 55 88 77 66

After 6th Pass 11 22 33 44 55 66 77 88

After 7th Pass 11 22 33 44 55 66 77 88

Complexity of Selection Sort

There are (N-1) numbers of comparisons in the first pass, (N-2) number of comparisons in the second pass and so on. So there will be 1 comparison in the last pass.

So time complexity f(x) = (N-1) + (N-2) + (N-3) +…. +2+1

= N (N-1)/2

O (N2)

In both worst case and average case the complexity is O (N2)

Algorithm for Selection Sort:-

Arr represents the array of values where N is the number of elements in the array. I and J are two integer type variables. Set initial value 0 in Temp is an integer variable, will help to interchange values.

Repeat the following steps while I< N

Set J=I+1

Repeat the following steps while J< N

If Arr[I]>Arr[J]

Temp=Arr[I]

Arr[I]=Arr[J]

Arr[J]=Temp

[End of If body]

J=J+1

[End of the inner loop]

I=I+1

[End of the outer loop]

Exit

C Language Program on Selection Sort

#include < stdio.h>

void sS(int array[], int size)

{

int temp,i,j,x=0;

for (i= 0;i< size-1;i++)

{

for (j =i+1;j< size;j++)

{

x++;

if (array[i] > array[j])

{

temp = array[i];

array[i] = array[j];

array[j] = temp;

}

printf("\nNumber of passes required:-%d",i-1);

printf("\nTotal Number of comparisions:-%d",x);

}

void main()

{

int values[]={4,5,2,7,11,1}, i;

clrscr();

printf("\n Unsorted list is as follows \n");

for (i = 0; i <6; i++)

{

printf(" %d",values[i]);

}

sS(values, 6);

printf("\n Sorted list is as follows \n");

for (i = 0; i < 6; i++)

printf("%d ", values[i]);

getch();

}

Find the total number of comparisons in worst case for a selection sort:-

Suppose there are N numbers of values in an array. So the number of comparison in the first pass will be (N-1), in the second pass it will be (N-2) and so on. So the number of comparisons will be N (N-1)/2.If the number of elements is 6, then the number of comparisons will be 6(6-1)/2, 6*5/2, 30/2, 15

C Language program on Quick Sort with technical analysis and algorithm

2011-12-25T05:43:00.000+05:30

Quick sort is also known as partition exchange sort. Let x be an array and there are n number of elements in the array to be sorted. Choose an element a from a specific position within the array - a may be the first element of the array and place a in its appropriate position (suppose the location is j) of the array such that the following conditions are true:-All the elements of the array within 0 through j-1 is less than or equal to a and all the elements of the array within j+1 through n-1 is greater than a.

So the array is divided into two partitions. The left part contains values less than or equal to a while the right part contains values greater than a. suppose we have a list of 12 numbers like

44 33 11 55 77 90 40 60 99 22 88 66

Let's start with the first number 44. 44 will be placed in its actual location within the array.

Begin with the last number 66 and scan the list from right to left comparing each number with 44.When a number less than 44 is found stop the scan and interchange the positions between the numbers. Here in the list when 22 are reached the scan will stop and 44 and 22 will interchange their positions. So the list will be as follows:-

22 33 11 55 77 90 40 60 99 44 88 66

Note that all the values at the right of 44 are greater than it.

Next start scan from left to right beginning with 22 and stop when a number greater than 44 is found. Interchange their positions. Here in the left to right scan 55 is such a value when the scan will be stoped.So the list at present will be:-

22 33 11 44 77 90 40 60 99 55 88 66

Here also all the values at the left of 44 is less than it.

Next scan again from right to left beginning at 55 and stop when a value less than 44 is found before 44 and then interchange their positions. So after this scan the list will be like:-

22 33 11 40 77 90 44 60 99 55 88 66

Next left to right scan beginning with 40 up to 44 will yield the list as:-

22 33 11 40 44 90 77 60 99 55 88 66

Next scan starts with 77 - from right to left without producing any result.44 is now placed in it actual position and two sub lists are generated. Left sublist is at the left side of 44 and right sub list is at the right of 44.Any sub list containing at least two values will be subjected to the above steps to produce the final result.

Start with 22 33 11 40

11 33 22 40

next scan from left to right upto 11 if any number greater that 22 is found , 33 is found - interchange them

11 22 33 40

scan from right to left to search less value than 22 - not found so the sublist is in sorted order

Next start with the second sublist

90 77 60 99 55 88 66

right scan

66 77 60 99 55 88 90

left scan from 66

66 77 60 90 55 88 99

left scan from 88

66 77 60 88 55 90 99

right scan from 55

66 77 60 55 88 90 99

So 90 is in proper position , right sublist contains only one element so the left sublist will be needs sorting.

66 77 60 55 88

R->L starting from 88

55 77 60 66 88

L->R upto 66

55 66 60 77 88

R->L 60 to 66

55 60 66 77 88

So the final list is completed

Algorithm of Quick sort

Procedure will be called recursively until the array is completely sorted.

QS(Arr,N,Start,End,Loc)

Here Arr is the array with N number of elements. Start and End contains the lower and upper index value of the array or sub list on which the procedure will work. Loc keeps track of the position of the first value of the array sub list during execution. Two local variables Left and Right will contain the boundary values of the sub list that have not been scanned.

Set Left=Start

Set Right=End

Set Loc=Start

[Scan from right to left]

Repeat while Arr [Loc] <=Arr [Right] and Loc! =Right

Right=Right-1

[End of loop]

If Loc=Right

Return

If Arr [Loc]>Arr [Right]

Interchange Arr [Loc] and Arr [Right]

Set Loc=Right

Go to left scan

[End of If block]

[Scan from left to right]

Repeat while Arr [Left] <=Arr [Loc] and Loc! =Left

Left=Left+1

[End of loop]

If Loc=Left

Return

If Arr [Left]>Arr [Loc]

Interchange Arr [Loc] and Arr [Left]

Set Loc=Left

Go to Right scan

[End of If block]

This procedure will set the first value of the array or sub list in its proper position.

Complexity of Quick sort algorithm: - First consider the worst case. It occurs when the list is already sorted. Suppose there is n number of elements in the array, so the list needs n number comparisons to recognize that it remains at the proper location. Now the left sub list will be empty and there will be (n-1) number of elements in the right sublist.So (n-1) comparisons needed for this sub list again and so on. So the total number of comparisons will be

n+ (n-1) + (n-2) +….2+1

=n ((n+1)/2

=n2/2+n/2

O (n2)

Program on Quick Sort

#include

void qS(int array[], int first, int last)

{

int temp, low, high,i,x;

x=array[first];

/*position of this element will be fixed now */

low = first;

high = last;

{

while (array[high] > x)

high--;

// right to left

while (array[low] < x)

low++;

// left to right

if (low <= high)

{

temp = array[low];

array[low++] = array[high];

array[high--] = temp;

}

} while (low <= high);

printf("\n**\n");

for(i=0;i<6;i++)

printf("%d ",array[i]);

if (first < high)

qS(array, first, high);

if (low < last)

qS(array, low, last);

}

void main()

{

int values[]={3,2,6,5,4,8}, i;

clrscr();

printf("\n Unsorted list is as follows \n");

for(i=0;i<6;i++)

printf("%d ",values[i]);

qS(values,0,5);

/*passing the lower bound and upper bound as arguments.*/

printf("\n Sorted list as follows\n");

for (i = 0; i < 6; i++)

printf("%d ", values[i]);

getch();

}

Given a list of elements: - 2 51 82 12 31 14 78

Show the steps how the list can be sorted using quick sort algorithm :-

2 (51 82 12 31 14 78 ) right to left upto 2

2 (51 82 12 31 14 78 ) left to right upto 2

2 (14 82 12 31 51 78 ) right to left upto 51

2 14 51 12 31 82 78 left to right upto 51

2 14 31 12 51 82 78 right to left upto 51

2 14 31 12 51 82 78 left to right upto 51

So 51 is now placed in proper position

Start with the left sub list

14 31 12 left to right

12 31 14 right to left

12 is in proper position

31 14 right to left

14 31 left to right

14 31

So from left up to 51 the list is as follows

2 12 14 31 51

Now start with the right sub list

81 78 right to left

78 81 left to right

2 12 14 31 51 78 82

Sorting in C Language with algorithm

2011-11-29T07:15:00.000+05:30

Two very common activities in programs are sorting information on some basis and searching for particular item from a large body of data. The concept of an ordered set of elements is one that has considerable impact on our daily lives. Think of a telephone directory. Normally the names are listed in the directory in alphabetical order. This is known as sorted list. The process of finding a telephone number from the telephone directory is known as searching. It is easier to search a sorted list. Sorting can be defined as rearranging the data into a desired sequence based on some attribute of the data. It is a very tedious process because it can result into a massive reshuffling of the datas.

There are different sorting algorithms. There are several points to keep in mind when deciding on a sorting algorithm for a particular task. For example an algorithm may be very easy to implement but is slow while working on large volume of data.

Bubble Sort:-

This sorting technique is easy to implement but not very efficient. The basic technique of bubble sort is to pass through the values sequentially several times .During each pass each element of the list or array will be compared with its successor (A[i] with A[i+1]) and the values will be interchanged if they are not in proper position [ depending on the order , ascending or descending ].Consider the following values are to be sorted in ascending order :- 25 57 48 37 12 92 86 33 . The following operations are to be performed in the first pass.

Compare A[0] with A[1] -------- No interchanged

-- do -- A[1] with A[2]--------- Intechange

-- do -- A[2] with A[3]--------- Intechange

-- do -- A[3] with A[4]--------- Intechange

-- do -- A[4] with A[5]--------- No intechange

-- do -- A[5] with A[6]--------- Intechange

-- do -- A[6] with A[7]--------- Intechange

So after the first pass the array is in the order :- 25 48 37 12 57 86 33 92

After the first pass we find that the largest number 92 is placed in the last position of the array. After the second pass we will find that the second large number is placed just before 92 and this process will continue. Since each iteration will place a new value in its proper position, if there is n number of values then the number of iteration or number of passes will be n-1 times. So the position of the array after each pass will be as follows:-

Original: - 25 57 48 37 12 92 86 33

Pass 1:- 25 48 37 12 57 86 33 92

Pass 2:- 25 37 12 48 57 33 86 92

Pass 3:- 25 12 37 48 33 57 86 92

Pass 4:- 12 25 37 33 48 57 86 92

Pass 5:- 12 25 33 37 48 57 86 92

Pass 6:- 12 25 33 37 48 57 86 92

Pass 7:- 12 25 33 37 48 57 86 92

From the above chart it is clear that the values were positioned properly in the 5th iteration , still Pass 6 and Pass 7 took place without any effect.Such iterations can be stoped by determining whether any interchange of values took place in a given iteration.

Pseudocode algorithm of a bubble sort an array in descending order is as follows :-

N represents the number of elements in the array LIST.I and J are two integer type variables with initial value on I is 0.TEMP is another integer type variable.

Repeat through the following steps while(I< N)

Set J=0

Repeat through the following steps while(J< N-1)

If (LIST[J] > LIST[J+1])

Set TEMP=LIST[J]

Set LIST[J]=LIST[J+1]

Set LIST[J+1]=TEMP

[end of if block]

Set J=J+1

[end of inner loop]

Set I=I+1

[end of outer loop]

Exit

From the above algorithm it is clear that there are N-1 passes and on each pass there are N-1 comparisions.So the total number of comparisons is (N-1)*(N-1) =N2-2N+1.So we can say that the time complexity of the above algorithm is O(N2).

If the algorithm were so designed that when there is no exchange of values in a pass, the iterations will be stopped and the values are inserted in the array in complete sorted order then there will be only one pass of N-1 comparisons. So in this best case the complexity will be O(N).

#include < stdio.h>

void sort(int array[], int size)

{

int temp, i, j;

for (i = 0; i < size; i++)

{

for (j = 0; j < size-1; j++)

{

if (array[j] > array[j+1])

{

temp = array[j];

array[j] = array[j+1];

array[j+1] = temp;

}

void main()

{

int values[30], i;

clrscr();

printf("\n Unsorted list is as follows\n");

for (i = 0; i < 5; i++)

{

printf("\nEnter any integer value :-");

scanf("%d",&values[i]);

}

sort(values, 5);

printf("\n Sorted list is as follows\n");

for (i = 0; i < 5; i++)

printf("%d ", values[i]);

getch();

}

Program on Circular queue

2011-11-16T07:36:00.002+05:30

A queue is called circular when the last node comes just before the first node in case of queue implementation of linked list.There may a header node at the front.

# include < stdio.h>

# include < stdlib.h>

struct link

{

char info[20];

struct link *next;

};

struct link *p,*node,*new1,*start=NULL;

int x=0;

struct link *insert(struct link *nn)

{

if(x==0)

{

/*this will be a header node with no value in it's information part*/

fflush(stdin);

new1 = (struct link *) malloc(sizeof(struct link));

new1->next=new1;

node=new1;

x++;

}

else

{

x++;

node = nn;

p=start;

new1 = (struct link *) malloc(sizeof(struct link));

while(node->next!=node)

{

node=node->next;

p=p->next;

}

p->next=new1;

new1->next=node;

fflush(stdin);

printf("\n Input the node value: ");

gets(new1->info);

node=start->next;

}

return node;

}

void display(struct link *node)

{

while (node->next!=node)

{

printf(" %s", node->info);

node = node->next;

}

struct link *del(struct link *nn)

{

node=nn;

if(node==NULL)

printf("\nDeletion not possible.");

else

{

p=node->next;

free(node);

node=p;

}

return node;

}

void main()

{

struct link *start=NULL;

int k = 0;

char choice='i';

/* at the start of the program you must create a location*/

clrscr();

{

if(x!=0)

{

printf("\nInsert->i Delete->d Quit->q:");

printf("\nInput the choice : ");

{

choice = getchar();

choice = tolower(choice);

}while(strchr("idq",choice)==NULL);

printf("Your choice is: %c ", choice);

}

/* end of the if block.At the first iteration of the do loop , no need to take choice from the user as firstly a node will be inserted as a header node. */

switch(choice)

{

case 'i' :

{

start=insert(start);

if(x==1) /* after creating the header node x becomes 1*/

{

printf("\nHeader node is created.");

}

else

{

printf("\nQueue after inserting ");

display(start);

}/* no need to display when only the header node is created. */

break;

}

case 'd' :

{

start=del(start);

printf("\nQueue content after deleteion is as follows:\n");

display(start);

break;

}

case 'q':

{

k = 1;

}

} while(!k);

getch();

}

Doubly linked list implementation of Queue

2011-11-06T05:43:00.002+05:30

This is a program on queue using doubly linked list.

# include< stdio.h>

# include< stdlib.h>

struct link

{

int info;

struct link *next;

struct link *prev;

};

struct link *p;

void display(struct link *rec)

{

while(rec != NULL)

{

printf(" %d ",rec->info);

rec = rec->next;

}

struct link *insert(struct link *node)

{

struct link *xx,*new1;

xx=node;

p=NULL;

new1 = (struct link *) malloc(sizeof(struct link));

fflush(stdin);

printf("\nEnter the value: ");

scanf("%d", &new1->info);

if (node == NULL)

{

node->next=new1;

new1->prev=node;

new1->next=NULL;

node=new1;

}

else

{

while(xx)

{

xx = xx->next;

p=p->next;

}

p->next = new1;

new1->prev = p;

new1->next = xx;

}

return node;

}

struct link * del(struct link *rec)

{

struct link *temp;

if(rec == NULL)

{

printf("\n Empty");

}

else

{

temp = rec->next;

rec->next->prev=temp;

free(rec);

rec = temp;

printf("\n After deletion the queue is as follows:\n");

display(rec);

if(rec == NULL)

printf("\n Queue is empty");

}

return rec;

}

int selection()

{

int choice;

{

printf("\n 1<-Push ");

printf("\n 2<-Pop");

printf("\n 3<-Quit");

printf("\n Input your choice :");

scanf("%d", &choice);

if(choice <1 || choice >3)

printf("\n Incorrect choice-> Try once again");

} while(choice <1 || choice >3);

return choice;

}

void main()

{

struct link *start ;

int choice;

clrscr();

start = NULL;

{

choice = selection();

switch(choice)

{

case 1:

start = insert(start);

printf("\n After insertion queue is as follows:\n");

display(start);

break;

case 2:

start = del(start);

break;

default :

printf("\n End of session");

}

} while(choice != 3);

getch();

}

Linear Linked list implementation of Queue

2011-10-07T06:42:00.000+05:30

Here is the program on linear linked list implementation of queue where insertion and deletion can be performed as required, no limit.

# include < stdio.h>

# include < stdlib.h>

struct link

{

char info[20];

struct link *next;

};

struct link *p,*node,*new1,*start=NULL;

struct link *insert(struct link *nn)

{

node = nn;

p=NULL;

new1 = (struct link* ) malloc(sizeof(struct link));

while(node)

{

node=node->next;

p=p->next;

}

p->next=new1;

new1->next=node;

fflush(stdin);

printf("\n Input the node value: ");

gets(new1->info);

node=start->next;

return node;

}

void display(struct link *node)

{

while (node)

{

printf(" %s", node->info);

node = node->next;

}

struct link *del(struct link *nn)

{

node=nn;

if(node==NULL)

printf("\nDeletion not possible.");

else

{

p=node->next;

free(node);

node=p;

}

return node;

}

void main()

{

struct link *start=NULL;

int k = 0;

char choice;

clrscr();

{

printf("\nInsert->i Delete->d Quit->q:");

printf("\nInput the choice : ");

{

choice = getchar();

choice = tolower(choice);

}while(strchr("idq",choice)==NULL);

printf("Your choice is: %c ", choice);

switch(choice)

{

case 'i' :

{

start=insert(start);

printf("\nQueue after inserting ");

display(start);

break;

}

case 'd' :

{

start=del(start);

printf("\nQueue content after deleteion is as follows:\n");

display(start);

break;

}

case 'q':

{

k = 1;

}

} while(!k);

getch();

}

Using array as a queue

2011-09-02T14:46:00.000+05:30

A Queue can be defined as an ordered collection of items where items are added at one end and items are deleted at the other end. Hence the first item added in a Queue is the first item to be deleted .For this reason Queue is called fifo list. The end from which items are deleted in a Queue is called the front of the Queue and the other end is called the rear of the Queue.

Items can be inserted, at the rear end of the queue , items can be deleted from the front end of the queue. Item insertion has no limit as the rear end can grow but deletion of items from a queue is possible only when there is item in the queue.

Here is the program on queue

# include< stdio.h>

# include< string.h>

# define size 10

int rear, front;

int ch;

int x;

int q[size];

/* This array can work as a queue with maximum ten elements */

int rear = -1;

/* this variable will keep track of the elements inserted*/

int front = -1;

/*front will keep track of the elements deleted*/

void insert()

{

printf("\n Input the element :");

scanf("%d", &ch);

if(rear< size)

{

/* if block means insertion is possible.*/

rear ++;

q[rear] = ch ;

if(front == -1)

front = 0;

/* after inserting the first element, front becomes 0 .So we can delete elements. */

}

else

printf("\n Can't grow more.");

}

void del()

{

x=0;

if (front == -1)

{

printf("\n Underflow");

}

else

{

ch = q[front];

x=1;

printf("\n Element deleted : %d", ch);

}

if(front == rear)

{

/* front and rear will become same when all the inserted elements are deleted */

front =-1;

rear = -1;

}

else

front = front + 1;

/* after deleting an element front is incremented by 1 to access the next element.*/

}

void display()

{

int i;

if (front == -1)

return;

for(i = front ; i <= rear; i++)

printf(" %d ", q[i]);

}

void main()

{

int k = 0;

char choice;

clrscr();

{

printf("\nInsert->i Delete->d Quit->q:");

printf("\nInput the choice : ");

{

choice = getchar();

choice = tolower(choice);

}while(strchr("idq",choice)==NULL);

printf("Your choice is: %c ", choice);

switch(choice)

{

case 'i' :

{

insert();

printf("\nQueue after inserting ");

display();

break;

}

case 'd' :

{

del();

if(x==1)

{

printf("\nQueue content after deletion is as follows:\n");

display();

}

break;

}

case 'q':

{

k = 1;

}

} while(!k);

getch();

}

Program on entering infix expression and evaluation of the expression after converting in postfix using stack

2011-08-19T07:38:00.000+05:30

Here in this program the user will enter an infix expression , the infix will be displayed in postfix notation and the evaluated value of the postfix notation will be displayed.

# include< stdio.h>
# include< stdlib.h>
struct link
{
char ch;
struct link *next;
};

/*This structure is defined to store the operators of the infix notation.The operands of the infix notation will be displayed and the operators of the expression will be displayed according to precedence. functions push() , pop() , pop1() and pop2() are related with this staructure type stack */

struct link *dd1=NULL,*dd2;

/*these two external pointers will be used to store the postfix version of the expression in a stack.*/

struct list
{
int num;
char ch;
struct list *next;
};

/*This structure will be used to store the operands of the converted postfix notation*/

struct list *last=NULL;
struct link * pop2(struct link *rec)
{
char ch='a';
struct link *temp;
char x;
while((ch!='(')&&(rec!=NULL))
{
x=rec->ch;
if(x!='(')
{
dd2=(struct link *)malloc(sizeof(struct link));
dd2->ch=x;
dd2->next=dd1;
dd1=dd2;
/*operator stored in the stack for postfix evaluation*/
printf("%c",x);
/* operator is displayed for the postfix version*/
}
temp=rec->next;
free(rec);
/*stack which contains the operators for postfix version shrinks as the operator is displayed.*/
rec=temp;
}
return rec;
}
struct link * pop(struct link *rec)
{
if(rec != NULL)
{
struct link *temp;
char x;
x=rec->ch;
if(x!='(')
{
dd2=(struct link *)malloc(sizeof(struct link));
dd2->ch=x;
dd2->next=dd1;
dd1=dd2;
printf("%c",x);
}
temp=rec->next;
free(rec);
rec=temp;
}
return rec;
}
struct link * pop1(char z,struct link *rec)
{
struct link *temp;
char x;
x=rec->ch;
if(((x=='+')||(x=='-'))&&((z=='*')||(z=='/')||(z=='%')))
{

/*if the current operator has more precedence over the top item of the stack then no action should be taken , they should be kept in the stack as it is.Otherwise the last inserted item ( here operator) should be displayed ( from the else part).*/

}
else
{
if(x!='(')
{
dd2=(struct link *)malloc(sizeof(struct link));
dd2->ch=x;
dd2->next=dd1;
dd1=dd2;
/*the operator is stored in the stack no 2 (for postfix evaluation)*/
printf("%c",x);
}
temp=rec->next;
free(rec);
rec=temp;
/* if the top item of the stack is displayed , the stack should shrink.*/
}
return rec;
}
struct link *push(char c,struct link *rec)
{
if(c==')')
{
//if clossing bracket is found , there must be a openning bracket with operator
rec=pop2(rec);
}
if((rec!=NULL)&&(c!='('))
{

/*if the stack contains an operator and another operator is encountered, the operator which is of more precedence should be displayed.*/

rec=pop1(c,rec);
}
if(c!=')')
{
// from this block the current encountered operator is stored in the stack
struct link *new1;
new1 = (struct link *)malloc(sizeof(struct link));
new1->ch=c;
new1->next = rec;
rec = new1;
}
return rec;
}
struct list *push1(int i,struct list *node)
{
struct list *new1;
new1=(struct list *)malloc(sizeof(struct list));
new1->num=i;
new1->next=node;
node=new1;
return node;
}
struct list *pop3(struct list *node)
{
struct list *p;
p=node->next;
free(node);
node=p;
return node;
}

void dis(struct link *node)
{
int x,y,result;
struct list *ds,*sta=NULL;
while(node)
{
ds=(struct list *)malloc(sizeof(struct list));
ds->ch=node->ch;
node=node->next;
ds->next=last;
last=ds;
}

/* elements of the second stack are stored in another stack in reversed order whose top element is pointed by external pointer last.Now each element of the stack will be checked , if operand is found then it will be pushed in another stack , in case of operator the top two operands will be poped from the stack and operation will be performed according to the operator and the result will be pushed back again in the stack.*/

while(last)
{
char c=last->ch;
if(isdigit(c)!=0)
sta=push1(c-48,sta);
else
{
y=sta->num;
sta=pop3(sta);
x=sta->num;
sta=pop3(sta);
switch(c)
{

/*from here the result is calculated as per the operator and the result is pushed back into the stack*/

case '+':
{
result=(x+y);
sta=push1(result,sta);
break;
}
case '-':
{
result=(x-y);
sta=push1(result,sta);
break;
}
case '*':
{
result=(x*y);
sta=push1(result,sta);
break;
}
case '/':
{
result=(x/y);
sta=push1(result,sta);
break;
}
}
}
last=last->next;

/* pointer last which is traversing the stack containg the postfix version in reversed order moves to the next node.*/

}

/* when all the operations are performed , the final stack contains only one item , the result.*/

printf("\n*****\nResult of the expression is::%d",sta->num);
}
void main()
{
struct link *start;
int i=0;
char ch='a';
clrscr();
start = NULL;
printf("\nEnter the expression:-");
while(ch!='\n')
{
ch=getchar();
if((ch=='+')||(ch=='-')||(ch=='*')||(ch=='/')||(ch=='(')||
(ch=='%')||(ch==')'))
{

/* when operators are encountered ,push method is called with the character and structure pointer as argument. current stack will be returned. */

start=push(ch,start);
i++;
}
else
{
/* this block will be executed is the character read from the input is not an operator*/

if(ch!='\n')
{
printf("%c",ch);
/*operand in postfix version is displayed.*/
dd2=(struct link *)malloc(sizeof(struct link));
dd2->ch=ch;
dd2->next=dd1;
dd1=dd2;
/* the operands are stored in stack no.2 (for postfix evaluation)*/
}
}
}
while(i>0)
{

/* i counts the number of operators in the infix expression, although at present all the operators may not be present in the stack but we should call the pop method to display the remaining operators in the stack( which are not displayed through pop1() or pop2() */

start=pop(start);

/* every call to this function will display the top element of the stack and then the stack will be shrinked and returned so , before i becomes 0 start may point to NULL*/

i--;
}
dis(dd1);

/*dis () function of the second structure is called to reverse the elements of the second stack where all the operators and operands are stored in postfix notation */

getch();
}

Evaluation of entered postfix expression using C data Structure

2011-07-17T18:03:00.000+05:30

In this program, enter any postfix expression , the expression will be evaluated and the result will be displayed (e.g if the entered expression is 889*-88*- the result will display –128 )

Here are the codes of the program

# include < stdio.h>
# include < stdlib.h>
struct list
{
int num;
struct list *next;
};
struct list *push(int i,struct list *node)
{
struct list *new1;
new1=(struct list *)malloc(sizeof(struct list));
new1->num=i;
new1->next=node;
node=new1;
return node;
}
struct list *pop(struct list *node)
{
struct list *p;
p=node->next;
free(node);
node=p;
return node;
}
void main()
{
struct list *start=NULL;
char c;
int x,y,result;
clrscr();
printf("\nEnter the expression:-");
while((c=getchar())!='\n')
{
if(isdigit(c)!=0)
start=push(c-48,start);
else
{
y=start->num;
start=pop(start);
x=start->num;
start=pop(start);
switch(c)
{
case '+':
{
result=(x+y);
start=push(result,start);
break;
}
case '-':
{
result=(x-y);
start=push(result,start);
break;
}
case '*':
{

result=(x*y);
start=push(result,start);
break;
}
case '/':
{
result=(x/y);
start=push(result,start);
break;
}
}
}
}
printf("Result of the expression is::%d",start->num);
getch();
}

In this program the expression is taken as a string value and each character is checked whether it is digit or non digit. For digits, the element is pushed in a stack and for operators, two elements from the stack are popped from the stack. After evaluating the popped elements according to operator, the result is again pushed on the stack. Ultimately, the stack contains one element and that is the result.

Conversion of infix to postfix expression

2011-06-04T04:20:00.000+05:30

# include< stdio.h>
# include< stdlib.h>
struct link
{
char ch;
struct link *next;
};
struct link * pop2(struct link *rec)
{
char ch='a';
struct link *temp;
char x;
while((ch!='(')&&(rec!=NULL))
{
x=rec->ch;
if(x!='(')
printf("%c",x);
temp=rec->next;
free(rec);
rec=temp;
}
return rec;
}
struct link * pop(struct link *rec)
{
if(rec != NULL)
{
struct link *temp;
char x;
x=rec->ch;
if(x!='(')
printf("%c",x);
temp=rec->next;
free(rec);
rec=temp;
}
return rec;
}
struct link * pop1(char z,struct link *rec)
{
struct link *temp;
char x;
x=rec->ch;
if(((x=='+')||(x=='-'))&&((z=='*')||(z=='/')||(z=='%')))
{
}
else
{
if(x!='(')
printf("%c",x);
temp=rec->next;
free(rec);
rec=temp;
}
return rec;
}
struct link *push(char c,struct link *rec)
{
if(c==')')
{
rec=pop2(rec);
}
if((rec!=NULL)&&(c!='('))
{
rec=pop1(c,rec);
}
if(c!=')')
{
struct link *new1;
new1 = (struct link *)malloc(sizeof(struct link));
new1->ch=c;
new1->next = rec;
rec = new1;
}
return rec;
}
void main()
{
struct link *start ;
int i=0;
char ch='a';
clrscr();
start = NULL;
printf("\nEnter the expression:-");
while(ch!='\n')
{
ch=getchar();
if((ch=='+')||(ch=='-')||(ch=='*')||(ch=='/')||(ch=='(')||(ch=='%')||(ch==')'))
{
start=push(ch,start);
i++;
}
else
{
if(ch!='\n')
printf("%c",ch);
}
}
while(i>0)
{
start=pop(start);
i--;
}
getch();
}

Expression Evaluation using stack in C Language program

2011-05-15T20:23:00.000+05:30

Consider the expression for sum of A and B- normally we represents it with the expression A+B. A and B are two operands and ‘+’ is the operator. This particular representation is called infix. There are two alternate notations for expressing the sum of A and B :-
AB+ called postfix notation
+AB called prefix notation.
We will deal with infix and postfix notations.

Conversion from infix to postfix notation

Let us consider some additional examples, A + B * C is an mathematical expression and it is written using infix notation. Now we will see how we can convert it to postfix notation.
In a left to right scan of the expression, the first item encountered is A which may be directly displayed. Next the operator + is encountered and it should be pushed into a stack of operators. Next the operand B is encountered and is displayed. Next comes the second operator * and it is pushed in the stack. Last item of the expression is displayed. So upto this point we will get the out as :- ABC. Now start popping the items of the stack and display them .So the final output will be ABC*+.

# include< stdio.h >
# include< malloc.h >
int b=0;
struct link
{
char ch;
struct link *next;
};
struct link *push(char c,struct link *rec)
{
struct link *new1;
new1 = (struct link *)malloc(sizeof(struct link));
new1->ch=c;
new1->next = rec;
rec = new1;
return rec;
}
struct link * pop(struct link *rec)
{
if(rec != NULL)
{
struct link *temp;
char x;
x=rec->ch;
printf("%c",x);
temp=rec->next;
free(rec);
rec=temp;
}
return rec;
}
void main()
{
struct link *start ;
int i=0;
char ch='a';
clrscr();
start = NULL;
printf("\nEnter the expression:-");
while(ch!='\n')
{
ch=getchar();
if((ch=='+')||(ch=='-')||(ch=='*')||(ch=='/'))
{
start=push(ch,start);
i++;
}
else
{
if(ch!='\n')
printf("%c",ch);
}
}
while(i>0)
{
start=pop(start);
i--;
}
getch();
}

The above program is suitable for expressions like 7+2*3 , where the operators are of same precedence or precedences increase(s) from left to right. For the above expression , postfix notation will be 723*+.Evaluation of this postfix expression will be –
723*+
72*3+
76+
7+6
13

But what would happen if the expression is 7*2*3-2 ? The postfix notation of this expression would be 72*3*2-. If the postfix notation were 7232-** (which will be obtained if the conversion is done through the above program ) then the result would be 14 instead of 40.When operators other than the first operator is found in a expression it should be compared with the previous operator of the stack. If the operator in the stack is found of greater precedence over the current operator then the operator should be displayed.

Some examples of infix and postfix expressions are given below:-
Infix A+B-C Postfix AB+C-
Infix A+B*C postfix ABC*+
Infix (A+B)C postfix AB+C*
Infix (A+B)*(C-D) postfix AB+ CD-*

Follow my next post for the solution of these type of expression.

Application of stack-parentheses checking in an expression

2011-04-13T04:33:00.000+05:30

Let us see how we can use stack in problem solving. Consider a mathematical expression which contains a sets of nested parentheses— (x-(a+b) *(x-y)) and we have to check whether the parentheses are nested correctly. Actually we have to check two points.
There are equal numbers of left and right parentheses.
Every right parenthesis is preceded by a matching left parenthesis.

Expression such as ((A+B) violates first condition and expression such as (A+B} * { C+D) violates the second condition.
To solve such problem, we have to design a stack where each opening parentheses ‘(‘ , ‘{‘ or ‘[‘ of the expression will be pushed and when any closing parentheses is encountered , last inserted item from the stack will popped and checked with the closing parentheses. If mismatch is found, the expression is incorrect. At the end of the push and pop operation the stack should be empty to ensure that there are equal number opening and closing parentheses.

# include< stdio.h >
# include< stdlib.h>
int b=0;
struct link
{
char info;
struct link *next;
};
char xxx;
struct link *push(char c,struct link *rec)
{
struct link *new1;
xxx=c;
new1 = (struct link *)malloc(sizeof(struct link));
new1->info=xxx;
new1->next = rec;
rec = new1;
/* Every new opening parentheses is pushed at the top of the stack and pointer rec is made to point the new location */
return rec;
}
struct link * pop(char ch,struct link *rec)
{
struct link *temp;
char xx;
if(rec == NULL)
{
printf("Number of closing parentheses is more than number of closing\n");
b++;
}
else
{
temp=rec->next;
xx=rec->info;
if((xx=='(')&&(ch==')'))
{
free(rec);
rec = temp;
}
else if((xx=='{')&&(ch=='}'))
{
free(rec);
rec = temp;
}
else if((xx=='[')&&(ch==']'))
{
free(rec);
rec = temp;
}
else
{
b++;
}
}
return rec;
}
void main()
{
struct link *start ;
int d;
char ch='a';
clrscr();
start = NULL;
printf("\nEnter the expression:-");
while(ch!='\n')
{
ch=getchar();
if((ch=='(')||(ch=='{')||(ch=='['))
{
start=push(ch,start);
}
if((ch==')')||(ch=='}')||(ch==']'))
{
start=pop(ch,start);
}
if(b!=0)
break;
}
if(b!=0)
// mismatch is found.
printf("Expression is not Correct.");
else if(start==NULL)
/* this indicates that all items from the stack are poped and no mismatch was found. */
printf("Correct Expression.");
else
/* This point indicates that no mismatch is found but still there are items in the stack. So mismatch in number of opening and closing parentheses. */
printf("Expression is not Correct.");
getch();
}

C program on stack using doubly linked list

2011-03-28T04:49:00.003+05:30

So far we have seen array implementation of stack, stack using linear linked list. Today we will see stack using doubly linked list. Create stack, then push items in it and pop items from it.

# include< stdio.h >
# include< stdlib.h>
struct link
{
int info;
struct link *next;
struct link *prev;
};
void display(struct link *rec)
{
while(rec != NULL)
{
printf(" %d ",rec->info);
rec = rec->next;
}
}
struct link * push(struct link *rec)
{
struct link *new1;
printf("\n Enter value for stack:-");
new1 = (struct link *)malloc(sizeof(struct link));
scanf("%d", &new1->info);
new1->next = rec;
/* next pointer of new1 is holding the address of the first node of the list. so new1 is the first node now.*/
rec->prev=new1;
rec = new1;
/* from this point the pointer rec is pointing the first node of the list. */
return rec;
}
struct link * pop(struct link *rec)
{
struct link *temp;
if(rec == NULL)
{
printf("\n Stack is empty");
}
else
{
/*rec is pointing the first node of the list. */
temp = rec->next;
/* temp is pointing the second node of the list.*/
rec->next->prev=temp;
free(rec);
rec = temp;
printf("\n After pop operation the stack is as follows:\n");
display(rec);
if(rec == NULL)
printf("\n Stack is empty");
}
return rec;
}
int selection()
{
int choice;
do
{
printf("\n 1<-Push ");
printf("\n 2<-Pop");
printf("\n 3<-Quit");
printf("\n Input your choice :");
scanf("%d", &choice);
if(choice <1 || choice >3)
printf("\n Incorrect choice-> Try once again");
} while(choice <1 || choice >3);
return choice;
}
void main()
{
struct link *start ;
int choice;
clrscr();
start = NULL;
do
{
choice = selection();
switch(choice)
{
case 1:
start = push(start);
printf("\n After push operation stack is as follows:\n");
display(start);
break;
case 2:
start = pop(start);
break;
default :
printf("\n End of session");
}
} while(choice != 3);
getch();
}

C Program on reversing linked list using stack

2011-03-04T07:45:00.001+05:30

Create a linked list and then convert it into a stack. Again the stack is to be convert into a linked list so that the linked list is reversed.

#include< stdio.h>
#include< stdlib.h>
struct tag
{
int a;
struct tag *next;
};
int i=0;
struct tag *node,*p,*p1;
void create(struct tag *n)
{
char ch;
node=n;
printf("\n Want to create(y/n)");
ch=getche();
while(ch!='n')
{
node->next=(struct tag*)malloc(sizeof(struct tag));
node=node->next;
printf("\n Value");
scanf("%d",&node->a);
printf("\nany more(y/n)");
ch=getche();
}
node->next=NULL;
}
void display(struct tag*n)
{
node=n;
if(node==NULL)
i=0;
else
i=1;
while(node)
{
printf("%4d",node->a);
node=node->next;
}
}
struct tag *push(struct tag *p1,struct tag *p2)
{
p2->next=p1;
return(p2);
}
struct tag *delF(struct tag *n)
{
node=n->next;
n->next=node->next;
return(node);
}
struct tag *pop(struct tag *n)
{
node=n->next;
free(n);
return node;
}
void main()
{
struct tag *n,*link,*stack,*p;
clrscr();
link=NULL;
stack=NULL;
create(link);
printf("\nList is as follows\n");
display(link->next);
do
{
p=delF(link);
stack=push(stack,p);
}while(link->next!=NULL);
printf("\nList is as follows (after converting it into a stack.)");
display(link->next);
if(i==0)
printf("\nNo element in the list.");
printf("\nStack is\n");
display(stack);
n=link;
while(stack!=NULL)
{
n->next=stack;
n=n->next;
stack=pop(stack);
}
printf("\nStack is as follows (after converting it into a linked list.)");
display(stack);
if(i==0)
printf("\nNo element in the stack.");
printf("\nFinal list\n");
display(link->next);
getch();
}

Linked list implementation of stack in C Programming

2011-02-15T10:00:00.000+05:30

Our previous program was on implementing array as stack. Today I will show you the actual dynamic stack program where nodes are created and deleted as per requirements.

Codes of the stack program

# include< stdio.h>
# include< stdlib.h>
struct link
{
int info;
struct link *next;
};
void display(struct link *rec)
{
while(rec != NULL)
{
printf(" %d ",rec->info);
rec = rec->next;
}
}
struct link * push(struct link *rec)
{
struct link *new1;
printf("\n Enter value for stack:-");
new1 = (struct link *)malloc(sizeof(struct link));
scanf("%d", &new1->info);
new1->next = rec;
/* next pointer of new1 is holding the address of the first node of the list. so new1 is the first node now.*/
rec = new1;
/* from this point the pointer rec is pointing the first node of the list. */
return rec;
}
struct link * pop(struct link *rec)
{
struct link *temp;
if(rec == NULL)
{
printf("\n Stack is empty");
}
else
{
/*rec is pointing the first node of the list.*/
temp = rec->next;
/*temp is pointing the second node of the list. */
free(rec);
rec = temp;
printf("\n After pop operation the stack is as follows:\n");
display(rec);
if(rec == NULL)
printf("\n Stack is empty");
}
return rec;
}
int selection()
{
int choice;
do
{
printf("\n 1<-Push ");
printf("\n 2<-Pop");
printf("\n 3<-Quit");
printf("\n Input your choice :");
scanf("%d", &choice);
if(choice <1 || choice >3)
printf("\n Incorrect choice-> Try once again");
} while(choice <1 || choice >3);
return choice;
}
void main()
{
struct link *start ;
int choice;
clrscr();
start = NULL;
do
{
choice = selection();
switch(choice)
{
case 1:
start = push(start);
printf("\n After push operation stack is as follows:\n");
display(start);
break;
case 2:
start = pop(start);
break;
default :
printf("\n End of session");
}
} while(choice != 3);
getch();
}

Technical analysis of this stack program

‘struct link *start ;’ is the list pointer which will point the top of the stack. Initial value of this pointer is NULL. Two functions are defined in this program on stack. One is ‘struct link * push(struct link *rec)’ and the other is ‘struct link * pop(struct link *rec)’. Both the functions are return type, returning the address of top of the stack. Both the functions take the front node address of the stack as argument.

On calling the ‘push’ function, new node is dynamically created and the internal pointer is made to point the top of the stack. The address of the new node is returned to ‘void main()’, thus the new node is set on the top of the stack. Similarly when ‘pop ()’ function is called, the node at the front is removed and address of the next location is returned.

Stack in C Data Structure programs

2011-02-07T06:08:00.000+05:30

A stack is an ordered collection of items into which new items can be inserted and from which items can be deleted. But both the operations can be done from one end called the top of the stack (TOS).Unlike array stack provides the facilities for the insertion and deletion of items which makes stack dynamic. A single end of a stack can be designed as the TOS. New items can be put on TOS – in such case top of the stack moves upward to accommodate the new top most element or items from the top of the stack can be removed and top of the stack automatically moves downward to correspond to the new top element.

Array implementation of stack

Array can not be a stack but it can be the home of a stack. An array can be declared large enough for the maximum size of a stack. At the run time the stack can grow or shrink within the space reserved for it. One end of the array will act like the fixed bottom of stack while from the other end items can be added or removed. So another field is needed that keeps track of the current position of the top of the stack. This is called array implementation of stack.

Program on Array implementation of stack

# include< stdio.h>
# include< string.h>
# define size 3
int tos= -1;
/*this variable will keep track of the top of the stack */
int flag = 0;
/* this variable will determine whether push or pop will be granted. */
int stack[size];
/* array , within this array stack will grow and shrink. */
void push(int s[], int d)
{
if(tos==size-1)
{
/* this condition becomes true when the stack can not grow further */
flag=0;
}
else
{
flag = 1;
++tos;
s[tos] = d;
}
}
int pop(int s[])
{
int p;
if(tos == -1)
{
p = 0;
flag = 0;
}
else
{
flag = 1;
p = s[tos];
--tos;
}
return p;
}
void display(int s[])
{
int i;
if(tos == -1)
{
printf("\n Stack is empty");
}
else
{
for(i = tos; i >= 0; --i)
printf("\n %d", s[i] );
}
}
void main()
{
int data;
char choice;
int q = 0;
clrscr();
do
{
printf(" \nPush->i Pop->p Quit->q:");
printf("\nInput the choice : ");
do
{
choice = getchar();
choice =tolower(choice);
}while(strchr("ipq",choice)==NULL);
printf("Your choice is: %c",choice);
switch(choice)
{
case 'i' :
printf("\n Input the element to push:");
scanf("%d", &data);
push(stack, data);
if(flag)
{
printf("\n After inserting ");
display(stack);
if(tos == (size-1))
printf("\n Stack is full");
}
else
printf("\n capacity is exhausted");
break;
case 'p' :
data = pop(stack);
if(flag)
{
printf("\n Data is popped: %d", data);
printf("\n Rest data in stack is as follows:\n");
display(stack);
}
else
printf("\n No popping took place" );
break;
case 'q':
q = 1;
}
} while(!q);
getch();
}

Creating a linked list with common node values of two different linked lists

2011-02-02T07:43:00.000+05:30

In this C program on linked list, two different linked lists will be created with different number of nodes. A third linked list will be created from those two linked lists taking the nodes with common values.

Step by step analysis of the linked list program

Two linked lists are created separately with varying number of nodes. User enters the number of nodes of each linked list while creating them. The linked lists are displayed after creating. Function ‘void make(struct list *)’ is used to create linked list and another function ‘void show(struct list *)’ is defined in this program to display linked list. Function ‘struct list *com(struct list *,struct list *,struct list *)’ is defined in this program to do the final job, searching the common value nodes from each of the linked lists and creating the third linked list.

Codes of this linked list program

#include< stdio.h>
#include< stdlib.h>
struct list
{
int info;
struct list *next;
};
int i=0;
void make(struct list *);
void show(struct list *);
struct list *com(struct list *,struct list *,struct list *);
void main()
{
struct list *temp,*head,*in=NULL;
clrscr();
temp=(struct list *)malloc(sizeof(struct list));
make(temp);
printf("\ndisplaying FIRST linked list\n");
show(temp);
head=(struct list *)malloc(sizeof(struct list));
make(head);
printf("\ndisplaying SECOND linked list\n");
show(head);
in=com(temp,head,in);
printf("\nDisplaying the final linked list\n");
show(in);
getch();
}
void make(struct list *temp)
{
int n,i;
printf("\n\n enter the no of nodes you want to create\n");
scanf("%d",&n);
for(i=1;i< n;i++)
{
printf("entering value in %d node\n",i);
scanf("%d",&temp->info);
temp->next=(struct list *)malloc(sizeof(struct list));
temp=temp->next;
}
printf("Entering value in %d node\n",i);
scanf("%d",&temp->info);
temp->next=NULL;
}
void show(struct list *temp)
{
while(temp!=NULL)
{
printf("%d\t",temp->info);
temp=temp->next;
}
}
struct list *com(struct list *temp,struct list *h,struct list *in)
{
struct list *head,*head1;
while(temp!=NULL)
{
head=h;
while(head!=NULL)
{
if(temp->info==head->info)
{
in->next=(struct list *)malloc(sizeof(struct list));
in=in->next;
in->info=temp->info;
in->next=NULL;
if(i==0)
head1=in;
i++;
}
head=head->next;
}
temp=temp->next;
}
return head1;
}

C program on modification of values in a linked list

2011-01-24T15:07:00.000+05:30

Suppose a linked list is created with four fields in the information part and the user wants to modify the contents of a node of the linked list.

Creating the linked list and searching the linked list have been discussed earlier. This program on linked list also involves these two operations. After creating the list searching is required for modification of values. On successful seaching the values of the specific node is modified.

The program would be as follows :-

# include < stdio.h>
# include < stdlib.h>
struct link
{
char name[100];
char surname[100];
char add[100];
long ph;
struct link *next;
};
int x=0;
struct link *node;
int search(char ch[],struct link *n)
{
char c;
for(node=n; node->next != NULL; node = node->next)
{
if(strcmp(node-> name,ch)==0)
{
x++;
fflush(stdin);
printf("\nWant to change the surname ?(y/n)");
scanf("%c",&c);
fflush(stdin);
if(c!='n')
{
printf("\nEnter the Surname :-");
gets(node->surname);
}
printf("\nWant to change the address ?(y/n)");
scanf("%c",&c);
fflush(stdin);
if(c!='n')
{
printf("\nEnter the Address :-");
gets(node->add);
}
printf("\nWant to change the phone number ?(y/n)");
scanf("%c",&c);
fflush(stdin);
if(c!='n')
{
printf("\nEnter the Phone number :-");
scanf("%ld",&node->ph);
}
}
}
if(x == 0)
return 0;
else
return 1;
}
void display(struct link *n)
{
for(node=n; node->next != NULL; node = node->next)
{
printf("\n%s\n",node->name);
printf("%s\n",node->surname);
printf("%s\n",node->add);
printf("%ld\n",node->ph);
printf("\n*****************\n");
}
}
void get(struct link *n)
{
char ch='y';
node=n;
while(ch !='n')
{
fflush(stdin);
printf("\n Enter the name: -");
scanf("%s",node->name);
printf("\n Enter the surname: -");
scanf("%s",node->surname);
printf("\n Enter the address: -");
scanf("%s",node->add);
printf("\n Enter the Telephone number: -");
scanf("%ld",&node->ph);
node->next = (struct link* ) malloc (sizeof (struct link));
node = node->next;
node->next =NULL;
printf("\n Input choice n for break: ");
ch=getche();
}
}
void main()
{
struct link *start = (struct link *)malloc(sizeof(struct link));
char name[15];
int i=0;
clrscr();
get(start);
display(start);
while(i==0)
{
printf("\nEnter the name whose record is to be changed :");
scanf("%s",name);
i=search(name,start);
}
display(start);
getch();
}

Program to display a linked list from front side and reverse side
#include
#include
struct tag
{
int i;
struct tag *next;
};
struct tag *start=NULL,*node;
int x=1,flag=0,flag1;
void create()
{
char ch;
node=start;
puts("Want to create nodes(y/n):-");
scanf("%c",&ch);
while(ch!='n')
{
node->next=(struct tag *)malloc(sizeof(struct tag));
node=node->next;
node->next=NULL;
printf("\nEnter value::");
scanf("%d",&node->i);
flag++;
puts("Want to create nodes(y/n):-");
ch=getche();
}
flag1=flag;
}
void dis()
{
node=start->next;
while(node)
{
printf("%d\n",node->i);
node=node->next;
}
}
void dis1()
{
while(x<=flag1)
{
flag=flag1-x;
node=start->next;
while(flag)
{
node=node->next;
flag--;
}
printf("%d\n",node->i);
x++;
}
}
void main()
{
clrscr();
create();
printf("\nValues from front side are as follows.\n");
dis();
printf("\nLinked List displayed from reverse\n");
dis1();
getch();
}

C Program on linked list using address of list pointer

2011-01-18T15:34:00.000+05:30

I have posted number of programs on new node insertion and deletion of node from linked list. Those programs were either using header node in linked list or normal linked list. In linked list with header node the insertion at first location or deletion from the first location can be carried out easily but in linked list without header node, inserting new node at first location or deleting node from first location invokes some precautions. In both the cases the function is defined as returning address of the first node of the linked list after the operation is completed.

Today I will show you how to execute the operations of deletion and insertion on linked list even at the first location without returning values from the function. I have passed the address of the pointer holding the address of first node of the linked list to each function. So after deletion or insertion of node at starting location of the linked list, the address of the first node is assigned to the pointer to pointer and no need to return the new address of the first node of the linked list to void main.

# include < stdio.h>
# include < stdlib.h>
struct list
{
int age;
struct list *next;
};
struct list *new1,*node,*p;
void create(struct list **s)
{
char ch;
node=*s;
printf("\nWant to create a node(y/n):");
ch=getche();
while (ch != 'n')
{
node->next = (struct list *) malloc(sizeof(struct list));
node = node->next;
printf("\n Enter the numeric value:- ");
scanf("%d",&node->age);
printf("\n Enter choice--'n' for break: ");
ch = getche();
}
node->next = NULL;
}
void displayList (struct list **s)
{
node=*s;
while (node!=NULL)
{
printf("\n%d", node->age);
node = node->next;
}
printf("\n");
}
void delA(struct list **s)
{
int c=1,counter;
printf("\nEnter the location of the node to be deleted:");
scanf("%d",&counter);
if(c==counter)
{
node=(*s)->next;
free(*s);
s=&node;
}
else
{
node=*s;
p=node->next;
while(p->next!=NULL)
{
if(c+1==counter)
break;
c++;
node=node->next;
p=p->next;
}
node->next=p->next;
free(p);
}
}
void insA(struct list **s)
{
int c=1,counter;
printf("\nEnter the location where to insert the new node:");
scanf("%d",&counter);
new1=(struct list *) malloc(sizeof(struct list));
printf("\n Enter the numeric value:- ");
scanf("%d",&new1->age);

if(c==counter)
{
new1->next=*s;
s=&new1;
}
else
{
node=*s;
p=node->next;
while(p!=NULL)
{
if(c+1==counter)
break;
c++;
node=node->next;
p=p->next;
}
node->next=new1;
new1->next=p;
}
}

void main()
{
struct list *start;
clrscr();
start=(struct list *) malloc(sizeof(struct list));
printf("\n Enter the numeric value:- ");
scanf("%d",&start->age);

create(&start);
printf("\n Created list is as follows\n");
displayList(&start);
printf("\nDeleting any node\n");
delA(&start);
printf("\n now the list is\n");
displayList(&start);
printf("\nInserting new node\n");
insA(&start);
printf("\n now the list is\n");
displayList(&start);
getch();
}

C program to delete any node of a doubly linked list

2011-01-14T09:48:00.000+05:30

Previously we have seen how to delete the last node and first node of a doubly linked list. In both the above cases no traversal was required. To delete any location node of a doubly linked list, traversal is required but unlike linear linked list only one moving pointer is needed here. This moving pointer in the doubly linked list will trace out the location and from that point the node will be disconnected from the doubly linked list and removed.

Here is the program

# include
# include
struct list
{
int age;
struct list *next;
struct list *prev;
};
struct list *new1,*node;
void create(struct list *s,struct list *e)
{
char ch;
node=s;
node->next = (struct list *) malloc(sizeof(struct list));
node->next->prev= node;
node = node->next;
node->next=e;
e->prev=node;
printf("\n Enter the numeric value:- ");
scanf("%d",&node->age);

printf("\nWant to create a node(y/n):");
ch=getche();
while (ch != 'n')
{
node->next = (struct list *) malloc(sizeof(struct list));
node->next->prev= node;
node = node->next;
printf("\n Enter the numeric value:- ");
scanf("%d",&node->age);
printf("\n Enter choice--'n' for break: ");
ch = getche();
}
node->next = e;
e->prev=node;

}
void displayL (struct list *s,struct list *e)
{
node = s->next;
while (node!=e)
{
printf("\n%d", node->age);
node = node->next;
}
printf("\n");
}
void displayR (struct list *e,struct list *s)
{
node = e->prev;
while (node!=s)
{
printf("\n%d",node->age);
node = node->prev;
}
printf("\n");
}
void delA(struct list *s,struct list *e)
{
int c=1,counter;
printf("\nEnter the location of the node to be deleted:");
scanf("%d",&counter);
node=s->next;
while(node->next!=e)
{
if(c==counter)
break;
c++;
node=node->next;
}
node->prev->next=node->next;
node->next->prev=node->prev;
free(node);
}
void main()
{
struct list *start,*end;
clrscr();
start=(struct list *) malloc(sizeof(struct list));
end=(struct list *) malloc(sizeof(struct list));
create(start,end);
printf("\n Created list is as follows(L ->R)\n");
displayL(start,end);
printf("\n Created list displayed from R->L\n");
displayR(end,start);
printf("\nDeleting the First node\n");
delA(start,end);
printf("\n now the listfrom L ->R\n");
displayL(start,end);
printf("\n list from R to L after deletion\n");
displayR(end,start);
getch();
}

Related posts:
Deletion of last node from doubly linked list
Deletion of first node from doubly linked list

C program to delete the first node of a doubly linked list

2011-01-14T09:47:00.000+05:30

Previously we have seen how to delete the last node of a doubly linked list. To delete the first node, no traversal is required. Simply connect the left header node with the second node of the doubly linked list to disconnect the node from the list and remove it.

Here is the program

# include < stdio.h >
# include < stdlib.h >
struct list
{
char ch;
struct list *next;
struct list *prev;
};
struct list *new1,*node;
void create(struct list *s,struct list *e)
{
char ch;
node=s;
printf("\nWant to create a node(y/n):");
ch=getche();
while (ch != 'n')
{
node->next = (struct list *) malloc(sizeof(struct list));
node->next->prev= node;
node = node->next;
printf("\n Enter any character:- ");
scanf(“%c”,&node->ch);
printf("\n Enter choice--'n' for break: ");
ch = getche();
}
node->next = e;
e->prev=node;

}
void displayL (struct list *s,struct list *e)
{
node = s->next;
while (node!=e)
{
printf("\n 0x%x--%c", node,node->ch);
node = node->next;
}
printf("\n");
}
void displayR (struct list *e,struct list *s)
{
node = e->prev;
while (node!=s)
{
printf("\n%c",node->ch);
node = node->prev;
}
printf("\n");
}
void delF(struct list *s)
{
node=s->next;
node->prev->next=node->next;
node->next->prev=node->prev;
free(node);
}
void main()
{
struct list *start,*end;
clrscr();
start=(struct list *) malloc(sizeof(struct list));
end=(struct list *) malloc(sizeof(struct list));
create(start,end);
printf("\n Displaying the list from left to right\n");
displayL(start,end);
printf("\n Displaying the list from right to left\n");
displayR(end,start);
printf("\nFirst node deleted\n");
delF(start);
printf("\n now the list from left to right\n");
displayL(start,end);
printf("\nNow the list from right to left\n");
displayR(end,start);
getch();
}

Related posts:
Deletion of last node from doubly linked list
Deletion of any node from doubly linked list