Module 1 - DS

Download as ppt, pdf, or txt
Download as ppt, pdf, or txt
You are on page 1of 170

MODULE-1

Introduction:
Mrs.Mithuna H.R
Assistant Professor
Department of ISE
Acharya Institute Of Technology

Department of ISE Acharya Institute of Technology


TOPICS
• 2Data Structures, Array Operations: Traversing,
Classifications (Primitive & inserting, deleting, searching, and
Non Primitive), Data sorting. Multidimensional Arrays,
structure Operations, Polynomials and Sparse Matrices.
• Review of Arrays, Strings: Basic Terminology, Storing,
Structures, Self-Referential Operations and Pattern Matching
Structures, and Unions. algorithms.
• Pointers and Dynamic Programming Examples.
Memory Allocation
Functions. Representation
of Linear Arrays in Memory,
• Dynamically allocated
arrays.

Department of ISE Acharya Institute of Technology


2
Basic Terminologies
Data Structure
– Data: are simply a value are set of values of different type which is called
data types like string, integer, char etc.
– Structure: Way of organizing information, so that it is easier to use
– In simple words we can define data structures as
● Its a way organizing data in such a way so that data can be easier to use.

Department of ISE Acharya Institute of Technology


Basic Terminologies
Data Structure ..
– A data structure is a particular way of organizing data in a computer so that it
can be used effi ciently.
– A scheme for organizing related pieces of information.

Department of ISE Acharya Institute of Technology


Basic Terminologies
Data: The term ‘DATA’ simply refers to a value or a set of values. These values
may present anything about something, like it may be roll no of a student, marks,
name of an employee, address of person etc.

Data item: A data item refers to a single unit of value. For eg. roll no of a student,
marks, name of an employee, address of person etc. are data items. Data items
that can be divided into sub items are called group items (Eg. Address, date,
name), where as those who can not be divided in to sub items are called
elementary items (Eg. Roll no, marks, city, pin code etc.).

Department of ISE Acharya Institute of Technology


Basic Terminologies
• Entity - with similar attributes ( e.g all employees of an organization) form an
entity set.

• Information: Data with given attribute or processed data.

• Field is a single elementary unit of information representing an attribute of an


entity.

• Record is the collection of field values of a given entity.

• File is the collection of records of the entities in a given entity set.

Department of ISE Acharya Institute of Technology


Basic Terminologies
• Each record in a file may contain many field items but the value in a certain
field may uniquely determine the record in the file. Such a field K is called a
primary key, and the values K1, K2, K3… in such a field are called keys or key
values.

• Records can be classified as fixed-length records or variable-length records. In


fixed length records, all the records contain the same data items with the
same amount of space assigned to each data item .In variable length records ,
file records may contain different lengths.

Department of ISE Acharya Institute of Technology


Basic Terminologies
EXAMPLE:

Attributes: Name Age Gender Roll Number Branch

Values: A 17 M 109cs0132 CSE

B 18 M 109ee1234 ISE

Here, it is an example of student details where STUDENT is the given entity. Then
name, age, Gender, roll number, branch are attributes and their values are
properties (A, 17, M, 109cs0132, CSE). Collection of student details is student
entity set and Roll number is the primary key which uniquely indicates each
Department of ISE Acharya Institute of Technology
student details.
Why Data Structure

•Human requirement with computer are going to complex day by day. To solve
the complex requirements in efficient way we need this study.
• Provide fastest solution of human requirements.
• Provide efficient solution of complex problem.
–Space
– Time

Department of ISE Acharya Institute of Technology


Study in Data Structure
Logical or mathematical description of the structure.
● Implementation of structure on a computer using different computer
languages ( C, C++, JAVA, pl-languages etc.)
● Qunatitative analysis of the structure, which includes determining the
amount of memory needed to store the structure and the time required
to process the structure.

Department of ISE Acharya Institute of Technology


Classification of Data Structure

Department of ISE Acharya Institute of Technology


• Simple Data Structure: Simple data structure can be constructed
with the help of primitive data structure. A primitive data
structure used to represent the standard data types of any one
of the computer languages (integer, Character, float etc.).
• Compound Data Structure: Compound data structure can be
constructed with the help of any one of the primitive data
structure and it is having a specific functionality. It can be
designed by user. It can be classified as Linear and Non-Linear
Data Structure.

Department of ISE Acharya Institute of Technology


Anything that can store data can be called as a data structure, hence Integer,
Float, Boolean, Char etc, all are data structures. They are known as Primitive
Data Structures and some complex Data Structures, which are used to store
large and connected data. They are called Non-primitive Data Structures.
Examples:Array,Stack,Queue,Linked List,Tree,Graph

Department of ISE Acharya Institute of Technology


Primitive Data Structure: The data Structures that can be Manipulated
directly by Machine Instructions are called Primitive Data Structures.
For Example, in C language, the different primitive data structures are
defined using the data types such as int, float, char, double and pointers.
Non-Primitive Data structure:
The data Structures that cannot be Manipulated directly by Machine
Instructions are called Non-Primitive Data Structures.

Department of ISE Acharya Institute of Technology


Non-Primitive data structure can be constructed with the help of
any one of the primitive data structure and it is having a specific
functionality. It can be designed by user. Arrays, Structure, Union,
linked list, Stacks, Queue, trees, graphs etc are example for non
primitive data structures.
It can be classified as
1) Linear data structure
2) Non-linear data structure

Department of ISE Acharya Institute of Technology


Linear Data Structures: A linear data structure traverses the data
elements sequentially, in which only one data element can directly be
reached. Ex: Arrays, Linked Lists
● Non-Linear Data Structures: Every data item is attached to several
other data items in a way that is specific for reflecting relationships. The
data items are not arranged in a sequential structure. Ex: Trees, Graphs

Department of ISE Acharya Institute of Technology


Operation on Linear/Non-Linear
Data Structure
• Add an element
• Delete an element
• Traverse / Display
• Sort the list of elements
• Search for a data element
• Merge the list

Department of ISE Acharya Institute of Technology


(1)Traversing: Accessing each record exactly once so that certain items in
the record may be processed.
(2) Searching: Finding the location of a particular record with a given key
value, or finding the location of all records which satisfy one or more
conditions.
(3) Inserting: Adding a new record to the structure.
(4) Deleting: Removing the record from the structure.
(5) Sorting: Managing the data or record in some logical order (Ascending
or descending order).
(6) Merging: Combining the record in two different sorted files into a single
sorted file. Department of ISE Acharya Institute of Technology
Operations on linear data structures
1.Add an element
2.Delete an element
3.Traverse all the elements
4.Sort the list of elements
5.Search for a data element
Apply one or more functionality to create different types of data
structures.
For example Stack, Queue, and Linked Lists.

Department of ISE Acharya Institute of Technology


Operations applied on non-linear data structures
The following list of operations applied on non-linear data structures.
1. Add elements.
2. Delete elements
3. Display the elements
4. Sort the list of elements
5. Search for A data element by applying one or more functionalities
and different ways of joining randomly distributed data items to create
different types of data structures. For example Tree, Graphs and Files.

Department of ISE Acharya Institute of Technology


Types of Data Structure
Array: is commonly used in computer programming to mean a
contiguous block of memory locations, where each memory location
stores one fixed-length data item. e.g. Array of Integers int a[10], Array
of Character char b[10].

Department of ISE Acharya Institute of Technology


Stack: A stack is a data
structure in which items can
be inserted only from one
end and get items back from
the same end. There , the last
item inserted into stack, is
the the first item to be taken
out from the stack. In short
its also called Last in First
out [LIFO]

Department of ISE Acharya Institute of Technology


Department of ISE Acharya Institute of Technology
Department of ISE Acharya Institute of Technology
Operations on Stack

• Insert (PUSH)
• Delete(POP)
• Overflow
• Underflow

Department of ISE Acharya Institute of Technology


Queue: A queue is two
ended data structure in
which items can be
inserted from one end and
taken out from the other
end. Therefore , the first
item inserted into queue is
the first item to be taken
out from the queue. This
property is called First in
First out [FIFO].
Department of ISE Acharya Institute of Technology
Department of ISE Acharya Institute of Technology
Department of ISE Acharya Institute of Technology
front end-index to the first element-end at which elements
are deleted.
rear end-index to the last element-end at which elements
are added or inserted.

Department of ISE Acharya Institute of Technology


LIFO:Last element Inserted is the First element to
be deleted out.
FIFO: First element Inserted is the First element to
be deleted out.

Department of ISE Acharya Institute of Technology


Linked List: Could alternately used to store items. In linked list space
to store items is created as is needed and destroyed when space no
longer required to store items. Hence linked list is a dynamic data
structure space acquire only when need.

