Data structures and Applications 18CS32

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

1. INTRODUCTION

Basic Terminology of Data Organization:

Data: 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),
Data items which cannot be divided in to sub items are called elementary items
(Eg. Roll no, marks, city, pin code etc.).
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.
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,
eld 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.

Page 1
 Data structures and Applications 18CS32

EXAMPLE:
Attributes: Name Age Sex Roll Number Branch
A 17 M 109cs0132 CSE
Values:
B 18 M 109ee1234 EEE
Here, it is an example of student details where STUDENT is the given entity. Then
name, age, sex, 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 student details.

DATA STRUCTURE

ta Structure is a way of collecting and organizing data in such a way that the operations
on these data can be performed in an effective

can be defined as logical or mathematical model of a particular organization

of

cture is a representation of logical relationship existing between individual elements

data structure defines a way of organizing all data items that
considers not only the elements stored but also their relationship to each other. The term data
structure is used to describe the way data is stored.

Data Structures is about rendering data elements in terms of some relationship, for better
organization and storage in computer.

To develop a program of an algorithm we should select an appropriate data structure for that
algorithm. Therefore, data structure is represented as:
Algorithm + Data structure = Program
For example, data can be player's name "Virat" and age 26. Here "Virat" is of String data type
and 26 is of integer data type. This data can be recorded as a Player record. Now, it is possible to

"Gambhir" 31, "Sehwag" 33.

Data Structures are structures programmed to store ordered data, so that

Algorithms manipulate the data in these structures in order to accomplish some task

Page 2
 Data structures and Applications 18CS32

1.1 CLASSIFICATION OF DATA STRUCTURES

The logical or mathematical model of a particular organization of data is called a Data
Structure.

Data structures can be classified as

Primitive data structure

Non-Primitive data structure
Linear data structure
Nonlinear data structure

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
All these data structures allow us to perform different operations on data. The s e l e c t i o n of
these data structures is based on which type of operation is required.

Figure 1: Classification of data structure

Page 3
 Data structures and Applications 18CS32

Figure 1 gives the complete classification of the data structure.

Definitions:

A primitive data structure used to represent the standard data

types of any one of the c
structures. Simple data structure can be constructed with the help of primitive data structure.

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

primitive data structures.

Non primitive data structures can be futher classified as

1) Linear data structure
2) Non-linear data structure

Linear Data Structures:

can be constructed as a continuous arrangement of data elements in the
memory. In linear data structure the elements are stored in sequential order. In the linear Data Structures
the relationship of adjacency is maintained between the Data elements .It can be represented by using

The linear data structures are:

Array: Array is a collection of data of same data type stored in consecutive memory location
and is referred by common name
Stack: A stack is a Last-In-First-Out (LIFO) linear data structure in which insertion and deletion
takes place at only one end called the top of the stack.
Queue: A Queue is a First in First-Out (FIFO) linear data structure in which insertions takes
place one end called the rear and the deletions takes place at one end called the Front.
Linked list: Linked list is a collection of data of same data type but the data items need not be
stored in consecutive memory locations.

Page 4
 Data structures and Applications 18CS32

Non-Linear Data Structures:

Non-linear data structure can be constructed as a collection of randomly distributed set of

data item joined together by using a special pointer (tag). In non-linear Data structure the relationship of
adjacency is not maintained between the Data items. Elements are stored based on the hierarchical
relationship among the

The following are some of the Non-Linear data structure

Trees: Trees are used to represent data that has some hierarchical relationship among the data
elements.(as shown in figure 2)

Figure 2: Trees
Graph: Graph is used to represent data that has relationship between pair of elements not
necessarily hierarchical in nature. For example electrical and communication networks, airline
routes, flow chart, graphs for planning projects.(as shown in figure 3)

Figure 3: Graph
1.2 DATA STRUCTURE OPERATIONS
The data in the data structures are processed by certain operations. The particular data structure
chosen largely depends on the frequency of the operation that needs to be performed on the data
structure.
Traversing
Searching
Insertion

Page 5
 Data structures and Applications 18CS32

Deletion
Sorting
Merging

(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.
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.
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.
1.3 REVIEW OF STRUCTURES, UNIONS AND POINTERS
STRUCTURE DEFINITION
is a collection of data items of same or dissimilar data type. Each data item is
identified by its name and type. (Or) A Structure is a user defined data type that can store related
information together. (Or) A structure is a collection of different data items / heterogeneous data items

Page 6
 Data structures and Applications 18CS32

under a single name. The variable within a structure are of different data types and each has a name
that is used to select it from the structure.
C arrays allow you to define type of variables that can hold several data items of the same kind
but structure is another user defined data type available in C programming, which allows you to
combine data items of different kinds.
Structures are used to represent a record, Suppose, track of books are kept in a library are
recorded then it is required to track the following attributes about each book:
Title
Author
Subject
Book ID

STRUCTURE DECLARATION
It is declared using a keyword struct followed by the name of the structure. The members of the
structure are declared within the structure.

Example:
struct struct-name
{
data_type1 member_name1;
data_type2 member_name2;
.. ..
data_typen member_namen;
}structurevariablename;

STRUCTURE INITIALIZATION
Assigning values to the data members of the structure is called initializing of structure.
Syntax:
struct struct_name
{
data _type member_name1;
data _type member_name2;
} structure variable={constant1,constant2};

Page 7
 Data structures and Applications 18CS32

Accessing the Members of a structure :-

A structure member variable is generally accessed using a .
Syntax: structurevariable.member_name;
The dot operator is used to select a particular member of the structure. To assign value to the individual
Data members of the structure variable stud, it is written as,
stud.roll=01;

To input values for data members of the structure variable stud, can be written as,
tud.roll);

To print the values of structure variable stud, can be written as:

Example for structure:

struct employee
{
char name[10];
int age;
float salary;
}person;

Here struct is a keyword.

This example creates a variable whose name is person and that has three fields
A name that is a character array
An integer value Age
A float value salary
The . (Dot operator) is used as the structure member operator to select a particular member of the
structure.
Example:
person.age=20;
person.salary=40000;

Page 8
 Data structures and Applications 18CS32

Program to create a struct person , initializes its data member and print their values
#include<stdio.h>
#include<conio.h>
void main()
{
struct person{
char name[10];
int age;
float salary;
};
struct person p1;
clrscr();
strcpy(p1.name,"james");
p1.age=10;
p1.salary=35000;
printf("\n name=%s age=%d salary=%f",p1.name,p1.age,p1.salary);
getch();
}

ARRAY OF STRUCTUREs
An array of structure can also be declared. Each element of the array representing a structure
variable.
Example : struct employee emp[5];
The above code define an array emp of size 5 elements. Each element of array emp is of type employee
#include<stdio.h>
#include<conio.h>
struct employee
{
char ename[10];
int sal;
};
struct employee emp[5];
int i,j;
void ask()
{
for(i=0;i<3;i++)
{
printf("\nEnter %dst employee record\n",i+1);
printf("\nEmployee name\t");
scanf("%s",emp[i].ename);
printf("\nEnter employee salary\t");
scanf("%d",&emp[i].sal);
}
printf("\nDisplaying Employee record\n");
for(i=0;i<3;i++)
{
printf("\nEmployee name is %s",emp[i].ename);

Page 9
 Data structures and Applications 18CS32

printf("\nSlary is %d",emp[i].sal);
}
}
void main()
{
clrscr();
ask();
getch();
}

