NHẬP MÔN LẬP TRÌNH
Mảng 1 chiều
Arrays, Simple Data Structure
Contiguous Storage
Searching
Sorting
NHẬP MÔN LẬP TRÌNH
Objectives
• How to manage a group of data?
– Store
– Input
– Output
– Search
– Sort
–…
Contiguous Storage 2
NHẬP MÔN LẬP TRÌNH
Content
• Introduction to contiguous storage
• Arrays
• One-dimensional Arrays
– Declaration
– Memory Allocation
– Initialization
– Accessing elements
– Traversing
– 1-D Arrays are parameters of functions
– Searching
– Sorting
• 2-D Arrays
Contiguous Storage 3
NHẬP MÔN LẬP TRÌNH
1- Contiguous Storage
• Commonly, a group of the same meaning elements are
considered.
• They are stored in a contiguous block of memory.
• Ex: Group of 10 int numbers 40 bytes block is
needed.
• Data are considered can be a group of some items which
belong to some different data types Contiguous
memory block is partitioned into some parts which have
different size, one part for an item.
• Data structure: A structure of data stored.
• Array is the simplest data structure which contains some
items which belong to the same data type.
• Common used operations on a group: Add, Search,
Remove, Update, Sort
Contiguous Storage 4
NHẬP MÔN LẬP TRÌNH
2- Arrays
Array: A group index 0 1 2 3 4 5 6 7 8 9
of elements a 5 4 8 15 90 27 34 21 152 80
which belong to (array)
a[3]
the same data a[i] is an integer
element
type. Each
element is column
identified by it’s m m[1][3]
position row
(index).
• Dimension: Direction that is used to perform an action on array.
• Number of dimensions: Number of indexes are used to specify
an element.
• Common arrays: 1-D and 2-D arrays.
• Name of an array: An array has it’s name.
Contiguous Storage 5
NHẬP MÔN LẬP TRÌNH
3- One Dimensional (1-D)Arrays
• 1-D array: a collection of items (elements,
terms) which belong to the same data type and
are stored contiguously in memory.
Each element is identified by a unique index of
it’s position in the array (an integer from 0).
index 0 1 2 3 4 5 6 7 8 9
a 5 4 8 15 90 27 34 21 152 80
(array)
a[3]
element a[i] is an integer
Contiguous Storage 6
NHẬP MÔN LẬP TRÌNH
1-D Arrays: Declaration
• If the array is stored in the stack segment Use a STATIC
array The compiler will determine the array’s storage at
compile-time.
• If the array is stored in the heap Use a pointer
(DYNAMIC array) The array’s storage will be allocated
in the heap at run-time through memory allocating
functions (malloc, calloc, realloc)
DataType ArrayName[NumberOfElements] ;
How compilers can determine the memory size of
Examples:
an array?
int a1[5];
NumberOfElements * sizeof(dataType)
char s[12];
int a1[5] 5 *sizeof(int) = 5*4 = 20 bytes
double a3[100];
float *a;
a = (float*)calloc (10, sizeof(float)); /* allocate a block of 10 float numbers */
Contiguous Storage 7
NHẬP MÔN LẬP TRÌNH
1-D Arrays: Memory Allocation
Data segment 4202496 20
The name of the array is the code
Code segment 4199056
address of the first element.
80
Heap
bytes
4072496
Stack segment 20
a1: 2293584 bytes
a2:2293580 4072496
Contiguous Storage 8
NHẬP MÔN LẬP TRÌNH
1-D Arrays:
Initialization & Accessing Elements
Initialize an array:
Type a[] = {val1, val2, … };
How to access the ith element of the array a?
• a is the address of the first element. Based on operation on
pointers:
a+i : address of the ith element, another way: &a[i]
*(a+i): value of the ith element, another way: a[i]
Contiguous Storage 9
NHẬP MÔN LẬP TRÌNH
1-D Arrays: Init. & Accessing…
Compiler will
automatically count
number of initial
values to determine
the size of array
memory
The size of array
memory is pre-
defined.
Compiler will fill 0 to
elements which are
not initialized.
int a[5];
Elements contain
un-predictable
values because they
are local variables.
TEST IT !!!!
Contiguous Storage 10
NHẬP MÔN LẬP TRÌNH
1-D Arrays: Traversing
• A way to visit each element of an array
• Suppose that the 1-D array, named a, containing n
elements.
• Forward traversal:
int i;
for (i=0; i<n; i++)
{ [if (condition)] Access a[i];
}
• Backward traversal:
int i;
for (i=n-1; i >=0; i--)
{ [if (condition)] Access a[i];
}
Contiguous Storage 11
NHẬP MÔN LẬP TRÌNH
1-D Array is a Function Parameter
• The array parameter of a function is the pointer
of the first element of the array.
• Input an array of n integers
void input (int* a, int n)
• Input elements of an array of integers which it’s
number of element is stored at the pointer pn
void input (int a[], int*pn)
• Output an array of n double numbers
void output (double a[], int n)
• Calculate the sum of an array of n integers
int sum (int *a, int n)
Contiguous Storage 12
NHẬP MÔN LẬP TRÌNH
Array Function Parameter: Demo.
• Develop a C-program that will:
-Accept values to an integer array that may contain 100 elements.
- Print out the it’s maximum value.
- Print out it’s elements.
- Print out it’s even values.
• Nouns: • Verbs:
– Constant: -Begin
MAXN=100 -Input n (one value)
–Static array of integers -Input a, n (function)
int a[MAXN] - maxVal = get maximum value in a, n (function)
–Real number of - Print out maxVal (one value)
elements int n - Print out a, n (function)
–Maximum value - Print even values in a, n (function)
int maxVal. - End
Contiguous Storage 13
NHẬP MÔN LẬP TRÌNH
Array Function
Parameter: Demo 1.
Contiguous Storage 14
NHẬP MÔN LẬP TRÌNH
Array Function Parameter: Demo 1.
Contiguous Storage 15
NHẬP MÔN LẬP TRÌNH
Array Function Parameter: Demo 1.
• Comments
– If you allocate an array having 100 elements but
6 elements are used then memory is wasted.
– If If you allocate an array having 100 elements
but 101 elements are used then there is a lack of
memory.
• Solution: Use a dynamic array.
Contiguous Storage 16
NHẬP MÔN LẬP TRÌNH
Array Function
Parameter: Demo 1.
replace
int* a
insert
a = (int*) calloc (n, sizeof(int));
Other functions are
preserved.
Contiguous Storage 17
NHẬP MÔN LẬP TRÌNH
Array Function Parameter: Demo 1.
Contiguous Storage 18
NHẬP MÔN LẬP TRÌNH
Array Function Parameter: Demo 2.
• Develop a C-program that will:
-Accept values to an integer array that may
contains 100 elements. The input will terminate
when user enters the value of zero.
- Print out the it’s maximum value.
- Print out it’s elements.
- Print out it’s even values.
The difference between this problem with the previous one is the input operation can
terminate abruptly when 0 is accepted.
Memory block of the array needs to be allocated in excess
The function for input values of the array must be modified for this case and the
number of elements is updated after each valid value is accepted.
Contiguous Storage 19
NHẬP MÔN LẬP TRÌNH
Array Function Parameter: Demo 2.
Contiguous Storage 20
NHẬP MÔN LẬP TRÌNH
Array Function Parameter: Demo 2.
x=3 n=0 1
0
3
x=7 n=3 4
0 1 2
3 5 2
Contiguous Storage 21
NHẬP MÔN LẬP TRÌNH
1-D Arrays: Searching
• A search algorithm finds the record of
interest using the key array
• Return value: The positional index at
which the interest value is found.
• Two common search algorithms are
– linear search
– binary search
Contiguous Storage 22
NHẬP MÔN LẬP TRÌNH
1-D Arrays: Searching…
Linear search: Find the position of the value x in the
array a having n elements.
Search the value of 6 in the array a having 8 items.
5 9 2 7 6 5 2 5
i=0 1 2 3 4 There may be
n comparisons
Search the value of 12 in the array a having 8 items. performed.
5 9 2 7 6 5 2 5
i=0 1 2 3 4 5 6 7 -1
int firstLinearSearch ( int x, int a[], int n) int lastLinearSearch ( double x, double *a, int n)
{ int i; { int i;
for ( i=0; i<n; i++) for ( i=n-1; i>=0; i--)
if ( x == a[i] ) return i; if ( x == a[i] ) return i;
return -1; return -1;
} }
Contiguous Storage 23
NHẬP MÔN LẬP TRÌNH
1-D Arrays: Linear Searching…
Contiguous Storage 24
NHẬP MÔN LẬP TRÌNH
1-D Arrays: Binary Searching…
Binary search
- Condition for
application:
Values in the
array were
sorted.
int binarySearch ( int x, int a[], int n)
{ int i=0, j= n-1, c ;
while (i<=j)
{ c= (i+j)/2;
if ( x== a[c] ) return c ;
if (x < a[c] ) j = c-1; return c (7)
else i = c +1;
}
return -1; i>j return -1
}
Contiguous Storage 25
NHẬP MÔN LẬP TRÌNH
1-D Arrays: Binary Searching…
No. of elements considered No. of comparisons
n= 2m 1
2m-1 1
Evaluation: 2m-2 1
… …
20 1
Sum m+1 = log2(n) +1
Contiguous Storage 26
NHẬP MÔN LẬP TRÌNH
1-D Arrays: Sorting
• Sorting: Changing positions of elements in an
array so that values are in a order based on a
pre-defined order relation.
• Default order relation in set of numbers: Value
order
• Default order relation in a set of characters/
strings: Dictionary order
• Only two sorting algorithms are introduced
here.
– Selection Sort
– Bubble Sort
Contiguous Storage 27
NHẬP MÔN LẬP TRÌNH
1-D Arrays: Selection Sort
• Find the minimum value in the list
• Swap it with the value in the first position
• Repeat the steps above for remainder of the list
Contiguous Storage 28
NHẬP MÔN LẬP TRÌNH
1-D Arrays: Selection Sort
Contiguous Storage 29
NHẬP MÔN LẬP TRÌNH
1-D Arrays: Bubble Sort
•It works by
repeatedly
stepping
through the list
to be sorted,
comparing two
items at a time
and swapping
them if they are
in the wrong
order.
•The pass
through the list
is repeated
until no swaps
are needed,
which means
the list is sorted
Contiguous Storage 30
NHẬP MÔN LẬP TRÌNH
1-D Arrays: Bubble Sort…
Contiguous Storage 31
NHẬP MÔN LẬP TRÌNH
1-D Arrays: A Sample
• Develop a C-program that helps user managing an 1-D
array of integers (maximum of 100 elements) using the
following simple menu:
• 1- Add a value
• 2- Search a value
• 3- Remove the first existence of a value
• 4- Remove all existences of a value
• 5- Print out the array
• 6- Print out the array in ascending order (positions of
elements are preserved)
• 7- Print out the array in descending order (positions of
elements are preserved)
• Others- Quit
Contiguous Storage 32
NHẬP MÔN LẬP TRÌNH
1-D Arrays: A Sample…
• In this program, user can freely add or remove one or more elements to/
from the array. So, an extra memory allocation is needed (100 items).
• Data:
Array of integers int a[100], n
searched/added/removed number int value
• Functions:
– int menu() Get user choice
– int isFull(int *a, int n) - Testing whether an array is full or not
– int isEmpty(int *a, int n) - Testing whether an array is empty or not
– void add(int x, int*a, int*pn) adding an element to the array will
increase number of elements
– int search(int x, int *a, int n) return a position found in the array
– int removeOne (int pos, int*a, int*pn) Removing a value at the position
pos will decrease number of elements return 1: successfully, 0: fail
– int remove All(int x, int*a, int*pn) Removing a value will decrease
number of elements return 1: successfully, 0: fail
– void printAsc(int*a, int n) – printing array, elements are preserved
– void printDesc(int*a, int n) – printing array, elements are preserved
– void print(int*a, int n)
Contiguous Storage 33
NHẬP MÔN LẬP TRÌNH
1-D Arrays: A Sample…
After values 0 , 2, 8, 9, 7, 3, 2, 4, 2 are
added. Use menu 5 to view them.
Search option Remove one option
Contiguous Storage 34
NHẬP MÔN LẬP TRÌNH
1-D Arrays: A Sample…
Print out in ascending order
(elements are preserved)
Remove all option
Print out in descending order
(elements are preserved)
Contiguous Storage 35
NHẬP MÔN LẬP TRÌNH
1-D Arrays: A Sample…
Contiguous Storage 36
NHẬP MÔN LẬP TRÌNH
1-D Arrays: A Sample…
index 0 1 2 3 4 5 6 7 8
0 2 9 7 3 2 4 2 2
9 7 3 2 4 2 2
Contiguous Storage 37
NHẬP MÔN LẬP TRÌNH
1-D Arrays: A Sample…
0 1 2 3 4 5 6 7 8
0 2 9 7 3 2 4 2 2
0 2 9 7 3 2 4 2
0 2 9 7 3 2 4
0 2 9 7 3 2 4
0 2 9 7 3 4
0 2 9 7 3 4
0 2 9 7 3 4
0 2 9 7 3 4
0 9 7 3 4
0 9 7 Contiguous
3 Storage4 38
NHẬP MÔN LẬP TRÌNH
1-D Arrays: A Sample…
2293504
2293492
2293488
2293496
2293500
Values of pointers
after sorting
2293504
2293500
2293496
2293492
4223516 2293488
adds 4223516
2293504 5
2293500 1
2293496 2
2293492 4
2293488 3
Contiguous Storage 39
NHẬP MÔN LẬP TRÌNH
1-D Arrays: A Sample…
Contiguous Storage 40
NHẬP MÔN LẬP TRÌNH
1-D Arrays: A Sample…
Contiguous Storage 41
NHẬP MÔN LẬP TRÌNH
1-D Arrays: A Sample…
Contiguous Storage 42
NHẬP MÔN LẬP TRÌNH
1-D Arrays: A Sample…
Contiguous Storage 43
NHẬP MÔN LẬP TRÌNH
4- Two-Dimensional Arrays
• A group of elements which belong to the same
data type and they are divided into some rows
and some columns (it is called as matrix also).
• Each element is identified by two indexes
(index of row, index of column).
column
m m[1][3] The next slide
row will
demonstrate
Traversing a matrix: how static
for ( i =0; i<row; i++) and dynamic
{ for ( j=0; j< column; j++) 2-D arrays are
[if (condition)] Access m[i][j];
stored.
}
Contiguous Storage 44
NHẬP MÔN LẬP TRÌNH
3- 2-D Arrays: Memory Structure 4078848
4078840
4078832
4078824
4078808
H 4078800
4078792
E 4078784
A 4078768
4078760
P 4078752
4078744
4078824
4078784
4078720 4078744
4078616
m2 2293600 4078720
p 2293596 4078616
S 2293532
2293528
T 2293524
2293520
A 2293516
2293512
C 2293508
2293504
K 2293500
2293496
2293492
m1 2293488
Contiguous Storage 45
NHẬP MÔN LẬP TRÌNH
Static 2-D Arrays Demo.
Accept a matrix maximum 20x20.
Print out maximum value in it, print out the matrix.
Keep in your mind the way to
specify a matrix as a parameter
of a function ( the number of
column must be pre-defined.).
Contiguous Storage 46
NHẬP MÔN LẬP TRÌNH
Static 2-D Arrays Demo.
Contiguous Storage 47
NHẬP MÔN LẬP TRÌNH
Summary
• Array is the simplest data structure for a group of
elements which belong to the same data type.
• Each element in an array is identified by one or more
index beginning from 0.
• Number of dimensions: Number of indexes are used to
identify an element.
• Static arrays Stack segment
Type a[MAXN];
Type m[MAXROW][MAXCOL];
• Dynamic array: Use pointer and allocate memory using
functions
double *a = (double*)calloc(n, sizeof(double));
int** m = (int**) calloc(row, sizeof(int*));
for (i=0; i<row; i++) m[i]= (int*)calloc(col, sizeof(int));
Contiguous Storage 48
NHẬP MÔN LẬP TRÌNH
Summary
• Accessing elements in an array:
1-D Array (a) 2-D Array (m)
Address Value Address Value
&a[index] a[index] &m[i][j] m[i][j]
a+index *(a+index)
Compiler determines the address of an element:
a + index*sizeof(DataType) m + (i*NumCol + j)*sizeof(DataType)
• Common operations on
arrays:
• Add an element • Base of
• Search an element
• Remove an element
algorithms on
• Input arrays: Traversing
• Output
• Sort
Contiguous Storage 49
NHẬP MÔN LẬP TRÌNH
Exercise- Do yourself
• Develop a C-program that helps user managing an 1-
D array of real numbers(maximum of 100 elements)
using the following simple menu:
• 1- Add a value
• 2- Search a value
• 3- Print out the array
• 4- Print out values in a range
(minVal<=value<=maxVal, minVal and maxVal are
inputted)
• 5- Print out the array in ascending order (positions of
elements are preserved)
• Others- Quit
Contiguous Storage 50
NHẬP MÔN LẬP TRÌNH
Thank You
Contiguous Storage 51