Skip to main content

Section D.5 Exercise Sheet 5

1. printf.

Complete the following program so that it prints the array numbers in different representations.

#include <stdio.h>

int main(void) {
  int numbers[] = {-13427, -4233, -343, -12, -5, 0,
                   3, 17, 512, 2355, 29367};
  int n = /* Compute the amount of elements in numbers */

  for (int i=0; i < n; ++i) {
    printf("%d ", zahlen[i]); // This line must be changed for each subtask
  }

  return 0;
}

First, compute the number of elements in the array by use of sizeof. Afterwards, print the array in the following representations:

  1. In hexadecimal representation with preceding 0x and padded with zeroes up to size 8, e.g. 0x00000012. Which type of argument does the format specifier for hexadecimal representation expect?

  2. Every number divided by 1000, rounded to 2 decimal places.

  3. The numbers as usual decimal numbers, but with the sign of the number in front (i.e. also +).

Every subtask must be solved using the standard library function printf and the corresponding formatting string.

printf is a function with a variable number of arguments, i.e. calls of the form printf(format, x_1, ..., x_n) are viable for all \(n\text{.}\) As the format, a string is passed which may contain format specifiers. In the printed output, the \(i\)-th format specifier is replaced by the corresponding formatted representation of \(x_i\text{.}\) A format specifier has the form

%[flags][min field width][precision][length]conversion specifier

where all parameters enclosed in [] are optional. A description of the parameters can be found on the manpage for printf. You can view it with the command man 3 printf.

Remark: You should learn to find the relevant parts and extract the required information from the manpage.

202207281550

202205131400
Solution.

#include <stdio.h>

int main(void) {
  int numbers[] = { -13427, -4233, -343, -12, -5, 0, 3, 17, 512, 2355, 54367 };
  
  int n = sizeof(numbers) / sizeof(numbers[0]);

  for (int i = 0; i < n; ++i) {
    // part (a)
    printf("0x%08x\t", (unsigned int)numbers[i]);
    // part (b)
    printf("%.2f\t", numbers[i] / 1000.0);
    // part (c)
    printf("%+d\n", numbers[i]);
  }
  return 0;
}

2. scanf.

Write a program which calculates the body mass index (BMI). To this end, you must read the body height \(h\) as a floating point number, as well as the mass \(m\) in kilograms as an integer. Afterwards, print the BMI which is specified by the following equation:

\begin{equation*} b = \frac{m}{h^2} \end{equation*}

To read the numbers, use the standard library function scanf, which functions analogously to printf. scanf uses format specifiers similar to printf:

%[max field width][type modifier]conversion specifier

Be aware that scanf expects the address of the container in which the input should be written. You can look up the description of scanf on the manpage, which you open with the command man scanf, or if you want to read the German page: LANG=de_DE man scanf.

202207281550

202205131400
Solution.

#include <stdio.h>

int main(void) {
  float h, b;
  int m;

  printf("Body height (in m): ");
  scanf("%f", &h);
  printf("Body weight (in kg): ");
  scanf("%d", &m);

  b = m / (h * h);

  printf("bmi = %f\n", b);

  return 0;
}

3. Simple-Calc.

Konrad Klug has lost his calculator for integer calculations. Help him by writing a C program which reads an expression

          <Integer_1> <Operator> <Integer_2>

from the standard input and prints the result in the form

          <Integer_1> <Operator> <Integer_2> = <Result>

on the next line. Your calculator should support addition (+), substraction (-), multiplication (*) and division (/).

202207281550

202205131400
Solution.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char* argv[]) {
    int x = 0;
    int y = 0;
    char op = 0;
    char* s = calloc(64, sizeof(char));

    printf("Please enter the expression to be calculated: ");
    scanf("%d %c %d", &x, &op, &y);

    sprintf (s,"%d %c %d = ", x, op, y );
    int slen = strlen(s);
    s += slen;

    switch(op){
        case '+':
            sprintf (s, "%d", (x + y));
            break;
        case '-':
            sprintf (s, "%d", (x - y));
            break;
        case '*':
            sprintf (s, "%d", (x * y));
            break;
        case '/':
            sprintf (s, "%d", (x / y));
            break;
        default:
            sprintf(s - slen, "Invalid input!");
            break;
    }

    s -= slen;
    printf( "%s \n", s);

    free(s);
    return 0;
}

4. Using malloc Correctly.

Konrad Klug learned a lot about malloc and free today, but he has not drunk enough coffee before he tried to put his new knowledge into practice. Find the errors involving malloc and free in his code. Shortly explain each error.

  1. Array reverse:

    // Reverses an array, returns pointer to reversed array of equal size
// arrayptr: Base address of the array
// arraysize: Number of elements in the array
int *arrayrev(int *arrayptr, int arraysize) {
    int *ret = malloc(arraysize);
    for(int i = 0; i < arraysize; i++){
        ret[i] = arrayptr[arraysize-i-1];
    }

    return ret;
}

  2. Print 5:

    // prints the number 5 twice