Type definitions and structures

It is possible to create our own data types (user defined)by using typedef statement as below
typedef struct
{
char name[10];
int age;
} humanbeing;
Here humanbeing is the name of the type defined by structure definition and we may follow this
definition with declarations of variables such as humanbeing person1, person2;
Structures cannot be directly checked for equality or nor equality. i.e. directly using
person1==person2 is not allowed. If each individual data member is checked for equality then
the entire structure can be checked for equality.

Function to Check equity of two structures

#define FALSE 0
#define TRUE 1
int humansEqual(humanBeing person1, humanBeing person2))
{
if(strcmp(person1.name,person2.name))
return FALSE;
if((person1.age!=person2.age)
return FALSE;
if((person1.salary!=person2. salary)
return FALSE;
return TRUE;
}
void main()
{
if(humansEqual(person1,person2))
\
else

Page 10
 Data structures and Applications 18CS32

Program to check equality to structure variables.

#include<stdio.h>
#include<conio.h>
#define FALSE 0
#define TRUE 1
typedef struct
{
char name[10];
int age;
float salary;
}humanbeing;
int humansEqual(humanbeing p1,humanbeing p2)
{
if(strcmp(p1.name,p2.name))
return FALSE;
if(p1.age!=p2.age)
return FALSE;
if(p1.salary!=p2.salary)
return FALSE;
else
return TRUE;
}
void main()
{
humanbeing p1,p2;
clrscr();
strcpy(p1.name,"hiiiii");p1.age=12;p1.salary=12000;
strcpy(p2.name,"hi");p2.age=12;p2.salary=12000;
if(humansEqual(p1,p2))
printf("\n persons are same ");
else
printf("\n persons are not same");
getch();
}

POINTERS TO STRUCTURES
Pointer to a structure is a variable that holds the address of a structure. The syntax to declare
pointer to a structure can be given as:
strcut struct_name *ptr;
eg: struct stud *ptr_stud;
To assign address of stud to the pointer using address operator(&) we would write ptr_stud=&stud; To
access the members of the structure (->) operator is used.
for example
ptr_stud->name=Raj;

Page 11
 Data structures and Applications 18CS32

NESTED STRUCTURES

It is possible to embed a structure within a structure.

structure variable as its members is called a nested structure or a structure within a structure is

The structure should be declared separately and then be grouped into high level structure. The
data members of the nested structures can be accessed using (.) Dot operator.
Syntax to follow while accessing the data members of inner structure in nested structure with dot
operator is outer most structure variable. inner most structure variable. inner data member
;
Syntax to followed while accessing the data members of outer structure in nested structure with
dot operator is outer most structure variable .outer data member ;
Type1: declaring structure within a structure
Example :
struct student
{
char name[20];
int marks;
float per;
struct dob
{
int day,month,year;
}date;
}s1;
void main()
{
\n enter the student details-
,&s1. date.month,
&s1.date.year);

\
s1.date.day,s1.date.month,s1. date.year);
getch();
}
Type 2: declaring a structure variable of one within another structure
Example :
struct dob
{
int day,month,year;

Page 12
 Data structures and Applications 18CS32

};
struct student
{
char name[20];
int marks;
float per;
struct dob date;
}s1;
void main()
{
\n enter the student details-
sc
&s1.date.year);

\
s1.date.day,s1.date.month,s1.date.year);
getch();
}
Nested structures with typedef
Example :
typedef struct
{
int month;
int day;
int year;
}date;

typedef struct
{
char name[10];
int age;
salary;
date dob;
}humanbeing;
humanbeing person1,person2;

If humanbeing person1 and person2 declares person1 and person2 variables of type humanbeing.
Then consider a person born on feb 11, 1944, can have the values for the date struct set as:
person1.dob.month=2;
person1.dob.day=11;
person1.dob.year=1944;
Similarly for considering person2, his dob is 3rd December 1956 then
person2.dob.month=12;

Page 13
 Data structures and Applications 18CS32

person2.dob.day=3;
person2.dob.year=1956;
Program for illustration of nested structures with typedef
#include<stdio.h>
#include<conio.h>
void main()
{
typedef struct
{
int month;
int day;
int year;
}date;
typedef struct
{
char name[10];
int age;
salary;
date dob;
}humanbeing;
humanbeing person1;
strcpy(person1.name,"james");
person1.age=10;
person1.salary=35000;
Person1.dob.month=2;
Person1.dob.day=11;
Person1.dob.year=1944;
\n details of t
printf("\n name=%s age=%d salary=%f dob=%d-%d-%d",person1.name,
person1.age,person1.salary,Person1.dob.day,Person1.dob.month,Person1.dob.year);
getch();
}

UNIONS
Union is a collection of variables of different data types. Union information can only be stored in
one field at any one time.
A union is a special data type available in C that enables you to store different
data types in the same memory location.
union can define many members, but only one member can contain a value at any given time.
Unions provide an efficient way of using the same memory location for multi-purpose.

Declaring Union:
union union-name
{
data_type1 member_name1;

Page 14
 Data structures and Applications 18CS32

data_type2 member_name2;
.. ..
data_typen member_namen;
}union variablename;

Example:
union data
{
char a;
int x;
float f;
}mydata;

The union tag is optional and each member definition is a normal variable definition, such as int
i; or float f; or any other valid variable definition.
At the end of the union's definition, before the final semicolon, you can specify one or more
union variables but it is optional. The memory occupied by a union will be large enough to hold the
largest member of the union. For example, in above example Data type will occupy 4 bytes of memory
space because this is the maximum space which can be occupied by float data.

Accessing a Member of a Union

#include <stdio.h>
#include <string.h>
union Data
{
int i;
float f;
char str[20];
};
int main( )
{
union Data data;
data.i = 10;
data.f = 220.5;
strcpy( data.str, "C Programming");
printf( "data.i : %d\n", data.i);
printf( "data.f : %f\n", data.f);
printf( "data.str : %s\n", data.str); return 0;
}

Page 15
 Data structures and Applications 18CS32

Dot operator can be used to access a member of the union. The member access operator is coded
as a period between the union variable name and the union member that we wish to access.

Program to illustrate union with in a structure.

#include<stdio.h>
#include<conio.h>
typedef struct
{
enum tagfield {female,male} sex;
union
{
int child;
int beard;
}u;
}sextype;
typedef struct
{
int m,d,y;
}date;
typedef struct
{
char name[10];
int age;
float salary;
date dob;
sextype sexinfo;
}humanbeing;
void main()
{
humanbeing p1;
p1.dob.m=2;
p1.dob.d=11;
p1.dob.y=1994;
p1.sexinfo.sex=female;
p1.sexinfo.u.child=4;
printf("year=%d/%d/%d",p1.dob.m,p1.dob.d,p1.dob.y);
printf("\n sex=%d b=%d",p1.sexinfo.sex,p1.sexinfo.u. child);
getch();
}

