Class introduction (for everyone, starting with the tutor):
There is no "correct" answer for this exercise.
(Unless your tutor asks you what is your favourite beer, in which case the Correct Answer is any of BrewDog's "Sink The Bismarck" or Moon Dog Brewing's "Jumping the Shark 2013" or Ballast Point Brewing's "Grapefruit Sculpin". A Very Wrong answer to the question is VB or Toohey's New or Corona or Heineken or Peroni.)
Consider the following program (adapted from Sedgewick):
#include <stdlib.h> #include <stdio.h> #include <assert.h> int main(int argc, char *argv[]) { int i, j, *a; int N = 0; // initialisation for (i = 2; i < N; i++) a[i] = 1; // computation for (i = 2; i < N; i++) { if (a[i]) { for (j = i; i*j < N; j++) a[i*j] = 0; } } // results for (i = 2; i < N; i++) { } }
Try to answer each of the following questions about this program:
for
loops; does this matter?
sscanf(argv[1],"%d",&N);
doing?
sscanf(...)
statement?
assert
s ...
assert
a[0]
and a[1]
during execution?
a[0]
and a[1]
matter?
No, it doesn't matter. If a C control structure
(if
, else
, while
, for
)
has a "body" which is a single statement, braces are not required.
An alternative way of stating this is that all of the above control
structures have a "body" which is a single statement and braces
{...}
are a grouping mechanism that allows a collection
of statements to be treated as a single statement.
The sscanf
allows you to apply scanf
-style
extraction of data values from a string instead of a file.
This particular sscanf
is converting the first
command-line argument (argv[1]
) into an integer value
(%d
) and storing this value in the variable N
.
The following would produce a similar effect to the sscanf
:
N = atoi(argv[0]);
To find whether there are any subtle differences, take a look at
the man
entries for sscanf()
and atoi()
.
assert(argc > 1)
...
N
has been supplied available as the first
command-line argument (the first element on the command-line is always
the name of the command
Usage: a.out Number, where Number is positive
assert(N > 0)
...
N
)
is positive; since this value is being used to allocate an array of size N
,
it doesn't make sense to have a negative size
assert(a != NULL)
...
N
can be arbitrarily large (up to 231-1), it is
possible that a request could be made for such a large array that malloc()
cannot allocate the space
Cannot allocate space for array // but maybe not meaningful to a user Max number is too large // but this is not the only possible reason why malloc() might fail
The array elements a[0]
and a[1]
are never assigned a value,
so they contain random rubbish.
Since a[0]
and a[1]
are never accessed during the execution
(check the for
loops), it doesn't matter what their values are.
The program implements the "Sieve of Eratosthenes", a very old algorithm
for determining prime numbers. It does this by using an array to hold a true/false
value for each of the first N
integers; if a[i]
is true, this
means that i
is a prime number. The algorithm sets up this array by first
assuming that all of the numbers from 2..N
are prime. It then makes
multiple scans through the array, "eliminating" as potential prime numbers, any
numbers which are multiples of smaller numbers.
A C program has several means of interacting with its run-time environment.
Describe what each of the following is and what it is used for:
argc
,
argv
,
stdin
,
stdout
,
stderr
,
exit()
.
argc
: is an integer argument to the main()
function
that indicates how many arguments were typed on the command line that
invoked the program. Since it includes the name of the command, it always
has a value that is at least 1.
argv
: is an array of strings, argument to the main()
function
that contains the strings for the arguments that were typed on the command line
that invoked the program. argv[0]
is always the name of the executable
file of the program.
stdin
: is an input stream (type FILE *
) that is open when
the program starts and can be used to read program input. By default, it is
connected to the keyboard, but can be redirected to come from a file.
stdout
: is an output stream (type FILE *
) that is open when
the program starts and can be used as a destination for program output. By
default, it is connected to the screen, but can be redirected so that the
output is sent to a file.
stderr
: is an output stream (type FILE *
) that is open when
the program starts and can be used as a destination for program output. By
default, it is connected to the screen, but can be redirected so that the
output is sent to a file. Note that redirection of stderr
and
stdout
are independent, so you can redirect one without redirecting
the other.
exit()
: is a function that can be called to terminate execution of
the program. It takes a single integer argument which is used as the exit
status of the program. The exit status can be used by the program's
environment to determine whether the program completed successfully (exit
status of zero) or whether there was an error (exit status non-zero).
Consider a program called myprog
which is invoked as:
$ ./myprog hello there, 'John Shepherd' > myFile
What are the values of argc
and argv
?
Where would the statement printf("%s",argv[1])
place its output?
Where would the statement ch = getchar();
get its input?
argc
has the value 4; argv[0]
is "./myprog"
,
argv[1]
is "hello"
, argv[2]
is "there,"
,
argv[3]
is "John Shepherd"
printf
would place its output in the file myFile
getchar()
would get its input from the keyboard
Which of the following statements are equivalent? Which are incorrect?
Assume that x
is an int
variable.
scanf("%d", x);
scanf("%d", &x);
printf("%d", x);
fscanf(stdin, "%d", &x);
fscanf(stderr, "%d", &x);
fprintf(stdout, "%d", x);
fprintf(stderr, "%d", x);
(b) and (d) are equivalent. (c) and (f) are equivalent. (g) would have the
same effect as (c) and (f) if none of the output streams have been redirected.
(a) is incorrect (passing int
value rather than int *
).
(e) is incorrect (can't read from an output stream).
Define a swap()
function that exchanges two elements in an array.
For an array a[]
and two indexes i
and j
,
we could exchange the i'th and j'th elements by the call:
swap(a, i, j)
The function is defined as:
void swap(int a[], int i, int j) { int tmp; tmp = a[i]; a[i] = a[j]; a[j] = tmp; }
It would also be possible to define it using the C pre-processor:
#define swap(a,i,j) \
({ int tmp; tmp = a[i]; a[i] = a[j]; a[j] = tmp; })
Using the macro would result in (slightly) more efficient run-time. Only useful if we were doing a very large amount of swapping.
Consider the following simple linked-list representation and a function that sums the values in the list:
typedef struct _Node { int value; struct _Node *next; } Node; typedef Node *List; // pointer to first Node
Write a function to sum the values in the list.
Implement it first using while
and then using for
.
Finally, implement it using recursion.
Version using while
:
int sumOfList(List L) { Node *cur = L; int sum = 0; while (cur != NULL) { sum += cur->value; cur = cur->next; } return sum; }
Version using for
:
int sumOfList(List L) { Node *cur; int sum = 0; for (cur = L; cur != NULL; cur = cur->next) { sum += cur->value; } return sum; }
Recursive version:
int sumOfList(List L) { if (L == NULL) return 0; else return L->value + sum(L->next); }
Important: Make sure you can properly understand and effectively use the following topics (covered in COMP1511). In case you have any questions, please discuss them with your tutor.