void broken() {
    int a = 5;
    int *b = malloc(sizeof(int));
    *b = 5;
    printf("two numbers: %d, %d\n", a, *b);

    free(&a);
    free(&b);
}

  3. Squares:

    // prints squares of the numbers in [1, upto].
void quadratics(int upto) {
    for(int i = 1; i <= upto; i++){
        int *a = malloc(sizeof(int));
        *a = i*i;
        printf("i*i =  %d\n", *a);
    }

    free(a);
}

  4. Why does the code in i) work, but not the code in ii)?

    1. Code 1:

      int main() {
    int array[] = {10, 20, 30, 40};
    int elements = sizeof(array) / sizeof(int);
        for(int i = 0; i < elements; i++){
            printf("%d\n", array[i]);
        }
    }
}

    2. Code 2:

      void printArray(int array[]) {
    int elements = sizeof(array) / sizeof(int);
    for(int i = 0; i < elements; i++){
        printf("%d\n", array[i]);
    }
}

int main() {
    int array[] = {10, 20, 30, 40};
    printArray(array);
}

202207281550

202205131400
Solution.

  1. malloc expects the size of the memory to be allocated in bytes, not in the number of elements. The following would be correct:

    int *ret = malloc(arraysize * sizeof(int));

  2. free expects a pointer to a container which was allocated by malloc. The container of the local variable a is automatically deallocated when the surrounding block (here: the function) is left and must therefore not be freed with free. Additionally, free(&b) is an error, since b is already a pointer to memory allocated by malloc. The following would be correct: free(b)

  3. It is attempted to refer to the variable a when using free. This variable is however only defined in the block of the for-loop. This leads to a compilation error. Although the container is automatically freed after every loop iteration, but this is not the case for the container the address in a points to. This leads to a memory leak which can be fixed by moving free(a) to the end of the for-loop behind printf.

  4. When executing ii) only the first few elements (depending on the processor architecture and operating system more or less many) are printed. The problem is that int array[] in the parameter list of the function printArray is only syntactical sugar for int* array. Thus, sizeof(array) evaluates only to the size of an int* value. For the other code, sizeof(array) evaluates to the amount of bytes in the array.

    When compiling the erroneous with gcc, the compiler prints a helpful warning:

    warning: 'sizeof' on array function parameter
'array' will return size of 'int *'.

5. malloc and Strings.

  1. Write a function which takes an integer parameter and returns a new C string “False” if the argument is 0. For every other value, the function should return “True”, also as a new string. The function shall store the return value in a local variable and return it afterwards. Allocate the memory for the string using malloc()!

  2. Write a main function which receives a number as a command line parameter and uses the function you implemented in a) to print “False” if a 0 was passed and “True” otherwise. Make sure to manage the memory correctly.

    Hint: The arguments of the main function are always passed as char arrays. You can use the standard library function atoi to transform the string representation of a decimal number to the numeric value. For example: int x = atoi("1234"); // x = 1234

  3. On the next day, Rainer Wahnsinn and Konrad Klug meet each other. Konrad Klug is amazed by the abilities of his fellow. However, Konrad would like to return “Richtig” and “Falsch” instead of “True” and “False”. Unfortunately, he caught a virus so that he cannot change the functions he already wrote, except for the main function.

    Write a function char* convert_to_german(char*) which transforms a given string into the German equivalent (“True” to “Richtig” and “False” to “Falsch”). For the case where neither “True” nor “False” are passed, the function shall return the C string “Undefiniert”.

    Attention: Also make sure to correctly allocate and deallocate the used memory here! It could make sense to use the standard library function strcmp.

  4. Rainer Wahnsinn has caught a rare encrypting virus which encrypted his string.h file! Help him by providing your own implementation of the strcpy function.

    Tip: You can display the specification of strcpy with man strcpy.

    Test your implementation by using it in your implementation of a).

202207281550

202205131400
Solution.

  1. Solution for subtask a):

    #include <stdlib.h>
#include <string.h>

char* bool_eval(int x) {
    char* ret = NULL;
    if (x == 0) {
        ret = malloc(6 * sizeof(char));
        strcpy(ret, "False");
    }
    else {
        ret = malloc(5 * sizeof(char));
        strcpy(ret, "True");
    }
    return ret;
}

  2. Solution for subtask b):

    #include <stdio.h>
#include <stdlib.h>

int main(int argc, char* argv[]) {
    if (argc != 2) {
        fprintf(stderr, "Invalid number of arguments!\n");
    }
    else {
        char* test = bool_eval(atoi(argv[1]));
        printf("%s\n", test);
        free(test);
    }
}

  3. Solution for subtask c):

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* bool_eval(int x) {
    char* ret = NULL;
    if (x == 0) {
        ret = malloc(6 * sizeof(char));
        strcpy(ret, "False");
    }
    else {
        ret = malloc(5 * sizeof(char));
        strcpy(ret, "True");
    }
    return ret;
}

