LAB MANUAL

Lab Name : Computer Programming Lab-I

Lab Code : 3EC8A

Branch : Electronics & Communications Engineering

Year : 2nd Year

Jaipur Engineering College and Research Center, Jaipur

Department of Electronics & Communication
(Rajasthan Technical University, KOTA)

1
 INDEX

S.NO CONTENTS CO PAGE

NO.

1 VISION/MISION 4

2. PEO 4

3. POS 5

4. COS 6

5. MAPPING OF CO & PO 6

6. SYLLABUS 7

7. BOOKS 8

8. INSTRUCTIONAL METHODS 8

9. LEARNING MATERIALS 8

10. ASSESSMENT OF OUTCOMES 9

LIST OF EXPERIMENTS (RTU SYLLABUS)

Exp:- 1 Objectives: - Introduction of sorting methods. Implementation of bubble, selection 12

and insertion sort

Exp:- 2 Objectives :- Implementation of binary search 17

Exp:-3 Objectives :- Write a program to search an element using linear search 20

Exp:-4 21
Objectives: - Write a program for addition, multiplication and transpose of
matrices.

Exp:-5 Objectives: - implementation of quick sort 23

2
Exp:-6 Objectives: - Write a program to implement singly linked list 26

Exp:-7 Objectives: - Write a program to implement doubly linked list 31

Exp:-8 Objectives: - write a program to implement queue using array and linked list 38

Exp:-9 Objectives: - Write a program to implement stack using array and linked list 39

Exp:-10 Objectives: - Write a program to merge two sorted array 44

3
 JAIPUR ENGINEERING COLLEGE AND RESEARCH CENTER

Department of Electronics & Communications

Branch: Electronics & Communications Semester: 3rd

Course Name: Computer Programming Lab -I Code: 3EC8A

External Marks: 45 Practical hrs: 2 hr/week

Internal Marks: 30 Total Marks: 75

1. VISION & MISSION

VISION: To provide an excellent platform to students to grow professionally with an
impeccable blend of technology and creativity.

MISSION:

 To inculcate in students the sense of ethics, morality, professionalism, creativity,

leadership, self confidence, good communication skills and prepare them to become
successful engineers.
 To develop professionals that has strong knowledge and clear thinking of the subject.
 To nature engineers with over all development so that they can contribute for
development of society.

2. PEO
i. To enrich students with fundamental knowledge, effective computing, problem solving
and communication skills enable them to have successful career in Information
Technology.
ii. To enable students in acquiring Information Technology's latest tools, technologies and
management principles to give them an ability to solve multidisciplinary engineering
problems.
iii. To impart students with ethical values and commitment towards sustainable
development in collaborative mode.
iv. To imbibe students with research oriented and innovative approaches which help them
to identify, analyze, formulate and solve real life problems and motivates them for
lifelong learning.
v. To empower students with leadership quality and team building skills that prepare them
for employment, entrepreneurship and to become competent professionals to serve
societies and global needs.

3. PROGRAM OUTCOMES
4
1. Engineering Knowledge: Apply the knowledge of mathematics, science, engineering
fundamentals, and an engineering specialization to the solution of complex
engineering problems in IT.
2. Problem analysis: Identify, formulate, research literature, and analyze complex
engineering problems reaching substantiated conclusions using first principles of
mathematics, natural sciences, and engineering sciences in IT.
3. Design/development of solutions: Design solutions for complex engineering
problems and design system components or processes that meet the specified needs
with appropriate consideration for the public health and safety, and the cultural,
societal, and environmental considerations using IT.
4. Conduct investigations of complex problems: Use research-based knowledge and
research methods including design of experiments, analysis and interpretation of data,
and synthesis of the information to provide valid conclusions using IT.
5. Modern tool usage: Create, select, and apply appropriate techniques, resources, and
modern engineering and IT tools including prediction and modeling to complex
engineering activities with an understanding of the limitations in IT.
6. The engineer and society: Apply reasoning informed by the contextual knowledge
to assess societal, health, safety, legal and cultural issues and the consequent
responsibilities relevant to the professional engineering practice using IT.
7. Environment and sustainability: Understand the impact of the professional
engineering solutions in societal and environmental contexts, and demonstrate the
knowledge of, and need for sustainable development in IT.
8. Ethics: Apply ethical principles and commit to professional ethics and
responsibilities and norms of the engineering practice using IT.
9. Individual and team work: Function effectively as an individual, and as a member
or leader in diverse teams, and in multidisciplinary settings in IT.
10. Communication: Communicate effectively on complex engineering activities with
the engineering community and with society at large, such as, being able to
comprehend and write effective reports and design documentation, make effective
presentations, and give and receive clear instructions.
11. Project Management and finance: Demonstrate knowledge and understanding of
the engineering and management principles and apply these to one’s own work, as a
member and leader in a team, to manage IT projects and in multidisciplinary
environments.
12. Life –long Learning: Recognize the need for, and have the preparation and ability to
engage in independent and life-long learning in the broadest context of technological
changes needed in IT.

