Elementary data structure

Introduction To Data Structure
> Basic Concepts
> What is data structure?
> What is Algorithm?
> Examples
> 1D & 2D array representation in memory

1. Elementary of
Data Structure &
Algorithms
B. MANDAL

2. Basic Terminology
A good program is that
Runs correctly
Easy to read & understand
Easy to debug
Easy to modify
A program should undoubtedly
Gives correct result &
Efficiently
To write efficient programs –we need to
enforce certain data management concepts

3. A group of data elements that put together under one
name.
Data Structure is a way of storingand organizing
data in computer system.
Logically &
Mathematically
Purpose :–For efficient access of stored data
Data Structure

4. Data: a value or set of values
Record: collection of data items
E.g. name, address & subject for a particular student
File: collection of related records [Dictionary]
Key: one or more data item(s) which will uniquely
identify each records form a file.
Data Structure –Elementary

5. Primitive: atomic, fundamental data types (e.g. integer,
real, Boolean)
Non-primitive: derived from primitive DS (e.g. array,
structure)
Linear: elements are stored in linear or sequential manner.
Linear memory allocations
Linear relationship between elements
E.g. Array, linked list, Stack, Queue …
Non-Linear: elements are not stored in linear manner.
E.g. Graph, Tree
Classification of Data Structure

6. Traversing: Accessing each data item exactly once
Searching: Finding location of one/more data items
Inserting: Add new data items
Deleting: Removing data
Sorting: Arranging data
Merging: Combining set of data
Operations on Data Structure

7. Way we look at a Data Structure
Focusing on what it dose
Ignoring implementation details
E.g. List, Stack, Queue …
Real world problem solving
Abstract Data Type (ADT)

8. Any well-defined computational procedure
Takes some value, or set of values, as input
produces some value, or set of values, as output
An algorithm is a sequence of computational steps that
transform the input into the output.
For a particular problem –we may have several
algorithms
One algorithm may not fit for other problems
Algorithm

9. Ex. Searching an element from a list
Algo: Search(A, key, N)
{
For i=0 to N
if( A[i] == key )
RETURN (i)
RETURN (-1)
}

10. Ex. GCD of two number
Algorithm: GCD(a, b)
{
while (a ≠ b)
{
if a > b
a ←a –b
else
b ←b –a
}
RETURN (a)
}

11. Ex. Factorial of positive integer
Algorithm: Factorial(n)
{
Fact ←1
If n = 1
return (1)
else
Fact ←n * Factorial(n -1)
return (Fact)
}

12. Collection of similar data item
Referred by a common name
Contiguous memory allocation
E.g. intStudent[10];
Array

13. 2-Dimentional Array
E.g. char matrix[5] [4];


14. E.g. char matrix[6] [12];
Will not fit


15. 2-dimensional array mapped to 1-dimensional array
Special way to access
E.g.
char A[3][4];
A ⇒ 012 3
0
1
2
A´⇒
Representation in Memory
a b c d
e f g h
i j k l
abcdefghijkl
0 1234567 8 9 10 11
A [row][col] = A´[row * m + col]
m # columns

16. Dynamic Memory Allocation
Calloc–contiguous memory allocation
Arr= (int*) calloc(n, sizeof(int))
Malloc–block of memory allocation
Arr= (int*) malloc(n * sizeof(int))
Free: release memory
free(Arr)
**Arris a pointer to integer

17. Thank You 