Department of ISE Acharya Institute of Technology


Department of ISE Acharya Institute of Technology
Department of ISE Acharya Institute of Technology
Tree: is a non-linear data Binary Tree: A binary
structure which is tree is a tree such that
mainly used to represent every node has at most 2
data containing a child and each node is
hierarchical relationship labeled as either left of
between elements. right child

Department of ISE Acharya Institute of Technology


Department of ISE Acharya Institute of Technology
Department of ISE Acharya Institute of Technology
Graph: It is a set of items connected by edges. Each item is
called a vertex or node. Trees are just like a special kinds of
graphs. Graphs are usually represented by G = (V, E), where V
is the set vertices and E is the set of Edges.

Department of ISE Acharya Institute of Technology


Undirected Graph: A graph
whose edges are unordered pair of vertices. That is each edge
connects two vertices. In an undirected graph, direction is not
important, if the path is available, it can be traversed in any direction.

Department of ISE Acharya Institute of Technology


Directed Graph: In directed graph a directional edge connect two
node/vertex. If there is one edge from one vertex to other then only this
path can be followed.

Department of ISE Acharya Institute of Technology


Weighted Graph: A graph having a weight, or number
associated with each edge.

Department of ISE Acharya Institute of Technology


Selecting a Data Structure

• Analyze the problem to determine the resource constraints a


solution must meet.
• Determine the basic operations that must be supported. Quantify
the resource constraints for each operation.
• Select the data structure that best meets these
requirements.

Department of ISE Acharya Institute of Technology


ARRAYS

Department of ISE Acharya Institute of Technology


• An array is a special and very powerful data structure in C language.
• An array is a collection of similar data items. All elements of the array
share a common name.
• Each element of an array is given a number by which we can access
that element which is called an index.
• To refer to a particular location or element in the array we specify the
name to the array and position number of particular element in the
array.

Department of ISE Acharya Institute of Technology


Element − each item stored in an array is called an element.

Index − each location of an element in an array has a numerical index


which is used to identify the element.

Department of ISE Acharya Institute of Technology


ARRAY REPRESENTATION
Arrays can be declared in various ways in different languages. For
illustration, let's take
C array declaration

Figure 8.a: Array with 10 elements

Department of ISE Acharya Institute of Technology


Figure : Array index

As per above shown illustration, following are the important points


to be considered.(As shown in figure 8.a and figure 8.b)
•Index starts with 0.
•Array length is 10 which mean it can store 10 elements.
•Each element can be accessed via its index. For example, we can
fetch element at index 6 as 27.
Department of ISE Acharya Institute of Technology
One Dimensional Array
Declaration:
Before using the array in the program it must be declared
Syntax: data_type array_name[size];
data_type represents the type of elements present in the array. array_name
represents the name of the array. Size represents the number of elements that
can be stored in the array.
Example: int age[100]; float sal[15]; char grade[20];
Here age is an integer type array, which can store 100 elements of integer type.
The array sal is floating type array of size 15, can hold float values. Grade is a
character type array which holds 20 characters.
Department of ISE Acharya Institute of Technology
Initialization:
Initialize arrays at the time of declaration.
Syntax:data_type array_name[size]={value1, value2,……..valueN};
Value1, value2, valueN are the constant values known as initializers,
which are assigned to the array elements one after another.
Example: int marks[5]={10,2,0,23,4};
The values of the array elements after this initialization are:
marks[0]=10, marks[1]=2, marks[2]=0, marks[3]=23, marks[4]=4;

Department of ISE Acharya Institute of Technology


NOTE:
1. In 1-D arrays it is optional to specify the size of the array. If size is
omitted during initialization then the compiler assumes the size of
array equal to the number of initializers.

Example: int marks[]={10,2,0,23,4};

Here the size of array marks is initialized to 5.


2. We can’t copy the elements of one array to another array by simply
assigning it.

Department of ISE Acharya Institute of Technology


Example:
int a[5]={9,8,7,6,5};
int b[5];
b=a; //not valid
all the elements of the array are copied by using for loop.
for(i=0; i<5; i++)
b[i]=a[i];
Processing: For processing arrays we mostly use for loop. The total no.
of passes is equal to the no. of elements present in the array and in each
pass one element is processed.

Department of ISE Acharya Institute of Technology


Example: This program reads and displays 3 elements of integer type.
#include<stdio.h>
main()
{
int a[3],i;
for(i=0;i<=2;i++) //Reading the array values
{
printf(“enter the elements”); scanf(“%d”,&a[i]);
}
for(i=0;i<=2;i++) //display the array values
{
printf(“%d”,a[i]); printf(“\n”);
}
Department of ISE Acharya Institute of Technology
}
OPERATIONS ON ARRAYS
Following are the basic operations supported by an array.
•Traversal – processing each element in the list.
•Insertion − adding a new element at given index to the list.
•Deletion – removing an element at given index from the list.
•Search − finding the location of the element with a given value or
the record with a given key
•Sorting: arranging the elements in some type of order.
•Merging: Combing two lists into a single list.

Department of ISE Acharya Institute of Technology


• Traversing linear arrays
Let A be the array in the memory of the computer. If the operation required is
to print the contents of each element of A OR Count the number of elements
of A. Then this is accomplished by traversing A, i.e, by accessing and
processing each element of A exactly once.

Department of ISE Acharya Institute of Technology


n=4
Function to Insert an item at specified position
i-> 0 1 2 3
void insert()
a 1 3 4 5
{
i=4-1=3
printf("\nEnter the position for the new element:\t");
scanf("%d",&pos); pos=1 i-> 0 1 2 3 4
printf("\nEnter the element to be inserted :\t"); a 1 3
2 4
3 5
4 5

scanf("%d",&val); val=2

for(i=n-1;i>=pos;i--) 3>=1
2>=1
1>=1
0>=1
i=3
i=1
i=0
i=2
{
a[i+1]=a[i]; a[4]=a[3]
a[3]=a[2]
a[2]=a[1]
}
a[pos]=val; n=4+1=5
a[1]=2
n=n+1;}
Department of ISE Acharya Institute of Technology
}
Function to Delete an item at specified position
void delete() n=4

{
i-> 0 1 2 3
printf("\nEnter the position of the element to be deleted:\t");
a 1 2 3 4
scanf("%d",&pos); pos=1
i-> 0 1 2 3
val=a[pos]; val=a[1] val=2
a 1 3 3
4 4
for(i=pos;i<n-1;i++)
i=1
i=2
i=3
1<3
2<3
3<3 i-> 0 1 2
{
a 1 3 4
a[i]=a[i+1];
a[1]=a[2]
a[2]=a[3]
}
n=n-1; n=4-1=3

printf("\nThe deleted element is =%d",val);


}
Department of ISE Acharya Institute of Technology
Department of ISE Acharya Institute of Technology
Write a C program to input elements in two array
and merge two array to third array. How to merge
two array in C programming.
Logic to merge two sorted array to third array in C program.
Example:
Input
Input first array elements: 1, 4, 6, 9, 15
Input second array elements: 2, 5, 8, 10
Output
Merged array in ascending order = 1, 2, 4, 5, 6, 8, 9, 10, 15
Department of ISE Acharya Institute of Technology
Department of ISE Acharya Institute of Technology
void merge_array(int a[],int b[],int c[],int n1,int n2) while(i<n1)
{ int i=0; n1=2 n2=3 { 2<2 False
int j=0; i-->0
i-->
i--> 12 c[k]=a[i];
int k=0; i++;
/*merging starts*/ a 10 20
k++;
while(i<n1&&j<n2) }
8 12 25
{ if(a[i]<=b[j]) b while(j<n2)
0<2&&0<3
0<2&&1<3
1<2&&1<3
1<2&&2<3
2<2&&2<3 { j-->
j->0
j--> 1 32 2<3 True
{
True
False c[k]=a[i]; c[k]=b[j];
i++; c[4]=b[2]
a[0]<=b[1]
a[0]<=b[0]
a[1]<=b[1]
a[1]<=b[2] j++;
10<=12
10<=8
20<=12
20<=25False
True
False k++; k++;
} }
else for(i=0;i<n1+n2;i++)
c[0]=b[0]
c[1]=a[0]
c[2]=b[1]
c[3]=a[1]
{ {
c[k]=b[j]; printf("%d\t",c[i]);
c 8
8 10 12
12 20
20 25
j++; }
k++; } } }
k-->
k-->0
k-->
k--> 2 3
145 Department of ISE Acharya Institute of Technology
TWO DIMENSIONAL ARRAYS

Arrays that we have considered up to now are one dimensional array,