Page 16
 Data structures and Applications 18CS32

1.4 SELF REFERENTIAL STRUCTURES

referential structures are those structures that contain a reference to data of its same
type as that of structure. i.e one or more of the components of the structure will be a pointer to

Example 1
struct node
{
int val;
struct node*next;
}list;
Example 2:
typedef struct
{
char data;
struct list * link;
}list;
In this example each instance of the structure list have two components data and link.
Data is a single character, while link is a pointer to a list structure.
The value of link is either the address in memory of an instance of list or NULL pointer.

Program to illustrate self-referential structures

#include <stdio.h>
#include <conio.h>
typedef struct
{
char data;
struct list *link;
}list;
void main()
{
list l1,l2,l3;
l1.data='a';
l2.data='b';
l3.data='c';
l1.link=&l1;
l2.link=&l2;
l3.link=&l3;
printf("\n data values of l1=%d,l2=%d,l3=%d",l1.data,l2.data,l3.data);
printf("\n link of l1,l2,l3=%d %d %d",l1.link,l2.link,l3.link);
getch();
}

Page 17
 Data structures and Applications 18CS32

Difference between structure and union

1.The keyword struct is used to define a 1. The keyword union is used to define a union.
structure
2. When a variable is associated with a 2. When a variable is associated with a union,
structure, the compiler allocates the memory the compiler allocates the memory by
for each member. considering the size of the largest memory.
The size of structure is greater than or equal to So, size of union is equal to the size of largest
the sum of sizes of its members. The smaller member.
members may end with unused slack bytes.
3. Each member within a structure is assigned 3. Memory allocated is shared by individual
unique storage area of location. members of union.
4. The address of each member will be in 4. The address is same for all the members of a
ascending order. This indicates that memory union. This indicates that every member begins
for each member will start at different offset at the same offset value.
values.
5 Altering the value of a member will not 5. Altering the value of any of the member will
affect other members of the structure. alter other member values.
6. Individual member can be accessed at a time 6. Only one member can be accessed at a time.
7. Several members of a structure can initialize 7. Only the first member of a union can be
at once. initialized.
Ex: struct Book Ex: union Book
{ {
int isbn; int isbn;
float price; float price;
char title[20]; char title[20];
}book; }book;
Total memory reserved will be Total memory reserved will be
Sizeof(int)+sizeof(float)+(20*sizeof(char)) Max(Sizeof(int)+sizeof(float)+(20*sizeof(char))

1.5 POINTERS
are variables that hold address of another variable of same dat
Pointers are one of the most distinct and exciting features of C language. It provides power and
flexibility to the language.
Benefit of using pointers
Pointers are more efficient in handling Array and Structure.
Pointer allows references to function and thereby helps in passing of function as arguments to
other function.
It reduces length and the program execution time.
It allows C to support dynamic memory management.

Page 18
 Data structures and Applications 18CS32

Concept of Pointer
Whenever a variable is declared, system will allocate a location to that variable in the memory,
to hold value. This location will have its own address number. Let us assume that system has allocated
memory location 80F for a variable a.
Example : int a = 10 ;

The value 10 can be accessed by either using the variable name a or the address 80F.Since the
memory addresses are simply numbers they can be assigned to some other variable. The variable that
holds memory address are called pointer variables. A pointer variable is therefore nothing but a
variable that contains an address, which is a location of another variable. Value of pointer variable will
be stored in another memory location.

Figure 5: Pointer variable

Declaring a pointer variable
General syntax of pointer declaration is, data-type *pointer_name;
Data type of pointer must be same as the variable, which the pointer is pointing. void type
pointer works with all data types, but isn't used oftenly.

Initialization of Pointer variable

Pointer Initialization is the process of assigning address of a variable to pointer variable.
Pointer variable contains address of variable of same data type. In C language address operator & is
used to determine the address of a variable. The & (immediately preceding a variable name) returns the
address of the variable associated with it.
int a = 10 ;
int *ptr ; //pointer declaration

Page 19
 Data structures and Applications 18CS32

ptr = &a ; //pointer initialization

or,
int *ptr = &a ; //initialization and declaration together

Pointer variable always points to same type of data.

float a;
float *ptr;
ptr = &a;

Dereferencing of Pointer
Once a pointer has been assigned the address of a variable. To access the value of variable, pointer is
dereferenced, using the indirection operator *.
void main()
{
int a,*p;
a = 10;
p = &a;
printf("%d",*p); //this will print the value of a.
printf("%d",*&a); //this will also print the value of a.
printf("%u",&a); //this will print the address of a.
printf("%u",p); //this will also print the address of a.
printf("%u",&p); //this will also print the address of p.
}
Pointer and Arrays
When an array is declared, compiler allocates sufficient amount of memory to
contain all the elements of the array. Base address which gives location of the first element is also
allocated by the compiler.
Suppose we declare an array arr,
int arr[5]={ 1, 2, 3, 4, 5 };
Assuming that the base address of arr is 1000 and each integer requires two byte,
the five element will be stored as follows in figure 6

Figure 6: Array Representation

Here variable arr will give the base address, which is a constant pointer pointing to
the element, arr[0]. Therefore arr is containing the address of arr[0] i.e 1000.
We can declare a pointer of type int to point to the array arr.

Page 20
 Data structures and Applications 18CS32

int *p;
p = arr;
or p = &arr[0]; //both the statements are equivalent.
Now we can access every element of array arr using p++ to move from one element to another. NOTE
: You cannot decrement a pointer once incremented. p-- won't work.
Pointer to Array
As studied above, we can use a pointer to point to an Array, and then we can use
that pointer to access the array. Lets have an example,
int i;
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);
p++;
}
In the above program, the pointer *p will print all the values stored in the array one by one. We can also
use the Base address (a in above case) to act as pointer and print all the values.

what will be the result

ting index

array

array

array

a[0] only

a++; compile time error, we cannot change base address of the array.

Pointers to multidimensional array

A multidimensional array is of form, a[i][j] . Lets see how we can make a pointer point to such
an array. As we know now, name of the array gives its base address. In a[i][j] , a will give the base
address of this array, even a+0+0 will also give the base address, that is the address of a[0][0] element.
Here is the generalized form for using pointer with multidimensional arrays.
*(*(ptr + i) + j) is same as a[i][j]
2. ARRAYS
Array is a container which can hold fix number of items and these items should be of same
type. Most of the data structures make use of array to implement their algorithms. Following are

Page 21
 Data structures and Applications 18CS32

important terms to understand the concepts of Array.

An array is a data structure that is a collection of variables of one type that are accessed
through 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.
Element
Index of an element in an array has a numerical index which is used to identify
the element.

2.1 ARRAY REPRESENTATION

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

Figure 8a: Array with 10 elements

Figure 8b: Array index

