lecture 1-2

Data Structures and
Algorithms (CST203)
DR. LAVIKA GOEL
Data Structures
A data structure is a scheme for organizing data in the
memory of a computer.
Also, it is a representation of the logical relationship that
exists between the individual elements of data.
Some of the more commonly used data structures include
lists, arrays, stacks, queues, heaps, trees, and graphs.
The way in which the data is organized affects the
performance of a program for different tasks.
Need: Better time complexity, easy to read, debug, modify.
(Contd.)
Data structures are the building blocks of a program:
▪ Rich enough in structure to reflect the relationship
between the data.
▪ Simple structure to process the data effectively whenever
required.
Data structure affects the structural and functional aspects
of a program.
▪ Algorithm + data structure = program
Classification of data structure
Two types: Primitive and non-primitive data structures.
Primitive data Structures: Primitive data structures are the fundamental data
types which are supported by a programming language. These can be directly
operated upon by machine instructions and can have different representations
on different computers. Basic data types such as integer, float, character and
Boolean are known as Primitive data Structures.
Non- Primitive data Structures: Non-primitive data structures are those data
structures which are created using primitive data structures. Examples of non-
primitive data structures is the processing of complex numbers, linked lists,
stacks, trees, and graphs.
Based on the structure and arrangement of data, non-primitive data structures
is further classified into :
1. Linear Data Structure
2. Non-linear Data Structure
1. 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 sequential memory location. These linear
structures are called arrays.
2. The other way is to have the linear relationship between the

elements represented by means of pointers or links. These linear
structures are called linked lists.
The common examples of linear data structure are Arrays, Queues, Stacks,
Linked lists.
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 insertion and 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-linear data structure.
Classification of data structure
Arrays
• Arrays are data structures consisting of
related data items of the same type
• Arrays are “static” entities in that they remain
the same size throughout program execution
• An array is a group of contiguous memory
locations that all have the same type.
• To refer to a particular location or element in
the array, we specify the array’s name and
the position number of the particular
element in the array.
Arrays
• Any array element can be referred by giving
the array’s name followed by the position
number of the element in square brackets
([]), which is called index or subscript.
• An index must be an integer
• The first element in every array is the zeroth
element.
• An array name is like any other identifiers
• The brackets used to enclose the index of an
array are actually an operator in C.
Arrays
Arrays
Defining Arrays
• Arrays occupy space in memory.

• The type of each element and the number of
elements each array requires are to be
specified so that the computer can reserve
the appropriate amount of memory.
• The definition int b[100] reserves 100
elements for integer array b with indices in
the ranges 0–99
• Arrays may contain other data types like char,
float, double etc.
Linked list
Stacks
Queue
Trees
Graph data structure
Algorithm
Incremental algorithms
Divide and conquer algorithms
Example
Complexity of algorithms
The complexity of an algorithm M is the function f(n) which gives the running
time and/or storage space requirement of the algorithm in terms of the size ‘n’
of the input data. Mostly, the storage space required by an algorithm is simply a
multiple of the data size ‘n’. Complexity shall refer to the running time of the
algorithm.
The function f(n), gives the running time of an algorithm, depends not only on
the size ‘n’ of the input data but also on the particular data. The complexity
function f(n) for certain cases are:
1. Best Case : The minimum possible value of f(n) is called the best case.
2. Average Case : The expected value of f(n).
3. Worst Case : The maximum value of f(n) for any key possible input.
The field of computer science, which studies efficiency of algorithms, is known as
analysis of algorithms.
Omega notation
Theta notation
Big-O notation
Categories of algorithms
Data structure operations
1. Traversing: accessing each record/node exactly once so that certain items in
the record may be processed. (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
Memory Layout of C Programs
A typical memory representation of C program consists of following sections:
1. Text segment
2. Initialized data segment
3. Uninitialized data segment
4. Stack
5. Heap
Text segment
This is the machine code that the CPU executes. This segment is usually shareable so only a
single copy needs to be in memory and it is often read-only.
Initialized data segment (data segment)
Contains variable that are specifically initialized in the
program. For example:
int maxcount = 99;
It is like a piece of virtual address space for a program,
containing global and static variables that have been
initialized by the programmer.
Not read-only as values of variables can be altered at run-
time.
Uninitialized data segment
aka bss - block started by symbol - segment
For global and static uninitialized variables.

Data here is initialized by the kernel to arithmetic 0 or NULL
pointers before program starts executing.
Stack
This is where automatic variables are stored.
Each time a function is called, the address of where to
return to and certain info about the caller's environment
(i.e. machine registers) are saved on the stack. The newly
called function then allocates room on the stack for its
automatic and temporary variables.
◦ This is how recursive calls in C work.
Heap
The heap is a large free pool of memory available to the
programmer to repeatedly request.
Eg. malloc()
Thank you

lecture 1-2

Uploaded by

Copyright:

Available Formats

lecture 1-2

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

lecture 1-2

Uploaded by

Copyright:

Available Formats

Data Structures and

A data structure is said to be linear if its elements form a sequence or

1. One way is to have the linear relationships between the elements

2. The other way is to have the linear relationship between the

A data structure is said to be non-linear if the data are not arranged in

• Arrays occupy space in memory.

For global and static uninitialized variables.

You might also like