Data Structures

B20CI0303
(UNIT – 1)

Introduction to Data Structures

Data structure is a representation of the logical relationships existing between individual elements
of data. A data structure is a way of organizing all data items that considers not only the elements
stored but also their relationship to each other for better organization and storage.
The logical or mathematical model of a particular organization of data is called a data structure.

Data: Data are simply values or sets of values.

Basic types of Data Structures/Classification of Data Structures

Data structures are generally classified into

 Primitive Data Structures

 Non-primitive Data Structures

1. Primitive Data Structures: Primitive data structures are the fundamental data types which are
supported by a programming language. Basic data types such as integer, real, character and
Boolean areknown as Primitive data Structures. These data types consist of characters that cannot
be divided and hence they also called simple data types.
2. Non-Primitive Data Structures: Non-primitive data structures are those data structures
which arecreated using primitive data structures. Examples of non-primitive data structures is
the processing ofcomplex numbers, linked lists, stacks, trees, and graphs.

Based on the structure and arrangement of data, Non – Primitive data structures are further
subdivided into linear and Non linear. All these data structures allow us to perform different
operations on data. We select these data structures based on which type of operation is
required. Let us look into these data structures in more details at a later part.

Linear Data Structure:

A data structure is said to be linear if its elements form a sequence or a linear list. There are
basically two ways of representing such linear structure in memory.
1. One way is to have the linear relationships between the elements represented by means of
sequentialmemory location. These linear structures are called arrays.

2. The other way is to have the linear relationship between the elements represented by means of
pointersor links. These linear structures are called linked lists.

The common examples of linear data structure are Arrays, Queues, Stacks, Linked lists
 Data Structures
B20CI0303
(UNIT – 1)
2. Non-linear Data Structure:
A data structure is said to be non-linear if the data are not arranged in sequence or a linear. The
insertionand deletion of data is not possible in linear fashion. This structure is mainly used to
represent data containing a hierarchical relationship between elements. Trees and graphs are the
examples of non-lineardata structure.
The diagram shown below would best explain it.

Figure 1.1 Classification of Data

Structures

Some of the Data structures are briefly described below

Arrays:
The simplest type of data structure is a linear (or one dimensional) array. A list of a finite
number nof similar data referenced respectively by a set of n consecutive numbers, usually
1,2, 3 . . . . . . .
n. if A is chosen the name for the array, then the elements of A are denoted by subscript
notationa1, a2, a3 an

or
by the parenthesis notation A (1), A (2), A (3) .............. A (n)
or
by the bracket notation A [1], A [2], A [3] .............. A [n]

Example 1: A linear array STUDENT consisting of the names of six students is

pictured in below figure. Here STUDENT [1] denotes John Brown, STUDENT [2]
denotes Sandra Gold, and so
 Data Structures
B20CI0303
(UNIT – 1)

Linear arrays are called one-dimensional arrays because each element in such an array is
referenced by one subscript. A two-dimensional array is a collection of similar data
elementswhere each element is referenced by two subscripts.

Example 2: A chain of 28 stores, each store having 4 departments, may list its weekly sales as in
below fig. Such data can be stored in the computer using a two-dimensional array in which the
first subscript denotes the store and the second subscript the department. If SALES is the name
given to the array, then
SALES [1, 1] = 2872, SALES [1, 2] - 805, SALES [1, 3] = 3211, , SALES [28, 4] = 982

Trees:
Data frequently contain a hierarchical relationship between various elements. The data structure
which reflects this relationship is called a rooted tree graph or a tree.

Stack :
A stack, also called a fast-in first-out (LIFO) system, is a linear list in which insertions and deletions can take
place only at one end, called the top. This structure is similar in its operation to a stack of dishes on a spring

system as shown in fig.Note that new 4 dishes are inserted only at the top of the stack and dishes can be deleted
only from the top of the Stack
Queue: A queue, also called a first-in first-out (FIFO) system, is a linear list in which deletions
can take place only at one end of the list, the "from'' of the list, and insertions can take place only
at the other end of the list, the “rear” of the list.
This structure operates in much the same way as a line of people waiting at a bus stop, as pictured
in Fig. the first person in line is the first person to board the bus. Another analogy is with
automobiles waiting to pass through an intersection the first car in line is the first car through.
 Data Structures
B20CI0303
(UNIT – 1)

Data Structure Operations

The data appearing in data structures are processed by means of certain operations.
The following four operations play a major role in this text:
1. Traversing: accessing each record/node exactly once so that certain items in the record
may beprocessed. (This accessing and processing is sometimes called “visiting” the
record.)
2. Searching: Finding the location of the desired node with a given key value, or finding
the locations of all such nodes which satisfy one or more conditions.
3. Inserting: Adding a new node/record to the structure.
4. Deleting: Removing a node/record from the structure.