As per above shown illustration, following are the important points to be considered.(As shown in
figure 8a and figure 8b)
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.

ADT ARRAY
Objects: A set of pairs<index,value > where for each of index there is a value from the set item. Index
is a finite ordered set of one or more dimensions , for example -1} for one dimension, { (0 ,0
),(0,1),(0.2),(1,0),(1,2),(1,1),(2,1),(2,2),(2,0))} for two dimensions etc.

Page 22
 Data structures and Applications 18CS32

Functions:
For all A C Array, I C index, x C item, j, size C integer
1. Array create (j, list) = return an array of j dimensions where list is a j-tuple whose ith element is the
size of ith dimension. Items are undefined.
2. Item retrieve (A, i) = if (I C index) return the item associated with index value i in array A else return
error.
3.array store (A, i, x) = if (i in index) return an array that is identical to array A expect the new pair
<i,x> has been inserted else return error.
end Array

One Dimensional Array

Declaration:
Before using the array in the program it must be declared
Syntax: data_type array_name[size];
Where , 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.

Initialization:
Initialize arrays at the time of declaration.
Syntax:
Where ,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;
NOTE:
1. address of an data element in the array can be calculated as:
A[K]=BA(A)+W(K-LOWERBOUND);

Page 23
 Data structures and Applications 18CS32

Where, A is an array, K is the index of the element for which address has to be calculated ,BA is
the base address of the array A,and W is the size of one element in memory
2. calculating the length of an array
Length = Upperbound-Lowerbound+1
Where , upperbound is index of the last element and lowerbound is index of the first element in
the array

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.
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
{

}
for(i=0;i<=2;i++) //display the array values
{
\
}
}

Example: C Program to Increment every Element of the Array by one & Print Incremented
Array.
#include <stdio.h> void main()
{
int i;
int array[4] = {10, 20, 30, 40};
for (i = 0; i < 4; i++)
arr[i]++;
for (i = 0; i < 4; i++)
printf("%d\t", array[i]);
}

2.2 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.

Page 24
 Data structures and Applications 18CS32

Search given key

Sorting: arranging the elements in some type of order.
Merging: Combing two lists into a single list.

Traversing linear arrays

Let A be the array in the memory of the computer. If the operation requied 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.

INSERT(LA,N,K,ITEM)
HERE LA is a linear array with N elements and K is a positive integer such that K<=N. this
algorithm inserts an element ITEM into Kth position in LA.
1.[Initalize the counter]. Set J=N.
2.repeat steps 3 and 4 while J>=K
3.[move jth element downward] set LA[J+1]=LA[J].
4.[Decrease the counter] set J=J-1
[end of step 2 loop]
5.[insert element] set LA[K]A=ITEM
6.[reset N] set N=N+1
7.Exit

DELETE(LA,N,K,ITEM)
HERE LA is a linear array with N elements and K is a positive integer such that K<=N. this
algorithm deletes an element ITEM into Kth position in LA.
1. Set ITEM=LA[K]
2. repeat for J=K to N-1
3.[move j+1st element upward] set LA[J]=LA[J+1].
4.[end of step 2 loop]
5.[reset N] set N=N-1
6.Exit

BUBBLE SORT(DATA,N)
Here DATA is an array with N elements . THIS Algorithm sorts the elemts in DATA.
1. repeat steps 2 and 3 for k=1 to N-1

Page 25
 Data structures and Applications 18CS32

2. [Initalize the pass pointer PTR]. Set PTR=1.

3. Repeat while PTR<=N-K :[Executes pass]
(a) if DATA[PTR]>DATA[PTR+1] then
Interchange DATA[PTR] and DATA[PTR+1]
[end of IF structure]
(b) set PTR=PTR+1
[End of inner loop]
[end of step1 outer loop]
4.Exit

LINEAR SEARCH(DATA,N,ITEM,LOC)
Here DATA is a linear array with N elements and ITEM is a given item of information. this
algorithm finds the location LOC of item in DATA or set LOC=0 if the search is unsuccessful
1.[Insert ITEM at the end of DATA]. Set DATA[N+1]=ITEM.
2.[initialize the counter] set LOC=0,FOUND=0
3.[Search for ITEM]
Repeat for j=0 to N-1
If(ITEM=DATA[J]) then SET FOUND=1 and break
[end of loop]
4.[Succesful?] if FOUND=1Then SUCCESSFUL
else UNSUCCESSFUL
6.Exit

BINARY SEARCH(DATA,LB,UB,ITEM,LOC)
Here DATA is a sorted array with lower bound LB and upper bound UB and ITEM is a given
item of information. The variables BEG, END and MID denote respectively the beginning, end and
middle locations of a segment of elements of data. This algorithm finds the location LOC of item in
DATA or sets LOC=NULL
1.[Initialize segment variables ].
Set BEG=LB,END=UB and MID=INT((BEG+END)/2);
2. repeat steps 3 and 4 while BEG<=END and DATA[MID]!=ITEM
3. if ITEM<DATA[MID] then
Set END=MID-1

Page 26
 Data structures and Applications 18CS32

ELSE
Set BEG=MID+1
[end of loop]
4. set MID=INT(BEG+END)/2
5. if DATA[MID]=ITEM Then
set LOC=MID
else
set LOC=NULL
6.Exit

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];
Where, Rowsize specifies the no.of rows Columnsize specifies the no.of columns.
Example: int a[4][5];
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]
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} };

2D ARRAY REPRESENTATION USING COLUMN MAJOR ORDER AND ROW MAJOR

ORDER

1. In case of Column Major Order:

The formula is:

Page 27
 Data structures and Applications 18CS32

LOC (A [J, K]) = Base (A) + w [M (K-1) + (J-1)]

Here
LOC (A [J, K]) : is the location of the element in the Jth row and Kth column.
Base (A) : is the base address of the array A.
w : is the number of bytes required to store single element of the array A.
M : is the total number of rows in the array.
J : is the row number of the element.
K : is the column number of the element.
E.g.
A 3 x 4 integer array A is as below:
Subscript Elements Address
(1,1) 10 1000
(2,1) 20 1002
(3,1) 50 1004
(1,2) 60 1006
(2,2) 90 1008
(3,2) 40 1010
(1,3) 30 1012
(2,3) 80 1014
(3,3) 75 1016
(1,4) 55 1018
(2,4) 65 1020
(3,4) 79 1022

Suppose we have to find the location of A [3, 2]. The required values are:
Base (A) : 1000
w : 2 (because an integer takes 2 bytes in memory)
M : 3
J : 3
K : 2
Now put these values in the given formula as below:
LOC (A [3, 2]) = 1000 + 2 [3 (2-1) + (3-1)]
= 1000 + 2 [3 (1) + 2]

= 1000 + 2 [3 + 2]

= 1000 + 2 [5]

= 1000 + 10 = 1010

2. In case of Row Major Order:

The formula is:
LOC (A [J, K]) = Base (A) + w [N (J-1) + (K-1)]
Here

Page 28
 Data structures and Applications 18CS32