4. MAPPING OF PEOs & POs

5
 PROGRAM PROGRAM OUTCOMES
OBJECTIVE
S 1 2 3 4 5 6 7 8 9 10 11 12

I H L H

II M H M H H L H

III L H M H L M

IV L M H M H M

V M M

5. COURSE OUTCOMES
Graduates would be able:
1. To implement various searching and sorting techniques on linear/non linear data structures to
solve various computing problems.
2. To implement various operations on non linear data structures using linked lists.
3. To implement recursive/non recursive functions to perform various operations on data
structures.
4. To design a suitable data structure and algorithm to solve a real world problem
6. MAPPING OF CO & PO
COURSE PROGRAM OUTCOMES
OUTCOMES
1 2 3 4 5 6 7 8 9 10 11 12
I H H H H H L M L H M H H

II H H H H H L M L H M H H

III H H H H H L M L H M H H

IV H H H H H L M L H M H H

7. SYLLABUS

6
3IT8A Computer Programming Lab-I

7
 Class: III Sem. B.Tech. Branch: Electronics & Communications
Schedule per Week Practical Hrs.: 2 Examination Time = Three (3) Hours
Maximum Marks = 75 [Sessional / Mid-term (45) & End-term (30)]

Outcomes: At the end of the semester, the students should have clearly understood and implemented
the following:
1. Perform the searching algorithms.
2. Perform various sorting algorithms.
3. Implementation of various types of linked list
4. Perform queue using array and linked list
5. Perform stack using array and linked list

8. BOOKS:-

8.1 Text books:-

1. Schaum, Schaum’s Outline Series of theory and problems of Data Structures, Edition2002, Tata
McGraw Hill
8.2 Reference Books:-

1. Aaron M. Tanenbaum, “Data Structures in C/C++”, second edition, Prentice Hall of

India
9. INSTRUCTIONAL METHODS:-
9.1. Direct Instructions:

I. Black board presentation

9.2. Interactive Instruction:

I. Algorithms

9.3 .Indirect Instructions:

I. Problem solving

10. LEARNING MATERIALS:-

9.1. Text/Lab Manual

11. ASSESSMENT OF OUTCOMES:-

8
 1. End term Practical exam (Conducted by RTU, KOTA)
2. Daily Lab interaction.

12. OUTCOMES WILL BE ACHIEVED THROUGH FOLLOWING:-

1. Lab Teaching (through chalk and board).

2. Discussion on Algorithms.

INSTRUCTIONS OF LAB

DO’s
1. Please switch off the Mobile/Cell phone before entering Lab.
2. Enter the Lab with complete source code and data.
3. Check whether all peripheral are available at your desktop before proceeding for
program.
4. Intimate the lab In charge whenever you are incompatible in using the system or
in case software get corrupted/ infected by virus.
5. Arrange all the peripheral and seats before leaving the lab.
6. Properly shutdown the system before leaving the lab.
7. Keep the bag outside in the racks.
8. Enter the lab on time and leave at proper time.
9. Maintain the decorum of the lab.
10. Utilize lab hours in the corresponding experiment.
11. Get your Cd / Pen drive checked by lab In charge before using it in the lab.

DON’TS
1. No one is allowed to bring storage devices like Pan Drive /Floppy etc. in the lab.
2. Don’t mishandle the system.
3. Don’t leave the system on standing for long
4. Don’t bring any external material in the lab.
5. Don’t make noise in the lab.

9
6. Don’t bring the mobile in the lab. If extremely necessary then keep ringers off.
7. Don’t enter in the lab without permission of lab Incharge.
8. Don’t litter in the lab.
9. Don’t delete or make any modification in system files.
10. Don’t carry any lab equipments outside the lab.
We need your full support and cooperation for smooth functioning of the

10
 INSTRUCTIONS FOR STUDENT

BEFORE ENTERING IN THE LAB

 All the students are supposed to prepare the theory regarding the next program.
 Students are supposed to bring the practical file and the lab copy.
 Previous programs should be written in the practical file.
 Any student not following these instructions will be denied entry in the lab.

WHILE WORKING IN THE LAB

 Adhere to experimental schedule as instructed by the lab incharge.
 Get the previously executed program signed by the instructor.
 Get the output of the current program checked by the instructor in the lab copy.
 Each student should work on his/her assigned computer at each turn of the lab.
 Take responsibility of valuable accessories.
 Concentrate on the assigned practical and do not play games.
 If anyone caught red handed carrying any equipment of the lab, then he will have to face