char* convert_to_german(char* string) {
    if (strcmp(string, "True") == 0) {
        string = realloc(string, 8 * sizeof(char));
        strcpy(string, "Richtig");
        return string;
    }
    if (strcmp(string, "False") == 0) {
        string = realloc(string, 7 * sizeof(char));
        strcpy(string, "Falsch");
        return string;
    }
    string = realloc(string, 12 * sizeof(char));
    strcpy(string, "Undefiniert");
    return string;
}

int main(int argc, char* argv[]) {
    if (argc != 2) {
        fprintf(stderr, "Invalid number of arguments!\n");
    }
    else {
        char* test = bool_eval(atoi(argv[1]));
        test = convert_to_german(test);
        printf("%s\n", test);
        free(test);
    }
}

  4. Solution for subtask d):

    #include <stdio.h>
#include <stdlib.h>

char* strcpy(char* s1, const char* s2) {
    char* s = s1;
    while ((*s++ = *s2++) != 0);
    return s1;
}

char* bool_eval(int x) {
    char* ret = NULL;
    if (x == 0) {
        ret = malloc(6 * sizeof(char));
        strcpy(ret, "False");
    }
    else {
        ret = malloc(5 * sizeof(char));
        strcpy(ret, "True");
    }
    return ret;
}

int main(int argc, char* argv[]) {
    if (argc != 2) {
        fprintf(stderr, "Invalid number of arguments!\n");
    }
    else {
        char* test = bool_eval(atoi(argv[1]));
        printf("%s\n", test);
        free(test);
    }
}

6. Functions and Pointers - Powers.

Take a look at the following program:

#include <stdio.h>

float pow(int n, float x);

int main() {
    float y = pow(3, 2.71);
    printf("%.3f\n", y);
    return 0;
}

  1. Implement the function float pow(int n, float x); which returns the \(n\)-th power of the number \(x\text{.}\)

  2. No Hau learned about pointers in the last lecture and now wants to modify pow in such a way that no return value is needed. To this end, she writes a function void pow_shiny(int n, float x, float *y);. Imitate No Hau and implement the functionpow_shiny. Afterwards, change the above program where needed to use your new function pow_shiny instead of pow.

  3. Extend pow so that for numbers \(n < 0\) or \(x < 0\) the value 0 is returned. Also modify pot_shiny such that the program immediately aborts under the above conditions or when the passed pointer points to NULL.

  4. We now want to compare the results of the previous tasks. Write a function float pot_switch(int n, float x, int b); which returns the \(n\)-th power of \(x\) using pow if \(b = 0\) and using pow_shiny otherwise. Adapt the main function only by returning the value of the comparison

    pot_switch(3, 2.71, 0) != pot_switch(3, 2.71, 1)

    Make yourself clear when the program terminates with 0.

202207281550

202205131400
Solution.

  1. Solution Code:

    float pow(int n, float x) {
    float y = 1;
    while (n-- > 0)
        y *= x;
    return y;
}

  2. Solution Code:

    #include <stdio.h>

void pow_shiny(int n, float x, float *y);

int main() {
    float y = 0.0f;
    pow_shiny(3, 2.71, &y);
    printf("%.3f\n", y);
    return 0;
}

void pow_shiny(int n, float x, float *y) {
    *y = 1;
    while (n-- > 0)
        *y *= x;
}

  3. Solution Code:

    float pot(int n, float x) {
    if (n < 0 || x < 0)
        return 0;
    ...
}

void pot_shiny(int n, float x, float *y) {
    if (n < 0 || x < 0 || !y)
        return;
    ...
}

  4. Solution Code:

    float pot(int n, float x);
void pot_shiny(int n, float x, float *y);
float pot_switch(int n, float x, int s);

int main() {
    return pot_switch(3, 2.71, 0) != pot_switch(3, 2.71, 1);
}

float pot_switch(int n, float x, int b) {
    if (b) {
        float y = 0;
        pot_shiny(n, x, &y);
        return y;
    }
    return pot(n, x);
}
...

7. Functions and Pointers - Finding Errors.

Konrad Klug is amazed by pointers and has written the following program which checks if a positive integer has digit sum 7.

int mod_ten(int x) {
    return x % 10;
}

void div_ten(int *x) {
    x = *x / 10;
}

void quer(int *a, int b) {
    if (a > 0)
        b = b + mod_ten(a);
    div_ten(a);
    quer(a, b);
}

int main() {
    int a = 322;
    int b;
    quer(a, &b);
    return b = 7;
}

However, Konrad realizes that some bugs have nested in his code after he spilled a cup of coffee over his keyboard, which causes some of the keys to be stuck. Help Konrad by correcting the bugs in his program.

202207281550

202205131400
Solution.

int mod_ten(int x) {
    return x % 10;
}

void div_ten(int *x) {
    *x = *x / 10;
}

void quer(int *a, int *b) {
    if (*a > 0) {
        *b = *b + mod_ten(*a);
        div_ten(a);
        quer(a, b);
    }
}

int main() {
    int a = 322;
    int b = 0;
    quer(&a, &b);
    return b != 7;
}

8. Queue.

Farmer John wants to implement a new system for his milking machine by milking his cows in order of registrations: If a cow wants to be milked, it registers itself on the milking machine using its ID number. If the milking machine is not occupied, and no other cow has registered before the cow, the cow is the next to be milked by the milking machine.

Konrad Klug thinks that this can be implemented by a FIFO (first-in, first-out) queue with the operations pushBack() and popFront(). A linked list is viable as the underlying data structure. In a linked list, an element also contains a pointer to the next element in addition to the element value.

To this end, Konrad built a small code skeleton and wants you to implement the functions createQueueElem(), pushBack(), and popFront(). If you implemented everything correctly, the numbers 1, 2, and 3 should be printed in this order.

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct Queue Queue;
typedef struct QueueElem QueueElem;

struct QueueElem {
    int value;
    QueueElem* successor;
};
struct Queue {
    QueueElem* front;
    QueueElem* back;
};

QueueElem* createQueueElem(int value) {
    // TODO
}

void pushBack(Queue* queue, int value) {
    // TODO
}

int popFront(Queue* queue) {
    // TODO
}

int main() {
    Queue myQueue = {NULL, NULL};
    pushBack(&myQueue, 1);
    pushBack(&myQueue, 2);
    pushBack(&myQueue, 3);
    
    printf("%d\n", popFront(&myQueue));
    printf("%d\n", popFront(&myQueue));
    printf("%d\n", popFront(&myQueue));
    
    return 0;
}

202207281550

202205131400
Solution.

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct Queue Queue;
typedef struct QueueElem QueueElem;

struct QueueElem {
    int value;
    QueueElem *successor;
};

struct Queue {
    QueueElem *front;
    QueueElem *back;
};

QueueElem *createQueueElem(int value) {
    QueueElem *element = (QueueElem *) malloc(sizeof(QueueElem));
    element->value = value;
    return element;
}

void pushBack(Queue *queue, int value) {
    QueueElem *element = createQueueElem(value);
    if (queue->front == NULL) {
        queue->front = element;
    } else {
        queue->back->successor = element;
    }
    element->successor = NULL;
    queue->back = element;
}

int popFront(Queue *queue) {
    assert(queue->front != NULL);
    int returnValue = queue->front->value;
    QueueElem *firstElem = queue->front;
    if (firstElem->successor == NULL) {
        queue->back = NULL;
    }
    queue->front = firstElem->successor;
    free(firstElem);
    return returnValue;
}

int main() {
    Queue myQueue = {NULL, NULL};
    pushBack(&myQueue, 1);
    pushBack(&myQueue, 2);
    pushBack(&myQueue, 3);

    printf("%d\n", popFront(&myQueue));
    printf("%d\n", popFront(&myQueue));
    printf("%d\n", popFront(&myQueue));

    return 0;
}

9. Binary Tree.

Konrad Klug wants to write a C program which sorts data from an input file with the help of binary trees. Unfortunately, Konrad is unable to get it right and needs your help to complete his program.

Implement a binary search tree with integer keys, which has strings of length 20 (including the null terminator) as values. Stick with the code skeleton given by Konrad and implement the functions and structs as instructed by the comments. Be aware of the binary search tree invariant: All keys in the left subtree are smaller and all keys in the right subtree are larger than the key of their parent node.

Proceed as follows:

  1. First, write a struct node, which saves all needed information in addition to key and value.

  2. Implement the function createNewNode which allocates memory for a new node and initializes the key and value.

  3. Implement the function insertNode. It may be helpful to make use of createNewNode.

  4. Implement the function freeTree which frees all memory allocated by the tree.

  5. printInOrder shall print all elements of the tree sorted in ascending order of their keys.

  6. Lastly, implement the function getNameById which returns the value in the binary search tree for a given key.

Hint: It may be useful to use recursion in some places. You may also use the standard library function in string.h.

Use the following template: 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BUF_SIZE 20

typedef struct node node;

/**
 * A binary search tree node.
 */
struct node {
    // TODO
};

/**
 * Initializes a new node.
 */
node* createNewNode(int n, char* name){
    // TODO
}

/**
 * Inserts a node with key n and value name into the tree given by root.
 */
void insertNode(node** root, int n, char* name) {
    // TODO
}

/**
 * Prints all key-value pairs in the tree in order of their keys.
 */
void printInOrder(node* root) {
    // TODO
}

/**
 * Finds a value for a given key.
 */
char* getNameById(node* root, int id) {
    // TODO
}

int main (int argc, char* argv[]) {
    node* tree = NULL;
    int val;
    char name[BUF_SIZE];

    FILE* in = fopen("data.txt", "r");

    while (fscanf(in, "%d %s", &amp;val, name) == 2) {
        insertNode(&amp;tree, val, name);
    }

    printf("Tree:\n");
    printInOrder(tree);
    printf("\n");

    printf("%s\n", getNameById(tree, 5));
    printf("%s\n", getNameById(tree, 10));
}

