C Program of reversing a string using stack


Let's Code

/*Program of reversing a string using stack */
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define MAX 20

int top = -1;
char stack[MAX];
char pop();
void push(char);

main()
{
char str[20];
unsigned int i;
printf(“Enter the string : ” );
gets(str);
/*Push characters of the string str on the stack */
for(i=0;i<strlen(str);i++)
push(str[i]);
/*Pop characters from the stack and store in string str */
for(i=0;i
str[i]=pop();
printf(“Reversed string is : “);
puts(str);
}/*End of main()*/

void push(char item)
{
if(top == (MAX-1))
{
printf(“Stack Overflown”);
return;
}
stack[++top] =item;
}/*End of push()*/

char pop()
{
if(top == -1)
{
printf(“Stack Underflown”);
exit(1);
}
return stack[top–];
}/*End of pop()*/

View original post

C Program of priority queue using linked list


/*Program of priority queue using linked list*/
#include<stdio.h>
#include<stdlib.h>

struct node
{
int priority;
int info;
struct node *link;
}*front=NULL;

void insert(int item, int item_priority);
int del();
void display();
int isEmpty();

main()
{
int choice,item,item_priority;
while(1)
{
printf(“1.Insert\n”);
printf(“2.Delete\n”);
printf(“3.Display\n”);
printf(“4.Quit\n”);
printf(“Enter your choice : “);
scanf(“%d”, &choice);

switch(choice)
{
case 1:
printf(“Input the item to be added in the queue : “);
scanf(“%d”,&item);
printf(“Enter its priority : “);
scanf(“%d”,&item_priority);
insert(item, item_priority);
break;
case 2:
printf(“Deleted item is %d\n”,del());
break;
case 3:
display();
break;
case 4:
exit(1);
default :
printf(“Wrong choice\n”);
}/*End of switch*/
}/*End of while*/
}/*End of main()*/

void insert(int item,int item_priority)
{
struct node *tmp,*p;

tmp=(struct node *)malloc(sizeof(struct node));
if(tmp==NULL)
{
printf(“Memory not available\n”);
return;
}
tmp->info=item;
tmp->priority=item_priority;
/*Queue is empty or item to be added has priority more than first element*/
if( isEmpty() || item_priority < front->priority )
{
tmp->link=front;
front=tmp;
}
else
{
p = front;
while( p->link!=NULL && p->link->priority<=item_priority )
p=p->link;
tmp->link=p->link;
p->link=tmp;
}
}/*End of insert()*/

int del()
{
struct node *tmp;
int item;
if( isEmpty() )
{
printf(“Queue Underflow\n”);
exit(1);
}
else
{
tmp=front;
item=tmp->info;
front=front->link;
free(tmp);
}
return item;
}/*End of del()*/

int isEmpty()
{
if( front == NULL )
return 1;
else
return 0;

}/*End of isEmpty()*/

void display()
{
struct node *ptr;
ptr=front;
if( isEmpty() )
printf(“Queue is empty\n”);
else
{    printf(“Queue is :\n”);
printf(“Priority       Item\n”);
while(ptr!=NULL)
{
printf(“%5d        %5d\n”,ptr->priority,ptr->info);
ptr=ptr->link;
}
}
}/*End of display() */

C Program of reversing a string using stack


 

/*Program of reversing a string using stack */
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define MAX 20

int top = -1;
char stack[MAX];
char pop();
void push(char);

main()
{
char str[20];
unsigned int i;
printf(“Enter the string : ” );
gets(str);
/*Push characters of the string str on the stack */
for(i=0;i<strlen(str);i++)
push(str[i]);
/*Pop characters from the stack and store in string str */
for(i=0;i
str[i]=pop();
printf(“Reversed string is : “);
puts(str);
}/*End of main()*/

void push(char item)
{
if(top == (MAX-1))
{
printf(“Stack Overflow\n”);
return;
}
stack[++top] =item;
}/*End of push()*/

char pop()
{
if(top == -1)
{
printf(“Stack Underflow\n”);
exit(1);
}
return stack[top–];
}/*End of pop()*/

 

C program for Linked Lists Using Recursion for all operations


/*Linked list using Recursion*/
#include<stdio.h>
#include<stdlib.h>

struct node
{
int info;
struct node *link;
};
struct node *create_list(struct node *start);
void display(struct node *ptr);
void Rdisplay(struct node *ptr);
int length(struct node *ptr);
int sum (struct node *ptr);
int search(struct node *ptr, int item );
struct node *insertLast(struct node *ptr, int value);
struct node *delLast(struct node *ptr );
struct node *reverse(struct node *ptr);

main()
{
struct node *start=NULL;
int choice,data;

while(1)
{
printf(“\n1.Create List\n”);
printf(“\n2.Display\n”);
printf(“\n3.Display in reverse order\n”);
printf(“\n4.Count\n”);
printf(“\n5.Sum of elements\n”);
printf(“\n6.Search\n”);
printf(“\n7.Insert at last\n”);
printf(“\n8.Delete the last node\n”);
printf(“\n9.Reverse the list\n”);
printf(“\n10.Quit\n”);

printf(“\n\nEnter your choice : “);
scanf(“%d”,&choice);
printf(“\n”);
switch(choice)
{
case 1:
start=create_list(start);
break;
case 2:
display(start);
printf(“\n\n”);
break;
case 3:
Rdisplay(start);
printf(“\n\n”);
break;
case 4:
printf(“\nNumber of elements = %d\n\n”,length(start));
break;
case 5:
printf(“\nSum of elements = %d\n\n”,sum(start));
break;
case 6:
printf(“\nEnter the element to be searched : “);
scanf(“%d”,&data);
if( search(start,data) == 1 )
printf(“\nElement present\n\n”);
else
printf(“\nElement not present\n\n”);
break;
case 7:
printf(“\nEnter the element to be inserted : “);
scanf(“%d”,&data);
start=insertLast(start,data);
break;
case 8:
start=delLast(start);
printf(“\nLast node deleted……\n”);
break;
case 9:
start=reverse(start);
break;
case 10:
exit(1);
default:
printf(“\nWrong choice\n”);
}/*End of switch */
}/*End of while */
}/*End of main()*/

struct node *create_list(struct node *start)
{
int i,n,value;
struct node *q,*tmp;
printf(“\nEnter the number of nodes : “);
scanf(“%d”,&n);
start=NULL;
for(i=1;i<=n;i++)
{
printf(“\nEnter the element to be inserted : “);
scanf(“%d”,&value);

tmp= malloc(sizeof(struct node));
tmp->info=value;
tmp->link=NULL;

if(start==NULL) /*If list is empty */
start=tmp;
else
{ /*Element inserted at the end */
q=start;
while(q->link!=NULL)
q=q->link;
q->link=tmp;
}
}
return start;
}/*End of create_list()*/

void display(struct node *ptr)
{
if(ptr==NULL)
return;
printf(“%3d”,ptr->info);
display(ptr->link);
}/*End of display()*/

void Rdisplay(struct node *ptr)
{
if(ptr==NULL)
return;
Rdisplay(ptr->link);
printf(“%3d”,ptr->info);
}/*End of Rdisplay()*/

int length(struct node *ptr)
{
if(ptr==NULL)
return 0;
return 1 + length(ptr->link);

}/*End of length()*/

int sum (struct node *ptr)
{
if (ptr == NULL)
return 0;
return ptr->info + sum(ptr->link);
}/*End of sum()*/

int search(struct node *ptr, int item )
{
if(ptr==NULL)
return 0;
if( ptr->info == item )
return 1;
return search(ptr->link, item);
}/*End of search()*/

struct node *insertLast(struct node *ptr, int item)
{
struct node *temp;
if (ptr == NULL)
{
temp = malloc(sizeof(struct node));
temp->info = item;
temp->link = NULL;
return temp;
}
ptr->link = insertLast(ptr->link, item);
return ptr;
}/*End of insertLast()*/

struct node *delLast(struct node *ptr )
{
if( ptr->link == NULL )
{
free(ptr);
return NULL;
}
ptr->link = delLast(ptr->link);
return ptr;
}/*End of delLast()*/

struct node *reverse(struct node *ptr)
{
struct node *temp;
if( ptr->link == NULL )
return ptr;
temp=reverse(ptr->link);
ptr->link->link=ptr;
ptr->link=NULL;
return temp;
}/*End of reverse()*/

Program to transpose a sparse matrix using Linked Lists


 

#include <stdio.h>
#include <conio.h>
#include <malloc.h>

#define MAX1 3
#define MAX2 3

/* structure for col headnode */
struct cheadnode
{
int colno ;
struct node *down ;
struct cheadnode *next ;
} ;

/* structure for row headnode */
struct rheadnode
{
int rowno ;
struct node * right ;
struct rheadnode *next ;
} ;

/* structure for node to store element */
struct node
{
int row ;
int col ;
int val ;
struct node *right ;
struct node *down ;
} ;

/* structure for special headnode */
struct spmat
{
struct rheadnode *firstrow ;
struct cheadnode *firstcol ;
int noofrows ;
int noofcols ;
} ;

struct sparse
{
int *sp ;
int row ;
struct spmat *smat ;
struct cheadnode *chead[MAX2] ;
struct rheadnode *rhead[MAX1] ;
struct node *nd ;
} ;

void initsparse ( struct sparse * ) ;
void create_array ( struct sparse * ) ;
void display ( struct sparse ) ;
int count ( struct sparse ) ;
void create_triplet ( struct sparse *, struct sparse ) ;
void create_llist ( struct sparse * ) ;
void insert ( struct sparse *, struct spmat *, int, int, int ) ;
void show_llist ( struct sparse ) ;
void delsparse ( struct sparse * ) ;

void main( )
{
struct sparse s1, s2 ;

clrscr( ) ;

initsparse ( &s1 ) ;
initsparse ( &s2 ) ;

create_array ( &s1 ) ;

printf ( “\nElements in sparse matrix: ” ) ;
display ( s1 ) ;

create_triplet ( &s2, s1 ) ;

create_llist ( &s2 ) ;
printf ( “\n\nInformation stored in linked list : ” ) ;
show_llist ( s2 ) ;

delsparse ( &s1 ) ;
delsparse ( &s2 ) ;

getch( ) ;
}

/* initializes structure elements */
void initsparse ( struct sparse *p )
{
int i ;
/* create row headnodes */
for ( i = 0 ; i < MAX1 ; i++ )
p -> rhead[i] = ( struct rheadnode * ) malloc ( sizeof ( struct rheadnode ) ) ;

/* initialize and link row headnodes together */
for ( i = 0 ; i < MAX1 – 1 ; i++ )
{
p -> rhead[i] -> next = p -> rhead[i + 1] ;
p -> rhead[i] -> right = NULL ;
p -> rhead[i] -> rowno = i ;
}
p -> rhead[i] -> right = NULL ;
p -> rhead[i] -> next = NULL ;

/* create col headnodes */
for ( i = 0 ; i < MAX1 ; i++ )
p -> chead[i] = ( struct cheadnode * ) malloc ( sizeof ( struct cheadnode ) ) ;

/* initialize and link col headnodes together */
for ( i = 0 ; i < MAX2 – 1 ; i++ )
{
p -> chead[i] -> next = p -> chead[i + 1] ;
p -> chead[i] -> down = NULL ;
p -> chead[i] -> colno = i ;
}
p -> chead[i] -> down = NULL ;
p -> chead[i] -> next = NULL ;

/* create and initialize special headnode */

p -> smat = ( struct spmat * ) malloc ( sizeof ( struct spmat ) ) ;
p -> smat -> firstcol = p -> chead[0] ;
p -> smat -> firstrow = p -> rhead[0] ;
p -> smat -> noofcols = MAX2 ;
p -> smat -> noofrows = MAX1 ;
}

/* creates, dynamically the matrix of size MAX1 x MAX2 */
void create_array ( struct sparse *p )
{
int n, i ;

p -> sp = ( int * ) malloc ( MAX1 * MAX2 * sizeof ( int ) ) ;

/* get the element and store it */
for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
{
printf ( “Enter element no. %d:”, i ) ;
scanf ( “%d”, &n ) ;
* ( p -> sp + i ) = n ;
}
}

/* displays the contents of the matrix */
void display ( struct sparse s )
{
int i ;

/* traverses the entire matrix */
for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
{
/* positions the cursor to the new line for every new row */
if ( i % MAX2 == 0 )
printf ( “\n” ) ;
printf ( “%d\t”, * ( s.sp + i ) ) ;
}
}

/* counts the number of non-zero elements */
int count ( struct sparse s )
{
int cnt = 0, i ;

for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
{
if ( * ( s.sp + i ) != 0 )
cnt++ ;
}
return cnt ;
}

/* creates an array of triplet containing info. about non-zero elements */
void create_triplet ( struct sparse *p, struct sparse s )
{
int r = 0 , c = -1, l = -1, i ;

p -> row = count ( s ) ;
p -> sp = ( int * ) malloc ( p -> row * 3 * sizeof ( int ) ) ;

for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
{
c++ ;
/* sets the row and column values */
if ( ( ( i % MAX2 ) == 0 ) && ( i != 0 ) )
{
r++ ;
c = 0 ;
}

/* checks for non-zero element. Row, column and
non-zero element value is assigned to the matrix */
if ( * ( s.sp + i ) != 0 )
{
l++ ;
* ( p -> sp + l ) = r ;
l++ ;
* ( p -> sp + l ) = c ;
l++ ;
* ( p -> sp + l ) = * ( s.sp + i ) ;
}
}
}

/* stores information of triplet in a linked list form */
void create_llist ( struct sparse *p )
{
int j = 0, i ;
for ( i = 0 ; i < p -> row ; i++, j+= 3 )
insert ( p, p -> smat, * ( p -> sp + j ), * ( p -> sp + j + 1 ),
* ( p -> sp + j + 2) ) ;
}

/* inserts element to the list */
void insert ( struct sparse *p, struct spmat *smat , int r, int c, int v )
{
struct node *temp1, *temp2 ;
struct rheadnode *rh ;
struct cheadnode *ch ;
int i, j ;

/* allocate and initialize memory for the node */

p -> nd = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
p -> nd -> col = c ;
p -> nd -> row = r ;
p -> nd -> val = v ;

/* get the first row headnode */

rh = smat -> firstrow ;

/* get the proper row headnode */
for ( i = 0 ; i < r ; i++ )
rh = rh -> next ;
temp1 = rh -> right ;

/* if no element added in a row */
if ( temp1 == NULL )
{
rh -> right = p -> nd ;
p -> nd -> right = NULL ;
}
else
{
/* add element at proper position */
while ( ( temp1 != NULL ) && ( temp1 -> col < c ) )
{
temp2 = temp1 ;
temp1 = temp1 -> right ;
}
temp2 -> right = p -> nd ;
p -> nd -> right = NULL ;
}

/* link proper col headnode with the node */

ch = p -> smat -> firstcol ;
for ( j = 0 ; j < c ; j++ )
ch = ch -> next ;
temp1 = ch -> down ;

/* if col not pointing to any node */
if ( temp1 == NULL )
{
ch -> down = p -> nd ;
p -> nd -> down = NULL ;
}
else
{
/* link previous node in column with next node in same column */
while ( ( temp1 != NULL ) && ( temp1 -> row < r ) )
{
temp2 = temp1 ;
temp1 = temp1 -> down ;
}
temp2 -> down = p -> nd ;
p -> nd -> down = NULL ;
}
}

void show_llist ( struct sparse s )
{
struct node *temp ;
/* get the first row headnode */
int r = s.smat -> noofrows ;
int i ;

printf ( “\n” ) ;

for ( i = 0 ; i < r ; i++ )
{
temp = s.rhead[i] -> right ;
if ( temp != NULL )
{
while ( temp -> right != NULL )
{
printf ( “Row: %d Col: %d Val: %d\n”, temp -> row, temp -> col,
temp -> val ) ;
temp = temp -> right ;
}
if ( temp -> row == i )
printf ( “Row: %d Col: %d Val: %d\n”, temp -> row, temp -> col,
temp -> val ) ;
}
}
}

/* deallocates memory */
void delsparse ( struct sparse *p )
{
int r = p -> smat -> noofrows ;
struct rheadnode *rh ;
struct node *temp1, *temp2 ;
int i, c ;

/* deallocate memeory of nodes by traversing rowwise */
for ( i = r – 1 ; i >= 0 ; i– )
{
rh = p -> rhead[i] ;
temp1 = rh -> right ;

while ( temp1 != NULL )
{
temp2 = temp1 -> right ;
free ( temp1 ) ;
temp1 = temp2 ;
}
}

/* deallocate memory of row headnodes */
for ( i = r – 1 ; i >= 0 ; i– )
free ( p -> rhead[i] ) ;

/* deallocate memory of col headnodes */

c = p -> smat -> noofcols ;
for ( i = c – 1 ; i >= 0 ; i– )
free ( p -> chead[i] ) ;
}

\n

Transposing a Sparse Matrix Using Array [Part 1-Long]


 

#include<stdio.h>
#include<conio.h>
// transpose for the sparse matrix
main()
{
//clrscr();
int a[10][10],b[10][10];
int m,n,p,q,t,col;
int i,j;

printf(“enter the no of row and columns :\n”);
scanf(“%d %d”,&m,&n);

// assigning the value of matrix

for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
printf(“a[%d][%d]= “,i,j);
scanf(“%d”,&a[i][j]);
}
}
printf(“\n\n”);

//displaying the matrix

printf(“\n\nThe matrix is :\n\n”);

for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
printf(“%d”,a[i][j]);
}
printf(“\n”);
}
t=0;

printf(“\n\nthe non zero value matrix are :\n\n”);

for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{

// accepting only non zero value
if(a[i][j]!=0)
{
t=t+1;
b[t][1]=i;
b[t][2]=j;
b[t][3]=a[i][j];
} }
}

// displaying the matrix of non-zero value

printf(“\n”);
printf(“a[0 %d %d %d\n”,m,n,t);

for(i=1;i<=t;i++)
{
printf(“a[%d %d %d %d \n”,i,b[i][1],b[i][2],b[i][3]);
}

b[0][1]=n; b[0][2]=m; b[0][3]=t;
q=1;

// transpose of the matrix

printf(“\n\nthe transpose of the matrix :\n “);

if(t>0)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=t;j++)
{
if(b[j][2]==i)
{
a[q][1]=b[j][2]; a[q][2]=b[j][1];
a[q][3]=b[j][3]; q=q+1;
} }
} }

printf(“\n\n”);
printf(“a[0 %d %d %d\n”,b[0][1],b[0][2],b[0][3]);

for(i=1;i<=t;i++)
{
printf(“a[%d %d %d %d\n”,i,a[i][1],a[i][2],a[i][3]);
}
getch();
}

\n