Data Structures and Algorithms

Mohammad GANJTABESH

Department of Computer Science,

School of Mathematics, Statistics and Computer Science,
University of Tehran,
Tehran, Iran.

mgtabesh@ut.ac.ir

Dept. of Computer Science

University of Tehran
 Variables, Pointers and Arrays

Data Structures and Algorithms

Undergraduate course

Mohammad GANJTABESH Dept. of Computer Science

mgtabesh@ut.ac.ir University of Tehran
 Data types
• Data type indicates the category of data and its properties (including the
size, permitted operations, etc.).
• Different data types:
programming Lang
elementary data types
in ,

I Built-in types ÷
float
identical Lint
char
I Arrays ÷ collection of data with , ,
- - .

)
I Struct and class : collection of type
data (
.

Data structures : methods) with

possibly
I
User-defined
collection data different
of types .

and its operations .

1 / 11
 Memory management
• How different types of data are stored and manipulated in memory?
• The role of operating system all the resources
÷
managing etc )
( memory , ,
.

• Different parts of program/process: code, data, stack, heap

process
Memory management:
• Segmentation
• Paging
Memory

☐
2 / 11
 Memory management: segmentation
File system
int mainly Machine →

int x ; code .

\main.enI
char c ; file
(0/1)
Cin >> xD C 's
process main

Contax Kc ;

}
return to ) ;
ode segment
Data
/
¥
Heap

Segment .

3 / 11
mmmm
6/5
 Memory management: paging
Mem

t.im#iE*r
.

} code , A , P#3

Page
512 B

4 / 11
 Memiadd allocated
-

Variables -

(o
( ooo

o I
to
my
-

2
process
I 00

• A place-holder in memory for storing data.

-

{
10 03
-

• Variables’ attributes: 2L _
too 4

I The number of allocated memory bytes

I The location of the allocated memory ÷
I The defined/permitted operations on it -
i

I Type casting: convert one type to another -

'

c { -
'

5 / 11
 Pointers Too

[
• A place-holder in memory for storing memory address! 102

• Can be used to access the stored data.

104

µ ,
my µ , ,

; ;¥÷:
" *

p=&x :
cart Kxk*pK&p ; '

, I

5
?
"° I

cant KP
=
¥ man .

6 / 11
type X-P 's
1/5/73 :
Arrays int sets]={
Ptt 's = p= ptsizeofctype) int x-p =&x[is ; Ptt 's

int Aef - x ;

• Contiguous area of memory consists of equal-size elements indexed by

contiguous integers

: ¥=÷÷:÷
• Random access (constant time)
• Fixed size (static memory allocation)
• Consecutive memory bytes are allocated to arrays
• Number of elements in an array could be specified at
I compile time (static memory allocation)
I run time (dynamic memory allocation)

÷÷¥É |¥≠
*

*
91¥
a
/☒ 7 / 11
 them
Multi-dimensional arrays

↑
A- [0,3]

Column major

-
-
-
-

"""
mxn
"

v.
£ columns

Now - major

index of element [ rij] in

K
men
=

,
µ , µ, , ,.gg, , , ,
,,÷,
8 / 11
 Dynamic memory allocation
• Should be asked from the operating system to do the memory allocation
at run-time.
• Pointers are usually required.
at run-time .

could be specified
int x-p ;

(int))
A) maltoccnxsizeof
;
p - (int
↓
allocation
memory
.

'
int with
'

points to an
array of type n
element,

9 / 11
 Struct and Class
• To define a new type containing different types of data (fields).
• User-defined type.

ɧ÷ !
struct students
}
name
a.

int ID ;
4 bytes

char * name : "ites

float cops ; 4 bytes

÷
}
student x ;
struct *p=&n ;

10 / 11
?⃝
 Abstract Data Type (ADT)

Concerns what is getting done not how it is getting done.

Definition
A class of objects whose logical behavior is defined by a set of values and a
set of operations.

-
Constructors -
-
Destructions .

the state
- Transformers -
clear

of
change /modify the ADT .

state of ADT

-
Observers :

allow read-only
access to the state
of ADF
-

Iterators :

allow sequential access to the elements in ADT .

11 / 11