Page |

19

Lab Assi gnment

-
II

1.

Wr i te a menu dri ven prog ram to per form the fol l ow ing operati ons on a SIN G LYLI N
KED LI ST

i)

C reate a li st

#include <stdio .h>

#include <stdlib.h>

/ / D efine no de structure

struct No de {

int data;

struct No de* next;

};

/ / Functio n to create linked list

struct No de* createL ist( intn) {

struct No de*head = NULL , *tem p = NULL ,*newNo de = NUL L;

intvalue, i;

fo r (i=0 ; i< n; i++ ) {

new No de= (struct Node* )m allo c(sizeo f(struct No de) );

if(newNo de == NULL ){

printf("Memo ry no tallo cated.

\
n");

exit( 0);

printf("Enter data fo r no de%d: ", i + 1 );

scanf("%d",&value);

new No de
-
>data = value;

new No de
-
>next = NULL ;

if (head == NULL ) {

head = new No de;

} e lse {

tem p
-
>next = newNo de;

tem p = new No de;

ret urn head;

/ / Functio n to display t he list

vo id displayL ist( struct No de* head) {

struct No de* current= head;

printf("L inkedL ist: ");

while (current != NULL ){

printf("%d
-
> " ,current
-
>data);

current= current
-
>next;

printf(" NUL L
\
n");

/ / M ain functio n

int m ain() {

int n;

struct No de* head = NULL ;

printf("Enter num bero fno des: " );

Page |
20

scanf("%d",&n);

head= createL ist( n);

display L ist(head);

ret urn 0;
}

Output
:

ii)

I ns er t a rec ord atthe beg inni ng of the li st

#include <stdio .h>

#include <stdlib.h>

/ / D efine no de structure

struct No de {

int data;

struct No de* next;

};

/ / Insert at beginning

struct No de* insertAtBe ginning(struct No de* head, int value) {

struct No de* newNo de = ( struct No de*)m alloc(sizeof(struct No de) );

if(newNo de = = NULL ) {

printf("M emo ry allo catio n failed.

\
n");
exit( 0 );

new No de
-
>data = value;

new No de
-
>next = head;

head = new No de;

return head;

/ / D isplay t he list

vo id displayL ist( struct No de* head) {

struct No de* c urrent = head;

printf("L inkedL ist: ");

while (current != NULL ){

printf("%d
-
> " ,current
-
>data);
current= current
-
>next;

printf(" NUL L
\
n");

/ / M ain functio n

int m ain() {

struct No de* head = NULL ;

int n, val;

/ / Create initial list

printf("Enter num bero f initial no des: " );

scanf("%d",&n);

fo r (int i = 0 ; i < n; i+ +) {

printf("Enter data fo r no de%d: ", i + 1 );

Page |
21
scanf("%d",&val);

head = insertAtBeginning(head, val);

/ / D isplay list after initial creatio n

displayL ist( head);

/ / Insert ano ther no de at beginning

printf("Enter a newvalue to insert at beginning: " );

scanf("%d",&val);

head = insertAtBeginning(head,val);

/ / D isplay list after insert ion

displayL ist( head);

ret urn0 ;

Output
:

i i i)
I ns er t a rec ord atthe end of the l ist

#include <stdio .h>

#include <stdlib.h>

/ / D efine no de structure

struct No de {

int data;

struct No de* next;

};

/ / Functio n to insert at end

struct No de* insertAtE nd(struct No de* head, intvalue) {

struct No de* newNo de = ( struct No de*)m alloc(sizeof(struct No de) );

new No de
-
>data = value;

new No de
-
>next = NUL L ;

if (head == NULL ) {

head = new No de;

} e lse {
struct No de* tem p= head;

while (tem p
-
>next != NULL)

tem p = tem p
-
>next ;

tem p
-
>next = newNo de;

return head;

/ / Functio n to display t he list

vo id displayL ist( struct No de* head) {

struct No de* tem p = head;

printf("L inkedL ist: ");

while (tem p != NUL L) {

printf("%d
-
> " ,tem p
-
>data);

tem p = tem p
-
>next ;

Page |
22

printf(" NUL L
\
n");

/ / M ain functio n

int m ain() {

struct No de* head = NULL ;

int n, val;

printf(" Enter num bero f initial no des: ");

scanf("%d",&n);

fo r (int i = 0 ; i < n; i+ +) {
printf("Enter data fo r no de%d: ", i + 1 );

scanf("%d",&val);

head = insertAtEnd(head, val);

display L ist( head);

printf(" Entervalue to insert at the end: " );

scanf("%d",&val);

head = insertAtEnd(head, val);

display L ist( head);

return 0;

Output
:

i v)

I ns er t a rec ord at a partic ul ar pos iti on

#include <stdio .h>

#include <stdlib.h>

/ / D efine no de structure

struct No de {

int data;

struct No de* next;

};

/ / Functio n to insert at a specific po sitio n

struct No de* insertAtPo sitio n(struct No de* head, intvalue, int positio n) {

struct No de* newNo de = ( struct No de*)m alloc(sizeof(struct No de) );

new No de
-
>data = value;

new No de
-
>next = NUL L ;

if (po sitio n== 1 ){

new No de
-
>next = head;

head = new No de;

} e lse {

struct No de* tem p= head;

fo r (int i = 1 ; i < po sition

-

1 && tem p != NULL ; i+ +) {

tem p = tem p
-
>next ;

if (tem p== NUL L ) {

Page |
23

printf("Po sitio no uto f bo unds.

\
n");

free(newNo de);

} e lse {

new No de
-
>next = tem p
-
>next ;

tem p
-
>next = newNo de;

return head;

}/ / Functio nto display list

vo id displayL ist( struct No de* head) {

struct No de* tem p = head;

printf("L inkedL ist: ");

while (tem p != NUL L) {

printf("%d
-
> " ,tem p
-
>data);

tem p = tem p
-
>next ;
}

printf(" NUL L
\
n");

/ / M ain functio n

int m ain() {

struct No de* head = NULL ;

int n, val, pos;

printf(" Enter num bero f initial no des: ");

scanf("%d",&n);

fo r (int i = 0 ; i < n; i+ +) {

printf("Entervalue forno de %d: " , i + 1 );

scanf("%d",&val);

head = insertAtPo sition(head,val, i+ 1); // Initial insertio n in order

display L ist( head);

printf(" Entervalue to insert: " );

scanf("%d",&val);

printf("Enter po sitio n to insert (1

-
based index): " );

scanf("%d",&po s);

head = insertAtPo sitio n(head,val, po s);

displayL ist( head);

return 0;

Output
:

v)

I ns er t a rec ordafter a parti c ul ar rec ord

#include <stdio .h>

#include <stdlib.h>

/ / No destructure

struct No de {

Page |
24
int data;

struct No de* next;

};

/ / Functio n to insert after a specificvalue

struct No de* insertAfterValue( struct No de* head, int target , intvalue) {

struct No de* tem p = head;

while (tem p != NUL L &&tem p

-
>data != target) {

tem p = tem p
-
>next ;

if (tem p== NUL L ) {

printf(" Record w ithvalue %d no t fo und.

\
n",target) ;

} e lse {

struct No de* newNo de = (struct No de*)m alloc(sizeo f(struct No de) );

new No de
-
>data = value;

new No de
-
>next = temp
-
>next;

tem p
-
>next = newNo de;

return head;

/ / Functio n to display list

vo id displayL ist( struct No de* head) {

struct No de* tem p = head;

printf("L inkedL ist: ");

while (tem p != NUL L) {

printf("%d
-
> " ,tem p
-
>data);

tem p = tem p
-
>next ;

printf(" NUL L
\
n");

/ / Functio n to create list by inserting atend

struct No de* insertAtE nd(struct No de* head, intvalue) {

struct No de* newNo de = ( struct No de*)m alloc(sizeof(struct No de) );

new No de
-
>data = value;

new No de
-
>next = NUL L ;

if (head== NUL L) ret urn new No de;

struct No de* tem p = head;

while (tem p
-
>next != NUL L )

tem p = tem p
-
>next ;

tem p
-
>next = newNo de;

return head;

/ / M ain

int m ain() {

struct No de* head = NULL ;

int n, val, after;

printf(" Enter num ber o f initial no des: ");

scanf("%d",&n);

fo r (int i = 0 ; i < n; i+ +) {

printf("Entervalue forno de %d: " , i + 1 );

scanf("%d",&val);
head = insertAtEnd(head, val);

Page |
25

display L ist( head);

printf(" Enter thevalue after w hich to insert: ");

scanf("%d",&after);

printf("Entervalue to insert: ");

scanf("% d", &val);

head = insertAfterValue( head, after,val);

displayL ist( head);

ret urn0 ;

Output
:

v i)

I ns er t a rec ord before a par tic ul ar rec ord

#include <stdio .h>

#include <stdlib.h>

/ / No destructure

struct No de {

int data;

struct No de* next;

};

/ / Functio n to insert befo re a specificvalue

struct No de* insertBefo reValue( struct No de* head, int target , intvalue) {

struct No de* newNo de = ( struct No de*)m alloc(sizeof(struct No de) );

new No de
-
>data = value;

new No de
-
>next = NUL L ;

/ / If list is em pty o rtarget is at head

if(head == NULL ){

printf("L ist is em pty.

\
n");
free (newNo de);

return head;

if (head
-
>data == target) {

new No de
-
>next = head;

head = new No de;

return head;

/ / Traverse to find no de befo re target

struct No de* tem p = head;

while (tem p
-
>next != NUL L && tem p
-
>next
-
>data != target ) {

tem p = tem p
-
>next ;

if (tem p
-
>next == NUL L) {

printf("Target value %d no t fo und.

\
n",target );

free (newNo de);

Page |
26

} e lse {

new No de
-
>next = temp
-
>next;

tem p
-
>next = newNo de;

} ret urn head;

}/ / D isplay list

vo id displayL ist( struct No de* head) {

struct No de* tem p = head;

printf("L inkedL ist: ");

while (tem p != NUL L) {

printf("%d
-
> " ,tem p
-
>data);

tem p = tem p
-
>next ;

printf(" NUL L
\
n");

}/ / Insert at end utility

struct No de* insertAtE nd(struct No de* head, intvalue) {

struct No de* newNo de = ( struct No de*)m alloc(sizeof(struct No de) );

new No de
-
>data = value;

new No de
-
>next = NUL L ;

if (head == NULL ) ret urnnew No de;

struct No de* tem p= head;

while (tem p
-
>next != NUL L )tem p = tem p
-
>next;

tem p
-
>next = newNo de;

return head;

/ / M ain functio n

int m ain() {

struct No de* head = NULL ;

int n, val, befo re;

printf(" Enter num bero f initial no des: ");

scanf("%d",&n);

fo r (int i = 0 ; i < n; i+ +) {

printf("Entervalue forno de %d: " , i + 1 );

scanf("%d",&val);

head = insertAtEnd(head, val);

display L ist( head);

printf(" Enterthevalue befo re w hich to insert: " );

scanf("%d",&befo re);

printf("Entervalue to insert: ");

scanf("%d",&val);

head = insertBefo reValue(head, befo re,val);

displayL ist( head);

ret urn0 ;

Output
:

Page |
27

v ii )

I ns er t a rec ordi n s orted order ( asc endi ng )

#include <stdio .h>

#include <stdlib.h>

/ / No destructure

struct No de {

int data;

struct No de* next;

};

/ / Functio n to insert inso rted o rder (ascending)

struct No de* insertInSo rtedOrder(struct No de* head, int value) {

struct No de* newNo de = ( struct No de*)m alloc(sizeof(struct No de) );

new No de
-
>data = value;
new No de
-
>next = NUL L ;

/ / If list is em pty o r new no de is to be inserted at thehead

if(head == NULL ||value < head

-
>data) {

new No de
-
>next = head;

head = new No de;

return head;

/ / Findthe no de after w hich t he new no de is to be inserted

struct No de* tem p = head;

while (tem p
-
>next != NUL L && tem p
-
>next
-
>data < value) {

tem p = tem p
-
>next ;

new No de
-
>next = tem p
-
>next;

tem p
-
>next = newNo de;

ret urn head;

/ / Functio n to display list

vo id displayL ist( struct No de* head) {

struct No de* tem p = head;

printf("L inkedL ist ( Ascending O rder): " );

while (tem p != NUL L) {

printf("%d
-
> " ,tem p
-
>data);

tem p = tem p
-
>next ;

printf(" NUL L
\
n");

/ / M ain functio n

int m ain() {

struct No de* head = NULL ;

int n,val;

Page |
28

printf(" Enter num bero felements to insert in so rtedo rder: " );

scanf("%d",&n);

fo r (int i = 0 ; i < n; i+ +) {

printf("Entervalue %d: " , i+ 1);

scanf("%d",&val);
head = insertInSo rtedOrder(head,val);

display L ist( head);

ret urn0 ;

Output
:

v ii i)

Delete a rec ord from the beg i nni ng

#include <stdio .h>

#include <stdlib.h>

/ / No destructure

struct No de {

int data;

struct No de* next;

};

/ / Functio n to delete fro mbeginning

struct No de* deleteFrom Beginning(struct No de* head) {

if(head == NULL ){
printf("L ist is em pty. No thing to delete.
\
n");

return NULL ;

struct No de* tem p = head;

head = head
-
>next;

printf("D eleted no de: %d

\
n", tem p
-
>data);

free (tem p);

return head;

}/ / Functio nto display list

vo id displayL ist( struct No de* head) {

struct No de* tem p = head;

printf("L inkedL ist: ");

while (tem p != NUL L) {

printf("%d
-
> " ,tem p
-
>data);

tem p = tem p
-
>next ;

printf(" NUL L
\
n");

/ / Insert at end utility

struct No de* insertAtE nd(struct No de* head, intvalue) {

Page |
29

struct No de* newNo de = ( struct No de*)m alloc(sizeof(struct No de) );

new No de
-
>data = value;
new No de
-
>next = NUL L ;

if (head== NUL L) ret urn new No de;

struct No de* tem p= head;

while (tem p
-
>next != NUL L )tem p = tem p
-
>next;

tem p
-
>next = newNo de;

ret urn head;

/ / M ain

int m ain() {

struct No de* head = NULL ;

int n, val;

printf(" Enter num bero f initial no des: ");

scanf("%d",&n);
fo r (int i = 0 ; i < n; i+ +) {

printf("Entervalue forno de %d: " , i + 1 );

scanf("%d",&val);

head = insertAtE nd(head,val);

display L ist( head);

// D elete from beginning

head = deleteFrom Beginning(head);

displayL ist( head);

ret urn0 ;

Output
:

i x)

Delete a rec ord from the end

#include <stdlib.h>

/ / No destructure
struct No de {

int data;

struct No de* next;

};

/ / Functio n to delete fro mend

struct No de* deleteFrom End(struct No de* head) {

if(head == NULL ){

printf("L ist is em pty. No thing to delete.

\
n");

return NULL ;

if (head
-
>next = = NULL ) {

printf("D eleted no de:%d

\
n", head
-
>data);

free (head);
Page |
30

return NULL ;

struct No de* tem p = head;

while (tem p
-
>next
-
>next!= NULL ) {

tem p = tem p
-
>next ;

printf(" D eleted no de: %d

\
n", tem p
-
>next
-
>data);

free (tem p
-
>next );
tem p
-
>next = NUL L;

return head;

}/ / Functio nto display list

vo id displayL ist( struct No de* head) {

struct No de* tem p = head;

printf("L inkedL ist: ");

while (tem p != NUL L) {

printf("%d
-
> " ,tem p
-
>data);

tem p = tem p
-
>next ;

printf(" NUL L
\
n");

}/ / Insert at end utility

struct No de* insertAtE nd(struct No de* head, intvalue) {

struct No de* newNo de = ( struct No de*)m alloc(sizeof(struct No de) );

new No de
-
>data = value;

new No de
-
>next = NUL L ;

if (head == NULL ) return newNo de;

struct No de* tem p = head;

while (tem p
-
>next != NUL L )tem p = tem p
-
>next;

tem p
-
>next = newNo de;

ret urn head;

/ / M ain functio n

int m ain() {

struct No de* head = NULL ;

int n, val;

printf(" Enter num bero f initial no des: ");

scanf("%d",&n);

fo r (int i = 0 ; i < n; i+ +) {

printf("Entervalue forno de %d: " , i + 1 );

scanf("%d",&val);

head = insertAtEnd(head, val);

display L ist( head);

/ / D elete from end

head = deleteFrom End(head);

displayL ist( head);

return 0;

Output
:
Page |
31

x)

Delete a par tic ul ar rec ord

#include <stdio .h>

#include <stdlib.h>

/ / No destructure

struct No de {

int data;

struct No de* next;

};

/ / D elete no de by value

struct No de* deleteBy Value( struct No de* head, int target ) {

if(head == NULL ){

printf("L ist is em pty. No thing to delete.

\
n");

return NULL ;
}

struct No de* tem p = head;

struct No de* prev = NULL ;

/ / If t he no de to delete isthe head

if(head
-
>data = =target ){

head = head
-
>next;

printf("D eleted no dewithvalue: % d

\
n", tem p
-
>data);

free (tem p);

return head;

// Search fo r t he no de to delete
while (tem p != NUL L &&tem p
-
>data != target) {

prev = tem p;

tem p = tem p
-
>next ;

if (tem p== NUL L ) {

printf("Value%d no t found in the list.

\
n", target) ;

return head;

prev
-
>next = tem p
-
>next;

printf("D eleted no de with value: %d

\
n",tem p
-
>data);
free (tem p);

return head;

}/ / D isplay list

vo id displayL ist( struct No de* head) {

struct No de* tem p = head;

printf("L inkedL ist: ");

while (tem p != NUL L) {

printf("%d
-
> " ,tem p
-
>data);

tem p = tem p
-
>next ;

Page |
32

printf(" NUL L
\
n");
}

/ / Insert at end utility

struct No de* insertAtE nd(struct No de* head, intvalue) {

struct No de* newNo de = ( struct No de*)m alloc(sizeof(struct No de) );

new No de
-
>data = value;

new No de
-
>next = NUL L ;

f (head == NULL )return newNo de;

struct No de* tem p = head;

while (tem p
-
>next != NUL L )tem p = tem p
-
>next;

tem p
-
>next = newNo de;

return head;

}/ / M ain

int m ain() {
struct No de* head = NULL ;

int n, val, target;

printf(" Enter num bero f initial no des: ");

scanf("%d",&n);

fo r (int i = 0 ; i < n; i+ +) {

printf("Entervalue forno de %d: " , i + 1 );

scanf("%d",&val);

head = insertAtEnd(head, val);

display L ist( head);

printf(" Entervalue to delete: ");

scanf("%d",&target );

head = deleteBy Value( head, target );

display L ist( head);

return 0;

}
Output
:

2.

Wr i te a menu dri ven prog ram to per form the fol l ow ing operati ons on a CI RC ULAR
LIN KED
LI ST

i)

C reate a circ ul ar l i st

ii)

I ns er t a rec ordi n ac irc ul ar l ist

i i i)

Delete a rec ord from thec irc ul ar l i st

i v)

Delete t he enti reci rc ul ar list

v)

C ount the total number ofrec ords i n t he circ ul ar l i st

v i)

Di s pl ay t he circ ul ar l i st

#include <stdio .h>

Page |
33
#include <stdlib.h>

struct No de {

int data;

struct No de* next;

};

struct No de* last= NULL ;

/ / Functio n to create acircular linked list

vo id createL ist( int data) {

struct No de* newNo de = ( struct No de*)m alloc(sizeof(struct No de) );

new No de
-
>data = data;

new No de
-
>next = new No de;

last = newNo de;

printf("Circular list created w ith no de %d.

\
n", data);

/ / Functio n to insert a no de
vo id insert( int data) {

if(last== NUL L ) {

createL ist( data);

return;

}struct No de* newNo de= (struct No de* )m allo c(sizeo f(struct No de) );

new No de
-
>data = data;

new No de
-
>next = last
-
>next;

last
-
>next = newNo de;

last = newNo de;

printf(" Inserted no dewith data % d.

\
n", data);

}/ / Functio nto delete a node

vo id deleteNode( int key ) {

if(last== NUL L ) {

printf("L ist is em pty.

\
n");

return;

}struct No de*tem p= last

-
>next , * prev = last; / / Single no de case

if(last== last
-
>next && last
-
>data== key ){

free (last);

last = NULL ;

printf("D eleted no dewith key % d.

\
n", key );

return;

} do {

if(tem p
-
>data = = key){

if ( tem p== last)

last= prev;

prev
-
>next = tem p
-
>next ;

free(tem p);

printf("Deleted no de w ith key %d.

\
n",key );

return;

}prev = tem p;

tem p = tem p
-
>next ;

} w hile(tem p != last
-
>next );
printf(" Key %d not fo und.
\
n", key );

}/ / Functio nto delete t heentire list

vo id deleteAll(){

Page |
34

if(last== NUL L ) {

printf("L ist is alreadyem pty.

\
n");

return;

} struct No de * tem p = last

-
>next;

struct No de*next No de;

while (tem p != last) {

next No de = tem p
-
>next;
free (tem p);

tem p = next No de;

free (last);

last = NUL L;

printf("Entirecircular listdeleted.
\
n");

}/ / Functio nto co untthe num bero f no des

vo id co untNodes() {

if(last== NUL L ) {

printf("L ist is em pty.

\
n");

return;

} int co unt =0 ;

struct No de* tem p = last

-
>next;
do {

co unt+ +;

tem p = tem p
-
>next ;

} w hile(tem p != last
-
>next );

printf("To tal no des: % d

\
n", co unt);

}/ / Functio nto display t he list

vo id display () {

if(last== NUL L ) {

printf("L ist is em pty.

\
n");

return;

}struct No de* tem p= last

-
>next;

printf("CircularL inkedL ist: " );

do {

printf("%d ", tem p

-
>data);

tem p = tem p
-
>next ;

} w hile(tem p != last
-
>next );

printf("
\
n");

}int m ain() {

intcho ice, data;

do {

printf("
\
n
---

Circular L inked L ist Menu

---
\
n");
printf("1 . Create L ist
\
n");

printf("2 . Insert Reco rd

\
n");

printf("3 .D elete Reco rd

\
n");

printf("4 .D elete Entire L ist

\
n");

printf("5 . Co unt Reco rds

\
n");

printf("6 .D isplay L ist

\
n");

printf(" 0 . Ex it
\
n");

printf("Enteryo ur cho ice: ");

scanf("%d",&c ho ice);
Page |
35

switch (cho ice) {

case1 :

if ( last != NUL L)

printf("L ist already c reated.

\
n");

else {

printf("E nter data: ");

scanf("% d", & data);

createL ist( data);

break;

case2 :
printf("Enter datato insert: " );

scanf("% d",&data);

insert( data);

break;

case3 :

printf("Enter datato delete: " );

scanf("% d",&data);

deleteNo de( data);

break;

case4 :

deleteAll();

break;

case5 :

co untNodes( );

break;
case6 :

display();

break;

case0 :

printf("Ex iting program .

\
n");

break;

default:

printf("Invalid c hoice!
\
n");

} w hile(cho ice !=0 );

ret urn0 ;

Output
:
Page |
36

3.

Wr i te a menu dri ven prog ram to per form the fol l ow ing operati ons on a DOUB LY LIN
KED
LI ST

i)

C reate a doubl y l i nked l ist

ii)

I ns er t a rec ord atthe beg inni ng of the li st

i i i)

I ns er t a rec ord atthe end of the l ist

i v)

I ns er t a rec ord at a partic ul ar pos iti on

v)

Delete a rec ord from the beg i nni ng

v i)

Delete a rec ord from the end

v ii )

Delete a par tic ul ar rec ord

v ii i)

Delete a rec ord from a parti c ul ar posi ti on

i x)

Delete t he enti rel ist

x)

C ount the total number ofrec ords i n t he li st

xi)

S earc h for a par tic ul ar record

Page |
37

xii )

Di s pl ay t he li st

#include <stdio .h>

#include <stdlib.h>

struct No de {

int data;

struct No de*prev, * next ;

};

struct No de* head = NUL L;

/ / Create and insert at e nd

vo id create( int data) {

struct No de* newNo de = ( struct No de*)m alloc(sizeof(struct No de) );

new No de
-
>data = data;

new No de
-
>prev = newNo de
-
>next = NULL ;

if (head == NUL L ) {

head = new No de;

} e lse {

struct No de* tem p= head;

while (tem p
-
>next !=NUL L )

tem p = tem p
-
>next ;
tem p
-
>next = newNo de;

new No de
-
>prev = temp;

printf(" No dewith data %d c reated.

\
n", data);

vo id insertAtBeginning(int data) {

struct No de* newNo de = ( struct No de*)m alloc(sizeof(struct No de) );

new No de
-
>data = data;

new No de
-
>prev = NULL ;

new No de
-
>next = head;

if (head != NULL )
head
-
>prev = new No de;

head = newNo de;

printf(" Inserted at beginning: % d

\
n", data);

vo id insertAtEnd(int data){

create( data);

vo id insertAtPo sitio n(int pos, int data) {

if(po s<= 0 ){

printf(" Invalid po sitio n.

\
n");

return;

if(po s== 1 ){

insertAtBeginning(data);
return;

struct No de* tem p= head;

fo r (int i = 1 ; tem p != NUL L && i < po s

-

1 ; i++ )

tem p = tem p
-
>next ;

if (tem p = = NUL L) {

Page |
38

printf("Po sitio n o ut o frange.

\
n");

return;

struct No de* newNo de = (struct No de* )m allo c(sizeo f(struct No de) );

new No de
-
>data = data;

new No de
-
>next = tem p
-
>next;

new No de
-
>prev = tem p;

if (tem p
-
>next != NUL L)

tem p
-
>next
-
>prev = newNo de;

tem p
-
>next = newNo de;

printf(" Inserted%d at positio n%d

\
n", data, po s);

vo id deleteFrom Beginning() {

if(head == NULL ){
printf("L ist is em pty.
\
n");

return;

}struct No de* tem p= head;

head = head
-
>next;

if (head != NULL )

head
-
>prev = NULL ;

printf(" Deleted from beginning: % d

\
n", tem p
-
>data);

free (tem p);

}vo id deleteFrom End(){

if(head == NULL ){

printf("L ist is em pty.

\
n");

return;

} struct No de* tem p = head;

if(tem p
-
>next == NUL L ) {

printf("D eleted from end: % d

\
n", tem p
-
>data);

free (tem p);

head = NUL L;

return;

while (tem p
-
>next != NULL)

tem p = tem p
-
>next ;

printf(" D eleted from end: %d

\
n",tem p
-
>data);

tem p
-
>prev
-
>next = NULL ;

free (tem p);

}vo id deleteBy Value( intkey) {

struct No de* tem p = head;

while (tem p != NULL && tem p

-
>data!= key )

tem p = tem p
-
>next ;

if (tem p== NUL L ) {

printf("Value no t fo und.
\
n");

return;

}
if (tem p
-
>prev != NUL L )

tem p
-
>prev
-
>next =tem p
-
>next ;

else

head = tem p
-
>next;

Page |
39

5 4 |Page

if(tem p
-
>next != NUL L )

tem p
-
>next
-
>prev = tem p
-
>prev;

printf(" Deleted no dewithvalue: % d

\
n",key );

free (tem p);

}vo id deleteAtPo sitio n(int po s) {

if(head == NULL || pos <= 0 ) {

printf(" Invalid o peration.

\
n");

return;

struct No de* tem p = head;

fo r(int i = 1; tem p != NULL && i< po s; i+ +)

tem p = tem p
-
>next ;

if (tem p == NULL ){
printf("Po sitio n not found.
\
n");

return;

if (tem p
-
>prev != NUL L)

tem p
-
>prev
-
>next =tem p
-
>next ;

else

head = tem p
-
>next;

if (tem p
-
>next != NUL L )

tem p
-
>next
-
>prev = tem p
-
>prev;

printf("D eleted no de atpo sitio n % d: % d

\
n", po s, tem p
-
>data);

free (tem p);

}vo id deleteAll() {

struct No de* tem p;

while (head != NUL L ) {

tem p = head;

head = head
-
>next;

free (tem p);

printf("D eleted e ntire list.

\
n");

vo id co untNodes() {
int co unt = 0;

struct No de* tem p = head;

while (tem p != NULL ) {

co unt+ +;

tem p = tem p
-
>next ;

printf("To tal num bero f no des: % d

\
n", co unt) ;

}vo id search(int key ) {

struct No de* tem p = head;

int po s= 1;

while (tem p != NULL ) {

if(tem p
-
>data = = key){

printf("Value%d fo und at po sitio n%d

\
n",key, po s);

return;

Page |
40

po s+ +;

tem p = tem p
-
>next ;

printf(" Value %d no t fo und in the list.

\
n", key );

}vo id display() {

struct No de* tem p = head;

if(tem p == NUL L ){

printf("L ist is em pty.

\
n");
return;

printf(" Do ubly L inked L ist:");

while (tem p != NUL L) {

printf("%d ", tem p

-
>data);

tem p = tem p
-
>next ;

printf("
\
n");

int m ain() {

intcho ice, data, po s;

do {

printf("
\
n
---

D o ubly L inked L istM enu

---
\
n");

printf("1 . Create L ist

\
n2 . Insert at Beginning
\
n3 . Insert atEnd
\
n");

printf("4 . Insert at Po sitio n

\
n5 . Delete from Be ginning
\
n6 . Delete fro m
End
\
n");

printf("7 .D elete by Value

\
n8 .D elete at Po sitio n
\
n9 . DeleteEntire L ist
\
n");

printf("10 . Co unt No des

\
n11 . Search
\
n1 2 .D isplay
\
n0 . Exit
\
n");

printf("Enteryo ur cho ice: ");

scanf("%d",&c ho ice);

switch (cho ice) {

case1 :

case3 :

printf("Enter data: " );

scanf("% d",&data);

create( data);

break;

case2 :

printf("Enter data: " );

scanf("% d",&data);

insertAtBe ginning(data);
break;

case4 :

printf("Enter po sitio n and data: " );

scanf("% d%d", & po s,&data);

insertAtPo sitio n(po s, data);

break;

case5 :

deleteFrom Beginning();

break;

case6 :

deleteFrom End();

Page |
41

break;
case7 :

printf("Entervalue to delete: " );

scanf("% d",&data);

deleteBy Value( data);

break;

case8 :

printf("Enter po sitio n to delete: ");

scanf("% d",&pos);

deleteAtPo sitio n(po s);

break;

case9 :

deleteAll();

break;

case1 0:
co untNodes( );

break;

case1 1:

printf("Entervalue to search: ");

scanf("% d",&data);

search(data);

break;

case1 2:

display();

break;

case0 :

printf("Ex iting.
\
n");

break;

default:
printf("Invalid c hoice.
\
n");

} w hile(cho ice !=0 );

ret urn0 ;

Output
:

Page |
42

4.

Wr i te a menu dri ven prog ram to i mpl ement aSTAC Kus i ng an array of si ze1 0.

#include <stdio .h>

#define SIZE1 0

int stack[SIZE];

int to p=
-
1;
/ / P ush functio n

vo id push(intvalue) {

if(to p = = SIZE
-

1){

printf(" Stack O verflo w! Canno t push %d.

\
n",value) ;

} e lse {

to p+ +;

stack[to p]=value;

printf(" P ushed % d to the stack.

\
n",value);

Page |
43

/ / Po p functio n

vo id po p() {
if(to p = =
-
1 ){

printf(" Stack Underflow! Cannot po p.

\
n");

} e lse {

printf("Po pped % d from t he stack.

\
n", stack[to p]);

to p
--
;

}/ / Peek functio n

vo id peek () {

if(to p = =
-
1 ){

printf(" Stack is em pty.

\
n");

} e lse {
printf("To p e lement is%d
\
n",stack[to p]);

}/ / D isplay functio n

vo id display () {

if(to p = =
-
1 ){

printf(" Stack is em pty.

\
n");

} e lse {

printf(" Stack e lements: " );

fo r (int i = to p; i >=0 ; i
--
){

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

printf("
\
n");

int m ain() {

intcho ice,value;

do {

printf("
\
n
---

StackM enu ( Array Im plementatio n)

---
\
n");

printf("1 .P ush
\
n2 . Po p
\
n3 .Peek
\
n4 . D isplay
\
n0 . Exit
\
n");

printf("Enteryo ur cho ice: ");

scanf("%d",&c ho ice);
switch ( cho ice) {

case1 :

printf("Entervalue to push: " );

scanf("% d",&value) ;

push(value);

break;

case2 :

po p();

break;

case3 :

pee k();

break;

case4 :

display();
break;

Page |
44

case0 :

printf("Ex iting program .

\
n");

break;

default:

printf("Invalid c hoice! Try again.

\
n");

} w hile(cho ice !=0 );

ret urn0 ;

Output
:
5.

Wr i te a menu dri ven prog ram to i mpl ement aSTAC Kus i ng al i nked
-
l ist.

#include <stdio .h>

#include <stdlib.h>

/ / D efine a no de structure

struct No de {

int data;

struct No de* next;

};

struct No de* to p= NUL L ;

/ / P ush functio n

vo id push(intvalue) {

struct No de* newNo de = ( struct No de*)m alloc(sizeof(struct No de) );

if(!newNo de) {

printf(" Heap Overflow! Canno t push %d.

\
n",value) ;

Page |
45
return;

new No de
-
>data = value;

new No de
-
>next = to p;

to p = newNo de;

printf("P ushed%d to t he stack.

\
n",value) ;

}/ / Po p functio n

vo id po p() {

if(to p = = NUL L) {

printf(" Stack Underflow! Cannot po p.

\
n");

return;

}
struct No de* tem p = to p;

printf("Po pped % d fromthe stack.

\
n", tem p
-
>data);

to p = to p
-
>next;

free (tem p);

/ / Peek functio n

vo id peek () {

if(to p = = NUL L) {

printf(" Stack is em pty.

\
n");

} e lse {

printf("To p e lement is%d

\
n",to p
-
>data);
}

/ / D isplay functio n

vo id display () {

if(to p = = NUL L) {

printf(" Stack is em pty.

\
n");

return;

struct No de* tem p = to p;

printf(" Stack e lem ents: ");

while (tem p != NUL L) {

printf("%d ", tem p

-
>data);

tem p = tem p
-
>next ;

}
printf("
\
n");

int m ain() {

intcho ice,value;

do {

printf("
\
n
---

StackM enu ( L inkedL ist Im plementatio n)

---
\
n");

printf("1 .P ush
\
n2 . Po p
\
n3 .Peek
\
n4 . D isplay
\
n0 . Exit
\
n");

printf("Enteryo ur cho ice: ");

scanf("%d",&c ho ice);

switch (cho ice) {

case1 :

printf("Entervalue to push: " );

scanf("% d",&value) ;

push(value);

Page |
46

break;

case2 :

po p();

break;

case3 :

pee k();
break;

case4 :

display();

break;

case0 :

printf("Ex iting program .

\
n");

break;

default:

printf("Invalid c hoice! Try again.

\
n");

} w hile(cho ice !=0 );

ret urn 0;

Output
:
6.

Wr i te a menu dri ven prog ram to i mpl ement a QUEUE usi ng an array ofs i ze 10 .

#include <stdio .h>

#define SIZE1 0

int queue[SIZE];

int fro nt =
-
1 , rear=
-
1;

/ / Enqueue functio n

vo idenqueue(intvalue) {

Page |
47

if(rear = = SIZE
-

1){

printf("Queue O verflow! Cannot insert %d.

\
n",value) ;

} e lse {
if(fro nt ==
-
1)

fro nt = 0 ;

rear+ +;

queue[rear]=value;

printf("Enqueued %d to t he queue.
\
n",value);

/ / D equeue functio n

vo id dequeue( ){

if(fro nt ==
-
1 || fro nt > rear) {

printf("Queue Underflo w! Cannot dequeue.

\
n");

} e lse {

printf("D equeued %d from the queue.

\
n", queue[fro nt]);

fro nt+ +;

if(fro nt > rear) {

fro nt = rear=
-
1;

/ / Peek functio n

vo id peek () {

if(fro nt ==
-
1 || fro nt > rear) {

printf("Queue is em pty.
\
n");

} e lse {

printf(" Fro nt element is % d

\
n", queue[fro nt]);
}

/ / D isplay functio n

vo id display () {

if(fro nt ==
-
1 || fro nt > rear) {

printf("Queue is em pty.
\
n");

} e lse {

printf("Queue e lem ents: " );

fo r (int i = fro nt; i < = rear; i+ +) {

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

printf("
\
n");

}
}int m ain() {

intcho ice,value;

do {

printf("
\
n
---

QueueM enu ( Array Im plementatio n)

---
\
n");

printf("1 . Enqueue
\
n2 . D equeue
\
n3 . Pee k
\
n4 .D isplay
\
n0 . Exit
\
n");

printf("Enteryo ur cho ice: ");

scanf("%d",&c ho ice);

switch(cho ice) {

case1 :
printf("Entervalue to enqueue: " );

Page |
48

scanf("% d",&value) ;

enqueue(value);

break;

case2 :

dequeue();

break;

case3 :

pee k();

break;

case4 :

display();
break;

case0 :

printf("Ex iting program .

\
n");

break;

default:

printf("Invalid c hoice! Try again.

\
n");

} while ( cho ice!=0 );

ret urn 0;

Output
:

7.

Wr i te a menu dri ven prog ram to i mpl ement a QUEUE usi ng a li nked l i st.

#include <stdio .h>

#include <stdlib.h>

/ / D efine a no de structure

struct No de {

int data;

Page |
49

struct No de* next;

};

struct No de *fro nt = NULL ,*rear= NULL ;

/ / Enqueue functio n

vo idenqueue(intvalue) {

struct No de* newNo de = ( struct No de*)m alloc(sizeof(struct No de) );

if(!newNo de) {

printf("M emo ry allo catio n failed!Canno t e nqueue %d.

\
n",value);

return;

}
new No de
-
>data = value;

new No de
-
>next = NUL L ;

if (rear== NUL L) {

fro nt = rear= new No de;

} e lse {

rear
-
>next = newNo de;

rear= new No de;

printf(" Enqueued %dto the queue.

\
n",value);

}/ / Dequeue functio n

vo id dequeue( ){

if(fro nt == NULL ){

printf("Queue Underflo w! Cannot dequeue.

\
n");

return;

struct No de* tem p = fro nt;

printf("D equeued % d from t he queue.

\
n", fro nt
-
>data);

fro nt = fro nt
-
>next;

if(fro nt == NULL )

rear= NULL ;

free (tem p);

}/ / Peek functio n

vo id peek () {

if(fro nt == NULL ){

printf("Queue is em pty.
\
n");
} e lse {

printf(" Fro nt element is % d

\
n", fro nt
-
>data);

/ / D isplay functio n

vo id display () {

if(fro nt == NULL ){

printf("Queue is em pty.
\
n");

return;

struct No de* tem p = fro nt;

printf("Queueelem ents: ");

while (tem p != NUL L) {

printf("%d ", tem p

-
>data);

tem p = tem p
-
>next ;

Page |
50

printf("
\
n");

}int m ain() {

intcho ice,value;

do {

printf("
\
n
---

QueueM enu ( L inkedL ist Im plem entatio n)

---
\
n");

printf("1 . Enqueue
\
n2 . D equeue
\
n3 . Pee k
\
n4 .D isplay
\
n0 . Exit
\
n");

printf("Enteryo ur cho ice: ");

scanf("%d",&c ho ice);

switch (cho ice) {

case1 :

printf("Entervalue to enqueue: " );

scanf("% d",&value) ;

enqueue(value);

break;

case2 :

dequeue();

break;
case3 :

pee k();

break;

case4 :

display();

break;

case0 :

printf("Ex iting program .

\
n");

break;

default:

printf("Invalid c hoice! Try again.

\
n");

} w hile(cho ice !=0 );

ret urn0 ;

Output
:

Page |
51

8.

Wr i te a menu dri ven prog ram to i mpl ement aC I RC ULAR QUEUE us i ng a li nked l ist.

#include <stdio .h>

#include <stdlib.h>

/ / No de definitio n

struct No de {

int data;

struct No de* next;

};

struct No de *fro nt = NULL ,*rear= NULL ;

/ / Enqueueo peratio n

vo idenqueue(intvalue) {

struct No de* newNo de = ( struct No de*)m alloc(sizeof(struct No de) );

if(!newNo de) {

printf("M emo ry allo catio n failed!

\
n");

return;

new No de
-
>data = value;

new No de
-
>next = NUL L ;

if(fro nt == NULL ){

fro nt = rear= new No de;

rear
-
>next = fro nt; // Circular link

} e lse {

rear
-
>next = newNo de;

rear= new No de;

rear
-
>next = fro nt;

Page |
52

printf(" Enqueued %d to t he circular queue.

\
n",value);

}/ / Dequeueo peratio n

vo id dequeue( ){

if(fro nt == NULL ){

printf("Queue Underflo w! Cannot dequeue.

\
n");

return;

}
if (fro nt== rear){ // Only one no de

printf("D equeued %d from the c ircular queue.

\
n", fro nt
-
>data);

free (fro nt) ;

fro nt = rear= NULL ;

} e lse {

struct No de* tem p= fro nt;

printf("D equeued %d from the c ircular queue.

\
n", tem p
-
>data);

fro nt = fro nt
-
>next;

rear
-
>next = fro nt;

free (tem p);

}

}/ / Peek o peratio n

vo id peek () {

if(fro nt == NULL ){

printf("CircularQueueis em pty.
\
n");

} e lse {

printf(" Fro nt element is % d

\
n", fro nt
-
>data);

/ / D isplay o peratio n

vo id display () {

if(fro nt == NULL ){

printf("CircularQueueis em pty.
\
n");

return;
}

struct No de* tem p= fro nt;

printf("CircularQueueelements: ");

do {

printf("%d ", tem p

-
>data);

tem p = tem p
-
>next ;

} w hile(tem p != fro nt);

printf("
\
n");

int m ain() {

intcho ice,value;

do {

printf("
\
n
---

Circular Queue Menu ( L inked L ist Implem entatio n)

---
\
n");

printf("1 . Enqueue
\
n2 . D equeue
\
n3 . Pee k
\
n4 .D isplay
\
n0 . Exit
\
n");

printf("Enteryo ur cho ice: ");

scanf("%d",&c ho ice);

switch (cho ice) {

case1 :

printf("Entervalue to enqueue: " );

Page |
53
scanf("% d",&value) ;

enqueue(value);

break;

case2 :

dequeue();

break;

case3 :

pee k();

break;

case4 :

display();

break;

case0 :

printf("Ex iting program .

\
n");
break;

default:

printf("Invalid c hoice! Try again.

\
n");

} w hile(cho ice !=0 );

return 0;

Output
:

9.

Wr i te a menu dri ven prog ram to i mpl ement a PRI ORIT Y QUEUE usi ng a li nked l ist.

#include <stdio .h>

#include <stdlib.h>

/ / No destructurewith priority
Page |
54

struct No de {

int data;

int prio rity ;

struct No de* next;

};

struct No de* fro nt = NUL L;

/ / Enqueuewith prio rity

vo idenqueue(intvalue, intpriority ) {

struct No de* newNo de = ( struct No de*)m alloc(sizeof(struct No de) );

new No de
-
>data = value;

new No de
-
>prio rity = prio rity;

new No de
-
>next = NUL L ;
// Insert at beginning if it's t he highest priority

if(fro nt == NULL || prio rity < fro nt

-
>prio rity ) {

new No de
-
>next = fro nt;

fro nt = new No de;

} e lse {

/ / Traverse to co rrect po sitio n

struct No de* tem p= fro nt;

while (tem p
-
>next !=NUL L && tem p
-
>next
-
>priority <= prio rity)

tem p = tem p
-
>next ;

new No de
-
>next = tem p
-
>next;
tem p
-
>next = newNo de;

printf(" Enqueued %dwithpriority % d.

\
n",value, prio rity );

}/ / Dequeue (highest priority first)

vo id dequeue( ){

if(fro nt == NULL ){

printf("P rio rity Q ueueUnderflow! Canno t dequeue.

\
n");

return;

} struct No de* tem p = fro nt;

printf("D equeued % dwith prio rity % d.

\
n", tem p
-
>data, tem p
-
>prio rity );

fro nt = fro nt
-
>next;
free (tem p);

}/ / Peek fro nt element

vo id peek () {

if(fro nt == NULL ){

printf("P rio rity Q ueue is em pty.

\
n");

} e lse {

printf(" Fro nt element: %d w ith prio rity % d

\
n", front
-
>data, fro nt
-
>prio rity);

}/ / D isplay queue

vo id display () {

if(fro nt == NULL ){

printf("P rio rity Q ueue is em pty.

\
n");
return;

}struct No de* tem p= front;

printf("P rio rity Q ueue elements:

\
n");

while (tem p != NUL L) {

printf("D ata: %d,P riority : % d

\
n", tem p
-
>data, temp
-
>prio rity);

tem p = tem p
-
>next ;

Page |
55

}int m ain() {

intcho ice,value, prio rity;

do {

printf("
\
n
---

P riority Queue Menu ( L inked L ist Implem entatio n)

---
\
n");

printf("1 . Enqueue
\
n2 . D equeue
\
n3 . Pee k
\
n4 .D isplay
\
n0 . Exit
\
n");

printf("Enteryo ur cho ice: ");

scanf("%d",&c ho ice);

switch (cho ice) {

case1 :

printf("Entervalue and prio rity : ");

scanf("% d%d", &value, &prio rity);

enqueue(value, prio rity);

break;

case2 :

dequeue();

break;

case3 :

pee k();

break;

case4 :

display();

break;

case0 :

printf("Ex iting program .

\
n");

break;
default:

printf("Invalid c hoice! Try again.

\
n");

} w hile(cho ice !=0 );

return 0;

Output
:

Page |
56

1 0.

Wr i te a menu dri ven prog ram to i mpl ement a DEQUEUE usi ng al i nked l ist.

#include <stdio .h>

#include <stdlib.h>
/ / No de definitio n

struct No de {

int data;

struct No de* prev;

struct No de* next;

};

struct No de *fro nt = NULL ,*rear= NULL ;

/ / Insert at fro nt

vo id insertFro nt( intvalue) {

struct No de* newNo de = ( struct No de*)m alloc(sizeof(struct No de) );

new No de
-
>data = value;

new No de
-
>prev = NULL ;

new No de
-
>next = fro nt;

if (fro nt== NUL L )

fro nt = rear= new No de;

else {

fro nt
-
>prev = new No de;

fro nt = new No de;

printf(" Inserted%d at front.

\
n",value);

Page |
57

/ / Insert at rear

vo id insertRear(intvalue) {

struct No de* newNo de = ( struct No de*)m alloc(sizeof(struct No de) );

new No de
-
>data = value;

new No de
-
>next = NUL L ;

new No de
-
>prev = rear;

if (rear = = NULL )

fro nt = rear= new No de;

else {

rear
-
>next = newNo de;

rear= new No de;

printf(" Inserted % d at rear.

\
n",value);

/ / D elete from fro nt

vo id deleteFro nt( ) {

if(fro nt == NULL ){
printf("D equeue Underflow! Cannot delete from fro nt.
\
n");

return;

struct No de* tem p = fro nt;

printf("D eleted % d from fro nt.

\
n", tem p
-
>data);

fro nt = fro nt
-
>next;

if (fro nt== NUL L)

rear= NULL ;

else

fro nt
-
>prev = NULL ;

free(tem p);

}
/ / D elete from rear

vo id deleteRear() {

if(rear = = NUL L) {

printf("D equeue Underflow! Cannot delete from rear.

\
n");

return;

struct No de* tem p= rear;

printf("D eleted % d from rear.

\
n", tem p
-
>data);

rear = rear
-
>prev ;

if(rear = = NUL L)

fro nt = NUL L;

else
rear
-
>next = NULL ;

free (tem p);

}/ / D isplay DEQUEUE

vo id display () {

if(fro nt == NULL ){

printf("D equeue isempty.

\
n");

return;

Page |
58

struct No de* tem p= fro nt;

printf("D equeue elements: " );

while (tem p != NUL L) {

printf("%d ", tem p
-
>data);

tem p = tem p
-
>next ;

printf("
\
n");

}int m ain() {

intcho ice,value;

do {

printf("
\
n
---

D EQUEUEM enu (L inkedL ist Im plem entatio n)

---
\
n");

printf("1 . Insert at Front

\
n2 . Insert at Rear
\
n");

printf("3 .D elete from Fro nt

\
n4 .D elete from Rear
\
n");

printf("5 .D isplay
\
n0 . Exit
\
n");

printf("Enteryo ur cho ice: ");

scanf("%d",&c ho ice);

switch(cho ice) {

case1 :

printf("Entervalue to insert at fro nt: " );

scanf("% d",&value) ;

insertFro nt(value) ;

break;

case2 :
printf("Entervalue to insert at rear:");

scanf("% d",&value) ;

insertRear(value) ;

break;

case3 :

deleteFro nt();

break;

case4 :

deleteRear();

break;

case5 :

display();

break;

case0 :
printf("Ex iting program .
\
n");

break;

default:

printf("Invalid c hoice! Try again.

\
n");

} w hile(cho ice !=0 );

return 0;

Output
:

Page |
59

1 1.
Wr i te a program toreverse a stri ng us i ng stac k.

#include <stdio .h>

#include <string.h>

#define SIZE1 00

/ / Stack im plementatio n

char stack[SIZE];

int to p=
-
1;

/ / P usho peratio n

vo id push(char c h) {

if(to p = = SIZE
-

1){

printf(" Stack O verflo w!

\
n");

} e lse {

stack[+ +to p]= ch;

}/ / Po po peratio n

char po p(){
if(to p = =
-
1 ){

printf(" Stack Underflow!

\
n");

return '
\
0 ';

} e lse {

return stack[to p
--
];

Page |
60

int m ain() {

char str[SIZE],reversed[SIZE];

int i;
printf(" Enter a string: " );

get s(str); // No te: get s() is unsafe; yo u can use fget s() instead

/ / P usheach charactero nto t he stack

fo r (i=0 ; i < strlen(str); i+ +) {

push(str[i]);

/ / Po p c haracters and build reversedstring

fo r (i=0 ; i < strlen(str); i+ +) {

reversed[i] = po p();

reversed[i] = '
\
0 '; / / Null
-
term inate the reversed string

printf(" Reversed string: %s

\
n", reversed);

ret urn 0;
}

Output
:

1 2.

Wr i te a program toc onvert an i nfi x express i on toi tsequi val ent postfi x form.

#include <stdio .h>

#include <cty pe.h>

#include <string.h>

#define SIZE1 00

char stack[SIZE];

int to p=
-
1;

/ / P usho peratio n

vo id push(char c h) {

if(to p = = SIZE
-

1)

printf(" Stack O verflo w

\
n");

else
stack[+ +to p]= ch;

/ / Po p o peratio n

char po p(){

if(to p = =
-
1)

return
-
1;

else

return stack[to p
--
];

/ / Peek to po f stack

char peek() {

if(to p = =
-
1)

return
-
1;
else

return stack[to p];

Page |
61

/ / Get prece denceo fo perato rs

int prece dence( char c h) {

switch (ch) {

case '^': ret urn3 ;

case '*':

case '/ ': ret urn2 ;

case '+':

case '
-
': return 1;

default: ret urn0 ;

}
}

int isOperato r(char c h) {

return c h == '+' || c h== '

-
' || c h = = '*' || c h== '/ ' || c h = = '^';}

int m ain() {

char infix[SIZE], po stfix[SIZE];

int i = 0 , j=0 ;

printf(" Enter infixexpression: " );

scanf("%s" , infix);

while (infix[i] != '

\
0 ') {

char to ken= infix[i];

if (isalnum (to ken)) {

po stfix[j++ ] = to ken;

} e lse if (to ken == '(') {

push(to ken);

} e lse if (to ken == ')') {

while (pee k() != '(' && to p !=
-
1)

po stfix[j++ ] = po p();

po p(); // Remove '('from stack

} e lse if (isOperato r(to ken)) {

while (to p !=
-
1 &&prece dence( peek ()) >= precedence(token))

po stfix[j++ ] = po p();

push(to ken);

i+ +;

while (to p !=
-
1)

po stfix[j+ +] = po p();

po stfix[j] = '
\
0 ';

printf(" Postfixexpressio n: %s
\
n", po stfix);

return 0;

Output
:

1 3.

Wr i te a program toeval uate a postfi xexpres si on using stac k.

#include <stdio .h>

#include <cty pe.h>

Page |
62

#include <stdlib.h>

#define SIZE1 00

int stack[SIZE];

int to p=
-
1;

/ / P usho peratio n
vo id push(intvalue) {

if(to p = = SIZE
-

1)

printf(" Stack O verflo w

\
n");

else

stack[+ +to p]=value;

/ / Po p o peratio n

int po p() {

if(to p = =
-
1 ){

printf(" Stack Underflow

\
n");

exit( 1 );

} e lse {

return stack[to p
--
];

int m ain() {

char po stfix[SIZE];

int i, a, b,result;

printf(" Enter po stfix expressio n: ");

scanf("%s" , po stfix) ;

fo r(i = 0; po stfix[i] != '

\
0 '; i+ +) {

char c h = po stfix[i];

if (isdigit(ch)) {

push(ch
-

'0 '); // co nvertchar digit to int

} e lse {

b= po p();
a = po p();

switch(ch) {

case '+': result = a+ b; break;

case '
-
': result = a
-

b; break;

case '*': result = a* b; break;

case '/ ':

if ( b ==0 ) {

printf(" D iv ision by zero e rror.

\
n");

ret urn1 ;

result = a / b; break;

default:
printf("Invalidoperato r%c
\
n", ch);

ret urn 1;

push(result);

printf(" Result o f po stfixexpressio n=%d

\
n", po p());

return 0;

Page |
63

Output
:

1 4.
Wr i te a program toc onvert an i nfi x express i on toi tsequi val ent prefi x for m.

#include <stdio .h>

#include <string.h>

#include <stdlib.h>

#include <cty pe.h>

#define M AX1 00

char stack[MAX];

int to p=
-
1;

/ / Stack o peratio ns

vo id push(char c ) {

stack[+ +to p] = c ;

char po p(){

return stack[to p
--
];

char peek() {

return stack[to p];

}
int isEmpty() {

return to p==
-
1;

/ / P rece denceo fo perato rs

int prece dence( char o p) {

switch (o p) {

case '^': ret urn3 ;

case '*':

case '/ ': ret urn2 ;

case '+':

case '
-
': return 1;

default: ret urn0 ;

/ / Check if c haracter is o perato r

int isOperato r(char c h) {

return c h == '+' || c h== '

-
' || c h = = '*' || c h== '/ ' || c h = = '^';

/ / Reversea string

vo id reverse(char* str) {

int len = strlen(str), i;

fo r (i=0 ; i < len / 2; i++ ) {

char tem p= str[i];

str[i] =str[len
-

i
-

1 ];

str[len
-

i
-

1 ]= tem p;

}
Page |
64

/ / Co nvert infix to po stfix

vo id infixTo Po stfix(c har* infix, char* po stfix) {

int i, j = 0;

char c h;

fo r (i=0 ; infix[i]; i+ +) {

ch = infix[i];

if (isalnum (ch)) {

po stfix[j++ ] =ch;

} e lse if (ch == ')') {

push(ch);

} e lse if (ch == '(') {

while (!isEm pty ()&& peek() != ')'){

po stfix[j++ ] = po p();
}

po p(); // Remove ')'

} e lse if (isOperato r(ch)) {

while (!isEm pty ()&& precedence( peek() ) > = prece dence( ch)) {

po stfix[j++ ] = po p();

push(ch);

while (!isEm pty ()) {

po stfix[j+ +] = po p();

}po stfix[j] = '

\
0 ';

}/ / Co nvert infix to prefix

vo id infixToP refix(char* infix, char* prefix) {

reverse( infix);

/ / Swap ( and)

fo r (int i = 0 ; infix[i]; i++ ){

if(infix[i] = = '(') infix[i]= ')';

else if ( infix[i] = = ')') infix[i] = '(';

}char po stfix[MAX];

infixTo Po stfix( infix, postfix) ;

reverse( po stfix) ;

strcpy (prefix, po stfix);

}/ / M ain functio n

int m ain() {

char infix[M AX], prefix[MAX];

printf(" Enter an infixexpressio n: ");

scanf("%s" , infix);

infixTo Prefix(infix, prefix);

printf("P refixexpressio n: % s
\
n", prefix) ;
return 0;

Output
:

Page |
65

1 5.

Wr i te a program to perform I nter pol ati on S earc h.

#include <stdio .h>

/ / Interpo latio n Search Functio n

int interpo latio nSearch(intarr[], int n, int key ) {

int low = 0 , high = n

-

1;

while (low <= high & & key>= arr[lo w] && key <= arr[high]) {

if(lo w== high) {

if ( arr[lo w]== key ) ret urn low;

return
-
1;

/ / Estim ate po sitio n

int po s= lo w + ((do uble) (high

-

lo w) / ( arr[high]
-

arr[lo w])) * ( key

-

arr[low]);

if (arr[po s] == key )

return po s;

if(arr[po s] < key )

low = po s + 1 ;

else

high = po s
-

1;

} ret urn
-
1; / / No t fo und

}/ / M ain functio n

int m ain() {

int arr[1 00 ], n, key, index;

printf(" Enter num bero felements: ");

scanf("%d",&n);

printf("Enter%d so rtedelements:
\
n", n);

fo r (int i = 0 ; i < n; i+ +) {

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

printf(" Enter e lement to search: " );

scanf("%d",&key);

index = interpo latio nSearch(arr, n, key );

if (index !=
-
1)
printf("Elem ent%d fo und at index%d.
\
n", key, index);

else

printf("Elem ent%d not fo und in the array.

\
n", key);

ret urn0 ;

Output
:

1 6.

Wr i te a program to fi nd t he fac tori al of a number using rec ursi on.

1

#include <stdio .h>

/ / Recursive functio n to calculate facto rial

Page |
66

lo ng lo ng facto rial(int n) {

if (n ==0 || n == 1)
return 1;

else

return n * facto rial(n

-

1 );

/ / M ain functio n

int m ain() {

int num ;

printf("Enter a no n
-
negative integer: ");

scanf("%d",&num );

if (num <0 ) {

printf("Facto rial is no tdefined fo r negative num bers.

\
n");

} e lse {

lo ng lo ngresult= factorial(num );
printf("Facto rialo f%dis % lld
\
n", num , result);

return 0;

Output
:

1 7.

Wr i te a program togenerate t he terms of Fi bonac ci Ser i es us i ng rec ursi on.

#include <stdio .h>

/ / Recursive functio n to return nth Fibo nacci num ber

int fibo nacci(int n) {

if(n == 0 ) ret urn0 ;

else if ( n == 1) ret urn1 ;

elsereturn fibo nacci(n

-

1 ) + fibo nacci(n
-

2 );
}

/ / M ain functio n

int m ain() {

int n;

printf(" Enter the num berof term s inthe Fibo nacci series: ");

scanf("%d",&n);

if (n <= 0) {

printf("P leaseenterapo sitive num ber.

\
n");

} e lse {

printf(" Fibo nacci Series up to %d term s:

\
n", n);

fo r (int i = 0 ; i < n; i+ +){

printf("% d ", fibo nacci(i));

printf("
\
n");

ret urn 0;

Output
:

Page |
67

1 8.

Wr i te a program to fi nd t he G C D of two or m ore numbers usi ng rec urs i on.

#include <stdio .h>

/ / Recursive functio n to calculate GCD

int gcd(int a, int b) {

if(b == 0 )

return a;

return gcd(b, a % b);

/ / M ain functio n
int m ain() {

int num 1 , num2 ;

printf(" Enter two integers: " );

scanf("%d % d", & num 1 ,&num 2);

intresult= gcd(num1 , num 2);

printf("GCD o f % d and%d is %d
\
n", num1 , num 2 , result) ;

ret urn0 ;}

Output
:

1 9.

Wr i te a program to fi nd t he val ue of xy usi ng rec urs ion.

#include <stdio .h>

/ / Recursive functio n to calculate x^y

lo ng lo ng po wer(int x, inty ) {

if(y == 0 )

return 1;
else

return x * po wer(x ,y
-

1 );

/ / M ain functio n

int m ain() {

int base,expo nent;

printf("Enter base (x) : ");

scanf("%d",&base);

printf("Enterexpo nent(y): " );

scanf("%d",&expo nent);

if (expo nent < 0 ) {

printf("This pro gram handles o nly no n

-
negativeexpo nents.
\
n");

} e lse {
lo ng lo ngresult= po wer(base,expo nent);

printf("%d^%d = %lld
\
n", base,expo nent, result);

ret urn 0;

Page |
68

Output
:

2 0.

Wr i te a program toi mpl ement the probl em ofTower of Hanoi .

#include <stdio .h>

/ / Recursive functio n to so lveTo wer o f Hano i

vo id towerOfHano i(int n,char so urce,char auxiliary, char destinatio n) {

if(n == 1 ) {

printf("Move disk 1 from %c to %c

\
n", so urce, destinatio n);

return;

towerOfHano i(n
-

1 , so urce, destinatio n, auxiliary );

printf("Move disk % d from %c to %c

\
n", n, so urce, destinatio n);

towerOfHano i(n
-

1 , auxiliary, so urce, destinatio n);

/ / M ain functio n

int m ain() {

int n;

printf(" Enter num bero f disks: ");

scanf("%d",&n);

printf(" Steps to so lve Towero f Hano i w ith%d disks:

\
n", n);

towerOfHano i(n, 'A', 'B', 'C'); / / A = so urce,B = auxiliary, C = destinatio n

return 0;

Output
:

2 1.

Wr i te a program tos or tN numbers by usi ng the foll ow i ng tec hni ques

a)

B ubbl e S ort

b)

S el ecti onS or t

c)

I ns er ti on S ort

#include <stdio .h>

/ / Functio n to display an array

9 4 |Page

vo id display Array(int arr[], int n) {

fo r (int i = 0 ; i < n; i+ +)

Page |
69

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

printf("
\
n");

/ / B ubbl eS or t

vo id bubbleSo rt( int arr[], int n) {

printf("
\
nBubble So rt:
\
n");

fo r (int i = 0 ; i < n
-

1; i+ +) {

fo r (int j =0; j < n

-

i
-

1; j+ +) {
if ( arr[j] > arr[j + 1 ]) {

// Swap

int tem p = arr[j];

arr[j] = arr[j + 1 ];

arr[j + 1 ] = tem p;

display Array(arr, n);

/ / S el ec ti on S ort

vo id selectio nSo rt(int arr[],int n) {

printf("
\
nSelectio n So rt:
\
n");

fo r (int i = 0 ; i < n
-

1; i+ +) {

intm in= i;

fo r (int j = i + 1 ; j < n; j++ ) {

if ( arr[j] < arr[m in])

m in= j;

/ / Swap

inttem p = arr[m in];

arr[m in] = arr[i];

arr[i]= tem p;

display Array(arr, n);

/ / I ns er ti onS or t

vo id insertio nSo rt(int arr[],int n) {

printf("
\
nInsert io n So rt:
\
n");

fo r (int i = 1 ; i < n; i+ +) {

intkey = arr[i];

int j = i
-

1;

while( j >= 0 && arr[j] > key ) {

arr[j + 1 ] = arr[j];

j
--
;

arr[j +1 ] =key;

display Array(arr, n);

}
/ / M ain functio n

int m ain() {

int arr[1 00 ], n, c ho ice;

Page |
70

printf(" Enter num bero felem ents: " );

scanf("%d",&n);

printf(" Enter%d e lem ents:

\
n", n);

into riginal[10 0 ];

fo r (int i = 0 ; i < n; i+ +) {

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

o riginal[i] = arr[i]; // Saveo riginal fo r reuse

bubbleSo rt(arr, n);

fo r (int i = 0 ; i < n; i+ +) arr[i] = o riginal[i]; // Reset

selectio nSort(arr, n);

fo r (int i = 0 ; i < n; i+ +) arr[i] = o riginal[i]; // Reset

insertio nSo rt(arr, n);

return 0;

Output
: