Classification of Data Structures:

Below Diagram shows the classification of Data Structures

:

Dept. of CSE, YIT Moodbidri

Classification of Data Structures:
Data structures are broadly classified as shown below :

Primitive Data structures:

Fundamental Data types that are supported by programming
languages are called Primitive Data structures.
These Data structures are manipulated directly by machine
instructions
Examples: int,float,char,double,pointers

Dept. of CSE, YIT Moodbidri

Non- Primitive Data structures:
Data Structures that are created/constructed using primitive data
structures are called Non- Primitive Data structures.
These Data structures are not manipulated directly by machine
instructions

Dept. of CSE, YIT Moodbidri

Linear Data structures:
Linear data structures are data structures in which elements are
arranged sequentially.
These structures follow a linear order, meaning that there is a
linear relationship between the elements.
Examples of linear data structures:
Arrays, Linked Lists, Stacks and Queues

Example: Linked List

In a singly linked list, each element (node) contains data and a
reference to the next node in the sequence.

Dept. of CSE, YIT Moodbidri

Non- Linear Data structures:
Linear data structures are data structures in which elements are
not arranged sequentially.
These structures do not follow a linear order, meaning that there
is no linear relationship between the elements.
Examples of linear data structures:
Trees and Graphs

Example: Binary tree

In a binary tree, each node has at most two
children, a left child and a right child.

Dept. of CSE, YIT Moodbidri

Operations on Data Structures:
Data structure operations are the methods used to manipulate
the data in a data structure. The most common data structure
operations are:
Traversal
Insertion
Deletion
Updation
Search
Sort
Merge
Copy

Dept. of CSE, YIT Moodbidri

‍Traversal: ‍Traversal operations are used to visit each node in a
data structure in a specific order.
‍Insertion: Insertion operations add new data elements to a data
structure. You can do this at the data structure's beginning,
middle, or end.
‍Deletion: ‍Deletion operations remove data elements from a data
structure. These operations are typically performed on nodes that
are no longer needed.
Updation: updation operations are used to replace the existing
value with new value in a data structure.
Search: Search operations are used to find a specific data
element in a data structure.

Dept. of CSE, YIT Moodbidri

Sort: ‍Sort operations are used to arrange the data elements in a
data structure in a specific order. This can be done using various
sorting algorithms, such as insertion sort, bubble sort, merge sort,
and quick sort.
‍Merge: ‍Merge operations are used to combine two data
structures into one. This operation is typically used when two data
structures need to be combined into a single structure.
‍Copy: ‍Copy operations are used to create a duplicate of a data
structure.

Dept. of CSE, YIT Moodbidri

 NEED FOR DATA STRUCTURES

Computers are the electronic data processsing machines. In

order to solve a particular problem we need to know.
How to represent the data in the computer
How to access them
What are the steps to be followed to get the required output

These tasks can be achieved with the help of Data structures and
the Algorithms

Dept. of CSE, YIT Moodbidri

Questions?.....

1. Define Data Structure?.Explain the classification of Data

Structures with Example (06 Marks)
2. Define Data Structure?.Explain the various Operations that
can be
performed on Data structures (06 Marks)
3. Define Data Structures? Explain with neat schematic different
types of Data Structures with examples? What are the
primitive
operations that can be performed on Data Structures (10
Marks)
4. Define Data Structures and why do we need Data structures
(4 Dept. of CSE, YIT Moodbidri
 Review of pointers

In this we are going to learn ……….

Definition of Pointer
Pointer Declaration
Pointer Assignment/ Initialization
 Pointer Definition
Accessing Variable through Pointer
Pointer Disadvantages
Pointer and Array

Dept. of CSE, YIT Moodbidri

Pointer:
Definition : Pointer is a variable which stores the address of
another variable of same data types.
Example: Below diagram shows that pointer variable ptr holds
the address of variable called Var.

Dept. of CSE, YIT Moodbidri

Pointer Declaration:
In pointer declaration ,we only declare the pointer but do not
initialize it.

Syntax to declare pointer:

dataType * variable_name;
Example: In the below example we declare a pointer variable
called ptr.
int * ptr;

Dept. of CSE, YIT Moodbidri

Pointer Initialization:
Pointer initialization is the process where we assign some initial
value to the pointer variable. We generally use the ( & )
addressof operator to get the memory address of a variable
and then store it in the pointer variable..
Syntax to initialize pointer:
pointer_var = &(variable_name);
Example:
int var = 10;
int * ptr;
ptr = &var;

Dept. of CSE, YIT Moodbidri

Pointer Definition:
The process of initializing the pointer at the time of declaration is
called pointer definition.
Syntax for pointer definition:
dataType *pointer_var = &(variable_name);
Example:
int var = 10;
int * ptr = &var ;

Dept. of CSE, YIT Moodbidri

Accessing variable through Pointer:
We can access the value of a variable through the pointer
variable, this is done by using the unary operator * (astrisk)
usually known as indirection operator.
Example:
int var = 10, *ptr, n;
ptr = &var ;
n = *p;
In the above example in the line three * operator is placed before
the variable in the expression, the pointer returns the value of the
variable of which the pointer value is address. *p returns the
value stored in var, because p contains the address of var.

Dept. of CSE, YIT Moodbidri

 Pointer Disadvantages:
Pointer is most dangerous feature available in c when they are
not used correctly, following are the some disadvantages of
pointer.
No proper usage of pointer may cause the crashing the system.
Pointers must be initialized otherwise pointers contain the
garbage
value results in the crashing the system.
When pointers are used wrongly ,the compiler may not detect
the
errors in most cases and therefore the program is likely to
produce unexpected results.
Debugging becomes difficult task.
Dept. of CSE, YIT Moodbidri
Pointers and Arrays:
We know that base address is the location of the first element
(index 0) of the array.
The name of the array is equivalent to the address of its first
element.
Since the array name is the pointer constant to the
first element the address of the first element and the array
name both belong to a same memory location.
Example: int a[] = { 12,13,14,15,16}, *ptr;
ptr = a;
printf (“%u”, &a[0]);
printf( “%u”,a);
Above two printf statements print the address of first element of
array
Dept. of CSE, YIT Moodbidri
 Relationship between Pointers and
Arrays:
Suppose if we declare a integer pointer variable p, then we can
make the pointer variable to point to the array ‘arr’ by:
p = arr;
The relation between p and arr is:

p=&arr[0] = 1024
p+1= &arr[1] = 1028
p+2= &arr[2] = 1032
p+3=& arr[3] = 1036
p+4=& arr[4] = 1028

Dept. of CSE, YIT Moodbidri

Questions?.....

1. Define pointer? Explain how to declare and initialize pointers

with Example? (5 marks)
2. Define pointer? Explain the relation between pointer and
array with Example? (5 marks)
3. Define pointer? List the advantages of pointer over Array? (5
marks)
4. Is it possible to store the content of an array into pointer?
Justify your opinion with suitable c-statements?(8 marks)

Dept. of CSE, YIT Moodbidri

 Dynamic Memory Allocation

In this we are going to learn ……….

Dynamic memory allocation functions
Malloc()
Calloc()
Free()
Realloc()
Difference between static and dynamic
Memory
Difference between Malloc() and calloc()
Dept. of CSE, YIT Moodbidri
In C the dynamic memory allocation is supported by the following
functions
malloc(),calloc(),free(),realloc()

Dynamic memory allocation: The allocation

of memory during runtime is called
Dynamic memory allocation.

The Dynamic memory allocation takes

Place in heap.

Dept. of CSE, YIT Moodbidri

 malloc( ) function
The name "malloc" stands for memory allocation.
The malloc() function reserves a block of memory of the
specified number of bytes. And, it returns a pointer of void which
can be casted into pointers of any form.
Syntax of malloc()
ptr = (castType*) malloc(size);
Example:
ptr = (float*) malloc(100 * sizeof(float));
The above statement allocates 400 bytes of memory. It's because
the size of float is 4 bytes. And, the pointer ptr holds the address
of the first byte in the allocated memory.
The expression results in a NULL pointer if the memory cannot be
allocated.

Dept. of CSE, YIT Moodbidri

 calloc( ) function
The name "calloc" stands for contiguous allocation.
The malloc() function allocates memory and leaves the memory
uninitialized, whereas the calloc() function allocates memory and
initializes all bits to zero.

Syntax of calloc()
ptr = (castType*) calloc(n,size);

Example:
ptr = (float*) calloc(25, sizeof(float));

The above statement allocates contiguous space in memory for

25 elements of type float

Dept. of CSE, YIT Moodbidri

 free( ) function

This funtion is used to de-allocate the memory that is previously

allocated by malloc() and calloc()
free function is used to return the memory back to the memory
RAM
Syntax of free()
free(ptr);

Dept. of CSE, YIT Moodbidri

 realloc( ) function

This function is used to resize the size of memory block. Which is

already allocated.
The memory to be resized should be first allocated using
ptr = malloc(size);
Syntax of Realloc()
ptr = realloc( ptr, new_size);

Example:
ptr = realloc( ptr, 50);

Dept. of CSE, YIT Moodbidri

 Difference between Static Memory and Dynamic

Static Memory Dynamic Memory

Memory allocation is done at Memory allocation is done at run

compilation time time

Prior to allocation of memory No need to know amount of

some fixed amount of it must be memory prior to allocation
decided

Wastage of memory No Wastage of memory

Shortage of memory No Shortage of memory

Dept. of CSE, YIT Moodbidri

 Difference between malloc and calloc

Malloc calloc

The syntax of malloc is The syntax of calloc is

ptr = (dataType*)malloc(number of ptr = (dataType*)calloc(number of
elements*size of each element) elements, size of each element)

Allocates a single block o memory Allocates multiple blocks of

with the specified size in memory and each block contains
parameter equal size

Allocated memory locations are not Initializes all bytes in the allocated
initialized block to zero

Since there is no initialization then Calloc() is computationally more

time efficiency is more than the expensive because it set to zero
calloc function but it is more convenient than
malloc() function.

Dept. of CSE, YIT Moodbidri

 Example
#include <stdio.h> p1 = realloc(p1, n2);
#include <stdlib.h> for(i = 0; i < n2; ++i)
void main() printf("%d\t", *(p1 + i));
free(p1);
{
}
int *p1, i , n1, n2;
printf("Enter size of array: ");
scanf("%d", &n1);
p1 = (int*) calloc(n1 ,
sizeof(int));
printf("Enter array elements: \n");
for(i = 0; i < n1; i++)
scanf("%d",p1 + i);
printf("Array elements are:\n");
for(i = 0; i < n1; i++)
printf("%d\t",*(p1 + i));
printf("\nEnter new size of array: ");
scanf("%d", &n2);

Dept. of CSE, YIT Moodbidri

Questions?.....

1. Define Dynamic memory allocation? Explain all the functions

in c that are supported for Dynamic memory allocation with
example? (8 marks)
2. Explain any four dynamic memory allocation functions with
syntax and examples? (10 marks)
3. Write the difference between static and Dynamic memory(4
marks)
4. Write the difference between malloc ,calloc (4 marks)

Dept. of CSE, YIT Moodbidri

 Review of Arrays

In this we are going to learn ……….

Definition of an Array
Array Declaration
Array Initialization
 Modify, Input, Output Array
Accessing Array using Pointer
Array Examples
Abstract Data Type for an Array

Dept. of CSE, YIT Moodbidri

 ARRAY IN DETAIL

Definition of Array: Array is a data structure that store

elements/items of same data type.

Array Declaration: A one-dimensional array in C is declared

implicitly by appending brackets to the name of a variable. For
Example: int list [5], *plist[5];

The first array defines five integers, while the second defines
five pointers to integers.
In C all arrays start at index 0, so list[0], list[l], list[2], list[3], and
list[4] are the names of the five array elements, each of which
contains an integer value.
 ARRAY IN DETAIL

Similarly, plist[0], plist[1], plist[2], plist[3], and plist[4] are the

names of five array elements, each of which contains a pointer to
an integer.

Address of Array Elements: When we declare one dimensional

array as int list[5];
If the address of the first element list[0], is called the base
address. If the size of an integer on your machine is denoted by
sizeof(int), then we get the following memory addresses for the
five elements of list[] as:
Below is an Example how address of array elements is calculated
ARRAY DECLARATION
ACCESSING ARRAY ELEMENTS
INITIALIZE ARRAY
MODIFY, INPUT and OUTPUT ARRAY ELEMENTS
ARRAY EXAMPLE
ARRAY EXAMPLE
ACCESSING ARRAY USING POINTERS
 ABSTRACT DATA TYPE FOR ARRAY

An ADT of Array provides the details of Array Implementation and

the various operations that can be performed on Array
The Create(j, list) function produces a new, empty array of
the appropriate size. All of the items are initially undefined.
 Retrieve accepts an array and an index. It returns the value
associated with the index if the index is valid, or an error if the
index is invalid.
Store accepts an array, an index, and an item, and returns the
original array augmented with the new <index, value> pair.
Questions?.....
1. Define Array? Explain how do you declare and initialize one-
Dimensional Array with an example (8 marks)
2. Write a program in C to search an element using linear
search?(6 Marks)
3. Write a program to insert an element into 1-d Array at
specified index( 6 marks)
4. Write a program to delete an element into 1-d Array at
specified index( 6 marks)
5. Define 1-D Array? Write and Explain the ADT for Array ( 6
Marks)

Dept. of CSE, YIT Moodbidri

 DYNAMICLLAY ALLOCTED ARRAYS

In this we are going to learn ……….

One-dimensional Array
Two-dimensional Array

Dept. of CSE, YIT Moodbidri

Disadvantages of static allocated
memory:
Array is Static Structure ( Array is of fixed size)
The number of elements/items to be stored should be known
well
in advance.
You cannot increase the size of array during execution if you
need
more space.
You cannot decrease the size of an array during execution if you
need less memory than what is declared.

Dept. of CSE, YIT Moodbidri

 One Dimensional Dynamic Allocated Array

Creating a one-dimensional array using dynamic allocation

involves the use of pointers and memory allocation functions.

The most common functions for memory allocation in C are

malloc and calloc

Allocating memory using malloc

Allocating memory using calloc

Dept. of CSE, YIT Moodbidri

 Dynamic Allocation using malloc
Dynamic allocation using malloc (memory allocation) allows you
to allocate memory during the runtime of the program.
Using malloc, you can create a block of memory for storing
elements in an array.
To allocate memory for an array, follow these steps:
Declare a pointer that will point to the first element of the 1D
array
Use malloc to allocate memory for the desired number of
elements
Assign the address of the memory block returned by malloc to
the pointer
Access and manipulate the elements in the array using the
pointer
Dept. of CSE, YIT Moodbidri
 Example using malloc
#include <stdio.h>
#include<stdlib.h>
void main()
{
int n, i, *ptr;
printf("Enter the number of elements: ");
scanf("%d", &n);
ptr = (int*) malloc(n * sizeof(int));
if (ptr == NULL)
{
printf("Memory allocation failed!");
return -1;
}
printf("Enter %d Elements: ", n);
for (i = 0; i < n; i++)
{
scanf("%d", (ptr+i));
}

Dept. of CSE, YIT Moodbidri

 Example
printf(“ The %d Elements are: ", n);
for (i = 0; i < n; i++)
{
printf("%d", *(ptr +i));
}
free(ptr);
}

Output:

Enter the number of elements: 4

Enter 4 Elements: 12 23 45 34
Array elements: 12 23 45 34

Dept. of CSE, YIT Moodbidri

 Example using Calloc
#include <stdio.h>
#include<stdlib.h>
void main()
{
int n, i, *ptr;
printf("Enter the number of elements: ");
scanf("%d", &n);
ptr = (int*) calloc(n, sizeof(int));
if (ptr == NULL)
{
printf("Memory allocation failed!");
return -1;
}
printf("Enter %d Elements: ", n);
for (i = 0; i < n; i++)
{
scanf("%d", (ptr+i));
}

Dept. of CSE, YIT Moodbidri

 Example
printf(“ The Elements: ", n);
for (i = 0; i < n; i++)
{
printf("%d", *(ptr +i));
}
free(ptr);
}

Output:

Enter the number of elements: 4

Enter 4 Elements: 12 23 45 34
Array elements: 12 23 45 34

Dept. of CSE, YIT Moodbidri

 Two Dimensional Dynamic Allocated Array

Dynamic allocation of a two-dimensional array involves

allocating memory for both rows and columns.

Here are the steps to allocate memory for a 2D array:

Declare a pointer to a pointer for holding the base address of
the
2D array
Allocate memory for the rows using malloc
For each row, allocate memory for the columns using malloc
Assign the addresses to the row pointers

Allocating memory using malloc

Allocating memory using calloc
Dept. of CSE, YIT Moodbidri
 2D Array Example using malloc

#include <stdio.h>
#include<stdlib.h>
void main()
{
int **array;
int rows, cols, i, j;
printf("Enter the number of rows: ");
scanf("%d", &rows);
printf("Enter the number of columns: ");
scanf("%d", &cols);
array = (int**) malloc(rows * sizeof(int*)); // Allocate memory
for rows

Dept. of CSE, YIT Moodbidri

if (array == NULL)
{
printf("Memory allocation failed!");
return -1;
}
for (i = 0; i < rows; i++)
{
array[i] = (int*) malloc(cols * sizeof(int));
if (array[i] == NULL)
{
printf("Memory allocation failed!"); return -1;
}
}
Dept. of CSE, YIT Moodbidri
printf("Enter the elements of the 2D array:\n");
for (i = 0; i < rows; i++)
{
for (j = 0; j < cols; j++)
{
scanf("%d", &array[i][j]);
}
}
printf("2D array elements:\n");
for (i = 0; i < rows; i++) {
for (j = 0; j < cols; j++) {
printf("%d ", array[i][j]);
}
printf("\n");
}
free(array);

Dept. of CSE, YIT Moodbidri

 STRUCTURES AND UNIONS

In this we are going to learn ……….

Definition of structure
Declare/Define Structure
Declare Structure Variable
Assign values to members of structure
Create own structures using typedef
Structures and Arrays
Structures and Pointers
Union
Difference between Structure and union

Dept. of CSE, YIT Moodbidri

 STRUCTURES NEED

Need for structures:

At times, during programming, there is a need to store multiple

logically related elements under one roof.

For instance, an employee’s details like name, employee

number, and designation need to be stored together. In such
cases, structures do the job for us.

Dept. of CSE, YIT Moodbidri

 DEFINITION OF STRUCTURES & DECLARATION

Define Structures: Structure is a collection of variables of

different data types.
Structure is a collection of variables of different data type
under a single name.

Structure Declaration: Before we create structure

variables, we should need to define its data type. To define a
structure, the struct keyword is used.

Dept. of CSE, YIT Moodbidri

EXAMPLES STRUCTURES

Dept. of CSE, YIT Moodbidri

 STRUCTURES VARIABLES

Declare Structures Variables: when the structure is

declared the compiler will not allocate the memory. To allocate
memory of a given structure type and work with it, we need to
create variables.

There are two ways to create a structure variables

1. Declare the structure variables along structure definition.

2. Declare the structure variables after structure definition

Dept. of CSE, YIT Moodbidri

Declare Structures Variables along with
structure Definition: We can declare the structure
variables along with the definition of the structure .
Synatx: Example:
struct structure_name struct Student
{ {
dataType member1; int rollNo;
dataType member2; char name[30];
.. int sem;
dataType memberN; float marks;
} var1,vr2,……,VarN; } S1,S2;

Dept. of CSE, YIT Moodbidri

Declare Structures Variables after structure
Definition: We can declare the structure variables after
definition of the structure or in main function .
Synatx: Example:
struct structure_name struct Student
{ {
dataType member1; int rollNo;
dataType member2; char name[30];
.. int sem;
dataType memberN; float marks;
}; };
struct structure_name var1,var2; struct Student S1,S2;

Dept. of CSE, YIT Moodbidri

Assigning values to structure members/ structure
initialization
Structure Initialization:
It is not possible to assign the values to the members of the
structure during the structure definition because when a structure
is defined, no memory is allocated to the structure’s data
members at this point. Memory is only allocated when a structure
variable is declared. Consider the following code snippet.
struct Student
{
int rollNo=10; //COMPILER ERROR: cannot initialize
members
char name[30]= “Anand”;
int sem=4;
};
Dept. of CSE, YIT Moodbidri
 Defining Own structure using typedef

We can create a new data type for the exisiting data type using
the keyword struct and typedef .

Syntax: Example:
typedef struct structure_name typedef struct Student
{ {[
datatype member1; int rollNo;
datatype member2; char name[20];
…… int sem;
datatype memberN float marks;
}; }Engg,Med;
structure_name var1,var2; Engg e1, Med m1;

Dept. of CSE, YIT Moodbidri

Example of structure using typedef

Dept. of CSE, YIT Moodbidri

 Accessing structure members
The members of a structure are accessed outside the structure by
the structure variables using the dot operator (.).
The following syntax is used to access any member of a structure
by its variable:
Syntax:
structure_variable . Member;

Dept. of CSE, YIT Moodbidri

 Structures and Array
Array of Structures: Consider a Scenario
Suppose you need to store the details of students like name,
class, and roll number in your database.
We create a structure variable and access the student
details. This method is practical for a few students only, but what
if the total number of students is 100 or something. It is not
convenient to create 100 separate structure variables for 100
students. In such cases, we use an array of structures.

we can also declare an array of structures. An array of structures

acts similar to a normal array. Just like other datatype (Primitive)

Dept. of CSE, YIT Moodbidri

Example: Array of Structure

Dept. of CSE, YIT Moodbidri

 Structures and Pointers
Structures and Pointers: A structure pointer is defined as the
pointer which points to the address of the memory block that
stores a structure known as the structure pointer.

Accessing the structure members using pointers:

There are two ways to access the members of the structure with
the help of a structure pointer:
With the help of (*) asterisk or indirection operator and (.) dot
operator.
With the help of ( -> ) Arrow operator.

Dept. of CSE, YIT Moodbidri

Example of Structures and Pointers

Dept. of CSE, YIT Moodbidri

Example of Structures and Pointers

Dept. of CSE, YIT Moodbidri

 Union
Union: The Union is a user-defined data type in C language that
can contain elements of the different data types just like
structure. But unlike structures, all the members in the C union
are stored in the same memory location.
In union, only one member can store data at the given instance
Union Declaration: we only declare the members’ names and
data types along with the name of the union. No memory is
allocated to the union in the declaration.
Syntax: Example:
union union_name union coordinates
{ {
datatype member1; int x;
datatype member2; ... Int y;
}; };

Dept. of CSE, YIT Moodbidri

 Union
Union Variables: We can declare the variables of the union
With union definition
After union definition
Syntax with union def: Example:
union union_name union coordinates
{ {
datatype member1; int x;
datatype member2; ... Int y;
} var1,var2,…VarN; }P1,P2;
Syntax with After union def: Example:
union union_name union coordinates
{ {
datatype member1; int x;
datatype member2; ... Int y;
}; };
union var1,var2,…VarN; union P1,P2;

Dept. of CSE, YIT Moodbidri

 Union
Access union memebers: We can access the members of a
union by using the ( . ) dot operator just like structures.
Example:
var1.member1;
where var1 is the union variable and member1 is the member of
the union.

Initialization of Union in C: The initialization of a union is the

initialization of its members by simply assigning the value to it.
var1.member1 = some_value;
One important thing to note here is that only one member can
contain some value at a given instance of time.

Dept. of CSE, YIT Moodbidri

 Example Union

Dept. of CSE, YIT Moodbidri

Difference between Structure and Union

Dept. of CSE, YIT Moodbidri

Questions?.....

1. What is structure? How it is different from array? Explain

different types of structure declaration with examples and
give the difference between the structure and union? (10
marks)
2. Define structures? Explain the types of structure with
examples?(7 marks)
3. Differentiate between structure and union and show example
for each (6 marks)
4. Define union? Explain how do you declare union and
initialize , access members of union with example? (8 marks)

Dept. of CSE, YIT Moodbidri

 POLYNOMIAL

In this we are going to learn ……….

Definition of polynomial
Polynomial Representation
Program to add two poly with n terms

Dept. of CSE, YIT Moodbidri

Definition of Polynomials: polynomial is a sum of terms, where
each term has a form axe, where x is the variable, a is the
coefficient, and e is the exponent.
Two example polynomials are:

The largest exponent of a polynomial is called its degree.

 Coefficients that are zero are not displayed.

The term with exponent equal to zero does not show the

variable

since x raised toDept. of CSE,

a power YIT
of zero is Moodbidri
1.
The standard mathematical definition for sum and product
of Polynomials are:

Assume that we have two polynomials

Dept. of CSE, YIT Moodbidri

Polynomials Representation:

Representation of one variable polynomial:

Example: A Polynomial consist of one variable is shown below:
x4+10x3+2x2+1

The polynomial with one variable can be represented using

structure namely by two fields:
cf (representing coefficient)
px (power of x)

Dept. of CSE, YIT Moodbidri

The structure definition for the one variable is as shown here:
typedef struct
{
int cf; //hold the coefficient
int px; // holds the power of x
} POLY;

Dept. of CSE, YIT Moodbidri

The below structure definition show how to represent the
polynomial with more terms
typedef struct
{
int cf; //hold the coefficient
int px; // holds the power of x
} POLY;
POLY p[10];

Dept. of CSE, YIT Moodbidri

Function read and print a polynomial with n terms

Dept. of CSE, YIT Moodbidri

 Add two polynomials

If we want to add two polynomials first we need to search for the

power of polynomial 1 in polynomial 2. we can do this by linear
search.
The below function shows how to search for term poly1 in poly2.

Dept. of CSE, YIT Moodbidri

Once we know how to search for a term of polynomial 1 in
polynomial 2, the general procedure to add two polynomials is
shown below

Dept. of CSE, YIT Moodbidri

Function to copy remaining terms of polynomials

Dept. of CSE, YIT Moodbidri

Function to add two polynomials

Dept. of CSE, YIT Moodbidri

Main function to read the polynomials

Dept. of CSE, YIT Moodbidri

 Representation of two polynomials in Array

Consider the two polynomials:

A(x)= 2x1000 +1
B(x) =x4 +10x3+3x2+1
The below fig shows how the polynomials are stored in array
terms.

The index of the first term of A is given by starta

The index of the first term of B is given by startb
The index of the last term of A is given by finisha
The index of the last term of B is given by finishb
Dept. of CSE, YIT Moodbidri
The index of the next free location in the array is given by avail.
In our example :
starta=0, finisha =1, startb=2, finishb=5 and avail=6

This representation does not impose any limit on the number of

polynomials that we can place in terms. The only stipulation is
that the total number of nonzero terms must be no more than
MAX-TERMS.
Any polynomial A that has n nonzero terms has starta and
finisha such that finisha = starta + n - 1.

Dept. of CSE, YIT Moodbidri

 SPARSE MATRIX

In this we are going to learn ……….

Definition of Sparse matrix

Representation of sparse matrix as array
Transposing a matrix

Dept. of CSE, YIT Moodbidri

Definition and Example of Sparse Matrix:
As show in the below two matrix the first matrix contains all the
non zero elements where as the second matrix contains many
zero elements. So second matrix is called sparse matrix.

Sparse matrix: Matrix is said to be sparse matrix if it contains

many zero elements and few non zero elements.

Dept. of CSE, YIT Moodbidri

 disadvantage of Sparse matrix
The sparse matrix contains many zeroes. If we are manipulating
only non-zero values, then we are wasting the memory space by
storing unnecessary zero values. This disadvantage can be
overcome by storing only non-zero values thus saving the space
For example: Consider a matrix of size 1000 x 1000.
Assume it has 2000 non-zero elements and remaining are zero
elements.
The corresponding two-dimensional array occupy 1,000,000
memory locations.
Instead of storing both zero and non-zero elements, if we store
only non-zero elements, the space can be reduced.
This can be done using sparse matrix representation as shown
below:
Dept. of CSE, YIT Moodbidri
 Representation of sparse matrix as an Array

In the array representation of a sparse matrix ,only the non zero
elements are stored so, storage space can be reduced.
Each non zero elements in the matrix are represented as triplet:
<row,col,value>
For this the two dimensional array containing 3 columns can be
used.
The first column is for storing the row numbers
The second column is for storing the column numbers
The third column is for storing the value (corresponding to the
non zero element at (row,column))

Dept. of CSE, YIT Moodbidri

 Example
Consider the following sparse matrix :

The second diagram shows how this matrix is represented in the

array a.
a [0].row contains the number of rows;
a[0].col contains the number of columns
a[0].value contains the total number of nonzero entries.
Positions 1 through 8 store the triples representing the nonzero
entries.
Dept. of CSE, YIT Moodbidri
We know that any element in the matrix can be uniquely defined
using the triples<row, col, val>. Thus, a sparse matrix can be
created using the array of triples as shown below:

Dept. of CSE, YIT Moodbidri

Dept. of CSE, YIT Moodbidri
Dept. of CSE, YIT Moodbidri
 Transpose of a matrix

Transpose of a Matrix:
Definition: A matrix which is obtained by changing the row
elements into column elements and column elements into row
elements is called transpose of a matrix.
Example:
MATRIX TRANSPOSE MATRIX

Dept. of CSE, YIT Moodbidri

 STEPS TO BE FOLLOWED FOR TRANSPOSE FOR SPARSE

It is very easy and simple method to find the transpose of sparse matrix
Time complexity is O (num of col *num of non zero values)

Steps
1. Obtain the triplet form of sparse matrix
2. Inititalze currentB to 1
3. Traverse triplet matrix from second row and consider the column
element
4. Check if column number is equal to i, then swap its row and column
and add it to transpose matrix then increment currentB
5. Repeat above steps for all rows
6. Repeat step 3 and 4 for the column number values 1,2,3,4( total
number of columns)

Dept. of CSE, YIT Moodbidri

Algorithm for Transpose of a sparse matrix

Dept. of CSE, YIT Moodbidri

Transpose of a matrix

Dept. of CSE, YIT Moodbidri

 Example

Dept. of CSE, YIT Moodbidri

 STEPS TO BE FOLLOWED FOR FAST TRANSPOSE
It is very fast but little complex method to find the transpose of sparse
matrix
Time complexity is O (num of col +num of non zero values)

Steps
1. Obtain the triplet form of sparse matrix
2. Create two 1-D arrays: row_terms and starting_pos
3. Size of row_terms array is the total number of columns in the original
matrix
4. At every index of row_terms,put the number of times respective index
appear in second column of sparse matrix
5. Size of starting_pos array: size of row_terms+1
6. Assign starting_pos[0]=1 and starting_pos[i]=starting_pos[i-
1]+row_terms[i-1]
7. Now traverse the sparse matrix from second row and consider column
element
8. J = starting_pos[col_no]
9. Jth index of transpose matrix = swapped row from original matrix
10.Increase starting_pos[col_no] by 1
11.Repeat steps from 7 to 10 for the remaining triplets of original matrix

Dept. of CSE, YIT Moodbidri

ALGORITHM FOR FAST TRANSPOSE OF SPARSE MAT

Dept. of CSE, YIT Moodbidri

 Questions

1. Define sparse matrix and express the following matrix

in the triplet form and find its transpose. (10 Marks)

2. What is sparse matrix? Write the ADT for sparse

matrix? Express the following matrix in the triplet form
and find its transpose. (8 Marks)

Dept. of CSE, YIT Moodbidri

 Questions
A(x) = 3x23+3x4+4x 2
+15 and B(x) = x5+20x3+2

3. Define polynomial ?Explain with example how

A(x) = 3x23+3x4+4x2+15 and B(x) = x5+20x3+2 are
stored in
1-D Array (6 Marks)
4. Write the fast transpose algorithm to transpose the
given sparse matrix? Write the ADT for sparse matrix?
Express the following matrix in the triplet form and
find its transpose. (8 Marks)

Dept. of CSE, YIT Moodbidri

 REPRESENTATION OF MULTI DIMENSIONAL ARRAY

In this we are going to learn ……….

Representation of linear arrays in memory

Representation of Multi Dimensional arrays
Row Major Order
Column Major Order
Representation in row major order
Representation in column major order

Dept. of CSE, YIT Moodbidri

A(x) = 3x23+3x4+4x2+15 and B(+2
Representation of Linear Array in memory:

Array index in C Language starts from 0

Where as the array index in Pascal can begin from any index
(even the negative index is possible in Pascal)

Dept. of CSE, YIT Moodbidri

A(x) = 3x23+3x4+4x2+15 and B(+2
Obtaining the LOC a[j] in the array:

Consider the following array declaration in Pascal

Dept. of CSE, YIT Moodbidri

A(x) = 3x23+3x4+4x2+15 and B(+2
Calculation of X :

Dept. of CSE, YIT Moodbidri

A(x) = 3x23+3x4+4x2+15 and B(+2
Example 1:

Dept. of CSE, YIT Moodbidri

A(x) = 3x23+3x4+4x2+15 and B(+2
Example 2:

Dept. of CSE, YIT Moodbidri

A(x) = 3x23+3x4+4x2+15 and B(+2
Storage Representation of Multi Dimensional Arrays in
Memory:

Two-Dimensional: Even though we represent the array in 2

Dimensional the elements of the array are stored contiguously
one after the other.
The elements of the 2D Array can be stored either in
Row Major order
Column Major order

Dept. of CSE, YIT Moodbidri

A(x) = 3x23+3x4+4x2+15 and B(+2
Row Major Order:
In row major order ,the elements in 2D Array are stored in row by
row one row at a time.
Example:

Dept. of CSE, YIT Moodbidri

A(x) = 3x23+3x4+4x2+15 and B(+2
Column Major Order:
In column major order ,the elements in 2D Array are stored in
column by column one column at a time.
Example:

Dept. of CSE, YIT Moodbidri

A(x) = 3x23+3x4+4x2+15 and B(+2

Storage Representation of 2D in row Major Order: How to

obtain the address of a[i][j] where the elements are stored in row
major order.

Dept. of CSE, YIT Moodbidri

A(x) = 3x23+3x4+4x2+15 and B(+2

Dept. of CSE, YIT Moodbidri

A(x) = 3x23+3x4+4x2+15 and B(+2

Dept. of CSE, YIT Moodbidri

 EXAMPLE

Dept. of CSE, YIT Moodbidri

 COLUMN MAJOR ORDER

Storage Representation of 2D in Column Major Order:

How to obtain the address of a[i][j] where the elements are
stored in col major order.

Dept. of CSE, YIT Moodbidri

Dept. of CSE, YIT Moodbidri
Dept. of CSE, YIT Moodbidri
 EXAMPLE

Dept. of CSE, YIT Moodbidri

Dept. of CSE, YIT Moodbidri
 Questions

1. Explain the representation of linear arrays in memory?

Consider the
linear arrays AAA(5:50) and BBB(-5:10)
i. Find the number of each element in the array
ii. Suppose Base (AAA) =300 and (BBB)= 500 and 4
words per memory cell for AAA and 2 words per memory
cell for BBB Find address of AAA[15],AAA[55], BBB[8]
and BBB[0] (08 Marks)

Dept. of CSE, YIT Moodbidri

 STACK

In this we are going to learn ……….

Definition of Stack
Operations Performed on Stack
Applications of Stack
Stack using Dynamic Array
Evaluation of Expression
Expression
Evaluating Postfix Expression
Converting infix to Postfix

Dept. of CSE, YIT Moodbidri

 STACK

Definition:

Dept. of CSE, YIT Moodbidri

OPERATIONS PERFORMED ON STACK

Dept. of CSE, YIT Moodbidri

Function to Insert/ Push item into stack using global varibles

Dept. of CSE, YIT Moodbidri

Function to Insert/ Push item into stack using parameters

Dept. of CSE, YIT Moodbidri

 POP OPERATION

Dept. of CSE, YIT Moodbidri

C Function to pop an item from stack using parameter passing

Dept. of CSE, YIT Moodbidri

C Function to Display all items using parameter passing

Dept. of CSE, YIT Moodbidri

 Applications of Stack

Dept. of CSE, YIT Moodbidri

 Evaluating Expression
What is an Expression and what are the types of expressions?

Dept. of CSE, YIT Moodbidri

 Infix Postfix and Prefix Expression
What is an Infix Expression

What is an Postfix Expression

Dept. of CSE, YIT Moodbidri

 Infix Postfix and Prefix Expression
What is an Prefix Expression

Dept. of CSE, YIT Moodbidri

Operator Precedence and Associativity

Dept. of CSE, YIT Moodbidri

Convert Infix expression to Postfix Expression

Dept. of CSE, YIT Moodbidri

Convert Infix expression to Postfix Expression

Dept. of CSE, YIT Moodbidri

Dept. of CSE, YIT Moodbidri
Convert Infix to Prefix Expression

Dept. of CSE, YIT Moodbidri

Convert Infix to Prefix Expression

Dept. of CSE, YIT Moodbidri

 Alg to Convert Infix to Postfix Expression using stack Method

Algorithm:
1. Scan the infix expression from left to right
2. If scanned character is operand then push it into postfix expression.
3. If the scanned character is operator then push it on to the stack.
4. If the scanned operator is greater than stacked operator then the
scanned operator is pushed into the stack.
5. If the scanned operator is less than or same than stacked operator
then the stacked operator will be popped out from stack and pushed
into postfix expression and scanned operator is pushed into the stack.
6. If the scanned operator is right parenthesis then till left parenthesis of
stack all operators from stack are popped and put into postfix
expression and cancel the parenthesis.
7. Repeat steps from 1 to 6 until end of expression.

Dept. of CSE, YIT Moodbidri

Convert Infix to Postfix using stack

Dept. of CSE, YIT Moodbidri

Convert Infix to Postfix using stack

Dept. of CSE, YIT Moodbidri

 Alg to Evaluate postix expression using stack Method

Algorithm:
1. Scan the postfix expression from left to right
2. If scanned character is operand then push it into stack.
3. If the scanned character is operator then pop top two operands from
the stack perform the operation and later push result back into the
stack.
4. Repeat steps from 1 to 3 until end of expression.

Dept. of CSE, YIT Moodbidri

Evaluate the given Postfix Expression using stack

Dept. of CSE, YIT Moodbidri

Evaluate the given Postfix Expression using stack

Dept. of CSE, YIT Moodbidri

Algorithm to Convert Infix to Prefix Expression using stack Method
Algorithm:
1. Reverse the input expression or start from right to left of infix
expression
2. Examine the next element in the input
3. If the scanned character is operand then add it to output string/Prefix
exp.
4. If it is closing parenthesis then push it into the stack.
5. If it is an operator then:
i. if stack is empty then push operator on to stack.
ii. If the top of stack is closing paranthesis.push operator on stack.
iii. if it has same or higher priority then the top of stack, push operator

on stack.
iv. Else pop the operator from the stack and add it to output
string,repeat step 5.
Dept. of,pop
6. If it is opening paranthesis CSE, YIT Moodbidri
opertor from stack and add them to
Algorithm to Convert Infix to Prefix Expression using stack Method
7. If there is more input go to step 2.
8. If there is no more input then unstack remaining operators and add
them to output string.
9. Reverse the output string.

Dept. of CSE, YIT Moodbidri

Convert Given Infix to Prefix Expression using stack Method

Dept. of CSE, YIT Moodbidri

Convert Given Infix to Prefix Expression using stack Method

Dept. of CSE, YIT Moodbidri

 Questions

1. Define stack? Explain different types of operations that

can
be performed using suitable c Functions and Examples?
[7 Marks]
2. Convert the following infix expression into postfix
expression using stack
i. A+(B*C-(D/E^F)*G)*H
ii. ((H*((((A+((B+C)*D))*F)*G)*E))+J)
iii. (a+b)*d+e/(f+a*d)+c
iv. ((a/(b-c+d))*(e-a)*c)
v. A$B*C-D+E|F|(G+H)
vi. A-B|(C*D$E)
vii. (A+B*C)*((D+E-F)/J)
Dept. of CSE, YIT Moodbidri
 Questions

3. Write an algorithm to evaluate postfix expression Trace

the algorithm for the following expression showing the
stack content
i. 651-4*23^/+
ii.546+*493/+*
iii. 123+*321-+*
iv. 623+-382/+*2$3+
v. ABC-D*+E$F+ where A=5 B=3 C=1 D=2 E=4 F=2

Dept. of CSE, YIT Moodbidri

 String

String: Sequence of characters enclosed in double quotes is called

“String”
Examples:
“India is my country”,
“Eat an apple a day to keep doctor away”

In C programming, a string is essentially an array of characters

that ends with a null character '\0', which is used to mark the
end of the string. C does not have a dedicated string data type
like some other programming languages; instead, strings are
managed as arrays of characters.

Dept. of CSE, YIT Moodbidri

 String

Key Points:
Null Terminator ('\0'): In C, strings are terminated by a null
character. This is how functions like printf know where the string
ends.
Declaration: You can declare a string by:
Initializing it during declaration: char str[ ] = "example";
Declaring a fixed-size array and then initializing it later
char str[10];
strcpy(str, "example“);

Dept. of CSE, YIT Moodbidri

 String

String Functions: The standard library <string.h> provides

various string manipulation functions like:
strcpy(): Copies one string to another.
strlen(): Returns the length of a string.
strcmp(): Compares two strings.
strcat(): Concatenates two strings.
strncmp(): Compares n charcaters in two strings.

Dept. of CSE, YIT Moodbidri

 Custom Function to Copy String

void stringCopy(char *destination, const char *source)

{
int i = 0; // Copy each character from source to destination
while (source[i] != '\0')
{
destination[i] = source[i];
i++;
}
destination[i] = '\0';
}

Dept. of CSE, YIT Moodbidri

 Custom Function to Concatenate Strings
void stringConcat(char *destination, const char *source)
{
int i = 0, j = 0; // Find the end of the destination string
while (destination[i] != '\0')
{
i++;
}
// Append each character of the source string to
destination
while (source[j] != '\0')
{
destination[i] = source[j];
i++;
j++;
}
// Add null terminator at the end of the concatenated
string

destination[i] = '\0';
} Dept. of CSE, YIT Moodbidri
 Custom Function to Compare two Strings
int stringCompare(const char *str1, const char *str2)
{
int i = 0;
// Compare each character of both strings
while (str1[i] != '\0' && str2[i] != '\0')
{
if (str1[i] != str2[i])
{
return str1[i] - str2[i]; // return diff btwn the characters
}
i++;
}
// If one string is longer than the other, the comparison
result should reflect that

return str1[i] - str2[i]; // return 0 if both strings are equal, or

the
difference in lengths
}
Dept. of CSE, YIT Moodbidri
 Custom Function to Find the length of a String

// Function to find the length of a string

int stringLength(const char *str)
{
int length = 0;
// Increment length until we reach the null terminator
while (str[length] != '\0')
{
length++;
}
return length;
}

Dept. of CSE, YIT Moodbidri

 Pattern Matching

Pattern matching refers to the process of searching for a specific

sequence or pattern of characters (often called a "pattern") within
a larger text. It's a common problem in computer science,
especially in string processing applications like text search, data
mining, bioinformatics, and natural language processing.

Basic Concept: In pattern matching, you're given:

A text: The larger string in which you want to search for the
pattern.
A pattern: The string you're searching for within the text.
The goal is to find whether the pattern occurs in the text, and if it
found then return the index (or indices) where it occurs. if not
found then return -1.
Dept. of CSE, YIT Moodbidri
 Naïve Pattern Matching Algorithm

This is the simplest approach where you check every possible

starting position in the text and compare the pattern with the
substring of the text at that position.
Steps:
 Start with the first character of the text.
 For each character, check whether the pattern matches the
substring starting at that position.
 If it matches, record the starting index. If not, move to the
next
character.
Time Complexity: O((n - m + 1) * m) where n is the length of the
text and m is the length of the pattern. This can be inefficient for
large texts and patterns.
Dept. of CSE, YIT Moodbidri
Example: Naive Pattern Matching Algorithm

Dept. of CSE, YIT Moodbidri

 Example: Knuth-Morris-Pratt (KMP) Algorithm

The KMP algorithm improves the naive algorithm by avoiding

unnecessary comparisons after a mismatch. It preprocesses the
pattern into a partial match table (also called the "longest prefix
suffix" table or LPS array), which helps skip over redundant
comparisons.
Steps:
 Preprocess the pattern to create an LPS (longest prefix which is

also a suffix) array.

 Use the LPS array to skip unnecessary comparisons when a
mismatch is found.
Time Complexity: O(n + m) for both preprocessing and
searching.
Dept. of CSE, YIT Moodbidri
Example: Knuth Morris Pratt Matching Algorithm

Dept. of CSE, YIT Moodbidri

Steps in Solving KPM Algorithm

Dept. of CSE, YIT Moodbidri

Function to find Longest Proper Prefix and Suffix

Dept. of CSE, YIT Moodbidri

Function to find Pattern using KPM

Dept. of CSE, YIT Moodbidri