When the hard disk is new the files and directories are properly organized. As the hard disk grows old, some laxity sets in and one tends to create files with duplicate names in different directories. Write a program to locate these duplicate filenames.

C Program to find files with duplicate names using binary search tree

#include < stdio.h >
#include < conio.h >
#include < dos.h >
#include < dir.h >
#include < string.h >
#include < alloc.h >

struct btreenode
{
struct btreenode *leftchild ;

char data[13] ; /* file name */

char *loc ; /* location of filename */

struct btreenode *rightchild ;

} *bt = NULL ;

void disktree( ) ;

int insert ( struct btreenode **, char*, char* ) ;

void main( )

{
char current_dir[32] ;

clrscr( ) ;

getcwd ( current_dir, 32 ) ;

chdir ( “\\” ) ;

disktree( ) ;

chdir ( current_dir ) ;

getch( ) ;
}

void disktree( )
{
struct ffblk file ;

int flag ;

char loc[80] ;

getcwd ( loc, 80 ) ;
flag = findfirst ( “*.*”, &file, FA_NORMAL | FA_RDONLY | FA_HIDDEN |

FA_SYSTEM | FA_LABEL | FA_DIREC | FA_ARCH ) ;

while ( flag == 0 )

{

if ( file.ff_name[0] != ‘.’ )

{

if ( file.ff_attrib == FA_DIREC && file.ff_fsize == 0 )
{
chdir ( file.ff_name ) ;

disktree( ) ;

chdir ( loc ) ;
}
else
insert ( &bt, loc, file.ff_name ) ;
}
flag = findnext ( &file ) ;
}
}

/* inserts a new node in a binary search tree */

int insert ( struct btreenode **sr, char* l, char* f )
{
char *p ;

int flag ;

if ( *sr == NULL )
{
*sr = ( struct btreenode * ) malloc ( sizeof ( struct btreenode ) ) ;

if ( *sr == NULL )
{
printf ( “\nOut of memory.” ) ;

exit ( 1 ) ;
}

( *sr ) – > leftchild = NULL ;

( *sr ) – > rightchild = NULL ;

strcpy ( ( *sr ) – > data, f ) ;

p = ( char * ) malloc ( ( strlen ( l ) + 1 ) ) ;

if ( p == NULL )
{
printf ( “\nOut of memory.” ) ;

exit ( 1 ) ;
}

strcpy ( p, l ) ;

( *sr ) – > loc = p ;
}
else
{
flag = strcmp ( ( *sr ) – > data, f ) ;

if ( flag == 0 )
{
printf ( “org: %s”, ( *sr ) – > loc ) ;

if ( strlen ( ( *sr ) – > loc ) > 4 )

printf ( “\\” ) ;

printf ( “%s\n”, ( *sr ) – > data ) ;

printf (“dup: %s”, l ) ;

if ( strlen ( l ) > 4 )

printf ( “\\” ) ;

printf ( “%s\n\n”, f ) ;
}

else if ( flag < 0 )

insert ( &( ( *sr ) - > leftchild ), l, f ) ;

else

insert ( &( ( *sr ) – > rightchild ), l, f ) ;

}

return ;
}

In an input restricted deque the insertion of elements is at one end only, but the deletion of elements can be done at both the ends of a queue. Write a program that demonstrates an input-restricted deque.

Here’s an Input-Restricted Deque Program Using Array

#include < stdio.h >

#include < conio.h >

#include < alloc.h >

#define MAX 10

struct dqueue

{
int arr[MAX] ;

int front, rear ;
} ;

void initdqueue ( struct dqueue * ) ;

void addqatend ( struct dqueue *, int item ) ;

int delqatbeg ( struct dqueue * ) ;

int delqatend ( struct dqueue * ) ;

void display ( struct dqueue ) ;

int count ( struct dqueue ) ;

void main( )

{
struct dqueue dq ;

int i, n ;

clrscr( ) ;

initdqueue ( &dq ) ;

addqatend ( &dq, 11 ) ;

addqatend ( &dq, 12 ) ;

addqatend ( &dq, 13 ) ;

addqatend ( &dq, 14 ) ;

addqatend ( &dq, 15 ) ;

addqatend ( &dq, 16 ) ;

addqatend ( &dq, 17 ) ;

addqatend ( &dq, 18 ) ;

addqatend ( &dq, 19 ) ;

addqatend ( &dq, 20 ) ;

display ( dq ) ;

n = count ( dq ) ;

printf ( “\nTotal elements: %d”, n ) ;

i = delqatbeg ( &dq ) ;

printf ( “\nItem extracted = %d”, i ) ;

i = delqatbeg ( &dq ) ;

printf ( “\nItem extracted = %d”, i ) ;

i = delqatend ( &dq ) ;

printf ( “\nItem extracted = %d”, i ) ;

i = delqatend ( &dq ) ;

printf ( “\nItem extracted = %d”, i ) ;

n = count ( dq ) ;

printf ( “\nElements Left: %d”, n ) ;

display ( dq ) ;

addqatend ( &dq, 19 ) ;

addqatend ( &dq, 20 ) ;

addqatend ( &dq, 21 ) ;

addqatend ( &dq, 22 ) ;

addqatend ( &dq, 23 ) ;

addqatend ( &dq, 24 ) ;

display ( dq ) ;

getch( ) ;
}