a single line of elements. Often data come naturally in the form of a
table, e.g. spreadsheet, which need a two-dimensional array.

Declaration: The syntax is same as for 1-D array but here 2 subscripts
are used.
Syntax:data_type array_name[rowsize][columnsize];
Rowsize specifies the no.of rows Columnsize specifies the no.of
columns.
Example: int a[4][5];

Department of ISE Acharya Institute of Technology


This is a 2-D array of 4 rows and 5 columns. Here the first element of the
array is a[0][0] and last element of the array is a[3][4] and total no.of
elements is 4*5=20.

Col 0 Col 1 Col 2 Col 3 Col 4


Row 0 a[0][0] a[0][1] a[0][2] a[0][3] a[0][4]
Row 1 a[1][0] a[1][1] a[1][2] a[1][3] a[1][4]
Row 2 a[2][1] a[2][2] a[2][2] a[2][3] a[2][4]
Row 3 a[3][0] a[3][1] a[3][2] 3a[3][3] a[3][4]

Department of ISE Acharya Institute of Technology


Initialization:
2-D arrays can be initialized in a way similar to 1-D arrays.
Example: int m[4][3]={1,2,3,4,5,6,7,8,9,10,11,12};
Example: int m[][3]={ {1,10}, {2,20,200}, {3}, {4,40,400} };

Department of ISE Acharya Institute of Technology


STRINGS

Department of ISE Acharya Institute of Technology


STRINGS
Strings are one-dimensional array of characters terminated by a null
character '\0'.
Thus a null-terminated string contains the characters that comprise the
string followed by a null.
The following declaration and initialization create a string consisting of the
word "Hello".
To hold the null character at the end of the array, the size of the character
array containing the string is one more than the number of characters in the
word "Hello."

Department of ISE Acharya Institute of Technology


Example:
•char greeting[6] = {'H', 'e', 'l', 'l', 'o', '\0'};
•char greeting[] = "Hello";

Department of ISE Acharya Institute of Technology


Example Program:-
#include <stdio.h>
int main ()
{
char greeting[6] = {'H', 'e', 'l', 'l', 'o', '\0'};
printf("Greeting message: %s\n", greeting );
return 0;
}

Department of ISE Acharya Institute of Technology


Arrays of strings
The Programming statement to read 5 names can be written as shown
below :
•To create an array of string, we should use two-
dimensional array as shown below. for(i=0;i<=4;i++)
Example: {
scanf(“%s”,a[i]);
}
char a[row][col];
Maximum length of each string The array elements can be printed as shown below:
Number of strings
Name of the array for(i=0;i<=4;i++)
{
•The memory representation for the following printf(“%s\n”,a[i]);
}
initialization

Char a[5][11]={
“DHARMARAYA”,
“BHIMA”,
“ARJUNA”,
“NAKULA”,
“SAHADEVA”
}
0 1 2 3 4 5 6 7 8 9 10
0 D H A R. M A R A Y A \0
1 B H I M A \0
a 2 A R J U N A \0
3 N A K U L A \0
4 S A H A D E V A \0
STRING OPERATIONS
C supports a wide range of built in functions that manipulate null-terminated
strings :− strcpy(s1, s2):- Copies string s2 into string s1.

strcat(s1, s2):- Concatenates string s2 onto the end of string s1.

strlen(s1):- Returns the length of string s1.

strcmp(s1, s2):- Returns 0 if s1 and s2 are the same; less than 0 if s1<s2;
greater than 0 if s1>s2.
strrev(s1):-This function reverses all characters in the string str except the
terminating NULL character ‘\0’.

Department of ISE Acharya Institute of Technology


