31/03/2022

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

Data structures and Algorithms Basic Lab

Nguyễn Khánh Phương

Computer Science department

School of Information and Communication technology
E-mail: phuongnk@[Link]

CODE TO TEAMS:

wg3m1hr

1
 31/03/2022

Introduction
• C Programming practice in UNIX environment.
• Programming topics related to [Data Structures and Algorithms]
• Compiler: gcc
• Editor: Emacs, K-Developer,..

gcc syntax
• Parameter:
-Wall : turn on all alerts
-c: make object file
-o: name of output file
-g: debug information
-l: library
Example:
gcc –Wall hello.c –o runhello
./runhello

2
 31/03/2022

Course outline
Chapter 1. Basic data types, I/O with files
Chapter 2. Recursion
Chapter 3. Lists
Chapter 4. Stack and Queue
Chapter 5. Trees
Chapter 6. Sorting
Chapter 7. Searching

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

Chapter 1. Basic data types, I/O with files

Nguyễn Khánh Phương

Computer Science department

School of Information and Communication technology
E-mail: phuongnk@[Link]

3
 31/03/2022

Contents
1. Pointers and arrays
2. String
3. Struct data type
4. Dynamic allocation
5. Input/output with text files
6. Input/output with binary files

NGUYỄN KHÁNH PHƯƠNG 7

SOICT– HUST

Contents
1. Pointers and arrays
2. String
3. Struct data type
4. Dynamic allocation
5. Input/output with text files
6. Input/output with binary files

NGUYỄN KHÁNH PHƯƠNG 8

SOICT– HUST

4
 31/03/2022

1. Pointers and arrays

1.1. Getting the Address of a Variable
1.2. Pointer Variables
1.3. The Relationship Between Arrays and Pointers
1.4. Pointer Arithmetic
1.5. Initializing Pointers
1.6. Pointers as Function Parameters

NGUYỄN KHÁNH PHƯƠNG 9

SOICT– HUST

1 Pointers and arrays

1.1. Getting the Address of a Variable
1.2. Pointer Variables
1.3. The Relationship Between Arrays and Pointers
1.4. Pointer Arithmetic
1.5. Initializing Pointers
1.6. Pointers as Function Parameters

NGUYỄN KHÁNH PHƯƠNG 10

SOICT– HUST

5
 31/03/2022

1.1. Getting the Address of a Variable

• A program being executed by a processor has two major parts: the
code and the data. The code section is the code you've written and the
data section holds the variables you're using in the program.
• All code and variables are loaded into memory (usually RAM) and the
processor executes the code from there. Each segment (usually a byte)
in the memory has an address - whether it holds code or variable -
that's the way for the processor to access the code and variables.

NGUYỄN KHÁNH PHƯƠNG

SOICT– HUST

1.1. Getting the Address of a Variable

• When the program
Addresses inruns, the computer allocated contiguous
Memory
blocks of memory (called as User Space) to user.
• Memory is divided into “memory cells”.
• Each cell has an unique address.
• The size of each cell is 1 byte

Address Value stored in address

12

6
 31/03/2022

1.1. Getting the Address of a Variable

• When a variable is declared, enough memory to hold a value of that
Addresses in Memory
type is allocated for it at an unused memory location. This is the
address of the variable. x
int x; //4 bytes
x = 5;
• Assume variable x is stored in 4
memory cells starting at address 1000110.
• Value of variable x is 5 (4 memory
cells are used to store this value).
• To get the address of first memory cell
allocated to variable x, we use address operator &
 &x will return the value = 1000110
13
Address of variable x

1.1. Getting the Address of a Variable

• The address of a non-array variable can be obtained by using the
Obtaining Memory Addresses
address operator &

70fe0c 70fe08 70fe07

x number ch

• Each variable in program is stored at a unique address

• Use address operator & to get address of a variable

// prints address in hexadecimal 14

7
 31/03/2022

1 Pointers and arrays

1.1. Getting the Address of a Variable
1.2. Pointer Variables
1.3. The Relationship Between Arrays and Pointers
1.4. Pointer Arithmetic
1.5. Initializing Pointers
1.6. Pointers as Function Parameters

NGUYỄN KHÁNH PHƯƠNG 15

SOICT– HUST

1.2. Pointer Variables

• A pointer is a variable that stores the address of something else.
• Declare pointer:
type *pointer_name;
Use asterisk ( * ) to show this is pointer

• There are many types of variables with different sizes, so there are
also many types of pointers. (Example: int pointer to point to a
variable or function of type int).
Example:
int *countPtr; //This is read as “countPtr is a pointer to an int”
double *tPtr; //This is read as “tPtr is a pointer to a double”
• A Pointer may be initialized to 0, NULL, or an address.
• A Pointer that is assigned 0 or NULL points to nothing.

16

8
 31/03/2022

1.2. Pointer Variables

 A pointer is a variable that holds
the address of something else. MEMORY
Address
 Pointer points to the data. 0
1
int x = 123; 2
//Declare an int, assign the value of 123
x 3 123
int *ptr;//declare a pointer to an int 4
//same as int* ptr; 5

...

...
//or int * ptr;
ptr = &x; //assign ptr the memory address of x
ptr 345 3
346
Address of x is value of ptr 347