LOC (A [J, K]) : is the location of the element in the Jth row and Kth column.
Base (A) : is the base address of the array A.
w : is the number of bytes required to store single element of the array A.
N : is the total number of columns in the array.
J : is the row number of the element.
K : is the column number of the element.
E.g.
A 3 x 4 integer array A is as below:
Subscript Elements Address

(1,1) 10 1000
(1,2) 60 1002
(1,3) 30 1004
(1,4) 55 1006
(2,1) 20 1008
(2,2) 90 1010
(2,3) 80 1012
(2,4) 65 1014
(3,1) 50 1016
(3,2) 40 1018
(3,3) 75 1020
(3,4) 79 1022

Suppose we have to find the location of A [3, 2]. The required values are:
Base (A) : 1000
w : 2 (because an integer takes 2 bytes in memory)
N : 4
J : 3
K : 2
Now put these values in the given formula as below:
LOC (A [3, 2]) = 1000 + 2 [4 (3-1) + (2-1)]
= 1000 + 2 [4 (2) + 1]
= 1000 + 2 [8 + 1]
= 1000 + 2 [9]
= 1000 + 18
= 1018
Example 1:
Write a C program to find sum of two matrices
#include <stdio.h>
#include<conio.h>

Page 29
 Data structures and Applications 18CS32

void main()
{
float a[2][2], b[2][2], c[2][2];
int i,j;
clrscr();
printf("Enter the elements of 1st matrix\n");
/* Reading two dimensional Array with the help of two for loop. If there is an array of 'n'
dimension, 'n' numbers of loops are needed for inserting data to array.*/
for(i=0;i<2;I++)
for(j=0;j<2;j++)
{
scanf("%f",&a[i][j]);
}
printf("Enter the elements of 2nd matrix\n");
for(i=0;i<2;i++)
for(j=0;j<2;j++)
{
scanf("%f",&b[i][j]);
}
/* accessing corresponding elements of two arrays. */ for(i=0;i<2;i++)
for(j=0;j<2;j++)
{
c[i][j]=a[i][j]+b[i][j]; /* Sum of corresponding elements of two arrays. */
}
/* To display matrix sum in order. */
printf("\nSum Of Matrix:");
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
printf("%f\t", c[i][j]);
printf("\n");
}
getch();
}
Example 2: Program for multiplication of two matrices
#include<stdio.h>
#include<conio.h>
int main()
{
int i,j,k;
int row1,col1,row2,col2,row3,col3;
int mat1[5][5], mat2[5][5], mat3[5][5];
clrscr();

Page 30
 Data structures and Applications 18CS32

\n enter the nu

if(col1 != row2)
{
\n The number of columns in the first matrix must be equal to the number of rows

getch(); exit();
}
row3= row1; col3= col2;
\
for(i=0;i<row1;i++)
{
for(j=0;j<col1;j++)
[i][j]);
}
\
for(i=0;i<row2;i++)
{
for(j=0;j<col2;j++)

}
for(i=0;i<row3;i++)
{
for(j=0;j<col3;j++)
{
mat3[i][j]=0;
for(k=0;k<col3;k++)
mat3[i][j] +=mat1[i][k]*mat2[k][j];
}
}
prin \
for(i=0;i<row3;i++)
{
\
for(j=0;j<col3;j++)
\
}

Page 31
 Data structures and Applications 18CS32

return 0;
}
Output:
Enter the number of rows in the first matrix: 2
Enter the number of columns in the first matrix: 2
Enter the number of rows in the second matrix: 2
Enter the number of columns in the second matrix: 2
Enter the elements of the first matrix
1234
Enter the elements of the second matrix
5678
The elements of the product matrix are
19 22
43 50

Example 3: Program to find transpose of a matrix.

#include <stdio.h>
int main()
{
int a[10][10], trans[10][10], r, c, i, j;
printf("Enter rows and column of matrix: ");
scanf("%d %d", &r, &c);
printf("\nEnter elements of matrix:\n");
for(i=0; i<r; i++)
for(j=0; j<c; j++)
{
printf("Enter elements a%d%d: ",i+1,j+1);
scanf("%d", &a[i][j]);
}
/* Displaying the matrix a[][] */ printf("\n Entered Matrix: \n");
for(i=0; i<r; i++)
for(j=0; j<c; j++)
{
printf("%d ",a[i][j]);
if(j==c-1)
printf("\n\n");
}
/* Finding transpose of matrix a[][] and storing it in array trans[][]. */
for(i=0; i<r;i++)
for(j=0; j<c; j++)
{
trans[j][i]=a[i][j];
}

Page 32
 Data structures and Applications 18CS32

/* Displaying the array trans[][]. */ printf("\nTranspose of Matrix:\n");

for(i=0; i<c;i++)
for(j=0; j<r;j++)
{
printf("%d ",trans[i][j]);
if(j==r-1)
printf("\n\n");
}
return 0;
}

2.4 DYNAMICALLY ALLOCATED ARRAYS

Array can be dynamically allotted using malloc(), calloc() or realloc() functions, similarly the
allotted memory can be freed after the use of array using free() function.
One dimensional array
When large programs are written, it is difficult to determine how large array to use. So, solution
to this problem is to defer this decision to runtime and allocate the required array size. The advantage of
dynamic array is that the memory for the array of any desired size can be allotted. There is no need to
declare a fixed size array.
During the use of dynamically allocated arrays the following changes are required in first few
lines of main function of program
int i ,n,*list;
\n ent

if(n<1)
{
\
exit(EXIT_FAILURE);
}
MALLOC(list,n*sizeof(int));
This above main function fails only when n<1 or when sufficient memory is not allotted.

Example program for illustration of use of dynamic array:-

#include<stdio.h>
#include<stdlib.h>
void main()
{
int i,n;
int *ptr;
\n enter the number of elements\

ptr=(int*)malloc(sizeof(int)*n);
if(ptr==NULL)

Page 33
 Data structures and Applications 18CS32

{
\
return;
}
\
for(i=0;<n;i++)

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

getch();
}

Two dimensional array

A two dimensional array is represented as a one dimensional array in which each element is itself
a one dimensional array.(As shown in figure 9)
int x[3][5];
Here, actually a one dimensional array x is created whose length is 3 and each element of x is a one
dimensional array whose length is 5.
[0] [1] [2] [3] [4]

x[0]
x[1]
x[2]
Figure 9: Two dimensional array
C finds the element x[i][j] by first accessing the point in x[i].this pointer gives the address in memory of
the zeroth element of row I of the array. Then by adding j*sizeof(int) to this pointer , the address of the
[j]th elemnt of row i is determined.
Example program for allocating memory dynamically for 2D array
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
void main()
{
int **a;
int p,q;
int **make2darray();
\
sc
\

a=make2darray(p,q);

getch();

Page 34
 Data structures and Applications 18CS32

}
int **make2darray(int rows,int cols)
{
int **x,i;
x=malloc(rows*sizeof(*x));
for(i=0;i<rows;i++)
x[i]=malloc(cols*sizeof(**x));
return x;
}
2.4 APPLICATIONS OF ARRAYS
The two major applications of the arrays are polynomial and sparse matrix
1. 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.
Examples :
A(x) = 3x20+2x5+4
B(x) = x4+10x3+3x2+1
The largest exponent of a polynomial is called its degree.
In the above example, degree of first polynomial is 20 and for the second polynomial it is 4.
Note: Coefficients that are zero are not displayed, the term with exponent zero does not show the
variable i.e. 4x2+5x+1 where 1 is a term having exponent zero so variable is not displayed.
Operations on polynomials
Addition
Subtraction
Multiplication
But division is not allowed.

