Programming in C Exam Review and Practices (II)

Posted on Edited on In Views: Symbols count in article: 16k Reading time ≈ 14 mins.

Here is a series of general study guides to college-level C programming courses. This is the second part covering dynamic memory allocation, advanced pointer operations, recursion, linked list and tree common functions, etc.

Dynamic Memory Allocation

  • Given the following definitions:

    1
    2
    3
    4
    int *pi = NULL;
    float *pf = NULL;
    char *pc = NULL;
    char my_string[] = "Hello, World!";

    write statements to do the following memory operations:

    • reserve space for 100 integers and assign a pointer to that space to pi

      1
      2
      pi = (int *)malloc(sizeof(int) * 100);
      assert(pi != NULL);

    • reserve space for 5 floats and assign a pointer to that space to pf

      1
      2
      pf = (float *)malloc(sizeof(float) * 5);
      assert(pf != NULL);

    • unreserve the space that pi points to

      1
      2
      free(pi);
      pi = NULL;

    • reserve space for enough characters to hold the string in my_string and assign a pointer to that space to pc. Copy my_string into that space.

      1
      2
      3
      pc = (char *)malloc(strlen(my_string) + 1));
      assert(pc != NULL);
      strcpy(pc, mystring);

    • free everything that hasn't been unreserved yet.

      1
      2
      3
      4
      free(pc);
      free(pf);
      pc = NULL;
      pf = NULL;

  • What happens if you reserve memory and assign it to a pointer named p and then reserve more memory and assign the new pointer to p? How can you refer to the first memory reservation?
    If you reserve then assign then reserve more memory you will have a memory leak. If you want to refer to the first pointer, you can set a new pointer to point to the new one before reserving more memory.

  • Does it make sense to free() something twice? What's a good way to prevent this from happening?
    No, it doesn’t make sense to free something twice, a good way to prevent this is setting the thing you freed to NULL after freeing it.

Advanced Pointer Operations

  • Suppose p is a pointer to a structure and f is one of its fields. What is a simpler way of saying: x = (*p).f;.

    1
    x = p->f;

  • Given the following declarations and definitions:

    1
    2
    3
    4
    struct s {
    	int x;
    	struct s *next;
    };
    what will the following code print?

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    struct s *p1 = NULL;
    struct s *p2 = NULL;
    struct s *p3 = NULL;
    struct s *p4 = NULL;
    struct s *p5 = NULL;
    p5 = malloc(sizeof(struct s));
    p5->x = 5;
    p5->next = NULL;
    p4 = malloc(sizeof(struct s));
    p4->x = 4;
    p4->next = p5;
    p3 = malloc(sizeof(struct s));
    p3->x = 3;
    p3->next = p4;
    p2 = malloc(sizeof(struct s));
    p2->x = 2;
    p2->next = p3;
    p1 = malloc(sizeof(struct s));
    p1->x = 1;
    p1->next = p2;
    printf("%d %d\n", p1->next->next->next->x, p2->next->x);

    It will print "4 3".

  • Write a subroutine called do_allocate that is passed a pointer to the head pointer to a list of block structures: do_allocate(struct block **). If the head pointer is NULL, do_allocate should allocate a new struct block and make the head pointer point to it. If the head is not NULL, the new struct block should be prepended to the list, and the head pointer set to point to it.

    This is a linked list insertion function. New data items should always be inserted into the front of the list. Note the input argument has to be a pointer to pointer to make a change to the original head pointer. A sample solution is shown below

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    #include <stdlib.h>

    struct block {
        int data;
        struct block *next;
    };

    void do_allocate(struct block **head) {
        struct block *new_block = malloc(sizeof(struct block));
        if (new_block == NULL) {
            // Handle memory allocation failure
            return;
        }

        // Initialize the new block
        new_block->data = 0;
        new_block->next = *head;

        // Update the head pointer
        *head = new_block;
    }

  • Write a subroutine called my_free that will accept a pointer to a pointer of some arbitrary type and:

    • free the space pointed to by the pointer
    • set the pointer to NULL

    1
    2
    3
    4
    5
    6
    7
    8
    #include <stdlib.h>

    void my_free(void **ptr) {
        if (ptr != NULL && *ptr != NULL) {
            free(*ptr);
            *ptr = NULL;
        }
    }

  • Given the following declaration:

    1
    2
    3
    4
    5
    struct employee {
        char *name;
        char *title;
        int id;
    };
    write a subroutine called create_employee that accepts two string parameters for the new name and title and one integer parameter for the ID. It should return a newly allocated Employee structure with all of the fields filled in.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    #include <stdlib.h>
    #include <string.h>

    struct employee *create_employee(const char *name, const char *title, int id)
    {
        struct employee *new_employee = malloc(sizeof(struct employee));
        if (new_employee == NULL) {
            return NULL;
        }

        // Allocate memory for the name and copy the string
        new_employee->name = malloc(strlen(name) + 1);
        if (new_employee->name == NULL) {
            free(new_employee);
            return NULL;
        }
        strcpy(new_employee->name, name);

        // Allocate memory for the title and copy the string
        new_employee->title = malloc(strlen(title) + 1);
        if (new_employee->title == NULL) {
            free(new_employee->name);
            free(new_employee);
            return NULL;
        }
        strcpy(new_employee->title, title);

        // Set the ID
        new_employee->id = id;

        return new_employee;
    }

  • Write a subroutine called fire_employee that accepts a pointer to pointer to struct employee, frees its storage and sets the pointer that points to the storage to NULL.

    1
    2
    3
    4
    5
    6
    7
    8
    void fire_employee(struct employee **emp_ptr) {
        if (emp_ptr != NULL && *emp_ptr != NULL) {
           	free((*emp_ptr)->name);
           	free((*emp_ptr)->title);
           	free(*emp_ptr);
           	*emp_ptr = NULL;
        }
    }