Built_in function User defined function
strcat(s1,s2)-string concatenate
#include <stdio.h> #include<stdio.h>
Syntax: It is defined in “string.h”.
void main() Void main()
{ {
strcat(char s1[], char s2[]);
char s1[15]=“RAMA”; int i, j;
Where: Char s2[]=“KRISHNA”; printf("Enter the string1\n");
scanf("%[^\n]", str1);
s1 is the first string my_strcat(s1,s2); printf("Enter the string2\n");
s2 is the second string scanf("%[^\n]", str2);
printf(“Con string =%s\n”,s1); i = 0;
while( str1[i] != '\0’)
•The function copies all the characters of string s2 to the end } {
of string s1. i + +;
OUTPUT: }
s1 V I V E K \ ? ? ? ? R A s2
M A \0 ? ? ? ? ? Concatenated string= j=0;
0
RAMAKRISHNA while( str2[j] != '\0’)
{
After strcat(s1, s2); str1[i] = str2[j];
i + +;
j + +;
V I V E K R A M A \0 }
str1[i] = '\0’;
}
. printf("Concat string = %s\n", str1);
}
1)Write a C program to concatenate two strings without using builtin function.
#include<stdio.h>
void strcate(char s1[],char s2[])
{
int i=0,j=0; void main()
while(s1[i]!='\0') {
i++; char s1[40],s2[20];
while(s2[j]!='\0') printf("Enter two strings :\n");
{ gets(s1);
s1[i]=s2[j]; gets(s2);
i++; strcate(s1,s2);
j++; printf("Concatenated string : %s\n",s1);
} }
S1[i]=’\0’;
} Department of ISE Acharya Institute of Technology
Department of ISE Acharya Institute of Technology
strcmp(s1,s2)-string compare
Syntax: int strcmp(char s1[],char s2[]); Built_in function
Where
User-defined function
s1 is the first string #include<stdio.h> #include<stdio.h>
s2 is the second string #include<string.h> #include<string.h>
void main() Void main()
•This function is used to compare two strings. {
{
•The comparison starts with first character of each string. char s1[]=“RAMA”;
Int difference,I;
•The comparision continues till the corresponding characters differ or until the char s2[]=“KRISHNA”;
char str1[20], str2[20];
end of the character reached.
Int difference;
The following values are returned after comparison: printf("Enter the string1\n"); scanf("%
difference=strcmp(s1,s2);
[^\n]", str1); // gets(str1);
if s1=s2zero If(difference==0)
if s1>s2positive Printf(%s = %s\n”,s1,s2); printf("Enter the string2\n"); scanf("%
if s1<s2 negative else if (difference>0) [^\n]", str2); // gets(str2);
Printf(“%s>%s\n”,s1,s2);
i=0;
0 R
== R
0 dest[0]== src[0] else While(s1[i]==s2[i])
1 == 1 dest[1]== src[1] {
A A Printf(“%s<%s\n”,s1,s2); If(s1[i]== ‘\0’)
2 == 2 dest[2]= =src[2] } break;
M M
i++
A A }
3 == 3 dest[3]= =src[3] difference=s1[i]-s2[i];
\0 \0
if(difference = = 0)
4 == 4 printf("%s = %s\n", s1, s2);
else if (difference >0)
In general, dest[i]==src[i]
. printf("%s > %s\n",s1, s2);
where initial value of i=0 else
printf("%s < %s\n", s1, s2);
}
2)Write a C program to compare two strings without using built-in function.
#include<stdio.h> void main()
int strcomp(char s1[],char s2[]) {
{ char s1[20],s2[20];
int i=0; int i=0;
while(s1[i]==s2[i]) printf("Enter two strings :\n");
{ gets(s1);
if(s1[i]=='\0') gets(s2);
break; i=strcomp(s1,s2);
i++; if(i==0)
} printf("Strings are equal.\n");
return s1[i]-s2[i]; else
} printf("Strings are not equal.\n");
}

Department of ISE Acharya Institute of Technology


strcpy(dest, src)-String Copy Built_in function User-defined function

#include<stdio.h> #include<stdio.h>
#include<string.h> #include<string.h>
The syntax to use strcpy() is
void main() Void main()
strcpy(char dest[], char src[]) { {
•The function strcpy copies the contents of source string src to destination dest
char src[]=“RAMA”; char src[20];
char dest[6]; char dest[20];
including ‘\0’.
•So, the size of destination string dest should be greater or equal to the size of strcpy(dest,src); int i = 0;
printf(“Enter the string\n”);
source string src. printf(“Dest string = %s\ gets(src);
n”,dest);
dest src dest src
} while( src[i] != '\0’)
0 0 dest[0]= src[0] {
R R dest[i]=src[i];
1 1 dest[1]= src[1] i + +;
A A INPUT }
2 2 dest[2]= src[2] RAMA dest[i]=‘\0’;
M M
3 3 dest[3]= src[3]
A A OUTPUT printf(“Dest String = %s\
4 4 Dest string = RAMA n”,dest);
\0 \0 }
In general, dest[i]=src[i] INPUT
Enter the string
where initial RAMA

value
. of i=0 OUTPUT
Dest string = RAMA
Write a C program to copy string src to string dest without using built-in function.
#include<stdio.h>
void strcopy(char src[],char dest[])
{
int i=0;
void main()
while(src[i]!='\0')
{
{
char s1[20],s2[20];
dest[i]=src[i];
printf("Enter a string : ");
i++;
gets(s1);
}
strcopy(s1,s2);
dest[i]=’\0’;
printf("Given string : %s\n",s1);
}
printf("Copied string : %s\n",s2);
}

Department of ISE Acharya Institute of Technology


strlen(str):String Length Built_in function User-defined function

#include<stdio.h> #include<stdio.h>
The syntax to use strlen() is #include<string.h> #include<string.h>
Void main()
void main() {
strlen(str)
{ char str[20];
•This function returns the length of the string str i.e. it counts all the characters char str[]=“RAMA”; int i = 0;
up to ‘\0’ except ‘\0’. printf(“Length = %d\ printf(“Enter the string\n”);
•So, an empty string has length zero. n”,strlen(str)); gets(str);
i=0; A I T \0
} while( str[i] != '\0’)
Consider the string “ACIT”
{
str OUTPUT i + +; \\0 1 2 3
Length=4 }
printf(“Length = %d\n”,i); //3
}
A C I T \n

i 0 1 2 3 4 INPUT
AIT
i=0;
while(str[i]!=‘\0’) OUTPUT
i++ Length=3

.
4)Write a C program to find string length without using built-in function.
#include<stdio.h>
int strleng(char s1[])
{
int i=0; void main()
while(s1[i]!='\0') {
i++; int len;
return i; char s[20];
} printf("Enter a string : ");
gets(s);
len=strleng(s);
printf("The length of the string : %d.",len);
}

Department of ISE Acharya Institute of Technology


Strrev(str)-String reverse
Built_in function User-defined function
Syntax: strrev(str) #include<stdio.h>
#include<stdio.h>
#include<string.h> #include<string.h>
where Void main()
str is the given string void main() {
{ char src[20],dest[20];
This function reverses all characters in the string str except the terminating char str[]=“INDIA”; int i,n;
NULL character ‘\0’. printf(“Enter the string\n”);
strrev(str); gets(src);
n=strlen(src)
for(i=0;i<n;i++)
printf(“Rev String = %s\ {
n”,str); dest[n-1-i]=src[i];
} }
dest[n]=‘\0’;
printf(“Source Destination\n”);
printf(“%-5s\t\t%5s\”,src,dest);
INPUT }
INDIA INPUT
INDIA
OUTPUT
OUTPUT
Rev String = AIDNI Source Destination
INDIA AIDNI

.
5)Write a C program to reverse a given string without using built-in function.
#include<stdio.h>
void str_rev(char src[],char dest[])
{
int i,n=0; void main()
while(src[n]!='\0') {
n++;
for(i=0;i<n;i++) char src[20],dest[20];
{ printf("Enter a string1 : ");
dest[n-1-i]=src[i]; gets(src);
} str_rev(src,dest);
dest[n]=’\0’; printf("The reversed string : %s",dest);
} }

Department of ISE Acharya Institute of Technology


Pointers

Department of ISE Acharya Institute of Technology


Pointers Example: If i is a variable and address of i is stored in a
•The basic data types in C language are int float char, double and void. variable P
•Pointer is a special data type which is derived from these data types. p=&i;
•So pointer is called derived data type. Then the variable p is called a Pointer variable.
•The pointers are always associated with the following three concept.
Pointer constants
Pointer values
Pointer variables
•The computer memory is divided into a number of locations called
storage cells.
•Each location can hold one byte of information and each location is
associated with address.
•These memory address are called pointer constants.
•These memory location assigned to variable by the system are called
pointer values. Accessing variables through pointers
•A variable which holds the address of another variable is called a
pointer variable. Steps to be followed while using pointers

•Declare a data variable


Ex: int a;
•Declare a pointer variable
Ex: int *p;
•Initialize a pointer variable
Ex: p=&a;
•Access data using pointer variable
Ex: printf(“%d”,*P);
Pointers declaration and definition: Dangling Pointer
•Pointer variables should be declared before they are used. Example:
Syntax: type * identifier; int *p;

Example 1: int *p; p Garbage value


double *pd;
•A pointer variable should contain a valid address.
In the declaration, the position of * is immaterial. •A pointer variable which does not contain a valid address is
Example 2: int *pa;
called dangling pointer.
int * pa;
int* pa;
Initializing a pointer variable
Example 3: int* pa,pb,pc; Initializing of a pointer variable is the process of assigning the
address of a variable to a pointer variable.
int *pa; //pa is the pointer variable
int pb; //pb and pc are ordinary variable •Declare a data variable
int pc; Ex: int x;
•Declare a pointer variable
Ex: int *px;
•Assign address of a data variable to pointer variable using &
operator and assignment operator.
Ex: px=&x;
OR
int x,*px=&x;

Example: int p,*ip;


float d,f;
ip = &p; /* Correct */ ip= &d; /* wrong
*/
Accessing variables through pointers
Pointers are flexible: i.e pointer can point to different data
The value of a variable can be accessed using pointer variable
Variables by storing the address of appropriate variables.
using unary operator *(called asterisk)
Example:
int x=10,y=20,z=30; x 100 ? ?
Example: int x=100,y; X y p
Int *p; 10 int *p; 2000
P=&x; p=&x;
100
P=&y; p y=*p; p 2000 y
P=&z; 20 y
z
NULL pointer:- 30 /* C program to add two number using pointers */
A NULL pointer is defined as a special pointer value that point
#include <stdio.h>
to nowhere in the memory.
int main()
Example: #include<stdio.h> {
int *p=NULL int num1, num2, sum;
if(p==NULL) //Error condition int *ptr1, *ptr2;
printf(“P does not point to any memory\n”); ptr1 = &num1; // ptr1 stores the address of num1
else ptr2 = &num2; // ptr2 stores the address of num2
printf(“Access the value of P\n”); printf("Enter any two numbers: ");
scanf("%d%d", &num1, &num2);

sum = *ptr1 + *ptr2;

printf("Sum = %d", sum);


return 0;
}
/* Pointers and functions */ C program swapping of two numbers

There are two ways of passing parameters to the functions Calling function Called function
#include<stdio.h> Void exchange(int a,int b)
•Pass by value (also called call by value)
•Pass by reference (also called call by reference) Void exchange(int m, int n); {
int temp;
Pass by value (call by value) void main() printf(“Before exchange\n”);
{ printf(“m=%d and n=%d\
•When a function is called with actual parameters, the values of actual int a,b; n”,a,b);
parameters are copied into formal parameters. a=10, b=20;
printf(“Before exchange”); temp=a;
•If the values of the formal parameters changes in the functions, the values of printf(“a=%d and b=%d\ a=b;
the actual parameters are not changed. n”,a,b); b=temp;
•This way of passing parameters is called pass by value or call by value
exchange(a,b); printf(“After exchange\n”);
printf(“a=%d and b=%d\
printf(“After exchange”); n”,a,b);
printf(“a=%d and b=%d\
n”,a,b);
} }
OUTPUT Before exchange
Before exchange
m=10 and n=20
a=10 and b=20
. After exchange
After exchange

m=20 and n=10


a=10 and b=20
Pass by reference (call by reference) C program swapping of two numbers

•In pass by reference, a function is called with addresses of actual parameters. Calling function Called function
•In the function header, the formal parameters receive the addresses of actual #include<stdio.h> Void exchange(int *m,int *n)
parameters. Void exchange(int *m, int *n); {
int temp;
•Now, the formal parameters do not contain values, instead they contain
void main() printf(“Before exchange\n”);
addresses.
{ printf(“m=%d and n=%d\
•Any variable if it contains an address, it is called a pointer variable. int a,b; n”,*m,*n);
a=10, b=20;
•Using pointer variables, the values of the actual parameters can be changed. temp=*m;
printf(“Before exchange”); *m=*n;
•This way of passing parameters is called Pass by reference or call by printf(“a=%d and b=%d\ *n=temp;
reference. n”,a,b);
printf(“After exchange\n”);
exchange(&a,&b); printf(“m=%d and n=%d\
n”,*m,*n);
printf(“After exchange”);
printf(“a=%d and b=%d\ }
n”,a,b);
}
Before exchange
OUTPUT
Before exchange m=10 and n=20
.
a=10 and b=20 After exchange

After exchange
m=20 and n=10
Comparison of Pass by Value and Pass by Reference

Sl no. Pass by Value Pass by Reference

