C Programming and Data Structure (20CS0501)

UNIT-I
Introduction to C Language
C LANGUAGE ELEMENTS
The elements of the C programming language, including the names, numbers, and characters
used to construct a C program.
The following topics are discussed:
 Tokens
 Comments
 Keywords
 Identifiers
 Constants
 String literals
 Punctuation and special characters
Tokens:
In a C source program, the basic element recognized by the compiler is the "token." A
token is source-program text that the compiler does not break down into component elements.
Comments
A "comment" is a sequence of characters beginning with a forward slash/asterisk
combination (/*) that is treated as a single white-space character by the compiler and is otherwise
ignored.
/* Comments can contain keywords such as
for and while without generating errors. */
Keywords
Keywords are words that have special meaning to the C compiler.

The C language uses the following keywords:

Auto break case char const continue default do double else enum extern float for
goto if inline int long register restrict return short signed sizeof static struct
switch typedef union unsigned void volatile
Identifiers
"Identifiers" or "symbols" are the names you supply for variables, types, functions, and
labels in your program. Identifier names must differ in spelling and case from any keywords.
You cannot use keywords (either C or Microsoft) as identifiers; they are reserved for
special use.
Constants
A constant is a number, character, or character string that can be used as a value in a
program. Use constants to represent floating-point, integer, enumeration, or character values that
cannot be modified.
String literals
A "string literal" is a sequence of characters from the source character set enclosed in
double quotation marks (" "). String literals are used to represent a sequence of characters which,
taken together, form a null-terminated string. You must always prefix wide-string literals with
the letter L.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

Punctuation and special characters

The punctuation and special characters in the C character set have various uses, from
organizing program text to defining the tasks that the compiler or the compiled program carries
out.
Punctuator: one of ( ) [ ] { } * , : = ; ... #
VARIABLE DECLARATIONS AND DATA TYPES
Variable:
Variables are used to store the value during the execution of a program. The name itself
means, the value of variable can be changed hence the name “Variable“.
The variables are stored in Main Memory i.e. RAM (size depending on the data type). In C
Programming we always have to declare variable before we can use them. Note that the space is
allocated to variable in memory during execution or run-time.
C is a strongly typed language. What this means it that, the type of a variable cannot be
changed. Suppose we declared an integer type variable so we cannot store character or a decimal
number in that variable.
There are set of rules to be followed while declaring variables and data types in C Programming:
 The 1st letter should be alphabet.
 Variables can be combination of alphabets and digits.
 Underscore (_) is the only special character allowed.
 Variables can be written in both Uppercase and Lowercase or combination of both.
 Variables are Case Sensitive.
 No Spaces allowed between Characters.
 Variable name should not make use to the C Reserved Keywords.
 Variable name should not start with a number.
Data Types:
A data type can represent what type of data we can store and how much space it
occupied.

Data Type Size Value Range

char 1 byte -128 to 127 or 0 to 255

unsigned char 1 byte 0 to 255

signed char 1 byte -128 to 127

int 2 or 4 bytes -32,768 to 32,767 or -2,147,483,648 to 2,147,483,647

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

unsigned int 2 or 4 bytes 0 to 65,535 or 0 to 4,294,967,295

short 2 byte -32,768 to 32,767

unsigned short 2 byte 0 to 65,535

long 4 byte -2,147,483,648 to 2,147,483,647

unsigned long 4 byte 0 to 4,294,967,295

GENERAL FORM OF A C PROGRAM

The basic structure of a C program is divided into 6 parts which makes it easy to read,
modify, document, and understand in a particular format. C program must follow the below
mentioned outline in order to successfully compile and execute. Debugging is easier in a well -
structured C program.

1. Documentation
2. Preprocessor Section
3. Definition
4. Global Declaration
5. Main() Function
6. Sub Programs
1. Documentation
This section consists of the description of the program, the name of the program, and the
creation date and time of the program. It is specified at the start of the program in the form of
comments. Documentation can be represented as:
// description, name of the program, programmer name, date, time etc.
OR
/*
description, name of the program, programmer name, date, time etc.
*/
2. Preprocessor Section
All the header files of the program will be declared in the preprocessor section of the
program. Header files help us to access other‟s improved code into our code. A copy of these
multiple files is inserted into our program before the process of compilation.
Example:
#include<stdio.h>
#include<math.h>
3. Definition
Preprocessors are the programs that process our source code before the process of
compilation. There are multiple steps which are involved in the writing and execution of the
program. Preprocessor directives start with the „#‟ symbol. The #define preprocessor is used to
create a constant throughout the program. Whenever this name is encountered by the compiler,
it is replaced by the actual piece of defined code.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

Example:
#define long long ll
4. Global Declaration
The global declaration section contains global variables, function declaration, and static
variables. Variables and functions which are declared in this scope can be used anywhere in the
program.
5. Main() Function
Every C program must have a main function. The main() function of the program is written in
this section. Operations like declaration and execution are performed inside the curly braces of
the main program. The return type of the main() function can be int as well as void too. void()
main tells the compiler that the program will not return any value. The int main() tells the
compiler that the program will return an integer value.
6. Sub Programs
User-defined functions are called in this section of the program. The control of the program is
shifted to the called function whenever they are called from the main or outside the main()
function. These are specified as per the requirements of the programmer.
INPUT AND OUTPUT STATEMENTS
Input and Output statement are used to read and write the data in C programming.
These are embedded in stdio.h (standard Input/Output header file).
Input means to provide the program with some data to be used in the program
and Output means to display data on screen or write the data to a printer or a file.

Formatted I/O Functions:

Formatted I/O functions which refers to an Input or Ouput data that has been arranged in a
particular format. There are mainly two formatted I/O functions discussed as follows:
 scanf()
 printf()
scanf():
The scanf() function is an input function. It used to read the mixed type of data from keyboard.
You can read integer, float and character data by using its control codes or format codes.
scanf("control strings",&v1,&v2,&v3,................&vn);
printf():
This ia an output function. It is used to display a text message and to display the mixed type
(int, float, char) of data on screen.
The general syntax is as:
printf("control strings",v1,v2,v3,................vn);
OR
printf("Message line or text line");

Format Code Meaning

%c To read a single character

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

%d To read a signed decimal integer (short)

%ld To read a signed long decimal integer

%e To read a float value exponential

%f To read a float (short0 or a single precision value

%lf To read a double precision float value

%g To read double float value

%h To read short integer

%i To read an integer (decimal, octal, hexadecimal)

%o To read an octal integer only

%x To read a hexadecimal integer only

%u To read unsigned decimal integer (used in pointer)

%s To read a string

OPERATORS
 Arithmetic operators
 Assignment operators
 Relational or Comparison operators
 Logical operators
 Bitwise operators
Arithmetic Operators:
Arithmetic operators are used to perform common mathematical operations.
Operator Name Description Example

+ Addition Adds together two values x+y

- Subtraction Subtracts one value from another x-y

* Multiplication Multiplies two values x*y

/ Division Divides one value by another x/y

% Modulus Returns the division remainder x%y

Assignment operators:
Assignment operators are used to assign values to variables.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

In the example below, we use the assignment operator (=) to assign the value 10 to a
variable called x:
Relational or Comparison operators:
Comparison operators are used to compare two values. This is important in programming,
because it helps us to find answers and make decisions.
The return value of a comparison is either 1 or 0, which means true (1) or false (0). These
values are known as Boolean values, and you will learn more about them in
the Booleans and If..Else chapter.
We use the greater than operator (>) to find out if 5 is greater than 3:
Operator Name Example

== Equal to x == y

!= Not equal x != y

> Greater than x>y

< Less than x<y

>= Greater than or equal to x >= y

<= Less than or equal to x <= y

Logical Operators:
Logical operators are used to determine the logic between variables or values:
Operator Name Description Example

&& Logical and Returns true if both statements are true x < 5 && x < 10

|| Logical or Returns true if one of the statements is true x < 5 || x < 4

! Logical not Reverse the result, returns false if the result is !(x < 5 && x < 10)
true

EXPRESSIONS
An expression is a formula in which operands are linked to each other by the use of operators
to compute a value. An operand can be a function reference, a variable, an array element or a
constant.

o Arithmetic expressions
o Relational expressions
o Logical expressions
o Conditional expressions

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

PRECEDENCE AND ASSOCIATIVITY

Precedence and Associativity are two of the characters that are used for operators in an
expression for determining the order of sub-expressions when they do not have brackets.
Operator Precedence
Operator precedence helps us determine which of the operators in an expression must be
evaluated first in case the expression consists of more than a single operator.
Example,
50 – 2 * 15 is going to yield 20. It is because it gets evaluated as 50 – (2 * 15), and not as (50 – 2) *
15. The reason here is that subtraction (-) has lower precedence as compared to multiplication
(*).
Operator Associativity
We use associativity when two or more than two operators with the same precedence are
present in the same expression.
Example,
The precedence of Division and Multiplication arithmetic operators is the same. So, let‟s say we
have an expression with us which is 6 * 3 / 20. The evaluation of this expression would be (6 *
3) / 20 because the associativity will be left to right for both the operators – multiplication and
division. In a similar case, the calculation of 40 / 4 * 5 would be (40 / 4) * 5 because the
associativity would be from right to left here as well.

TYPE CONVERSIONS
Type casting refers to changing an variable of one data type into another. The compiler will
automatically change one type of data into another if it makes sense.

C‟ programming provides two types of type casting operations:

1. Implicit type casting
2. Explicit type casting
Implicit type casting
When the type conversion is performed automatically by the compiler without
programmers intervention, such type of conversion is known as implicit type conversion or
type promotion.
Explicit type casting
The type conversion performed by the programmer by posing the data type of the expression
of specific type is known as explicit type conversion.
Type casting in c is done in the following form:
(data_type) expression;
where, data_type is any valid c data type, and expression may be constant, variable or
expression.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

STATEMENTS
DECISION STATEMENTS
Decision-making statements in programming languages decide the direction of the flow of
program execution.
Decision-making statements are:
1. if statement
2. if-else statements
3. nested if statements
4. if-else-if ladder
5. switch statements
6. Jump Statements:
 break
 continue
 goto
 return

if statement
It is used to decide whether a certain statement or block of statements will be executed
or not i.e if a certain condition is true then a block of statement is executed otherwise not.
Syntax:
if(condition)
{
// Statements to execute if
// condition is true
}
if-else statements
The if statement alone tells us that if a condition is true it will execute a block of
statements and if the condition is false it won‟t. But what if we want to do something else if the
condition is false. Here comes the C else statement. We can use the else statement with
the if statement to execute a block of code when the condition is false.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

Syntax:
if (condition)
{
// Executes this block if
// condition is true
}
else
{
// Executes this block if
// condition is false
}
nested if else statements
Nested if statements mean an if statement inside another if statement.
Syntax:

if (condition)
{
If(condition)
{
// Executes this block if
// condition is true
}
else
{
// Executes this block if
// condition is false
}
}
else
{
If(condition)
{
// Executes this block if
// condition is true
}
else
{
// Executes this block if
// condition is false
}
}
if-else-if ladder
The C if statements are executed from the top down. As soon as one of the conditions
controlling the if is true, the statement associated with that if is executed, and the rest of the C

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

else-if ladder is bypassed. If none of the conditions is true, then the final else statement will be
executed.
Syntax:
if (condition)
statement;
else if (condition)
statement;
.
.
else
statement;
LOOP CONTROL STATEMENTS
Loop control statements are used to repeat set of statements.
 for loop
 while loop
 do-while loop
for loop
The syntax is as follows
for (initialization ; condition ; increment / decrement)
{
body of the loop
}

 Initialization is usually an assignment statement that is used to set the loop control
variable.
 The condition is a relational expression that determines when the loop will exit.
 The increment/decrement part defines how the loop control variable will change each
time loop is repeated.
 Loop continues to execute as long as the condition is true.
 Once the condition is false, program continues with the next statement after for loop.
while loop
The syntax is as follows
while (condition)
{
body of the loop
}

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

 Initialization is done before the loop.

 Loop continues as long as the condition is true.
 Increment and decrement part is done within the loop.
Do-while loop
The syntax is as follows
Initialization
do{
body of the loop
inc/ dec
} while (condition);

BREAK
This loop control statement is used to terminate the loop. As soon as the break statement
is encountered from within a loop, the loop iterations stop there, and control returns from the
loop immediately to the first statement after the loop.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

CONTINUE

This loop control statement is just like the break statement. The continue statement is
opposite to that of the break statement, instead of terminating the loop, it forces to execute the
next iteration of the loop.
As the name suggests the continue statement forces the loop to continue or execute the
next iteration. When the continue statement is executed in the loop, the code inside the loop
following the continue statement will be skipped and the next iteration of the loop will begin.
GOTO
The goto statement in C also referred to as the unconditional jump statement can be used
to jump from one point to another within a function

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

UNIT-II
Arrays
DECLARING AND REFERENCING ARRAYS
An array is defined as the collection of similar type of data items stored at contiguous
memory locations. Arrays are the derived data type in C programming language which can
store the primitive type of data such as int, char, double, float, etc.

Declaration of C Array
Syntax:
data_type array_name[array_size];
Example:
int marks[5];

Initialization of C Array
The simplest way to initialize an array is by using the index of each element. We can initialize
each element of the array by using the index. Consider the following example.
marks[0]=80;//initialization of array
marks[1]=60;
marks[2]=70;
marks[3]=85;
marks[4]=75;

Declaration with Initialization

We can initialize the c array at the time of declaration
int marks[5]={20,30,40,50,60};
ARRAY SUBSCRIPTS
Array Subscript in C is an integer type constant or variable name whose value ranges from 0
to SIZE 1 where SIZE is the total number of elements in the array.
Arrays are classified into two types.

1. Single Dimensional Array / One Dimensional Array

2. Two Dimensional Array
3. Multi-Dimensional Array

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

Single Dimensional Array / One Dimensional Array

Single dimensional arrays are used to store list of values of same datatype. In other words,
single dimensional arrays are used to store a row of values. In single dimensional array, data is
stored in linear form. Single dimensional arrays are also called as one-dimensional
arrays, Linear Arrays or simply 1-D Arrays.
Declaration of Single Dimensional Array
Syntax: datatype arrayName [ size ] ;

Eg: int score [60] ;

Initialization of Single Dimensional Array

Syntax: datatype arrayName [ size ] = {value1, value2, ...} ;
Eg: int marks [6] = { 89, 90, 76, 78, 98, 86 } ;

Two Dimensional Array

The two-dimensional array can be defined as an array of arrays. The 2D array is
organized as matrices which can be represented as the collection of rows and columns.
However, 2D arrays are created to implement a relational database lookalike data
structure. It provides ease of holding the bulk of data at once which can be passed to any
number of functions wherever required.
Declaration of two dimensional Array
Syntax: data_type array_name[rows][columns];

Eg: int x[3][4];

Initialization of 2D Array
Syntax: int arr[3][4]={{1,2,3,4},{5,6,7,8},{2,4,6,8}};

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

MULTI DIMENSIONAL ARRAY

An array of arrays is called as multi-dimensional array. In simple words, an array
created with more than one dimension (size) is called as multi-dimensional array. Multi-
dimensional array can be of two dimensional array or three dimensional array or four
dimensional array or more...
Initializing Three-Dimensional Array
int x[2][3][4] =
{
{ {0,1,2,3}, {4,5,6,7}, {8,9,10,11} },
{ {12,13,14,15}, {16,17,18,19}, {20,21,22,23} }
};

Accessing elements in Three-Dimensional Arrays: Accessing elements in Three-

Dimensional Arrays is also similar to that of Two-Dimensional Arrays. The difference is we
have to use three loops instead of two loops for one additional dimension in Three-dimensional
Arrays.

Functions

A function is a block of code which only runs when it is called.

Functions are two types

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

LIBRARY FUNCTIONS
Library functions in C are also inbuilt functions. These inbuilt functions are located in
some common location, and it is known as the library. All the functions are used to execute a
particular operation. These library functions are generally preferred to obtain the predefined
output.

Library Functions in Different Header Files

Header file Description

stdio.h This is standard input/output header file in which Input/Output functions are declared

conio.h This is console input/output header file

string.h All string related functions are defined in this header file

stdlib.h This header file contains general functions used in C programs

math.h All maths related functions are defined in this header file

time.h This header file contains time and clock related functions

ctype.h All character handling functions are defined in this header file

stdarg.h Variable argument functions are declared in this header file

signal.h Signal handling functions are declared in this file

setjmp.h It includes all jump functions

locale.h It includes locale functions

errno.h Error handling functions are given in this file

assert.h It includes diagnostics functions

User Defined Functions

SYNTAX :
retu_datatype func_name(arguments)
{
Body of the function
statements;
return;
}

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

call the function from main() :

syntax : func_name(arguments );

COMMUNICATION AMONG FUNCTIONS

Depending on whether arguments are present or not and whether a value is returned or not,
functions are categorized into −
 Functions without arguments and without return values
 Functions without arguments and with return values
 Functions with arguments and without return values
 Functions with arguments and with return values
Functions without arguments and without return values
In this type of functions there is no data transfer between calling function and called
function. Simply the execution control jumps from calling-function to called function and
executes called function, and finally comes back to the calling function. For example, consider
the following program...

Program
#include<stdio.h>
#include<conio.h>
void main(){
void addition() ; // function declaration
clrscr() ;
addition() ; // function call

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

getch() ;
}
void addition() // function definition
{
int num1, num2 ;
printf("Enter any two integer numbers : ") ;
scanf("%d%d", &num1, &num2);
printf("Sum = %d", num1+num2 ) ;
}

Functions without arguments and with return values

In this type of functions there is no data transfer from calling-function to called-function
(parameters) but there is data transfer from called function to calling-function (return value).
The execution control jumps from calling-function to called function and executes called
function, and finally comes back to the calling function along with a return value. For example,

consider the following program...

Program
#include<stdio.h>
#include<conio.h>
void main(){
int result ;
int addition() ; // function declaration
clrscr() ;
result = addition() ; // function call
printf("Sum = %d", result) ;
getch() ;
}
int addition() // function definition

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

{
int num1, num2 ;
printf("Enter any two integer numbers : ") ;
scanf("%d%d", &num1, &num2);
return (num1+num2) ;
}

Functions with arguments and without return values

In this type of functions there is data transfer from calling-function to called function
(parameters) but there is no data transfer from called function to calling-function (return
value). The execution control jumps from calling-function to called function along with the
parameters and executes called function, and finally comes back to the calling function. For
example, consider the following program...

Program
#include<stdio.h>
#include<conio.h>
void main(){
int num1, num2 ;
void addition(int, int) ; // function declaration
clrscr() ;
printf("Enter any two integer numbers : ") ;
scanf("%d%d", &num1, &num2);
addition(num1, num2) ; // function call
getch() ;
}
void addition(int a, int b) // function definition
{
printf("Sum = %d", a+b ) ;
}

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

Functions with arguments and with return values

In this type of functions there is data transfer from calling-function to called-function
(parameters) and also from called function to calling-function (return value). The execution
control jumps from calling-function to called function along with parameters and executes
called function, and finally comes back to the calling function along with a return value. For

example, consider the following program...

Program
#include<stdio.h>
#include<conio.h>
void main(){
int num1, num2, result ;
int addition(int, int) ; // function declaration
clrscr() ;
printf("Enter any two integer numbers : ") ;
scanf("%d%d", &num1, &num2);
result = addition(num1, num2) ; // function call
printf("Sum = %d", result) ;
getch() ;
}
int addition(int a, int b) // function definition
{
return (a+b) ;
}

Using array Elements as Function Arguments

We can pass an array (one, two or multidimensional) as an argument to a function. The C
language allows us to define functions that have one or more arrays as parameters. These
parameters can be of different types and sizes.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

Syntax:
ret_type func_name ( arr_type arr_name [ ])
{
.........
}
Program:
double Average(int Array[10]); //function prototype
int main()
{
int Dal[]= {1,2,3,4,5,6,7,8,9,10}; //array
clrscr();
printf("Average of Array Element is : %5.3f\n",Average (Dal));
}
double Average (int AR [10]) // definition of function
{
int i;
double Sum =0;
for( i =0; i<10; i++)
Sum +=AR[i];
return Sum/10;
}
SCOPE
A scope in any programming is a region of the program where a defined variable can have its
existence and beyond that variable it cannot be accessed.
 Inside a function or a block which is called local variables.
 Outside of all functions which is called global variables.
 In the definition of function parameters which are called formal parameters.

Local Variables
Variables that are declared inside a function or block are called local variables. They can be used
only by statements that are inside that function or block of code.
#include <stdio.h>
int main () {
int a, b; /* local variable declaration */
int c;
a = 10; /* actual initialization */
b = 20;
c = a + b;
printf ("value of a = %d, b = %d and c = %d\n", a, b, c);
}
Global variables
Global variables are defined outside a function, usually on top of the program. Global
variables hold their values throughout the lifetime of your program and they can be accessed
inside any of the functions defined for the program.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

A global variable can be accessed by any function. That is, a global variable is available for
use throughout your entire program after its declaration.
#include <stdio.h>
int g; /* global variable declaration */
int main () {
int a, b; /* local variable declaration */
a = 10; /* actual initialization */
b = 20;
g = a + b;
printf ("value of a = %d, b = %d and g = %d\n", a, b, g);
}
Formal Parameters
Formal parameters, are treated as local variables with-in a function and they take precedence over
global variables.
#include <stdio.h>
int a = 20; /* global variable declaration */
int main () {
int a = 10; /* local variable declaration in main function */
int b = 20;
int c = 0;
printf ("value of a in main() = %d\n", a);
c = sum( a, b);
printf ("value of c in main() = %d\n", c);
}

/* function to add two integers */

int sum(int a, int b) {
printf ("value of a in sum() = %d\n", a);
printf ("value of b in sum() = %d\n", b);
return a + b;
}

STORAGE CLASSES
Storage Classes are used to describe the features of a variable/function. These features
basically include the scope, visibility and life-time which help us to trace the existence of a
particular variable during the runtime of a program.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

auto:
 This is the default storage class for all the variables declared inside a function or a
block.
 Hence, the keyword auto is rarely used while writing programs in C language.
 Auto variables can be only accessed within the block/function they have been declared
and not outside them (which defines their scope).
 They are assigned a garbage value by default whenever they are declared.

extern:
 Extern storage class simply tells us that the variable is defined elsewhere and not
within the same block where it is used.
 Basically, the value is assigned to it in a different block and this can be
overwritten/changed in a different block as well.
 So an extern variable is nothing but a global variable initialized with a legal value
where it is declared in order to be used elsewhere.
 It can be accessed within any function/block. Also, a normal global variable can be
made extern as well by placing the „extern‟ keyword before its declaration/definition
in any function/block.
static:
 This storage class is used to declare static variables which are popularly used while
writing programs in C language.
 Static variables have the property of preserving their value even after they are out of their
scope!
 Hence, static variables preserve the value of their last use in their scope. So we can say that
they are initialized only once and exist till the termination of the program.
 Thus, no new memory is allocated because they are not re-declared. Their scope is local to
the function to which they were defined.
 Global static variables can be accessed anywhere in the program.
 By default, they are assigned the value 0 by the compiler.
register:
 This storage class declares register variables that have the same functionality as that of the
auto variables.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

 The only difference is that the compiler tries to store these variables in the register of the
microprocessor if a free registration is available.
 This makes the use of register variables to be much faster than that of the variables stored
in the memory during the runtime of the program.
 If a free registration is not available, these are then stored in the memory only.
 Usually few variables which are to be accessed very frequently in a program are declared
with the register keyword which improves the running time of the program.
TYPE QUALIFIERS
The keywords which are used to modify the properties of a variable are called type qualifiers.
There are two types of qualifiers available in C language. They are,
1. const
2. volatile
1. Const keyword:
 Constants are also like normal variables. But, only difference is, their values can‟t be
modified by the program once they are defined.
 They refer to fixed values. They are also called as literals.
 They may be belonging to any of the data type.
 Syntax:
const data_type variable_name; (or) const data_type *variable_name;
2. Volatile Keyword:
 When a variable is defined as volatile, the program may not change the value of the
variable explicitly.
 But, these variable values might keep on changing without any explicit assignment by
the program. These types of qualifiers are called volatile.
 For example, if global variable‟s address is passed to clock routine of the operating
system to store the system time, the value in this address keep on changing without
any assignment by the program. These variables are named as volatile variable.
 Syntax:
volatile data_type variable_name; (or) volatile data_type *variable_name;
RECURSION
Recursion is the technique of making a function call itself. This technique provides a way to
break complicated problems down into simple problems which are easier to solve.
unsigned long long int factorial(unsigned int i)
{
if(i <= 1) {
return 1;
}
return i * factorial(i - 1);
}
int main() {
int i = 12;

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

printf("Factorial of %d is %d\n", i, factorial(i));

return 0;
}
PREPROCESSOR COMMANDS
The C preprocessor is a macro processor that is used automatically by the C compiler to
transform your program before actual compilation. It is called a macro processor because it
allows you to define macros, which are brief abbreviations for longer constructs. A macro is a
segment of code which is replaced by the value of macro. Macro is defined by #define directive.

 #define: It substitutes a preprocessor using macro.

 #include: It helps to insert a certain header from another file.

 #undef: It undefines a certain preprocessor macro.

 #ifdef: It returns true if a certain macro is defined.

 #ifndef: It returns true if a certain macro is not defined.

 #if, #elif, #else, and #endif: It tests the program using a certain condition; these
directives can be nested too.

 #line: It handles the line numbers on the errors and warnings. It can be used to change
the line number and source files while generating output during compile time.

 #error and #warning: It can be used for generating errors and warnings.

 #error can be performed to stop compilation.

 #warning is performed to continue compilation with messages in the console window.

 #region and #endregion: To define the sections of the code to make them more
understandable and readable, we can use the region using expansion and collapse
features.

Strings
STRING BASICS
String in C programming is a sequence of characters terminated with a null character „\0‟.
Strings are defined as an array of characters. The difference between a character array and a
string is the string is terminated with a unique character „\0‟.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

Declaration of Strings
Declaring a string is as simple as declaring a one-dimensional array. Below is the basic syntax for
declaring a string.
char str_name[size];
Initializing a String
char str[] = "GeeksforGeeks";
char str[50] = "GeeksforGeeks";
char str[14] = { 'G','e','e','k','s','f','o','r','G','e','e','k','s','\0'};
char str[] = { 'G','e','e','k','s','f','o','r','G','e','e','k','s','\0'};
Sample Program
int main()
{
char str[] = "Geeks"; // declare and initialize string
printf("%s\n", str); // print string
int length = 0;
length = strlen(str);
printf("Length of string str is %d", length); // displaying the length of string
}
STRING LIBRARY FUNCTIONS
The predefined functions which are designed to handle strings are available in the library
“string.h”. They are –

 strlen ()
 strcmp ()
 strcpy ()
 strncmp ()
 strncpy ()
 strrev ()
 strcat ()
 strstr ()

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

 strncat ()
The strlen () function
It returns the number of characters in a string.
Syntax: int strlen (string name);
Sample Program
int main(){
char ch[20]={'j', 'a', 'v', 'a', 't', 'p', 'o', 'i', 'n', 't', '\0'};
printf("Length of string is: %d",strlen(ch));
return 0;
}
The strcpy () function
 It is for copying source string into destination string.
 The length of the destination string >= source string.
Syntax: strcpy (Destination string, Source String);
Sample Program
int main(){
char ch[20]={'j', 'a', 'v', 'a', 't', 'p', 'o', 'i', 'n', 't', '\0'};
char ch2[20];
strcpy(ch2,ch);
printf("Value of second string is: %s",ch2);
return 0;
}
The strcat () function
 It combines two strings.
 The length of the destination string must be > than the source string.
Syntax: strcat (Destination String, Source string);
Sample Program
int main(){
char ch[10]={'h', 'e', 'l', 'l', 'o', '\0'};
char ch2[10]={'c', '\0'};
strcat(ch,ch2);
printf("Value of first string is: %s",ch);
return 0;
}

The strcmp() function (String comparison)

 This function compares 2 strings.
 It returns the ASCII difference of the first two non – matching characters in both the
strings.
Syntax: int strcmp (string1, string2);
//If the difference is equal to zero, then string1 = string2
//If the difference is positive, then string1 > string2
//If the difference is negative, then string1 < string2

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

Sample Program
int main(){
char str1[20],str2[20];
printf("Enter 1st string: ");
gets(str1);//reads string from console
printf("Enter 2nd string: ");
gets(str2);
if(strcmp(str1,str2)==0)
printf("Strings are equal");
else
printf("Strings are not equal");
}
The strrev () function
The function is used for reversing a string.
The reversed string will be stored in the same string.
Syntax: strrev (string)
Sample Program
int main(){
char str[20];
printf("Enter string: ");
gets(str);//reads string from console
printf("String is: %s",str);
printf("\nReverse String is: %s",strrev(str));
}
Function Description

strlen(string_name) returns the length of string name.

strcpy(destination, source) copies the contents of source string to destination string.

strcat(first_string, second_string) concats or joins first string with second string. The result of the
string is stored in first string.

strcmp(first_string, compares the first string with second string. If both strings are
second_string) same, it returns 0.

strrev(string) returns reverse string.

strlwr(string) returns string characters in lowercase.

strupr(string) returns string characters in uppercase.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

UNIT-III
Pointers
POINTER DECLARATION
A pointer is a variable used to store memory address.
Declaring a Pointer in C
Syntax: datatype *pointer_name;
Here, pointer_name is the name of the pointer and that should be a valid C identifier.
The datatype of the pointer and the variable to which the pointer variable is pointing must be
the same.
Example
int *ptr; //pointer to int
float *ptr; //pointer to float
char *ptr; //pointer to char
double *ptr; //pointer to double
Assigning Value to a Pointer Variable
When we declare a pointer, it contains garbage value, which means it could be pointing
anywhere in the memory.
Pointer Initialization is the process of assigning the address of a variable to a pointer. In C
language, the address operator & is used to determine the address of a variable. The & returns
the address of the variable associated with it.
Example
#include<stdio.h>
int main(void)
{
int a = 10;
int *ptr; // declare a pointer
ptr = &a; // assign value to pointer
printf("Value at ptr is: %d \n", *ptr); //10
printf("Address pointed by ptr is: %p \n", ptr); //2000
}

Pointer variables must always point to variables of the same data type.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

POINTERS AND ARRAYS

 An Array name is „C‟ is very much like a pointer but there is a difference between them.
 The pointer is a variable that can be appeared on the left side of an assignment operator.
The array name is constant and can‟t appear on the left side of an assignment operator.
1. Generating Pointer to an Array :
int a[5]={10,20,30,40,50};
int *p=a;
2. Pointer and one-dimensional Array (and) Indexing pointer:
In „C‟, pointer and one dimensional array have a close relationship
Consider the following declaration,
int value[20];
int *ptr;
 Where the array „value‟ is an integer type and the address of the first element can be
declared as a value[0].
 value[0] holds the address of the zeroth element of the array „value‟.
 The pointer variable ptr is also an address, so the declaration of value[0] and the ptr is
same as both hold addresses.
 If the pointer is incremented to the next data elements, then the address of the
incremented value of the pointer will be same as the value of the next element.
 Arrays subscripting is terms of pointer arithmetic. The expression a[i] is defined as
a[i] = * ((a) + (i))
= *(& (a) (0) + (i))
&a[1] is equivalent to (a+1) AND, a[1] is equivalent to *(a+1).
&a[2] is equivalent to (a+2) AND, a[2] is equivalent to *(a+2).
&a[3] is equivalent to (a+1) AND, a[3] is equivalent to *(a+3).
…..
&a[i] is equivalent to (a+i) AND, a[i] is equivalent to *(a+i).
ARRAY OF POINTERS
When we want to point at multiple variables or memories of the same data type in a C
program, we use an array of pointers.
An array of pointers can be declared just like we declare the arrays of char, float, int, etc.
The syntax for declaring an array of pointers would be:
Syntax: data_type *name_of_array [array_size];
Example: int *ary[55]
Sample Program
#include <stdio.h>
const int MAX = 3;
int main () {
int var[] = {10, 100, 200};
int i, *ptr[MAX];
for ( i = 0; i < MAX; i++) {
ptr[i] = &var[i]; /* assign the address of integer. */
}

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

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

printf("Value of var[%d] = %d\n", i, *ptr[i] );
}
}
POINTERS TO POINTERS
A pointer variable can store the address of another pointer variable is called Pointe to
Pointer.
The first pointer is used to store the address of a variable whereas the second pointer is
used to store the address of the first pointer. Let's understand it by the diagram given below.

The syntax of declaring a double pointer is given below.

int **p; // pointer to a pointer which is pointing to an integer.
Example Program
#include<stdio.h>
void main ()
{
int a = 10;
int *p;
int **pp;
p = &a; // pointer p is pointing to the address of a
pp = &p; // pointer pp is a double pointer pointing to the address of pointer p
printf("address of a: %x\n",p); // Address of a will be printed
printf("address of p: %x\n",pp); // Address of p will be printed
printf("value stored at p: %d\n",*p); // value stoted at the address contained by p is
printf("value stored at pp: %d\n",**pp);
// value stored at the address contained by the pointer stoyred at pp
}

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

VOID POINTER
The void pointer in C is a pointer that is not associated with any data types. It points to some
data location in the storage. This means that it points to the address of variables. It is also called
the general purpose pointer.

Syntax
void *name_of_pointer;
 Here, the void keyword acts as the pointer type, and it is followed by the pointer name-
to which the pointer type points and allocates the address location in the code.
 The declaration of a pointer happens with the name and type of pointer that supports
any given data type. Let us take a look at an example to understand this better.
Ex: void *ptr;
#include<stdlib.h>
int main() {
int v = 7;
float w = 7.6;
void *u;
u = &v;
printf(“The Integer variable in the program is equal to = %d”, *( (int*) u) );
u = &w;
printf(“\nThe Float variable in the program is equal to = %f”, *( (float*) u) );
return 0;
}
MEMORY ALLOCATION FUNCTIONS
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.
1. malloc()
2. calloc()
3. realloc()
4. free()

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

malloc() allocates single block of requested memory.

calloc() allocates multiple block of requested memory.

realloc() reallocates the memory occupied by malloc() or calloc() functions.

free() frees the dynamically allocated memory.

malloc() function in C
The malloc() function allocates single block of requested memory.

Syntax: ptr=(cast-type*)malloc(byte-size);
Program:
int main(){
int n,i,*ptr,sum=0;
printf("Enter number of elements: ");
scanf("%d",&n);
ptr=(int*)malloc(n*sizeof(int)); //memory allocated using malloc
if(ptr==NULL)
{
printf("Sorry! unable to allocate memory");
}
printf("Enter elements of array: ");
for(i=0;i<n;++i)
{
scanf("%d",ptr+i);
sum+=*(ptr+i);
}
printf("Sum=%d",sum);
free(ptr);
}
calloc() function in C
The calloc() function allocates multiple block of requested memory.
Syntax: ptr=(cast-type*)calloc(number, byte-size);
Program:
int main(){
int n,i,*ptr,sum=0;
printf("Enter number of elements: ");
scanf("%d",&n);
ptr=(int*)calloc(n,sizeof(int)); //memory allocated using calloc
if(ptr==NULL)
{
printf("Sorry! unable to allocate memory");

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

}
printf("Enter elements of array: ");
for(i=0;i<n;++i){
scanf("%d",ptr+i);
sum+=*(ptr+i);
}
printf("Sum=%d",sum);
free(ptr);
}

realloc() function in C
If memory is not sufficient for malloc() or calloc(), you can reallocate the memory by realloc()
function. In short, it changes the memory size.
Syntax: ptr=realloc(ptr, new-size);

free() function in C
The memory occupied by malloc() or calloc() functions must be released by calling free()
function. Otherwise, it will consume memory until program exit.
Syntax: free(ptr);
POINTER TO FUNCTIONS
Pointer to functions can implemented in ways
 Call by value
 Call by reference
Call by value
o In call by value method, the value of the actual parameters is copied into the formal
parameters. In other words, we can say that the value of the variable is used in the
function call in the call by value method.
o In call by value method, we can not modify the value of the actual parameter by the
formal parameter.
o In call by value, different memory is allocated for actual and formal parameters since the
value of the actual parameter is copied into the formal parameter.
o The actual parameter is the argument which is used in the function call whereas formal
parameter is the argument which is used in the function definition.
#include <stdio.h>
void swap(int , int); //prototype of the function
int main()
{
int a = 10;
int b = 20;
printf("Before swapping the values in main a = %d, b = %d\n",a,b);
// printing the value of a and b in main
swap(a,b);
printf("After swapping values in main a = %d, b = %d\n",a,b);

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

// The value of actual parameters do not change by changing the formal parameter
s in call by value, a = 10, b = 20
}
void swap (int a, int b)
{
int temp;
temp = a;
a=b;
b=temp;
printf("After swapping values in function a = %d, b = %d\n",a,b);
// Formal parameters, a = 20, b = 10
}
Call by Reference
o In call by reference, the address of the variable is passed into the function call as the actual
parameter.
o The value of the actual parameters can be modified by changing the formal parameters
since the address of the actual parameters is passed.
o In call by reference, the memory allocation is similar for both formal parameters and
actual parameters. All the operations in the function are performed on the value stored at
the address of the actual parameters, and the modified value gets stored at the same
address.
#include <stdio.h>
void swap(int *, int *); //prototype of the function
int main()
{
int a = 10;
int b = 20;
printf("Before swapping the values in main a = %d, b = %d\n",a,b);
// printing the value of a and b in main
swap(&a,&b);
printf("After swapping values in main a = %d, b = %d\n",a,b);
// The values of actual parameters do change in call by reference, a = 10, b = 20
}
void swap (int *a, int *b)
{
int temp;
temp = *a;
*a=*b;
*b=temp;
printf("After swapping values in function a = %d, b = %d\n",*a,*b);
// Formal parameters, a = 20, b = 10
}

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

POINTERS AND STRINGS

A string is a sequence of characters which we save in an array. In C programming language
the \0 null character marks the end of a string.
char str[6]=”Hello”;
The above string can be represented in memory as follows.

Each character in the string str takes 1 byte of memory space.

Creating a pointer for the string:
The variable name of the string str holds the address of the first element of the array i.e., it points
at the starting memory address.
So, we can create a character pointer ptr and store the address of the string str variable in it. This
way, ptr will point at the string str.
In the following code we are assigning the address of the string str to the pointer ptr.
char *ptr=str;

We can represent the character pointer variable ptr as follows.

The pointer variable ptr is allocated memory address 8000 and it holds the address of the string
variable str i.e., 1000.
Accessing string via pointer:
To access and print the elements of the string we can use a loop and check for the \0 null
character.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

STRUCTURE AND UNION

DECLARATION AND INITIALIZATION OF STRUCTURE
The structure is a collection of different datatype variables, grouped together under a single
name. It is a heterogeneous collection of data items that share a common name.
The general form of structure declaration
struct tagname{
datatype member2;
datatype member n;
};
Here,
 struct is the keyword.
 tagname specifies the name of a structure
 member1, member2 specifies the data items that makeup structure.
For example,
struct book{
int pages;
char author [30];
float price;
};
Declaring structure variable along with structure declaration
Syntax
struct name/tag
{
//structure members
} variables;

Example1:
struct car

{
char name[100];
float price;
} car1;

Example2:
struct car
{
char name[100];
float price;
} car1, car2, car3; // We can also declare many variables using comma (,) like below,

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

Declaring structure variable using struct keyword

Syntax: struct name variables;

Example:
struct car
{
char name[100];
float price;
};
struct car car1, car2, car3;
Initializing structure members
struct car
{
char name[100];
float price;
};
struct car car1 ={"xyz", 987432.50};

How to access the structure members

 To access structure members, we have to use dot (.) operator.

 It is also called the member access operator.

#include<stdio.h>
int main()
{
struct car
{
char name[100];
float price;
};
struct car car1 ={"xyz", 987432.50};
printf("Name of car1 = %s\n",car1.name);
printf("Price of car1 = %f\n",car1.price);
}

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

STRUCTURE WITHIN STRUCTURE

One structure can be declared inside another structure in the same way structure members are
declared inside a structure.

struct name_1
{
member1;
member2;
.
.
membern;
struct name_2
{
member_1;
member_2;
.
.
member_n;
} var1;
} var2;

The member of a nested structure can be accessed using the following syntax:
Variable name of Outer_Structure.Variable name of Nested_Structure.data member to access
#include<stdio.h>
struct Person{ //Main Structure
char Name[500];
int Age;
char Gender;
char temp; //To clear buffer
struct Address{ //Nested Structure
char Apartment[500];
char Street[500];
char City[100];
char State[100];
int Zipcode;
}a[20];//Nested Structure Variable
}p[20]; //Main Structure Variable
void main(){
int i;
//Reading User I/p
for (i=1;i<3;i++){ //Declaring function to accept 2 people's data
printf("Enter the Name of person %d : ",i);
gets(p[i].Name);

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

printf("Enter the Age of person %d : ",i);

scanf("%d",&p[i].Age);
scanf("%c",&p[i].temp); //Clearing Buffer
printf("Enter the Gender of person %d : ",i);
scanf("%c",&p[i].Gender);
scanf("%c",&p[i].temp); //Clearing Buffer
printf("Enter the City of person %d : ",i);
gets(p[i].a[i].City);
printf("Enter the State of person %d : ",i);
gets(p[i].a[i].State);
printf("Enter the Zip Code of person %d : ",i);
scanf("%d",&p[i].a[i].Zipcode);
scanf("%c",&p[i].temp); //Clearing Buffer
}
for (i=1;i<3;i++){ //Printing O/P
printf("The Name of person %d is : %s\n",i,p[i].Name);
printf("The Age of person %d is : %d\n",i,p[i].Age);
printf("The Gender of person %d is : %c\n",i,p[i].Gender);
printf("The City of person %d is : %s\n",i,p[i].a[i].City);
printf("The State of person %d is : %s\n",i,p[i].a[i].State);
printf("The Zip code of person %d is : %d\n",i,p[i].a[i].Zipcode);
}
}
ARRAY OF STRUCTURES

 An array of structure in C programming is a collection of different datatype variables,

grouped together under a single name.
 In array of structure to declare structure variable as an array variable

struct book{
int pages;
char author [30];
float price;
};
struct book b[10]; // 10 elements in an array of structures of type „book‟
Example
struct student
{
int id;
char name[30];
float percentage;
};
int main()

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

{
int i;
struct student record[2]; //Structure variable as array variable
record[0].id=1; // 1st student's record
strcpy(record[0].name, "Bhanu");
record[0].percentage = 86.5;
record[1].id=2; // 2nd student's record
strcpy(record[1].name, "Priya");
record[1].percentage = 90.5;
record[2].id=3; // 3rd student's record
strcpy(record[2].name, "Hari");
record[2].percentage = 81.5;
for(i=0; i<3; i++)
{
printf(" Records of STUDENT : %d \n", i+1);
printf(" Id is: %d \n", record[i].id);
printf(" Name is: %s \n", record[i].name);
printf(" Percentage is: %f\n\n", record[i].percentage);
}
}

POINTER TO STRUCTURE
The structure pointer points to the address of a memory block where the Structure is being
stored.
Declaration
 The declaration of a structure pointer is similar to the declaration of the structure variable.
 So, we can declare the structure pointer and variable inside and outside of the main()
function.
 To declare a pointer variable in C, we use the asterisk (*) symbol before the variable's
name.
Syntax:
struct structure_name *ptr;
Initialization of the Structure Pointer
Syntax:
ptr = &structure_variable;
(OR)
struct structure_name *ptr = &structure_variable;
Access Structure member using pointer:
There are two ways to access the member of the structure using Structure pointer:
1. Using ( * ) asterisk or indirection operator and dot ( . ) operator.
2. Using arrow ( -> ) operator or membership operator.
Example:
#include <stdio.h>

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

{
char name[30];
int id;
int age;
char gender[30];
char city[40];
};
// define the variables of the Structure with pointers
struct Employee emp1, emp2, *ptr1, *ptr2;

int main()
{
// store the address of the emp1 and emp2 structure variable
ptr1 = &emp1;
ptr2 = &emp2;
printf (" Enter the name of the Employee (emp1): ");
scanf (" %s", &ptr1->name);
printf (" Enter the id of the Employee (emp1): ");
scanf (" %d", &ptr1->id);
printf (" Enter the age of the Employee (emp1): ");
scanf (" %d", &ptr1->age);
printf (" Enter the gender of the Employee (emp1): ");
scanf (" %s", &ptr1->gender);
printf (" Enter the city of the Employee (emp1): ");
scanf (" %s", &ptr1->city);

printf (" \n Second Employee: \n");

printf (" Enter the name of the Employee (emp2): ");
scanf (" %s", &ptr2->name);
printf (" Enter the id of the Employee (emp2): ");
scanf (" %d", &ptr2->id);
printf (" Enter the age of the Employee (emp2): ");
scanf (" %d", &ptr2->age);
printf (" Enter the gender of the Employee (emp2): ");
scanf (" %s", &ptr2->gender);
printf (" Enter the city of the Employee (emp2): ");
scanf (" %s", &ptr2->city);

printf ("\n Display the Details of the Employee using Structure Pointer");
printf ("\n Details of the Employee (emp1) \n");
printf(" Name: %s\n", ptr1->name);
printf(" Id: %d\n", ptr1->id);
printf(" Age: %d\n", ptr1->age);
printf(" Gender: %s\n", ptr1->gender);

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

printf(" City: %s\n", ptr1->city);

printf ("\n Details of the Employee (emp2) \n");

printf(" Name: %s\n", ptr2->name);
printf(" Id: %d\n", ptr2->id);
printf(" Age: %d\n", ptr2->age);
printf(" Gender: %s\n", ptr2->gender);
printf(" City: %s\n", ptr2->city);

STRUCTURES AND FUNCTIONS

The C Programming allows us to pass the structures as the function parameters.
We can pass the C structures to functions in 3 ways
1. Passing each item of the structure as a function argument. It is similar to passing normal
values as arguments. Although it is easy to implement, we don‟t use this approach
because if the size of a structure is a bit larger, then our life becomes miserable.
2. Pass the whole structure as a value.
3. We can also Pass the address of the structure (pass by reference).

Example
#include <stdio.h>
struct student {
char name[50];
int age;
};
void display(struct student s); // function prototype
int main()
{
struct student s1;
printf("Enter name: ");
scanf("%c", s1.name);
printf("Enter age: ");
scanf("%d", &s1.age);
display(s1); // passing struct as an argument
}

void display(struct student s)

{
printf("\nDisplaying information\n");
printf("Name: %s", s.name);
printf("\nAge: %d", s.age);
}

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

TYPEDEF

The typedef is a keyword used in C programming to provide some meaningful names to the
already existing variable in the C program. It behaves similarly as we define the alias for the
commands. In short, we can say that this keyword is used to redefine the name of an already
existing variable.
Syntax:
typedef <existing name> <alias name>
Example:
typedef int unit;
In the above statements, we have declared the unit variable of type int by using a
typedef keyword.
int main()
{
typedef int unit;
unit i,j;
i=10;
j=20;
printf("Value of i & j is :%d %d",i,j);}

BIT FIELDS

In C, we can specify the size (in bits) of the structure and union members. The idea of bit-field
is to use memory efficiently when we know that the value of a field or group of fields will
never exceed a limit or is within a small range. Bit fields are used when the storage of our
program is limited. Need of bit fields in C programming language:
 Reduces memory consumption.
 To make our program more efficient and flexible.
 Easy to Implement.
Declaring Bit Fields
Variables that are defined using a predefined width or size are called bit fields. This bit field
can leave more than a single bit.
struct {
data - type[nameofmember]: width_of_Bit - field;
};
data-type: defines the data type which establishes how a bit-field's value will be represented and
interpreted. The data type can be of simple integer, signed integer, or unsigned integer.

nameofmember: defines the name of the bit-field member within the structure

width_of_Bit-field: specifies the number of bits required in the bit-field. It is to be noted that the
width of the bit-field should have to be lesser than or at least equal to the width of the specified
type.

struct example_bitField

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

{
int val1;
int val2;
};
struct example_bitField2
{
int val1: 1;
int val2: 1;
};
int main(void)
{
printf("memory engaged by example_bitField : %zu ", sizeof(struct example_bitField)); //8
printf("memory engaged by example_bitField2: %zu ", sizeof(example_bitField2));//4
}

ENUMERATED DATA TYPE

The enum in C is also known as the enumerated type. It is a user-defined data type that
consists of integer values, and it provides meaningful names to these values. The enum is
defined by using the enum keyword.

Syntax:
enum flag{integer_const1, integer_const2,.....integter_constN};

Program
#include <stdio.h>
enum weekdays{Sunday=1, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday};
int main()
{
enum weekdays w; // variable declaration of weekdays type
w=Monday; // assigning value of Monday to w.
printf("The value of w is %d",w);
}

UNION

 A union is a special data type available in C that allows to store different data types in the
same memory location.
 To define a union with many members, but only one member can contain a value at any
given time. Unions provide an efficient way of using the same memory location for
multiple-purpose.
 In union, members will share the memory location. If we try to make changes in any of the
member then it will be reflected to the other member as well.

union abc
{

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

int a;
char b;
}var;
int main()
{
var.a = 66;
printf("\n a = %d", var.a);
printf("\n b = %d", var.b);
}
In the above code, union has two members, i.e., 'a' and 'b'. The 'var' is a variable of union
abc type. In the main() method, we assign the 66 to 'a' variable, so var.a will print 66 on the
screen. Since both 'a' and 'b' share the memory location, var.b will print 'B' (ascii code of 66).

UNION OF STRUCTURES
 A structure can be nested inside a union and it is called union of structures.
 It is possible to create a union inside a structure.
Example:
struct x
{
int a;
float b;
};
union z{
struct x s;
};
main ( ){
union z u;
u.s.a = 10;
u.s.b = 30.5;
printf("a=%d \n", u.s.a);
printf("b=%f", u.s.b);
}

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

UNIT-IV
DATA STRUCTURES
OVERVIEW OF THE DATA STRUCTURE
The data structure name indicates itself that organizing the data in memory. There are many
ways of organizing the data in the memory as we have already seen one of the data structures,
i.e., array in C language.

TYPES OF DATA STRUCTURES

Linear Data Structures

A data structure is called linear if all of its elements are arranged in the linear order. In linear
data structures, the elements are stored in non-hierarchical way where each element has the
successors and predecessors except the first and last element.
Linear data structures are:
1. Arrays
2. Stacks
3. Queues
4. Linked List

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

Non Linear Data Structures

This data structure does not form a sequence i.e. each item or element is connected with two or
more other items in a non-linear arrangement. The data elements are not arranged in sequential
structure.
Non Linear data structures are:
1. Trees
2. Graphs

STACK

Introduction

A stack is an Abstract Data Type (ADT), commonly used in most programming languages. It is
named stack as it behaves like a real-world stack, for example – a deck of cards or a pile of plates,
etc.
A real-world stack allows operations at one end only. For example, we can place or remove a
card or plate from the top of the stack only.

Stack ADT allows all data operations at one end only. At any given time, we can only access the
top element of a stack.
This feature makes it LIFO data structure. LIFO stands for Last-in-first-out. Here, the element
which is placed (inserted or added) last, is accessed first. In stack terminology, insertion
operation is called PUSH operation and removal operation is called POP operation.
Definition

 A stack is a linear data structure, collection of items of the same type.

 Stack follows the Last In First Out (LIFO) fashion wherein the last element entered is the
first one to be popped out.

Stack Representation

A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack can
either be a fixed size one or it may have a sense of dynamic resizing.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

Operations on Stack

Stack operations may involve initializing the stack, using it and then de-initializing it. Apart
from these basic stuffs, a stack is used for the following two primary operations −
 push() − Pushing (storing) an element on the stack.
 pop() − Removing (accessing) an element from the stack.

Push Operation
The process of putting a new data element onto stack is known as a Push Operation. Push
operation involves a series of steps −
 Step 1 − Checks if the stack is full.
 Step 2 − If the stack is full, produces an error and exit.
 Step 3 − If the stack is not full, increments top to point next empty space.
 Step 4 − Adds data element to the stack location, where top is pointing.
 Step 5 − Returns success.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

void push(int data) {

if(!isFull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
}
}

Pop Operation
Accessing the content while removing it from the stack, is known as a Pop Operation. In
an array implementation of pop() operation, the data element is not actually removed,
instead top is decremented to a lower position in the stack to point to the next value. But in
linked-list implementation, pop() actually removes data element and deallocates memory space.

A Pop operation may involve the following steps −

 Step 1 − Checks if the stack is empty.
 Step 2 − If the stack is empty, produces an error and exit.
 Step 3 − If the stack is not empty, accesses the data element at which top is pointing.
 Step 4 − Decreases the value of top by 1.
 Step 5 − Returns success.

int pop(int data) {

if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
} else {
printf("Could not retrieve data, Stack is empty.\n");
}
}

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

APPLICATIONS OF STACK
o Evaluation of Arithmetic Expressions
o Backtracking
o Delimiter Checking
o Reverse a Data
o Processing Function Calls
Evaluation of Arithmetic Expressions
A stack is a very effective data structure for evaluating arithmetic expressions in programming
languages. An arithmetic expression consists of operands and operators.

Notations for Arithmetic Expression

There are three notations to represent an arithmetic expression:
o Infix Notation
o Prefix Notation
o Postfix Notation
Infix Notation
The infix notation is a convenient way of writing an expression in which each operator is
placed between the operands. Infix expressions can be parenthesized or unparenthesized
depending upon the problem requirement.
Example: A + B, (C - D)
All these expressions are in infix notation because the operator comes between the operands.
Prefix Notation
The prefix notation places the operator before the operands. This notation was introduced
by the Polish mathematician and hence often referred to as polish notation.
Example: + A B, -CD etc.
All these expressions are in prefix notation because the operator comes before the operands.
Postfix Notation
The postfix notation places the operator after the operands. This notation is just the
reverse of Polish notation and also known as Reverse Polish notation.
Example: AB +, CD+, etc.
All these expressions are in postfix notation because the operator comes after the operands.

QUEUES

Introduction

A queue is a useful data structure in programming. It is similar to the ticket queue outside
a cinema hall, where the first person entering the queue is the first person who gets the ticket.

The order is First In First Out (FIFO). One can imagine a queue as a line of people waiting
to receive something in sequential order which starts from the beginning of the line. It is an
ordered list in which insertions are done at one end which is known as the rear and deletions are
done from the other end known as the front. A good example of a queue is any queue of
consumers for a resource where the consumer that came first is served first.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

Definition

A queue is a linear data structure that follows the FIFO (First In First Out) principle in
deletion and insertion operations. That means the item that was inserted first should be removed
first.

Representation of Queues

There are two ways of implementing the Queue:

 Queue Implementation using an array
 Queue Implementation using Linked list
 We will have to maintain two pointers that are used to track the FRONT and REAR end.
 FRONT is used to track the first element of the queue. REAR is used to track the last
element of the queue. Initially, set the value of FRONT and REAR to -1.
Operations on Queue
 Enqueue
 Dequeue
Enqueue
This method is used to add the element to the queue. As we have two ends (Front end, Rear end)
in the queue, this addition will happen at the Rear end.
1. First, check whether the Queue is Full or not.
2. If it is full, then we cannot add the new element to it. This is overflow. So exit.
3. If it is not full, and if this is the very first element, make the FRONT to 0.
4. The increase the REAR index by 1.
5. Finally, add the new element in the position pointed to by REAR.
Dequeue
This method is used to remove the element from the queue. As we have two ends
(Front end, Rear end) in the queue, this removal will happen at the Front end.
1. First, check whether the Queue is empty or not.
2. If that is empty, we cannot remove the element as no elements are present. So exit from
there.
3. If it is not empty, then return the value which is pointing to FRONT.
4. Increment the FRONT.
Sample Program
#include<stdio.h>
void insert();
void delete();
void display();

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

int queue_array[MAX];
int rear = - 1;
int front = - 1;
main()
{
int choice;
while (1)
{
printf("1.Insert element to queue \n");
printf("2.Delete element from queue \n");
printf("3.Display all elements of queue \n");
printf("4.Quit \n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1: insert(); break;
case 2: delete(); break;
case 3: display(); break;
case 4: exit(1);
default: printf("Wrong choice \n");
} /* End of switch */
} /* End of while */
} /* End of main() */
void insert()
{
int add_item;
if (rear == MAX - 1)
printf("Queue Overflow \n");
else
{
if (front == - 1)
/*If queue is initially empty */
front = 0;
printf("Inset the element in queue : ");
scanf("%d", &add_item);
rear = rear + 1;
queue_array[rear] = add_item;
}
} /* End of insert() */
void delete()
{
if (front == - 1 || front > rear)
{

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

printf("Queue Underflow \n");

return ;
}
else
{
printf("Element deleted from queue is : %d\n", queue_array[front]);
front = front + 1;
}
} /* End of delete() */
void display()
{
int i;
if (front == - 1)
printf("Queue is empty \n");
else
{
printf("Queue is : \n");
for (i = front; i <= rear; i++)
printf("%d ", queue_array[i]);
printf("\n");
}
} /* End of display() */
VARIOUS QUEUE STRUCTURES
A queue is a useful data structure in programming. It is similar to the ticket queue outside
a cinema hall, where the first person entering the queue is the first person who gets the ticket.
There are four different types of queues:
 Simple Queue
 Circular Queue
 Priority Queue
 Double Ended Queue
Simple Queue
In a simple queue, insertion takes place at the rear and removal occurs at the front. It

strictly follows the FIFO (First in First out) rule.

Circular Queue
In a circular queue, the last element points to the first element making a circular link.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

The main advantage of a circular queue over a simple queue is better memory utilization.
If the last position is full and the first position is empty, we can insert an element in the first
position. This action is not possible in a simple queue.

Priority Queue
A priority queue is a special type of queue in which each element is associated with a
priority and is served according to its priority. If elements with the same priority occur, they are

served according to their order in the queue.

Deque (Double Ended Queue)

In a double ended queue, insertion and removal of elements can be performed from either
from the front or rear. Thus, it does not follow the FIFO (First In First Out) rule.

APPLICATIONS OF QUEUES

1. Implementation of a queue is also an important application of data structure. Nowadays

computer handles multiuser, multiprogramming environment and time-sharing environment.
In this environment a system (computer) handles several jobs at a time, to handle these jobs
the concept of a queue is used.
2. To implement printer spooler so that jobs can be printed in the order of their arrival.
3. Round robin scheduling technique is implemented using queue
4. All types of customer service (like railway reservation) centers are designed using the concept
of queues.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

LINKED LIST
 Linked List is a very commonly used linear data structure which consists of group
of nodes in a sequence.
 Each node holds its own data and the address of the next node hence forming a chain like
structure.
 A Node in a linked list holds the data value and the pointer which points to the location of
the next node in the linked list.

 Linked Lists are used to create trees and graphs

Types of Linked Lists

There are 3 different implementations of Linked List available, they are:
1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List

SINGLY LINKED LIST

Singly linked lists contain nodes which have a data part as well as an address part i.e. next,
which points to the next node in the sequence of nodes.

The operations we can perform on singly linked lists are insertion, deletion and traversal.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

Insertion at the Beginning

Steps to insert a Node at beginning :

1. The first Node is the Head for any Linked List.
2. When a new Linked List is instantiated, it just has the Head, which is Null.
3. Else, the Head holds the pointer to the first Node of the List.
4. When we want to add any Node at the front, we must make the head point to it.
5. And the Next pointer of the newly added Node, must point to the previous Head, whether
it be NULL(in case of new List) or the pointer to the first Node of the List.
6. The previous Head Node is now the second Node of Linked List, because the new Node is
added at the front.
int LinkedList :: addAtFront(node *n) {
int i = 0; //making the next of the new Node point to Head
n->next = head; //making the new Node as Head
head = n;
i++;
//returning the position where Node is added
return i;
}
Inserting at the End
Steps to insert a Node at the end:

1. If the Linked List is empty then we simply, add the new Node as the Head of the Linked
List.
2. If the Linked List is not empty then we find the last node, and make it' next to the new
Node, hence making the new node the last Node.

int LinkedList :: addAtEnd(node *n) {

//If list is empty
if(head == NULL) {
//making the new Node as Head
head = n;
//making the next pointe of the new Node as Null
n->next = NULL;
}
else {
//getting the last node
node *n2 = getLastNode();
n2->next = n;
}
}

node* LinkedList :: getLastNode() {

//creating a pointer pointing to Head

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

node* ptr = head;

//Iterating over the list till the node whose Next pointer points to null
//Return that node, because that will be the last node.
while(ptr->next!=NULL) {
//if Next is not Null, take the pointer one step forward
ptr = ptr->next;
}
return ptr;
}

CIRCULAR LINKED LIST

In circular linked list the last node of the list holds the address of the first node hence forming a
circular chain.

Circular Linked List is little more complicated linked data structure. In the circular linked list we
can insert elements anywhere in the list whereas in the array we cannot insert element anywhere
in the list because it is in the contiguous memory. In the circular linked list the previous element
stores the address of the next element and the last element stores the address of the starting
element. The elements points to each other in a circular way which forms a circular chain. The
circular linked list has a dynamic size which means the memory can be allocated when it is
required.

DOUBLY LINKED LIST

In a doubly linked list, each node contains a data part and two addresses, one for

the previous node and one for the next node.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

UNIT-V
SEARCHING & SORTINGS
INTRODUCTION
Searching is an operation or a technique that helps finds the place of a given element or
value in the list.
Any search is said to be successful or unsuccessful depending upon whether the element
that is being searched is found or not.
Some of the standard searching technique that is being followed in data structure is listed
below:
1. Linear Search
2. Binary Search
LINEAR SEARCH
Linear search is a very basic and simple search algorithm. In Linear search, we search an
element or value in a given array by traversing the array from the starting, till the desired
element or value is found. It compares the element to be searched with all the elements present in
the array and when the element is matched successfully, it returns the index of the element in the
array, else it return -1. Linear Search is applied on unsorted or unordered lists, when there are
fewer elements in a list.

Algorithm
Linear Search (Array A, Value x)
Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit
Pseudo code procedure
linear_search (list, value)
for each item in the list
if match item == value
return the item‟s location
end if
end for
end procedure
BINARY SEARCH
Binary Search is used with sorted array or list. In binary search, we follow the following steps:
1. We start by comparing the element to be searched with the element in the middle of the
list/array.
2. If we get a match, we return the index of the middle element.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

3. If we do not get a match, we check whether the element to be searched is less or greater
than in value than the middle element.
4. If the element/number to be searched is greater in value than the middle number, then
we pick the elements on the right side of the middle element(as the list/array is sorted,
hence on the right, we will have all the numbers greater than the middle number), and
start again from the step 1.
5. If the element/number to be searched is lesser in value than the middle number, then we
pick the elements on the left side of the middle element, and start again from the step 1.

Binary Search is useful when there are large number of elements in an array and they are
sorted. So a necessary condition for Binary search to work is that the list/array should be sorted.

For a binary search to work, it is mandatory for the target array to be sorted. We shall
learn the process of binary search with a pictorial example. The following is our sorted array and
let us assume that we need to search the location of value 31 using binary search.
10 14 19 26 27 31 33 35 42 44
0 1 2 3 4 5 6 7 8 9

First, we shall determine half of the array by using this formula -

mid = low + (high - low) / 2
Here it is, 0 + (9 - 0 ) / 2 = 4 (integer value of 4.5). So, 4 is the mid of the array.

10 14 19 26 27 31 33 35 42 44

0 1 2 3 4 5 6 7 8 9
Now we compare the value stored at location 4, with the value being searched, i.e. 31.
We find that the value at location 4 is 27, which is not a match. As the value is greater than 27
and we have a sorted array, so we also know that the target value must be in the upper portion
of the array.

10 14 19 26 27 31 33 35 42 44

0 1 2 3 4 5 6 7 8 9

We change our low to mid + 1 and find the new mid value again.
low = mid + 1
mid = low + (high - low) / 2
Our new mid is 7 now. We compare the value stored at location 7 with our
target value 31

10 14 19 26 27 31 33 35 42 44
0 1 2 3 4 5 6 7 8 9
The value stored at location 7 is not a match, rather it is more than what we are looking
for. So, the value must be in the lower part from this location.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

10 14 19 26 27 31 33 35 42 44

0 1 2 3 4 5 6 7 8 9

Hence, we calculate the mid again. This time it is 5.

10 14 19 26 27 31 33 35 42 44

0 1 2 3 4 5 6 7 8 9
We compare the value stored at location 5 with our target value. We find that it is a
match.

10 14 19 26 27 31 33 35 42 44
0 1 2 3 4 5 6 7 8 9

We conclude that the target value 31 is stored at location 5.

Binary search halves the searchable items and thus reduces the count of comparisons to
be made to very less numbers.
Procedure binary_search
A ! sorted array
n ! size of array
x ! value to be searched
Set lowerBound = 1
Set upperBound = n
while x not found
if upperBound < lowerBound
EXIT: x does not exists.
set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
if A[midPoint] < x
set lowerBound = midPoint + 1
if A[midPoint] > x
set upperBound = midPoint - 1
if A[midPoint] = x
EXIT: x found at location midPoint
end while
end procedure

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

SORTING
A sorting algorithm is an algorithm that puts elements of a list in a certain order. The
most used orders are numerical order and lexicographical order.
EXECHANGE SORT
The bubble/exchange sort makes multiple passes through a list. It compares
adjacent items and exchanges those that are out of order. Each pass through the list places the
next largest value in its proper place. In essence, each item “bubbles” up to the location where
it belongs.
Program for bubble sort:
def bubbleSort(alist):
for passnum in range(len(alist)-1,0,-1):
for i in range(passnum):
if alist[i]>alist[i+1]:
temp = alist[i]
alist[i] = alist[i+1]
alist[i+1] = temp
alist = [54,26,93,17,77,31,44,55,20]
bubbleSort(alist)
print(alist)

INSERTION SORT
Insertion sorts works by taking elements from the list one by one and inserting them in
their current position into a new sorted list. Insertion sort consists of N - 1 passes, where N is the
number of elements to be sorted
void Insertion_Sort (int a[ ], int n)
{
int i, j, temp ;
for (i = 0; i < n ; i++)
{
temp = a[i] ;
for (j = i ; j>0 && a[j-1] > temp ; j--)
{
a[j] = a[ j - 1] ;
}
a[j] = temp ;
}
}
SELECTION SORT
The selection sort improves on the bubble sort by making only one exchange for
every pass through the list. In order to do this, a selection sort looks for the largest value as it
makes a pass and, after completing the pass, places it in the proper location. As with a
bubble sort, after the first pass, the largest item is in the correct place.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

#include <stdio.h>
int main()
{
int n = 10;
int a[] = {3,2,6,5,4,7,8,9,5,1};
int min;
for(int i = 0; i < n - 1; i++) {
min = i;
for(int j = i + 1; j < n; j++)
{
if(a[min] > a[j])
{
min = j;
}
}
if(min!= i)
{
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
printf("Sorted Array: ");
for(int i = 0; i < n; i++)
{
printf(" %d", a[i]);
}
}
MERGE SORT
Merge sort is similar to the quick sort algorithm as it uses the divide and conquer
approach to sort the elements. It is one of the most popular and efficient sorting algorithm. It
divides the given list into two equal halves, calls itself for the two halves and then merges the
two sorted halves. We have to define the merge() function to perform the merging.
The sub-lists are divided again and again into halves until the list cannot be divided
further. Then we combine the pair of one element lists into two-element lists, sorting them in
the process. The sorted two-element pairs is merged into the four-element lists, and so on
until we get the sorted list.

void merge(int a[], int beg, int mid, int end)

{
int i, j, k;
int n1 = mid - beg + 1;
int n2 = end - mid;

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

int LeftArray[n1], RightArray[n2]; //temporary arrays

/* copy data to temp arrays */
for (int i = 0; i < n1; i++)
LeftArray[i] = a[beg + i];
for (int j = 0; j < n2; j++)
RightArray[j] = a[mid + 1 + j];
i = 0, /* initial index of first sub-array */
j = 0; /* initial index of second sub-array */
k = beg; /* initial index of merged sub-array */
while (i < n1 && j < n2)
{
if(LeftArray[i] <= RightArray[j])
{
a[k] = LeftArray[i];
i++;
}
else
{
a[k] = RightArray[j];
j++;
}
k++;
}
while (i<n1)
{
a[k] = LeftArray[i];
i++;
k++;
}
while (j<n2)
{
a[k] = RightArray[j];
j++;
k++;
}
}
QUICK SORT
It is a divide and conquer algorithm.

Step 1 − Pick an element from an array, call it as pivot element.

Step 2 − Divide an unsorted array element into two arrays.
Step 3 − If the value less than pivot element come under first sub array, the remaining
elements

Consider an example given below, wherein

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

P is the pivot element.

L is the left pointer.
R is the right pointer.th value greater than pivot come in second sub array.

The elements are 6, 3, 7, 2, 4, 5.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

Now,

 The pivot is in fixed position.

 All the left elements are less.
 The right elements are greater than pivot.
 Now, divide the array into 2 sub arrays left part and right part.
 Take left partition apply quick sort.

Siddartha Institute of Science and Technology: Puttur

C Programming and Data Structure (20CS0501)

Now,

 The pivot is in fixed position.

 All the left elements are less and sorted
 The right elements are greater and are in sorted order.
 The final sorted list is combining two sub arrays is 2, 3, 4, 5, 6, 7

Siddartha Institute of Science and Technology: Puttur