KLE Society’s

B. V. Bhoomaraddi.
College of Engineering
and Technology

Course Title: C Programming for

Problem Solving
Code: 18ECSP101
Pointers
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

Overview
• Introduction
• Declaring pointers
• Pointer variables
• Pointer expression and arithmetic
• Passing arguments to functions using pointers
• Pointers and arrays
• Passing an array to a function

17/04/2023 2
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

INTRODUCTION

17/04/2023 3
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

Introduction
• Each variable in a program occupies a part of
the computer’s memory:-
– An integer variable occupies 2 bytes of memory
– A character variable occupies 1 byte
– A float occupies 4 bytes
– An array[4][2] of integers occupies 8 * 2 = 16 bytes
• Since data (int/char/float/double) is stored in
memory, it has an address of storage
associated with it
17/04/2023 4
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

Address of a variable
• The location or the chunk of memory used to
store a variable is called the address of that
variable.
• An address is some kind of number similar to
house numbers in a street that is used to
locate the information stored in that particular
variable
• Where do we refer to the address of a
variable?
17/04/2023 K. L. E. Technological University, Hubli-31.
5
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

The scanf Statement

• scanf(”%d”, &num);
• scanf(”%c”, &grade);
• scanf(”%f”, &temp);
• for(i=0;i<n;i++)
{
scanf(”%f”, &marks[i]);
}
• & says: Store the value at the address of the variable

04/17/2023 6
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

Memory representation
int i=150; address of i 0x1056
0x1057 150

char c = ’A’; address of c 0x1058 65

1. How many bytes are occupied by int?

2. What does 0x imply?
3. What is the address range for variable i?
4. What is the starting address of i?
5. What is stored in i?
6.If I need to store the address of a
variable what do I need?
17/04/2023 K. L. E. Technological University, Hubli-31.
7
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

WHAT ARE POINTERS?

17/04/2023 8
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

What is a pointer variable?

• A pointer variable is a variable that holds
address values.
• Each data type has its own pointer variable,
pointer to int, pointer to double, pointer to
char...
data_type *pointer_variable name;
Ex1: int *pt_int;
char *pt_char;
float *pt_flt;
17/04/2023 9
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

Accessing the address of a variable

Let marks be any variable.
int marks = 36; ü
int ptr = &marks; û
int *ptr = &marks; ü

• The asterix (*) tells the address_marks is a pointer variable

• int states that address_marks will store the address of an
integer variable
17/04/2023 10
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

Operators used for Pointer handling

• C uses the indirection operator * to access the
value of the variable pointed by.
• C uses the address-of operator & to get the
address of an variable.

int i =17; //Regular Variable

*
int ptr; /* defines a pointer to an integer variable*/
ptr= &i; /* assign the address of i to pointer */
printf(”%d”, *ptr); /* prints contents of variable i */
17/04/2023 K. L. E. Technological University, Hubli-
31.
11
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering

Regular variable vs. pointer variables

and Technology

1 int num =17; A normal integer variable

2 int *ptr; /* defines a pointer to an integer

variable */
ptr= &num; /*assign the address of num to
pointer */

4 printf(”%d”, *ptr); /* prints contents of variable num

using a pointer*/
printf(”%d”, num); /* prints contents of variable num*/

5 printf(”%p”, ptr); /* prints address of num */

printf(”%p”, &num);
12
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

Pictorial representation 1 4 bytes

float value=17.25; 0x1054 17.25

float *ptr;
value
ptr=&value;
printf(”%d”, *ptr); 2 bytes
0x2034 1054
ptr
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

Activity 1: Identify the intention of each of the Time: 10 minutes

statements Type: Individual
1 int v; /*declares variable v of
type int */
2 int w;
3 int *p; /* declares a integer
pointer */
4 p=&v;
5 v=3;
6 *p=7;
7 p=&w;
8 *p=12;

17/04/2023 K. L. E. Technological University, Hubli-

31.
14
1 int v; /*defines variable v of type int */
KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

2 int w; /* defines variable w of type int */

3 int *p; /*defines variable p of type pointer to int

*/
4 p=&v; /* assigns address of v to pointer p */

5 v=3; /* assigns value 3 to v */

6 *p=7; /* assigns value 7 to v */
7 p=&w; /* assigns address of w to pointer p */

8 p=12 /* assigns value 12 to w */

17/04/2023 K. L. E. Technological University, Hubli-
31.
15
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

Activity 2: Correct the statements, if Time: 5 minutes

necessary. Give justification Type: Individual
1 float a, b; float a, b;
int x, *p1, *p2;
p1 = &a; int x, *p2, *p1;
p2= &x; p1 = &x;
p2= &x;
2 int *p = &x, x;
3 int *p; int x, *p = &x;
4 float *p1;
5 char *p3 = ‘ch’;
char *p3 = &ch;

16
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

Remember...
• Assign the address of a variable to a pointer
using the & (address of operator)
• The type of variable and pointer must be same
• Declare target variable before declaring the
pointer to it
• When *(indirection operator) is placed before
the pointer, the pointer returns the value of
the variable it points to.

17/04/2023 K. L. E. Technological University, Hubli-

31.
17
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

Activity 3: State intention of each statement & Time: 5 minutes

write printf stmts Type: Individual

Consider the following code segment:

int quantity, *p, n;
quantity = 179;
p = &quantity;
n = *p;

17/04/2023 K. L. E. Technological University, Hubli-

31.
18
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

Time: 10 minutes
Activity 3: Write printf stmts Type: Individual
1. Print the address of quantity in two ways
a) Using Pointer to quantity
b) Using the address of operator for quantity
2. Print the value of quantity in three ways
a) Using Pointer to quantity
b) Using the variable quantity int quantity, *p, n;
c) Use the regular variable quantity = 179;
3. What is printed for:- p = &quantity;
a) printf(“%p\n”, *&p);
n = *p;
b) printf(“%p\n”, &*p);
19
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering

int quantity, *p, n;

and Technology

quantity = 179;
p = &quantity;
n = *p;
• Address of quantity
– printf(“address of quantity = %p\n”, &quantity);
– printf(“address of quantity = %p\n”, p);
• Value of quantity
– printf(“Value of quantity = %d\n”, quantity);
– printf(“address of quantity = %d\n”, *p);
– printf(“address of quantity = %d\n”, n);
17/04/2023 20
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

Time: 15 minutes
Activity 4 Type: Individual

float a = 0.001, b=0.003, c, *pa,*pb;

pa=&a;
*pa= 2 * a;
pb=&b;
c=3 * (*pb - *pa);
Assume that the address of a is(hexadecimal)
1130, the address assigned to b begins at 1134,
and c begins at 1138;

21
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

Activity 4
a) What value is assigned to &a?
b) What value is assigned to &b?
c) What value is assigned to &c;
d) What is the value assigned to pa?
e) What is the value assigned to *pa?
f) What value is represented by & (*pa)?
g) What value is assigned to pb?
h) What value is represented by *pb?
i) What value is assigned to c?
22
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

POINTER EXPRESSIONS AND

ARITHMETIC
17/04/2023 23
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

Pointer expressions
• It is possible to add integers to pointers or
subtract integers from pointers as well as to
subtract one pointer from the other pointer.
• We can compare pointers by using relational
operators in the expressions. For example
p1 > p2 , p1==p2 and p1!=p2 are all valid in C.

17/04/2023 24
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

Example for Pointer arithmetic

int num1=2, num2= 3, sum=0, mul=0, div=1;
int *ptr1, *ptr2;
ptr1 = &num1;
ptr2 = &num2;
sum = *ptr1 + *ptr2;
mul = sum * *ptr1;
*ptr2 +=1;
div = 9 + *ptr1/ *ptr2 - 30;
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

PASSING ARGUMENTS TO
FUNCTIONS USING POINTERS
17/04/2023 K. L. E. Technological University, Hubli-
31.
26
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

Two ways of passing arguments to functions

1. By value So far you have been passing
• Sum= getSum(num1,num2); Variable by value
• printStatus(status);
Pointer variables are passed
2. By reference
by reference
• getSum(&num1,&num2);
As we know in passing by value the function
obtains only a local copy of the variable, so
that changes to the local variable have no
impact on the argument with which the
function was invoked
In passing by reference the function manipulates
the original variable rather than only a copy of
it.
17/04/2023 27
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

Rules for Passing pointer arguments

Rule1:
In prototype the parameters are declared as
pointers
Rule2:
When calling the functions, address are passed
as actual arguments
Rule3:
In the functions body, the dereferenced (with *)
pointers are used
17/04/2023 K. L. E. Technological University, Hubli-
31.
28
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

Example 1
Rule1: void subtract(int *n1, int *n2, int *r);
Rule2: subtract(&n1, &n2, &r);
Rule3:
void subtract(int *a1, int *a2, int *a3)
{
*a3 = *a1 - *a2;
}

17/04/2023 K. L. E. Technological University, Hubli-

31.
29
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

Activity:What is output of following C Program

main() void swap (int pa, int pb)
{ {
int a; int b; int temp;
printf("Enter the values of a temp =pa;
and b\n"); scanf("%d pa=pb;
%d",&a,&b); pb=temp;
printf(“Value of A and B before }
calling function is %d and
%d",a,b);
swap(a,b); Let the values of a and b be
printf(“Value of A and B after 10 and 5 respectively.
calling function is %d and %d",
a, b);
}
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

Activity: Write appropriate main function to call the

User defined function

void area_circum(float radius, float *area, float *circumference)

{
*area = 3.142
*radius * radius;
*circumference = 2 * 3.142 * radius;
}

31
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

Practise Programs
1. Program to calculate area of circle using
pointers
2. Program to add, subtract, multiply and divide
numbers using pointers
3. Program to find the biggest of three numbers
using pointers
4. Swap two numbers HOMEWORK
5. Determine GCD and LCM of two numbers.
HOMEWORK
17/04/2023 32
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

POINTERS AND ARRAYS

17/04/2023 33
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

How are Pointers and Arrays related?

• There is a close association between pointers
and arrays
• Arrays can be accessed using pointers
• The name of an array is a constant pointer to
the data type of the elements stored in the
array

17/04/2023 K. L. E. Technological University, Hubli-

31.
34
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

Accessing array elements

int a[5] = { 23, 5, 12, 34, 17 }; /* array of 5 integers*/
for (int i=0; i< 5; i++)
printf(”%d”, a[i]); /* using index to access elements

17/04/2023 K. L. E. Technological University, Hubli-

31.
35
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

Accessing array elements using pointers

for (int i=0; i< 5; i++)
printf(”%d”, *(a+i)); /* using pointer to access
elements*/
/* array is of type pointer to integer*/

17/04/2023 36
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

1 int SUM(void)
2 { int i, n;
3 int arr[10], *parr;
4 parr = arr;
5 printf(“\n Enter the number of elements : “);
6 scanf(“%d”, &n);
7 for(i=0; i < n; i++)
8 scanf(“%d”, (parr+i));
9 for(i=0; i < n; i++)
10 printf(“\n arr[%d] = %d”, i, *(parr+i));
}
17/04/2023 K. L. E. Technological University, Hubli-
31.
37
 KLE Society’s
B. V. Bhoomaraddi.
College of Engineering
and Technology

Practise for Pointers

Write a modular program for the following:-
1. Read and display a list of integers.
2. Implement linear search on a list of integers.
3. To add two array elements and store the
result in the third array
4. To read the 2 lists (2 arrays) of numbers with
same size n and exchange the content of two
lists.

17/04/2023 K. L. E. Technological University, Hubli-

31.
38
KLE Technological University

Structures

II Semester
18ECSP102– Problem Solving with Data Structures

Structures

2021-2022
1
Structures

Content
 Introduction to Structures
 Defining Structures
 Declaring Structure variables
 Accessing members of Structure
 Structures with functions
 Array of Structures
 Pointers to Structures

2
Structures

Class Task- 1

1. Identify the suitable attributes for above image.

2. Group all the attributes.
3. Give a name to the group.
4. Identify the appropriate data types for the above listed attributes.
5. Can we use homogeneous data type?

Grouping of heterogeneous data in C can be accomplished through

Structures.
Structures

Structure
 Structure is a user defined data type in C.
 It is used to group heterogeneous items into a single data type.

Declaring a structure:
struct <tag_name>
{
data_type member1; Each attribute
is a member of
data_type member2; structure.
…
};
Structures

Creating Structure : cricket_player

struct cricket_player
{
char player_name[20];
char team_name[20];
float average;
int highest_score;
int centuries;
int ODI_rank;

};
Structures

Class Task-2
Write a structure for your mobile.
1. Identify the attributes .
2. Group all the attributes.
3. Give a name to the group.
4. Identify the appropriate data types for the above listed attributes.
5. Create a structure for your mobile.
Structures

Declaration of Structure Variables

Ex: cricket_player
struct cricket_player struct cricket_player
{ {
char player_name[20]; char player_name[20];
char team_name[20]; char team_name[20];
float average; float average;
int highest_score; int highest_score;
int centuries; int centuries;
int ODI_rank; int ODI_rank;
}; };
struct cricket_player p1; struct cricket_player p1,p2,p3;
Structures

Task

 Write the structure declaration for cell-phone in both

formats(single and multiple variable declaration/s).
 Structures

Structure Variable(s):
Ex:Mobile
Method 2 : Declare Variables using
Method 1 : Immediately after Structure struct Keyword
Template
struct mobile struct mobile
{ {
char model_name[10]; char model_name[10];
float price; float price;
char os_name[20]; char os_name[20];
float os_version; float os_version;
}samsung; };
struct mobile samsung;
Declaring Multiple Structure Variables
Declaring Multiple Structure Variables struct mobile
struct mobile {
{ char model_name[10];
char model_name[10]; float price;
float price; char os_name[20];
char os_name[20]; float os_version;
float os_version;
}samsung, nokia, htc; };
struct mobile samsung, nokia,
htc;
Structures

Memory Allocation of a structure

Ex: cricket_player
Memory is
allocated to
struct cricket_player the structure
{ when a
char player_name[20]; structure
char team_name[20];
float average; variable is
int highest_score; declared.
int centuries;
int ODI_rank; Total bytes
allocated
}; is 56
sturct cricket_player p1;
Structures

Class task-3

 Draw the memory allocation diagram for cell_phone structure

Structures

Accessing Structure Members

 Structure members are accessed using . (dot) operator.
 . (dot) is called as “Structure member Operator”.
 Dot operator is used between “structure variable” & “member of structure”.

structure_variable.member
Structures

Example of Accessing Structure Members

 structure_variable.member

struct cricket_player To access player_name : p1.player_name

{
char player_name[20]; To access team_name : p1.team_name
char team_name[20]; To access average: p1. average
float average;
int highest_score; To access highest_score:
int centuries; p1.highest_score
int ODI_rank;
}; To access centuries: p1.centuries
struct cricket_player p1; To access ODI_rank: p1.ODI_rank
Structures

Initialization of Structure Members

 Compile Time Initialization
Example: cricket_player
struct cricket_player
{ Order of
char player_name[20]; initialization
char team_name[20]; must map with
float average; order of
int highest_score; member
int centuries; declarations in the
int ODI_rank; structure
};

struct cricket_player p1= {“Virat”, “INDIA”, 59.76,183, 39, 1};

Structures

Initialization of Structure Members

 Compile Time Initialization
Example: cricket_player

struct cricket_player
{ Order of
char player_name[20]; initialization
char team_name[20]; must map with
float average; order of
int highest_score; member
int centuries; declarations in the
int ODI_rank; structure
}p1= {“Virat”, “INDIA”, 59.76,183, 39, 1};
 Structures

Initialization of Structure Members

 Run Time Initialization:
Example: cricket_player
struct cricket_player main()
{ {
char player_name[20]; struct cricket_player p1;
char team_name[20]; scanf(“%s”, p1.player_name);
float average; scanf(“%s”, p1.team_name);
int highest_score; scanf(“%f”, &p1.average);
int centuries; scanf(“%d”, &p1.highest_score);
int ODI_rank; scanf(“%d”, &p1.centuries);
}; scanf(“%d”, &p1.ODI_rank);
}
 Structures

Class Task-4
• Initialize all the members of cell_phone structure.
Structures

Aliasing
 Registered name of Cricket player may have:
firstname, middlename and last name.

 What name can you give to display on screen?

 Suppose: Mahendra Singh Dhoni

Short Name: MSD

 How this can be achieved in structures?

Structures

typedef Structures

• A typedef is a way of renaming a structure type.

• Alias name for structure data type.
typedef struct <tag_name> typedef struct cricket_player

{ {

data_type member1; char player_name[20];

data_type member2; char team_name[20];

… float average;

} TYPEDEF_NAME; int highest_score;

int centuries;
int ODI_rank;
} PLR;

To create a variable(s) for structure:

PLR p1, p2;
Structures

typedef Structures

struct <tag_name> struct cricket_player

{
{
char player_name[20];
data_type member1;
char team_name[20];
data_type member2;
float average;
… int highest_score;
}; int centuries;
typedef struct <tag_name> int ODI_rank;
TYPEDEF_NAME; };
typedef struct cricket_player PLR;
To create a variable(s) for structure:
PLR p1, p2;
Structures

Structures with Functions

1. Pass individual member of a structure
2. Pass entire structure
3. Pass the address of a structure (call-by-reference)
 Structures

Passing Individual Structure Elements

Ex 1: cricket_player
void display ( char [], ,float,int);
struct cricket_player main()
{ {
char player_name[20]; struct cricket_player p1={"Virat", "INDIA", 59.76,183, 39, 1};
display(p1.player_name, p1.average,p1.ODI_rank) ;
char team_name[20]; }
float average;
int highest_score;
int centuries;
int ODI_rank;
void display ( char player_name[20],float average, int
}; ODI_rank)
{
printf("%s,%f,%d",player_name, average, ODI_rank);
}
 Structures

Class Task-5
• Create a structure for cell-phone and pass the individual structure
elements to the function
 Structures

Passing Individual Structure Elements

Ex 2: Browser
struct browser void display ( char bname[25], char copyrt[25],
float n )
{
{
char name[25] ;
printf ("\n%s\n%s\n%f",bname,copyrt,n);
char copyright[25] ; }
float version;
};
void display ( char [] , char [], float);
main()
{
struct browser b1={"Chrome", "Google Inc. ",71.0}
;
display ( b1.name, b1.copyright ,b1.version ) ;
}
 Structures

Passing Entire Structure Variable

void display (struct cricket_player);
Ex 1: Cricket_Player main()
{
struct cricket_player p1={"Virat", "INDIA", 59.76,183, 39,
struct cricket_player 1};
display ( p1) ;
{
}
char player_name[20];
char team_name[20];
float average;
int highest_score; void display (struct cricket_player p1)
int centuries; { printf("%s,%s,%f,%d,%d,
int ODI_rank; %d",p1.player_name,p1.team_name,p1.average,p1.highes
t_score,p1.centuries,p1.ODI_rank);
};
}
 Structures

Passing Entire Structure Variable (Revisit Ex 1: Cricket_Player)

struct cricket_player struct cricket_player read( struct
cricket_player p1)
{ char player_name[20];
{
char team_name[20];
printf ( "\nEnter player name ");
float average;
scanf ("%s", p1. player_name );
int
highest_score,centuries,ODI_rank; …
}; return p1;
struct cricket_player read( struct }
cricket_player);
void display( struct cricket_player p1)
void display( struct cricket_player);
{
main( )
printf ( “ Player Name: %s\
{ n”p1.player_name);
struct cricket_player p1; .
p1=read(p1);
.
display (p1) ;
}
}
Structures

Class Task-6
• Convert the previously discussed Cricket_player structure
into modular C program to read the details, store and display
them on screen.
Structures

Exercises
1)Calculate difference between two time periods.

2) Add two complex numbers.