What is the result of the program for the following file which was selected randomly from Konrad's computer?

5 garden
10 four
1 my
-6 In
17 binary
22 trees
8 there
9 are

202207281550

202205131400
Solution.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BUF_SIZE 20

typedef struct node node;

/**
 * A binary search tree node.
 */
struct node {
    int id;
    char name[BUF_SIZE];
    node* left;
    node* right;
};

/**
 * Initializes a new node.
 */
node* createNewNode(int n, char* name){
    node* new_node = calloc(1, sizeof(*new_node));
    new_node->id = n;
    strcpy(new_node->name, name);
    return new_node;
}

/**
 * Inserts a node with key n and value name into the tree given by root.
 */
void insertNode(node** root, int n, char* name){
    if (*root == NULL) {
        *root = createNewNode(n, name);
    } else if (n < (*root)->id) {
        insertNode(&(*root)->left, n, name);
    } else {
        insertNode(&(*root)->right, n, name);
    }
}

/**
 * Frees the dynamically allocated memory for the binary tree.
 */
void freeTree(node* root){
    if(root == NULL){
        return;
    } else {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

/**
 * Prints all key-value pairs in the tree in order of their keys.
 */
void printInOrder(node* root){
    if (root == NULL) {
        return;
    } else {
        printInOrder(root->left);
        printf("ID: %d name: %s \n", root->id, root->name);
        printInOrder(root->right);
    }
}

/**
 * Finds a value for a given key.
 */
char* getNameById(node* root, int id){
    if(root == NULL) {
        return "------ No matching Name ------";
    } else if (root->id == id) {
        return root->name;
    } else if (id < root->id) {
        return getNameById(root->left, id);
    } else {
        return getNameById(root->right, id);
    }
}

int main (int argc, char* argv[]){
    node* tree = NULL;
    int val;
    char name[BUF_SIZE];

    FILE* in = fopen("data.txt", "r");

    while (fscanf(in, "%d %s", &val, name) == 2) {
        insertNode(&tree, val, name);
    }

    printf("Tree:\n");
    printInOrder(tree);
    printf("\n");

    printf("%s\n", getNameById(tree, 5));
    printf("%s\n", getNameById(tree, 10));
}

Output: 

Tree:
ID: -6 name: In
ID: 1 name: my
ID: 5 name: garden
ID: 8 name: there
ID: 9 name: are
ID: 10 name: four
ID: 17 name: binary
ID: 22 name: trees

garden
four

10. Defined or Undefined?

For the following programs, find out if their execution is uniquely defined by the C11 standard. You may assume that enough memory is available.

  1. Task a: 

    #include <stdio.h>
int main() {
    int a[15];
    for (int i = 0; i < 15; i++) {
        a[i] = 14 - i;
    }
    int x = 3[a];
    printf("Value of x: %i\n", x);
    return 0;
}

  2. Task b: 

    #include <stdio.h>
int main() {
    int x = 0;
    int y = 42 % x;
    return 0;
}

  3. Task c: 

    #include <stdio.h>
int main() {
    printf("%f\n", 0);
    return 0;
}

  4. Task d: 

    #include <stdio.h>
int sum(int x, int y) {
    return x + y;
}

int main() {
    int i = 5;
    int res = sum(i*i, ++i);
    printf("result of sum: %i", res);
    return 0;
}

  5. Task e: 

    #include <stdio.h>
int main() {
    int a[10];
    for (int i = 0; i < 11; i++) {
        a[i] = a + i;
    }
    return 0;
}

  6. Task f: 

    #include <stdio.h>
int main() {
    char* p = NULL;
    char c = *p;
    return 0;
}

  7. Task g: 

    #include <stdio.h>
int foo() {
    int a = 1234;
    double b = 12.34;
}

int main() {
    int x = foo();
    return 0;
}

  8. Task h: 

    #include <stdio.h>
int main() {
    int x;
    x ^= x;
    return x;
}

202207281550

202205131400
Solution.

  1. The program contains no undefined behaviour. The output of the program is Value of x: 11. The expression 3[a] is only syntactical sugar for *(3+a) and therefore valid.

  2. The behaviour of division / modulo by zero is undefined.

  3. The behaviour is undefined. %f expects a value of type double, but 0 is of type int.

  4. The C standard does not mandate in which order the arguments to a function are evaluated. The resulting situation is called “unsequenced read/write” and the behaviour is undefined in this case, since it is uncertain whether i is incremented or read first.

  5. The behaviour is undefined. The calculation a + i is allowed, also for the case i = 10, since pointers to the element behind the array may be used. But the access a[i] in the case i = 10 is invalid, since you may only access the elements of the array. Additionally, the access needs a conversion from a pointer to int, which is implementation defined and may therefore produce undefined behaviour.

  6. Dereferencing a null pointer is undefined behaviour.

  7. Undefined behaviour occurs since main calls the function foo and accesses the return value, but foo lacks a return statement.

  8. Reading uninitialized memory leads to undefined behaviour. Not only the value itself is undefined, otherwise one could think that the program would always return 0, but the entire program behaviour is undefined. This means the program could also crash with an error message or continue running with \(\texttt{x} \neq 0\text{.}\)

11. Argument Parser.

In this exercise, you must implement a calculator. Your program must read the expression to evaluate from the command line. For this, you must write a so-called argument parser, argparser in short. To this end, use the function getopt, which you must import via #include <getopt.h> Your program must accept the parameters h, x, y, r and c:

  1. -h: Prints a short program usage description

  2. -r <char>: After -r, the character describing the operation follows (+, -, *, /)

  3. -x <float>: After -x, the first operand (as a float) of the operation follows

  4. -y <float>: After -y, the second operand (as a float) of the operation follows

  5. -c <char*>: After -c, a string to be printed follows.

If -h is specified, the program does not expect any additional parameters and stops immediately after printing the usage description. In all other cases, the parameters x, y and r must be specified, while c is optional. You can find information regarding getopt in the manpage using the command man 3 getopt.

  1. Implement the operations +, - and / for your calculator. Print the results with a precision of 5 decimal points.

  2. Extend the calculator with the operation *. What do you notice when you try to execute the program with this parameter?

  3. Extend the calculator with the -c comment option. Test the program with arbitrary input strings. Which problem do you notice?

  4. Find solutions for the problems in b) and c).