Polynomial addition is defined as :

i i i
Assume ix and jx then i+bj)x
i i
ix jx ))

Polynomial representation
In c, typedef is used to create the polynomial as below:-
#define MAX_DEGREE 101
typedef struct
{
int degree;
float coef[MAX_DEGREE];
}polynomial;
polynomial a;

Page 35
 Data structures and Applications 18CS32

i
Conisder a is of type polynomial and n>MAX_DEGREE then polynomial ix for i=0 to n
would be represented as
a.degree=n;
a.coef[i]=an-i,0<=i<=n.

Useful polynomial representation

To preserve space, an alternative polynomial representation is given below which uses only one
global array, terms to store all polynomials
#define MAX_TERMS 100
typedef struct
{
float coeff;
int expon;
}polynomial;
polynomial terms[MAX_TERMS];
int avail=0;
ADT polynomial

Page 36
 Data structures and Applications 18CS32

Polynomial addition
Function which adds two polynomials A and B giving D, represented as D=A+B. using previous
polynomial representation the following figure 10 shows how two polynomials are represented
Ex: A(x)=2x1000+1
B(x) =x4-1+10x3+3x2+1

Figure 10: Array representation of polynomial

The index of the first term of A and B is given by startA and startB respectively,while finishA
and finishB give the index of the last term of A and B. the index of the next free location in the array is
given by avail.
Example startA=0,finishA=1,startB=2,finish=5 and avail=6.
This representation ha no limitation on the number of terms in a polynomial but total number of
non-zero terms should not exceed MAX_TERMS.
Poly is used to refer a polynomial and is translated poly into a <start,finish>pair. Any polynomial
A that has n nonzero terms has startA and finishA such that finishA=startA+n-1.
Function To Add Two Polynomials
void padd(int startA,int finishA,int startB, int finish,int *startD,int *FINISHd)
{
float coefficient;
*startd=avail;
while(startA<=finiSHs && startb<=finish)
switch(COMPARE(terms[startA].expon,terms[startB].expon))
{
case -1: /* a.expon<b.expon)*/
attach(terms[startB].coef,terms[startB].expon);
startB++;
break;
case 0:/* equal exponents*/
coefficient=terms[startA].coef+terms[startB].coef;
if(coefficient)
attach(coefficient , terms[startA].expon);
startA++;
startB++;
break;
case 1: /*a.expon>b.expon*/
attach(terms[startA].coef,terms[startA].expon);
startA++;

Page 37
 Data structures and Applications 18CS32

}
for(;startA<=finishA;startA++)
attach(terms[startA].coef,terms[startA].expon);
for(;startB<=finishB;startB++)
attach(terms[startB].coef,terms[startB].expon);
*finishD=avail-1;
}
Function To Add a new term
void attach(float coefficient ,int exponent)
{
if(avail>=MAX_TERMS)
{
\
exit(0);
}
terms[avail].coef=coefficient;
terms[avail++].expon=exponent;
}

2. SPARSE MATRICES
Matrix contains m rows and n columns of elements. it has m rows and n columns. In general
mxn, is used to designate a matrix with m rows and n columns. The total no of elements in such matrix
is m*n. If m equals n then matrix is square.
A matrix containing more number of zero entries, such matrices is called as

In figure11, since this matrix contains many zeros it is called as sparse matrix. Here 8 of 36
elements are only having non-zero values so it is called as sparse matrix. When sparse matrix is
represented as two dimensional array hence space is wasted so need another form of representation to
save memory where only non-zero values are stored.

Figure 11: sparse matrix

Page 38
 Data structures and Applications 18CS32

ADT sparse matrix

Sparse Matrix representation

A array of triples <row,col,value> is used to represent sparse matrix. In triples the row indices
are in ascending order as well as column indices are also in ascending order.(as shown in figure 12).
First row in triplet representation gives the total number of rows, total number of columns and total
number of non-zero values in sparse matrix.
Create operation of sparse matrix is written as
#define MAX_TERMS 101
typdef struct
{
int col;
int rows;
int value;
}term A[MAX_TERMS];
The above Sparse matrix is represented as triples.

Page 39
 Data structures and Applications 18CS32

Figure 12: Triple representation

Transposing a Matrix
Transpose of a given matrix is obtained rows and columns. each element a[i][j].In the original
matrix becomes element b[j][i] in the transpose matrix.
The following algorithm is given by

The algorithm indicates that find all the elements in column 0 and store them in row 0 of the
transpose matrix, find all the elements in column1 and store them in row1 etc. Since the original matrix
ordered the rows, the columns within each row of incorporated in transpose. The first array a is the
original array which the second array b holds the transpose.(As shown in figure13)

Page 40
 Data structures and Applications 18CS32

Figure 13: Transpose of matrix

Function: Transpose a sparse matrix.
void transpose(term a[],term b[])
{
int n,i,j,currentb;
n=a[0].value;
b[0].row=a[0].col;
b[0].col=a[0].row;
b[0].value=n;
if(n>0)
{
currentb=1;
for(i=0;i<a[0].col;i++)
for(j=0;j<=n;j++)
if(a[j].col==i)
{
b[currentb].row=a[j].col;
b[currentb].col=a[j].row;
b[currentb].value=a[j].value;
currentb++;
}
}
}

3. 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."
char greeting[6] = {'H', 'e', 'l', 'l', 'o', '\0'};
If you follow the rule of array initialization then you can write the above statem

Page 41
 Data structures and Applications 18CS32

char greeting[] = "Hello";

Following is the memory presentation of the above defined string in C
Note: Actually, you do not place the null character at the end of a string constant. The C compiler
automatically places the '\0' at the end of the string when it initializes the array.

#include <stdio.h>
int main ()
{
char greeting[6] = {'H', 'e', 'l', 'l', 'o', '\0'};
printf("Greeting message: %s\n", greeting );
return 0;
}
When the above code
Greeting message: Hello
ADT STRING
Objects: a finite set of zero or more characters
Functions:
For all s, t C string,i,j,m C non-negative intergers
String Null(m) = return a string whose maximum length is m characters , but is initally set to NULL we

Integer Compare(s,t) = if s equals t return 0

else if s precedes t return -1
else retun +1
Boolean IsNull(s) = if(Compare(s,NULL)) return FALSE
else return TRUE
Integer Length(s) = if(Compare(s,NULL)) return the number of characters in s
else return 0
String Concat(s,t) = if(Compare(t,NULL)) return a string whose elements are those of s followed by
those of t
else return 0
String Substr(s,i,j) = if((j>0) && (i+j-1) < Length (s)) return the string containing the characters of s at
positions i, i+1, .... , i+j-1
else return NULL