Recursion

  • Create a recursive function to compute the factorial function.

    1
    2
    3
    4
    unsigned long long factorial(unsigned int n) {
        if (n == 0) return 1;
        return n * factorial(n - 1);
    }

  • Create a recursive function to compute the Nth element of the Fibonacci sequence: 0 1 1 2 3 5 8 13 21 34 55 ...

    1
    2
    3
    4
    5
    unsigned int fibonacci(unsigned int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

  • Implement a recursive list search. e.g. each function call should either return the list node that it's looking at because it matches the search item or it should return the value from calling itself on the next item in the list.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    struct Node {
        int data;
        struct Node* next;
    };

    struct Node* search(struct Node* node, int value) {
        if (node == NULL) return NULL;

        if (node->data == value) {
            return node;
        } else {
            // Recursive call on the next node
            return search(node->next, value);
        }
    }

Linked List Functions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};


// Assume the list is ordered with decreasing date values,
// insert before all nodes with less or equal data values.
// [7, 5, 5, (new:4), 4, 2, 1]

void insertBefore(struct Node** head, struct Node* newNode) {
    if (*head == NULL) {
        // If the head is NULL, insert the new node as the first node
        newNode->next = NULL;
        *head = newNode;
        return;
    }

    // The first node's value is less than or equal to the new node's,
    // insert the new node as the new first node.
    if ((*head)->data <= newNode->data) {
        newNode->next = *head;
        *head = newNode;
        return;
    }

    struct Node* current = *head;
    while (current->next != NULL && current->next->data > newNode->data) {
        current = current->next;
    }

    newNode->next = current->next;
    current->next = newNode;
}

// Assume the list is ordered with decreasing date values,
// insert after all nodes with greater or equal data values.
// [7, 5, 5, 4, (new:4), 2, 1]

void insertAfter(struct Node** head, struct Node* newNode) {
    if (*head == NULL) {
        // If the head is NULL, insert the new node as the first node
        newNode->next = NULL;
        *head = newNode;
        return;
    }

    // The first node's value is less than the new node's,
    // insert the new node as the new first node.
    if ((*head)->data < newNode->data) {
        newNode->next = *head;
        *head = newNode;
        return;
    }

    struct Node* current = *head;
    while (current->next != NULL && current->next->data >= value) {
        current = current->next;
    }

    newNode->next = current->next;
    current->next = newNode;
}