202207281550

202205131400
Solution.
#include <stdio.h> 
#include <stdlib.h>
#include <getopt.h>

int calculate(float x, float y, char r);

int main(int argc, char *argv[]) {
    char c;
    
    float x, y;
    char r;
    
    int xflag = 0;
    int yflag = 0;
    int rflag = 0;

    while ((c = getopt(argc, argv, "hx:y:r:c:")) != -1) {
        switch (c) {
            case 'h':
                printf("The following parameters are allowed:\n\
  -r <char>: Operator, which specifies the operation\n\
  -x <float>: First operand of the given operation\n\
  -y <float>: Second operand of the given operation\n\
  -c <char*>: arbitrary comment\n\
The parameters -r, -x and -y must always be specified!\n");
                exit(0);
                
            case 'x':
                x = atof(optarg);
                xflag = 1;
                break;
            
            case 'y':
                y = atof(optarg);
                yflag = 1;
                break;
                
            case 'r':
                r = *optarg;
                rflag = 1;
                break;
                
            case 'c':
                printf("Kommentar: %s\n", optarg);  
                break;  
                
            case '?':
                if ((optopt == 'x') || (optopt == 'y') || (optopt == 'r')) {
                    printf("Parameter -%c needs exactly on argument! \
Specify -h for additional help.\n", optopt);
                } else {
                    printf("Error: Parameter -%c unknown.\n", optopt);
                }
                exit(1);

            default:
                printf("Error: optind %i, argc %i\n", optind, argc);
                exit(1);
        }
    }
        
    if (rflag == 0 || xflag == 0 || yflag == 0) {
        printf("Not all required parameters were specified! \
Specify -h for additional help.\n");
        exit(1);
    }
        
    int ret = calculate(x, y, r);
    exit(ret);
}


int calculate(float x, float y, char r) {
    switch(r) {
        case '+':
            printf("%.5f + %.5f = %.5f\n", x, y, x+y);
            return 0;
        case '*':
            printf("%.5f * %.5f = %.5f\n", x, y, x*y);
            return 0;
        case '-':
            printf("%.5f - %.5f = %.5f\n", x, y, x-y);
            return 0;
        case '/':
            printf("%.5f / %.5f = %.5f\n", x, y, x/y);
            return 0;
        default:
            printf("Operator %c unknown!\n", r);
            return 1;
    }
}

If the above program is for example called with

./calculator -x 3 -y 4 -r *

then * will not be read correctly. The reason is that * is already interpreted by the Bash shell.

To fix this problem, one can call the above program with

./calculator -x 3 -y 4 -r '*'

or

./calculator -x 3 -y 4 -r \*

To supply a parameter containing spaces to the comment option c, one also has to wrap the string in quotes:

./calculator -x 3 -y 4 -r + -c "Hallo Welt!"

Without the quotes, everything after the space will not be read, resulting in only "Hallo" being read.

12. Calendar.

Write a C program which can be used as a basis to implement a calendar. Your program shall:

  1. Declare a struct in which an event can be stored. An event consists of a title, and a date (for the sake of simplicity, we ignore start and end times here).

  2. Declare a struct representing a date. A date consists of a day, month and year.

  3. Add the option to read appointments via the console. A date is always read in the order: day, month, year.

  4. Be able to print a date to the console.

  5. Challenge: Organize all events in a data structure of your choice and print them all in chronological order.

  6. Challenge: Write all events stored in the data structure to a file and read all events saved in the file at the beginning of the program.