1 Values of variables are passed in the function call. Addresses of the variables are passed in the function
call.

2 The type of actual and formal parameters must be same. The type of actual and formal parameters must be
same and the formal parameters must be declared as
pointers.

3 Formal parameters contain the values of actual Formal parameters contain the addresses of actual
parameters. parameters.

4 The actual parameters are not changed when the formal The actual parameters are changed when the formal
parameters are changed. parameters are changed.

5 Less information transfer. Only one value can be More information transfer as changes made to formal
returned. parameters change actual parameters.
Functions returning pointers /* Pointer to pointer */
•A function can return a single value using return statement or multiple values
It is possible to make a pointer to point to another pointer variable.
using pointers in parameters. A variable which contains address of a pointer variable is called pointer
•Since pointer is also a data type in C, we can return a pointer from a function.
to pointer.

Example:-Program to return pointer to larger of two numbers. Example:


int v;
void main() int *pt1;
int **pt2;
{
int x,y,*big; void main()
printf(“Enter the value of x & y\n”); {
scanf(“%d%d”,&x,&y); int a;
big=largest(&x,&y); int *p1;
int **p2;
printf(“Maximum(%d,%d)=%d\n”,x,y,*big); a=10;
} p1=&a
int *largest(int *a, int *b) p2=&p1;
{ printf(“a=%d”,a); //a=10
if (*a>*b) printf(“*p1=%d\n”,*p1); //*p1=10
Printf(“**p2=%d\n”,**p2); //**p2=10
return a; }
else
return b;
}

.
Arrays and pointers:
Traversing an array by using pointers
int arr[5] = { 10, 20, 30, 40, 50};

arr=1000

10 20 30 40 50 #include <stdio.h>
int main()
{
int i,sum,*p;
int a[5] = {1, 2, 3, 4, 5};
int *p = a; // same as int*p = &a[0]

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


{
printf("%d", *p);
arr=&arr[0]=1000 p++;
}

*p; return 0;
p=x; is equal to p=&x[0]; }

Now we can access every value of x using p++ to move from one element to
another.
p=&x[0](=1000)
p+1=&x[1](=1002)
p+2=&x[2](=1004) OUTPUT:
p+3=&x[3](=1006) 1
p+4=&x[4](=1008) 2
3
. 4
5
Pointers can be used to manipulate two – dimensional arrays as well . Pointers and Character Strings
C supports an alternative method to create strings using
One dimensional array x, the expression.
* (x+i) or *(p+i) = x[i]
pointer variables of type char.
char *str=“good”;
Two dimensional array can be represented by the pointer expression as follows: The pointer str now points to the first character of the string
“good: as
*(*(a+i)+j) or *(*(p+i)+j) g o o d

*(*(p+i)+j)value stored in the cell (I,j) str


printf(“%s”, str); //puts(str);
p pointer to first row
p+i pointer to ith row
*(p+i) pointer to first element in the ith row
Write a program using pointer to determine the length of
a character string.
*(p+i)+j pointer to jth element in the ith row main()
{
char *name;
int length;
char *cptr = name;
name = DELHI”;
printf(“%s\n”,name);
while(*ctr!=‘\0’)
{
printf(“%c is stored at address %u\n”,*cptr,cptr);
cptr++;
}
length = cptr-name;
. printf(“\n length of the string = %d\n”,length);
}
Pointer to functions #include<stdio.h>
int addition ();
A function, like a variable, has a physical location in the memory.. int main ()
{
Like assigning address of a variable to pointer, it is possible to assign address of a int result;
function to a pointer. int (*ptr)();
ptr = &addition;
Once a pointer points to a function, the function can be invoked using this pointer result = (*ptr)(); //result=addition();
printf("The sum is %d",result);
Using function pointer, it is possible to pass functions as parameters . }
int addition()
Syntax: type (*fp)(); {
int a, b;
type : type of value returns from the function printf("Enter two numbers?");
*fp is pointer to a function scanf("%d %d",&a,&b);
return a+b;
}

Enter two numbers?

10 and 15

The sum is 25

.
Pointers and Structures /*Write a program to illustrate the use of structure pointer
The name of an array stands for the address of its zeroth element. */
The same thing is true of the name of arrays of structure variables.
Suppose product is an array variable of struct type.
struct invent
The name product represents the address of its zeroth element.
Consider the following declaration: {
struct inventory char name[30];
{ int number[30];
char name[30]; float price;
int number[30];
};
float price;
}product[2],*ptr;
ptr=product; main()
{
Its members can be accessed using the following struct invent product[3],*ptr;
ptrname
printf(“INPUT \n\n”);
ptrnumber
ptrprice
for(ptr=product;ptr<product+3;ptr++)
scanf(“%s%d%f”,ptrname,&ptrnumber,&ptrprice);

printf(“\n OUTPUT \n\n”);


ptr=product;
while(ptr<product+3)
{
printf(“%-20s%5d%10.2f\n”,ptrname, ptrnumber, ptrprice);
. ptr++;
}

}
Memory Allocation
Static Memory Allocation
•It is a process where in the memory space is allocated during the
compilation time.
•Here the allocated memory space cannot be expanded or reduced to
accommodate more or less data, i.e. the size of the allocated memory space
is fixed and it cannot be altered during execution.

Department of ISE Acharya Institute of Technology


EX: Consider the declaration int a[10];

During compilation, the compiler will allocate 10 memory locations for the
variable ‘a’ and once defined cannot be changed.

During execution we cannot have more than 10 data items, and if we use 3
locations, another 7 locations are wasted.

Department of ISE Acharya Institute of Technology


Disadvantages:
•In this type of memory allocation, the data structures require a fixed amount
of storage. Since the amount of storage is fixed,
•If the data structure in use, uses only a small amount of memory, rest of the
memory is wasted.
•If the data structure in use, tries to use more memory than actually allocated
for it results in an overflow.
•Because of these limitations, this type of memory allocation can be used in
applications where the data size is fixed and known before processing.

Department of ISE Acharya Institute of Technology


Dynamic Memory Allocation

It is the process of allocating memory space during run time. This type of

memory allocation can be used in applications where the storage

requirement is unpredictable.

The following are the functions using which additional memory space can be

allocated or unwanted space can be deleted, thereby optimizing the use of

storage space.

Department of ISE Acharya Institute of Technology


Comparison of Static and Dynamic Memory Allocation
Sl. Static Memory Allocation Dynamic Memory Allocation
No
1 Memory is allocated during compilation time. Memory is allocated during run time.

2 The size of the allocated memory space is fixed and The size of the allocated memory space is not
it cannot be altered during execution. fixed and it can be altered (increased / decreased)
during execution.
3 This type of memory allocation can be used in This type of memory allocation can be used in
applications where the data size is fixed and known applications where the storage requirement is
before processing. unpredictable.
4 Execution is faster because memory is already Execution is slower because memory is has to be
allocated and only data manipulation is done. allocated and only then data manipulation is done.
5 Part of memory allocated is stack memory or Part of memory allocated is heap memory
global/static memory.
6 Ex: arrays Ex: Dynamic arrays, linked lists

Department of ISE Acharya Institute of Technology


1.malloc
Description: This function allocates and reserves a block of memory, specified
in bytes and returns a pointer to the first byte of the allocated space.
Syntax:
ptr = (datatype *) malloc (size);
Where - ptr is a pointer of type datatype
- datatype can be any of the basic data type or user
defined data type.
- size is the number of bytes required.
Example: ptr = ( int * ) malloc ( sizeof ( int ) );

Department of ISE Acharya Institute of Technology


On successful execution of this statement, a memory space equivalent to size

of int is reserved and the address of the first byte of the memory allocated is

assigned to the pointer ptr of type int.

Return Value – On success, it returns a pointer of type void to the newly

allocated block of memory. On failure i.e. if the specified size of memory is not

available, it returns NULL.

Department of ISE Acharya Institute of Technology


Department of ISE Acharya Institute of Technology
2.calloc
Description – This function allocates multiple blocks of same size, initializes
all locations to zero and returns a pointer to the first byte of allocated space.
Syntax:
ptr = (datatype *) calloc (n, size);
Where - ptr is a pointer of type datatype
- datatype can be any of the basic data type or user
defined data type.
- size is the number of bytes required.
- n is the number of blocks to be allocated of size bytes.

Department of ISE Acharya Institute of Technology


Example: ptr = ( int * ) calloc (200, sizeof ( int ) );

On successful execution of this statement, a memory space equivalent to size

of 200 int (array of 200 integers) is reserved and the address of the first byte

of the memory allocated is assigned to the pointer ptr of type int.

Return Value – On success, it returns a pointer of type void to the newly