/* initializes elements of structure */

void initdqueue ( struct dqueue *p )

{
int i ;

p – > front = p – > rear = -1 ;

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

p - > arr[i] = 0 ;
}

/* adds item at the end of dqueue */

void addqatend ( struct dqueue *p, int item )
{
int i, k ;

if ( p – > front == 0 && p – > rear == MAX )
{
printf ( “\nQueue is full.\n” ) ;
return ;
}

if ( p – > rear == -1 && p – > front == -1 )
{
p – > rear = p – > front = 0 ;

p – > arr[p - > rear] = item ;

( p – > rear )++ ;

return ;
}

if ( p – > rear == MAX )
{
for ( i = k = p – > front – 1 ; i < p - > rear ; i++ )
{
k = i ;
if ( k == MAX – 1 )
p – > arr[k] = 0 ;
else
p – > arr[k] = p – > arr[i + 1] ;
}
( p – > rear )– ;
( p – > front )– ;
}
p – > arr[p - > rear] = item ;
( p – > rear )++ ;
}

/* deletes item from beginning of dequeue */

int delqatbeg ( struct dqueue *p )
{
int item ;

if ( p – > front == -1 && p – > rear == -1 )
{
printf ( “\nQueue is empty.\n” ) ;
return 0 ;
}

item = p – > arr[p - > front] ;
p – > arr[p - > front] = 0 ;
( p – > front )++ ;

if ( p – > front == MAX )
p – > front = -1 ;

return item ;
}

/* deletes item from end of dqueue */

int delqatend ( struct dqueue *p )

{
int item ;

if ( p – > front == -1 && p – > rear == -1 )

{
printf ( “\nQueue is empty.\n” ) ;

return 0 ;
}

( p – > rear )– ;

item = p – > arr[p - > rear] ;

p – > arr[p - > rear] = 0 ;

if ( p – > rear == 0 )

p – > rear = -1 ;

return item ;
}

/* displays the queue */

void display ( struct dqueue dq )

{
int i ;

printf ( “\n front – > ” ) ;

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

printf ( "%d\t", dq.arr[i] ) ;

printf ( " < - rear" ) ;
}

/* counts the number of items in dqueue */

int count ( struct dqueue dq )
{
int c, i ;

for ( i = c = 0 ; i < MAX ; i++ )

{
if ( dq.arr[i] != 0 )

c++ ;

}

return c ;
}

A deque is a data structure that allows both deletion as well as insertion of elements to be done at both ends. Write a program to demonstrate working of a deque using a linked list.

Here’s an Program on deque that implements a linked list.

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

struct node

{
int data ;

struct node *link ;

} ;

struct dqueue

{
struct node *front ;

struct node *rear ;
} ;

void initdqueue ( struct dqueue * ) ;

void addqatend ( struct dqueue *, int item ) ;

void addqatbeg ( struct dqueue *, int item ) ;

int delqatbeg ( struct dqueue * ) ;

int delqatend ( struct dqueue * ) ;

void display ( struct dqueue ) ;

int count ( struct dqueue ) ;

void deldqueue ( struct dqueue * ) ;

void main( )
{
struct dqueue dq ;

int i, n ;

clrscr( ) ;

initdqueue ( &dq ) ;

addqatend ( &dq, 11 ) ;

addqatbeg ( &dq, 10 ) ;

addqatend ( &dq, 12 ) ;

addqatbeg ( &dq, 9 ) ;

addqatend ( &dq, 13 ) ;

addqatbeg ( &dq, 8 ) ;

addqatend ( &dq, 14 ) ;

addqatbeg ( &dq, 7 ) ;

display ( dq ) ;

n = count ( dq ) ;

printf ( “\nTotal elements: %d”, n ) ;

i = delqatbeg ( &dq ) ;

printf ( “\nItem extracted = %d”, i ) ;

i = delqatbeg ( &dq ) ;

printf ( “\nItem extracted = %d”, i ) ;

i = delqatbeg ( &dq ) ;

printf ( “\nItem extracted = %d”, i ) ;

i = delqatend ( &dq ) ;

printf ( “\nItem extracted = %d”, i ) ;

display ( dq ) ;

n = count ( dq ) ;

printf ( “\nElements Left: %d”, n ) ;

deldqueue ( &dq ) ;

getch( ) ;
}