202207281550

202205131400
Solution.
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// b.
typedef struct {
    int year;
    int month;
    int day;
} Date;

// a.
typedef struct {
    Date *date;
    char *title;
} Event;

Date* init_Date(int day, int month, int year) {
    Date *date = malloc(sizeof(Date));
    date->year = year;
    date->month = month;
    date->day = day;
    return date;
}

Event* init_Event(char *title) {
    Event *event = malloc(sizeof(Event));
    event->title = title;
    return event;
}

void destroy_Event(Event *event) {
    free(event->date);
    free(event->title);
    free(event);
}

// d. (pass stdout to print to console)
void print_Event(Event *event, FILE* fp) {
    fprintf(fp, "%02d.%02d.%04d %s\n", event->date->day,
            event->date->month, event->date->year, event->title);
}

// c. (pass stdin to read from console)
Event *read_Event(FILE* fp) {
    int day, month, year;
    Event *event = init_Event(malloc(sizeof(char) * 256));
    int i = fscanf(fp, "%d.%d.%d %255[^\n]s", &day, &month, &year, event->title);
    if (i != 4) {
        free(event->title);
        free(event);
        return NULL;
    };
    event->date = init_Date(day, month, year);
    return event;
}

//Begin Challenge 1

typedef struct list {
    Event* event;
    struct list* next;
} List;

List* read_Events(List* old_list, FILE* fp) {
    int i;
    if (fp == stdin) {
        printf("How many events? ");
        if (scanf("%d", &i) != 1) {
            return NULL;
        }
    } else {
        i = 0;
        int c;
        while ((c = fgetc(fp)) != EOF) {
            if (c == '\n') i++;  // #events
        }
        rewind(fp);  // need to reset position in file
    }
    List* list = NULL;
    List **tail = &list;
    for (; i > 0; i--) {
        *tail = malloc(sizeof(List));
        (*tail)->event = read_Event(fp);
        (*tail)->next = NULL;
        if ((*tail)->event == NULL)
            return NULL;
        tail = &(*tail)->next;
    }
    if (old_list != NULL) {
        *tail = old_list;
    }
    return list;
}

int compare_Date(Date* a, Date* b) {
    if (a->year < b->year) {
        return -1;
    }
    if (a->year > b->year) {
        return 1;
    }
    if (a->month < b->month) {
        return -1;
    }
    if (a->month > b->month) {
        return 1;
    }
    if (a->day < b->day) {
        return -1;
    }
    return a->day > b->day;
}

//clever pointer-to-pointer magic that properly unlinks
Event *unlink_max(List** delete_entry) {
    List *list = *delete_entry;
    if (!list) return NULL;

    Event* max = list->event;
    List* last = list;
    list = list->next;
    while (list) {
        if (compare_Date(list->event->date, max->date) > 0) {
            max = list->event;
            delete_entry = &last->next;
        }
        last = list;
        list = list->next;
    }
    if (max != NULL) {
        List* tofree = *delete_entry;
        (*delete_entry) = (*delete_entry)->next;
        free(tofree);
    }
    return max;
}

List* bubblesort(List* in) {
    List* newlist = NULL;
    while (in) {
        Event* event = unlink_max(&in);
        List* next = newlist;
        newlist = malloc(sizeof(List));
        newlist->next = next;
        newlist->event = event;
    }
    return newlist;
}

void print_List(List* list, FILE* fp) {
    for (;list;list = list->next) {
        Event* event = list->event;
        print_Event(event, fp);
    }
}

void destroy_List(List* list) {
    List* next;
    while (list) {
        next = list->next;
        destroy_Event(list->event);
        free(list);
        list = next;
    }
}

//End Challenge 1

//Begin Challenge 2

/* we only define the name of the data file here for the other parts see:
 * - read_Events for reading the events from the file
 * - print_List for writing the appointments to the file
 * Note: read_Events can also read from the console
 */
#define FILENAME "Events.txt"

//End Challenge 2

int main() {
    // read stored appointments in the beginning
    FILE *fp = fopen(FILENAME, "a+");
    List* list = read_Events(NULL, fp);
    fclose(fp);

    list = read_Events(list, stdin); // read console
    if (!list) {
        fprintf(stderr, "Error while reading!\n");
        return 1;
    }
    list = bubblesort(list);
    print_List(list, stdout);

    // write all appointments in the end, creating the file if necessary
    fp = fopen(FILENAME, "w");
    print_List(list, fp);
    fclose(fp);

    destroy_List(list);
    return 0;
}

13. Doubly Linked Lists.

Implement insertion and removal for doubly linked lists without using a dummy list element. Make sure that:

  • prev of the first element and next of the last element are both always NULL (in contrast to the implementation as a ring in the lecture notes).

  • head always points to the first element of the list and tail to the last unless the list is empty, in that case both should be NULL .

Use the following struct and implement the five declared functions.