3) Write a program to add two distances in inch-feet using structure. the values of
the distances is to be taken from the user.

4) Write a program to sort the structure using ODI_rank.

struct player
{
char team_name[15];
char player_name[15];
int ODI_rank;
};
Structures

Create a Profile of Cricket Team

How can you create a Cricket Team for World Cup 2021?
Structures

Array of Structures

struct cricket_player
{
char player_name[20];
char team_name[20];
float average;
int highest_score;
int centuries;
int ODI_rank;
};
struct team player[11];
Structures

Array of Structures Cont..

 An ordinary array: One type of data

0 1 2 … 98 99
 An array of structures: Multiple types of data in each array element.

0 1 2 … 98 99
 Structures

Declaring Array of Structure

struct cricket_player
{
char player_name[20];
char team_name[20];
float average; For each array index
int highest_score; value we will be
int centuries; accessing all the
int ODI_rank; structure members
};
struct cricket_player p1[11];
 Structures

Accessing Array of Structure

struct cricket_player main()

{ {
char player_name[20]; int i;
char team_name[20]; for(i=0;i<11;i++)
float average; {
int highest_score; scanf("%s%s%f%d%d%d",
int centuries;
int ODI_rank; p1[i].player_name, p1[i].team_name,
&p1[i].average, &p1[i].highest_score,
}; &p1[i].centuries, &p1[i].ODI_rank)
struct cricket_player p1[11]; }
}
Structures

Class Task-7

 Write a modular C program to store details of 10 students and list the details of
the student who scored maximum marks.
Structures

Summary

In this session we learned about

 Structures: Declaration, Initialization, Access the members of the
structure
 Structures and functions
 Array of structures
Structures

Take Home Tasks

Write the following programs with and without typedef:
1) Write a program to store the metro token details (ticket) such as from, to and price.
a) display token details using starting point.
b)display token details using ending point.

2) Write a program to store movie details such as name, producer, director , release year and
production house .
a) sort the structure using release year.
b) display structures using director.
c) display structures using production house.
Structures

Nested Structure
 Nested structure in C is nothing but structure within structure.

struct structure1
{
datatype member1;
datatype member2;
…
};

struct structure2
{
datatype member1;
datatype member2;
…
struct structure1 obj;
};
 Structures

Nested Structure Example

