CA3CRT09-Data Structures using C++

Unit 1
Introduction to Data Structure
First we define the meaning of simple data. Data are simply values or set of values. A
data item is either the value of a variable or a constant. For example, the value of a
variable x is 5 which is described by the data type integer, a data item is a row in a
database table, which is described by a data type. A data item that does not have
subordinate data items is called an elementary item. A data item that is composed of
one or more subordinate data items is called a group item. A record can be either an
elementary item or a group item. For example, an employee’s name may be divided into
three sub items – first name, middle name and last name but the
social_security_number would normally be treated as a single item.

Data Structure Definition

The logical or mathematical model of a particular organization of data is called a data
structure.
or
A data structure is an arrangement of data in a computer’s memory or even disk
storage.
or
Data structure is the method to store and organize data to facilitate access and
modifications.
or

Data structures are building blocks of a program. If program is built using improper data
structures, then the program may not work as expected always. The examples of
several common data structures are string, arrays, Stacks, Queues, Linked list, Binary
Trees, Graph and Hash Tables.
A data structure, sometimes called data type, can be thought of as a category of data.
Like, Integer is a data category which can only contain integers. String is data category
holding only strings. A Data structure not only defines what elements it may contain, it
also supports a set of operations on these elements, such as addition or Multiplication.

Classification of Data Structures

Normally The Data structures are of two types or it can be broadly classified into two
Types of data structures:
1.Primitive Data Structure
2.Non-primitive Data Structure

Primitive Data Structure

Primitive data structures, also known as basic data types, are the simplest and most
fundamental types of data structures used in programming. These data structures can
be used to store only a single value. These are directly operated upon by machine level
instruction.
Examples: Integers, Real numbers, Characters and Pointers, and their corresponding
storage representation.
Programmers can use these data types when creating variables in their programs. For
example, A programmer may create a variable say “z” and define it as a real Data type.
The variable will then store data as a real number.

The most common basic or intrinsic data types or primitive data types are As follows:
 Integer : It is a positive or negative number that does not contain any fractional
part.
 Boolean : It is a data type that can store one of only two values, Usually these
values are TRUE or FALSE
 Character : It is any letter, number, punctuation mark or space, which takes up a
single unit of storage, usually a byte
 Float : The float is a data type that can hold decimal values. When the precision
of decimal value increases then the Double data type is used.
 Pointer : A pointer is a variable that stores the memory address of an object.
 Real : A number that contains the decimal part.
Non- primitive Data Structure

Non-primitive data structure is a type of data structure that can store the data of more
than one type. These data structures are not defined by the programming language, but
are instead created by the programmer. They are also called as the reference
variables, since they reference a memory location, which stores the data. These data
structures are derived from the primitive data structures. They are emphasize on
structuring a group of homogeneous (same type) or heterogeneous (different type) data
items.
Examples: Array, Stack, Queues, Linked list, Tree, Graphs and hash table.

The main difference between primitive and non-primitive data

structures is that Primitive data structures are considered as the
fundamental data structure while non-primitive data structures are
defined by the user with the help of primitive data structure.
There are two types of Non-primitive data structure

a) Linear Data Structures:-

In linear data structure the elements are stored in sequential order. Hence they are in
the form of a list, which shows the relationship of adjacency between elements and is
said to be linear data structure. The most, simplest linear data structure is a 1-D array. It
includes the data at a single level such that we can traverse all data into a single run.
The linear data structures are:
1. Array
An array is a linear data structure that collects elements of the same data type and
stores them in contiguous and adjacent memory locations.
2. Stack
A stack is a Last-In-First-Out or First-In-Last-out linear data structure in which insertion
and deletion takes place at only from one end called the top of the stack.
3. Queue
A Queue is a First-In-First-Out or Last-In-Last-Out data structure in which insertion
takes place from one end called the rear and the deletions takes place at one end called
the Front.
4. Linked List

Linked list is a collection of data items in which each item is linked with other. Each
element in the list is known as node. Each node consists of two fields, one for
storing data or information and other for storing address of next element.
The last node of the list contains pointer to the null.

b) Non- linear Data Structure :-

Non-linear data structures are not arranged in a sequence manner. There exists a
hierarchal relationship or network relationship between individuals elements or items.
Examples of Non-linear data structures are trees and graphs.
1.Trees

A tree can be defined as finite set of data items (nodes) in which data items are
arranged in branches and sub branches according to requirement. It represent the
hierarchical relationship between various elements. Tree consist of nodes connected by
edge, the node represented by circle and edge lives connecting to circle.

2. Graph

Graph is collection of nodes and connecting edges or vertices between nodes.

Types of Graphs :

 Directed graph
 Non-directed graph
 Connected graph
 Simple graph
 Multi-graph

OPERATIONS ON DATA STRUCTURES

The most commonly used operations on data structures are broadly categorized into
four types.
i. CREATE
This operation results in reserving memory for the program elements. This can be
done by declaration statement.
ii. INSERTION
Insertion means adding new details or new node in the data structure.
iii. DELETION
Deletion means removing a node from the data structure.
iv. TRAVERSAL
 Traversing means accessing each node exactly once so that the nodes of a date
structure can be processed. Traversal is also called as visiting.
Apart from the four operations, there are three more operations occasionally performed
on data structures. They are
 SEARCHING
This operation finds the presence of the desired data item in the list of data item. It may
also find the locations of all elements that satisfy certain conditions.
 SORTING
Sorting is the process of arranging all data items in a data structure in a particular order
say for example, either in ascending order or in descending order.
 MERGING
Merging is the process of combining the data items of two different sorted lists into a
single sorted list.