#include <stdlib.h>
#include <assert.h>

struct list_node_t {
    int element;
    struct list_node_t* prev;
    struct list_node_t* next;
};
typedef struct list_node_t list_node_t;

list_node_t* list_root_init(list_node_t** head, list_node_t** tail) {
    *head = NULL;
    *tail = NULL;
}
Run

Compare your implementation with the one in the lecture notes:

  • Why do you need the arguments head and tail in contrast to the implementation as a ring, where the root element is not passed to in the functions for insertion and removal?

  • Why do you need a separate function to prepend an element, but don't need it in the other implementation?

  • Why do you need functions for prepending (appending) at head (tail)?

202207281550

202205131400
Solution.
        struct list_node_t {
            int element;
            struct list_node_t* prev;
            struct list_node_t* next;
        };
        typedef struct list_node_t list_node_t;

        list_node_t* list_root_init(list_node_t** head, list_node_t** tail) {
            *head = NULL;
            *tail = NULL;
        }

        list_node_t* list_prepend_at_head(list_node_t** head, list_node_t** tail,
                                          int element) {
Run

  • The dummy list node in the other implementation is the analog to the head and tail pointers in this one. But there the first and last list element have pointers to the dummy node, thus it is accessible from within the list. This is not the case when the first and last elements point to NULL, so we have to pass them as double pointers to be able to change them appropriately.

  • In the implementation as a ring we can always just append it to the previous list node instead of prepending (or vice versa: instead of appending we could prepend to the next node). Here, the previous (or next) node does not necessarily exist, so there has to be some case distinction.

  • Appending to the dummy node is equivalent to list_prepend_at_head and prepending to the dummy node is equivalent to list_append_at_tail. Without (one of) these functions it would not be possible to add the first element to an empty list.

14. Balanced Binary Trees.

Prove:

For a balanced tree of height \(h\) and size \(n\text{,}\) holds:

\begin{equation*} h \leq 2\log_2 n\text{.} \end{equation*}
202207281550

202205131400
Solution.

We first prove the dual formulation of the above statement:

\begin{equation*} n \geq 2^{h/2}\text{.} \end{equation*}

To do this, we introduce the minimal size of a balanced tree of height \(h\) as \(s_{min}(h)\text{.}\)

\(h = 0:\)

The tree is a single node.

\begin{equation*} s_{min}(h) := 1\text{.} \end{equation*}

\(h = 1:\)

The tree is either a root with a single child or a root node with two children. The first case has less nodes, so we define:

\begin{equation*} s_{min}(h) := 2\text{.} \end{equation*}

\(h-1,h\rightarrow h + 1:\)

By the definition of height, one subtree has height \(h-1\text{.}\) Using proof by contradiction, we can show that the other subtree has height \(h-2\) as the size \(s_{min}\) would not be minimal otherwise. By recursion, we obtain the minimal sized trees for \(h-1\) and \(h-2\text{.}\)

\begin{equation*} s_{min}(h+1) := s_{min}(h) + s_{min}(h-1) + 1\text{.} \end{equation*}

By definition of \(s_{min}\text{,}\) we have for every tree of size \(n\) and height \(h\text{:}\)

\begin{equation*} n \geq s_{min}(h)\text{.} \end{equation*}

We show \(s_{min} \geq 2^{h/2}\) to obtain \(n\geq 2^{h/2}\) by transitivity.

By complete induction on \(h\text{:}\)

\(h = 0:\)

\begin{equation*} s_{min}(h) = s_{min}(0) = 1 \geq 1 = 2^{0} = 2^{h/2}\text{.} \end{equation*}

\(h = 1:\)

\begin{equation*} s_{min}(h) = s_{min}(1) = 2 \geq \sqrt{2} = 2^{0.5} = 2^{h/2}\text{.} \end{equation*}

\(h = 2:\)

\begin{align*} s_{min}(h) \amp= s_{min}(h-1) + s_{min}(h-2) + 1\\ \amp = s_{min}(1) + s_{min}(0) + 1\\ \amp = 2 + 1 = 3 \geq 2 = 2^{1}\\ \amp = 2^{h/2} \end{align*}

\(h-1,h\rightarrow h + 1:\)

Induction hypothesis: \(s_{min}(h-1)\geq 2^{(h-1)/2} = 2^{h/2-1}\)

\begin{align*} s_{min}(h+1) \amp= s_{min}(h) + s_{min}(h-1) + 1\\ \amp = (s_{min}(h-1) + s_{min}(h-2) + 1) + s_{min}(h-1) + 1\\ \amp = 2s_{min}(h-1) + s_{min}(h-2) + 2\\ \amp \geq 2s_{min}(h-1) \\ \amp \overset{IH}{\geq} 2\cdot 2^{h/2-1}\\ \amp = 2^{h/2} \end{align*}

Lastly, we obtain from \(n\geq 2^{h/2}\) the inequality:

\begin{equation*} h \leq 2\log_2(n)\text{.} \end{equation*}