void insertAtBeginning(struct Node** head, struct Node* newNode) {
    newNode->next = *head;
    *head = newNode;
}

void insertAtTail(struct Node** head, struct Node* newNode) {
    if (*head == NULL) {
        *head = newNode;
        return;
    }

    struct Node* current = *head;
    while (current->next != NULL) {
        current = current->next;
    }

    current->next = newNode;
    newNode->next = NULL;
}

void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}

int main() {
    struct Node* head = NULL;
    struct Node* node1 = (struct Node*)malloc(sizeof(struct Node));
    node1->data = 1;
    node1->next = NULL;

    struct Node* node2 = (struct Node*)malloc(sizeof(struct Node));
    node2->data = 3;
    node2->next = NULL;

    struct Node* node3 = (struct Node*)malloc(sizeof(struct Node));
    node3->data = 5;
    node3->next = NULL;

    insertAtBeginning(&head, node1);
    insertAfter(&head, node2);
    insertBefore(&head, node3, 4);
    insertAtTail(&head, node3);

    printf("Linked list after insertion: ");
    printList(head);

    return 0;
}

Tree Common Functions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

struct Node* createNode(int value) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

struct Node* insertNode(struct Node* root, int value) {
    if (root == NULL) {
        return createNode(value);
    }

    if (value < root->data) {
        root->left = insertNode(root->left, value);
    } else if (value > root->data) {
        root->right = insertNode(root->right, value);
    }

    return root;
}

struct Node* minValueNode(struct Node* node) {
    struct Node* current = node;
    while (current && current->left != NULL) {
        current = current->left;
    }
    return current;
}

struct Node* maxValueNode(struct Node* node) {
    struct Node* current = node;
    while (current && current->right != NULL) {
        current = current->right;
    }
    return current;
}