The following two operations, which are used in special situations:

1. Sorting: Arranging the records in some logical order (e.g., alphabetically according to some
NAME key, or in numerical order according to some NUMBER key, such as social security
number or account number)
2. Merging: Combining the records in two different sorted files into a single sorted file.

Data types

Data types refer the semantics and characteristics of storage of data elements. They are expressed in
the language syntax in form of declarations for memory locations or variables
 Data Structures
B20CI0303
(UNIT – 1)

Algorithms
Definition: - An algorithm is a step by step process to solve a problem, where
each step indicates an intermediate task. Algorithm contains finite number
of steps that leads to the solution of the problem.

Categories of Algorithm:
Based on the different types of steps in an Algorithm, it can be divided into three
categories, namely
 Sequence
 Selection and
 Iteration
Sequence: The steps described in an algorithm are performed successively one by one without skipping any
step. The sequence of steps defined in an algorithm should be simple and easy to understand. Each
instruction of such an algorithm is executed because no selection procedure or conditional branching exists
in a sequence algorithm.
Example:
// adding two numbers
Step 1: start
Step 2: read a,b
Step 3: Sum=a+b
Step 4: write Sum
Step 5: stop
 Data Structures
B20CI0303
(UNIT – 1)
Selection: The sequence type of algorithms are not sufficient to solve the problems, which involves
decision and conditions. In order to solve the problem which involve decision making or option selection,
we go for Selection type of algorithm. The general format of Selection type of statement is as shown below:

if(condition)
Statement-1;
else
Statement-2;
The above syntax specifies that if the condition is true, statement-1 will be executed otherwise statement-2
will be executed. In case the operation is unsuccessful. Then sequence of algorithm should be changed/
corrected in such a way that the system will re execute until the operation is successful.

Abstract data type

Abstract Data type (ADT) is a type (or class) for objects whose behaviour is defined by a set of
valueand a set of operations.
The definition of ADT only mentions what operations are to be performed but not how these
operations will be implemented. It does not specify how data will be organized in memory and
what algorithms will be used for implementing the operations. It is called “abstract” because it
gives an implementation-independent view. The process of providing only the essentials and hiding
thedetails is known as abstraction.
 Data Structures
B20CI0303
(UNIT – 1)

Common ADT Examples

 List

 Stack

 Queue

 Set

 Map

 Stream

Example of Abstract Data type

A stack is a last in, first out (LIFO) data structure. The item that is in line to be the next one removed
from the stack is the one that was added last, that is most recently. The operations on a stack include
adding and removing items. Typically, we also specify operations for making a stack empty and for
testing whether it is empty. Since we consider a stack to be a stack of items of some specified base
type, the base type is also part of the definition. Formally, we get a different stack ADT for each
different basetype. So, we define the ADT “stack of BaseType” where BaseType could be integer,
string, or any other data type
We define an abstract data type Stack of BaseType. The possible values of this type are sequences of
items of type BaseType (including the sequence of length zero).

The operations of the ADT are:

push(x): Adds an item, x, of type BaseType to the stack; that is, modifies the value of the stack by
appending x to the sequence of items that is already on the stack. No return value.
pop: Removes an item from the stack and returns that item. The item removed is the one that was
added most recently by the push operation. It is an error to apply this operation to an empty stack.
makeEmpty: Removes all items from the stack. No return value.
isEmpty: Returns a value of type boolean, which is true if the stack contains no items and is false
ifthere is at least one item on the stack.
 Data Structures
B20CI0303
(UNIT – 1)

ARRAYS
 An Array is defined as, an ordered set of similar data items. All the data items of an
array are stored in consecutive memory locations.
 The data items of an array are of same type and each data items can be accessed usingthe
same name but different index value.
 An array is a set of pairs, <index, value >, such that each index has a value associated
with it. It can be called as corresponding or a mapping
Example: <index, value>
< 0 , 25 > list[0]=25
< 1 , 15 > list[1]=15
< 2 , 20 > list[2]=20
< 3 , 17 > list[3]=17
< 4 , 35 > list[4]=35

Here, list is the name of array. By using, list [0] to list [4] the data items in list can be
accessed.
Data Structures
B20CI0303
(UNIT – 1)
Data Structures
B20CI0303
(UNIT – 1)
Data Structures
B20CI0303
(UNIT – 1)
 Data Structures
B20CI0303
(UNIT – 1)

Compile time Initialization:

Data Structures
B20CI0303
(UNIT – 1)
 Data Structures
B20CI0303
(UNIT – 1)

Array i n C

Declaration: A one dimensional array in C is declared by adding brackets to the name of a

variable.
Ex: int list[5], *plist[5];

 The array list[5], defines 5 integers and in C array start at index 0, so list[0], list[1],
list[2], list[3], list[4] are the names of five array elements which contains an integer
value.
 The array *plist[5], defines an array of 5 pointers to integers. Where, plist[0], plist[1],
plist[2], plist[3], plist[4] are the five array elements which contains a pointer to an
integer.
 Data Structures
B20CI0303
(UNIT – 1)

Implementation:
 When the complier encounters an array declaration, list[5], it allocates five consecutive
memorylocations. Each memory is enough large to hold a single integer.
 The address of first element of an array is called Base Address. Ex: For list[5] the
address of list[0] is called the base address.
 If the memory address of list[i] need to compute by the compiler, then the size of the
int would get by sizeof (int), then memory address of list[i] is as follows:

list[i] = α + i * sizeof (int)

Where, α is base address.

Difference between int *list1; & int list2[5];

The variables list1 and list2 are both pointers to an int, but in list2[5] five memory locations are
reserved for holding integers. list2 is a pointer to list2[0] and list2+i is a pointer to list2[i].
 Data Structures
B20CI0303
(UNIT – 1)

Note: In C the offset i do not multiply with the size of the type to get to the appropriate element
of the array. Hence (list2+i) is equal &list2[i] and *(list2+i) is equal to list2[i].

How C treats an array when it is parameter to a function?

 All parameters of a C functions must be declared within the function. As various

parameters are passed to functions, the name of an array can be passed as parameter.
 The range of a one-dimensional array is defined only in the main function since new
storage for an array is not allocated within a function.
 If the size of a one- d i m e n s i o n a l array is needed, it must be passed into function
as argument or accessed as a global variable.
 Data Structures
B20CI0303
(UNIT – 1)

Two-Dimensional Array
Data Structures
B20CI0303
(UNIT – 1)
 Data Structures
B20CI0303
(UNIT – 1)

Two-Dimensional Array Representation

Data Structures
B20CI0303
(UNIT – 1)
 Data Structures
B20CI0303
(UNIT – 1)

C program for displaying the elements of a two-dimensional array

Data Structures
B20CI0303
(UNIT – 1)
 Data Structures
B20CI0303
(UNIT – 1)

STRUCTURES

Structure is a user-defined datatype in C language which allows us to combine data of different types
together. Structure helps to construct a complex data type which is more meaningful. It is somewhat
similar to an Array, but an array holds data of similar type only. But structure on the other hand, can
store data of any type, which is practical more useful. This mechanism is called the structure, for short
struct.
A structure (a record) is a collection of data items, where each item is identified as to its type and name.
Syntax:
struct struct_tag
{ data_type member 1;
data_type member 2;
………………………
………………………
data_type member n;
};

Example of a Structure
struct student
{
int rollnumber;
char name[20];
float percentage;
};
Here struct student name declares a structure to hold the details of a student which consists of 3 data fields,
namely rollnumber ,name and percentage. These fields are called structure elements or members.Each
member can have different datatype, like in this case, name is an array of char type and rollnumber is of int
type etc. student is the name of the structure and is called as the structure tag.

Memory Allocation in Structure in C

 Data Structures
B20CI0303
(UNIT – 1)
Declaring Structure Variables

It is possible to declare variables of a structure, either along with structure definition or after the structure
is defined. Structure variable declaration is similar to the declaration of any normal variable ofany other
datatype. Structure variables can be declared in following two ways:

struct Student
{
char name[25];
int age;
char branch[10];
char gender;
};

struct Student S1, S2; //declaring variables of struct Student

Accessing Structure Members

Structure members can be accessed and assigned values in a number of ways. Structure members haveno
meaning individually without the structure. In order to assign a value to any structure member, the
member name must be linked with the structure variable using a dot . operator also
called period or member access operator.

For example:

#include <stdio.h>
struct student
{
char name[50];
int roll;
float marks;
};
int main()
{
struct student s;
printf("Enter The Information of Students :\n\n");
printf("Enter Name : ");
scanf("%s",s.name);
printf("Enter Roll No. : ");
scanf("%d",&s.roll);
printf("Enter marks : ");
scanf("%f",&s.marks);
printf("\nDisplaying Information\n");
printf("Name: %s\n",s.name);
printf("Roll: %d\n",s.roll);
printf("Marks: %.2f\n",s.marks);
return 0;
}
 Data Structures
B20CI0303
(UNIT – 1)