serious consequences.

11
 Experiment No. 1

Aim:

Introduction of sorting methods Implementation of bubble, selection and insertion sort.

Description:

Let A be an array of n elements. Sorting A refers to the operation of rearranging the elements of A so they
are in increasing order. i.e. so that,

A[1] < A[2] < A[3] < A[4] < ……. < A[N]

Example: A[]: 15, 5, 3, 6, 9, 1, 2

After Soritng A[]: 1, 2, 3, 5, 6, 9, 15

Bubble Sort:

Algorithm:

BUBBLESORT (A [MAX], N)
[BUBBLESORT is a procedure to arrange the elements of array A (0: N-1) in sorted order.
Where N is the number of elements insert in the array and MAX is the size of an array. ]

Step 1: Repeat steps 2 to 3 for I: = 0 to N-2 by 1 do:

Step 2: Repeat step 3 for J: = 0 to N-I-2 by 1 do:
Step 3: If A [J] > A [J+1] then:
a. Set TEMP: = A[J]
b. Set A[J]: = A[J+1]
c. Set A[J+1]: = TEMP
[End of If structure]
[End of step 2 for loop]
[End of step 1 for loop]
Step 4: Repeat step 5 for I: = 0 to N-1 by 1 do:
Step 5: Write A [I]
Step 6: Stop

Source Code:

#include<iostream.h>
#include<conio.h>
void main()
{

12
 clrscr();
int x[50],temp,n;
cout<<"Enter the size of array : \n";
cin>>n;
cout<<"Enter the elements of array : \n";
for(int i=0;i<n;i++)
cin>>x[i];
for(i=0;i<n-1;i++)
{
for(int j=0;j<(n-i-1);j++)
{
if(x[j]>x[j+1])
{
temp=x[j];
x[j]=x[j+1];
x[j+1]=temp;
}
}
cout<<"\nArray after "<<i+1<<" phase is : \n";
for(int k=0;k<n;k++)
cout<<x[k]<<" ";

}
cout<<"\nThe sorted array is : \n";
for(i=0;i<n;i++)
cout<<x[i]<<" ";
getch();
}

Selection Sort:

Algorithm:

1. For (i = 0; i <=n-2 ; i++)

min = a[i]

for (j = i+1 ; j <=n-1 ; j++) If (min >a[j])

Swap (min,a[j])

2. Exit

Source Code:

#include<iostream.h>
#include<conio.h>
void main()

13
 {
clrscr();
int x[50],temp,n;
cout<<"Enter the size of array : \n";
cin>>n;
cout<<"Enter the elements of array : \n";
for(int i=0;i<n;i++)
cin>>x[i];
for(i=0;i<n-1;i++)
{
int pos=i,min=x[i];
for(int j=i+1;j<n;j++)
{
if(min>x[j])
{
min=x[j];
pos=j;
}
}
temp=x[pos];
x[pos]=x[i];
x[i]=temp;
cout<<"\nArray after "<<i+1<<" phase is : \n";
for(int k=0;k<n;k++)
cout<<x[k]<<" ";

}
cout<<"\nThe sorted array is : \n";
for(i=0;i<n;i++)
cout<<x[i]<<" ";
getch();
}

Insertion Sort:

Algorithm:

INSERTIONSORT (A [MAX], N)
[The procedure INSERTIONSORT is used to arrange the elements of array A (0: N-1) in sorted
order. Where N is the number of elements insert in the array and MAX is the size of an array.]

Step 1: Repeat steps 2 to 6 for I: = 0 to N-2 by 1 do:

Step 2: set J: = I, Y: = A [I+1]
Step 3: Repeat steps 4 and 5 while J>=0 and Y< A [J]
Step 4: set A [J+1]: = A [J]
Step 5: set J: = J-1
[End of step 3 While loop]
Step 6: set A [J+1]: = Y
[End of step 1 for loop]

14
Step 7: Repeat step 8 for I: = 0 to N-1 by 1 do:
Step 8: Write A [I]
[End of for loop]
Step 9: Stop

Source Code:

#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int x[50],temp,n;
cout<<"Enter the size of array : \n";
cin>>n;
cout<<"Enter the elements of array : \n";
for(int i=0;i<n;i++)
cin>>x[i];
for(i=0;i<n-1;i++)
{
int j=i,y=x[i+1];
while(j>=0&&y<x[j])
{
x[j+1]=x[j];
j=j-1;
}
x[j+1]=y;

cout<<"\nArray after "<<i+1<<" phase is : \n";

for(int k=0;k<n;k++)
cout<<x[k]<<" ";

}
cout<<"\nThe sorted array is : \n";
for(i=0;i<n;i++)
cout<<x[i]<<" ";
getch();
}