allocated block of memory. On failure i.e. if the specified size of memory is

not available, it returns NULL.

Department of ISE Acharya Institute of Technology


Department of ISE Acharya Institute of Technology
3.realloc
Description – This function is used to alter the size of the previously allocated
space which is allocated either by using malloc or calloc function.
Syntax:
ptr = (datatype *) realloc (ptr, size);
Where - ptr is the starting address of allocated memory obtained previously
by calling malloc, calloc, or realloc functions.
- size is the number of bytes required for reallocation. The
size specified may be larger or smaller than the previously allocated memory.

Department of ISE Acharya Institute of Technology


Example:
If the original allocation is done by the statement
ptr = malloc(size);
Then reallocation of space may be done by the statement
ptr = realloc(ptr, newsize)
On successful execution of this statement, realloc allocates a new memory
space of size newsize to the pointer variable ptr and returns a pointer to the
first byte of the new memory block.
Return Value – On success, it returns a pointer to the newly allocated block of
memory. On failure i.e. if the specified size of memory is not available, it
returns NULL.

Department of ISE Acharya Institute of Technology


Department of ISE Acharya Institute of Technology
Note:

•The storage space allocated dynamically has no name and therefore its

contents can be accessed only through a pointer.

•It is the responsibility of a programmer to de-allocate memory whenever it

is not required by the application.

•In case of realloc( ), the contents of the old block will be copied into the

newly allocated space and so, this function guarantees that the earlier

contents are not lost.

Department of ISE Acharya Institute of Technology


4.free
Description – This function de-allocates (frees) the allocated block of
memory which is allocated by using the functions malloc( ), calloc( ) or
realloc( ).
Syntax: free(ptr);
Where ptr is a pointer to a memory block which has already been created by
invoking one of the 3 functions malloc( ), calloc( ) or realloc( ).
Return Value – None.

Department of ISE Acharya Institute of Technology


Department of ISE Acharya Institute of Technology
Department of ISE Acharya Institute of Technology
Problems with Dynamic Memory Allocation
1.Memory Leakage
This is a problem where in a part of the memory is reserved but is not
accessible to any of the applications.
Example: Consider the following program segment.
main ( )
{ int *a; Here, memory for the variable ‘a’ is
allocated twice. However, ‘a’ contains
a = (int *)malloc(sizeof (int) ); the address of most recently allocated
memory, thereby making the earlier
*a =10; allocated memory inaccessible i.e. the
memory location where the value 10 is
a = (int *)malloc(sizeof (int) ); stored is inaccessible to any of the
application and is not possible to free
*a =20; so that it can be reused.
}
Department of ISE Acharya Institute of Technology
2.Dangling Pointer
Any pointer pointing to a destroyed object or which does not contain a valid
address is called a dangling pointer.
Example: Consider the following program segment
main ( )
{
Here, if we de-allocate the memory
int *a; for the variable ‘a’ using free(a), the
a =(int *)malloc(sizeof(int)); memory location pointing to by it is
*a=20; returned to the free pool. Now the
pointer variable ‘a’ can be used, but
……. the contents pointed by that cannot
……. be used, because the pointer
free(a); variable ‘a’ does not contain a valid
address now and is called a dangling
} pointer.

Department of ISE Acharya Institute of Technology


Department of ISE Acharya Institute of Technology
Comparison of Malloc and Calloc
Sl. malloc ( ) calloc ( )
No

1 Syntax:ptr = (datatype*) malloc ( size ) Syntax:ptr = (datatype*) calloc (n, size )


(Takes only one argument which is the size of the (Takes 2 arguments, first is number of blocks to be
block) allocated and second is the size of each block)

2 Allocates a block of memory of specified size. Allocates multiple blocks of memory, each block
with same size.
3 Allocated space will not be initialized. Each byte of the allocated space is initialized to
zero.
4 Since no initialization takes place, time efficiency is calloc( ) is computationally more expensive because
higher than calloc( ) of zero filling but, occasionally, more convenient
than malloc( )
5 This function can allocate the required size of memory This function can allocate the required number of
even if the memory is not available contiguously but blocks contiguously. If the required memory cannot
available at different locations. be allocated contiguously, it returns NULL.

Department of ISE Acharya Institute of Technology


Functions to allocate memory for integers, floats, chars and double
1)Allocating memory for integers
int* MALLOC_INT(int n)
{ 2) Allocating memory for floats
int *x;
float* MALLOC_FLOAT(int n)
x=(int*)malloc(n*sizeof(int));
{
if(x==NULL)
float *x;
{
x=(float*)malloc(n*sizeof(float));
printf(“Insufficient memory\n”);
if(x==NULL)
exit(0);
{
}
printf(“Insufficient memory\n”);
return x;
exit(0);
}
}
return x;
}
Functions to allocate memory for integers, floats, chars and double
1)Allocating memory for integers
int* MALLOC_INT(int n)
{ 2) Allocating memory for floats
int *x;
float* MALLOC_FLOAT(int n)
x=(int*)malloc(n*sizeof(int));
{
if(x==NULL)
float *x;
{
x=(float*)malloc(n*sizeof(float));
printf(“Insufficient memory\n”);
if(x==NULL)
exit(0);
{
}
printf(“Insufficient memory\n”);
return x;
exit(0);
}
}
return x;
}
Functions to allocate memory for integers, floats, chars and double
3)Allocating memory for characters

char* MALLOC_CHAR(int n) 4)Allocating memory for double values


{
double* MALLOC_DOUBLE(int n)
char *x;
{
x=(char*)malloc(n*sizeof(char));
double *x;
if(x==NULL)
x=(double*)malloc(n*sizeof(double));
{
if(x==NULL)
printf(“Insufficient memory\n”);
{
exit(0);
printf(“Insufficient memory\n”);
}
exit(0);
return x;
}
}
return x;
}
The above functions have to be invoked appropriately as shown below:
P=MALLOC_INT(n);
Where n is the number of elements in array
Program Segment example1:
int *p;
p=MALLOC_INT(5);
above segment allocate 5 locations to store integer values. consider
size of integer is 2 bytes so, total 5*2 =10 bytes allocates for 5 integer
values.

Department of ISE Acharya Institute of Technology


Program Segment example 2: allocate memory for n floating point
numbers
float *p;
p=MALLOC_FLOAT(n);
Program Segment example 3: allocate memory for n characters
char *p;
p=MALLOC_CHAR(n);

It is not possible to write generalized function to allocate memory for


n elements of any data type in C. But it’s possible to write a
generalized macro in place of generalized function.
Department of ISE Acharya Institute of Technology
Macro to allocate memory for one or more items of any data type using
malloc
#define MALLOC(p,n,type) \
p=(type*)malloc(n*sizeof(type)); \
if(p==NULL) \
{ \
printf(“Insufficient memory\n”); \
exit(0); \
}

Department of ISE Acharya Institute of Technology


NOTE:
The symbol \ is an instruction given to the preprocessor that all the
lines following \ are continuation of the first line of that macro
definition.

Department of ISE Acharya Institute of Technology


PROGRAM Example: program to add two numbers using macro MALLOC

#include<stdio.h>
#define MALLOC(p,n,type)\ main()
{
p=(type*)malloc(n*sizeof(type));\ int *p1,*p2;
int sum;
if(p==NULL)\ MALLOC(p1,1,int);
{\ MALLOC(p2,1,int);

printf(“Insufficient memory\n”);\ *p1=10;


*p2=20;
exit(0);\ sum=*p1+*p2;
printf(“%d+%d=%d\n”,*p1,*p2,sum);
} }

Department of ISE Acharya Institute of Technology