NGUYỄN KHÁNH PHƯƠNG 17

SOICT– HUST

Dereference a pointer
• To declare pointer: type *pointer_name;
• Assign value to pointer (get address of other object and assign this address to
the pointer): pointer_name = &var_name;
(type of pointer_name and var_name must be the same)
• Access the object that the pointer points to: *pointer_name
(dereference the pointer)
Example:
double foo = 3.2;
double *ptr; ptr =&foo; //double *ptr = &foo;
printf(“%f”,*ptr); // this prints 3.2
• A pointer must have a value before you can dereference it (follow the pointer).

int *ptr; int foo;

*ptr = 3; int *ptr = &foo;
*ptr = 3;

18

9
 31/03/2022

Example: Pointer
int c;
int *ptr; /* declare ptr as an int pointer */
c = 7;
ptr = &c;

printf(“%d”, *ptr); /* print out 7*/

*ptr = 80;
printf(“%d”, c); /* print out 80 */

C
… 7 3 4 …
Address 172 173 174 175 176 177 178 179 180 181

ptr
… 174 3 4 …
Address 832 833 834 835 836 837 838 839 840 841

19

Pointers to anything

x some int
int *x;
int **y;
y some *int some int

double *z;
z some double

NGUYỄN KHÁNH PHƯƠNG 20

SOICT– HUST

10
 31/03/2022

1. Pointers and arrays

1.1. Getting the Address of a Variable
1.2. Pointer Variables
1.3. The Relationship Between Arrays and Pointers
1.4. Pointer Arithmetic
1.5. Initializing Pointers
1.6. Pointers as Function Parameters

NGUYỄN KHÁNH PHƯƠNG 21

SOICT– HUST

1.3. The relationship between arrays and pointers

1.3.1. One dimensional array
1.3.2. Two dimensional array
1.3.3. The relationship between arrays and pointers

NGUYỄN KHÁNH PHƯƠNG 22

SOICT– HUST

11
 31/03/2022

1.3. The relationship between arrays and pointers

1.3.1. One dimensional array
1.3.2. Two dimensional array
1.3.3. The relationship between arrays and pointers

NGUYỄN KHÁNH PHƯƠNG 23

SOICT– HUST

Declaring an one-dimensional array

To declare an array, we need to specify its data type, the array’s identifier and the
size:

type arrayName [arraySize];

Example:
• to create an array scores having 9 elements
of integer type (4 bytes for each element)
• index starts at 0

24

12
 31/03/2022

1D Array: initialization
• Arrays can be initialized with an initialization list:

• The initialization list cannot exceed the array size.

• But it can be less: In this case, the remaining elements are initialized
to 0.
• Note: char str[6] = “Henry”;
//with string initialization, must leave room for \0 at end of array
char str[6] = { ‘H’, ‘e’, ‘n’, ‘r’, ‘y’, ‘\0’}; 25

Exercise 1: How to store user input data into 1D array

Write a program:
• Get 10 integer numbers from the keyboards and store them in 1D
array named A.
• Print these 10 integer numbers in reversed order on the screen.

#include <stdio.h>