Output:
Given array is
12, 11, 13, 5, 6, 7

Sorted array is
5 6 7 11 12 13

15
Viva Questions:

1. what are the needs of bubble, selection and insertion sort

2. complexity of bubble sort, selection and insertion sort
3. In a selection sort of n elements, how many times is the swap function called in the complete
execution of the algorithm?

16
 Experiment No. 2

Aim:

To search an element using Binary Search

Description:

In Binary Search we use Divide & Conquer principle.

General principle of Divide & Conquer: If a problem is given we divide it into no. of sub-problems if we
get solution of each part then we stop at that point. Otherwise we still divide the problem as we solve all
individual sub-problems at last combine all these solution which gives solution of main problem.

Algorithm:

Step 1: if (low > high) then return -1

Step 2: if (low < high) the mid=(low + high)/2

Step 3: X be a key. If a[mid] = X then return mid

Step 4: If a[mid] > X then search for X from a[low] to a[mid-1]

Step 5: If a[mid] < X then search for X from a[mid + 1] to a[high]

Source Code:

#include<stdio.h>

#include<conio.h>

void main()

int a[10],n,i,j,temp;

int beg,end,mid,target;

17
clrscr();

printf("Enter the total numbers:");

scanf("%d",&n);

printf("Enter the array elements:" );

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

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

beg=0;

end=n;

mid=(beg+end)/2;

printf("\nEnter the number to be searched:");

scanf("%d",&target);

while(beg<=end && a[mid]!=target)

if(target<a[mid])

end=mid-1;

else

beg=mid+1;

mid=(beg+end)/2;

if(a[mid]==target)

printf("\nThe number is found at position %2d",mid);

else

18
 printf("\nThe number is not found");

getch();

OutPut:

Enter the total numbers:5

Enter the array elements:1 2 3 4 5

Enter the number to be searched: 5

The number is found at position 4

Result: Hence, BinarySearch is implemented.

Viva Questions:

1. Define array.

2. If there is more than one position of item is exist, then what will be the position of item?

Experiment No. 3

AIM: Write a program to search an element using linear search

1. Set k: = 1 & loc: = 0

2. Repeat step 3 & 4 while loc: = 0 &k < = n
3. If (item = data[k])
loc: = k
Else
K=k+1
4. If loc: = 0, then
Print “no. not found” Else
Print “loc is the location of item”
5.Exit

Source Code:
#include <stdio.h>

19
int main()
{
int array[100], search, c, n;

printf("Enter the number of elements in array\n");

scanf("%d",&n);

printf("Enter %d integer(s)\n", n);

for (c = 0; c < n; c++)

scanf("%d", &array[c]);

printf("Enter the number to search\n");

scanf("%d", &search);

for (c = 0; c < n; c++)

{
if (array[c] == search) /* if required element found */
{
printf("%d is present at location %d.\n", search, c+1);
break;
}
}
if (c == n)
printf("%d is not present in array.\n", search);

return 0;
}

Output:

Enter the no of elements: 6

Enter the array: 10 20 30 40 50 60

Enter the number to search: 30

Position of an element: 3

Viva questions:

1. Define array.
2. If there is more than one position of item is exist, then what will be the position of item?

20
 Experiment No.4

Aim: Write a program for addition, multiplication and transpose of matrices.

Algorithm

Matmul(a,b,m,n,p)
1 for(i=1 to m)
2 for(j = 1 to p)
3 c[i][j] =0;
4 for(k= 1to n)
5 c[i][j] = c[i][j]+a[i][j]*b[i][j]
6 exit

Output:

Enter the first matrix

Enter the element 234

356

111

Enter the second matrix

Enter the element 123

456

789

Matrix after multiplication

42 51 60

64 79 120

11 15 18

Algorithm

Matadd(a,b,m,n)
1 for (i=1 to m
2 for(j= 1 to n)
3c[i][j] = a[i][j]+b[i][j]
4 exit

21
Output:

Enter the first matrix

Enter the element 234

356

111

Enter the second matrix

Enter the element 123

456

789

Matrix after Addition

3 5 7

7 10 12

8 9 10

Algorithm

Transpose(a,m,n)
1 for(i= 1 to m) for(j= 1 to n)
b[i][j]= a[j][i]
2 for (i=1to m) for (j= 1to n)
a[i][j]= b[i][j]
Exit

Output:

Enter the first matrix

Enter the element 234

356

111

Matrix after Transpose

231

351

22
 461

Viva Questions:

1. What is the condition for multiplication of two matrices?

2. Explain the matrix representation in memory?
3. What is the condition for addition of two matrices?

Experiment No. 5

Aim:

To sort an array using quick sort.

Description:

Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions
the given array around the picked pivot. There are many different versions of quickSort that pick pivot in
different ways:

1) Always pick first element as pivot.