void inorderTraversal(struct Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

int main() {
    struct Node* root = NULL;
    root = insertNode(root, 50);
    insertNode(root, 30);
    insertNode(root, 20);
    insertNode(root, 40);
    insertNode(root, 70);
    insertNode(root, 60);

    printf("Inorder traversal: ");
    inorderTraversal(root);
    printf("\n");
    
    return 0;
}

Local, Static and Global Variables

  • Try the following two programs to appreciate the differences between static and non-static local variables.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    void try() {                    void try() {
        int x = 0;                      static int x = 0;
        if (x == 0) {                   if (x == 0) {
            x = 5;                          x = 5;
        }                               }
        x++;                            x++;
        printf("X = %d\n", x);          printf("X = %d\n", x);
    }                                }
    int main() {                     int main() {
        int i=0;                         int i=0;
        for (i=0; i<10; i++)             for (i=0; i<10; i++)
            try();                           try();
    }                                }
    // Output "X = 6" always         // Output "X = 6/7/8/..."

  • What happens if you define a global variable with a static storage class in one module and attempt to refer to that variable in a different module?
    The variable will not be accessible in the other module. This is because static variables have internal linkage by default, meaning they are only accessible within the same module.

  • Can a function be declared with a static storage class? If so, how? If not, why not?
    Yes, you can declare a function with the static storage class, you can use the static keyword. It means that the function has internal linkage, which restricts its scope to the current translation unit (i.e., the source file in which it is defined). This means that the function can only be called from within the same source file, and its name is not visible outside of that file.

  • Create a global variable in one module and, in another module use an "extern" declaration to refer to it.

    module1.c
    1
    int globalVariable = 42;

    module2.c
    1
    2
    3
    4
    5
    6
    extern int globalVariable; // Declare the global variable from module1

    int main() {
           printf("The value of globalVariable is: %d\n", globalVariable);
           return 0;
    }

Types

  • Under what conditions can you qualify a type as "const"?
    The const keyword is used to indicate that the value of the object with that type cannot be modified.

  • What is the difference between the following types?

    1
    2
    3
    const char * cp1;
    char * const cp2;
    const char * const cp3;

    const char * cp1;: This declares cp1 as a pointer to a constant char. It means that the data cp1 points to cannot be modified through cp1, but cp1 itself can be changed to point to a different memory location.

    char * const cp2;: This declares cp2 as a constant pointer to a char. It means that cp2 always points to the same memory location, and this memory location cannot be changed. However, the data at this memory location can be modified through cp2.

    const char * const cp3;: This declares cp3 as a constant pointer to a constant char. It means that both cp3 and the data it points to are constant. cp3 cannot be changed to point to a different memory location, and the data it points to cannot be modified through cp3.

    In summary:

    • const to the left of * makes the data constant.
    • const to the right of * makes the pointer constant.
    • const on both sides makes both the pointer and the data constant.

  • Name all of the first-class types in "C".
    Scalar types (e.g., int, float, double, char, void, short, long, etc.)

  • Give an example of a derived type in "C".
    Pointer types (e.g., int *, char *, etc.).
    Pointer to function types (e.g., int (*)(int, int), a pointer to a function that takes two int arguments and returns an int)

    An example is declaring a struct type, e.g.:

    1
    2
    3
    4
    5
    struct person {
    	char name[20];
    	int age;
    	float height;
    };

  • Can you assign a float variable to an int variable?
    Yes, but the value will be truncated.

  • Can you assign an int variable to a float variable?
    Yes, but the type will be promoted.

  • Can you assign any first-class type variable to any other first-class type variable?
    Yes, you just have to typecast them to the matching data type.

  • Can you assign a first-class type variable to any kind of derived type variable?
    No, e.g. you cannot assign an int to a structure

C Preprocessor and Libraries

  • Review how to use the following preprocessor directives:
1
2
3
4
5
6
7
#define SOMETHING SOMETHING_ELSE
...
#ifdef SOMETHING
...
#else
...
#endif

#define is a preprocessor directive in C that unconditionally defines a macro.

#ifdef is a preprocessor directive in the C programming language that tests whether a macro has been defined or not. It allows conditional compilation of code based on whether a particular macro has been defined or not.

#else is run if the macro is not defined in a #ifdef

#endif Ends a #ifdef macro

1
#if (SOMETHING == 5)

#if is a preprocessor directive in the C programming language that allows conditional compilation of code based on the value of an expression.

  • Does the following program cause a compile-time error?

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    #define C 1
    #define A B
    #define B C
    int function() {
       	int x = 0;
    #if (A == 1)
       	return;
    #else
       	return 0;
    #endif
    }
    No, no compile time error. The macro A is defined as B and B is defined as C. So when the preprocessor replaces A in the #if directive, it replaces it with B and then replaces B with C. Therefore, the #if statement is effectively replaced by #if (C == 1).

    Since C is defined as 1, the condition in the #if statement evaluates to true, and the code in the first branch of the if statement is executed, which is a return statement without a value.

    In this specific case, the program still works because the function return type is int, and the return statement in the first branch of the if statement might just return some undetermined number.

    In general, however, it is good practice to always explicitly return a value from a function that has a return type, as it makes the code more clear and less error-prone.

  • What are the reasons for using libraries?
    To import useful code, promote modular programming, and provide cross-platform compatibility.

  • What are the differences between static and dynamic (shared) libraries?

    Aspects Static library Dynamic library
    Linking Linked at compile time Linked at run time
    Size Increase the size of the executable (the library code is included in the executable. Reduce the size of the executable (the library code is stored separately and referenced at run time)
    Memory Usage Increase memory usage (the entire library code is loaded into memory) Reduce memory usage (the code is shared among multiple processes, and only one copy of the library code is loaded into memory)
    Ease of Updates Require recompilation of the entire program Allow for easier updates (can replace the library file without recompiling the program)
    Portability More portable (does not require the presence of the library file at run time) Less portable (requires the library file to be present and correctly configured at run time)
    Runtime Dependencies No (directly included in the executable) Yes (must be present in the correct location for the program to run)

  • What are the trade-offs between the above two?
    The trade-offs between static and dynamic libraries involve executable size, memory usage, ease of updates, runtime dependencies, portability, and performance considerations.

  • How do you create a library?
    Compile c files into an object file and link them with

    1
    gcc (name).o –shared –o library.so