Ex: Player main( )
struct achievements
{
{ struct player p1;
int man_of_matches; p1=read (p1);
int man_of_series; display (p1);
}
int no_of_centuries;
struct player read( struct player p1)
};
{
struct player printf ("Enter cricket team name , ODI rank, and achievements – Man of matches,
{ Man of the series and number of centuries \n");
scanf(" %s%d%d%d%d", p1.team_name, &p1.ODI_rank, p1.achieved. man_of_matches,
char team_name[20]; &p1.achieved. man_of_series, &p1.achieved. no_of_centuries);
int ODI_rank; return p1;
// structure within structure }
struct achievements achieved; void display( struct player p1)
{
};
printf(" team name is: %s\n ODI rank is : %d\n man of the Matches: %d\n Man of
struct player read( struct player); the Series: %d\n Number of Centuries: %d\n ", p1.team_name, p1.ODI_rank,
p1.achieved. man_of_matches, p1.achieved. man_of_series, p1.achieved.
void display( struct player); no_of_centuries);
}
 Structures

Nested Structure Example

main()
{
Ex: Mobile
struct mobile mob_data;
struct application mob_data =read(mob_data);
{ display(mob_data);
float app_version; }
struct player read( struct mobile mob_data)
char app_name[20];
{
}
printf ("Enter mobile version , name and app version, name \n");
struct mobile scanf(" %f%s%f%s", &mob_data.mob_version, mob_data.mob_name,
{ &mob_data.app_data.app_version, mob_data.app_data.app_name);
return mob_data;
float mob_version;
}
char mob_name[50];
void display( struct mobile mob_data)
// structure within structure {
struct application app_data; printf(" mobile version is: %f\n mobile name is: %s\n app version is: %f\n app name is:
%s \n ", mob_data.mob_version, mob_data.mob_name, mob_data.app_data.app_version,
}; mob_data.app_data.app_name);
struct player read( struct mobile); }
void display( struct mobile);
Structures

Pointers and Structures

 Pointer which stores address of structure is called as “Pointer to a Structure”.
 Pointer variable holds the address of the structure .
  and (.) both represent the same. These operators are used to access data
member of structure by using structure’s pointer.
 Structures

Pointers and Structures Cont..

struct player void main()

{ {

char team_name[20]; struct player *p, p1;

p=&p1;
char player_name[20]; printf(" Enter Team name ,Captain name and Highest
int highest_score; score\n ");
scanf( "\n%s%s%d", p->team_name, p -> player_name, p-
}; >highest_score);

printf ( "\nTeam name :%s \nPlayer name :%s \n

Highest_score :%d", p->team_name, p-> player_name, p-
> highest_score);
}
 Structures

Passing Structure Using Call By Reference

Ex: Cricket void read(struct player *p)

struct player {

{ printf ("Enter cricket team name, player name and highest

score ");
char team_name[20];
scanf("\n%s%s%d", p->team_ name, p-> player_name,& p->
char player_name[20]; highest_score);
int highest_score; }
};
void read(struct player * ); void display (struct player *p)
void display ( struct player * ); {
main( ) printf ( "\n%s\n%s\n%d", p-> team_name,
{ p->player_name, p-> highest_score);
struct player *p, p1; }
p=&p1;
read(p);
display (p);
}
 Structures

Passing Structure Using Call By Reference

Ex: Browser void read(struct browser *b1)
struct browser {
{ printf ("Enter book name, copyright and version of
char name[25] ; browser");
char copyright[25] ; scanf("\n%s%s%f", b-> name, b->copyright, &b-
float version; >version);

}; }

void read(struct browser *b1 );

void display ( struct browser *b1 ); void display (struct browser *b1)

main() {

{ printf ( "\n%s\n%s\n%f", b-> name, b->copyright, b-

>version);
struct browser *b,b1;
}
b=&b1;
read(b);
display ( b );
 Structures

Nested Structure example using pointers

Ex: Player main( )

struct achievements {
struct player p, *p1;
{
p1=&p;
int man_of_matches; read (p1);
int man_of_series; display (p1);
int no_of_centuries; }
}; void read( struct player *p1)
{
struct player
printf ("Enter cricket team name , ODI rank, and achievements – Man of matches,
{ Man of the series and number of centuries \n");
char team_name[20]; scanf(" %s%d%d%d%d", p1->team_name, &p1->ODI_rank, p1->achieved.
man_of_matches, &p1->achieved. man_of_series, &p1->achieved. no_of_centuries);
int ODI_rank;
}
// structure within structure void display( struct player *p1)
struct achievements achieved; {
}; printf(" team name is: %s\n ODI rank is : %d\n man of the Matches: %d\n Man
of the Series: %d\n Number of Centuries: %d\n ", p1-> team_name, p1-
void read( struct player *); >ODI_rank, p1->achieved. man_of_matches, p1-> achieved. man_of_series, p1-
>achieved. no_of_centuries);
void display( struct player *);
}
 Structures

Ex:Structure
Nested Mobile Example Using Pointers
Ex: Mobile mob_data_ptr = &mob_data;

struct application read(mob_data_ptr);

{ display(mob_data_ptr);

float app_version; }
char app_name[20]; void read( struct mobile *mob_data)
} {
struct mobile printf ("Enter mobile version , name and app version, name \n");
{ scanf(" %f%s%f%s", &mob_data->mob_version, mob_data-
>mob_name, &mob_data->app_data.app_version, mob_data-
float mob_version; >app_data.app_name);
char mob_name[50]; }
// structure within structure
void display( struct mobile *mob_data)
struct application app_data;
{
};
printf(" mobile version is: %d\n mobile name is: %s\n app version
void read( struct mobile*); is: %d\n app name is: %s \n ", mob_data->mob_version, mob_data-
void display( struct mobile *); >mob_name, mob_data->app_data.app_version, mob_data-
>app_data.app_name);
main()
}
{
struct mobile mob_data, *mob_data_ptr;
Structures

Take Home Tasks

1. Create a structure to store the data related to vehicle.
Access the stored data with and without using pointers.

2. Design a modular C program to use typedef structure for mobile strucutre, store data into
members and display them on screen.
KLE Technological University

Dynamic Memory Allocation

II Semester
18ECSP102– Problem Solving with Data Structures

Dynamic Memory Allocation

2021-2022
1
Dynamic Memory Allocation

Static memory

 What is Static memory Allocation?

 List the advantages and disadvantages of Static memory
Allocation.
Dynamic Memory Allocation

Static memory

 Advantages:
 Static allocation is done at compile time when you know the size of
the array.
 The memory size allocated to “data” is static. But it is possible to
change content of a static structure without increasing the memory
space allocated to it.
 Global variables are declared “ahead of time,” such as fixed array.
 Lifetime of Static allocation is the entire runtime of program.
 It has efficient execution time.
Dynamic Memory Allocation

Static memory

 Disadvantages:
 In case more static data space is declared than needed, there is waste of
space.
 In case less static space is declared than needed, then it becomes impossible
to expand this fixed size during run time.
Dynamic Memory Allocation

Dynamic Memory Allocation

 The concept of dynamic memory allocation in C language enables

the C programmer to allocate memory at runtime.
 Dynamic memory allocation in c language is possible by 4 functions of stdlib.h
header file.
 malloc( )
 calloc( )
 realloc( )
 free( )
Dynamic Memory Allocation

malloc()
 “malloc” or “memory allocation” method in C is used to dynamically allocate
a single large block of memory with the specified size.
 Returns a pointer of type void which can be cast into a pointer of any form.
ptr = (cast-type*) malloc(byte-size);
Example:
 ptr = (int*) malloc(100 * sizeof(int));
 Since the size of int is 4 bytes, malloc will allocate 400 bytes of memory.
 However, if the space is insufficient, allocation fails and returns a NULL
pointer.
Dynamic Memory Allocation

malloc()
Dynamic Memory Allocation

calloc()
 “calloc” or “contiguous allocation” method in C is used to dynamically
allocate the specified number of blocks of memory of the specified type. It
initializes each block with a default value ‘0’.
ptr = (cast-type*)calloc(n, element-size);
Example:
 ptr = (float*) calloc(25, sizeof(float));
 This statement allocates contiguous space in memory for 25 elements each
with the size of the float
 If space is insufficient, allocation fails and returns a NULL pointer.
Dynamic Memory Allocation

calloc()
Dynamic Memory Allocation

realloc()

 The function realloc use to change the size of the memory block and it alter the
size of the memory block without loosing the old data, it is called reallocation of
memory.
ptr = realloc(ptr, x);
Dynamic Memory Allocation

free()

 “free” method in C is used to dynamically de-allocate the memory.

 Memory allocated using functions malloc() and calloc() is not de-allocated on
their own.
 free helps to reduce wastage of memory by freeing it , whenever the dynamic
memory allocation takes place.

free(ptr);
Dynamic Memory Allocation

free()
Dynamic Memory Allocation

Dynamic memory
Advantages:
 Data structures can grow Dynamic Allocation is done at run time.
Shrink to fit changing data requirements.
We can allocate (create) additional storage whenever we need them.
 We can de-allocate (free/delete) dynamic space whenever we are done
with them.
We can always have exactly the amount of space required - no more,
no less.
Disadvantages:
As the memory is allocated during runtime, it requires more time.
Memory needs to be freed by the user when done. This is important as
it is more likely to turn into bugs that are difficult to find.
Dynamic Memory Allocation

Thank You
KLE Technological University

Files

II Semester
18ECSP102– Problem Solving with Data Structures

Files

2021-2022
1
Files

Introduction

 Collection of data or information that are stored on a computer known as file.

 File is a collection of bytes stored on a secondary storage device.

 There are four different types of file.

 Data files
 Text files
 Program files

 Directory files
 Different types of file store different types of information.
Files

Types of files

 ASCII text file

 A text file can be a stream of characters that a computer can process

sequentially.

 It is processed only in forward direction.

 Binary file

 A binary file is a file consisting of collection of bytes.

 A binary file is also referred to as a character stream

Files

Steps in processing a file

1. Create the stream via a pointer variable using the FILE structure.
Ex: FILE *p;
2. Open the file, associating the stream name with the file name.
3. Read or write the data.
4. Close the file.
Files

File Functions
Files

Naming a file
 file is identified by its name.
 This name is divided into two parts
 File Name
 It consists of alphabets and digits.
 Special characters are also supported, but it depends on the operating
system we use.
 Extension
 It describes the file type
Files

File Pointer
 The file pointer is a pointer variable which can be store the address of a
special file that means it is based upon the file pointer a file gets opened.
 Declaration of a file pointer:-
FILE* var;
Note:
 The last byte of a file contains the end-of-file character (EOF),
 While reading a text file, the EOF character can be checked to know the
end.
 Files

File Modes
Mode Meaning
r • Open a text file for reading only. If the file doesn’t exist, it returns null.
w • Opens a file for writing only.
• If file exists, than all the contents of that file are destroyed and new fresh blank
file is copied on the disk and memory with same name
• If file dosen’t exists, a new blank file is created and opened for writing.
• Returns NULL if it is unable to open the file

a • Appends to the existing text file

• Adds data at the end of the file.
• If file doesn’t exists then a new file is created.
• Returns NULL if it is unable to open the file.
Files

File Modes
Files

Additional Modes
 r+ :open for reading and writing, start at beginning
 w+ : open for reading and writing (overwrite file)
 a+ :open for reading and writing (append if fileexists)
 Three special file streams are defined in the <stdio.h> header
 – stdin :reads input from the keyboard
 – stdout :send output to the screen
 – stderr :prints errors to an error device (usually also the screen)
 Files

Opening a file

 Before performing any type of operation, a file must be opened and for this
fopen() function is used.

file-pointer=fopen(“FILE NAME ”,”Mode of open”);

Example: FILE *fp=fopen(“ar.c”, ”r”);

If fopen() unable to open a file then it will return NULL to the file pointer.
Files

Closing a file
 To close a file and dis-associate it with a stream (file pointer), use fclose()
function.
 fclose(FILE *fp)
 fclose() returns 0 if the file is closed successfully.

 fcloseall() closes all the files opened previously.

Files

End of file (EOF)

 Generally, a file contains a large amount of data.

 In a large file, it is difficult to detect the end of file while reading.

 In order to mark the end of a text file, a special character EOF is stored at the

end.
Files

Input/Output operations on files

 getc() – read a character

 putc() – write a character
 fprintf() – write set of data values
 fscanf() – read set of data values
 getw() – read integer
 putw() – write integer
Files

getc()

identifier = getc (file pointer);

Example:
FILE *fp;
fp=fopen(“input.txt”,”r”);
char ch;
ch = getc (fp);
Files

putc()
putc (variable,file pointer);
write a single character to the output file, pointed to by fp.
Example:
FILE *fp;
char ch;
putc (ch,fp);
Files

fprintf()

fprintf (fp,"string",variables);
Example:
int i = 12;
float x = 2.356;
char ch = 's';
FILE *fp;
fp=fopen(“out.txt”,”w”);
fprintf (fp, "%d %f %c", i, x, ch);
Files

fscanf()

fscanf (fp,"string",identifiers);
Example:
FILE *fp;
fp=fopen(“input.txt”,”r”);
int i;
fscanf (fp,“%d",i);
Files

Application of files

Mr. Ram works in KLETU as a covid task force manager and wants to know
the student list who have taken the covid vaccination. To find out the student
list, he uses a file to store the students' information and then print the
student list who have taken the covid vaccination. Please help Mr. Ram to
solve the problem.
 Files

Writing student details to the file void write(FILE *fp)

{

#include<stdio.h> char student_name[10];

#include<stdlib.h> int student_id,vaccinated,n,i;
fp=fopen("vaccine.txt","w");
#include<string.h> printf("Enter the number of students\n");
void write(FILE *fp); scanf("%d",&n);
void read(FILE *fp); for(i=1;i<=n;i++)
void Vaccinated_students(FILE *fp); {
printf("Enter the student ID\n");
void main() scanf("%d",&student_id);
{ printf("Enter the student name\n");
FILE *fp; scanf("%s",student_name);
write(fp); printf("is student vaccinated if yes press 1 else 0\n");
scanf("%d",&vaccinated);
read(fp); if(i!=n)
Vaccinated_students(fp); fprintf(fp,"%d\t%s\t%d\
n",student_id,student_name,vaccinated);
else
fprintf(fp,"%d\t%s\t
} %d",student_id,student_name,vaccinated);
}
fclose(fp);
}
 Files

Reading Student details from the file

Reading student details from the file Display vaccinated student details from the
file
void read(FILE *fp) void Vaccinated_students(FILE *fp)
{ {
char student_name[10];
int student_id,vaccinated;// vaccinated=1 int student_id,vaccinated;
else 0 printf("\n\nDisplaying vaccinated students\n");
char student_name[10]; fp=fopen("vaccine.txt","r");
fp=fopen("vaccine.txt","r");
while(!feof(fp))
{
while(!feof(fp)) fscanf(fp,"%d%s
{ %d",&student_id,student_name,&vaccinated);
fscanf(fp,"%d%s if(vaccinated==1)
%d",&student_id,student_name,&vaccinated); {
printf("student ID= %d\n",student_id); printf("student ID= %d\n",student_id);
printf("student name= %s\ printf("student name= %s\
n",student_name); n",student_name);
printf("student vaccinated_status =%d\ printf("student RAM =%d\n",vaccinated);
n",vaccinated); }
} }
fclose(fp); fclose(fp);
} }
Files

Thank You
 Chapter - 1
Introduction to Data Structures
(Sample Programs)

Syllabus
• Pointers

• Structures

• Dynamic Memory Allocation Functions

• Files

• Data Structures: Classifications, Operations

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 1 of 31

 Chapter-1 Sample Programs

1 Pointers
1.1 Pointer: Declaration, Initialization, Accessing
1 # include < stdio .h >
2
3 int main ()
4 {
5 int x1 =2 , x2 =3 , y1 =0 , y2 = -23;
6
7 int * p1 , * p2 ;
8
9 int * q1 , q2 ;
10
11 p1 = & x1 ;
12 p2 = & x2 ;
13
14 q1 = & y1 ;
15 q2 = & y2 ;
16
17 printf ( " \ nx1 =% d " ,* p1 ) ;
18 printf ( " \ nx2 =% d " ,* p2 ) ;
19 printf ( " \ ny1 =% d " ,* q1 ) ;
20 printf ( " \ ny2 =% d " ,* q2 ) ;
21
22 return 0;
23 }

1.2 Largest of 3 Numbers using Pointers

1 # include < stdio .h >
2
3 int main ()
4 {
5 int num1 , num2 , num3 ;
6 int * p1 , * p2 , * p3 ;
7
8 printf ( " Enter First Number : " ) ;
9 scanf ( " % d " ,& num1 ) ;
10 printf ( " Enter Second Number : " ) ;
11 scanf ( " % d " ,& num2 ) ;
12 printf ( " Enter Third Number : " ) ;
13 scanf ( " % d " ,& num3 ) ;
14
15 // assigning the address of input numbers to pointers
16 p1 = & num1 ;
17 p2 = & num2 ;
18 p3 = & num3 ;
19
20 if (* p1 > * p2 )
21 {
22 if (* p1 > * p3 )
23 {
24 printf ( " % d is the largest number " , * p1 ) ;
25 }
26 else
27 {
28 printf ( " % d is the largest number " , * p3 ) ;
29 }
30 }

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 2 of 31

 Chapter-1 Sample Programs

31 else
32 {
33 if (* p2 > * p3 )
34 {
35 printf ( " % d is the largest number " , * p2 ) ;
36 }
37 else
38 {
39 printf ( " % d is the largest number " , * p3 ) ;
40 }
41 }
42
43 return 0;
44 }

1.3 Using Pointers for Variable Value Arithmetic

1 # include < stdio .h >
2

3 int main ()
4 {
5 int num1 =2 , num2 =3 , sum =0 , mul =0 , div =1;
6 int * ptr1 , * ptr2 ;
7
8 ptr1 = & num1 ;
9 ptr2 = & num2 ;
10
11 sum = * ptr1 + * ptr2 ;
12
13 mul = sum * * ptr1 ;
14

15 * ptr2 +=1;
16
17 div = 9 + * ptr1 / * ptr2 - 30;
18
19 printf ( " \ nsum =% d " , sum ) ;
20 printf ( " \ nproduct =% d " , mul ) ;
21 printf ( " \ ndiv =% d " , div ) ;
22
23 return 0;
24 }

1.4 Area of Circle through Pointers

1 # include < stdio .h >
2
3 void area_of_circle ( float *r , float * a )
4 {
5 * a = 3.14 * (* r ) * (* r ) ;
6 }
7

8 int main ()
9 {
10 float radius , area ;
11
12 printf ( " \ nEnter the radius of Circle >\ t " ) ;
13 scanf ( " % f " , & radius ) ;
14
15 // area = 3.14 * radius * radius ;
16 area (& radius , & area ) ;
17 printf ( " \ nArea of Circleis >\ t % f " , area ) ;

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 3 of 31

 Chapter-1 Sample Programs

18
19 return 0;
20 }

1.5 Call–by–Address: Using Pointers

1 # include < stdio .h >
2

3 void swap ( int * , int *) ;

4
5 int main ()
6 {
7 int a ;
8 int b ;
9
10 printf ( " \ nEnter the values of a and b >\ t " ) ;
11 scanf ( " % d % d " , &a , & b ) ;
12
13 printf ( " \ nValue of A and B before calling function is % d and % d " , a , b ) ;
14

15 swap (& a , & b ) ;

16
17 printf ( " \ nValue of A and B after calling function is % d and % d " , a , b ) ;
18
19 return 0;
20 }
21
22 void swap ( int * pa , int * pb )
23 {
24 int temp ;
25
26 temp = * pa ;
27 * pa = * pb ;
28 * pb = temp ;
29 }

1.6 Arrays through Pointers

1 # include < stdio .h >
2
3 int main ()
4 {
5 int a [4]={10 ,20 ,30 ,40};
6 int *p , i ;
7
8 p = a ; // No need for address operator (&) , as array name ( basename ) holds
starting address of the array .
9
10 printf ( " Array elements are :\ n " ) ;
11
12 for ( i =0; i <4; i ++ )
13 {
14 printf ( " % d \ n " ,*( a + i ) ) ;
15 }
16
17 return 0;
18 }

1.7 Addition of 2 Arrays through Pointers

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 4 of 31

 Chapter-1 Sample Programs

1 # include < stdio .h >

2
3 int main ()
4 {
5 int a [8] , b [8] , c [8] , n , i ;
6
7 printf ( " \ nEnter the array size > " ) ;
8 scanf ( " % d " ,& n ) ;
9
10 printf ( " \ nEnter the elements for array -1 > " ) ;
11 for ( i =0; i < n ; i ++ )
12 scanf ( " % d " ,( a + i ) ) ;
13
14 printf ( " \ nEnter the elements for array -2\ n " ) ;
15 for ( i =0; i < n ; i ++ )
16 {
17 scanf ( " % d " ,( b + i ) ) ;
18 *( c + i ) = *( a + i ) + *( b + i ) ;
19 }
20
21 printf ( " \ nResultant array is >\ t " ) ;
22 for ( i =0; i < n ; i ++ )
23 {
24 printf ( " % d " ,*( c + i ) ) ;
25 }
26
27 return 0;
28 }

1.8 Array Swapping through Pointers

1 # include < stdio .h >
2
3 int main ()
4 {
5 int a [8] , b [8] , n , i , temp ;
6
7 printf ( " \ nEnter the array size > " ) ;
8 scanf ( " % d " ,& n ) ;
9
10 printf ( " \ nEnter the elements for array a > " ) ;
11 for ( i =0; i < n ; i ++)
12 scanf ( " % d " ,( a + i ) ) ;
13

14 printf ( " \ nEnter the elements for array b \ n " ) ;

15 for ( i =0; i < n ; i ++)
16 scanf ( " % d " ,( b + i ) ) ;
17
18 // swaping
19 for ( i =0; i < n ; i ++)
20 {
21 temp = *( a + i ) ;
22 *( a + i ) = *( b + i ) ;
23 *( b + i ) = temp ;
24 }
25

26 printf ( " \ nAfter swapping " ) ;

27
28 printf ( " \ nElements for array a >\ t " ) ;
29 for ( i =0; i < n ; i ++)
30 printf ( " % d " , *( a + i ) ) ;

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 5 of 31

 Chapter-1 Sample Programs

31
32 printf ( " \ nElements for array b >\ t " ) ;
33 for ( i =0; i < n ; i ++)
34 printf ( " % d " , *( b + i ) ) ;
35

36 return 0;
37 }

1.9 Linear Search through Pointers

1 # include < stdio .h >
2
3 int main ()
4 {
5 int a [5] = {10 ,20 ,30 ,40 ,50};
6 int *p , key , i ;
7
8 p = a;
9
10 printf ( " \ nEnter the key element to be searched > " ) ;
11 scanf ( " % d " ,& key ) ;
12
13 for ( i =0; i <5; i ++)
14 {
15 if ( key == *( p + i ) )
16 {
17 printf ( " \ n % d is found at position % d " , key , i +1) ;
18 return 0;
19 }
20 }
21
22 printf ( " \ n % d is Not found " , key ) ;
23
24 return 0;
25 }

2 Structures
2.1 Structures: Declaration, Initialization, Accessing
1 # include < stdio .h >
2 # include < string .h >
3
4 // Structure Definition
5 struct stud
6 {
7 char name [20];
8 int roll ;
9 float marks ;
10 };
11

12 int main ()
13 {
14 // Structure Declaration
15 struct stud s ;
16
17 // Accessing and Initializing Members
18 strcpy ( s . name , " I am Don " ) ;
19 s . roll = 420;
20 s . marks = 0;

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 6 of 31

 Chapter-1 Sample Programs

21
22 printf ( " \ nStudent details are > " ) ;
23 printf ( " \ nNAME =% s \ tROLL =% d \ tMARKS =% f " , s . name , s . roll , s . marks ) ;
24
25 return 0;
26 }

2.2 Declaring Multiple Structure Variables

1 # include < stdio .h >
2 # include < string .h >
3
4 struct employee
5 { int id ;
6 char name [50];
7 };
8
9 int main ()
10 {
11 struct employee e1 , e2 ;
12
13 // 1 st variable
14 e1 . id =101;
15 strcpy ( e1 . name , " KLE " ) ;
16

17 // 2 nd variable
18 e2 . id =102;
19 strcpy ( e2 . name , " VTU " ) ;
20
21 printf ( " \ n1st employee id > % d " , e1 . id ) ;
22 printf ( " \ n1st employee name > % s \ n " , e1 . name ) ;
23
24 printf ( " \ n2nd employee id > % d \ n " , e2 . id ) ;
25 printf ( " \ n2nd employee name > % s \ n " , e2 . name ) ;
26
27 return 0;
28 }

2.3 Global Variable and Reading Data of Structure Members

1 # include < stdio .h >
2
3 // Structure Definition and Global Declaration
4 struct stud
5 {
6 char name [10];
7 int roll ;
8 float marks ;
9 }s;
10
11 int main ()
12 {
13
14 printf ( " \ nEnter name , roll and marks of student > " ) ;
15 scanf ( " % s % d % f " , s . name , & s . roll , & s . marks ) ;
16
17 printf ( " \ nStudent Details are " ) ;
18 printf ( " \ nName > % s " , s . name ) ;
19 printf ( " \ nRoll no > % d " , s . roll ) ;
20 printf ( " \ nMarks > % f " , s . marks ) ;
21

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 7 of 31

 Chapter-1 Sample Programs

22 return 0;
23 }

2.4 Renaming through TYPEDEF

1 # include < stdio .h >
2
3 int main ()
4 {
5 typedef int I ;
6
7 I a =10 , b =20 , c = a + b ;
8 printf ( " \ nsum = % d " , c ) ;
9
10 return 0;
11 }

2.5 Structure Renaming through TYPEDEF

1 # include < stdio .h >
2
3 typedef struct complex_number
4 {
5 float real ;
6 float img ;
7 } CMP ;
8
9 int main ()
10 {
11 CMP x , y , res ;
12
13 printf ( " \ nEnter real - part of 1 st complex number > " ) ;
14 scanf ( " % f " , & x . real ) ;
15
16 printf ( " \ nEnter imaginary - part of 1 st complex number > " ) ;
17 scanf ( " % f " , & x . img ) ;
18
19 printf ( " \ nEnter real - part of 2 st complex number > " ) ;
20 scanf ( " % f " , & y . real ) ;
21
22 printf ( " \ nEnter imaginary - part of 2 st complex number > " ) ;
23 scanf ( " % f " , & y . img ) ;
24
25 // addition of x and y
26 res . real = x . real + y . real ;
27 res . img = x . img + y . img ;
28
29 printf ( " \ nResult is > %0.2 f + i (%0.2 f ) " , res . real , res . img ) ;
30
31 return 0;
32 }

2.6 Passing Entire Structure Variable as Argument

1 # include < stdio .h >
2 struct stud
3 {
4 char name [20];
5 int roll ;
6 float marks ;
7 };

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 8 of 31

 Chapter-1 Sample Programs

8
9 // Function Declaration : structure as parameter
10 void display ( struct stud ) ;
11
12 int main ()
13 {
14 struct stud s ;
15
16 printf ( " \ nEnter name , roll , marks > " ) ;
17 scanf ( " % s % d % f " ,s . name , & s . roll , & s . marks ) ;
18

19 display ( s ) ;
20
21 return 0;
22 }
23
24 void display ( struct stud t )
25 {
26 printf ( " \ nStudent details are > " ) ;
27 printf ( " \ nNAME =% s \ tROLL =% d \ tMARKS =% f " , t . name , t . roll , t . marks ) ;
28
29 return ;
30 }

2.7 Passing Structure Members as Arguments

1 # include < stdio .h >
2
3 typedef struct complex_number
4 {
5 float real ;
6 float img ;
7 } CMP ;
8
9 void square ( float , float ) ;
10
11 int main ()
12 {
13 CMP x ;
14
15 printf ( " \ nEnter real - part of complex number > " ) ;
16 scanf ( " % f " , & x . real ) ;
17
18 printf ( " \ nEnter imaginary - part of complex number > " ) ;
19 scanf ( " % f " , & x . img ) ;
20
21 square ( x . real , x . img ) ;
22
23 return 0;
24 }
25
26 void square ( float r , float i )
27 {
28 CMP res ;
29
30 res . real = r * r ;
31 res . img = i * i ;
32
33 printf ( " \ nResult is > %0.2 f + i (%0.2 f ) " , res . real , res . img ) ;
34
35 return ;

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 9 of 31

 Chapter-1 Sample Programs

36 }

2.8 Returning Structure from Function

1 # include < stdio .h >
2
3 struct stud
4 {
5 char name [10];
6 int roll ;
7 float marks ;
8 };
9

10 struct stud read () ;

11
12 int main ()
13 {
14 struct stud x ;
15

16 x = read () ;
17
18 printf ( " \ nName > % s " , x . name ) ;
19 printf ( " \ nRoll no > % d " , x . roll ) ;
20 printf ( " \ nMarks > % f " , x . marks ) ;
21

22 return 0;
23 }
24
25 struct stud read ()
26 {
27 struct stud s ;
28 printf ( " \ nEnter name , roll and marks > " ) ;
29 scanf ( " % s % d % f " , s . name , & s . roll , & s . marks ) ;
30
31 return s ;
32 }

2.9 Returning Structure from Function-2

1 # include < stdio .h >
2
3 struct cricketer
4 {
5 char name [50];
6 int age ;
7 int match ;
8 float avrn ;
9 char temp ;
10 };
11
12 struct cricketer read () ;
13 void display ( struct cricketer ) ;
14
15 int main ()
16 {
17 int n , i ;
18 struct cricketer c1 ;
19
20 printf ( " \ nEnter the number of cricketers > " ) ;
21 scanf ( " % d " , & n ) ;
22

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 10 of 31

 Chapter-1 Sample Programs

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

24 {
25 printf ( " \ nEnter data of cricketer %d > " , i +1) ;
26 c1 = read () ;
27

28 printf ( " \ nDetails of cricketer % d " ,i +1) ;

29 display ( c1 ) ;
30 }
31
32 return 0;
33 }
34
35 struct cricketer read ()
36 {
37 struct cricketer c ;
38
39 printf ( " \ nName > " ) ;
40 scanf ( " % s " , c . name ) ;
41
42 printf ( " \ nAge > " ) ;
43 scanf ( " % d " , & c . age ) ;
44
45 printf ( " \ nMatches > " ) ;
46 scanf ( " % d " , & c . match ) ;
47
48 printf ( " \ nAverage runs > " ) ;
49 scanf ( " % f " , & c . avrn ) ;
50
51 return c ;
52 }
53
54 void display ( struct cricketer c )
55 {
56 printf ( " \ nName > % s " , c . name ) ;
57 printf ( " \ nAge > % d " , c . age ) ;
58 printf ( " \ nMatches > % d " , c . match ) ;
59 printf ( " \ nAverage runs > % f " , c . avrn ) ;
60 }

2.10 Pointer to Structure

1 # include < stdio .h >
2
3 // Structure Definition
4 struct stud
5 {
6 char name [20];
7 int roll ;
8 float marks ;
9 };
10
11 int main ()
12 {
13 struct stud * ps , s ;
14
15 // Initialize pointer with address of structure .
16 ps = & s ;
17
18 printf ( " \ nEnter name , roll , marks > " ) ;
19 scanf ( " % s % d % f " , ps - > name , & ps - > roll , & ps - > marks ) ;
20

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 11 of 31

 Chapter-1 Sample Programs

21 printf ( " \ nStudent details are : " ) ;

22 printf ( " \ nNAME =% s \ tROLL =% d \ tMARKS =% f " , ps - > name , ps - > roll , ps - > marks ) ;
23
24 return 0;
25 }

2.11 Array of Structures

1 # include < stdio .h >
2
3 /* Declaration of structure */
4 struct student
5 {
6 char name [30];
7 int roll ;
8 float marks ;
9 };
10
11 int main ()
12 {
13 struct student s [10];
14 int n , i ;
15
16 printf ( " \ nEnter the number of students > " ) ;
17 scanf ( " % d " , & n ) ;
18
19 for ( i =0; i < n ; i ++)
20 {
21 printf ( " Enter name , roll and marks of % d student > " , i +1) ;
22 scanf ( " % s % d % f " ,s [ i ]. name , & s [ i ]. roll , & s [ i ]. marks ) ;
23 }
24
25 printf ( " \ nStudent details are : " ) ;
26 for ( i =0; i < n ; i ++)
27 {
28 printf ( " \ nName > % s " ,s [ i ]. name ) ;
29 printf ( " \ nRoll > % d " , s [ i ]. roll ) ;
30 printf ( " \ nMarks > %0.2 f " , s [ i ]. marks ) ;
31 }
32
33 return 0;
34 }

2.12 Pointer to Array of Structures

1 # include < stdio .h >
2
3 struct x
4 {
5 int i ;
6 float f ;
7 char c [10];
8 };
9
10 void main ()
11 {
12 struct x x1 [10] , * p ;
13 int n , j ;
14
15 p = x1 ;
16

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 12 of 31

 Chapter-1 Sample Programs

17 printf ( " \ nEnter the array size > " ) ;

18 scanf ( " % d " ,& n ) ;
19
20 for ( j =0; j < n ; j ++)
21 {
22 printf ( " \ nEnter int , float and char values > " ) ;
23 scanf ( " % d % f % s " , &( p + j ) ->i , &( p + j ) ->f , ( p + j ) ->c ) ;
24 }
25
26 printf ( " \ nThe int , float and char values assigned are : " ) ;
27 for ( j =0; j < n ; j ++)
28 printf ( " \ n % d \ t %0.2 f \ t % s " , ( p + j ) ->i , ( p + j ) ->f , ( p + j ) ->c ) ;
29 }

2.13 Nested Structures

1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
2 Display the achievements of cricket players .
3 [ Hint > make use of Nested structure ]
4 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
5
6 # include < stdio .h >
7
8 struct stats
9 {
10 int matches ;
11 float average ;
12 };
13
14 struct cricketer
15 {
16 char name [50];
17 int age ;
18 struct stats pstats ;
19 };
20
21 struct cricketer read () ;
22 void display ( struct cricketer ) ;
23
24 void main ()
25 {
26 int i ;
27 struct cricketer c1 ;
28

29 printf ( " \ nEnter data of cricketer > " ) ;

30 c1 = read () ;
31
32 printf ( " \ nDetails of the cricketer are as follows : " ) ;
33 display ( c1 ) ;
34 }
35
36 struct cricketer read ( struct cricketer c )
37 {
38 printf ( " \ nName > " ) ;
39 scanf ( " % s " , c . name ) ;
40

41 printf ( " \ nAge > " ) ;

42 scanf ( " % d " , & c . age ) ;
43
44 printf ( " \ nMatches > " ) ;
45 scanf ( " % d " , & c . pstats . matches ) ;

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 13 of 31

 Chapter-1 Sample Programs

46
47 printf ( " \ nAverage runs > " ) ;
48 scanf ( " %0.2 f " , & c . pstats . average ) ;
49
50 return c ;
51 }
52
53 void display ( struct cricketer c )
54 {
55 printf ( " \ nName > % s " , c . name ) ;
56 printf ( " \ nAge > % d " , c . age ) ;
57 printf ( " \ nMatches > % d " , c . pstats . matches ) ;
58 printf ( " \ nAverage runs > % f " , c . pstats . average ) ;
59 }

2.14 Pointer to Nested Structures

1 # include < stdio .h >
2 # include < string .h >
3

4 struct colDetail
5 {
6 int cid ;
7 char cname [50];
8 };
9

10 struct studDetail
11 {
12 int id ;
13 char name [20];
14 float percentage ;
15

16 // structure within structure

17 struct colDetail cData ;
18 };
19
20 int main ()
21 {
22 struct studDetail s = {1 , " Blue - Om " , 90.5 , 02 , " KLE " };
23
24 struct studDetail * sPtr = & s ;
25
26 printf ( " \ nId is > % d " , sPtr - > id ) ;
27 printf ( " \ nName is > % s " , sPtr - > name ) ;
28 printf ( " \ nPercentage is > %0.2 f " , sPtr - > percentage ) ;
29
30 printf ( " \ nCollege Id is > % d " , sPtr - > cData . cid ) ;
31 printf ( " \ nCollege Name is > % s " , sPtr - > cData . cname ) ;
32
33 return 0;
34 }

3 Dynamic Memory Management

3.1 Dynamic String Memory Allocation through – malloc
1 # include < stdio .h >
2 # include < stdlib .h >
3
4 int main ()

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 14 of 31

 Chapter-1 Sample Programs

5 {
6 char * p ;
7 int n ;
8
9 printf ( " \ nWhat is the length of your string > " ) ;
10 scanf ( " % d " , & n ) ;
11
12 // allocate memory dynamically
13 p = ( char *) malloc ( n * sizeof ( char ) ) ;
14
15 if ( p == NULL )
16 {
17 printf ( " \ nError - unable to allocate required memory " ) ;
18 exit (101) ;
19 }
20 else
21 {
22 printf ( " \ nEnter the string > " ) ;
23 scanf ( " % s " , p ) ;
24 }
25
26 printf ( " \ nYour dynamically allocated string is % s " , p ) ;
27

28 // release the allocated memory

29 free ( p ) ;
30
31 return 0;
32 }

3.2 Sum of Dynamic Array Elements through – calloc

1 # include < stdio .h >
2 # include < stdlib .h >
3
4 int main ()
5 {
6 int n , i , *p , sum =0;
7

8 printf ( " \ nEnter number of elements > " ) ;

9 scanf ( " % d " , & n ) ;
10
11 // memory allocated using calloc
12 p = ( int *) calloc ( n , sizeof ( int ) ) ;
13

14 if ( p == NULL )
15 {
16 printf ( " Error ! unable to allocate memory " ) ;
17 exit (101) ;
18 }
19

20 printf ( " \ nEnter elements of array > " ) ;

21 for ( i =0; i < n ; i ++ )
22 {
23 scanf ( " % d " , p + i ) ;
24 sum += *( p + i ) ;
25 }
26
27 printf ( " Sum of the array elements is % d " , sum ) ;
28
29 free ( p ) ;
30

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 15 of 31

 Chapter-1 Sample Programs

31 return 0;
32 }

3.3 Dynamic Structure Memory Management

1 # include < stdio .h >
2 # include < stdlib .h >
3
4 struct course
5 {
6 char name [10];
7 int marks ;
8 };
9
10 int main ()
11 {
12 struct course * p ;
13 int n , i ;
14

15 printf ( " \ nEnter the number of courses > " ) ;

16 scanf ( " % d " , & n ) ;
17
18 // Memory allocation for n structures
19 p = ( struct course *) malloc ( n * sizeof ( struct course ) ) ;
20

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

22 {
23 printf ( " \ nEnter % d course name and marks : " , i +1) ;
24 scanf ( " % s % d " , ( p + i ) -> name , &( p + i ) -> marks ) ;
25 }
26

27 printf ( " \ nDisplaying Information : " ) ;

28 for ( i = 0; i < n ; i ++)
29 {
30 printf ( " \ nName : % s \ tMarks : % d " , ( p + i ) -> name , ( p + i ) -> marks ) ;
31 }
32

33 free ( p ) ;
34
35 return 0;
36 }

3.4 Increasing the Size of Dynamic Array through – realloc

1 # include < stdio .h >
2 # include < stdlib .h >
3
4 int main ()
5 {
6 int *p , * pNew , n , nNew , i ;
7 char ch ;
8
9 printf ( " \ nEnter the size of the array > " ) ;
10 scanf ( " % d " , & n ) ;
11
12 // allocate memory for n size
13 p = ( int *) malloc ( n * sizeof ( int ) ) ;
14
15 // read the data
16 for ( i =0; i < n ; i ++)
17 {

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 16 of 31

 Chapter-1 Sample Programs

18 printf ( " \ nEnter % d value > " , i +1) ;

19 scanf ( " % d " , ( p + i ) ) ;
20 }
21
22 // choose to add new items
23 printf ( " \ nDo you want to add new items [ y | n ] > " ) ;
24 scanf ( " % c " , & ch ) ;
25
26 if ( ch == ’y ’ || ch == ’Y ’ )
27 {
28 printf ( " \ nHow many more items > " ) ;
29 scanf ( " % d " , & nNew ) ;
30
31 // increase the size of data items
32 n += nNew ;
33
34 printf ( " \ nNew size : % d " , n ) ;
35
36 // reallocate the new memory
37 pNew = ( int *) realloc (p , n * sizeof ( int ) ) ;
38
39 // read the new data
40 for ( ; i < n ; i ++)
41 {
42 printf ( " \ nEnter % d value > " , i +1) ;
43 scanf ( " % d " , ( pNew + i ) ) ;
44 }
45 }
46

47 // display the data

48 printf ( " \ nData items are : " ) ;
49 for ( i =0; i < n ; i ++)
50 {
51 printf ( " % d " , *( p + i ) ) ;
52 }
53
54 return 0;
55 }

4 File Management
4.1 File Read through – fgetc
1 # include < stdio .h >
2
3 int main ()
4 {
5 FILE * fp ;
6 char ch ;
7
8 fp = fopen ( " 1. c " ," r " ) ;
9
10 while ( 1 )
11 {
12 ch = fgetc ( fp ) ;
13 if ( ch == EOF )
14 break ;
15 printf ( " % c " , ch ) ;
16 }
17

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 17 of 31

 Chapter-1 Sample Programs

18 fclose ( fp ) ;
19
20 return 0;
21 }

4.2 File Read through – fgets

1 # include < stdio .h >
2
3 int main ()
4 {
5 FILE * fp ;
6 char data [50];
7
8 fp = fopen ( " test . txt " ," r " ) ;
9
10 if ( fp == NULL )
11 {
12 printf ( " test . txt file failed to open . " ) ;
13 }
14 else
15 {
16
17 printf ( " The file is now opened .\ n " ) ;
18

19 while ( fgets ( data , 50 , fp ) != NULL )

20 {
21 printf ( " % s " , data ) ;
22 }
23 }
24

25 fclose ( fp ) ;
26
27 printf ( " \ nData successfully read from file test . txt " ) ;
28 printf ( " \ nThe file is now closed . " ) ;
29
30 return 0;
31 }

4.3 File Write through – fputs

1 # include < stdio .h >
2 # include < string .h >
3
4 int main ( )
5 {
6 FILE * fp ;
7
8 char data [50] = " I am Don , my file is dummy - dummie " ;
9
10 fp = fopen ( " test . txt " , " w " ) ;
11
12 if ( fp == NULL )
13 {
14 printf ( " \ ntest . txt file failed to open . " ) ;
15 }
16 else
17 {
18 printf ( " \ nThe file is now opened .\ n " ) ;
19 fputs ( data , fp ) ;
20 }

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 18 of 31

 Chapter-1 Sample Programs

21
22 fclose ( fp ) ;
23
24 printf ( " \ nData successfully written in file test . txt " ) ;
25 printf ( " \ nThe file is now closed . " ) ;
26
27 return 0;
28 }

5 Sample PSF and Programs

5.1 Structures

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 19 of 31

 Sample PSF and Program for Structures

April 20, 2023

Problem Statement: Varun Finchi is a manger of BCR franchise team, where he has to
select 3 players to make squad full for playing in PPL League. He contacts Lord Hassan, an
analyst of BCR team, where he has all the player details. Varun Finchi selects the players as
(1) who have highest runs in their career, (2) one who has least runs in his career and (3) one
more player who has name “Rajat”. Please help Varun Finchi to select players for BCR team.

1 Understanding the Problem

1.1 Sub-problems
Yes, we have three sub-problem in the question.

• To select the highest and lowest scoring player we have to sort the players.

• To select “Rajat” player we have to search the player from the pool.

• Copy the 3 selected players from pool to selected list.

1.2 Ambiguity
Yes, there are two ambiguity in the question. First one is how many players are there in the
pool?. Second one is which are the other player details to consider, apart from runs?
We remove the ambiguity in assumption section.

1.3 Extra Information

Yes, there are extraneous information in the question. BCR franchise team and PPL League.
These information are not needed to solve the problem.

1.4 Known
• There is pool of players.

• Every player has some details, including runs scored in his career.

• 3 players are to be selected.

• One player named “Rajat” has to be selected.

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 1 of 8

Sample PSF & Program Structures

1.5 Unknowns
• Highest run scorer.

• Lowest run scorer.

1.6 Assumptions
For the given problem as there are two ambiguities, we thus have to make two assumptions.

• For first ambiguity, we assume that user will give the pool size.

• For second ambiguity, we assume that we will take 3 player details: name, jersey number
and runs scored.

1.7 Constraints
Player name Rajat has to be selected. Thus, he has to be there in the player pool. Also, pool
should have a minimum of 3 players.

2 Plan to Solve the Problem

2.1 Problem Representation
The given problem is based on the selecting highest and lowest values. Thus, problem at hand
can be represented numerically.

2.2 Problem Solving Strategy

To find the highest and lowest values, we can sort the player details according to the runs
scored. Thus, we can solve the problem using Mathematical Reasoning strategy.

2.3 Identification of Structure Name and its Members

• Structure Name: players

• Structure Members: These include the player details

– name ← Name of the player, it is string data type.

– jerseyNo ← Jersey number of the player, it is integer data type.
– runs ← Total number of runs scored by the player, it is integer data type.

2.4 Identification of Functions

• readDetails() ← To read the number of players and their details.

• displayDetails() ← To display the players’ details and selected players.

• sortPlayers() ← To sort the players according to their runs scored.

• searchPlayer() ← To search for the rajat player.

• selectPlayers() ← To copy the selected players from pool structure to selected structure.

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 2 of 8

Sample PSF & Program Structures

3 Carrying out the Plan

3.1 Solution Strategy
The problem is solved in three steps.

1. Sort the players in descending order by their runs scored.

2. Select the first and last player from sorted list, to obtain the highest and lowest scoring
player.

3. Search the player pool from rajat and copy his details to the selected list.

Algorithm for the above solution to the problem is as shown in Algorithm 1.

Algorithm 1: Select Players

Data: pool, array of structures, holds the player details.
Result: selected, array of structures, holds the selected players.
1 STEP-0: START
2 STEP-1: // Read the player details into pool structure.
3 n ← Read the number of players.
4 for p ← 0 to n − 1 do
5 Read the player details.
6 STEP-2: Sort the players details in descending order.
// Bubble Sort
7 for i ← 0 to n − 1 do
8 for j ← 0 to (n − i) − 1 do
9 if Is players[j].runs less than players[j+1].runs? then
// then, swap entire players details
10 temp ← players[j]
11 players[j] ← players[j+1]
12 players[j+1] ← temp

13 STEP-3: Copy the highest and lowest player details to selected structure.
14 selected[0] ← players[0]
15 selected[1] ← players[1]
16 STEP-4: Search for player named “Rajat” and copy the details to selected structure.
// Linear Search
17 for i ← 0 to n − 1 do
18 if strcmp(players[j].name , “Rajat”) is ture? then
19 selected[2] ← Rajat player details.
20 STEP-5: Display the selected player details.
21 STEP-6: END

4 Assessing the Results

4.1 Was our understanding of the problem correct?
Yes. We applied the PSF to select the players according to the given rules.

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 3 of 8

Sample PSF & Program Structures

4.2 Did we overlook anything?

No. We solved all the sub-problems player selection. Also, the extra information was eliminated.

4.3 Did we choose the correct strategy?

Yes. As the problem was based on mathematical reasoning, we applied sorting technique to
obtain the highest and lowest run scorer. Further, we also used searching technique to select
the specified player.

4.4 Did we employ that strategy correctly?

Yes. We used bubble sort algorithm to obtain highest and lowest run scorers. Also, linear
search was employed to look for given player.

5 Lessons Learnt
The BCR team manager’s problem is solved using the sorting and searching algorithms.
Through descending order sort, we can obtain the players with highest runs scorers to low-
est runs scorers. Therefore we select find and last index players. We perform linear search
for player name with Rajat. Therefore we select and display the selected 3 players as per the
manager’s needs.

6 Solution Documentation
Enter number of player details to read > 7
Enter Player name, jersey number, runs scored
virat 1 40
dhoni 2 50
rohit 3 29000
ashwin 12 12000
ishant 34 2554
raina 20 12455
Rajat 10 4832
The sorted players from pool are:
NAME JERSEY RUNS
———————————-
rohit 3 29000
raina 20 12455
ashwin 12 12000
ishant 34 2554
dhoni 2 50
The selected players are:
NAME JERSEY RUNS
———————————-
rohit 3 29000
Rajat 10 4832
virat 1 40

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 4 of 8

 Sample PSF & Program Structures

7 C Program
7.1 Without Using Functions
1 # include < stdio .h >
2 # include < string .h >
3
4 // Structure Definition
5 struct player
6 {
7 char name [20];
8 int jerseyNo , runs ;
9 };
10
11 int main ()
12 {
13 struct player pool [10] , selected [10] , temp ;
14 int i , n , j ;
15
16 printf ( " \ nEnter no . of players > " ) ;
17 scanf ( " % d " ,& n ) ;
18
19 for ( i = 0; i < n ; i ++ )
20 {
21 printf ( " \ nEnter player % d details ( name , jersey number , runs ) >\ t " ,i
+1) ;
22 scanf ( " % s % d % d " , pool [ i ]. name , & pool [ i ]. jerseyNo , & pool [ i ]. runs ) ;
23 }
24
25 // Bubble Sort
26 for ( i = 0; i < n ; i ++ )
27 {
28 for ( j = 0; j < n -i -1; j ++ )
29 {
30 if ( pool [ j ]. runs < pool [ j +1]. runs )
31 {
32 temp = pool [ j ];
33 pool [ j ] = pool [ j +1];
34 pool [ j +1] = temp ;
35 }
36 }
37 }
38
39 selected [0] = pool [0];
40 selected [1] = pool [n -1];
41
42 // Linear Search
43 for ( i = 0; i < n ; i ++ )
44 {
45 if ( strcmp ( pool [ i ]. name , " rajat " ) == 0 )
46 {
47 selected [2] = pool [ i ];
48 }
49 }
50
51 printf ( " \ nPlayers in the sorted pool are : " ) ;
52 printf ( " \ nNAME \ tJERSEY \ tRUNS \ t \ n " ) ;
53 printf ( " - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\ n " ) ;
54 for ( i = 0; i < n ; i ++ )
55 {

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 5 of 8

 Sample PSF & Program Structures

56 printf ( " % s \ t %3 d \ t %3 d \ n " , pool [ i ]. name , pool [ i ]. jerseyNo , pool [ i ].

runs ) ;
57 }
58
59 printf ( " \ nThe selected players are :\ n " ) ;
60 printf ( " \ nNAME \ tJERSEY \ tRUNS \ t \ n " ) ;
61 printf ( " - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\ n " ) ;
62 for ( i = 0; i < 3 ; i ++ )
63 {
64 printf ( " % s \ t %3 d \ t %3 d \ n " , selected [ i ]. name , selected [ i ]. jerseyNo ,
selected [ i ]. runs ) ;
65 }
66
67 }

7.2 Modular Approach

1 # include < stdio .h >
2 # include < string .h >
3
4 // Structure Definition
5 struct player
6 {
7 char name [20];
8 int jerseyNo , runs ;
9 };
10

11 // Function Definition
12 void read ( int , struct player *) ;
13 void display ( int , int , struct player [] , struct player []) ;
14 int search ( int , char [] , struct player []) ;
15 void sort ( int , struct player *) ;
16 int select ( struct player [] , struct player * , int , int ) ;
17
18 int main ()
19 {
20 struct player pool [10];
21 struct player selected [10];
22 struct player * p ;
23 int n ;
24 int pos ;
25 int cnt ;
26
27 printf ( " \ nEnter no . of players > " ) ;
28 scanf ( " % d " ,& n ) ;
29
30 p = pool ;
31
32 read (n , p ) ;
33
34 sort (n , p ) ;
35
36 pos = search (n , " rajat " , p ) ;
37
38 cnt = select ( pool , selected , n , pos ) ;
39
40 display (n , cnt , pool , selected ) ;
41 }
42
43
44 void read ( int l , struct player * ply )

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 6 of 8

 Sample PSF & Program Structures

45 {
46 int i ;
47
48 for ( i = 0; i < l ; i ++ )
49 {
50 printf ( " \ nEnter player % d details ( name , jersey number , runs ) >\ t " ,i
+1) ;
51 scanf ( " % s % d % d " , ( ply + i ) -> name , &( ply + i ) -> jerseyNo , &( ply + i ) -> runs ) ;
52 }
53 }
54
55 void sort ( int l , struct player * ply )
56 {
57 int i , j ;
58 struct player temp ;
59
60 // Bubble Sort
61 for ( i = 0; i < l ; i ++ )
62 {
63 for ( j = 0; j < l -i -1; j ++ )
64 {
65 if ( ( ply + j ) -> runs < ( ply + j +1) -> runs )
66 {
67 temp = *( ply + j ) ;
68 *( ply + j ) = *( ply + j +1) ;
69 *( ply + j +1) = temp ;
70 }
71 }
72 }
73 }
74

75
76 int search ( int l , char key [] , struct player pool [])
77 {
78 int i ;
79 // Linear Search
80 for ( i = 0; i < l ; i ++ )
81 {
82 if ( strcmp ( pool [ i ]. name , " rajat " ) == 0 )
83 {
84 return i ;
85 }
86 }
87 return -1;
88 }
89
90 int select ( struct player pool [] , struct player *s , int l , int pos )
91 {
92 int cnt = 0;
93
94 * s = pool [0];
95 *( s +1) = pool [l -1];
96
97 cnt = 2;
98

99 if ( pos != -1)
100 {
101 *( s +2) = pool [ pos ];
102 cnt ++;
103 }

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 7 of 8

 Sample PSF & Program Structures

104 else
105 printf ( " \ n Rajat player not found in the pool ! " ) ;
106
107 return cnt ;
108 }
109
110 void display ( int l , int cnt , struct player p [] , struct player s [])
111 {
112 int i ;
113
114 printf ( " \n - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\ n " ) ;
115 printf ( " \ nThe sorted players from pool are : " ) ;
116 printf ( " \ nNAME \ tJERSEY \ tRUNS \ t \ n " ) ;
117 printf ( " -\n - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - " ) ;
118 for ( i = 0; i < l ; i ++ )
119 {
120 printf ( " % s \ t %3 d \ t %3 d \ n " , p [ i ]. name , p [ i ]. jerseyNo , p [ i ]. runs ) ;
121 }
122

123 printf ( " \n - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - " ) ;

124 printf ( " \ nThe selected players are : " ) ;
125 printf ( " \ nNAME \ tJERSEY \ tRUNS \ t \ n " ) ;
126 printf ( " \n - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - " ) ;
127 for ( i = 0; i < cnt ; i ++ )
128 {
129 printf ( " % s \ t %3 d \ t %3 d \ n " , s [ i ]. name , s [ i ]. jerseyNo , s [ i ]. runs ) ;
130 }
131
132 }

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 8 of 8

Chapter-1 Sample Programs

5.2 Files
5.2.1 Understanding the Problem
Problem Statement: Sangamesh once a student, now works for Contineo. His boss has
asked him to implement a database for 3rd sem students. Sangamesh had studied about flat
file databases from SPattar sir. In flat file systems, files are used for storing the data. Help
sangamesh to implement the database.

General Overview

• We need to use file management operations to implement the flat file database.

• Following operations on file are to be performed.

– Write operation to store the data.

– Read operation to access the data.

Sub-problems Yes, we have two sub-problem in the question. One is to read the data from
file and other is to write the data to the file.

Ambiguity Yes, there are two ambiguity in the question. First one is how many students’
data are to be stored? Second one is which student details are to be stored.

Extra Information Yes, there are extraneous information in the question. Sangamesh,
Contineo and SPattar are extra information.

Known

• Data is to be stored and accessed from the file (read and write).

• Student data is to be stored (structures).

• There are many students.

Unknowns There are no unknowns in the question.

Assumptions

• We assume that user will give the number of students.

• For simplicity, we will take only two data items of students: name and marks.

Constraints Which type of file to use? As the data to be stored can be large, we can use
binary files. This will reduce the storage space and the read and write operations are also quick.

5.2.2 Plan to Solve the Problem

Problem Representation The given problem is based on storing the data in files. Thus,
problem at hand can be represented in tabular form.

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 28 of 31

Chapter-1 Sample Programs

Problem Solving Strategy To store the data, we need files, and to access the data, we need
the data members of the structure. Thus, we can solve the problem using Natural Language
strategy, i.e., based on Q and A or query technique of database.

Identification of Structure Name and its Members

• Structure Name: student

• Structure Members: These include the player details

– name ← Name of the student, it is string data type.

– marks ← Marks scored by the student, it is integer data type.

Identification of Functions

• writeFile() ← To store the student details in file, it makes use of readStruct().

• readFile() ← To access the students details from file, it makes use of displayStruct().

• readStruct() ← To read the students’ details from user and give it to writeFile().

• displayStruct() ← To display the students’ details received from the readFile().

5.2.3 Carrying out the Plan

Solution Strategy The problem is solved in two steps.

1. Read data from user and store it in file.

2. Read data from file and display it.

5.2.4 Assessing the Results

Was our understanding of the problem correct? Yes. We applied the PSF to store and
access the students’ details.

Did we overlook anything? No. We solved all the sub-problems. Also, the extra informa-
tion was eliminated.

Did we choose the correct strategy? Yes. As the problem was based on natural language,
we identified the students’ details and used correct file operations to store and access the data.

Did we employ that strategy correctly? Yes. We used binary files to store the data.
Also, fread() and fwrite() library functions are used to store and read the data from the binary
file.

5.2.5 Lessons Learnt

We learnt that binary files are efficient to store a large amount of data. Traditionally, flat file
database systems made use of binary files. Also, we learnt about fread() and fwrite() functions
in stdio.h

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 29 of 31

 Chapter-1 Sample Programs

5.2.6 Solution Documentation

Enter file name> stud.db
Enter number of students> 3

Enter details for student 1

Enter Student name> sangamesh
Enter Student marks> 23

Enter details for student 2

Enter Student name> Santosh
Enter Student marks> 100

Enter details for student 3

Enter Student name> Don
Enter Student marks> 99

Students details are:

name: sangamesh marks: 23
name: Santosh marks: 100
name: Don marks: 99

5.2.7 C Program

1 # include < stdio .h >

2 # include < stdlib .h >
3 # include < string .h >
4
5 struct stud
6 {
7 char name [10];
8 int marks ;
9 };
10
11 void writeFile ( char [] , int ) ;
12 void readFile ( char [] , int ) ;
13
14 struct stud readStruct () ;
15 void displayStruct ( struct stud ) ;
16
17 int main ()
18 {
19 int n ;
20 char fName [10];
21
22 printf ( " \ nEnter file name > " ) ;
23 scanf ( " % s " , fName ) ;
24

25 printf ( " \ nEnter number of students > " ) ;

26 scanf ( " % d " , & n ) ;
27
28 writeFile ( fName , n ) ;
29 readFile ( fName , n ) ;
30
31 return 0;

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 30 of 31

 Chapter-1 Sample Programs

32 }
33
34 void writeFile ( char fName [10] , int n )
35 {
36 int i ;
37 struct stud s ;
38 FILE * fptr ;
39
40 fptr = fopen ( fName , " wb " ) ;
41
42 if ( fptr == NULL )
43 {
44 printf ( " Error ! opening file " ) ;
45 exit (101) ;
46 }
47
48 for ( i = 0; i < n ; i ++ )
49 {
50 printf ( " \ nEnter details for student % d " , i +1) ;
51 s = readStruct () ;
52 fwrite (& s , sizeof ( struct stud ) , 1 , fptr ) ;
53 }
54

55 fclose ( fptr ) ;
56 }
57
58 struct stud readStruct ()
59 {
60 struct stud s ;
61
62 printf ( " \ nEnter Student name > " ) ;
63 scanf ( " % s " , s . name ) ;
64
65 printf ( " \ nEnter Student marks > " ) ;
66 scanf ( " % d " , & s . marks ) ;
67
68 return s ;
69 }
70
71 void readFile ( char fName [10] , int n )
72 {
73 struct stud s ;
74 int i ;
75 FILE * fptr ;
76
77 fptr = fopen ( fName , " rb " ) ;
78

79 printf ( " \ nStudents details are : " ) ;

80 for ( i = 0; i < n ; i ++ )
81 {
82 fread (& s , sizeof ( struct stud ) , 1 , fptr ) ;
83 displayStruct ( s ) ;
84 }
85
86 fclose ( fptr ) ;
87 }
88
89 void displayStruct ( struct stud s )
90 {
91 printf ( " \ nname : % s \ tmarks : % d " , s . name , s . marks ) ;
92 }

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 31 of 31

KLE Technological University

II Semester
18ECSP102– Problem Solving with Data Structures

Introduction to Data Structures

2021-2022
1
Data Structures

Motivation
A data structure is a special way of organizing and storing data in a computer
so that it can be used efficiently.

Why we need data structures?

1. Data Organization: We need a proper way of organizing the data so that it can
accessed efficiently when we need that particular data.

2. Efficiency: when we need to perform several operation such as add, delete

update and search on arrays , it takes more time in arrays than some of the
other data structures.

2
Data Structures

Classification

3
KLE Technological University

II Semester
18ECSP102– Problem Solving with Data Structures

List

2021-2022
4
List

Motivation

GROCERY LIST TRAVELLING CHECK LIST CLASS TIME TABLE 5

List?

List is a sequence of “what to do” one by one.

Class Activity – 1 (Individual)

1. Prepare a “TO-DO” list after returning home from college.
2. You are given 4 assignments to complete with different deadline
dates. Prepare a Plan to complete the assignments based on
deadline.

6
List

Basic operations
1. Inserting: Insert a new data in the list
2. Deleting : To remove the existing data from the list
3. Iterating a list: Navigation of list
4. Searching : Find out a specific data in the list

7
List

Motivation

GAME OF TREASURE HUNT ROUTE PLANNER MEDIA PLAYER 8

List

Class Activity – 2 (Individual)

What is the difference between GROCERY LIST and GAME OF

TREASURE HUNT?

9
List

Can we store the linked data items in an array storage structure?

Answer: No.

Disadvantages of arrays
• Fixed in size.
• Insertions and Deletions are time consuming process.

How do we solve the problem?

Answer: Linked list.

Linked list is a sequence of data items where each data item has the
related information. Every data item is interconnected with each
other. 10
List

Linked List
A linked list is a data structure in which data items can be added
and removed during run time of the program.

Characteristics of Linked List:

1. Dynamic behavior – Adding and removing of data items during
runtime.
2. Successive elements are connected by pointers.
3. Last element points to NULL (for selective Linked Lists).
4. Keeping track of a linked list: know the pointer to the first
element of the list (called as start, head, first etc…).

head

11
Linked List

Types
Depending on the way in which the links are used to maintain
adjacency, several different types of linked lists are possible.

1. Singly-linked list
2. Circular Singly-linked list
3. Doubly linked list
4. Circular Doubly linked list

12
Linked List

Singly Linked List

head

Circular Singly Linked List

The pointer from the last element in the list points back to the first
element.
head

13
Linked List

Doubly Linked List

Pointers exist between adjacent nodes in both directions.
The list can be traversed either forward or backward.
head

Circular Doubly Linked List

head

14
Linked List

Singly Linked List

15
Linked List

Singly Linked List – Basic Operations

1. Inserting an item in the Singly Linked List
• At the End,
• At the Front,
• At the Specific position

2. Deleting an item from the Singly Linked List

• From the End,
• From the Front,
• From the Specific position

3. Traversing the Singly Linked List

4. Searching the Singly Linked List

16
Singly Linked List

Working with Singly Linked List

Class Activity – 3 (Individual)
Karnataka CET started admission for first year under
graduate program for the year 2021. After the seat allotment
process, candidates who got their seat allotted in KLE Tech.
started visiting the campus for admission. Every candidate
provided his/her basic details for admission process.
Management of KLE Tech. wanted to know the admitted list
of candidates after first round. Apply Problem Solving
Framework to create and display the list of candidates.

17
Singly Linked List

Problem Solving Framework

18
Singly Linked List

Problem Solving Framework:

I. Understanding the Problem:
1. Knowns: .
Individual Candidate details.
2. Unknowns: List of Candidates admitted to KLE Tech.
3. Extra Information: KLE Tech. Admission Process
4. Assumptions: NIL
II. Devise a Plan:
1. Problem Representation: Numerical
2. Problem Solving Strategy: Mathematical Reasoning
3. Identification of Node and its Members:
• Node: Candidate.
• Members: Name, Rank, Age, Address.
4. Identification of Operations:
• Creation of Node.
• Reading the data for each Node.
• Insertion of a Node at the end of the List.
• Displaying the List. 19
Singly Linked List

Problem Solving Framework:

III. Carry Out a Plan:
.
Solution for the Plan in terms of Algorithm / modular C program.

IV. Assess the Result:

Specify the Input and Output for the designed Algorithm / modular
C program.

V. Summary
Summarize the way you have solved the problem.

20
Singly Linked List

Node in the Linked List

A Node:
A structure which contains two important fields of information.
1. Data Part.
2. Link Part.

21
Singly Linked List

Define a node for the Candidate

struct candidate
{
char name[25]; Pointer declared inside the
int rank, age; structure, pointing to itself –
Self Referential Structure
char address[100];
struct candidate *next;
};

/* A user-defined data type called “NODE” */

typedef struct candidate *NODE;
typedef name given to self
referential structure –
Pointer typedef name

22
Singly Linked List

Creating a Singly Linked List

23
Singly Linked List

Creating a Singly Linked List

Perform Insert operation to create a Singly inked List.
We start with Insert at the End of the List.

How to begin?
To start with, we have to create a node (the first node), and make head
point to it.
Algorithm: To create a node
Step 1: Start
Step 2: Declare a pointer for node.
Step 3: Allocate the memory for node.
Step 4: Check whether memory is allocated.
Step 5: Return the address of node.
Step 6: Stop
24
Singly Linked List

Function to Create a node

NODE getnode()
{
NODE new;
new=(NODE)malloc(sizeof(struct candidate));
if(new==NULL)
{
printf("Not created\n");
exit(0);
}
new->next = NULL;
return new;
}

25
Singly Linked List

Insert Node at the End

26
Singly Linked List

Inserting Nodes at the End

To insert a node at the end of the List for more number of candidates:
1.Create the nodes, one by one.
2.Read in the fields/members of the each node.
3. Modify the links of the nodes such that the chain is formed. To form the chain, we
insert the nodes at the end of the List.

Algorithm: To insert nodes at the end of the List.

Step 1: Start
Step 2: Declare a pointer for node.
Step 3: Create the node.
Step 4: Store [Read] the details.
Step 5: Check whether the list is empty.
if it is, then make the created node as head node.
Step 6: Traverse till end of list and then Connect node at the end.
Step 7: Return head node address [first node of the list].
Step 8: Stop. 27
Singly Linked Lists

Inserting Nodes at the End: Illustration

28
Singly Linked Lists

Inserting Nodes at the End

To be called from main() function as:
NODE head;
…
…
…
head = insert_end (head);

29
Singly Linked Lists

User Defined Function: Inserting Node at the End

NODE insert_end (NODE head)
{
NODE new, cur;
new = read_details();
new ->next = NULL;
if(head==NULL)
return new;
cur = head;
while (cur->next != NULL)
{
cur = cur->next;
}
cur -> next = new;
return head;
}

30
Singly Linked List

Read the details of each node

31
Singly Linked Lists

To Read the details of each node/ Candidate

NODE read_details()
{
NODE temp;
temp = getnode();
scanf("%s %d %d %s",temp->name,&temp->rank,&temp->age,temp->address);
return temp;
}

32
Singly Linked List

Insert Node at the Front

33
Singly Linked List

Insert a node at the front of the List

To insert a node at the front of the List for more number of
candidates:
Algorithm: To insert a node at the front of List.
Step 1: Start
Step 2: Create a new node.
Step 3: Store [Read] the details.
Step 4: Check whether the list is empty.
if it is, then link the newly created i.e. the new
Node will now point to head node.
Step 5: Otherwise, Make the new node as the head node, i.e.
now head node will point to new Node.
Step 6: Stop

34
Singly Linked Lists

Inserting Nodes at the Front: Illustration

35
Singly Linked List

User Defined Function: Insert a node at the front

NODE insert_front( NODE head)
{
NODE new;
new = read_details();
new -> next = NULL;
if(head == NULL)
{
return new;
}
new ->next = head;
head = new;
return head;
}

36
Singly Linked Lists

User Defined Function: Insert a node at the front

To be called from main() function as:
NODE head;
…
…
…
head = insert_front(head);

37
Singly Linked List

Traversing and Displaying the List

38
Singly Linked List

Traversing and Displaying the List

What is to be done?
Once the linked list has been constructed, head points to the first
node of the list, start from head node and print the contents of each
node on the screen.

Algorithm: Display the list

Step 1: Start
Step 2: Check whether the list is empty.
Step 3: Follow the cur pointer.
Step 4: Display the contents of the every node as it is pointed by
cur pointer
Step 5: Stop when the cur’s next pointer reaches NULL.
Step 6: Stop

39
 Singly Linked List

Traversing and Displaying the List

OUTPUT
Name Rank Age Address
Kiran 581 18 Bangalore
Raj 105 18 Hubballi
Amar 252 18 Hubballi
Abdul 187 19 Karwar
40
Singly Linked List

Display the List

void display_list (NODE head)
{
NODE cur;
if(head==NULL)
{
printf("Empty List\n");
return NULL;
}
printf("elements are\n");
cur = head;
printf(“Name\tRank\tAge\tAddress\n");
while (cur != NULL)
{
printf("%s\t%d\t%t\t%s\n",cur->name,cur->rank,cur->age,cur->address);
cur = cur ->next;
}
}
41
Singly Linked List

Display the List

To be called from main() function as:
NODE head;
…
…
…
display_list (head);

42
Singly Linked List

Inserting at Specific Position

43
Singly Linked List

Inserting at Specific Position

Can be performed in different ways.
1. Get the information of existing node from the list. Then connect
the new node either:
a. before the specified node.
b. after the specified node.

2. Based on the node count, a new node can be connected

44
Singly Linked List

Inserting before the Specified Node

Algorithm: To insert before the specified node
Step 1: Start
Step 2: Create the new node.
Step 3: Store[Read] the data into new node.
Step 4: Read the existing node’s data.
Step 5: Traverse using two pointers prev and cur, till the existing
node. prev pointer should follow the cur pointer [i.e.
prev pointer will be one node behind the cur pointer].
Step 6: Connect prev node’s next to new node.
Step 7: Connect new node’s next to cur node.
Step 8: Return the address of head node.
Step 9: Stop

45
Singly Linked List

Inserting before the Specified Node

Insert before the existing node: Amar

46
Singly Linked List

CLASS ACTIVITY – 4
Karnataka CET started admission for first year under graduate program for the year 2021. After the seat
allotment process, candidates who got their seat allotted in KLE Tech. started visiting the campus for
admission. Every candidate provided the his/her basic details for admission process. Management of
KLE Tech. wanted to know the admitted list of candidates after first round. Apply Problem Solving
Framework to create and display the list of candidates.

During the second round of admission process, the last candidate

from the list who is from Mangalore, got admission in the
Engineering College in his hometown. He withdrew his admission
from KLE Tech. Display the updated list of candidates admitted in
KLE Tech. after withdrawal of last candidate.

47
Singly Linked List

Delete node from the list

48
Singly Linked List

Delete a node from the list

To delete a node from the Singly Linked list:
1. Delete a node from the End.
2. Delete a node from the Front.
3. Delete a node from the specific position.

49
Singly Linked List

Delete a node from End

50
Singly Linked List

Delete a node from End of the list

Algorithm: To delete a node from end of the List.

Step 1: Start
Step 2: Check whether the List is empty.
if yes, display message that List is empty.
Step 3: Check whether the List has only one node.
if yes, display the data and make head=NULL.
Step 4: Otherwise, Declare two pointers, prev and cur.
Step 5: Assign address of head node to cur.
Step 6: Traverse till the last node of the List. Pointer prev points to
last but one node. Pointer cur points to last node.
Step 7: Disconnect the prev from cur [last node].
Step 8: Display the data of cur [last node].
Step 9: Deallocate the memory of cur [last node].
Step 10: Stop
51
Singly Linked List

Delete a node from End of the list

52
 Singly Linked List

Delete a node from End of the list

NODE delete_end(NODE head) prev =NULL;
{ cur =head;
NODE prev, cur; while(cur ->next != NULL)
if(head==NULL) {
{ prev= cur;
printf(“List Empty\n”); cur = cur ->next;
}
return head;
printf(“Deleted: %s\n”, cur->name);
}
free(cur);
if(head->next==NULL)
prev->next=NULL;
{
return head;
printf(“Deleted: %s\n”, head->name);
}
free(head);
return NULL;
}

53
Singly Linked List

CLASS ACTIVITY – 5
Karnataka CET started admission for first year under graduate program for the year 2021.
After the seat allotment process, candidates who got their seat allotted in KLE Tech. started
visiting the campus for admission. Every candidate provided the his/her basic details for
admission process. Management of KLE Tech. wanted to know the admitted list of
candidates after first round. Apply Problem Solving Framework to create and display the list
of candidates.
During the second round of admission process, the last candidate from the list who is from
Mangalore, got admission in the Engineering College in his hometown. He withdrew his
admission from KLE Tech. Display the updated list of candidates admitted in KLE Tech. after
withdrawal of last candidate.

During the third round of Admission process, the first candidate in

the list obtained the admission in IIT Dharwad, he withdrew his
admission from KLE Tech. Display the updated list of candidates
admitted in KLE Tech.
54
Singly Linked List

Delete node from Front

55
Singly Linked List

Delete a node from Front of the list

Algorithm: To delete a node from front of List.
Step 1: Start
Step 2: Check whether the List is empty.
if yes, display message that List is empty.
Step 3: Otherwise, Declare a pointer, cur.
Step 4: Assign address of head node to cur.
Step 5: Move head pointer to next node.
Step 6: Disconnect the cur [first node] from the list.
Step 7: Display the data of cur [first node].
Step 8: Deallocate the memory of cur [first node].
Step 9: Stop

After the above operation, the second node in the Singly linked list
becomes the head node of the list.
56
Singly Linked List

Delete a node from Front of the list

57
Singly Linked List

User Defined Function: Delete a node from Front

NODE delete_front (NODE head)
{
NODE cur;
if(head==NULL)
{
printf(“List Empty\n”);
return head;
}
cur=head;
head=head->next;
printf(“Deleted: %s\n”, cur->name);
free(cur);
return head;
}

58
Singly Linked List

Delete node from Specific Position

59
Singly Linked List

Delete a node from Specific Position

To delete the specified node: read the details of node to delete.

Algorithm: To delete a specific node.

Step 1: Start
Step 2: Read existing node’s information to delete.
Step 3: Traverse till the specified node using two pointers prev and cur. Prev
will be pointing to one node before the node to be deleted.
Step 4: Connect prev node’s next to cur node’s next node.
Step 5: Display the cur node’s information.
Step 6: Deallocate the cur node’s memory.
Step 7: Return the address of head node.
Step 8: Stop.

60
Singly Linked List

Delete a node from Specific Position

Delete the node with name: Raj

61
 Singly Linked List

PRACTICE PROBLEMS
1. Chicago college Placement Officer Mr. Mahon Raj has all the details of
the students who are placed from the college along with the company
name and passed out year. Since the ABN visit is in March 2021,
Placement Officer has two tasks. The first one displays the students
who are placed in 2020 and the second one displays the student
details who has the highest Package. Please help Mr. Mahon Raj to do
the tasks.

62
 Singly Linked List

TAKE HOME TASK

1. A development team in TCS plans a trekking trip to Kodachadri. The
trip admin keeps track of people joining the trip. After 2 days few
people drop out and 3 new people gets added. Help the trip admin to
check the total number of people ready for the trip and create a final
list.

63
Linked List

Circular Singly Linked List

64
Circular Singly linked list

Introduction
Circular linked list is a linked list where all nodes are connected to
form a circle.
There is no NULL at the end.

Single Node of Circular List

We can traverse the whole list by starting from any node. We just
need to stop when the first visited node is visited again.

head

101 20 30 40

65
Circular Singly linked list

Introduction
Class Activity-1 (Individual)

Everyday a Postman starts distribution of the letters at 10.00

am in Lingaraj Nagar area and returns to BVB CAMPUS post
office at 12.00 noon. On first Day of the week, postman has 3
letters to deliver in his allotted area. He prepares a list of
visiting houses before leaving the Post Office and notes down
the delivery address of each house. Apply Problem Solving
Framework to create and display the list of houses visited by the
postman.

66
Circular Singly linked list

Problem Solving Framework

67
Circular Singly linked list

Problem Solving Framework

I. Understanding the Problem:
1. Knowns: letters to deliver.
2. Unknowns: List of houses to visit based on delivery address on letterrs.
3. Extra Information: Lingaraj nagar area , BVB CAMPUS post office.
4. Assumptions: Creation of list of letters on a particular day.

II. Devise a Plan:

1. Problem Representation: Numerical
2. Problem Solving Strategy: Mathematical Reasoning
3. Identification of Node and its Members:
• Node: Letter.
• Members: Name, House No, Area, mobile no.
4. Identification of Operations:
•Creation of Node.
•Reading the data for each Node.
•Insertion of a Node in a List.
•Displaying the List.
68
Circular Singly linked list

Problem Solving Framework

III. Carry Out a Plan:
Solution for the Plan in terms of Algorithm / modular C program.

IV. Assess the Result:

Specify the Input and Output for the designed Algorithm / modular C program.

V. Summary
Summarize the way you have solved the problem.

69
Circular Singly linked list

Define a node for the letter

struct letter
{
char name[25]; Pointer declared inside the
int hno; structure, pointing to itself –
char area [100]; Self Referential Structure
long int mobileno;
struct letter *next;
};

/* A user-defined data type called “NODE” */

typedef struct letter *NODE;

typedef name given to self

referential structure –
Pointer typedef name

70
Circular Singly linked list

Create a node
Algorithm: To create a node in Circular List
Step 1: Start
Step 2: Declare a pointer for node.
Step 3: Allocate the memory for node.
Step 4: Check whether memory is allocated.
Step 5: Make the next pointer point to same node (circular!).
Step 5: Return the address of node.
Step 6: Stop

71
 Circular Singly linked list

Inserting a Node in the Circular List

72
Circular Singly linked list

Inserting a Node in Circular Singly Linked List

Can be performed in following ways:
• At the End,
• At the Front,
• At the Specific position.

73
Circular Singly linked list

Inserting a Node at the End

74
Circular Singly linked list

Inserting a Node at the End

Algorithm: To insert at the end of Circular list
Step 1: Start
Step 2: Create the new node.
Step 3: Set the new node’s next to itself (circular!).
Step 4: If the list is empty, return new node.
Step 5: Otherwise, Traverse till last node of the list [using cur pointer].
Step 6: Connect cur node’s next [last node] to new node.
Step 7: Connect new node’s next to first node.
Step 8: Return the address of first node of the list.
Step 9: Stop

75
Circular Singly linked list

Inserting a Node at the End

76
Circular Singly linked list

Class Activity - 2 (Individual)

Everyday a Postman starts distribution of the letters at 10.00 am in Lingaraj Nagar area and
returns to BVB CAMPUS post office at 12.00 noon. On first Day of the week, postman has 3
letters to deliver in his allotted area. He prepares a list of visiting houses before leaving the Post
Office and notes down the delivery address of each house. Apply Problem Solving Framework to
create and display the list of houses visited by the postman.

Consider second Day of the week, postman has 1 more

additional letter to be delivered compared to first Day (4 letters)
to distribute in his allotted area. The 4th letter belongs to the
house which is located at the end of all the houses which he
visited on first Day. Update and Display the list of houses to be
visited by the postman on second Day.

77
Circular Singly linked list

Inserting a Node at the End

After 3 nodes are inserted, the Circular List looks like:

78
Circular Singly linked list

Inserting a Node at the End

NODE insert_end (NODE head)
{
NODE new, cur=head;
new = read_details( );
if(head == NULL)
{
new->next=new;
return new;
}
else
{
while(cur -> next != head)
cur =cur -> next;
}
cur -> next = new;
new -> next = head;
return head;
} 79
Circular Singly linked list

Read the details of LETTER node

NODE read_details()
{
NODE temp;
temp=getnode();
scanf("%s%d%s%ld",temp->name, &temp->hno, temp->area, &temp->mobileno);
return temp;
}

80
Circular Singly linked list

Class Activity - 3 (Individual)

Everyday a Postman starts distribution of the letters at 10.00 am in Lingaraj Nagar area and
returns to BVB CAMPUS post office at 12.00 noon. On first Day of the week, postman has 3
letters to deliver in his allotted area. He prepares a list of visiting houses before leaving the Post
Office and notes down the delivery address of each house. Apply Problem Solving Framework to
create and display the list of houses visited by the postman.

Consider second Day of the week, postman has 1 more additional letter to be delivered compared
to first Day (4 letters) to distribute in his allotted area. The 4th letter belongs to the house which
is located at the end of all the houses which he visited on first Day. Update and Display the list of
houses to be visited by the postman on second Day.

Consider Day 3 of the week, postman has 1 more additional

letter compared to first and second Day (total 5 letters) to
distribute in his allotted area. The letter belongs to the house
which is located very near to his post office. Postman plans to
deliver letter to nearer house first. Update and display the list of
houses to be visited by the postman on Day 3.
81
Circular Singly linked list

Inserting a Node at the Front

82
Circular Singly linked list

Inserting a Node at the Front

Algorithm: To insert at front of Circular List
Step 1: Start
Step 2: Create the new node.
Step 3: Set the new node’s next to itself (circular!).
Step 4: If the list is empty, return new node.
Step 5: Otherwise, Set new node’s next to the first node [head node].
Step 6: Traverse to last node using cur pointer.
Step 7: Connect new node’s next to first node.
Step 8: Connect cur node’s next [last node] to first node.
Step 9: Shift the first node pointer to new node. New node becomes first
node.
Step 10: Return the first node’s address of the list.
Step 11: Stop

83
Circular Singly linked list

Inserting at the Front

84
Circular Singly linked list

User Defined Function: Insert at the Front

NODE insert_front (NODE head)
{
NODE new, cur=head;
new = read_details();
if (head ==NULL)
{
head = new;
new -> next = head;
return head;
}
while(cur ->next != head)
{
cur = cur -> next;
}
cur -> next=new;
new->next=head;
head = new;
return head;
} 85
Circular Singly linked list

Class Activity – 4 (Individual)

Postman contains a list of houses where he has to deliver the

letters. During his second week of work, on Day 1 he has 4
letters to be delivered to the same houses to those he had
delivered last week except the last house in the list. Now he has
to remove the last house details from the list. Update and
display the list by removing details of last house from the List.

86
Circular Singly linked list

Delete a node from Circular List

87
Circular Singly linked list

Delete a node from Circular List

To delete a node from the Circular Singly Linked list:
1.Delete a node from the end.
2.Delete a node from the front.
3.Delete a node from the specified position.

88
Circular Singly linked list

Delete a node from the End

89
Circular Singly linked list

Delete a node from End

90
 Circular Singly linked list

User Defined Function: Delete a node from the End

NODE delete_end (NODE head) // CASE 3: When multiple nodes present
{ cur = head;
NODE prev=NULL, cur=head; while(cur -> next != first)
// CASE 1: When list is empty {
if(head ==NULL) prev=cur;
{ cur=cur->next;
printf("List empty\n"); }
return NULL; prev->next=head;
} printf(“House deleted: %d\n",cur->hno);
//CASE 2: When list contains only one node free(cur);
if(head->next==first) return head;
{ }
printf(“House deleted: %d\n", head->hno);
free(head);
return NULL;
}

91
Circular Singly linked list

Class Activity - 5 (Individual)

Postman contains a list of houses where he has to deliver the

letters. During his second week of work, on Day 2 he has 4
letters to be delivered to the same houses to those he had
delivered last week, except the first house in the list. Update
and display the list by removing details of first house from the
List.

92
Circular Singly linked list

Delete a node from the Front

93
Circular Singly linked list

Delete a node from the Front

Algorithm: To Delete node from begin of Circular List
Step 1: Start
Step 2: Check whether list is Empty
Step 3: Check whether list is having only one node.
Delete the list and make the head pointer NULL.
Step 4: If the list contains more than one nodes:
Step 5: Traverse the list using single pointer to reach to last node of the list.
Step 6: Mark a new pointer to first node.
Step 7: Display the details of first node.
Step 8: Shift the head pointer to second node of the list.
Step 9: Deallocate the memory of node pointed by new pointer.
Step 10: Connect the last node’s next to second node (which now becomes
first node).
Step 11: Stop 94
Circular Singly linked list

Delete a node from the Front

95
 Circular Singly linked list

Delete a node from the Front.

NODE delete_front (NODE head) while(cur->next != head)
{ {
cur=cur->next;
NODE temp, cur=head; }
if(head==NULL) temp=head;
{ head=temp->next;
cur->next=head;
printf(“List empty\n"); printf(“Deleted house: %d\n",temp->hno);
return NULL; free(temp);
return head;
}
}
if(head->next==head) //single node
{
printf(“Deleted house: %d\n",head->hno);
free(head);
return NULL;
}
96
Circular Singly linked list

PRACTICE PROBLEMS
1. Wilson is resident of India, returns from America to India for a short visit. He
wishes to go for Brand Factory for shopping. Wilson buys 3 jeans of different
companies each with 40%, 50% and 60% discount and 3 casual shirts of
different companies with 40% discount on each. Apply Problem Solving to
Prepare a bill for Wilson using Circular Singly Linked List which stores the
details of each item purchased. Calculate Total Bill amount and Display the
bill.

97
Circular Singly linked list

TAKE HOME TASK

1. After getting her PhD, Christie has become a celebrity at her university, and
her facebook profile is full of friend requests. Being the nice girl she is,
Christie has accepted all the requests. Now Kuldeep is jealous of all the
attention she is getting from other guys, he asks her to delete some of the guys
from her friend list. To avoid a 'scene', Christie decides to remove some friends
from her friend list, since she knows the popularity of each of the friends she
has, she removes some friends who are less popular than others. Help
Christie to retain friends who are more popular and Kuldeep still being a good
friend.

98
 Chapter - 02
Linked List
(Sample Programs)

Syllabus
• Abstract Data Type

• Linked List: Definition, Representation

• Operations: Traversing, Searching, Insertion and Deletion

• Doubly Linked Lists

• Circular Linked Lists

• Applications of Linked lists – Polynomials, Sparse matrix representation

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 1 of 25

 Chapter-02 Sample Programs

1 Basics of Linked List

1.1 Definition
1 // Node Definition
2 struct node
3 {
4 // Data Members
5 data_type identifier1 ;
6 data_type identifier2 ;
7 . . .
8 . . .
9
10 // Address of Next - node
11 struct node * link ;
12 };
13
14 // New - name for the pointer - to node
15 typedef struct node * NODE ;
16
17 // Header Pointer : holds address of first - node .
18 NODE head = NULL ;

1.2 Memory Representation

head

data1 link1 data2 link2 data3 link3

Figure 1: Linked List with 3 Nodes.

1.3 Node Creation

1.3.1 Algorithm

Algorithm 1: Node Creation

Data: value, data to be initialized into node members.
Result: p, address of the new node created.
1 STEP-0: START
2 STEP-1: // Allocate memory to new node using malloc()
3 NODE p = (NODE) malloc(sizeof(NODE));
4 STEP-2: // Initialize data field of the node.
5 p − > data = value;
6 STEP-3: // Assign NULL to the link field.
7 p − > link = NULL;
8 STEP-4: END

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 2 of 25

 Chapter-02 Sample Programs

1.3.2 C-function: Node Creation

1 NODE createNode ( int val )

2 {
3 // create a new node
4 NODE p = ( NODE ) malloc ( sizeof ( NODE ) ) ;
5
6 // Initialize data field .
7 p - > data = val ;
8
9 // Initialize address field .
10 p - > link = NULL ;
11
12 return p ;
13 }

2 Operations on Linked List

2.1 Traversal
Traversal is visiting every node of the linked list.

2.1.1 Steps
1. Initialize: Starts with assignment of address of first node (i.e., head) to a pointer variable.
This is considered as the current node.

2. Process: The data of the current node is processed.

3. Increment: The current node is then updated with the address of next node by assigning
link part of current node to the current pointer.

4. Test: Check if current pointer is NULL. If yes, end the traversal.

2.1.2 Algorithm

Algorithm 2: List Traversal

Data: head, pointer to first-node in the list.
1 STEP-0: START
2 STEP-1: // Intialize.
3 NODE cur = head;
4 while cur != NULL do
5 STEP-2: // Process the data field.
6 cur − > data;
7 STEP-3: // Increment.
8 cur = cur − > link;
9 STEP-4: END

2.1.3 C-function: List Traversal

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 3 of 25

 Chapter-02 Sample Programs

1 void traverseList ( NODE h )

2 {
3 NODE cur = h ;
4
5 if ( h == NULL )
6 {
7 printf ( " \ nList is empty ! " ) ;
8 return ;
9 }
10
11 while ( cur != NULL )
12 {
13 // Process the current node ’s data
14 // cur -> data ;
15
16 // Increment cur to next node .
17 cur = cur -> link ;
18 }
19
20 return ;
21 }

cur

head 30 40 20 10

Figure 2: List during Initialization.

cur

head 30 40 20 10

Figure 3: List after 2nd Iteration.

Traversal is Used for:

• To display the node members of the list

• Searching

• Counting number of nodes in list

• To reach the end of list

• To go to required position/node in the list

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 4 of 25

 Chapter-02 Sample Programs

2.1.4 Size of List: Using Traversal

Number of nodes in the linked list can be found using traversal technique.

Steps

1. Initialize: Assign head node to cur pointer and size to 0.

2. If head is NULL, then return 0.

3. Increment: Size is incremented by 1 and cur is made to point to next node.

4. Test: Check if cur pointer is NULL. If yes, return the size of list and end the traversal.

1 int sizeList ( NODE h )

2 {
3 NODE cur = h ;
4
5 int size = 0;
6

7 // Find the number of nodes in list .

8 while ( cur )
9 {
10 cur = cur - > link ;
11 size ++;
12 }
13
14 return size ;
15 }

2.2 Searching

• A linked list can be searched using linear search algorithm.

• Every node is to be visited and its data is compared.

2.2.1 Steps

1. Initialize: Starts with assignment of address of first node (i.e., head)to a pointer variable.
This is considered as the current node.

2. Searching: The data of the current node is compared with the search key. If they are
equal then search is successful.

3. Increment: If key is not found, then current node is updated with the address of next
node by assigning link part of current node to the current pointer.

4. Test: Check if current pointer is NULL. If yes, end the traversal, else continue with the
second step.

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 5 of 25

 Chapter-02 Sample Programs

Algorithm 3: List Searching

Data: head, pointer to first-node in the list.
key, search key.
Result: f lag, NULL for un-successful and pointer for matching node.
1 STEP-0: START
2 STEP-1: // Intialize.
3 NODE cur = head;
4 while cur != NULL do
5 STEP-2: // Compare the search key and data of current node.
6 if cur − > data then
7 return( cur );
8 else
9 STEP-3: // Increment.
10 cur = cur − > link;
11 return( NULL )
12 STEP-4: END

2.2.2 Algorithm

2.2.3 C-function: Searching

1 NODE searchList ( NODE h , int key )

2 {
3 NODE cur = h ;
4
5 if ( h == NULL )
6 {
7 printf ( " \ nList is empty ! " ) ;
8 return ;
9 }
10
11 while ( cur != NULL )
12 {
13 // Compare key with the current node ’s data
14 if ( cur -> data == key )
15 return cur ;
16
17 // Increment cur to next node .
18 cur = cur -> link ;
19 }
20
21 return NULL ;
22 }

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 6 of 25

Chapter-02 Sample Programs

cur Key
20

head 30 40 20 10

Figure 4: List during Initialization.

cur Key
20

head 30 40 20 10

Figure 5: List during Successful Search.

Key cur
70

head 30 40 20 10

Figure 6: List during Un-successful Search.

2.3 Insertion
A new node can be inserted in linked list:

• at the Beginning

• at given Position

• before/after given element in node

• at the End

2.3.1 Insertion: At the Beginning of the List

Steps
1. Create a new node.

2. Case-1: If there are no nodes in the list, new-node is the header.

3. Case-2: If nodes exists

(a) Point link field of new-node to the header of list.

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 7 of 25

 Chapter-02 Sample Programs

(b) Reassign head to new-node.

Algorithm

Algorithm 4: Node Insertion: At the Start

Data: head, pointer to first-node in the list.
value, data to be added.
Result: head, pointer to first-node in the list.
1 STEP-0: START
2 STEP-1: // Create a new node.
3 NODE new = createNode(value.);
4 STEP-2: // Check if list is empty.
5 if head == NULL then
6 head = new;
7 STEP-3: // There are some nodes in the list.
8 new − > link = head;
9 return( new );
10 STEP-4: END

C-function: Insert at Front

1 NODE insertFront ( NODE h , int val )
2 {
3 NODE new = createNode ( val ) ;
4
5 if ( h == NULL )
6 {
7 printf ( " \ nList is empty , new node is first node ! " ) ;
8 h = new ;
9 return h ;
10 }
11

12 new -> link = h ;

13 return new ;
14 }

head new new

10 head 10

(a) List is empty, new node created. (b) New node made as first node of the list.

Figure 7: Insertion at Front – Case-1: List is empty.

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 8 of 25

Chapter-02 Sample Programs

new
head 40 30 20 10 50

(a) List is not empty, new node created.

new
head 50

40 30 20 10

(b) New node made as first node of the list.

Figure 8: Insertion at Front – Case-2: Some nodes are present.

2.3.2 Insertion: At the End of the List

Steps

1. Create a new node.

2. Case-1: If there are no nodes in the list, new-node is the header.

3. Case-2: If nodes exists

(a) Traverse to the end of list using cur.

(b) Reassign link field of cur to new-node.

head new new

10 head 10

(a) List is empty, new node created. (b) New node made as first node of the list.

Figure 9: Insertion at End – Case-1: List is empty.

new
head 20 10 5

(a) List is not empty, new node created.

cur

new
head 20 10 5

(b) New node made as last node of the list.

Figure 10: Insertion at End – Case-2: Some nodes are present.

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 9 of 25

 Chapter-02 Sample Programs

C-function: Insert at End

1 NODE insertEnd ( NODE h , int val )
2 {
3 // Initialize current pointer to the starting node .
4 NODE cur = h ;
5
6 // Create new node .
7 NODE new = createNode ( val ) ;
8
9 if ( h == NULL )
10 {
11 printf ( " \ nList is empty , new node is first node ! " ) ;
12 h = new ;
13 return h ;
14 }
15

16 // Traverse till the end of list .

17 while ( cur - > link != NULL )
18 cur = cur - > link ;
19
20 // Assign new node as last node .
21 cur - > link = new ;
22
23 return h ;
24 }

Algorithm

Algorithm 5: Node Insertion: At the End

Data: head, pointer to first-node in the list.
value, data to be added.
Result: head, pointer to first-node in the list.
1 STEP-0: START
2 STEP-1: // Create a new node.
3 NODE new = createNode(value.);
4 STEP-2: // Check if list is empty.
5 if head == NULL then
6 head = new;
7 STEP-3: // There are some nodes in the list.
// Traverse to the end of the list.
8 cur = head;
9 while cur − > link != NULL do
10 cur = cur − > link;
11 STEP-4: // Reassign link field of cur to new-node.
12 cur − > link = new;
13 return( head );
14 STEP-4: return( head );
15 END

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 10 of 25

 Chapter-02 Sample Programs

2.3.3 Insertion: At Any Given Position of the List

Steps
1. Create a new node.

2. Case-1: If there are no nodes in the list, stop.

3. Case-2: If nodes exists

(a) Traverse to the given node position using cur.

(b) Copy the link field of cur to temp pointer.
(c) Reassign link field of cur to new-node.
(d) Reassign link field of new-node to copied address.

1 2 3
head 10 20 40

new
30

(a) Insertion at 3rd Position.

cur

head 10 20 40

(2) cur− > link = new (1) new− > link = cur− > link
new
30

(b) Reassigning of Links.

Figure 11: Insert at Any Position.

C-function: Insert at Any Position

1 // Inserts a new node at any position of the list
2 NODE insertAny ( NODE h , int pos , int val )
3 {
4 // Initialize current pointer to the starting node .
5 NODE tmp , cur = h ;
6 int i ;
7

8 int size = sizeList ( h ) ;

9
10 // Create new node .
11 NODE new = createNode ( val ) ;
12
13 if ( pos < 1 || pos > size +1 ) // Sanity check for position
14 {
15 printf ( " \ nInvalid position ! " ) ;
16 }
17 else if ( h == NULL && pos > 1 ) // If List is empty and position is
invalid

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 11 of 25

 Chapter-02 Sample Programs

18 {
19 printf ( " \ nList is empty ! " ) ;
20 }
21 else if ( pos == 1 ) // Insert at 1 st position
22 {
23 new - > link = h ;
24 h = new ;
25 }
26 else // Insert at any position
27 {
28 // Traverse till the required position .
29 cur = h ;
30 i = 1;
31 while ( i < pos )
32 {
33 tmp = cur ;
34 cur = cur - > link ;
35 i ++;
36 }
37
38 // Reassign links .
39 new - > link = tmp - > link ;
40 tmp - > link = new ;
41 }
42
43 displayList ( h ) ;
44 return h ;
45 }

2.4 Deletion
A node can be deleted in the linked list:

• at the Beginning

• at given Position

• before/after given element in node

• at the End

2.4.1 Deletion: At the Beginning of the List

Steps

1. Case-1: If there are no nodes in the list, stop.

2. Case-2: If nodes exists, copy the header to temp pointer.

(a) Increment header to next node.

(b) Free the memory of temp pointer.

C-function: Delete at Front

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 12 of 25

 Chapter-02 Sample Programs

1 NODE deleteFront ( NODE h )

2 {
3 NODE temp = h ;
4
5 if ( h == NULL )
6 {
7 printf ( " \ nList is empty ! " ) ;
8 return h ;
9 }
10
11 h = h -> link ;
12
13 free ( temp ) ;
14
15 return h ;
16 }

(1) temp

head 10 20 30 40

(2) head = head − > link

Figure 12: Deletion from Front of List.

2.4.2 Deletion: At the End of the List

Steps
1. Case-1: If there are no nodes in the list, stop.

2. Case-2: If only one node exists, delete the node

3. Case-3: If nodes more than 1 node exists, traverse to the last but one node of the list
using cur pointer.

(a) During traversal, store the address of previous node in prev pointer.
(b) Make link of prev node as NULL.
(c) Free the memory of prev pointer.

C-function: Delete at End

1 NODE deleteEnd ( NODE h )
2 {
3 NODE cur = h ;
4 NODE prev ;
5

6 // Case -1: List is empty .

7 if ( h == NULL )
8 {
9 printf ( " \ nList is empty ! " ) ;

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 13 of 25

 Chapter-02 Sample Programs

10 return h ;
11 }
12
13 // Case -2: List has only 1 node .
14 if ( h - > link == NULL )
15 {
16 h = NULL ;
17 return h ;
18 }
19
20 // Case -3: More than 1 node in the list .
21 while ( cur - > link != NULL )
22 {
23 // store previous link node
24 prev = cur ;
25 cur = cur - > link ;
26 }
27
28 // Assign 2 nd last node ’s link to Null
29 prev - > link = NULL ;
30
31 free ( cur ) ;
32

33 return h ;
34 }

prev cur

head 10 20 30 40

Figure 13: Deletion at the End of List.

2.4.3 Deletion: At Any Position in the List

Steps

1. Case-1: If there are no nodes in the list, stop.

2. Case-2: If only one nodes exists, check for position. If position is 1 then delete the node.

3. Case-3: If more than one nodes exists, traverse to the given position in the list using cur
and prev pointer.

(a) Reassign prev’s link to cur’s next node.

(b) Free the memory of cur pointer.

C-function: Delete at Any Position

1 NODE deleteAny ( NODE h , int pos )
2 {
3 NODE cur = h ;
4 NODE prev ;
5
6 int cnt = 0;
7

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 14 of 25

 Chapter-02 Sample Programs

8 // Case -1: List is empty .

9 if ( h == NULL )
10 {
11 printf ( " \ nList is empty ! " ) ;
12 return h ;
13 }
14
15 // Case -2: List has only 1 node .
16 if ( h - > link == NULL )
17 {
18 h = NULL ;
19 return h ;
20 }
21
22 // Case -3: More than 1 node in the list .
23 while ( cnt != pos )
24 {
25 // store previous link node
26 prev = cur ;
27 cur = cur - > link ;
28
29 cnt ++;
30 }
31
32 // assign previous nodes link with address of next node to cur .
33 prev - > link = cur - > link ;
34
35 free ( cur ) ;
36

37 return h ;
38 }

prev cur
pos 3 cnt 3

head 40 30 20 10

prev− >link = cur− >link

Figure 14: Deletion from Any Position in the List.

3 Menu-driven Programming
A menu can be created using infinite loop and a switch-case statement.

• Infinite loop to perform the following operations.

• printf() and scanf() statments to display and accept menu options.
• Switch-case statement to select appropriate input option.
• Function call to perform appropriate tasks.

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 15 of 25

 Chapter-02 Sample Programs

C-function Skeleton for Menu-driven Applications

1 void menu ()
2 {
3 int opn ;
4
5 // Infinite Loop for Menu
6 for ( ; ; )
7 {
8
9 // display menu through printf ()
10 printf ( " ... " ) ;
11
12 // accept menu option through scanf ()
13 scanf ( " % d " , & opn ) ;
14
15 // select appropriate option through switch
16 switch ( opn )
17 {
18 case 1: // function call for 1 st task
19 break ;
20
21 case 2: // function call for 2 nd task
22 break ;
23
24 ...
25 ...
26
27 case n : // Terminate the menu
28 printf ( " \ nBye , Bye !! " ) ;
29 exit (0) ;
30 }
31 }
32 }

4 Sample Programs
4.1 Creating a Linked List
1 # include < stdio .h >
2 # include < stdlib .h >
3
4 // Structure Definition
5 struct node
6 {
7 int data ;
8 struct node * link ;
9 };
10

11 // Renaming the structure

12 typedef struct node * NODE ;
13
14 // Function Decelerations
15 NODE createNode ( int ) ;
16 NODE insertFront ( NODE , int ) ;
17 void displayList ( NODE ) ;
18
19 // Driver Code -- Main Function
20 void main ()

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 16 of 25

 Chapter-02 Sample Programs

21 {
22 NODE head = NULL ;
23
24 // Create a list with 5 nodes
25 head = insertFront ( head , 10) ;
26 head = insertFront ( head , 20) ;
27 head = insertFront ( head , 30) ;
28 head = insertFront ( head , 40) ;
29 head = insertFront ( head , 50) ;
30
31 // Display the list
32 displayList ( head ) ;
33 }
34
35 // Creates a new node and assigns values to its fields
36 NODE createNode ( int val )
37 {
38 NODE p = ( NODE ) malloc ( sizeof ( NODE ) ) ;
39
40 p - > data = val ;
41 p - > link = NULL ;
42
43 return p ;
44 }
45
46 // Inserts a new node at the beginning of the list
47 NODE insertFront ( NODE h , int val )
48 {
49 NODE new = createNode ( val ) ;
50
51 if ( h == NULL )
52 {
53 printf ( " \ nList is empty , new node ( data : % d ) is first node !\ n " , new - >
data ) ;
54 h = new ;
55 return h ;
56 }
57
58 new -> link = h ;
59 return new ;
60 }
61
62 // Displays the list nodes , by traversing the list
63 void displayList ( NODE h )
64 {
65 NODE temp = h ;
66 int i = 0;
67
68 if ( h == NULL )
69 {
70 printf ( " \ nList is Empty ! " ) ;
71 return ;
72 }
73
74 while ( temp != NULL )
75 {
76 printf ( " %d - > " , temp - > data ) ;
77 temp = temp - > link ;
78 i ++;
79 }
80 printf ( " NULL " ) ;

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 17 of 25

 Chapter-02 Sample Programs

81 return ;
82 }

4.2 Creating a Linked List with Global Variables

1 # include < stdio .h >
2 # include < stdlib .h >
3

4 struct node
5 {
6 int data ;
7 struct node * link ;
8 };
9

10 struct node * h = NULL ;

11
12 void insertFront () ;
13 void displayList () ;
14
15 void main ()
16 {
17 int i , n ;
18
19 printf ( " \ nHow many nodes > " ) ;
20 scanf ( " % d " , & n ) ;
21

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

23 {
24 insertFront () ;
25 }
26
27 displayList () ;
28 }
29
30 void insertFront ()
31 {
32 int val ;
33 struct node * p = ( struct node *) malloc ( sizeof ( struct node ) ) ;
34
35 printf ( " \ nEnter data > " ) ;
36 scanf ( " % d " , & val ) ;
37
38 p - > data = val ;
39 p - > link = NULL ;
40
41 if ( h == NULL )
42 {
43 h = p;
44 }
45

46 p - > link = h ;
47 h = p;
48 }
49
50 void displayList ()
51 {
52 struct node * temp ;
53 int i = 0;
54
55 if ( h == NULL )
56 {

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 18 of 25

 Chapter-02 Sample Programs

57 printf ( " \ nList is Empty ! " ) ;

58 }
59 else
60 {
61 for ( temp = h ; temp != NULL ; temp = temp - > link )
62 printf ( " %d - > " , temp - > data ) ;
63 }
64 }

From now on, we will only write function declarations in the sample programs. Refer to function
definitions from sections below and write the complete programs.
• Structure Definition – 1.1

• New Node Creation – 1.3.2

• List Traversal – 2.1.3

• Size of List – 2.1.4

• List Searching – 2.2.3

• Insert at Front – 2.3.1

• Insert at End – 2.3.2

• Insert at Any Position – 2.3.3

• Delete at Front – 2.4.1

• Delete at End – 2.4.2

• Delete at Any Position – 2.4.3

• Menu Application – 3

4.3 Insert Node Program

1 # include < stdio .h >
2 # include < stdlib .h >
3
4 // Structure Definition
5 struct node
6 {
7 int data ;
8 struct node * link ;
9 };
10
11 // Renaming the structure
12 typedef struct node * NODE ;
13
14 // Function Decelerations
15 NODE createNode ( int ) ;
16
17 NODE insertFront ( NODE , int ) ;
18 NODE insertEnd ( NODE , int ) ;
19 NODE insertAny ( NODE , int , int ) ;
20
21 void displayList ( NODE ) ;
22 int sizeList ( NODE ) ;

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 19 of 25

 Chapter-02 Sample Programs

23
24 NODE insertMenu ( NODE ) ;
25 void menu ( NODE ) ;
26
27 // Driver Code -- Main Function
28 void main ()
29 {
30 NODE head = NULL ;
31
32 menu ( head ) ;
33 }
34
35 // Menu for insertion
36 NODE insertMenu ( NODE h )
37 {
38 int opn , d , p ;
39

40 printf ( " \n - - - - - - - - - - - - INSERT - - - - - - - - - - - " ) ;

41 printf ( " \n - - - - - - - - - - - - - - - - - - - - - - - - - - - - - " ) ;
42 printf ( " \ n1 : Front \ n2 : End \ n3 : Any Position " ) ;
43 printf ( " \n - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\ n " ) ;
44 scanf ( " % d " , & opn ) ;
45

46 printf ( " \ nEnter the data > " ) ;

47 scanf ( " % d " , & d ) ;
48
49 switch ( opn )
50 {
51 case 1: h = insertFront (h , d ) ;
52 break ;
53
54 case 2: h = insertEnd (h , d ) ;
55 break ;
56
57 case 3: printf ( " \ nEnter position to insert > " ) ;
58 scanf ( " % d " , & p ) ;
59 h = insertAny (h , p , d ) ;
60 break ;
61
62 default : printf ( " \ nInvalid Option ! " ) ;
63 break ;
64 }
65
66 return h ;
67 }
68
69 // Function to display menu
70 void menu ( NODE h )
71 {
72 int opn ;
73
74 // Infinite Loop for Menu
75 for ( ; ; )
76 {
77 printf ( " \n - - - - - - - - - - - - - - - - - - - - - - - - - - - - - " ) ;
78 printf ( " \n - - - - - - - - - - - - MENU - - - - - - - - - - - - - " ) ;
79 printf ( " \ nEnter > " ) ;
80 printf ( " \ n1 : Insert \ n2 : Display \ n3 : Exit " ) ;
81 printf ( " \n - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\ n " ) ;
82
83 scanf ( " % d " , & opn ) ;

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 20 of 25

 Chapter-02 Sample Programs

84
85 // select appropriate option through switch
86 switch ( opn )
87 {
88 case 1: h = insertMenu ( h ) ;
89 break ;
90
91 case 2: displayList ( h ) ;
92 break ;
93
94 case 3: printf ( " \ nBye , Bye !! " ) ;
95 exit (0) ;
96
97 default : printf ( " \ nInvalid Option ! " ) ;
98 break ;
99 }
100 }
101 }
102
103 // Include other function definitions from respective sections

4.4 Delete Node Program

1 # include < stdio .h >
2 # include < stdlib .h >
3

4 // Structure Definition
5 struct node
6 {
7 int data ;
8 struct node * link ;
9 };
10
11 // Renaming the structure
12 typedef struct node * NODE ;
13
14 // Function Decelerations
15 NODE create ( NODE ) ;
16
17 NODE createNode ( int ) ;
18
19 NODE deleteFront ( NODE ) ;
20 NODE deleteEnd ( NODE ) ;
21 NODE deleteAny ( NODE , int ) ;
22 NODE delete ( NODE ) ;
23
24 void displayList ( NODE ) ;
25
26 void menu ( NODE ) ;
27

28 // Driver Code -- Main Function

29 void main ()
30 {
31 NODE head = NULL ;
32
33 menu ( head ) ;
34 }
35
36 NODE create ( NODE h )
37 {
38

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 21 of 25

 Chapter-02 Sample Programs

39 NODE n1 , n2 , n3 , n4 , n5 ;
40
41 n1 = createNode (10) ;
42 n2 = createNode (20) ;
43 n3 = createNode (30) ;
44 n4 = createNode (40) ;
45 n5 = createNode (50) ;
46
47 h = n1 ;
48 n1 - > link = n2 ;
49 n2 - > link = n3 ;
50 n3 - > link = n4 ;
51 n4 - > link = n5 ;
52
53 return h ;
54 }
55

56 // Menu for deletion

57 NODE delete ( NODE h )
58 {
59 int opn , p ;
60
61 printf ( " \n - - - - - - - - - - - - DELETE - - - - - - - - - - - " ) ;
62 printf ( " \n - - - - - - - - - - - - - - - - - - - - - - - - - - - - - " ) ;
63 printf ( " \ n1 : Front \ n2 : End \ n3 : Any Position " ) ;
64 printf ( " \n - - - - - - - - - - - - - - - - - - - - - - - - - - - - - " ) ;
65 scanf ( " % d " , & opn ) ;
66
67 switch ( opn )
68 {
69 case 1: h = deleteFront ( h ) ;
70 break ;
71
72 case 2: h = deleteEnd ( h ) ;
73 break ;
74
75 case 3: printf ( " \ nEnter position to delete > " ) ;
76 scanf ( " % d " , & p ) ;
77 h = deleteAny (h , p ) ;
78 break ;
79

80 default : printf ( " \ nInvalid Option ! " ) ;

81 break ;
82 }
83
84 return h ;
85 }
86
87 // Function to display menu
88 void menu ( NODE h )
89 {
90 int opn ;
91

92 // Infinite Loop for Menu

93 for ( ; ; )
94 {
95 printf ( " \n - - - - - - - - - - - - - - - - - - - - - - - - - - - - - " ) ;
96 printf ( " \n - - - - - - - - - - - - MENU - - - - - - - - - - - - - " ) ;
97 printf ( " \ nEnter > " ) ;
98 printf ( " \ n1 : Create List \ n2 : Delete \ n3 : Display \ n4 : Exit " ) ;
99 printf ( " \n - - - - - - - - - - - - - - - - - - - - - - - - - - - - - " ) ;

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 22 of 25

 Chapter-02 Sample Programs

100
101 scanf ( " % d " , & opn ) ;
102
103 // select appropriate option through switch
104 switch ( opn )
105 {
106 case 1: h = create ( h ) ;
107 break ;
108
109 case 2: h = delete ( h ) ;
110 break ;
111
112 case 3: displayList ( h ) ;
113 break ;
114
115 case 4: printf ( " \ nBye , Bye !! " ) ;
116 exit (0) ;
117
118 default : printf ( " \ nInvalid Option ! " ) ;
119 break ;
120 }
121 }
122 }
123
124 // Include other function definitions from respective sections .

4.5 Complete List Program

1 # include < stdio .h >
2 # include < stdlib .h >
3
4 // Structure Definition
5 struct node
6 {
7 int data ;
8 struct node * link ;
9 };
10

11 // Renaming the structure

12 typedef struct node * NODE ;
13
14 // Function Decelerations
15 NODE createNode ( int ) ;
16

17 NODE insertFront ( NODE , int ) ;

18 NODE insertEnd ( NODE , int ) ;
19 NODE insertAny ( NODE , int , int ) ;
20 NODE insert ( NODE ) ;
21
22 NODE deleteFront ( NODE ) ;
23 NODE deleteEnd ( NODE ) ;
24 NODE deleteAny ( NODE , int ) ;
25 NODE delete ( NODE ) ;
26
27 void displayList ( NODE ) ;
28 int sizeList ( NODE ) ;
29
30 void menu ( NODE ) ;
31
32 // Driver Code -- Main Function
33 void main ()

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 23 of 25

 Chapter-02 Sample Programs

34 {
35 NODE head = NULL ;
36
37 menu ( head ) ;
38 }
39
40 // Menu for insertion
41 NODE insert ( NODE h )
42 {
43 int opn , d , p ;
44

45 printf ( " \n - - - - - - - - - - - - INSERT - - - - - - - - - - - " ) ;

46 printf ( " \n - - - - - - - - - - - - - - - - - - - - - - - - - - - - - " ) ;
47 printf ( " \ n1 : Front \ n2 : End \ n3 : Any Position " ) ;
48 printf ( " \n - - - - - - - - - - - - - - - - - - - - - - - - - - - - - " ) ;
49 scanf ( " % d " , & opn ) ;
50

51 printf ( " \ nEnter the data > " ) ;

52 scanf ( " % d " , & d ) ;
53
54 switch ( opn )
55 {
56 case 1: h = insertFront (h , d ) ;
57 break ;
58
59 case 2: h = insertEnd (h , d ) ;
60 break ;
61
62 case 3: printf ( " \ nEnter position to insert > " ) ;
63 scanf ( " % d " , & p ) ;
64 h = insertAny (h , p , d ) ;
65 break ;
66
67 default : printf ( " \ nInvalid Option ! " ) ;
68 break ;
69 }
70
71 return h ;
72 }
73
74 // Menu for deletion
75 NODE delete ( NODE h )
76 {
77 int opn , p ;
78
79 printf ( " \n - - - - - - - - - - - - DELETE - - - - - - - - - - - " ) ;
80 printf ( " \n - - - - - - - - - - - - - - - - - - - - - - - - - - - - - " ) ;
81 printf ( " \ n1 : Front \ n2 : End \ n3 : Any Position " ) ;
82 printf ( " \n - - - - - - - - - - - - - - - - - - - - - - - - - - - - - " ) ;
83 scanf ( " % d " , & opn ) ;
84
85 switch ( opn )
86 {
87 case 1: h = deleteFront ( h ) ;
88 break ;
89
90 case 2: h = deleteEnd ( h ) ;
91 break ;
92

93 case 3: printf ( " \ nEnter position to delete > " ) ;

94 scanf ( " % d " , & p ) ;

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 24 of 25

 Chapter-02 Sample Programs

95 h = deleteAny (h , p ) ;
96 break ;
97
98 default : printf ( " \ nInvalid Option ! " ) ;
99 break ;
100 }
101
102 return h ;
103 }
104
105 // Function to display menu
106 void menu ( NODE h )
107 {
108 int opn ;
109
110 // Infinite Loop for Menu
111 for ( ; ; )
112 {
113 printf ( " \n - - - - - - - - - - - - - - - - - - - - - - - - - - - - - " ) ;
114 printf ( " \n - - - - - - - - - - - - MENU - - - - - - - - - - - - - " ) ;
115 printf ( " \ nEnter > " ) ;
116 printf ( " \ n1 : Insert \ n2 : Delete \ n3 : Display \ n4 : Exit " ) ;
117 printf ( " \n - - - - - - - - - - - - - - - - - - - - - - - - - - - - - " ) ;
118
119 scanf ( " % d " , & opn ) ;
120
121 // select appropriate option through switch
122 switch ( opn )
123 {
124 case 1: h = insert ( h ) ;
125 break ;
126
127 case 2: h = delete ( h ) ;
128 break ;
129

130 case 3: displayList ( h ) ;

131 break ;
132
133 case 4: printf ( " \ nBye , Bye !! " ) ;
134 exit (0) ;
135

136 default : printf ( " \ nInvalid Option ! " ) ;

137 break ;
138 }
139 }
140 }
141

142 // Include other function definitions from respective sections .

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 25 of 25