/* initializes elements of structure */

void initdqueue ( struct dqueue *p )
{
p – > front = p – > rear = NULL ;
}

/* adds item at the end of dqueue */

void addqatend ( struct dqueue *p, int item )
{
struct node *temp ;

temp = ( struct node * ) malloc ( sizeof ( struct node ) );

temp – > data = item ;

temp – > link = NULL ;

if ( p – > front == NULL )

p – > front = temp ;

else

p – > rear – > link = temp ;

p – > rear = temp ;
}

/* adds item at begining of dqueue */

void addqatbeg ( struct dqueue *p, int item )
{
struct node *temp ;

int *q ;

temp = ( struct node * ) malloc ( sizeof ( struct node ) );

temp – > data = item ;

temp – > link = NULL ;

if ( p – > front == NULL )

p – > front = p – > rear = temp ;

else

{

temp – > link = p – > front ;

p – > front = temp ;
}
}
/* deletes item from begining of dqueue */

int delqatbeg ( struct dqueue *p )
{
struct node *temp = p – > front ;

int item ;

if ( temp == NULL )

{

printf ( “\nQueue is empty.” ) ;

return 0 ;
}

else

{
temp = p – > front ;

item = temp – > data ;

p – > front = temp – > link ;

free ( temp ) ;

if ( temp == NULL )

p – > rear = NULL ;

return ( item ) ;
}
}

/* deletes item from end of dqueue */

int delqatend ( struct dqueue *p )
{
struct node *temp , *rleft, *q ;

int item ;

temp = p – > front ;

if ( p – > rear == NULL )

{
printf ( “\nQueue is empty.” ) ;

return 0 ;
}

else

{
while ( temp != p – > rear )

{
rleft = temp ;

temp = temp – > link ;
}
q = p – > rear ;

item = q – > data ;

free ( q ) ;

p – > rear = rleft ;

p – > rear – > link = NULL ;

if ( p – > rear == NULL )

p – > front = NULL ;

return ( item ) ;
}
}
/* displays the queue */