2) Always pick last element as pivot (implemented below)
3) Pick a random element as pivot.
4) Pick median as pivot.

The key process in quickSort is partition(). Target of partitions is, given an array and an element x of
array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x)
before x, and put all greater elements (greater than x) after x. All this should be done in linear time.
Partition Algorithm

There can be many ways to do partition, following code adopts the method given in CLRS book. The
logic is simple, we start from the leftmost element and keep track of index of smaller (or equal to)
elements as i. While traversing, if we find a smaller element, we swap current element with arr[i].
Otherwise we ignore current element.

Algorithm:

1. low =l, high = h, key a[(l+h)/2]

2. Repeat through step 7 while (low <= high)

3. Repeat step 4 while (a[low] < key)

4. low = low +1

23
 5. Repeat step 6 while (a[high] > key)

6. high = high – 1

7. If (low <= high)

a) temp = a[low]

b) a[low] = a[high]

c) a[high] = temp d) low =

low + 1

e) high = high + 1

8. If (l < high) quicksort (a,l,high)

9. If (h>low) quicksort (a,low,h)

10. Exit

This algorithm sorts an array a.

1. Top:= NULL
2. If N>1, then Top:= Top+1, Lower[1]:=N
3. Repeat steps 4 to 7 while Top!=NULL
4. [pop sublist from stacks]
Set low= Lower[Top], high:= Upper[Top], Top:= Top-1
5. return

Source Code:

#include<stdio.h>

void quicksort(int [10],int,int);

int main(){
int x[20],size,i;

printf("Enter size of the array: ");

scanf("%d",&size);

printf("Enter %d elements: ",size);

for(i=0;i<size;i++)
scanf("%d",&x[i]);

quicksort(x,0,size-1);

24
 printf("Sorted elements: ");
for(i=0;i<size;i++)
printf(" %d",x[i]);

return 0;
}

void quicksort(int x[10],int first,int last){

int pivot,j,temp,i;

if(first<last){
pivot=first;
i=first;
j=last;

while(i<j){
while(x[i]<=x[pivot]&&i<last)
i++;
while(x[j]>x[pivot])
j--;
if(i<j){
temp=x[i];
x[i]=x[j];
x[j]=temp;
}
}

temp=x[pivot];
x[pivot]=x[j];
x[j]=temp;
quicksort(x,first,j-1);
quicksort(x,j+1,last);

}
}

Output:

Enter the no of elements 5

Enter the array 15 5 3 7 12

Sorted array 3 5 7 12 15

Viva Questions:

25
i. What is the average case, best case and worst case complexity for quick sort
algorithm complexity of quick sort?
ii. Difference between merge sort and quick sort.

Experiment No. 6

Aim: Write a program to implement singly linked list

1. t = newmode( )
2. Enter info to be inserted
3. Read n
4. t Æ info = n
5. t Æ next = start
6. Start = t

INSERTION
BEGIN

1. t Æ next = start
2. start = t
Return

MIDDLE

1. Enter info of the node after which new node to be inserted

2. Read x
3. p = start
4. Repeat step 5 until p Æ info < > x
5. p = p Æ next
6. t Æ next = p Æ next
7. p Æ next = t
8. Return

LAST

1. p = start
2. Repeat step 3 until p Æ next NULL
3. p = p Æ next
4. t Æ next = NULL
5. p Æ next = t
6. Return

DELETION
BEGIN
1. x = start
2. start = start Æ next
3. delnode(x)

MIDDLE

26
 1. Enter the info of node to be deleted
2. Read n
3. p = start
4. c = start
5. while (c Æ info < > NULL)
p=c
c = c Æ next
6. p Æ next = c Æ next
7. delnode ( c )
8. Return

LAST
1. p = start
c = start
2. while (cÆnext < > NULL)
p=c
c = cÆnext
3. p Æ next = c Æ next
4. delnode ( c)
5. Return

TRAVERSAL
1. p = start
2. while (p < > NULL)
Print p Æ info
P = p Æ next
4. Return