Macro to allocate memory for one or more items of any data type
using calloc
#define CALLOC(p,n,type) \
p=(type*)calloc(n,sizeof(type)); \
if(p==NULL) \
{ \
printf(“Insufficient memory\n”); \
exit(0); \

Department of ISE Acharya Institute of Technology


PROGRAM Example: program to add two numbers using macro CALLOC

#include<stdio.h>
#define CALLOC(p,n,type) \ main()
{
p=(type*)calloc(n,sizeof(type)); \ int *p1,*p2;
int sum;
if(p==NULL)\ CALLOC(p1,1,int);
{ \ CALLOC(p2,1,int);
*p1=10;
printf(“Insufficient memory\n”); \ *p2=20;
sum=*p1+*p2;
exit(0); \ printf(“%d+%d=%d\n”,*p1,*p2,sum);
}
}

Department of ISE Acharya Institute of Technology


Macro to reallocate memory for one or more items of any data type
using realloc
#define REALLOC(p,n,type) \
p=(type*)realloc(p,n*sizeof(type)); \
if(p==NULL) \
{ \
printf(“Insufficient memory\n”); \
exit(0); \
}

Department of ISE Acharya Institute of Technology


PROGRAM Example: program to reallocate using macro REALLOC

#include<stdio.h>
#define REALLOC(p,n,type) \ void main()
{
p=(type*)realloc(p,n*sizeof(type)); \
Char *str;
if(p==NULL) \ str=(char*)malloc(15);
strcpy(str,”information”);
{ \ printf(“string=%s\n”,str);
REALLOC(str,60,char);
printf(“Insufficient memory\n”); \ strcpy(str,”information science and
Engineering”);
exit(0); \ printf(“string=%s\n”,str);
}
}

Department of ISE Acharya Institute of Technology


Two-Dimensional Arrays using pointer to pointer
For multidimensional arrays the concept of array-of-arrays is used. A 2-
dimensional array is
represented as a 1-dimensional array of pointers where each pointer contains
address of one
dimensional array.
EX: To represent a 2-dimensional array int a[3][5]; we create a 1-dimensional
array ‘a’ whose
length is 3; each element of ‘a’ is a 1-dimensional array whose length is 5.
The following shows the memory structure.

Department of ISE Acharya Institute of Technology


Department of ISE Acharya Institute of Technology
The element a[i][j] is found by first accessing the pointer in a[i]. This gives the address
of the zero th element of row ‘i’ of the array. Then by adding ‘j’ to this pointer the
address of the jth element of row ‘i’ is found
This means,
•The expression *(a + i) + j points to the jth element in the ith row i.e. *(a + i) + j = &a[i]
[j]
•The expression *( *(a + i) + j ) gives the value of the element in ith row and jth column
i.e. *( *(a + i) + j ) = a[i][j].

Department of ISE Acharya Institute of Technology


A 2-dimensional array with 3 rows and 5mcolumns can be created by allocating the memory
dynamically in two stages.
Stage 1: Allocate memory for specified number of row pointers.
Example: allocate memory for 3 row pointers using: MALLOC(x,3,int*);
Pictorial representation is shown below

In general
MALLOC(x,rows,int*); //rows-represents number of rows in a two dimensional array
Department of ISE Acharya Institute of Technology
Stage 2: Allocate memory for each row with specified number of column .
Example: Allocate memory for 5 columns with respect to row x[0],x[1] and x[2]
using MALLOC() three times as shown below.

Department of ISE Acharya Institute of Technology


By using both stages, we can write code (i.e program statements)in
general ,as shown below:
MALLOC(x,rows,int*) //Allocate memory for row pointers
for(i=0;i<rows;i++)
{
MALLOC(x[i],cols,int); //Allocate memory for specified number of columns
}
return x; //Return address of 0th row and 0th column

Department of ISE Acharya Institute of Technology


Now,the complete function to allocate memory for x[row][col] can
be written as shown below:
Example:Allocating memory for 2-dimensional array dynamically
int** make(int rows, int cols)
{
int **x,i;
MALLOC(x,rows,int*);
for(i=0;i<rows;i++)
MALLOC(x[i],cols,int);
return x;
}

Department of ISE Acharya Institute of Technology


STRUCTURES

Department of ISE Acharya Institute of Technology


Why structures?
If we want to store a number of data items of same datatype, we can use arrays.

However, if we want to store the information which is a collection of items of

dissimilar datatype, we cannot use arrays. This is where we use structures.

Department of ISE Acharya Institute of Technology


Structures Definition and Syntax
A structure is a collection or related information of possibly different datatype
under one name.
Syntax:
struct tagname
{
Where
datatype member1; struct is the keyword.
tagname is user defined name for structure.
datatype member2; datatype can be any of the basic datatype (int, float,
char etc) or user defined datatype.
.. member1, member2 are attributes of the structure
(also called members or fields).
..
};
Department of ISE Acharya Institute of Technology
Example:
struct student
{
char name[20];
int marks1;
int marks2;
int marks3;
char regno[10];
};

Department of ISE Acharya Institute of Technology


Just by defining a structure, memory will not be allocated for the various
fields. It simply describes a format called template to represent information.
If the structure is associated with a variable then the memory is allocated.
Various structure variable declaration forms
Format 1:struct student
{
char name[20];
int marks1;
int marks2;
int marks3;
char regno[10];
};
struct student a, b, c;

Department of ISE Acharya Institute of Technology


Format 2:
struct student
{
char name[20];
int marks1;
int marks2;
int marks3;
char regno[10];
}a, b, c;

Department of ISE Acharya Institute of Technology


Format 3: Using typedef
typedef struct
{ struct student
{
char name[20];
char name[10];
int marks1; int marks1;
or int marks2;
int marks2; int marks3;
char regno[10];
int marks3; };
typedef struct student STD;
char regno[20];
}STD;
Here STD is a new datatype of type struct student. Therefore
the statement
STD a, b;
creates 2 variables a, b of type STD.

Department of ISE Acharya Institute of Technology


Note:

The structure type declaration defines a template of the structure


and does not tell the compiler to reserve any space in memory.
Memory is allocated only when the structure is associated with a
variable.

Department of ISE Acharya Institute of Technology


Accessing structure fields or members
The fields of the structure can be accessed by using a dot operator ‘.’(member selection
operator).
Example: Consider the declaration
struct student
{ STD a;
char name[20]; Here ‘a’ is a variable of type STD and the
int marks1; elements of struct can be accessed as
int marks2; a.name, a.marks1, a.marks2, a.marks3 and
int marks3; a.regno.
char regno[10]; Note – Before the dot operator there must
always be a structure variable and after the
}; dot operator there must always be a
typedef struct student STD; structure member.

Department of ISE Acharya Institute of Technology


Assigning Values to Structure
Members
We can assign values like
in the program OR
strcpy(a.name, “Mahesh”);
a.marks1=97;
We can use scanf to five values through the keyboard
a.marks2=98; scanf(“%s”, a.name);
scanf(“%d%d%d”, &a.marks1, &a.marks2, &a.marks3);
a.marks3=99; scanf(“%s”, a.regno);
strcpy(a.regno, “1AY10IS001”);

Department of ISE Acharya Institute of Technology


Structure Initialization Structure Example:
struct book
Like primary variables and arrays, structure {
variables can also be initialized where they are char name[10];
declared. The format used is quite similar to that float price;
int pages;
used to initialize arrays.
};
Array example: struct book b1 = {“c++”, 150.00, 550};
struct book b2 = {“physics”, 150.80,
int num[6] = {2, 4, 12, 5, 45, 5}; 800};
OR
int num[ ] = {2, 4, 12, 5, 45, 5}; struct book
If the array is initialized where it is declared {
char name[10];
mentioning the dimension of the array is
float price;
optional. int pages;
} b1 = {“c++”, 150.00, 550}, b2 =
{“physics”, 150.80, 800};

Department of ISE Acharya Institute of Technology


Note – C language does not permit the initialization of individual
structure members within the template. The initialization must be
done only in the declaration of the actual variables.
Example:
struct person
{
int weight =60;
float height = 170.60;
}p1;
This is not permitted.

Department of ISE Acharya Institute of Technology


Array of structures
Suppose if we want to store data about a book, then the following structure
may be used.
struct book
{
char name[10];
float price;
int pages;
};
struct book b1={“c++”, 150.00, 570};
Now, if we want to store data of 100 books we would be required to use 100
different structure variables from b1 to b100 which is definitely not very
convenient.
A better approach would be to use an array of structures.

Department of ISE Acharya Institute of Technology


Assignment or Copying of Structure Variables
The values of a structure variable can be assigned to another structure
variable of the same type using the assignment operator ( = ). It is not
necessary to copy the structure elements or members piece-meal.
Obviously programmers prefer assignment to piece-meal copying.
struct employee struct employee e1 = {“Harish”, 30, 25000.00};
{ struct employee e2, e3;
char name[10];
int age; //piece-meal copying
float salary; strcpy(e2.name, e1.name);
}; e2.age = e1.age;
e2.sal = e1.sal;

//copying all elements at one go


e3 = e2;

Department of ISE Acharya Institute of Technology


Pointer to Structures void main( )
{
A variable which contains the address of a struct employee e1 = {“Harish”, 30, 25000.00};
structure variable is called pointer to a struct employee *ptr;
structure. The members of a structure can ptr = &e1;
be accessed very efficiently using pointers. //using de-referencing operator * and dot ( . )
operator
Example: Consider the following structure printf(“Name is %s \n”, (*ptr).name);
struct employee printf(“Age is %d \n”, (*ptr).age);
{ printf(“Salary is %f \n”, (*ptr).salary);
char name[10]; //using selection operator –>
printf(“Name is %s \n”, ptr–>name);
int age; printf(“Age is %d \n”, ptr –>age);
float salary; printf(“Salary is %f \n”, ptr –>salary);
}; }
Output:
Name is Harish
Age is 30
Salary is 25000.00
Name is Harish
Department of ISE Acharya Institute of Technology Age is 30
Salary is 25000.00
Difference between structures and
arrays
Arrays Structures

An array is a collection of related data Structure is a collection of variables of


elements of same datatype. similar or dissimilar datatype.

An array item can be accessed by using its Structure items can be accessed using ‘.’or
subscript or by using dereferencing / by using –> for pointers.
indirection (*) operator for pointers.

Department of ISE Acharya Institute of Technology


Union Syntax:
union tagname
Unions Definition and Syntax {
A union is a collection of related information of possibly
datatype member1;
different datatype under one name. It is a concept
derived from structures. The main features that datatype member2;
distinguish it form structures are
..
1. The amount of memory allocated is equal to the size
of the member that occupies largest space. ..
};
2. The memory allocated is shared by individual
Where
members of union. union is the keyword.
tagname is user defined name for union
datatype can be any of the basic datatype
(int, float, char etc) or user defined
datatype.
member1, member2 are attributes of the
union (also called members or fields).
Department of ISE Acharya Institute of Technology
Example:
union item
{
int i;
double d;
char c;
};
The definition of a union does not allocate any memory since the definition is
not associated with any variable.
The different forms of variable declarations for structures, holds good for
unions.
The union members are accessed exactly the same way in which the structure
elements are accessed i.e. using a ‘.’ operator.
The major difference between structures and unions is the way in which
memory is allocated.

Department of ISE Acharya Institute of Technology


Example: Consider the flowing declaration
struct a
This datatype would occupy 4 bytes in memory
{ key.i requires 2 bytes.
key.ch[0] requires 1 byte.
int i; key.ch[1] requires 1 byte.
This is as shown in the figure
char ch[2];
1002 1003 1004 1005
};
key.i key.ch[0] key.ch[1]
struct a key;
This datatype would occupy 4 bytes in Here the amount of memory allocated is the sum
memory of the storage specified for each of its members
(for the above example 4 bytes). Each member in
key.i requires 2 bytes. the structure is assigned its own unique storage
area (for the above example int i – 1002 to 1003,
key.ch[0] requires 1 byte. char ch[2] – 1004 to 1005).

key.ch[1] requires 1 byte.Department of ISE Acharya Institute of Technology


union a Here the amount of memory allocated is the size of the
key.ch[0] key.ch[1] member that occupies largest space. (for the above
{ 1002 1003 example int i – 2bytes, char ch[2] – 2bytes, therefore larger
int i; = 2 bytes). The memory allocated is shared by individual
key.i
members of union. (for the above example int i – 1002 to
char ch[2];
1003, char ch[2] – 1002 to 1003).
}; Note:
The same memory locations which are used for key.i are
union a key;
also used by key.ch[0] and key.ch[1]. It means that the
This datatype would occupy 2 bytes in memory locations used by key.i can also be accessed using
memory key.ch[0] and key.ch[1].
key.i , key.ch[0] , key.ch[1] – all share this 2
bytes.
This is as shown in the figure

Department of ISE Acharya Institute of Technology


Difference between structures and unions
Structure Union
1 The keyword ‘struct’ is used to start The keyword ‘union’ is used to start
the declaration of a structure. the declaration of a union.
2 The size of memory allocated by the The size of memory allocated by the
compiler is equal to or greater than the compiler is equal to the size of the
sum of sizes of its members. member that occupies largest space.
3 Memory allocated is unique (separate) Memory allocated is shared (common)
for all members declared within the for all the members declared within
structure. the union.
4 Altering the value of a member will Altering the value of any of the
not affect other members of the member will alter other member
structure. values.
5 Several members of a structure can be Only the first member of union can be
initialized at once. initialized.
6 Individual members can be accessed at Only one member can be accessed at a
a time. time.
Department of ISE Acharya Institute of Technology
POLYNOMIALS
Polynomials with one variable
Definition:-
A polynomial is a mathematical expression consisting of sum of terms where
each term is made up of a coefficient multiplied by a variables raised to a power.
Ex: A polynomial consisting of only one variable is shown below:
x4+10x3+3x2+1
Representation:-Each term consists of a coefficient multiplied by a variable
raised to a power. So, each term can be represented by a structure consisting of
2 fields namely:
•cf (representing coefficient)
•px (power of x)
Department of ISE Acharya Institute of Technology
The Structure definition for a term of a polynomial can be written as
shown below:-
typedef struct
{
int cf; //used to hold the coefficient
int px; //used to hold power of x
}POLY;
Consider the following declaration along with its memory
representation:
/*declaration*/
POLY p;
p
/*memory representation*/ cf pf

Department of ISE Acharya Institute of Technology


After memory is allocated ,the term 6x5 can be stored using variable p as shown
below:
6x5
p 6 5

cf px

Representation of complete polynomial:-


This can be done using array of structures with the following declaration:
typedef struct
{
int cf; //used to hold the coefficient
int px; //used to hold power of x
}POLY;
POLY p[10];
Department of ISE Acharya Institute of Technology
Using above declaration, we have an array of 10 terms.
Consider the following polynomial:
8x6+3x3+6x2+3x+4
It can be stored as an array of 5 terms as shown below:

Department of ISE Acharya Institute of Technology


Function to read a polynomial with n terms
void read_poly(POLY p[],int n)
{
int i,cf,px;
for(i=0;i<n;i++)
{
printf(“enter cf and px value”);
scanf(“%d%d”,&cf,&px);
p[i].cf=cf;
p[i].px=px;
}
}

Department of ISE Acharya Institute of Technology


Function to display a polynomial with n terms
void print_poly(POLY p[],int n)
{
int i;
for(i=0;i<n;i++)
{
if(p[i].cf<0)
printf(“%d”,p[i].cf);
else
printf(“+%d”,p[i].cf);
if(p[i].px!=0)
printf(“x^%d”,p[i].px);
}
printf(“\n”);
}

Department of ISE Acharya Institute of Technology


Addition of two polynomials:-
Poly 1:6x6+7x3+8x1+8 m=4 terms
Poly 2:8x7+4x6+7x3+3x2+4x n=5 terms
Poly 3: 10x6+14x3+12x1+8+8x7+3x2
Addition of two polynomial can be done by using linear search for
power of polynomial 1 in polynomial 2.

Department of ISE Acharya Institute of Technology


Function to search for term of poly1 in poly 2
int search(int px1,POLY p2[],int n)
{
int j,px2;
for(j=0;j<n;j++)
{
px2=p2[j].px
if(px1==px2)
return j;
}
return -1;
}

Department of ISE Acharya Institute of Technology


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:

for each term of polynomial 1


Step1: access each term of poly 1
Step2: search for power of above term in poly 2
Step3:if found in poly 2
Add the coefficients and add sum to poly 3
else
Add the term of poly 1 to poly 3
end for
Add remaining terms of poly 2 to poly 3

Department of ISE Acharya Institute of Technology


NOTE:
After adding the terms of both polynomials, immediately the term of
polynomial 2 should be removed.
This can be done by assigning -999 to coefficient field of the corresponding
term in poly 2.So, when all terms of polynomial 1 are scanned, we have to
copy the remaining terms of polynomial 2 into poly 3.The remaining terms
are the terms whose coefficient field is not -999. Now the function
copy_poly() can be written shown below.

Department of ISE Acharya Institute of Technology


Function to copy remaining terms of polynomial 2 into polynomial 3
int copy_poly(POLY p3[],int k,POLY p2[],int n)
{
int j;
for(j=0;j<n;j++)
{
if(p2[j].cf!=-999)
{
p3[k].cf=p2[j].cf;
p3[k].px=p2[j].px;
k++;
}
}
return k;
}
Department of ISE Acharya Institute of Technology
Polynomials with three variables
The polynomial with three variables is shown below
6x6y4z3+7x3yz2+8x3+8
Refer Notes for polynomial programs.

Department of ISE Acharya Institute of Technology


Teaching-Learning Process: Problem based learning (Implementation of different
programs to illustrate application of arrays and structures.
https://www.youtube.com/watch?v=3Xo6P_V-qns&t=201s
https://ds2-iiith.vlabs.ac.in/exp/selection-sort/index.html
https://ds1-iiith.vlabs.ac.in/data-structures-1/List%20of%20experiments.html

Department of ISE Acharya Institute of Technology


Department of ISE Acharya Institute of Technology

You might also like