SECTION B
Table of Contents
| |Name of the Project |Page No. |
|S.No | | |
|1 |Develop a project to find the solution for the maximum subsequence sum problem | |
| |with different time complexity solutions. | |
| 2 |Develop a project to test Linear and Binary searching techniques | |
|3 |Develop a project to test Insertion and shell sorting techniques | |
| 4 |Develop a project to test Merge and Quick sorting techniques(Devide and conquer| |
| |method) | |
|5. |Develop a project to test operations in array implementation of stacks and | |
| |queues. | |
|6. |Develop a project to convert an infix to postfix | |
| |Expression and evaluate a postfix expression. | |
|7 |Develop a project to implement all operations on Single Linked List. | |
|8 |Develop a project to implement all operations on Double Linked List. | |
|9 |Develop a project to implement polynomial Operations. | |
|10 |Develop a project to create a binary search tree and perform insertion, | |
| |deletion and traversal operation on it. | |
|11 |Develop a project to resolve collision resolving problem in hash table with | |
| |separate chaining hashing technique. | |
|12 |Develop a project to test operations in Linked list implementation stacks and | |
| |queues. | |
|13. |Develop a project to test AVL tree operations. | |
|14. |Develop a project to test all operations on circular linked list. | |
|15. |Develop a project to test Heap sort. | |
|16. |Develop a project for Airport simulation | |
| |(Applying Queue) | |
|17. | | |
| |Develop a project for Car GarageSimulation (Applying De-queue and stack ) | |
|18. |Develop a Project for Simulate a Dictionary (applying Linear Search) | |
|19. | | |
| |Develop a project for finding Duplicate files in a system by Applying Binary | |
| |search technique. | |
|20. | | |
| |Develop a project for Sorting the records using Sorting techniques. | |
PROJECT NO : 1
maximum subsequence sum
Learning Objectives:
To learn about:
|How to solve a problem with different complexities. | |
|To understand time complexity. | |
|How to select best algorithm based on their time complexity. | |
Problem Description:
A Program to solve maximum subsequence sum problem with Linear time complexity.
(The Maximum Contiguous Subsequence Sum (MCSS) Problem). Given a sequence
of numbers s = hs1, . . . , sni, the maximum contiguous subsequence sum problem is to find
. [pic]
(i.e., the sum of the contiguous subsequence of s that has the largest value).
Let’s look at an example. For s = {1,-5, 2,-1, 3}, we know that {1}, {2,-1, 3}, and {-5, 2} are all contiguous subsequences of s—whereas h1,2,3i is not. Among such subsequences, we’re interested in finding one that maximizies the sum. In this particular example, we can check that mcss(s) = 4, achieved by taking the subsequence {2,-1, 3}.
Input: A sequence {x1, x2,…. Xn} of integers. (Some of the integers may be negative.)
Output: The maximum sum over all subsequences.
H/W & S/W Specifications:
Pentium –IV
Putty software
Linux Server with c compiler
Source Code:
#include
#include
int max3(int x, int y, int z)
{
if(x>y)
{
if(x>z)
return(x);
else return z;
}
else if(y>z) return y;
else return z;
}
int alg3( int a[], unsigned int n )
{
int this_sum, max_sum, best_i, best_j, i, j, k;
/*1*/ max_sum = 0; best_i = best_j = -1;
/*2*/ for( i=0; i max_left_border_sum )
/*12*/ max_left_border_sum = left_border_sum;
}
/*13*/ max_right_border_sum = 0; right_border_sum = 0;
/*14*/ for( i=center+1; i max_right_border_sum )
/*17*/ max_right_border_sum = right_border_sum;
}
/*18*/ return max3( max_left_sum, max_right_sum,
max_left_border_sum + max_right_border_sum );
}
int lgn( int a[], unsigned int n )
{
int this_sum, max_sum, best_i, best_j, i, j;
/*1*/ i = this_sum = max_sum = 0; best_i = best_j = -1;
/*2*/ for( j=0; j max_sum )
{ /* update max_sum, best_i, best_j */
/*5*/ max_sum = this_sum;
/*6*/ best_i = i;
/*7*/ best_j = j;
}
else
/*8*/ if( this_sum < 0 )
{
/*9*/ i = j + 1;
/*10*/ this_sum = 0;
}
}
/*11*/ return( max_sum );
}
void main()
{
int a[20],i,j,n,sum,ch;
int alg4(int[],int);
clrscr();
printf("Enter N value: ");
scanf("%d",&n);
printf("\nEnter Array values: \n");
for(i=0;i0&&opdata=x;
head->next=NULL;
temp=head;
while(x!=0)
{
newnode=(struct node *)malloc(sizeof(struct node));
printf("\nenter data");
scanf("%d",&x);
if(x!=0)
{
newnode->prev=temp;
newnode->data=x;
newnode->next=NULL;
temp->next=newnode;
temp=newnode;
++n;
}
else
break;
}
}
void insert(int n)
{
int pos,x,i;
printf("\nenter position to insert");
scanf("%d",&pos);
printf("\nenter element to insert");
scanf("%d",&x);
newnode=(struct node *)malloc(sizeof(struct node));
if(pos==1)
{
newnode->data=x;
newnode->prev=NULL;
newnode->next=head;
head=newnode;
}
else if(pos==n-1)
{
temp=head;
while(temp->next!=NULL)
temp=temp->next;
newnode->data=x;
newnode->next=NULL;
newnode->prev=temp;
temp->next=newnode;
temp=newnode;
}
else
{
temp=head;
for(i=1;inext;
newnode->data=x;
newnode->next=temp->next;
temp->next->prev=newnode;
temp->next=newnode;
newnode->prev=temp;
}
}
void Delete(int n)
{
int pos,i;
printf("\nenter position to delete");
scanf("%d",&pos);
if(pos==1)
{
head=head->next;
head->prev=NULL;
}
else if(pos==n-1)
{
temp=head;
while(temp->next!=NULL)
temp=temp->next;
temp->prev->next=NULL;
}
else
{
temp=head;
for(i=1;inext;
temp->prev->next=temp->next;
temp->next->prev=temp->prev;
}
}
void sort()
{
int t;
for(temp1=head;temp1!=NULL;temp1=temp1->next)
for(temp2=head;temp2->next!=NULL;temp2=temp2->next)
{
if((temp1->data)data))
{
t=temp1->data;
temp1->data=temp2->data;
temp2->data=t;
}
}
}
void merge()
{
printf("\ncreate another list");
create();
temp=head;
while(temp->next!=NULL)
temp=temp->next;
temp->next=head1;
}
void reverse()
{
temp=head;
while(temp->next!=NULL)
temp=temp->next;
while(temp!=NULL)
{
printf("\n%d",temp->data);
temp=temp->prev;
}
}
void search()
{
int ele,flag=0;
printf("\nenter element to search");
scanf("%d",&ele);
for(temp=head;temp!=NULL;temp=temp->next)
{
if((temp->data)==ele)
{
flag=1;
break;
}
}
if(flag==1)
printf("\n%d is in list",ele);
else
printf("\n%d is not in list",ele);
}
void display()
{
temp=head;
printf("\nelements in list are:");
while(temp!=NULL)
{
printf("\n%d",temp->data);
temp=temp->next;
}
}
Result:
Operations on Double linked list were performed & tested with sample data.
Date: Signature of Instructor
Review Questions
List the applications of DLL’s.
1. How to reverse a DLL with out using previous pointer?
PROJECT NO :9
Polynomial
Learning Objectives:
To learn about:
|Polynomial manipulations | |
|How to Apply Linked List. | |
| | |
|Problem Description: | |
The biggest integer that we can store in a variable of the type int is 231 - 1 on 32-but CPU. You can easily verify this by the following operations:
int prod=1;
for(int i = 1; i Left );
MakeEmpty( T->Right );
free( T );
}
return NULL;
}
Position
Find( ElementType X, AvlTree T )
{
if( T == NULL )
return NULL;
if( X < T->Element )
return Find( X, T->Left );
else
if( X > T->Element )
return Find( X, T->Right );
else
return T;
}
Position
FindMin( AvlTree T )
{
if( T == NULL )
return NULL;
else
if( T->Left == NULL )
return T;
else
return FindMin( T->Left );
}
Position
FindMax( AvlTree T )
{
if( T != NULL )
while( T->Right != NULL )
T = T->Right;
return T;
}
/* START: fig4_36.txt */
static int
Height( Position P )
{
if( P == NULL )
return -1;
else
return P->Height;
}
/* END */
static int
Max( int Lhs, int Rhs )
{
return Lhs > Rhs ? Lhs : Rhs;
}
/* START: fig4_39.txt */
/* This function can be called only if K2 has a left child */
/* Perform a rotate between a node (K2) and its left child */
/* Update heights, then return new root */
static Position
SingleRotateWithLeft( Position K2 )
{
Position K1;
K1 = K2->Left;
K2->Left = K1->Right;
K1->Right = K2;
K2->Height = Max( Height( K2->Left ), Height( K2->Right ) ) + 1;
K1->Height = Max( Height( K1->Left ), K2->Height ) + 1;
return K1; /* New root */
}
/* END */
/* This function can be called only if K1 has a right child */
/* Perform a rotate between a node (K1) and its right child */
/* Update heights, then return new root */
static Position
SingleRotateWithRight( Position K1 )
{
Position K2;
K2 = K1->Right;
K1->Right = K2->Left;
K2->Left = K1;
K1->Height = Max( Height( K1->Left ), Height( K1->Right ) ) + 1;
K2->Height = Max( Height( K2->Right ), K1->Height ) + 1;
return K2; /* New root */
}
/* START: fig4_41.txt */
/* This function can be called only if K3 has a left */
/* child and K3's left child has a right child */
/* Do the left-right double rotation */
/* Update heights, then return new root */
static Position
DoubleRotateWithLeft( Position K3 )
{
/* Rotate between K1 and K2 */
K3->Left = SingleRotateWithRight( K3->Left );
/* Rotate between K3 and K2 */
return SingleRotateWithLeft( K3 );
}
/* END */
/* This function can be called only if K1 has a right */
/* child and K1's right child has a left child */
/* Do the right-left double rotation */
/* Update heights, then return new root */
static Position
DoubleRotateWithRight( Position K1 )
{
/* Rotate between K3 and K2 */
K1->Right = SingleRotateWithLeft( K1->Right );
/* Rotate between K1 and K2 */
return SingleRotateWithRight( K1 );
}
/* START: */
AvlTree
Insert( ElementType X, AvlTree T )
{
if( T == NULL )
{
/* Create and return a one-node tree */
T = malloc( sizeof( struct AvlNode ) );
if( T == NULL )
FatalError( "Out of space!!!" );
else
{
T->Element = X; T->Height = 0;
T->Left = T->Right = NULL;
}
}
else
if( X < T->Element )
{
T->Left = Insert( X, T->Left );
if( Height( T->Left ) - Height( T->Right ) == 2 )
if( X < T->Left->Element )
T = SingleRotateWithLeft( T );
else
T = DoubleRotateWithLeft( T );
}
else
if( X > T->Element )
{
T->Right = Insert( X, T->Right );
if( Height( T->Right ) - Height( T->Left ) == 2 )
if( X > T->Right->Element )
T = SingleRotateWithRight( T );
else
T = DoubleRotateWithRight( T );
}
/* Else X is in the tree already; we'll do nothing */
T->Height = Max( Height( T->Left ), Height( T->Right ) ) + 1;
return T;
}
/* END */
AvlTree
Delete( ElementType X, AvlTree T )
{
printf( "Sorry; Delete is unimplemented; %d remains\n", X );
return T;
}
ElementType
Retrieve( Position P )
{
return P->Element; }
#include "avltree.h"
#include
main( )
{
AvlTree T;
Position P;
int i;
int j = 0;
T = MakeEmpty( NULL );
for( i = 0; i < 50; i++, j = ( j + 7 ) % 50 )
T = Insert( j, T );
for( i = 0; i < 50; i++ )
if( ( P = Find( i, T ) ) == NULL || Retrieve( P ) != i )
printf( "Error at %d\n", i );
/* for( i = 0; i < 50; i += 2 )
T = Delete( i, T );
for( i = 1; i < 50; i += 2 )
if( ( P = Find( i, T ) ) == NULL || Retrieve( P ) != i )
printf( "Error at %d\n", i );
for( i = 0; i < 50; i += 2 )
if( ( P = Find( i, T ) ) != NULL )
printf( "Error at %d\n", i );
*/
printf( "Min is %d, Max is %d\n", Retrieve( FindMin( T ) ),
Retrieve( FindMax( T ) ) );
return 0;
}
Result:
AVL Tree implemented with sample data.
Date: Signature of Instructor
Review Questions
1. Compute the time complexity for above algorithm?
EXERCISE NO: 14
Circular Linked List
Learning Objectives:
To learn about:
|To learn how to implement circular Linked List Technique. | |
Problem Description:
In the last node of a list, the link field often contains a null reference, a special value used to indicate the lack of further nodes. A less common convention is to make it point to the first node of the list; in that case the list is said to be circular or circularly linked; otherwise it is said to be open or linear.
Input: Enter Data For constructing List.
Output: Showing Circular Linked List Data before and after performing operations.
H/W & S/W Specifications:
Pentium –IV
Putty software
Linux Server with c compiler
Source Code:
#include
#include
typedef struct Node
{
int data;
struct Node *next;
}node;
void insert(node *pointer, int data)
{
node *start = pointer;
/* Iterate through the list till we encounter the last node.*/
while(pointer->next!=start)
{
pointer = pointer -> next;
}
/* Allocate memory for the new node and put data in it.*/
pointer->next = (node *)malloc(sizeof(node));
pointer = pointer->next;
pointer->data = data;
pointer->next = start; }
int find(node *pointer, int key)
{
node *start = pointer;
pointer = pointer -> next; //First node is dummy node.
/* Iterate through the entire linked list and search for the key. */
while(pointer!=start)
{
if(pointer->data == key) //key is found.
{
return 1;
}
pointer = pointer -> next;//Search in the next node.
}
/*Key is not found */
return 0;
}
void delete(node *pointer, int data)
{
node *start = pointer;
/* Go to the node for which the node next to it has to be deleted */
while(pointer->next!=start && (pointer->next)->data != data)
{
pointer = pointer -> next;
}
if(pointer->next==start)
{
printf("Element %d is not present in the list\n",data);
return;
}
/* Now pointer points to a node and the node next to it has to be removed */
node *temp;
temp = pointer -> next;
/*temp points to the node which has to be removed*/
pointer->next = temp->next;
/*We removed the node which is next to the pointer (which is also temp) */
free(temp);
/* Beacuse we deleted the node, we no longer require the memory used for it .
free() will deallocate the memory.
*/
return;
}
void print(node *start,node *pointer)
{
if(pointer==start)
{
return;
}
printf("%d ",pointer->data);
print(start,pointer->next);
}
int main()
{
/* start always points to the first node of the linked list.
temp is used to point to the last node of the linked list.*/
node *start,*temp;
start = (node *)malloc(sizeof(node));
temp = start;
temp -> next = start;
/* Here in this code, we take the first node as a dummy node.
The first node does not contain data, but it used because to avoid handling special cases
in insert and delete functions.
*/
printf("1. Insert\n");
printf("2. Delete\n");
printf("3. Print\n");
printf("4. Find\n");
while(1)
{
int query;
scanf("%d",&query);
if(query==1)
{
int data;
scanf("%d",&data);
insert(start,data);
}
else if(query==2)
{
int data;
scanf("%d",&data);
delete(start,data);
}
else if(query==3)
{
printf("The list is ");
print(start,start->next);
printf("\n");
}
else if(query==4)
{
int data;
scanf("%d",&data);
int status = find(start,data);
if(status)
{
printf("Element Found\n");
}
else
{ printf("Element Not Found\n"); }
}
}
}
Result:
Circular Linked List technique was implemented & tested its performance with sample data.
Date: Signature of Instructor
Review Questions
1. Compute the time complexity for above algorithm?
EXERCISE NO : 15
Heap sort
Learning Objectives:
To learn about:
|To learn heap sort Technique. | |
Problem Description:
A heap is a specialized tree-based data structure that satisfies the heap property: If A is a parent node of B then key(A) is ordered with respect to key(B) with the same ordering applying across the heap. Either the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node (this kind of heap is called max heap) or the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node (min heap). Heaps are crucial in several efficient graph algorithms such as Dijkstra's algorithm, and in the sorting algorithm heapsort.
The operations commonly performed with a heap are:
• create-heap: create an empty heap
• heapify: create a heap out of given array of elements
• find-max or find-min: find the maximum item of a max-heap or a minimum item of a min-heap, respectively (aka, peek)
• delete-max or delete-min: removing the root node of a max- or min-heap, respectively
• increase-key or decrease-key: updating a key within a max- or min-heap, respectively
• insert: adding a new key to the heap
• merge: joining two heaps to form a valid new heap containing all the elements of both.
Input: Enter Data For constructing Heap Tree. Later to call Heap sort.
Output: Display node value deleted from the list and finally we get sorted List.
H/W & S/W Specifications:
Pentium –IV
Putty software
Linux Server with c compiler
Source Code:
void heapsort( input_type a[], unsigned int n )
{
int i;
for( i=n/2; i>0; i-- ) /* build_heap */
perc_down (a, i, n );
for( i=n; i>=2; i-- )
{
swap( &a[1], &a[i] ); /* delete_max */
perc_down( a, 1, i-1 );
}
}
void
perc_down( input_type a[], unsigned int i, unsigned int n )
{
unsigned int child;
input_type tmp;
for( tmp=a[i]; i*2 a[child] ) )
child++;
if( tmp < a[child] )
a[i] = a[child];
else
break;
}
a[i] = tmp;
}
Result:
Heap sort technique was implemented & tested its performance with sample data.
Date: Signature of Instructor
Review Questions
1. Compute the time complexity for above algorithm?
EXERCISE NO : 16
Airport simulation
Learning Objectives:
To learn about:
|To know how to apply queue for real time problems. | |
Problem Description:
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 program.
1. Create two queues one for the planes landing and the other for planes taking off.
2. Get the maximum number of units for which the simulation program would run.
3. Get the expected number of planes arriving in one unit and number of planes ready to take off in one unit .
3. To display the statistical data concerning the simulation, declare following data members.
a. idletime - to store the number of units the runway was idle
b. landwait - to store total waiting time required for planes landed
c. nland - to store number of planes landed
d. nplanes - to store number of planes processed
e. nrefuse - to store number of planes refused to land on airport
f. ntakeoff - to store number of planes taken off
g. takeoffwait - to store total waiting time taken for take off
Initialize the queue used for the plane landing and for the take off
Get the data for , and from the user.
The process of simulation would run for many units of time, hence run a loop in main( ) that would run from to where would be 1 and would be the maximum number of units the program has to be run.
Generate a random number. Depending on the value of random number generated, perform following tasks.
1. If the random number is less than or equal to 1 then get data for the plane ready to land. Check whether or not the queue for landing of planes is full. If the queue is full then refuse the plane to land. If the queue is not empty then add the data to the queue maintained for planes landing.
2. If the random number generated is zero, then generate a random number again. Check if this number is less than or equal to 1. If it is , then get data for the plane ready to take off. Check whether or not the queue for taking a plane off is full. If the queue is full then refuse the plane to take off otherwise add the data to the queue maintained for planes taking off.
3. It is better to keep a plane waiting on the ground than in the air, hence allow a plane to take off only, if there are no planes waiting to land.
4. After receiving a request from new plane to land or take off, check the queue of planes waiting to land, and only if the landing queue is empty, allow a plane to take off.
5. If the queue for planes landing is not empty then remove the data of plane in the queue else run the procedure to land the plane.
6. Similarly, if the queue for planes taking off is not empty then remove the data of plane in the queue else run the procedure to take off the plane.
7. If both the queues are empty then the runway would be idle.
8. Finally, display the statistical data As given below.
Total number of planes processed
Number of planes landed :
Number of planes taken off :
Number of planes refused use :
Number of planes left ready to land :
Number of planes left ready to take off :
Percentage of time the runway was idle :
Average wait time to land :
Average wait time to take off :
Input: Enter Data required for this project.
Output: display the statistical data As given below.
Total number of planes processed
Number of planes landed :
Number of planes taken off :
Number of planes refused use :
Number of planes left ready to land :
Number of planes left ready to take off :
Percentage of time the runway was idle :
Average wait time to land :
Average wait time to take off :
H/W & S/W Specifications:
Pentium –IV
Putty software
Linux Server with c compiler
Source Code:
/* Airport simulation */
#include
#include
#include
#include
#include
#include
#include
#define MAX 3
#define ARRIVE 0
#define DEPART 1
struct plane
{
int id ;
int tm ;
} ;
struct queue
{
int count ;
int front ;
int rear ;
struct plane p[MAX] ;
} ;
void initqueue ( struct queue * ) ;
void addqueue ( struct queue *, struct plane ) ;
struct plane delqueue ( struct queue * ) ;
int size ( struct queue ) ;
int empty ( struct queue ) ;
int full ( struct queue ) ;
void initqueue ( struct queue *pq )
{
pq -> count = 0 ;
pq -> front = 0 ;
pq -> rear = -1 ;
}
void addqueue ( struct queue *pq, struct plane item )
{
if ( pq -> count >= MAX )
{
printf ( "\nQueue is full.\n" ) ;
return ;
}
( pq -> count )++ ;
pq -> rear = ( pq -> rear + 1 ) % MAX ;
pq -> p[pq -> rear] = item ;
}
struct plane delqueue ( struct queue *pq )
{
struct plane p1 ;
if ( pq -> count count )-- ;
p1 = pq -> p[pq -> front] ;
pq -> front = ( pq -> front + 1 ) % MAX ;
}
return p1 ;
}
int size ( struct queue q )
{
return q.count ;
}
int empty ( struct queue q )
{
return ( q.count = MAX ) ;
}
struct airport
{
struct queue landing ;
struct queue takeoff ;
struct queue *pl ;
struct queue *pt ;
int idletime ;
int landwait, takeoffwait ;
int nland, nplanes, nrefuse, ntakeoff ;
struct plane pln ;
} ;
void initairport ( struct airport * ) ;
void start ( int *, double *, double * ) ;
void newplane ( struct airport *, int, int ) ;
void refuse ( struct airport *, int ) ;
void land ( struct airport *, struct plane, int ) ;
void fly ( struct airport *, struct plane, int ) ;
void idle ( struct airport *, int ) ;
void conclude ( struct airport *, int ) ;
int randomnumber ( double ) ;
void apaddqueue ( struct airport *, char ) ;
struct plane apdelqueue ( struct airport *, char ) ;
int apsize ( struct airport, char ) ;
int apfull ( struct airport, char ) ;
int apempty ( struct airport, char ) ;
void myrandomize ( ) ;
void initairport ( struct airport *ap )
{
initqueue ( &( ap-> landing ) ) ;
initqueue ( &( ap -> takeoff ) ) ;
ap -> pl = &( ap -> landing ) ;
ap -> pt = &( ap -> takeoff ) ;
ap -> nplanes = ap -> nland = ap -> ntakeoff = ap -> nrefuse = 0 ;
ap -> landwait = ap -> takeoffwait = ap -> idletime = 0 ;
}
void start ( int *endtime, double *expectarrive, double *expectdepart )
{
int flag = 0 ;
char wish ;
printf ( "\nProgram that simulates an airport with only one runway.\n" ) ;
printf ( "One plane can land or depart in each unit of time.\n" ) ;
printf ( "Up to %d planes can be waiting to land or take off at any time.\n", MAX ) ;
printf ( "How many units of time will the simulation run?" ) ;
scanf ( "%d", endtime ) ;
myrandomize( ) ;
do
{
printf ( "\nExpected number of arrivals per unit time? " ) ;
scanf ( "%lf", expectarrive ) ;
printf ( "\nExpected number of departures per unit time? " ) ;
scanf ( "%lf", expectdepart ) ;
if ( *expectarrive < 0.0 || *expectdepart < 0.0 )
{
printf ( "These numbers must be nonnegative.\n" ) ;
flag = 0 ;
}
else
{
if ( *expectarrive + *expectdepart > 1.0 )
{
printf ( "The airport will become saturated. Read new numbers? " ) ;
fflush ( stdin ) ;
scanf ( "%c", &wish ) ;
if ( tolower ( wish ) == 'y' )
flag = 0 ;
else
flag = 1 ;
}
else
flag = 1 ;
}
} while ( flag == 0 ) ;
}
void newplane ( struct airport *ap, int curtime, int action )
{
( ap -> nplanes )++ ;
ap -> pln.id = ap -> nplanes ;
ap -> pln.tm = curtime ;
switch ( action )
{
case ARRIVE :
printf ( "\n" ) ;
printf ( "Plane %d ready to land.\n", ap -> nplanes ) ;
break ;
case DEPART :
printf ( "\nPlane %d ready to take off.\n", ap -> nplanes ) ;
break ;
}
}
void refuse ( struct airport *ap, int action )
{
switch ( action )
{
case ARRIVE :
printf ( "\tplane %d directed to another airport.\n", ap -> pln.id ) ;
break ;
case DEPART :
printf ( "\tplane %d told to try later.\n", ap -> pln.id ) ;
break ;
}
( ap -> nrefuse )++ ;
}
void land ( struct airport *ap, struct plane pl, int curtime )
{
int wait ;
wait = curtime - pl.tm ;
printf ( "%d: Plane %d landed ", curtime, pl.id ) ;
printf ( "in queue %d units \n", wait ) ;
( ap -> nland ) ++ ;
( ap -> landwait ) += wait ;
}
void fly ( struct airport *ap, struct plane pl, int curtime )
{
int wait ;
wait = curtime - pl.tm ;
printf ( "%d: Plane %d took off ", curtime, pl.id ) ;
printf ( "in queue %d units \n", wait ) ;
( ap -> ntakeoff )++ ;
( ap -> takeoffwait ) += wait ;
}
void idle ( struct airport *ap, int curtime )
{
printf ( "%d: Runway is idle.\n", curtime ) ;
ap -> idletime++ ;
}
void conclude ( struct airport *ap, int endtime )
{
printf ( "\tSimulation has concluded after %d units.\n", endtime ) ;
printf ( "\tTotal number of planes processed: %d\n", ap -> nplanes ) ;
printf ( "\tNumber of planes landed: %d\n", ap -> nland ) ;
printf ( "\tNumber of planes taken off: %d\n", ap -> ntakeoff ) ;
printf ( "\tNumber of planes refused use: %d\n", ap -> nrefuse ) ;
printf ( "\tNumber left ready to land: %d\n", apsize ( *ap, 'l' ) ) ;
printf ( "\tNumber left ready to take off: %d\n", apsize ( *ap, 't' ) ) ;
if ( endtime > 0 )
printf ( "\tPercentage of time runway idle: %lf \n", ( ( double ) ap -> idletime / endtime ) * 100.0 ) ;
if ( ap -> nland > 0 )
printf ( "\tAverage wait time to land: %lf \n", ( ( double ) ap -> landwait / ap -> nland ) ) ;
if ( ap -> ntakeoff > 0 )
printf ( "\tAverage wait time to take off: %lf \n", ( ( double ) ap -> takeoffwait / ap -> ntakeoff ) ) ;
}
int randomnumber ( double expectedvalue )
{
int n = 0 ;
double em ;
double x ;
em = exp ( -expectedvalue ) ;
x = rand( ) / ( double ) INT_MAX ;
while ( x > em )
{
n++ ;
x *= rand( ) / ( double ) INT_MAX ;
}
return n ;
}
void apaddqueue ( struct airport *ap, char type )
{
switch ( tolower( type ) )
{
case 'l' :
addqueue ( ap -> pl, ap -> pln ) ;
break ;
case 't' :
addqueue ( ap -> pt, ap -> pln ) ;
break ;
}
}
struct plane apdelqueue ( struct airport *ap, char type )
{
struct plane p1 ;
switch ( tolower ( type ) )
{
case 'l' :
p1 = delqueue ( ap -> pl ) ;
break ;
case 't' :
p1 = delqueue ( ap -> pl ) ;
break ;
}
return p1 ;
}
int apsize ( struct airport ap, char type )
{
switch ( tolower ( type ) )
{
case 'l' :
return ( size ( *( ap.pl ) ) ) ;
case 't' :
return ( size ( *( ap.pt ) ) ) ;
}
return 0 ;
}
int apfull ( struct airport ap, char type )
{
switch ( tolower ( type ) )
{
case 'l' :
return ( full ( *( ap.pl ) ) ) ;
case 't' :
return ( full ( *( ap.pt ) ) ) ;
}
return 0 ;
}
int apempty ( struct airport ap, char type )
{
switch ( tolower ( type ) )
{
case 'l' :
return ( empty ( *( ap.pl ) ) ) ;
case 't' :
return ( empty ( *( ap.pt ) ) ) ;
}
return 0 ;
}
void myrandomize( )
{
srand ( ( unsigned int ) ( time ( NULL ) % 10000 ) ) ;
}
void main( )
{
struct airport a ;
int i, pri, curtime, endtime ;
double expectarrive, expectdepart ;
struct plane temp ;
clrscr( ) ;
initairport ( &a );
start ( &endtime, &expectarrive, &expectdepart ) ;
for ( curtime = 1 ; curtime 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" ) ;
}
Result:
Shows how cargarage is maintained
Date: Signature of Instructor
EXERCISE NO : 18
simulate a dictionary
Learning Objectives:
To learn about:
|To know how to apply Linked list and Linear search . | |
Problem Description:
Write a program to simulate a dictionary using linked list. It should be a menu driven program with the options for adding a word and its meanings, searching a word and displaying the dictionary. Steps to develop the program are as given below:
1. Declare a structure with the fields as
- a word,
- meaning of a word
- counter that holds the number of meanings
- link to the next node.
Each word added to the list can have maximum 5 meaning(s). Hence, variable used to store meaning(s) of a word would be a two dimensional character array.
2. The program should have following menu.
- Add a word
- Search for a word
- Show dictionary
- Exit
Input: Enter a word and their meaning to register a word in the dictionary.
Output: Display the meaning of the word by entering a word.
/* Dictionary with Linear search implementation*/
#include
#include
#include
#include
#include
#include
struct node
{
char data [ 20 ] ;
char m [ 5 ] [ 20 ] ;
int mcount ;
struct node * link ; } ;
struct node * dic [ 26 ] ;
void add ( char * ) ;
int search ( char * ) ;
void show( ) ;
void deldic( ) ;
void main( )
{
char word [ 20 ] , ch ;
int i ;
clrscr( ) ;
while ( 1 )
{
clrscr( ) ;
printf ( "\n\t\tDictionary\n" ) ;
printf ( "\n\t\t1.Add Word.\n" ) ;
printf ( "\t\t2.Search Word.\n" ) ;
printf ( "\t\t3.Show Dictionary.\n" ) ;
printf ( "\t\t0.Exit." ) ;
printf ( "\n\n\t\tYour Choice ") ;
scanf ( "%d", &ch ) ;
switch ( ch )
{
case 1 :
printf ( "\nEnter any word : " ) ;
fflush ( stdin ) ;
gets ( word ) ;
add ( word ) ;
break ;
case 2 :
printf ( "\nEnter the word to search : " ) ;
fflush ( stdin ) ;
gets ( word ) ;
i = search ( word ) ;
if ( ! i )
printf ( "Word does not exists." ) ;
getch( ) ;
break ;
case 3 :
show( ) ;
getch( ) ;
break ;
case 0 :
deldic( ) ;
exit ( 0 ) ;
default :
printf ( "\nWrong Choice" ) ;
}
}
}
void add ( char * str )
{
int i, j = toupper ( str [ 0 ] ) - 65 ;
struct node * r, * temp = dic [ j ], * q ;
char mean [ 5 ] [ 20 ], ch = 'y' ;
i = search ( str ) ;
if ( i )
{
printf ( "\nWord already exists." ) ;
getch( ) ;
return ;
}
q = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
strcpy ( q -> data, str ) ;
q -> link = NULL ;
for ( i = 0 ; tolower ( ch ) == 'y' && i < 5 ; i++ )
{
fflush ( stdin ) ;
printf ( "\n\nEnter the meaning(s) : " ) ;
gets ( mean [ i ] ) ;
strcpy ( q -> m [ i ] , mean [ i ] ) ;
if ( i != 4 )
printf ( "\nAdd more meanings (y/n) " ) ;
else
printf ( "You cannot enter more than 5 meanings." ) ;
fflush ( stdin ) ;
ch = getche( ) ;
}
q -> mcount = i ;
if ( dic [ j ] == NULL || strcmp ( dic [ j ] -> data, str ) > 0 )
{
r = dic [ j ] ;
dic [ j ] = q ;
q -> link = r ;
return ;
}
else
{
while ( temp != NULL )
{
if ( ( strcmp ( temp -> data, str ) < 0 ) && ( ( strcmp ( temp -> link -> data, str ) > 0 ) ||
temp -> link == NULL ) )
{
q -> link = temp -> link ;
temp -> link = q ;
return ;
}
temp = temp -> link ;
}
}
}
int search ( char *str )
{
struct node *n ;
char temp1 [ 20 ] ;
char temp2 [ 20 ] ;
int i ;
n = dic [ toupper ( str [ 0 ] ) - 65 ] ;
strcpy ( temp2, str ) ;
strupr ( temp2 ) ;
while ( n != NULL )
{
strcpy ( temp1, n -> data ) ;
if ( strcmp ( strupr ( temp1 ), temp2 ) == 0 )
{
printf ( "\n%s\t\t%s", n -> data, n -> m [ 0 ] ) ;
for ( i = 1 ; i < n -> mcount ; i++ )
printf ( "\n\t\t%s", n -> m [ i ] ) ;
return 1 ;
}
n = n -> link ;
}
return 0 ;
}
void show( )
{
struct node *n ;
int i, j ;
printf ( "Word\t\tMeaning\n" ) ;
for ( i = 0 ; i m [ 0 ] ) ;
for ( j = 1 ; j < n -> mcount ; j++ )
printf ( "\n\t\t%s", n -> m [ j ] ) ;
n = n -> link ;
}
}
}
void deldic( )
{
struct node *n, *t ;
int i ;
for ( i = 0 ; i link ;
free ( n ) ;
n = t ;
}
}
}
Result:
Shows meaning of the word that was added by end user in their dictionary.
Date: Signature of Instructor
EXERCISE NO : 19
Duplicate file finder
Learning Objectives:
To learn about:
|To know how to apply Binary search . | |
Problem Description:
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.
Input: Takes data from the system directory.
Output: Display the duplicate files with their path.
/* Program to find files with duplicate names using binary search tree */
#include
#include
#include
#include
#include
#include
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 ;
}
Result:
Shows List of files on console that was having duplicate files.
Date: Signature of Instructor
EXERCISE NO : 20
Sorting of a records
Learning Objectives:
To learn about:
|To know how to apply Binary search . | |
Problem Description:
Write a program that asks user an ID, name, age and salary of 5 employees. Store all the ID's into one array and sort the array in asscending order. Now to display the records in asscending order search for each elements from the array into records and display the corresponding records.
Input: Enter record details user id , age, and salry of 5 employees.
Output: Display the records in asscending order search for each elements from the array into records and display the corresponding records
/* Sorting of a structure on names using bubble sort */
#include
#include
void main( )
{
struct emp
{
char empid[7] ;
char name[25] ;
int age ;
float sal ;
} ;
int i, j ;
struct emp e[5] ;
char id[5][7], temp[7] ;
float ff ( float ) ;
clrscr( ) ;
printf ( "Enter empid, name, age and salary :-\n") ;
for ( i = 0 ; i ................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- nycha section 8 self portal
- section 8 recertification online
- section 8 self service portal
- wyoming section township map
- section 8 tenant log in
- nycha self service portal section 8
- nycha self service section 8
- wyoming section 9 map
- section 162 new york state labor law
- b to b sales
- air b n b ticker
- air b and b stock price today