DATA STRUCTURES AND
ALGORITHMS
LESSON 1: POINTERS AND STRUCTURED DATATYPES
Contents
1. Introduction
2. Static vs dynamic variable
3. Pointer, 1D array, structured datatypes
2
Introduction
What are data structures and algorithms?
• A data structure is a data organization, management,
and storage format that enables efficient access and
modification.
• Algorithms is a finite set of well-defined, computer-
implementable instructions, to solve a problems or to
perform a computation
3
Introduction
What are data structures and algorithms?
• You studied some data structures and algorithms in
programming discipline.
Ex:
- 1D array, 2D array
- Algorithm to arrange 1D array according to
ascending/descending order.
- Recursive
4
Introduction
Why do we need to study many data structures and algorithms?
• We want to design the good programs
ü Save executing time
ü Save memory space
• Our real data is multiform and complexible
• An algorithm cann’t be appropriate to many data structures
• We need to know many data structures and algorithms so
that we can choose an appropriate one for our real data.
5
Introduction
Contents:
1. Data structures: array, stack, queue, list, tree, etc.
2. Algorithms:
ü Sort: insertion, quick, merge, heap, and selection
ü Search: linear search, binary search, and binary search tree
ü Recursive, e.g. binary tree traversals; find path;
6
Introduction
Assessment:
1. Assignment: 30%
ü In class or at home
ü Submit to Wecode: an automatic grading system
[Link]
username: student ID (such as: 19521234)
password: 123456789 (should change the pw)
2. Practice: 20% (closed-book test when we finish this discipline)
ü In class, using computers in the lab (not allow to use your own computer)
ü Submit to Wecode: [Link]
3. Final test: 50% (closed-book test)
ü Written test (on paper)
“To Improve Programming Skills, write/modify lots of programs”
7
Variables and memory
• Source code and data are loaded
to computer memory (RAM) during Addresses Cells
0
combining and executing a C/C++ 1
1 byte
program 2
3
• Memory of a computer (RAM) is 4
like a succession of memory cells 5
6
• Each cell is one byte in size 7
• Each cell has a unique address . .
. .
• Memory cell address are . .
consecutive, first cell address is 0 …
Memory Layout (bytes)
8
?
How does C/C++ manage variables?
NMLT - CON TRỎ CƠ BẢN 9
Static vs Dynamic Variables
Static variables
• Memory is allocated when the int main() {
variable is declared. int a;
• Memory (RAM) will be freed by the cin >> a;
combiler when it goes out of the if(a){
scope
int value;
value = a;
}
value = --a;
}
10
Static vs Dynamic Variables
Static variables:
• Memory allocated for Address
the variable stores value
0
• Use variable name x ch
(identifier) to access the
1
value 2
3 a
• For example: print 7 on int main() {
the screen 4
char ch=‘x’; 5 7
cout << a; int a = 7; 6
} 7
. .
. .
. .
…
Memory Layout (bytes)
NMLT - CON TRỎ CƠ BẢN 11
Static vs Dynamic Variables
Static variables:
• Add & before the Address
variable name
(identifier) to access the 0
address 1 x ch
• For example: print 3 on 2
the screen 3 a
int main() {
cout << &a; 4
char ch=‘x’; 5 7
• Add * before an address
to access the value
int a = 7; 6
stored at that address } 7
. .
• For example: print 7 on
the screen . .
cout << *(&a);
. .
…
Memory Layout (bytes)
NMLT - CON TRỎ CƠ BẢN 12
Variables and memory
int value; 0x50
value
value = 3200; 3200
Memory Layout
cout << " value = " << value;
=> value = 3200;
cout << " &value = " << &value;
=> &value = 0x50;
cout << " *(&value) = " << *(&value);
=> *(&value) = 3200;
NMLT - CON TRỎ CƠ BẢN 13
Static vs Dynamic Allocation
Dynamic allocation int main() {
• Memory is allocated and freed int *p;
by the programmer p = new int;
o Allocate: new *p = 3200;
o Deallocate: delete delete p;
• We access a dynamic variable return 0;
through a pointer }
0x34
3200 0x90
ptr 0x34
Memory Layout
NMLT - CON TRỎ CƠ BẢN 14
Pointer
• Pointer variable (pointer) is used to store an address (of
static/dynamic variable)
• Every pointers are allocated 4 bytes (the same size
allocating for an int variable)
• Declaration:
<Date type> *<variable name>;
0x34
int a;
• Ex: int *ptr; a 0x90
p = &a;
ptr 0x34
Memory Layout
NMLT - CON TRỎ CƠ BẢN 15
Pointer
• Pointer must have the same data type as the
static/dynamic variable that the pointer points to
• Ex:
int a;
int *ptr;
p = &a; 0x34
double b, *pb; a 0x90
pb = &b;
ptr 0x34
Memory Layout
? double a;
int *ptr = &a;
NMLT - CON TRỎ CƠ BẢN 16
1.4 Con trỏ và toán tử &, *
• Put * before the pointer name to access value of the
variable that the pointer points to
• Ex:
int a = 1000;
0x34
int *ptr = &a;
a 3201
3200
1000
cout << ptr << “ ” << *ptr;
// a = 3200
*ptr = 3200; 0x90
cout << *ptr; ptr 0x34
(*ptr) ++;
Memory Layout
NMLT - CON TRỎ CƠ BẢN 17
Pointer
• Pointer is a static variable
o Programmer cann’t deallocate the pointers
• Ex:
int *ptr = new int;
0x34
*ptr = 3200;
3200
1000
cout << *ptr; // 3200
cout << ptr; // 0x34
cout << &ptr; // 0x90 0x90
cout << &(*ptr); //0x34 ptr 0x34
delete p; //free 0x34
Memory Layout
NMLT - CON TRỎ CƠ BẢN 18
Pointer assignment
• We can assign a pointer to another pointer.
int *p1, *p2;
p2 = p1;
NMLT - CON TRỎ CƠ BẢN 19
Ví dụ
p1 27 p1 27
p1 = p2
p2 5 p2 5
p1 27 p1 5
*p1 = *p2
p2 5 p2 5
NMLT - CON TRỎ VÀ CẤP PHÁT ĐỘNG 20
NULL pointer vs uninitialized pointer
• A NULL pointer doesn’t point to anywhere
• An uninitialized pointer point to random location
int n;
int *p1 = &n; // point to variable n
int *p2; // point to a random location
int *p3 = NULL; // doesn’t point to anywhere
NULL
NMLT - CON TRỎ CƠ BẢN 21
Exercise 1
• Find errors:
int main() {
int x, *p;
x = 10;
*p = x;
return 0;
}
NMLT - CON TRỎ CƠ BẢN 22
Exercise 2
#include <iostream>
Write a C++ program that using namespace std;
includes 2 variables as
follows: int main() {
+ initializing the integer i int i = 12;
with value 12
int *p1;
+ pointer p1 points to an
// i = 24;
integer location.
p1 = &i;
*p1 = 24;
Use p1 to change the value
cout << *p1 << " "
of i to 24? << i << endl;
}
NMLT - CON TRỎ CƠ BẢN 23
One-dimensional array
• Static allocation:
int arr[6] = {5, 6, 9, 4, 1, 2};
Address Value
&arr[0] 0x10 5 arr[0]
&arr[1] 0x14 6 arr[1]
&arr[2] 0x18 9 arr[2]
&arr[3] 0x22 4 arr[3]
&arr[4] 0x26 1 arr[4]
&arr[5] 0x30 2 arr[5]
Memory Layout
NMLT - CON TRỎ CƠ BẢN 24
One-dimensional array
• Static allocation int A[6] = {5, 6, 9, 4, 1, 2};
• Array name indicates the
address of the first element of 0x10 5 A
the array == &A[0]
èA == &A[0] 6
= 0x10
0x14
• Array name is a constant
pointer
0x18 9
è can’t change its value
A++; // a wrong command 4
0x22
• Programmer cann’t free the
memory allocated for static 1
0x26
variables
=> How can A store 7 integers?
0x30 2
Memory Layout
NMLT - CON TRỎ CƠ BẢN
One-dimensional array
• Array name is a constant pointer
Access element value
0x10 5 arr[0] = * arr = *(arr+0)
0x14 6 arr[1] = *(arr+1)
0x18 9 arr[2] = *(arr+2)
0x22 4 arr[3] = *(arr+3)
0x26 1 arr[4] = *(arr+4)
0x30 2 arr[5] = *(arr+5)
NMLT - CON TRỎ CƠ BẢN
Memory Layout 26
Pointer and 1D array
• Use one level pointer to store 1D array
0x10 5 arr
int *p = &arr[2]
0x14 6
p+1 (=0x22)
0x18 9
p+2 (=0x26)
0x22 4
0x26 1
0x30 2
Memory Layout
NMLT - CON TRỎ CƠ BẢN 27
Pointer and 1D array
• We can change the value of p
0x10 5 arr
p-2 (=0x18)
0x14 6
p-1 (=0x22)
0x18 9
int *p = &arr[4]
0x22 4
0x26 1
0x30 2
Memory Layout
NMLT - CON TRỎ CƠ BẢN 28
Pointer and 1D array
• Access value of ith element:
arr[i] == *(arr+i) == parr[i] == *(parr + i)
• Access address of ith element:
&arr[i] == arr+i == &parr[i] == parr + i
NMLT - CON TRỎ CƠ BẢN 29
Pointer and 1D array
0x10 5 arr[0] = parr[0] = *(parr+0)
0x14 6 arr[1] = parr[1] = *(parr+1)
0x18 9 arr[2] = parr[2] = *(parr+2)
0x22 4 arr[3] = parr[3] = *(parr+3)
0x26 1 arr[4] = parr[4] = *(parr+4)
0x30 2 arr[5] = parr[5] = *(parr+5)
Memory Layout
NMLT - CON TRỎ CƠ BẢN 30
1D array and function parameter
When the function parameter is an 1D array, it is not the
constant pointer
right
wrong
void xuat(int *a, int n) {
int main() { for (int i = 0; i<n; i++)
int a[] = {1,2,3,4,5,6}; printf("%d", *(a++));
}
for (int i = 0; i<6; i++)
printf("%d", *(a++)); int main() {
} int a[] = {1,2,3,4, 5, 6};
xuat(a, 6);
}
NMLT - CON TRỎ CƠ BẢN 31
Dynamic allocation for 1D array
• Commends:
int main() {
int *a = NULL, n;
cin >> n;
//Dynamic allocation an 1D array with n elements and assign it to the
pointer a.
a = new int[n];
//Input values to array
for (int i = 0; i<n; i++)
{
cin >> a[i];
// cin >> *(a+i);
}
//print element values on screen
for (int i = 0; i<n; i++)
{
cout << a[i] << " ";
// cout << *(a+i) << " ";
}
//deallocate 1D array
delete[] a; //
}
NMLT - CON TRỎ CƠ BẢN 32
Pointer and structured datatype
• Normal variable: use a dot “.” to access attributes
• Pointer variable: use right arrow “->” to access
attributes.
NMLT - CON TRỎ CƠ BẢN 33
Good luck!