Output:

Structure Initialization

Like a variable of any other datatype, structure variable can also be initialized at compile time.

struct Patient
{
float height;
int weight;
int age;
};

struct Patient p1 = {180.75 , 73, 23 }; //initialization

or
struct Patient p1;
p1.height = 180.75; //initialization of each member separately
p1.weight = 73;
p1.age = 23;
 Data Structures
B20CI0303
(UNIT – 1)

Array of Structure

We can also declare an array of structure variables. in which each element of the array will represent a
structure variable.

Example : struct employee emp[5];

The below program defines an array emp of size 5. Each element of the array emp is of type Employee.

#include<stdio.h>

struct Employee
{
char ename[10];
int sal;
};

int main()
{
struct Employee emp[5];
int i, j;
printf("Enter the employee details:”);
for(i = 0; i < 3; i++)
{
printf("\nEmployee name:\t");
scanf("%s", emp[i].ename);
printf("\nEnter Salary:\t");
scanf("%d", &emp[i].sal);
}
printf("\n Employee record is:\n");
for(i = 0; i < 3; i++)
{
printf("\nEmployee name is %s", emp[i].ename);
printf("\nSalary is %d", emp[i].sal);

}
}

Type-Defined Structure
The structure definition associated with keyword typedef is called Type-Defined Structure.
Syntax 1: typedef struct
{
data_type member 1;
data_type member 2;
………………………
 Data Structures
B20CI0303
(UNIT – 1)
………………………
data_type member n;
}Type_name;
Where,
 typedef is the keyword used at the beginning of the definition and by using typedefuser
defined data type can be obtained.
 struct is the keyword which tells structure is defined to the complier
 The members are declare with their data_type
 Type_name is not a variable, it is user defined data_type.

Syntax 2: struct struct_name

{
data_type member 1;
data_type member 2;
………………………
………………………
data_type member n;
};
typedef struct struct_name Type_name;

#include<stdio.h>

struct Books
{
int id;
char author[50];
char title[50];
};

typedef struct Books Book;

int main() {
//declare `book1` and `book2` of type `Book`
Book book1;
Book book2;

//the specifications for the `book1`

book1.id = 1;
strcpy(book1.author,"Zara Ali");
strcpy(book1.title,"Tutorials for C Programming");

//the specifications for the `book2`

book2.id = 2;
strcpy(book2.author,"Zaid Ali");
 Data Structures
B20CI0303
(UNIT – 1)
strcpy(book2.title,"Tutorials for Java Programming");
//display information for `book1` and `book2`
printf( "The id of book1: %d\n", book1.id);
printf( "The author of the book1: %s\n", book1.author);
printf( "The title of the book1: %s\n", book1.title);

printf( "The id of book2: %d\n", book2.id);

printf( "The author of the book2: %s\n", book2.author);
printf( "The title of the book2: %s\n", book2.title);

return 0;
}

Output:
The id of book1: 1
The author of the book1: Zara Ali
The title of the book1: Tutorials for C Programming
The id of book2: 2
The author of the book2: Zaid Ali
The title of the book2: Tutorials for Java Programming

Structure Using Pointers

C structure can be accessed in 2 ways in a C program. They are

1. Using normal structure variable
2. Using pointer variable3.
Dot(.) operator is used to access the data using normal structure variable and arrow (->) is used to access
the data using pointer variable.

Example program for c structure using pointer:

#include <stdio.h>
#include <string.h>

struct student
{
int id;
char name[30];
float percentage;
};

int main()
{
int i;
struct student record1 = {1, "Raju", 90.5};

struct student *ptr;

 Data Structures
B20CI0303
(UNIT – 1)
ptr = &record1;

printf("Records of STUDENT1: \n");

printf(" Id is: %d \n", ptr->id); printf("
Name is: %s \n", ptr->name);
printf(" Percentage is: %f \n\n", ptr->percentage);

return 0;
}

OUTPUT:

Records of STUDENT1:
Id is: 1
Name is: Raju Percentage
is: 90.500000

Nested Structures (Structure within a structure):

There is possibility to embed a structure within a structure. There are 2 ways to embed structure.
1. By separate structure
2. By Embedded structure

1. The structures are defined separately and a variable of structure type is declared inside the
definition of another structure. The accessing of the variable of a structure type that are nested
inside another structure in the same way as accessing other member of that structure

Example: The following example shows two structures, where both the structure are defined
separately.
#include<stdio.h>
struct address
{
char city[20];
int pin;
char phone[14];
};
struct employee
{
char name[20];
 Data Structures
B20CI0303
(UNIT – 1)

struct address add;

};
void main ()
{
struct employee emp;

printf("Enter employee information?\n");

scanf("%s %s %d %s",emp.name,emp.add.city, &emp.add.pin, emp.add.phone);
printf("Printing the employee information....\n");
printf("name: %s\nCity: %s\nPincode: %d\nPhone: %s”,
emp.name,emp.add.city,emp.add.pin,emp.add.phone);
}
Accessing Structure Members
To access any member of a structure, we use the member access operator (.). The member accessoperator
is coded as a period between the structure variable name and the structure member that
we wish to access. You would use the keyword struct to define variables of structure type. Thefollowing
example shows how to use a structure in a program −

#include <stdio.h>

#include<string.h>

struct Books
{
char title[50]; char

author[50]; char

subject[100];

int book_id;

};
 Data Structures
B20CI0303
(UNIT – 1)

int main( )
{

structBooksBook1; /* Declare Book1 of typeBook*/

structBooksBook2; /* Declare Book2 of type Book*/

/* book 1 specification */

strcpy( Book1.title, "DataStructures");

strcpy( Book1.author, "Sahni");

strcpy(Book1.subject, "DS");

Book1.book_id=6495407;

/* book 2 specification */

strcpy( Book2.title, "Telecom Billing");

strcpy( Book2.author, "Shiney");

strcpy( Book2.subject, "Telecom Tutorial");

Book2.book_id = 6495700;

/* print Book1 info */

printf( "Book 1 title : %s\n", Book1.title);

printf("Book 1 author : %s\n", Book1.author);

printf( "Book 1 subject : %s\n",Book1.subject);

printf( "Book 1 book_id : %d\n", Book1.book_id);

/* print Book2 info */

printf( "Book 2 title : %s\n", Book2.title);

printf("Book 2 author : %s\n", Book2.author);

printf( "Book 2 subject : %s\n",Book2.subject);

 Data Structures
B20CI0303
(UNIT – 1)

printf( "Book 2 book_id : %d\n", Book2.book_id);

return 0;

When the above code is compiled and executed, it produces the following result −Book 1

title : Data Structures

Book 1 author :Sahni

Book 1 subject : DS

Book 1 book_id : 6495407

Book 2 title : Telecom Billing

Book 2 author : Shiney

Book 2 subject : Telecom Tutorial

Book 2 book_id : 6495700

Data Structures
B20CI0303
(UNIT – 1)
Data Structures
B20CI0303
(UNIT – 1)
Data Structures
B20CI0303
(UNIT – 1)
Data Structures
B20CI0303
(UNIT – 1)
Data Structures
B20CI0303
(UNIT – 1)
Data Structures
B20CI0303
(UNIT – 1)
 Data Structures
B20CI0303
(UNIT – 1)

C Program Example of Matrix Operations

C Program to add two matrices

#include <stdio.h>
int main()
{
//fill your code
int m, n;
scanf(“%d %d”,&m,&n);
int i, j;
int mat1[m][n], mat2[m][n], mat3[m][n];
for(i = 0; i < m; i++)
{
for(j = 0; j < n; j++)
scanf(“%d”,&mat1[i][j]);
}
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
scanf(“%d”,&mat2[i][j]);
}

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

{
for(j = 0; j < n; j++)
{
mat3[i][j] = mat1[i][j] + mat2[i][j];
}
}
 Data Structures
B20CI0303
(UNIT – 1)

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

{
for(j = 0; j < n; j++)
printf(“%d “, mat3[i][j]);
printf(“\n”);
}

return 0;
}

Output
1 2 (order of the matrix)
1 2 3 4 (matrix 1 elements)
2 3 4 5 (matrix 2 elements)
3 5 (resultant matrix)
79

C program for the multiplication of two matrices

#include<stdio.h>
#include<stdlib.h>
int main(){
int a[10][10],b[10][10],mul[10][10],r,c,i,j,k;
system("cls");
printf("enter the number of row=");
scanf("%d",&r);
printf("enter the number of column=");
scanf("%d",&c);
printf("enter the first matrix element=\n");
for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
 Data Structures
B20CI0303
(UNIT – 1)

scanf("%d",&a[i][j]);
}
}
printf("enter the second matrix element=\n");
for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
scanf("%d",&b[i][j]);
}
}

printf("multiply of the matrix=\n");

for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
mul[i][j]=0;
for(k=0;k<c;k++)
{
mul[i][j]+=a[i][k]*b[k][j];
}
}
}
//for printing result
for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
printf("%d\t",mul[i][j]);
 Data Structures
B20CI0303
(UNIT – 1)

}
printf("\n");
}
return 0;
}
Output