int main(void){
int i, A[10];

printf(“Please enter 10 numbers:\n");

for(i=0; i<10; i++)
scanf("%d", &A[i]);

printf(“Numbers in reversed order:\n");

for(i=9; i>=0; i--)
printf("%d\n", A[i]);

return 0;
}
26

13
 31/03/2022

Exercise 1 (Continue)
Write a program:
• Print on the screen the maximum value of these 10 integer numbers
• Print on the screen the minimum value of these 10 integer numbers
• Print on the screen the average value of these 10 integer numbers

NGUYỄN KHÁNH PHƯƠNG 27

SOICT– HUST

Exercise 2
• Write a program that gets an input line from the user (ends with ‘\n’)
and displays the number of times each letter appears in it.

Please enter a line of text: hello, world!

The letter 'd' appears 1 time(s). Input from user

The letter 'e' appears 1 time(s).
The letter 'h' appears 1 time(s).
The letter 'l' appears 3 time(s).
The letter 'o' appears 2 time(s).
The letter 'r' appears 1 time(s).
The letter 'w' appears 1 time(s).

Assume all inputs are lower-case!

#define ALPHABET_LEN 26
int count[ALPHABET_LEN] = {0};

14
 31/03/2022

Get a character from keyboard and print it on screen

int getc(FILE *stream)
int putc(int char, FILE *stream)

int getchar(void)
int putchar(int char)

29

Exercise 2: Solution

#define ALPHABET_LEN 26
int main(void){
int i, count[ALPHABET_LEN] = {0};
char c = '\0';
printf("Please enter a line of text: \n");
/* Read in letter by letter and update the count array */
c = getchar();
while (c != '\n'){
if (c <= 'z' && c >= 'a') ++count[c - 'a’];
c = getchar();
}
for (i = 0; i < ALPHABET_LEN; ++i) {
if (count[i] > 0)
printf("The letter '%c' appears %d time(s).\n", 'a' + i, count[i]);
}
return 0;
}

NGUYỄN KHÁNH PHƯƠNG

SOICT– HUST

15
 31/03/2022

Exercise 3
• Implement a function that accepts two integer arrays of same size and returns 1 if
they are identical, 0 otherwise
– int compare_arrays(int arr1[], int arr2[], int size)

• Write a program that asks user to enter two integer arrays of same size and checks
for the identical by using the above function compare_arrays

arr1 1 2 3 4 5
arr1[0] arr1[1] arr1[2] arr1[3] arr1[4]

size=5
arr2 1 2 3 9 5
arr2[0] arr2[1] arr2[2] arr2[3] arr2[4]

NGUYỄN KHÁNH PHƯƠNG

SOICT– HUST

1.3. The relationship between arrays and pointers

1.3.1. One dimensional array
1.3.2. Two dimensional array
1.3.3. The relationship between arrays and pointers

32

16
 31/03/2022

Declaring two-dimensional array

• How to declare:
<element-type> <arrayName> [size1][size2];
Example: double a[3][4];
may be shown as a table

NGUYỄN KHÁNH PHƯƠNG

SOICT– HUST

Rows of a 2D Array

a[0][0] a[0][1] a[0][2] a[0][3] row 0

a[1][0] a[1][1] a[1][2] a[1][3] row 1
a[2][0] a[2][1] a[2][2] a[2][3] row 2

17
 31/03/2022

Columns of a 2D Array

a[0][0] a[0][1] a[0][2] a[0][3]

a[1][0] a[1][1] a[1][2] a[1][3]
a[2][0] a[2][1] a[2][2] a[2][3]

column 0 column 1 column 2 column 3

2D array: Initialization
int a[3][4] = {1,2,3,4,5,6,7,8,9,10,11,12};
int a[3][4] = {{1,2,3,4},{5,6,7,8}, {9,10,11,12}};
the 2nd method is more readable, because you can visualize the rows and columns of 2D array in this method

a[0][0] = 1 a[0][1]=2 a[0][2]=3 a[0][3]=4

a[1][0] = 5 a[1][1]=6 a[1][2]=7 a[1][3]=8

a[2][0] = 9 a[2][1]=10 a[2][2]=11 a[2][3]=12

When we initialize a 2D array during declaration, we must always

specify the second dimension
int abc[2][2] = {1, 2, 3 ,4 } ; //Valid declaration
int abc[][2] = {1, 2, 3 ,4 }; // Valid declaration
int abc[][] = {1, 2, 3 ,4 }; // Invalid declaration – you must specify second dimension
int abc[2][] = {1, 2, 3 ,4 }; // Invalid declaration – you must specify second dimension

18
 31/03/2022

2D array: Initialization
Example:
const int ROWS = 4, COLS = 3;
int exams[ROWS] [COLS];
int exams[ROWS] [COLS] = { {1,2,5},
{3,4,5},
{6,7,8},
{9,1,1}
};
int exams[ROWS] [COLS] = { {1,2}, {3,4} };

NGUYỄN KHÁNH PHƯƠNG 37

SOICT– HUST

Exercise 4: How to store user input data into 2D array

Write a program:
• Get 20 integer numbers from the keyboards and store them in 2D
array named A[5][4].
• Print these 20 integer numbers as a matrix 5x4 on the screen.
A[0][0]=1 A[0][1]=2 A[0][2]=3 A[0][3]=4

#include<stdio.h> A[1][0]=5 A[1][1]=6 A[1][2]=7 A[1][3]=8

int main(){ A[2][0]=9 A[2][1]=10 A[2][2]=11 A[2][3]=12
int A[5][4];
int i, j; A[3][0]=13 A[3][1]=14 A[3][2]=15 A[3][3]=16
for(i=0; i<5; i++) { A[4][0]=17 A[4][1]=18 A[4][2]=19 A[4][3]=20
for(j=0;j<4;j++) {
printf("Enter value for A[%d][%d]:", i, j);
scanf("%d", &A[i][j]);
}
}

for(i=0; i<5; i++) {

for(j=0;j<4;j++) printf("%d ", A[i][j]);
printf("\n");
}
return 0;
38
}

19
 31/03/2022

1.3. The relationship between arrays and pointers

1.3.1. One dimensional array
1.3.2. Two dimensional array
1.3.3. The relationship between arrays and pointers

NGUYỄN KHÁNH PHƯƠNG 39

SOICT– HUST

Pointer and 1D array

• Array name can be used as a pointer constant:
int a[] = {4, 7, 11, 5, 23};
printf(“%d”,a); //displays address of a[0]
//same as: printf(“%d”,&a[0]);
printf(“%d”,*a); //displays 4 (value of a[0])

• Pointer can be used as an array name:

int *ptr = a; //ptr stores address of a[0]
cout << ptr[1]; //displays 7 (value of a[1])

ptr[i] ~ value of a[i]

&ptr[i] ~ address of a[i]
40

20
 31/03/2022

Pointer in expressions
• Integer math operations can be used with pointers.
• If you increase a pointer, it will be increased by the size of whatever it
points to.
ptr ~ address of a[0]
int a[5]; ptr+i ~ address of a[i]
int *ptr = a; Value of a[i]~ a[i]
~ ???? *(ptr+i)

*ptr *(ptr+2) *(ptr+4) ptr[i] ~ value of a[i]

&ptr[i] ~ address of a[i]

a[0] a[1] a[2] a[3] a[4]

int a[5]; Value of a[i]: a[i] or ptr[i] or *(ptr+i)

int *ptr = a; Address of a[i]: &a[i] or &ptr[i] or (ptr+i)
41

Example
Write C program to print address and value of each element in a 1D-array:
#include <stdio.h>
int main()
{ Result in DevC
int A[ ] = {5, 10, 12, 15, 4}; (sizeof(int)=4)
printf("Address Contents\n“);
for (int i=0; i < 5; i++)
printf(“%d %d \n”,&A[i],A[i]);
return 0;
}

&A[i] : address of element A[i]

A[i] : value of element A[i]
Result in turboC
(sizeof(int)=2)
Memory Location(A[i]) = start_address + W*i
Address Contents
5 10 12 15 4 65516 5
65518 10
65520 12
65522 15
65524 4
start_address=6487536

21
 31/03/2022

Example
Write C program to print address and value of each element in a 1D-array:
#include <stdio.h>
int main()
{ int A[ ] = {5, 10, 12, 15, 4};
printf("Address Contents\n");
for (int i=0; i < 5; i++)
&A[i] : address of element A[i]
printf("%8d %5d\n", &A[i], A[i]); A[i] : value of element A[i]

printf("Address Contents\n");
for (int i=0; i < 5; i++) A+i : address of element A[i]
printf("%8d %5d\n", A+i, *(A+i)); *(A+i) : value of element A[i]

/* print the address of 1D array by using pointer */

int *ptr = A;
printf("Address Contents\n");
ptr+i : address of element A[i]
for (int i=0; i < 5; i++)
*(ptr+i) : value of element A[i]
printf("%8d %5d\n", ptr+i, *(ptr+i));

2D Array: Row-Major Mapping (e.g. Pascal, C/C++)

 Row- major order is a method of representing multi-dimensional array in sequential memory. In
this method, elements of an array are arranged sequentially row by row. Thus, elements of the first
row occupies the first set of memory locations reserved for the array, elements of the second row
occupies the next set of memory and so on.
Elements of Elements of Elements of Elements of
…. ……..
Row 0 Row 1 Row 2 Row i

 Example: int a[4][3]

in ascending direction of memory address

a[0][0] a[0][1] a[0][2] a[1][0] a[1][1] a[1][2]

row 0 row 1 row 2 row 3

NGUYỄN KHÁNH PHƯƠNG

SOICT– HUST

22
 31/03/2022

Example
Write program in C to print address of elements in two-dimensional array:
#include <stdio.h>
Result in DevC
int main()
{ int a[4] [3] = {1,2,3,4,5,6,7,8,9,10,11,12};
(sizeof(int)=4)
printf("Address Contents\n");
for (int i=0; i < 4; i++)
for (int j=0; j < 3; j++)
printf("%8d %5d\n", &a[i][j], a[i][j]);
}

Memory Location(a[i][j]) = start_address + W*[(i*cols) + j]

1 2 3 4 5 6 7 8 9 10 11 12

Location(a[1][2]) = ?
start_address=6487488

1. Pointers and arrays

1.1. Getting the Address of a Variable
1.2. Pointer Variables
1.3. The Relationship Between Arrays and Pointers
1.4. Pointer Arithmetic
1.5. Initializing Pointers
1.6. Pointers as Function Parameters

NGUYỄN KHÁNH PHƯƠNG 46

SOICT– HUST

23
 31/03/2022

1.4. Pointer arithmetic

int a[] = {4,7,11,5,23}; int *ptr = a;
Operation Example
++, -- ptr++; // points at 7
ptr--; // now points at 4
+, - (pointer and int) printf(“%d”,*(ptr + 2)); // 11
+=, -= (pointer and ptr = a; // points at 4
int) ptr += 2; // points at 11
- (pointer from pointer) printf(“%d”, ptr – a);
//difference (number of ints) between ptr and a

<, <=, >, >=, … //compare address in pointers

if(ptr1<ptr2) …
==, != if(ptr1 == ptr2)… //compare addresses
if(*ptr1 == *ptr2)… //compare contents
47

const int SIZE = 8;

int set[SIZE] = {5, 10, 15, 20, 25, 30, 35, 40};
int *numPtr; // Pointer
int count; // Counter variable for loops
// Make numPtr point to the set array.
numPtr = set;
// Use the pointer numPtr to display the array contents.
printf("The numbers in set are:\n“);
for (count = 0; count < SIZE; count++)
{
printf("%d ", *numPtr);
numPtr++;
}
// Display the array contents in reverse order.
printf("\nThe numbers in set backward are:\n");
for (count = 0; count < SIZE; count++)
{
numPtr--;
printf("%d ", *numPtr);
}
return 0;
} 48

24
 31/03/2022

#include <stdio.h>
const int MAX = 100;

int main()
{
int numbers[MAX]; // Array of integers
int SIZE; // Size of the array
int count; // Counter variable

int *ptr = numbers;

printf(“Size of the array = “);scanf(“%d”,&SIZE);
for (count = 0; count < SIZE; count++)
// Get a value to store in numbers[count].
// by using pointer ptr:

printf("Here are the numbers you entered:\n");

for (count = 0; count < SIZE; count++)
// Display a value of the array.
// by using pointer ptr:

return 0; 49
}

1. Pointers and arrays

1.1. Getting the Address of a Variable
1.2. Pointer Variables
1.3. The Relationship Between Arrays and Pointers
1.4. Pointer Arithmetic
1.5. Initializing Pointers
1.6. Pointers as Function Parameters

NGUYỄN KHÁNH PHƯƠNG 50

SOICT– HUST

25
 31/03/2022

1.5. Initializing Pointers

• Can initialize at definition time:
int num, *numptr = &num; int num;
int a[5], *ptr = a; int *numptr;
numptr =&num;

• Cannot mix data types:

double cost;
int *cptr = &cost; //won’t work: because ????
the type of “cost” is double, while “cptr” is the pointer to an
“int” (it is used to store address of variable with type of “int”)

NGUYỄN KHÁNH PHƯƠNG 51

SOICT– HUST

1. Pointers and arrays

1.1. Getting the Address of a Variable
1.2. Pointer Variables
1.3. The Relationship Between Arrays and Pointers
1.4. Pointer Arithmetic
1.5. Initializing Pointers
1.6. Pointers as Function Parameters

NGUYỄN KHÁNH PHƯƠNG 52

SOICT– HUST

26
 31/03/2022

Passing data in function

• Values that are sent into a function are called arguments.
• Two types of passing data to function:
– Passing data by value
– Passing data by reference

NGUYỄN KHÁNH PHƯƠNG 53

SOICT– HUST

Passing data in function

• Values that are sent into a function are called arguments.
• Two types of passing data to function:
– Passing data by value: when an argument is passed to a function, this value is
copied into the parameter.
• Changes to the parameter in the function do not affect the value of the argument

Function parameter
(in its memory allocation)
x= value of v1 = 2;
y= value of v2 =3

Value of v1 and v2 are

sent to the function

Original argument
(in its memory allocation)
v1 = 2; v2 =3

54

27
 31/03/2022

Passing data in function

• Values that are sent into a function are called arguments.
• Two types of passing data to function:
– Passing data by value: when an argument is passed to a function, this value is
copied into the parameter.
• Changes to the parameter in the function do not affect the value of the argument
– Passing data by reference: when an argument is passed to a function, the
pointer to this value (address (location) of the argument) is copied into the
parameter instead of this value.
• Changes to the parameter in the function do affect the value of the argument

Take the addresses of the arguments (v1,

v2) and assign these addresses to the
parameters x, y

55

Passing data in function: Passing data by value

0x70fe0c 0x8123f3

v1 = 2 v2 = 3

28
 31/03/2022

Passing data in function: Passing data by value

0x70fe0c 0x8123f3

v1 = 2 v2 = 3

Before swapping: v1 = 2, v2 = 3

Passing data in function: Passing data by value

0x70fe0c 0x70fe08 0x79fe27 0x8123f3

v1 = 2 x =2 y =3 v2 = 3

Function parameter
(in its memory allocation)
x= 2;
y= 3;

Value of v1 and v2 are

sent to the function
swap, and assigned to
x and y respectively

Before swapping: v1 = 2, v2 = 3

29
 31/03/2022

Passing data in function: Passing data by value

0x70fe0c 0x70fe08 0x71fa03 0x79fe27 0x8123f3

v1 = 2 x =2 tmp = 2 y =3 v2 = 3

Function parameter
(in its memory allocation)
x= 2;
y= 3;

Value of v1 and v2 are

sent to the function
swap, and assigned to
x and y respectively

Before swapping: v1 = 2, v2 = 3

Passing data in function: Passing data by value

0x70fe0c 0x70fe08 0x71fa03 0x79fe27 0x8123f3

v1 = 2 x =2 tmp = 2 y =3 v2 = 3

Function parameter
(in its memory allocation)
x= 2;
y= 3;

Value of v1 and v2 are

sent to the function
swap, and assigned to
x and y respectively

Before swapping: v1 = 2, v2 = 3

30
 31/03/2022

Passing data in function: Passing data by value

0x70fe0c 0x70fe08 0x71fa03 0x79fe27 0x8123f3

v1 = 2 x =3 tmp = 2 y =3 v2 = 3

Function parameter
(in its memory allocation)
x= 2;
y= 3;

Value of v1 and v2 are

sent to the function
swap, and assigned to
x and y respectively

Before swapping: v1 = 2, v2 = 3

Passing data in function: Passing data by value

0x70fe0c 0x70fe08 0x71fa03 0x79fe27 0x8123f3

v1 = 2 x =3 tmp = 2 y =3 v2 = 3

Function parameter
(in its memory allocation)
x= 2;
y= 3;

Value of v1 and v2 are

sent to the function
swap, and assigned to
x and y respectively

Before swapping: v1 = 2, v2 = 3

31
 31/03/2022

Passing data in function: Passing data by value

0x70fe0c 0x70fe08 0x71fa03 0x79fe27 0x8123f3

v1 = 2 x =3 tmp = 2 y =2 v2 = 3

Function parameter
(in its memory allocation)
x= 2;
y= 3;

Value of v1 and v2 are

sent to the function
swap, and assigned to
x and y respectively

Before swapping: v1 = 2, v2 = 3

Passing data in function: Passing data by value

0x70fe0c 0x70fe08 0x71fa03 0x79fe27 0x8123f3

v1 = 2 x =3 tmp = 2 y =2 v2 = 3

Function parameter
(in its memory allocation)
x= 2;
y= 3;

Value of v1 and v2 are

sent to the function
swap, and assigned to
x and y respectively

Before swapping: v1 = 2, v2 = 3
After swapping: v1 = 3, v2 = 2

32
 31/03/2022

Passing data in function: Passing data by reference

0x70fe0c 0x8123f3

v1 = 2 v2 = 3

65

Passing data in function: Passing data by reference

0x70fe0c 0x8123f3

v1 = 2 v2 = 3

Before swapping: v1 = 2, v2 = 3
66

33
 31/03/2022

Passing data in function: Passing data by reference

0x70fe0c 0x70fe08 0x79fe27 0x8123f3

v1 = 2 x = 0x70fe0c y = 0x8123f3 v2 = 3

Function parameter
(in its memory allocation)
x= 0x70fe0c;
y= 0x8123f3 ;

Address of v1 and v2
are sent to the
function swap, and
assigned to x and y
respectively

Before swapping: v1 = 2, v2 = 3
67

Passing data in function: Passing data by reference

0x70fe0c 0x70fe08 0x71fa10 0x79fe27 0x8123f3

v1 = 2 x = 0x70fe0c tmp = 2 y = 0x8123f3 v2 = 3

= *(0x70fe0c) ~ value stored in the address 0x70fe0c

Function parameter
(in its memory allocation)
x= 0x70fe0c;
y= 0x8123f3 ;

Address of v1 and v2
are sent to the
function swap, and
assigned to x and y
respectively

Before swapping: v1 = 2, v2 = 3
68

34
 31/03/2022

Passing data in function: Passing data by reference

0x70fe0c 0x70fe08 0x71fa10 0x79fe27 0x8123f3

v1 = 2 x = 0x70fe0c tmp = 2 y = 0x8123f3 v2 = 3

*x : *(0x70fe0c) ~ value stored in the address 0x79fe0c

*y : *(0x8123f3) ~ value stored in the address 0x8123f3
Function parameter
(in its memory allocation)
x= 0x70fe0c;
y= 0x8123f3 ;

Address of v1 and v2
are sent to the
function swap, and
assigned to x and y
respectively

Before swapping: v1 = 2, v2 = 3
69

Passing data in function: Passing data by reference

0x70fe0c 0x70fe08 0x71fa10 0x79fe27 0x8123f3

v1 = 3 x = 0x70fe0c tmp = 2 y = 0x8123f3 v2 = 3

*x : *(0x70fe0c) ~ value stored in the address 0x79fe0c

*y : *(0x8123f3) ~ value stored in the address 0x8123f3
Function parameter
(in its memory allocation)
x= 0x70fe0c;
y= 0x8123f3 ;

Address of v1 and v2
are sent to the
function swap, and
assigned to x and y
respectively

Before swapping: v1 = 2, v2 = 3
70

35
 31/03/2022

Passing data in function: Passing data by reference

0x70fe0c 0x70fe08 0x71fa10 0x79fe27 0x8123f3

v1 = 3 x = 0x70fe0c tmp = 2 y = 0x8123f3 v2 = 3

*y : *(0x8123f3) ~ value stored in the address 0x8123f3

Function parameter
(in its memory allocation)
x= 0x70fe0c;
y= 0x8123f3 ;

Address of v1 and v2
are sent to the
function swap, and
assigned to x and y
respectively

Before swapping: v1 = 2, v2 = 3
71

Passing data in function: Passing data by reference

0x70fe0c 0x70fe08 0x71fa10 0x79fe27 0x8123f3

v1 = 3 x = 0x70fe0c tmp = 2 y = 0x8123f3 v2 = 2

*y : *(0x8123f3) ~ value stored in the address 0x8123f3

Function parameter
(in its memory allocation)
x= 0x70fe0c;
y= 0x8123f3 ;

Address of v1 and v2
are sent to the
function swap, and
assigned to x and y
respectively

Before swapping: v1 = 2, v2 = 3

36
 31/03/2022

Passing data in function: Passing data by reference

0x70fe0c 0x70fe08 0x71fa10 0x79fe27 0x8123f3

v1 = 3 x = 0x70fe0c tmp = 2 y = 0x8123f3 v2 = 2

*y : *(0x8123f3) ~ value stored in the address 0x8123f3

Function parameter
(in its memory allocation)
x= 0x70fe0c;
y= 0x8123f3 ;

Address of v1 and v2
are sent to the
function swap, and
assigned to x and y
respectively

Before swapping: v1 = 2, v2 = 3
73
After swapping: v1 = 3, v2 = 2

Passing data in function

• Two types of passing data to function:
– Passing data by value: when an argument is passed to a function, this value is
copied into the parameter.
• Changes to the parameter in the function do not affect the value of the argument
– Passing data by reference: when an argument is passed to a function, the
pointer to this value (address (location) of the argument) is copied into the
parameter instead of this value.
• Changes to the parameter in the function do affect the value of the argument

37
 31/03/2022

Exercise 5
• Write a function that accepts a double parameter and returns its
integer and fraction parts.

void split(double num, int *int_part, double *frac_part)

• Write a program that accepts a number from the user and prints out
its integer and fraction parts, using this function.

NGUYỄN KHÁNH PHƯƠNG

SOICT– HUST

Arrays as Function Arguments

76

38
 31/03/2022

Arrays as Function Arguments

• To pass an array to a function, just use the array name:
showScores(a);
• To define a function that takes an array parameter, use empty [] for
array argument:
void showScores(int []); // function prototype
void showScores(int a[]) // function header
• When passing an array to a function, it is common to pass array size so
that funtion knows how many elements to process:
showScores(a, ARRAY_SIZE);
void showScores(int [], int); // function prototype
void showScores(int a[], int size) // function header

NGUYỄN KHÁNH PHƯƠNG 77

SOICT– HUST

Arrays as Function Arguments

•When an entire array is passed to a function, it is not passed by value, but passed by
reference.
– Why does not passed by value ?: Imagine the CPU time and memory that would be
necessary if a copy of a 10,000-element array were created each time it was passed
to a function! Instead, only the starting memory address of the array is passed.
 Changes made to array in a function are reflected in actual array in calling function

#include <stdio.h>

for (int index=0; index < ARRAY_SIZE; index++)

printf(“%d ”,numbers[index]);

for (int index=0; index < size; index++)

printf*(“%d”,num[index]);
printf*(“%d”,num[index]);
nums[index]*=2; 78

39
 31/03/2022

Printing an array
void print_array(int a[], int len) {
for (i=0;i<len;i++)
printf(“a[%d] = %d \n“,i,a[i]);
}

void print_array(int *a, int len) {

for (i=0;i<len;i++)
printf(“a[%d] = %d\n“,i,*a++);
}

void print_array(int *a, int len) {

for (i=0;i<len;i++)
printf(“a[%d] = %d \n“,i,a[i]);
} NGUYỄN KHÁNH PHƯƠNG 79
SOICT– HUST

Printing an array

80

40
 31/03/2022

Exercise 6
 Write a program that includes the following functions:
 Input values for an array
 Increase all values of the array by 2
 Print out an array
 You should use pointers to access the array. The array is
passed as function parameters
Array version:
void input_array(int a[], int len);
void change_array(int a[], int len);
void print_array(int a[], int len);
Pointer version:
void input_arrayP(int *a, int len);
void change_arrayP(int *a, int len);
void print_arrayP(int *a, int len);
81

Exercise 6: Array version

82

41
 31/03/2022

Exercise 6: Pointer version (1)

83

Exercise 6: Pointer version (2)

84

42
 31/03/2022

Two-Dimensional Arrays
• Passing two-dimensional array to functions: use empty [] for row, size
declarator for column in prototype, header:
const int COLS = 2;
void getExams(int [] [COLS], int); // prototype
void getExams(int exams [] [COLS], int rows); // header

C requires the columns to be specified in the function prototype and header

because of the way two-dimensional arrays are stored in memory. One row
follows another, as shown in the following figure:
Elements of Elements of Elements of Elements of
…. ……..
Row 0 Row 1 Row 2 Row i

NGUYỄN KHÁNH PHƯƠNG 85

SOICT– HUST

Exercise 7
Write a program to
• get the size of a matrix : row, col
• Get the elements of two matrices with that size: Arow*col and Brow*col
• Calculate the addition of two matrices

NGUYỄN KHÁNH PHƯƠNG

SOICT– HUST 86

43
 31/03/2022

Exercise

87

Exercise 8
Write a program to
• get the size of a matrix : row, col
• Get the elements of two matrices with that size: Arow*col and Brow*col
• Calculate the addition of two matrices

Rewrite so that the above program using function to

add two Matrices

void CalSum(int[][MAX], int [][MAX], int, int, int [][MAX]);

NGUYỄN KHÁNH PHƯƠNG

SOICT– HUST 88

44
 31/03/2022

Exercise 8

89

Exercise 8

NGUYỄN KHÁNH PHƯƠNG

SOICT– HUST 90

45
 31/03/2022

Homework 1
Write:
1) Function int countNum(int n) returns the total of all
numbers in the range [1, n] that satisfy one of the two
following conditions:
a. Both divisible for 3 and 5
b. Divide by 3 remainder 2, divide by 5 remainder 3
2) A program to get an integer n≥1, then call the function
countNum above to get the result.

NGUYỄN KHÁNH PHƯƠNG 91

SOICT– HUST

Homework 2
Write a program to get an integer n ≥ 2 and two square matrix
An*n and Bn*n; then calculate A*B.
Note: Using two-dimensional array to store the square matrix

NGUYỄN KHÁNH PHƯƠNG 92

SOICT– HUST

46
 31/03/2022

Contents
1. Pointers and arrays
2. String
3. Struct data type
4. Dynamic allocation
5. Input/output with text files
6. Input/output with binary files

NGUYỄN KHÁNH PHƯƠNG 93

SOICT– HUST

2. String
• An array of characters.
• You can initialize strings in a number of ways:

Terminator

 In order to hold a string of n characters, we need an array of length n + 1

Example: char c[5] = "abcde";
Here, we are trying to assign 6 characters (the last character is '\0') to
a char array having 5 characters. This is bad and you should never do this.
[Error] initializer-string for array of chars is too long [-fpermissive]

47
 31/03/2022

String and character related function

• getchar() Taking character input from keyboard
– Example: char c = getchar();
• scanf() Taking string/character input without space from keyboard
– Example:
• char str[20]; scanf("%s", str);
But, it accepts string only until it finds the first space.

• char c; scanf("%c", &c);

NGUYỄN KHÁNH PHƯƠNG

SOICT– HUST

Taking String input with space in C

• gets() Taking string/character input with space from keyboard
– Example: char str[20]; gets(str);

Note :
gets() has been removed from c11. So it might give you a warning when
implemented.
We see here that it doesn’t bother about the size of the array. So, there is a
chance of Buffer Overflow.

NGUYỄN KHÁNH PHƯƠNG

SOICT– HUST

48
 31/03/2022

Taking String input with space in C (cont.)

• char *fgets(char *str, int size, FILE *stream)
– Example: fgets(str, 20, stdin);
as here, 20 is MAX_LIMIT according to declaration.

String and character related function

• strlen(const char str[])
returns the length of string str
• strcmp(const char str1[], const char str2[])
compares str1 with str2
• strcpy(char str1[], const char str2[])
copies to contents of str2 to str1

NGUYỄN KHÁNH PHƯƠNG

SOICT– HUST

49
 31/03/2022

String and character related function

• strlen(const char str[])
returns the length of string str

NGUYỄN KHÁNH PHƯƠNG

SOICT– HUST

String and character related function

• strcmp(const char str1[], const char str2[])
compares str1 with str2

50
 31/03/2022

String and character related function

• strcpy(char str1[], const char str2[])
copies to contents of str2 to str1

NGUYỄN KHÁNH PHƯƠNG

SOICT– HUST

Exercise 9
• Write a function that:
– gets a string and two chars
– the functions scans the string and replaces every occurrence of the
first char with the second one.
void replace(char str[], char replace_what, char replace_with)
• Write a program to test the above function
– the program gets from the keyboard a string (no spaces) and two
characters, then calls the function with the input, and prints the
result on screen.
Example
– input: “papa”, ‘p’, ‘m’
– output: “mama”

NGUYỄN KHÁNH PHƯƠNG

SOICT– HUST

51
 31/03/2022

Exercise 10
• Write a function with the prototype:
void replace_char(char *str, char c1, char c2);
• It replaces each appearance of c1 by c2 in the string str.
• Demonstrate your function with a program that uses it

NGUYỄN KHÁNH PHƯƠNG

SOICT– HUST

Contents
1. Pointers and arrays
2. String
3. Struct data type
4. Dynamic allocation
5. Input/output with text files
6. Input/output with binary files

NGUYỄN KHÁNH PHƯƠNG 104

SOICT– HUST

52
 31/03/2022

3. Struct
• Example:

struct {
int numerator;
int denominator;
} fraction;
[Link] = 13;
[Link] = 17;

NGUYỄN KHÁNH PHƯƠNG 105

SOICT– HUST

Record name vs. field name

Just like in an array, we have two types of identifier in a record:
• the name of the record, and
• the name of each individual field inside the record.
The name of the record is the name of the whole structure, while the name of each field
allows us to refer to that field.
Example: in the student record:
• the name of the record is student,
• the name of the fields are [Link], [Link] and [Link].
Most programming languages use a period (.) to separate the name of the structure
(record) from the name of its components (fields).

106

53
 31/03/2022

Comparison of records and arrays

We can compare an array with a record. This helps us to understand when we should
use an array and when to use a record:
• An array defines a combination of elements, while a record defines the identifiable
parts of an element.
• For example, an array can define a class of students (40 students), but a record
defines different attributes of a student, such as id, name or grade.
• Array of records: If we need to define a combination of elements and at the same
time some attributes of each element, we can use an array of records. For example,
in a class of 30 students, we can have an array of 30 records, each record
representing a student.

107
Figure 1. Array of records

Variable declaration with/without using typedef

#include<stdio.h> #include<stdio.h>
#include<stdio.h>
struct Point{ typedef struct Point{
struct Point{
int x; int x;
int x;
int y; int y;
int y;
}; } Point;
};
typedef struct Point Point;
int main() {
int main() { int main() {
struct Point p1;
Point p1; Point p1;
p1.x = 1;
p1.x = 1; p1.x = 1;
p1.y = 3;
p1.y = 3; p1.y = 3;
printf("%d \n", p1.x);
printf("%d \n", p1.x); printf("%d \n", p1.x);
printf("%d \n", p1.y);
printf("%d \n", p1.y); printf("%d \n", p1.y);
return 0;
return 0; return 0;
}
} }

Method 1 Method 2
Without using typdef Using typdef

The C language contains the typedef keyword to allow users to

provide alternative names for struct data type. NGUYỄN KHÁNH PHƯƠNG 108
SOICT– HUST

54