Page 42
 Data structures and Applications 18CS32

3.2 STRING OPERATIONS

C supports a wide range of built in functions that manipulate null-
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.
strchr(s1, ch); Returns a pointer to the first occurrence of character ch in string s1

unction Description
char *strcat (char *dest, char *src) Concatenate dest and src strings; return result in
dest
char *strncat (char *dest, char *src, int n) Concatenate dest and n characters from src; return
result in dest
int strcmp (char *str1, char *str2) Compare 2 strings;
return < 0 if str1<str2;
0 if str1 = str2;
>0 if str1 > str2
int strncmp (char *str1, char *str2, int n) Compare first n characters;
return < 0 if str1<str2;
0 if str1 = str2;
>0 if str1 > str2
char *strcpy (char *dest, char *src) Copy src into dest; return dest
char *strncpy (char *dest, char *src, int n) Copy n characters from src into dest; return dest
size_t strlen (char *s)
char *strchr(char *s, int c) Return pointer to the first occurrence of c in s;
return NULL if not present
char *strrchr(char *s, int c) Return pointer to the last occurrence of c in s;
return NULL if not present
char *strtok(char *s, char *delimiters) Return a token from s;token is surrounded by
delimiters
char *strstr(char *s, char *pat) Return pointer to start of pat in s
size_t strspn (char *s, char *spanset) Scan s for characters in spanset; return length of
span
size_t strcspn (char *s, char *spanset) Scan s for characters not in spanset; return length
of span
char *strpbrk (char *s, char *spanset) Scan s for characters in spanset; return pointer to
first occurrence of a character from spanset

Page 43
 Data structures and Applications 18CS32

#include <stdio.h>
#include <string.h>
int main ()
{
char str1[12] = "Hello";
char str2[12] = "World";
char str3[12];
int len ;
/* copy str1 into str3 */
strcpy(str3, str1);
printf("strcpy( str3, str1) : %s\n", str3 );
strcat( str1, str2);
printf("strcat( str1, str2): %s\n", str1 );
/* total lenghth of str1 after concatenation */
len = strlen(str1);
printf("strlen(str1) : %d\n", len );
return 0;
}
When the above code
strcpy( str3, str1) : Hello
strcat( str1, str2): HelloWorld
strlen(str1) : 10
STRING INSERTION FUNCTION
void strnins(char *s,char *t,int i)
{
Char string[MAX_SIZE],*temp = string;
if( i < 0 && i > strlen(s))
\
exit(EXIT_FAILURE);
}
if(! strlen(s))
strcpy(s,t);
else if if( strlen(t))

Page 44
 Data structures and Applications 18CS32

{
strncpy(temp, s, i);
strcat(temp, t);
strcat(temp, (s+i));
strcpy(s,temp);
}
}
3.3 PATTERN MATCHING ALGORITHMS
C programming code to check if a given string is present in another string, For example the
string "programming" is present in "c programming". If the string is present then it's location (i.e. at
which position it is present) is printed. We create a function match which receives two character pointers
and return the position if matching occurs otherwise returns -1. naive string search algorithm is
implemented in this c program
Brute Force Pseudo-Code
-code
do
if (text letter == pattern letter)
compare next letter of pattern to next
letter of text
else
move pattern down text by one letter
while (entire pattern found or end of text)
1. PATTERN MATCHING BY CHECKING END INDICES FIRST

int nfind(char *string, char *pat)

{
int i , j , start = 0;
int lasts = strlen(string)-1;
int lastp = strlen(pat)-1;
int endmatch=lenp;
for( i = 0; endmatch<=lasts ; endmatch++, start++)
{
if( string[endmatch] == pat[lastp])
for( j = 0 , i = start; j< lastp && string[i] == pat[j]; i++, j++)
;
if(j == lastp)
return start;
} return -1;
}

2. KNUTH MORRIS PRATT STRING MATCHING ALGORITHMS

int pmatch(char *string,char *pat)

Page 45
 Data structures and Applications 18CS32

{
int i = 0,j = 0;
int lens = strlen(string);
int lenp = strlen(pat);
while( i < lens && j < lenp)
{
if( string[i] == pat[j])
{
i++,j++;
}
else if(j == 0) j++;
else j = failure[j-1]+1;
}
return ( if(j == lenp) ? (i-lenp):-1);
}

4. DYNAMIC MEMORY ALLOCATION

