Data Structures
and Algorithms
Week 1
Lecturers :
Cao Tuan Dung
Trinh Thanh Trung
Department of Software Engineering
Hanoi University of Science and Technology
Introduction
• C Programming practice in UNIX
environment.
• Programming topics related to [Data
Structures and Algorithms]
• Compiler: gcc
• Editor: Emacs, K-Developper.
gcc syntax
• Parameter:
-Wall : turn on all alerts
-c: make object file
-o: name of output file
-g: debug information
-l: library
gcc –Wall hello.c –o runhello
./runhello
This week: Basic Data
Structures and Algorithms
• Topic:
– Array, String, Pointer Review
– Character based File operations in UNIX
– Programming Exercises
Array
• A block of many variables of the same
type
• Array can be declared for any type
– E.g. int A[10] is an array of 10 integers.
• Examples:
– list of students’ marks
– series of numbers entered by user
– vectors
– matrices
Arrays in Memory
• Sequence of variables of specified type
• The array variable itself holds the
address in memory of beginning of
sequence
• Example:
double S[10]; … 0 1 2 3 4 5 6 7 8 9 …
• The k-th element of array A is specified
by A[k-1] (0-based)
Example - reverse
#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;
}
Exercise
• 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.
The output for the input line: “hello, world!”
The letter 'd' appears 1 time(s).
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!
Exercise (20 minutes)
• Implement a function that accepts
two integer arrays and returns 1 if
they are equal, 0 otherwise
• Write a program that accepts two
arrays of integers from the user and
checks for equality
Home Exercise 1
• Redo the program which compares
two integer array that not use the
size parameter.
String
• An array of characters
• Used to store text
• Another way to initialize:
char str[] = "Text";
…. 'H'
's' 'e'
'#' ''l'' 'f'
'l' 'o'
'd' 'y'
'' 'w'
'4' 'o'
'7' '$'
'r' '_'
'l' 'd'
'e' 'g'
'\0' 'd' '.' 'p' 'v' ….
str
Terminator
String
• In order to hold a string of N
characters we need an array of
length N + 1
• So the previous initialization is
equivalent to
char str[] = {'b', 'l', 'a', 'b', 'l',
'a', '\0'};
String and character related
function
• getchar()
– c = getchar()
• scanf
– scanf("%s", str);
• gets()
– gets(str);
String and character related
function
– strlen(const char s[])
returns the length of s
– strcmp(const char s1[],
const char s2[])
compares s1 with s2
– strcpy(char s1[],
const char s2[])
copies to contents of s2 to s1
Exercise
• 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.
• write a program to test the above function
– the program should read a string from the
user (no spaces) and two characters, then call
the function with the input, and print the
result.
• example
– input: “papa”, ‘p’, ‘m’
– output: “mama”
Pointer - Declaration
type *variable_name;
• A pointer is declared by adding a
* before the variable name.
• Pointer is a variable that contains
an address in memory.
• The address should be the
address of a variable or an array
that we defined.
Pointers
– Here ptr is said to point to the address
of variable c
C
… 7 3 4 …
172 173 174 175 176 177 178 179 180 181
Ptr
… 174 3 4 …
832 833 834 835 836 837 838 839 840 841
Referencing and
Dereferencing
int n;
int *iptr; /* Declare P as a pointer to int */
n = 7;
iptr = &n;
printf(“%d”, *iptr); /* Prints out ‘7’*/
*iptr = 177;
printf(“%d”, n); /* Prints out ‘177’ */
iptr = 177; /* This is unadvisable!! */
Exercises
Write a function that accepts a double
parameter and returns its integer
and fraction parts.
Write a program that accepts a
number from the user and prints out
its integer and fraction parts, using
this function.
Exercise
• 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.
Do not use the [] operator!
• Demonstrate your function with a
program that uses it
Command line arguments
• Command line arguments are
arguments for the main function
– Recall that main is basically a function
– It can receive arguments like other
functions
– The ‘calling function’ in this case is the
operating system, or another program
‘main’ prototype
int main(int argc, char* argv[])
• When we want main to accept
command line arguments, we must
define it like this
– argc holds the number of arguments that
were entered by the caller
– argv is an array of pointers to char – an
array of strings – holding the text values of
the arguments
• The first argument is always the
program’s name
‘main’ prototype
int main(int argc, char* argv[])
argc : 3
argv :
p t 1
r e 7
o x 8
g t \0
n \0
a
m
e
\0
Exercise
• Write a program that accepts two
numbers as command line
arguments, representing a
rectangle’s height and width (as
floating-point numbers).
• The program should display the
rectangle’s area and perimeter
Homework
• Write a command line program that
calculates ex with the following
syntax:
• E 50