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

Infix to Postfix Expression conversion using stacks


 

Illustration of infix notation
Illustration of infix notation (Photo credit: Wikipedia)

Here is and application of stacks in data structures in the conversion of infix to postfix expression

#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>

#define N 64

#define LP 10

#define RP 20

#define OPERATOR 30
#define OPERAND 40

#define LPP 0
#define AP 1
#define SP AP
#define MP 2
#define DP MP
#define REMP 2

#define NONE 9

static char infix[N+1],stack[N],postfix[N+1];
static int top;

void infixtopostfix(void);
int gettype(char);
void push(char);
char pop(void);
int getprec(char);
main()
{
char ch;
do
{
top=-1;
printf(“\nEnter an infix expression\n”);
fflush(stdin);
gets(infix);
infixtopostfix();
printf(“\ninfix = %s\npost fix =%s\n”,infix,postfix);
printf(“\nDo you wish to continue\n”);
ch=getche();
}while(ch==’Y’ || ch==’y’);
}

void infixtopostfix(void)
{
int i,p,l,type,prec;
char next;
i=p=0;
l=strlen(infix);
while(i<l)
{
type=gettype(infix[i]);
switch(type)
{
case LP:
push(infix[i]);
break;
case RP:
while((next=pop())!='(‘)
postfix[p++]=next;
break;
case OPERAND:
postfix[p++]=infix[i];
break;
case OPERATOR:
prec=getprec(infix[i]);
while(top>-1 && prec <= getprec(stack[top]))
postfix[p++]=pop();
push(infix[i]);
break;
}
i++;
}
while(top>-1)
postfix[p++]=pop();
postfix[p]=”;
}

int gettype(char sym)
{
switch(sym)
{
case ‘(‘:
return(LP);
case ‘)’:
return(RP);
case ‘+’:
case ‘-‘:
case ‘*’:
case ‘/’:
case ‘%’:
return(OPERATOR);
default :
return(OPERAND);
}
}

void push(char sym)
{
if(top>N)
{
printf(“\nStack is full\n”);
exit(0);
}
else
stack[++top]=sym;
}

char pop(void)
{
if(top<=-1)
{
printf(“\nStack is empty\n”);
exit(0);
}
else
return(stack[top–]);
}

int getprec(char sym)
{
switch(sym)
{
case ‘(‘:
return(LPP);
case ‘+’:
return(AP);
case ‘-‘:
return(SP);
case ‘*’:
return(MP);
case ‘/’:
return(DP);
case ‘%’:
return(REMP);
default :
return(NONE);
}
getch();
}

\n

Array Complete Program using C[DATA STRUCTURE]


 

Real (Laplace) spherical harmonics for to (top...
Real (Laplace) spherical harmonics for to (top to bottom) and to (left to right). The negative order harmonics are rotated about the axis by with respect to the positive order ones. (Photo credit: Wikipedia)

 

Here is what I present Before you is a complete array program where all operations of arrays are included eg:-

 

  1. Insertion

  2. Deletion

  3. Searching

  4. Sorting

  5. Dispay

 

#include <stdio.h>
#include <conio.h>
int n; //size of array

int BSearch(int *a,int ITEM)
{
int beg=0,end=n-1;
int mid;

while( beg<=end )
{
mid=(beg+end)/2;
if(a[mid]==ITEM)
return mid;
else if( a[mid] < ITEM )
beg=mid+1;
else
end=mid-1;
}

return -1;
}

void SSort(int *a)
{
int i,j,temp;

for(i=0; i
{
for(j=i+1; j
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}

}

void DEL(int *a, int ITEM)
{
int i;
int pos=BSearch(a, ITEM);

if(pos!=-1)
{
for(i=pos; i
a[i]=a[i+1];
n–;
printf(“\n Item Deleted. “);
}
else
printf(“\n Item not found. “);
}

void INS(int *a, int ITEM)
{
int pos,i;

//Finding the proper position for Sorted Array
if(ITEM>a[n-1])
pos=n;
else if(ITEM<a[0])
pos=0;
else
{
for(i=0; i
if(a[i]<=ITEM && a[i+1]>=ITEM)
{
pos=i+1;
break;
}
}

//Shifting of elements to Insert the element.
for(i=n; i>pos; i–)
a[i]=a[i-1];

a[pos]=ITEM;
n++;
printf(“\n Item Inserted. “);
}

void Display(int *a)
{
int i;
for(i=0; i<n; i++)
printf(” %d”,a[i]);
}

int main()
{
int a[100],ch,pos,ITEM,i;

printf(“\n Enter the number of Elements: “);
scanf(“%d”,&n);

printf(“\n Enter the Elements: “);
for(i=0; i<n; i++)
scanf(“%d”,&a[i]);

do
{
printf(“\n ______________________________________ “);
printf(“\n MENU:\n”);
printf(“\n 1. Insert an element. “);
printf(“\n 2. Delete an element. “);
printf(“\n 3. Search for an element. “);
printf(“\n 4. Display elements. “);
printf(“\n 0. Exit. “);
printf(“\n Your Choice: “);
scanf(“%d”,&ch);

switch(ch)
{

case 1: //INSERT
printf(“\n Enter the Item to Insert: “);
scanf(“%d”,&ITEM);

SSort(a);
INS(a,ITEM);
Display(a);

break;

case 2: //DELETE
printf(“\n Enter the Item to Delete: “);
scanf(“%d”,&ITEM);

SSort(a);
DEL(a,ITEM);
Display(a);

break;

case 3: //SEARCH
printf(“\n Enter the Item to Search: “);
scanf(“%d”,&ITEM);

SSort(a);
pos=BSearch(a,ITEM);

if(pos==-1)
printf(“\n Item not Found. “);
else
printf(“\n Item found at %d position. “,pos+1);

break;

case 4: //DISPLAY
printf(“\n The Elements are: “);

SSort(a);
Display(a);

break;

case 0:
printf(“\n Exiting… “);
break;
}

}while(ch!=0);
getch();
}

 

 

Double Ended Queue ( DEQUE)


 

  It is a homogeneous list of elements in which insertion and deletion operations are performed from both the ends i.e, we can insert elements from the rear end or from the front ends. Hence, it is called double-ended queue. It is commonly referred to as deque.

There are two types of deques. These two types are due to the restrictions put to preform either the insertions or deletions only at the end. They are :

1) Input Restricted Deque
2) Output Restricted Deque

Four Operations :

=> Insertion of an element at the REAR end of the queue
=> Deletion of an element from the FRONT end of the queue
=> Insertion of an element at the FRONT end of the queue
=> Deletion of an element from the REAR end of the queue
For an input-restricted deque only the operations 1,2,3 & 4 are valid. And for an output-restricated deque only the operations specified in 1,2,3 are valid.

a) Insertion of an element at the REAR end of the queue

void dqinsert_rear(int q[10],int front,int rear,int item,int MAXSIZE)
{
if(rear == (MAXSIZE-1))
{
printf(” QUEUE is full “);
return;
}
rear=rear+1;
q[rear]=item;
}
b) Deletions of an element from the FRONT end of the queue

void dqdelete_front(int q[10],int front,int rear,int item)
{
if(front == rear)
{
printf(” QUEUE is empty “);
return;
}

front=front+1;
item=q[item];
}

3) Insertion of an element at the FRONT end of the queue

void dqinsert_front(int q[10], int front, int rear, int item)
{
if(front == 0)
{
printf(” QUEUE is full”);
return;
}
front=front-1;
q[front]=item;

}

d) Deletion of an element from the REAR end of the queue
void dqdelete_rear( int q[10], int front, int rear, int item)
{
if(front == rear)
{
printf(” QUEUE is empty “);
return;
}

rear=rear-1;
item=q[item];

}

e) Function to display the contents (status) of a QUEUE

void dq_display(int q[10], int front, int rear)
{
if(front <= rear)
{
printf(” Status of the Queue \n”);
for(i = front; i<=rear; i++)
printf(“%d”,dq[i]);

}
else
printf(” QUEUE is empty “);

}