The memory allocation which is used till now was static memory allocation. So the memory that
could be used by the program was fixed. So it is not possible to allocate or de allocate memory during
the execution of the program. It is not possible to predict how much memory will be needed by the
program at run time.
For example assume an array with size 20 elements is declared, which is fixed. So if at run time
values to be stored in array are less than 20 then wastage of memory occur or our program may fail if
more than 20 values are to be stored in to that array. To solve the above problems and allocate memory
during runtime dynamic memory allocation is used.
The process of allocating memory during the runtime is called as DMA (dynamic memoey
allocation) and memory gets allotted in heap area of program stack.
example : a new area of memory is allocated using malloc().On success, malloc() returns a
pointer to the first byte of allocated memory. The returned pointer is of type void, which can be type cast
to appropriate type of pointer. The memory allocated by malloc() contains garbage value . when the
requested memory is not available, the pointer NULL is returned. when allocated memory is no longer
required , it is freed by using another function free().
void main()
{
int i,*pi;
float f,*pf;
pi=(int*)malloc(sizeof(int));
pf=(float*)malloc(sizeof(float));

Page 46
 Data structures and Applications 18CS32

*pi=1024;
*pf=3.14;

free(pi);
free(pf);
getch();
}
it shows allocation and deallocation of memory
if((pi=(int *)malloc(sizeof(int))==NULL) || (pf=(float*)malloc(sizeof(float))==NULL))
{

exit(EXIT_FAILURE);
}
if(!(pi=malloc(sizeof(int))) || !(pf=malloc(sizeof(float)))

#define MALLOC(p,s)
If(!((p))=malloc(n,s))
{

exit(EXIT_FAILURE);
}
thus ,MALLOC(pi, sizeof(int));
MALLOC(pf,sizeof(float));

int *x;
x=calloc(n,sizeof(int));
Instead of calloc function a calloc macro can be defined as sown below
#define CALLOC(p,n,s)
if(!((p))=calloc(n,s))
{

exit(EXIT_FAILURE);
}
The function realloc resizes the memory allocated by either malloc or calloc.
Ex: realloc(p,s)
This realloc(p,s) function changes the size of the memory block pointed at p to s.the contents of
the first allocated s with oldsize bytes of the block are unchanged as a result of this resizing.when
s>oldsize the additional s-oldsize have an unspecified value and s<oldsize the rightmost oldsize-s bytes
of the old block are freed.when realloc is able to do the resizing it returns a pointer to the start of the

Page 47
 Data structures and Applications 18CS32

new block and when it is unable to do the resizing the old block is unchanged and function returns the
value NULL.

#define REALLOC(p,s)
if(!((p))=realloc(p,s))
{

exit(EXIT_FAILURE);
}

The following functions are used in dynamic memory allocation and are defined in <stdlib.h>
1. malloc()
Declaration: void *malloc(size_t size); // ptr=(datatpe*)malloc(sizeof(datatype));
This function is used to allocate memory dynamically. The argument size specifies the number
of bytes to be allocated. On success, malloc() returns a pointer to the first byte of allocated memory. The
returned pointer is of type void, which can be type cast to appropriate type of pointer. The memory
allocated by malloc() contains garbage value .
2. calloc()
Declaration: void *calloc(size_t n,size_t size); //ptr=(datatype*)calloc(n,sizeof(datatype));
This function is used to allocate multiple blocks of memory. The first argument specifies the
number of blocks and the second one specifies the size of each block. The memory allocated by calloc()
is initialized to zero.
3. realloc()
Declaration: void *realloc(void *ptr,size_t newsize); //ptr=(datatype*)realloc(ptr,newsize)
The function realloc() is used to change the size of the memory block. It alters the size of the
memory block without losing the old data. This function takes two arguments, first is a pointer to the
block of memory that was previously allocated by malloc() or calloc() and second one is the new size for
that block.
4. free();
Declaration: void free(void *p); //free(ptr);
This function is used to release the memory space allocated dynamically. The memory released
by free() is made available to the heap again and can be used for some other purpose. We should not try
to free any memory location that was not allocated by malloc(), calloc() or realloc().

C programming allots memory at heap during runtime

Page 48
 Data structures and Applications 18CS32

C provides two additional Dynamic memory allocation functions calloc and realloc . The calloc function
allocates a user specified amount of memory and initializes the allocated memory to 0 , a pointer to the
start of the allocated memoey is returned. In case ther is insufficient memory to make the allocation , the
returned value is NULL.so, the example statements could be used to define a one dimensional array of
integers with the capacity of this array is n and x ranges from 0 to n-1 with initially 0 value.
The following program illustrates Dynamic memory allocation.
void main()
{
int *p,n,i;

/* If we
dynamically*/
if(p==NULL)
{

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

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

PROGRAMMING EXAMPLES
1) Write a C program to sort N numbers in ascending order using Bubble sort and print both the
given and the sorted array
#include <stdio.h>
#define MAXSIZE 10
void main()
{
int array[MAXSIZE];
int i, j, num, temp;

printf("Enter the value of num \n");

scanf("%d", &num);
printf("Enter the elements one by one \n");
for (i = 0; i < num; i++)
{
scanf("%d", &array[i]);

Page 49
 Data structures and Applications 18CS32

}
printf("Input array is \n");
for (i = 0; i < num; i++)
{
printf("%d\n", array[i]);
}
/* Bubble sorting begins */
for (i = 0; i < num; i++)
{
for (j = 0; j < (num - i - 1); j++)
{
if (array[j] > array[j + 1])
{
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
printf("Sorted array is...\n");
for (i = 0; i < num; i++)
{
printf("%d\n", array[i]);
}
}

2) Write a C program to input N numbers and store them in an array. Do a linear search for a
given key and report success or failure.
#include <stdio.h>
void main()
{
int array[10];
int i, num, keynum, found = 0;
clrscr();
printf("Enter the value of num \n");
scanf("%d", &num);
printf("Enter the elements one by one \n");
for (i = 0; i < num; i++)
{
scanf("%d", &array[i]);
}
printf("Input array is \n");
for (i = 0; i < num; i++)
{
printf("%d\n", array[i]);
}
printf("Enter the element to be searched \n");
scanf("%d", &keynum);
/* Linear search begins */

Page 50
 Data structures and Applications 18CS32

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

{
if (keynum == array[i] )
{
found = 1;
break;
}
}
if (found == 1)
printf("Element is present in the array\n");
else
printf("Element is not present in the array\n");
}

3) Write a C program to input N numbers and store them in an array. Do a binary search for a
given key and report success or failure.
#include<stdio.h>
main()
{
int a[20],i,j,d,t,x,l=0,low,mid,high;
printf("\nEnter the number of elements\n");
scanf("%d",&d);
printf("Enter the numbers\n");
for(i=0;i<d;i++)
scanf("%d",&a[i]);
for(i=0;i<d;i++)
{
for(j=i+1;j<d;j++)
{
if(a[i]>a[j])
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
}
printf("\nThe sorted list :");
for(i=0;i<d;i++)
printf("%d ",a[i]);
printf("\nEnter the number to be searched\n");
scanf("%d",&x);
low=0;
high=d-1;
while(low<=high)
{
mid=(low+high)/2;
if(x<a[mid])
high=mid-1;

Page 51
 Data structures and Applications 18CS32

else if(x>a[mid])
low=mid+1;
else
{
if(x==a[mid])
{
l++;
printf("The item %d is found at location %d\n",x,mid+1);
exit(0);
}
}
}
if(l==0)
printf("Item not found\n");
}

4. Program to illustrate union inside structure

#include <stdio.h>
struct student
{
union
{
char name[20];
int roll_no;
};
int marks;
};
int main()
{
struct student stud;
char choice;
\n you can enter the name or roll number of the st
\
gets(choice);

{
\
gets(stud.name);
}
else
{
\

}
\n e

\
else

Page 52
 Data structures and Applications 18CS32

\
\
return 0;
}

ASSIGNMENT - I
Module-1
1. Define data structures. With a neat diagram, explain the different classifications of Data structures.
2. Define structure. How it is represented in C language. Give an example program using structures.
3. Differentiate structure and union.
4. What are self referential structures? Give one example.
5. Define nested structure. Give 2 ways of declaring nested structure with example program.
6. Define Array. Explain with program, the operations performed on array.
7. Write C programs to perform each of the following (i) linear search (ii) binary search (iii)bubble sort
taking a array of
8. Which are the 4 inbuilt functions to perform dynamic memory allocation. Discuss the importance of
Dynamic memory allocation. Write a C program to create an array dynamically.
9. Write a C function to create 2d array dynamically. Use MALLOC macro.
10. Illustrate with an example how sparse matrix is efficiently stored in triple format. Write its C
representation.
11. Write an ADT of Polynomial.
12. Write an ADT of Sparse Matrix
13. Define String. Write a C program to perform pattern matching.
14. Write a function to perform polynomial addition.
Module-2
15. Define Stack. List the operations performed on Stack.
16. Write an algorithm to convert infix expression to postfix expression.
17. Convert the below Expression to postfix using stack.(a+b)*((b^c)*f)/g
18. Define Recursion. Illustrate with an example how stack is used in recursion.
19. Write an algorithm for Evaluation of postfix expression.
20. Write a Recursive C program for each of the following:
(i) Tower of Hanoi
(ii) Computing GCD of two numbers.
(iii) Fibonacci series
(iv) To compute factorial of N.

Page 53