1
Fundamentals of Data Structures
Understand the concepts of data structures
Understand data structure representation in memory
Understand data processing
Course Understand the implementation strategies of data structures
Outline Understand run-time storage management
Understand pointers and references
Understand linked list and structures
Understand efficiency analysis using big O notation
Understand data compression and memory
management
2
SEN209
Overview of Data Structures
Understand the concepts of data structures
Understand array data structure
Specific Understand the limitations of array data structure
objectives
Understand array memory allocation
Implement array operations
SEN209
Overview of Data Structures
What is Data and Data Structure?
Data is the basic entity or fact that is used in computation or manipulation process.
Data are classified into:
Data
Structures
Data can be single or a set of values and
It is to be organized in a particular fashion.
A data structure is basically a group of data elements that are put together under one name
and which provides an efficient way of storing and organizing data in a computer so that it
can be used efficiently.
Data structures are generally classified into primitive and non-primitive data structures.
SEN209
Overview of Data Structures
Classification of data structures
Data
Structures
SEN209
Overview of Data Structures
Data Structure?
Data structure is the structural representation of logical relationships between elements of
data.
In other words, a data structure is a way of organizing data items by considering its
relationship to each other.
Data Mathematically;
Structures
Data structure mainly specifies the structural organization of data, by providing accessing
methods with correct degree of associativity.
Data structure affects the design of both the structural and functional aspect of a program.
SEN209
Overview of Data Structures
Primitive Data Structures
The primitive data structures are the basic data types or the simple data types that consist
of characters that cannot be divided.
Examples of the primitive data structures are integer, Boolean, real and character.
Data In C and C++ variables are created by using declaration statement
Structures The syntax for declaration is:
<data type> < variables>;
Examples:
int x, y, z;
char x = ‘a’;
bool x = false;
7
SEN209
Overview of Data Structures
Non-Primitive Data Structures
The non-primitive data structures are further classified into linear and non-linear data
structures
Data A data structure is said to be linear if its elements form a sequence or a linear list.
Structures It is said to be linear if all of its elements are arranged in a linear order.
In linear data structure, the elements are stored in non-hierarchical way where each
element has the successors and predecessors except the first and last element.
Examples of linear list include: arrays, linked list, stacks and queues
8
Overview of Data Structures
Non-Primitive Data Structures
A data structure is said to be non-linear if the data is not arranged in sequence. But are
arranged in multiple levels (called hierarchy level).
Data Examples of non-primitive data structures include graphs and trees
Structures Insertion and deletion are not possible in a linear data structure
Non-primitive data structures can contain homogenous (same types) or heterogeneous
(different types) data items
9
Overview of Data Structures
Data structure operations
The six major operations of a data structure are:
Traversing – traversing means accessing each record exactly once so that certain items
Data in the record may be processed
Structures Searching – finding the location of the record with a given key value called searching
Inserting – means adding a new record to the structure
Deleting – means removing a record from the structure
Sorting – sorting means arranging the records in some logical order. Arranging data
elements of a data structure in a specified order is called sorting
Merging – merging means combining the records in two different sorted files into a single
sorted file.
10
Overview of Data Structures
Non-Primitive Data Structures- Arrays
An array is a collection of homogenous data items or elements described by a single
name.
Each element of an array is referenced by a subscripted variable or value, called
Array Data
Structure subscript or index enclosed in parenthesis
By a linear array, we mean a list of a finite number of similar data elements referenced
respectively by a set of n consecutive numbers usually
1, 2, 3, 4, 5, ….. , n
If we choose the name A for the array then the elements of A are denoted by subscript
notation a1, a2, a3, …….. , an
11
Overview of Data Structures
Non-Primitive Data Structures- Arrays
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]
Array Data In C programming, arrays are declared using the following syntax:
Structure <data type> <array_name[size]> or <data type><array_name[size][size]>;
Example
int Marks[50]; int Marks[50][50];
12
Overview of Data Structures
Non-Primitive Data Structures- Arrays
• Index starts with 0.
• The array's length is 5, which means we can store 5 elements.
Array Data • Each element in the array can be accessed via its index.
Structure
13
Overview of Data Structures
Non-Primitive Data Structures- Arrays
The number of elements is called the length or size of the array
Example: Mark[20] is an array of length 20
Array Data Generally, the length of an array can be obtained from the index set by the formula:
Structure Length = UB –LB +1
Where
UB is the largest index, called the upper bound
LB is the smallest index, called the lower bound of the array.
When LB = 1; then the length of the array will be:
Length = UB – 1 + 1 = UB
14
Overview of Data Structures
Non-Primitive Data Structures- Arrays
Example:
An automobile company uses an array Auto to record the of automobiles sold each year
from 2000 to 2023. rather than beginning the index set with 1, it is more useful to begin
Array Data the index set with 2000. find the length of the array or the number of elements in the
Structure array.
Solution:
Length UB – LB +1
2023 – 2000 + 1 =23 + 1 = 24
15
Overview of Data Structures
Limitation of Arrays
Arrays are of fixed size
Data elements are stored in contiguous memory locations which may not be always
available
Array Data
Insertion and deletion of elements can be problematic because of shifting of elements
Structure from their positions.
Insertions and deletions can be at the beginning, at the end or at the middle of the array
However, these limitations can be solved by using linked list
16
Overview of Data Structures
Memory Allocation of 1-Dimensional Arrays
All the data elements of an array are stored at contiguous locations in the main memory –
either in row order or column order.
Array Data The name of the array represents the base address or the address of the first element in
Structure the main memory.
Each element of the array is represented by proper indexing.
17
Overview of Data Structures
Memory Allocation of 1-Dimensional Arrays
There are two basic ways of representing linear structure in memory.
These are:
Sequential memory location (as in arrays)
Memory
Management Pointers or links (as in linked lists)
In linear arrays, the memory of the computer is simply a sequence of addressed location
The elements of the arrays are stored in successive memory cells.
18
Overview of Data Structures
Memory Allocation of 1-Dimensional Arrays
The computer does not need to keep track of the address of every element of the array LA,
but needs to keep track only of the address of the first element of LA, denoted by Base(LA).
This address is called the base address of the array LA.
Memory
Management The address of any element of LA is calculated by the formula
Loc(LA[k]) = Base(LA) + w(k-lower bound)
Where w is the number of word per memory cell for the array
k is any given subscript and
Lower bound is the index of the base address.
Example: If Base(Auto=2001) = 200, find the address element for the year 2010.
Loc(Auto(2010) = Base(Auto) + w(k – lower bound)
=200 + 4(2010 – 2001) = 200 + 4 * 9 = 200 + 36 = 236
The content of the memory at loc(Auto(2010)) = 236 19
Overview of Data Structures
Memory Allocation of 2-Dimensional Arrays
2D array can be defined as an array of arrays.
The 2D array is organized as matrices which can be represented as the collection of rows
Array Data and columns.
Structure However, 2D arrays are created to implement a relational database that looks like a data
structure.
It provides ease of holding bulk of data at once which can be passed to any number of
functions wherever required.
The syntax of declaring two dimensional array is:
int arr[max_rows][max_columns];
20
Overview of Data Structures
Memory Allocation of 2-Dimensional Arrays
A two-dimensional m x n array is a collection of m.n data elements such that each element is
specified by a pair of integers (such as j,k), called subscripts.
Array Data A[j,k]
Structure
Two-dimensional arrays are called matrices in mathematics and tables in business applications.
Hence, a two-dimensional arrays are called matrix array.
Suppose, A is a two-dimensional m x n array. The first dimension of A contains the index set 1, 2,
….,m with lower bound 1 and upper bound m and the second dimension of A contains the index set
1, 2, …, n with lower 1 and upper bound n.
Length of the array = (m-1+1).(n-1+1) = m.n
21
Overview of Data Structures
Memory Allocation of 2-Dimensional Arrays
Example: Given the declaration in Fortran
integer Number(2:5,-3:1); find the number of elements of the array?
Array Data Solution:
Structure number of rows = upper bound – lower bound +1 = 5-2+1 = 4
number of columns = 1- (-3) +1 = 1 + 3 + 1 = 5
Number of elements = 4 x 5 = 20 elements
22
Overview of Data Structures
Mapping of 2-Dimensional Arrays to 1-Dimensional Array
In row major ordering, all the rows of the 2D arrays are stored into the memory
contiguously.
Its memory allocation according to row major order is done row by row. That is row 1 is
Memory
Management stored completely before row 2.
23
Overview of Data Structures
Mapping of 2-Dimensional Arrays to 1-Dimensional Array
In column major ordering, all the columns of the 2D arrays are stored into the memory
contiguously.
Memory The memory allocation is done column by column. That is column 1 is stored completely
Management before column 2.
24
Overview of Data Structures
Mapping of 2-Dimensional Arrays to 1-Dimensional Array
Let A be a two-dimensional mxn array. A is pictured as a rectangular array of element with
m rows and n columns.
The array is represented in memory by a block of m.n sequential memory location.
Memory
Management The elements are stored either in column by column or column major order or row by row or
row major order
25
Overview of Data Structures
Mapping of 2-Dimensional Arrays to 1-Dimensional Array
In a two-dimensional array, the computer keeps track of the first element A[1.1] and
computes the address of Loc(A[j,k]) of A[m,n] using the formula.
Column-major order:
Memory
Loc (A[j,k])= Base + w(m[k-1]+[j-1])
Management
Where m is the maximum number of rows
Row-major order is calculate as:
Loc (A[j,k])= Base + w(n[j-1]+[k-1])
Where w denotes the number of words per memory location for the array and n is the
maximum number of columns.
Note that the formulas are linear in j and k and that one can find the address Loc(A[j,k])
in time independent of j and k.
26
Overview of Data Structures
Mapping of 2-Dimensional Arrays to 1-Dimensional Array
Example: Consider the 25 x 4 matrix array SCORE with Base(SCORE) = 200 and w =4
words per memory. Furthermore, suppose the programming language stored two-
dimensional arrays using row-major order. Find the address of SCORE[12,3]?
Memory Solution: Using the row-major order we have:
Management
Row-major order is calculate as:
Loc (A[j,k])= Base + w(n[j-1]+[k-1])
Where n is the maximum column of the given array
Loc(SCORE[12,3]) = 200 + 4(4(12-1)+ (3-1)) = 200 + 4(44+2) = 200 + 4x 46
= 200 + 184 = 384.
27
Overview of Data Structures
Mapping of 2-Dimensional Arrays to 1-Dimensional Array
Example: Consider the 25 x 4 matrix array SCORE with Base(SCORE) = 200 and w =4
words per memory. Furthermore, suppose the programming language stored two-
dimensional arrays using column-major order. Find the address of SCORE[12,3]?
Memory Solution: Using the row-major order we have:
Management
Column-major order is calculate as:
Loc (A[j,k])= Base + w(m[k-1]+[j-1])
Where m is the maximum row of the matrix array.
Loc(SCORE[12,3]) = 200 + 4(25(4-1)+ (12-1)) = 200 + 4(25x3+11) = 200 +
4(75+11)
= 200 + 4(86) = 200 + 344 = 544
28
Overview of Data Structures
Traversal operation
Traverse operation simply goes through the elements of the array and print them.
Array Data
Structure
29
Overview of Data Structures
Traversing a linear array (Traverse operation)
The traverse algorithm is:
Step 1: Initialize Counter by setting counter to lower bound (k = LB)
Data
Step 2: Repeat step 3 and 4 while k<=UB (Upper bound)
Structure
Step 3: Visit element apply process to Array[k]
Step 4: Increment counter. Set counter = counter + 1;
Step 5: Exit
30
Overview of Data Structures
Traversing a linear array (Traverse operation)
Data
Structure
31
Overview of Data Structures
Update operation
The update operation simply modifies an item in the array.
Array Data
Structure
32
Overview of Data Structures
Search operation
The search operation simply check for the present of an item in the array. Searching can
be done by value or index.
Searching by value
Array Data
Structure
33
Overview of Data Structures
Insertion and Deletion of array elements
Inserting elements to an array and deleting elements from an array cannot be done
straight away as arrays are fixed in sizes.
Array Data To insert an element to an array, we have to create a new array with increased size
Structure (current_size + n)
Copy the existing elements into the new array
34
Then add the new elements using the index
Overview of Data Structures
Insertion of array elements
Array Data
Structure
35
Overview of Data Structures
Insertion and Deletion of array elements
The same goes for the deletion with a new array of reduced size
To delete an element to an array, we have to create a new array with reduced size
Array Data (current_size - n)
Structure Delete the element and then Copy the remaining elements into the new array
36
Overview of Data Structures
Deletion of array elements
Array Data
Structure
37
Overview of Data Structures
Deletion of array elements
Array Data
Structure
38
Overview of Data Structures
Storing user data into 2D array and printing it
Array Data
Structure
39
40
THANK YOU
FOR
LISTENING
THE END
