BCA- SEMESTER-III

BCA 313
DATA STRUCTURE USING C++

L-2 T-1 P-0 C-3

UNIT-1: INTRODUCTION
 UNIT-1: INTRODUCTION
Agenda
⚫ Introduction
⚫ Basic Terminology
◦ Data
◦ Information
◦ Program
◦ Algorithm
◦ Data Structure
⚫ Types of Data Structures
 INTRODUCTION

• Programming requires different kinds of

information to be stored in the computer.
• The information can be stored in a generalized
format using variables.
 INTRODUCTION
• One variable allows the storage of a single data
entity. However, a set of single variables may not
solve complex problems efficiently.
• A data structure uses a collection of related
variables that can be accessed individually or as a
whole.
• A data structure represents a set of data items
with a specific relationship between them.
• The success of a software project often depends
upon the choices made in the representation of the
data and the choice of algorithms.
 BASIC TERMINOLOGY

Data
• Data can be defined as a set of recorded,
number or events that have no meaning.
• Data is meaning less until it is given relevance.
• Data are raw facts, unorganized facts, that need
to be processed.

42000
Deepak M
2
42
 BASIC TERMINOLOGY

Data
Atomic Data
• Atomic data is the data that we choose to
consider as a single, non-decomposable entity.
For example, the integer 1234
Composite Data
• Composite data can be broken down into
subfields that have meaning. For example, a
student’s record consists of Roll_Number,
Name, Branch, Year, and so on.
 BASIC TERMINOLOGY

Information
• Meaningful Data is called information.
• When data is processed, organized, structured
or presented in a given context so as to make it
useful, it is called information.

Name Age Gender Number of Kids Salary

Deepak 42 M 2 42000
 BASIC TERMINOLOGY

Data vs. Information

Parameters Data Information
What Just a fact Meaningful data
Based On Record or Analysis
Observation
Form Unorganized Organized
Useful May or May not Always
Specific No Yes
Dependency No On Data
 BASIC TERMINOLOGY

Data Type
Data type specifies
- the kind of data a variable may store
- type of operations can be performed on that data.

Data
Type

User
Built-In
Defined
 BASIC TERMINOLOGY

Built-In Data Type

- Languages have their built-in data types. For example, in the
C/C++ languages, int, float, and char are built-in data types.

User Defined Data Type

- Allow the user to define his or her own data types, called
user-defined data types, using the built-in data types.
- Using these built-in data types, we can design (define) our
own data types by means of structures, unions, and classes.
 BASIC TERMINOLOGY
Data Structure
- It is a particular way to store the information in a memory so
that we can retrieve the information and apply different
operations effectively and efficiently
- It is a way of collecting and organizing data in such a way that
we can perform operations on these data in an effective way.
- Data structure is a representation of the logical relationship
between individual elements of data.
- Data structure is a specialized format for analyzing and
storing data in memory and also store their relationship to
each other.
- Data structure represent a set of data items with a specific
relationship between them.
 BASIC TERMINOLOGY
Data Structure
A data structure is
- A combination of elements, each of which is either as a data
type or another data structure and
- A set of associations or relationships (structures) involving
the combined elements.
 BASIC TERMINOLOGY

Data Structure
- Data structure affects the design of both structural and
functional aspect of a program.
- Software project depends upon the choice made in
representation of the data and algorithm.
- Data structure has two aspects
- Specification(requires explaining the functioning and
overall behavior of the data structure)
- Realization (requires simulating the data structure in
some programming language).
 BASIC TERMINOLOGY

Program = Algorithm + Data Structure

TYPES OF DATA STRUCTURE
 TYPES OF DATA STRUCTURE

The various types of data structures are as follows:

- primitive and non-primitive
- linear and non-linear
- static and dynamic
- sequential and direct access
- Homogeneous and Non- Homogeneous
 TYPES OF DATA STRUCTURE

Primitive Data Structure

- Primitive data structures define a set of primitive elements
that do not involve any other elements as its subparts—for
example, data structures defined for integers and characters

Non-primitive Data Structures

- Non-primitive data structures are those that define a set of
derived elements such as arrays.
- Class and structure are other examples of non-primitive data
structures
 TYPES OF DATA STRUCTURE
Linear Data Structure
- A data structure is said to be linear if its elements form a
sequence or a linear list.
- In a linear data structure, every data element has a unique
successor and predecessor.
- There are two basic ways of representing linear structures in
memory.
- One way is to have the relationship between the elements by
means of pointers (links), called linked lists.
- The other way is using sequential organization, that is, arrays.
 TYPES OF DATA STRUCTURE

Non- Linear Data Structure

- Non-linear data structures are used to represent the data
containing hierarchical or network relationship among the
elements.
- In non-linear data structures, every data element may have
more than one predecessor as well as successor.
- Trees and graphs are examples of non-linear data structures
using C++ data structures.
 TYPES OF DATA STRUCTURE

Static Data Structure

- In Static data structure the size of the structure is fixed.
- The content of the data structure can be modified but
without changing the memory space allocated to it.
- Example of Static Data Structures: Array
Dynamic Data Structures
- In Dynamic data structure the size of the structure in not
fixed and can be modified during the operations performed
on it.
- Dynamic data structures are designed to facilitate change of
data structures in the run time.
- Example of Dynamic Data Structures: Linked List
 TYPES OF DATA STRUCTURE

Static vs Dynamic Data Structure

Advantage of Static data structure :
• Data type size is fixed
• Memory allocation before program execution.
• Stack is used.
• Less efficient than dynamic data structure.
• No memory reuse.
• Overflow is not possible.
Advantage Of Dynamic Data Structure :
• Data type size is not fixed
• Memory allocation is done during program execution.
• Heap is used.
• More efficient.
• Memory reuse.
• Overflow occurs.
 TYPES OF DATA STRUCTURE

Sequential Access Data Structure

- Sequential access means that to access the nth element, we
must access the preceding (n - 1) data elements.
- A linked list is a sequential access data structure.

Direct Access Data Structures

- Direct access means that any element can be accessed
without accessing its predecessor or successor; we can
directly access the nth element.
- An array is an example of a direct access data structure.
 TYPES OF DATA STRUCTURE

Homogeneous Data Structure

- All the elements are of same type
- For example : Array

Non-Homogeneous Data Structure

- All the elements are not of same type
- For example : Structure