void display ( struct dqueue dq )
{
struct node *temp = dq.front ;

printf ( “\nfront – > ” ) ;

while ( temp != NULL )
{
if ( temp – > link == NULL )
{
printf ( “\t%d”, temp – > data ) ;

printf ( ” < - rear" ) ;
}
else
printf ( "\t%d", temp - > data ) ;

temp = temp – > link ;
}
printf ( “\n” ) ;
}

/* counts the number of items in dqueue */

int count ( struct dqueue dq )
{
int c = 0 ;
struct node *temp = dq.front ;

while ( temp != NULL )
{
temp = temp – > link ;
c++ ;
}

return c ;
}

/* deletes the queue */

void deldqueue ( struct dqueue *p )
{
struct node *temp ;

if ( p – > front == NULL )
return ;

while ( p – > front != NULL )
{
temp = p – > front ;
p – > front = p – > front – > link ;
free ( temp ) ;
}
}

Suppose Fundu Parking Garage contains 10 parking lanes, each with a capacity to hold 10 cars at a time. As each car arrives/departs, the values A/D (representing arrival /departure) is entered along with the car registration number. If a car is departing the data should get updated. If a new car is arriving then on the screen a message should be displayed indicating suitable parking slot for the car. Cars arrive at the south end of the garage and leave from the north end. If a customer arrives to pick up a car that is not the northern most, all cars to the north of the car are moved out, the car is driven out, and the other cars are restored in the same order that they were in originally. Whenever a car leaves, all cars to the south are moved forward so that at all times all the empty spaces are in the south part of the garage. Write a program that implements this parking system.

Here’s an example of Car Ggarage Simulation using De-Queue

(link list implementation)

#include < stdio.h >

#include < conio.h >

#include < alloc.h >

#include < string.h >

#define TOP 1

#define BOT 2

struct node

{

char plate [15] ;

struct node *link ;

} *front[5], *rear[5] ;

char plate[15], temp[15] ;

int i ;

void add_dq ( struct node**, struct node**, int, char* ) ;

char* del_dq ( struct node**, struct node**, int ) ;

void push ( struct node**, char* ) ;

char* pop ( struct node** ) ;

void q_display ( struct node * ) ;

void main( )
{
char ad ;

int s, lane = -1, min, lc ;

clrscr( );

while ( 1 )
{
for ( i = 0 ; i < 5 ; i++ )
{
printf( "lane %d: ", i ) ;

q_display ( front[i] ) ;
}

printf( "\nArrival/Departure/Quit? ( A/D/Q ): " ) ;

ad = getch( ) ;

if ( toupper ( ad ) == 'Q' )

exit ( 1 ) ;

printf ( "\nEnter license plate num:" ) ;

gets ( plate ) ;

ad = toupper ( ad ) ;

if ( ad == 'A' ) /* arrival of car */
{
lane = -1 ; /* assume no lane is available */

min = 10 ;

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

{

s = count ( front[i] ) ;

if ( s < min )

{
min = s ;

lane = i ;
}
}

if ( lane == -1 )

printf ( "\nNo room available" ) ;

else
{
add_dq ( &front[ lane ], &rear[ lane ], BOT, plate ) ;

printf ( "\npark car at lane %d slot %d\n", lane, s ) ;
}
}
else
{
if ( ad == 'D' ) /* departure of car */
{
for ( i = 0 ; i < 5 ; ++i )
{
s = search ( front[i], plate ) ;

if ( s != -1 )
{
lane = i ;

break ;
}
}
if ( i == 5 )
printf ( "\nno such car!!\n" ) ;
else
{
printf ( "\ncar found at lane %d slot %d\n", lane, s ) ;

del_dq ( &front[ lane ], &rear[ lane ], s ) ;
}
}
else
if ( ad == 'Q' )

exit ( 1 ) ;
}
}
}

/* adds a new element at the end of queue */

void add_dq ( struct node **f, struct node **r, int tb, char *p )

{
struct node *q ;

/* create new node */

q = ( struct node * ) malloc ( sizeof ( struct node ) ) ;

strcpy ( q – > plate, p ) ;

q – > link = NULL ;

/* if the queue is empty */

if ( *f == NULL )

*f = q ;

else

{

if ( tb == BOT )

( *r ) – > link = q ;

else

{

q – > link = *f ;

*f = q ;

return ;

}
}

*r = q ;
}

char* del_dq ( struct node **f, struct node **r, int n )
{
struct node *q, *top = NULL ;

/* if queue is empty */

if ( *f == NULL )

printf ( “queue is empty” ) ;

else
{
if ( n == 0 )
{
strcpy ( temp, ( *f ) – > plate ) ;

q = *f ;

*f = ( *f ) – > link ;

free ( q ) ;

return temp ;
}

/* locate node */

for ( i = 0 ; i < n ; i++ )
{
/* drive out cars */

push ( &top, ( *f ) - > plate ) ;

/* delete the node */

q = *f ;

*f = q – > link ;

free ( q ) ;
}

/* delete the nth node */

q = *f ;

*f = q – > link ;

free ( q ) ;

for ( i = 0 ; i < n ; i++ )
{
strcpy ( temp, pop ( &top ) ) ;

/* add the node */

add_dq ( f, r, TOP, temp ) ;
}
}
}

int count ( struct node *q )

{
int c = 0 ;

/* traverse the entire linked list */

while ( q!= NULL )

{
q = q - > link ;

c++ ;
}

return c ;
}

int search ( struct node *q, char *p )

{
int s = -1, c = 0 ;

while ( q != NULL )
{
if ( strcmp ( p, q – > plate ) == 0 )
{
s = c ;

break ;
}
else
{
q = q – > link ;

c++ ;
}
}
return ( s ) ;
}

/* adds a new element to the top of stack */

void push ( struct node **s, char* item )

{
struct node *q ;

q = ( struct node* ) malloc ( sizeof ( struct node ) ) ;

strcpy ( q – > plate, item ) ;

q – > link = *s ;

*s = q ;
}

/* removes an element from top of stack */

char* pop ( struct node **s )

{
struct node *q ;

/* if stack is empty */

if ( *s == NULL )

{

return NULL ;

}

else

{
q = *s ;

strcpy ( temp, q – > plate ) ;

*s = q – > link ;

free ( q ) ;

return ( temp ) ;
}
}

void q_display ( struct node *q )
{
while( q != NULL )

{

printf ( “%s”, q – > plate ) ;

q = q – > link ;
}

printf ( “\n” ) ;

}

There is a small busy airport with only one runway. In each unit of time one plane can land or one plane can take off, but not both. Planes arrive ready to land or to take off at random times, so at any given unit of time, the runway may be idle or a plane may be landing or taking off. There may be several planes waiting either to land or to take off. Follow the steps given below to design the C program for simulation of an Airport.
Read the rest of this entry »

Tower of hanoi is a historical problem, which can be easily expressed using recursion. There are N disks of decreasing size stacked on one needle, and two other empty needles. Tower of hanoi is required to stack all the disks onto a second needle in the decreasing order of size. The third needle can be used as a temporary storage. The movement of the disks must confirm to the following rules,
Read the rest of this entry »

A stack is used by programming languages for implementing function calls. C program to check how function calls are made using stack.
Read the rest of this entry »