Source code:
#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
int data;
struct Node *next;
}node;
void insert(node *pointer, int data)
{
/* Iterate through the list till we encounter the last node.*/
while(pointer->next!=NULL)
{
pointer = pointer -> next;
}
27
 /* 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 = NULL;
}
int find(node *pointer, int key)
{
pointer = pointer -> next; //First node is dummy node.
/* Iterate through the entire linked list and search for the key. */
while(pointer!=NULL)
{
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)
{
/* Go to the node for which the node next to it has to be deleted */
while(pointer->next!=NULL && (pointer->next)->data != data)
{
pointer = pointer -> next;
}
if(pointer->next==NULL)
{
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;
28
 /*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 *pointer)
{
if(pointer==NULL)
{
return;
}
printf("%d ",pointer->data);
print(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 = NULL;
/* 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)
{
29
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->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");

}
}

30
 }
}
Output:
Enter the list: 12->100 13->101 14->104 15->NULL
Insert item at first position: 11
New list: 11->1000 12->100 13->101 14->104 15->NULL
Delete an item from last position:
Delete item: 15
New list: 11->1000 12->100 13->101 14->NULL

Viva Questions:

1. What is singly linked list?

2. What are the differences between array and linked list?

Experiment No. 7

Aim:
Write a program to implement double linked list

1. t = new node
2. Enter “the info to be inserted”
3. Read n
4. t Æ info = n
5. t Æ next = NULL
6. t Æ prev NULL

INSERTION
BEGIN
1. If start = NULL
start = t
2. else
t Æ next = NULL
t Æ next Æ prev = t
start = t
Return

MIDDLE
1. Print “ enter info of the node after which you want to insert”
2. Read x
3. p = start
4. Repeat while p< > NULL If
(pÆ info = n)
tÆnext = pÆ next

31
 pÆnext = t
t Æ prev = p
p Æ nextÆ prev = t
Return
Else
P = pÆ next
5. Print x not found

tÆnext = NULL
pÆnext = t

DELETION
BEGIN
1. p = start
2. pÆnextÆprev = NULL
3. start = pÆnext
4. start = pÆnext
5. delnode(p)
6. Return

MIDDLE
1. Enter “info of the node to be deleted”
2. Read x
3. p = start
4. Repeat until p< > NULL
If(pÆinfo = x) pÆprevÆnext =
pÆnext pÆ next Æ prev = pÆprev
delnode(p)
Return
Else
P = pÆ next
5. Print “x not found”

LAST
1. P = start
2. Repeat while p< > NULL
If(pÆnext = NULL)
Delnode(p)
3. Return

DISPLAY
1. p = start
2. Repeat while p < > NULL
Print pÆinfo
P = p Æ next

Source code:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {

32
 int data;
int key;

struct node *next;

struct node *prev;
};
//this link always point to first Link
struct node *head = NULL;
//this link always point to last Link
struct node *last = NULL;
struct node *current = NULL;
//is list empty
bool isEmpty(){
return head == NULL;
}
int length(){
int length = 0;
struct node *current;

for(current = head; current != NULL; current = current->next){

length++;
}

return length;
}
//display the list in from first to last
void displayForward(){
//start from the beginning
struct node *ptr = head;

//navigate till the end of the list

printf("\n[ ");

while(ptr != NULL){
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}

printf(" ]");
}
//display the list from last to first
void displayBackward(){
//start from the last
struct node *ptr = last;

//navigate till the start of the list

printf("\n[ ");

while(ptr != NULL){

//print data
printf("(%d,%d) ",ptr->key,ptr->data);

33
 //move to next item
ptr = ptr ->prev;
printf(" ");
}

printf(" ]");
}

//insert link at the first location

void insertFirst(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;

if(isEmpty()){
//make it the last link
last = link;
}else {
//update first prev link
head->prev = link;
}
//point it to old first link
link->next = head;

//point first to new first link

head = link;
}
//insert link at the last location
void insertLast(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;

if(isEmpty()){
//make it the last link
last = link;
}else {
//make link a new last link
last->next = link;
//mark old last node as prev of new link
link->prev = last;
}
//point last to new last node
last = link;
}
//delete first item
struct node* deleteFirst(){
//save reference to first link
struct node *tempLink = head;

//if only one link

34
 if(head->next == NULL){
last = NULL;
}else {
head->next->prev = NULL;
}

head = head->next;
//return the deleted link
return tempLink;
}
//delete link at the last location
struct node* deleteLast(){
//save reference to last link
struct node *tempLink = last;

//if only one link

if(head->next == NULL){
head = NULL;
}else {
last->prev->next = NULL;
}

last = last->prev;

//return the deleted link

return tempLink;
}
//delete a link with given key
struct node* delete(int key){
//start from the first link
struct node* current = head;
struct node* previous = NULL;

//if list is empty

if(head == NULL){
return NULL;
}
//navigate through list
while(current->key != key){
//if it is last node

if(current->next == NULL){
return NULL;
}else {
//store reference to current link
previous = current;

//move to next link

current = current->next;
}
}
//found a match, update the link
if(current == head) {
//change first to point to next link
head = head->next;

35
 }else {
//bypass the current link
current->prev->next = current->next;
}
if(current == last){
//change last to point to prev link
last = current->prev;
}else {
current->next->prev = current->prev;
}

return current;
}
bool insertAfter(int key, int newKey, int data){
//start from the first link
struct node *current = head;

//if list is empty

if(head == NULL){
return false;
}
//navigate through list
while(current->key != key){

//if it is last node

if(current->next == NULL){
return false;
}else {
//move to next link
current = current->next;
}
}

//create a link
struct node *newLink = (struct node*) malloc(sizeof(struct node));
newLink->key = key;
newLink->data = data;
if(current == last) {
newLink->next = NULL;
last = newLink;
}else {
newLink->next = current->next;
current->next->prev = newLink;
}

newLink->prev = current;
current->next = newLink;
return true;
}
main() {
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);

36
 printf("\nList (First to Last): ");
displayForward();

printf("\n");
printf("\nList (Last to first): ");
displayBackward();
printf("\nList , after deleting first record: ");
deleteFirst();
displayForward();
printf("\nList , after deleting last record: ");
deleteLast();
displayForward();
printf("\nList , insert after key(4) : ");
insertAfter(4,7, 13);
displayForward();

printf("\nList , after delete key(4) : ");

delete(4);
displayForward();
}
Output:
Enter the list: 107<-12->100 1000<-13->101 100<-14->104 101<-15->NULL
Insert item at first position: 11
New list: 108<-11->1000 107<-12->100 1000<-13->101 100<-14->104
101<-15->NULL
Delete an item from last position:
Delete item: 15
New list: 108<-11->1000 107<-12->100 1000<-13->101 100<-14-> NULL

Viva Questions:

1. What is doubly linked list?

2. What the differences are between singly doubly linked list?

37
 Experiment No.8

Aim:
write a program to implement queue using array and linked list

CREATE
1. t = new node
2. Enter info to be inserted
3. Read n
4. t Æ info = n
5. t Æ next = front
6. front = t

INSERTION
1. r Æ next = t
2. t Æ next = NULL
3. Return

DELETION
1. x = front
2. front = front Æ next
3. delnode(x)
4. Return

DISPLAY
1. If (front = NULL)
Print “ empty queue”
Return
Else
P = start
Repeat until (p< > NULL)
Print p Æ info
P = pÆ next
Return
Output:
Enter the list: 107<-12->100 1000<-13->101 100<-14->104 101<-15->NULL
Insert item at first position: 11
New list: 108<-11->1000 107<-12->100 1000<-13->101 100<-14->104
101<-15->NULL
Delete an item from last position:
Delete item: 15
New list: 108<-11->1000 107<-12->100 1000<-13->101 100<-14-> NULL

38
Viva Questions:

1. What is queue?

Experiment No. 9

Aim:
Write a program to implement stack using array and linked list
Using array:
INSERTION
PUSH(item)
1. If (item = max of stack)
Print “overflow”
Return
2. top = top + 1
3. stack[top] = item
4. Return

DELETION
POP(item)
1. If (top = - 1)
Print “underflow”
Return
2. Item = stack[top]
3. top = top – 1
4. Return

DISPLAY
1. If top = - 1
Print “underflow”
2. repeat step 3 for i = top to i >= 0
3. Print stack[i]
4. Return
Using Linked List

PUSH( )
1. t = newnode( )
2. Enter info to be inserted
3. Read n
4. tÆinfo = n
5. tÆnext = top
6. top = t
7. Return

POP( )
1. If (top = NULL) Print
“ underflow” Return
2. x = top
3. top = top Æ next

39
 4. delnode(x)
5. Return

Output:
Enter the no of elements: 5
Enter the elements in stack: 5 10 15 16 17
New element: 9
New stack: 5 10 15 16 17
#include <stdio.h>
#include <stdlib.h>
struct node
{
int info;
struct node *ptr;
}*top,*top1,*temp;
int topelement();
void push(int data);
void pop();
void empty();
void display();
void destroy();
void stack_count();
void create();
int count = 0;
void main()
{
int no, ch, e;
printf("\n 1 - Push");
printf("\n 2 - Pop");
printf("\n 3 - Top");
printf("\n 4 - Empty");
printf("\n 5 - Exit");
printf("\n 6 - Dipslay");
printf("\n 7 - Stack Count");
printf("\n 8 - Destroy stack");
create();
while (1)
{
printf("\n Enter choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("Enter data : ");
scanf("%d", &no);
push(no);
break;
case 2:
pop();

40
 break;
case 3:
if (top == NULL)
printf("No elements in stack");
else
{
e = topelement();
printf("\n Top element : %d", e);
}
break;
case 4:
empty();
break;
case 5:
exit(0);
case 6:
display();
break;
case 7:
stack_count();
break;
case 8:
destroy();
break;
default :
printf(" Wrong choice, Please enter correct choice ");
break;
}
}
}
/* Create empty stack */
void create()
{
top = NULL;
}
/* Count stack elements */
void stack_count()
{
printf("\n No. of elements in stack : %d", count);
}
/* Push data into stack */
void push(int data)
{
if (top == NULL)
{
top =(struct node *)malloc(1*sizeof(struct node));
top->ptr = NULL;
top->info = data;
}
else
{
temp =(struct node *)malloc(1*sizeof(struct node));
temp->ptr = top;
temp->info = data;
top = temp;
}
count++;
}
/* Display stack elements */
void display()

41
{
top1 = top;
if (top1 == NULL)
{
printf("Stack is empty");
return;
}
while (top1 != NULL)
{
printf("%d ", top1->info);
top1 = top1->ptr;
}
}
/* Pop Operation on stack */
void pop()
{
top1 = top;
if (top1 == NULL)
{
printf("\n Error : Trying to pop from empty stack");
return;
}
else
top1 = top1->ptr;
printf("\n Popped value : %d", top->info);
free(top);
top = top1;
count--;
}
/* Return top element */
int topelement()
{
return(top->info);
}
/* Check if stack is empty or not */
void empty()
{
if (top == NULL)
printf("\n Stack is empty");
else
printf("\n Stack is not empty with %d elements", count);
}
/* Destroy entire stack */
void destroy()
{
top1 = top;
while (top1 != NULL)
{
top1 = top->ptr;
free(top);
top = top1;
top1 = top1->ptr;
}
free(top1);
top = NULL;

42
 printf("\n All stack elements destroyed");
count = 0;
}
Output
1 - Push
2 - Pop
3 - Top
4 - Empty
5 - Exit
6 - Dipslay
7 - Stack Count
8 - Destroy stack
Enter choice : 1
Enter data : 56
Enter choice : 1
Enter data : 80
Enter choice : 2
Popped value : 80
Enter choice : 3
Top element : 56
Enter choice : 1
Enter data : 78
Enter choice : 1
Enter data : 90
Enter choice : 6
90 78 56
Enter choice : 7
No. of elements in stack : 3
Enter choice : 8
All stack elements destroyed
Enter choice : 4
Stack is empty
Enter choice : 5

Viva Questions:
1. What is stack?
2. What are the difference between stack and queue?

43
 Experiment No. 10

Aim: Write a program to merge two sorted array

ENTER (a[10],n)
1. Repeat step 2 for i = 0 to (n-1)
2. Input a[i]
3. Return

DISPLAY(c[20],p)
1. Repeat step 2 for k = 0 to p-1
2. Print c[k]
3. Return

MAIN( )
1. Start
st nd
2. Input no. of elements in 1 & 2 array as ‘n’ & ‘m’
3. Enter (a.n)
4. Enter (b,m)
5. i = j = k = 0
6. Repeat step 7 to 12 while ((i < n)&&(j < m))
7. If (a[i] >= b[j]),goto step 9
8. c[k+1] = a[i+1]
9. If a[i] = b[j] ,goto step 11
10. c[k++] = b[j++]
goto step 7
11. c[k++] = a[i++]
12. j++
13. Repeat step 14 while (i<n)
14. c[k++] = a[i++]
15. Repeat step 16 while m > j
16. c[k++] = b[j++]
17. Display merged arrays as display(c;k)
18. Exit

#include <stdio.h>

void merge(int [], int, int [], int, int []);

44
int main() {
int a[100], b[100], m, n, c, sorted[200];

printf("Input number of elements in first array\n");

scanf("%d", &m);

printf("Input %d integers\n", m);

for (c = 0; c < m; c++) {
scanf("%d", &a[c]);
}

printf("Input number of elements in second array\n");

scanf("%d", &n);

printf("Input %d integers\n", n);

for (c = 0; c < n; c++) {
scanf("%d", &b[c]);
}

merge(a, m, b, n, sorted);

printf("Sorted array:\n");

for (c = 0; c < m + n; c++) {

printf("%d\n", sorted[c]);
}

return 0;
}

void merge(int a[], int m, int b[], int n, int sorted[]) {

int i, j, k;

j = k = 0;

for (i = 0; i < m + n;) {

if (j < m && k < n) {
if (a[j] < b[k]) {
sorted[i] = a[j];
j++;
}
else {
sorted[i] = b[k];
k++;
}
i++;
}
else if (j == m) {
for (; i < m + n;) {
sorted[i] = b[k];
k++;
i++;
}
}
else {
for (; i < m + n;) {

45
 sorted[i] = a[j];
j++;
i++;
}
}
}
}

Output:
Enter first array: 5 15 20 25
Enter first array: 3 10 11 45
After merging:
3 5 10 11 15 20 25 45

Viva Question:
1. What is an array?

46