Review P: C Pointers: Questions

P1.1.

What does each of the following C programs display?

a.#include <stdio.h>

int main() {
    int i;  int j;
    int *p; int *q;

    p = &i;
    q = &j;
    i =  9;
    j =  8;
    p =  q;
    *q = 7;
    printf("%d %d\n", i, j);
    printf("%d %d\n", *p, *q);
    return 0;
} 		b.#include <stdio.h>

int main() {
    int i;  int j;
    int *p; int *q;

    p = &i;
    q = &j;
    i =  3;
    j =  5;
    *q = 8;
    q =  p;
    printf("%d %d\n", i, j);
    printf("%d %d\n", *p, *q);
    return 0;
}
P1.2.

What does each of the following C programs display?

a.#include <stdio.h>

int main() {
    int i;  int j;
    int *p; int *q; int *r;

    p = &i;
    q = &j;
    i = 3;
    j = 4;
    r = p;
    p = q;
    *r = 5;
    q = r;
    printf("%d %d\n", i, j);
    printf("%d %d\n", *p, *q);
    return 0;
} 		b.#include <stdio.h>

int main() {
    int i;  int j;
    int *p; int *q; int *r;

    p = &i;
    q = &j;
    i = 3;
    j = 4;
    r = p;
    p = q;
    *p = 5;
    *q = 6;
    *r = 7;
    printf("%d %d\n", i, j);
    printf("%d %d\n", *p, *q)
    printf("%d\n", *r);
}
P1.3.

What does each of the following C programs display?

a.#include <stdio.h>
int main() {
    int i;  int j;
    int *p; int *q;
    int **r;
    i =  9;
    j =  8;
    p = &i;
    q = p;
    r = &p;
    *p = 7;
    p = &j;
    **r = 6;
    *q = 5;
    printf("%d %d\n", i, j);
    printf("%d %d %d\n", *p, *q, **r);
    return 0;
} 		b.#include <stdio.h>
int main() {
    int i;   int j;  int k;
    int **p; int *q;
    i =  1;
    j =  2;
    k =  3;
    q = &i;
    p = &q;
    *q = 4;
    q = &k;
    **p = 5;
    printf("%d %d %d\n", i, j, k);
    printf("%d %d\n", **p, *q);
    return 0;
}
P1.4.

What does each of the following C programs display?

a.#include <stdio.h>

int main() {
    int i;   int j;
    int **p; int *q;

    i =  2;
    j =  3;
    q = &i;
    p = &q;
    *q = 5;
    q = &j;
    **p = 7;
    printf("%d %d\n", i, j);
    printf("%d %d\n", **p, *q);
    return 0;
} 		b.#include <stdio.h>

void mystery(int *ap, int *bp) {
    *ap = *ap + *bp;
    *bp = *ap - *bp;
    *ap = *ap - *bp;
}

int main() {
    int i;
    int j;

    i = 4;
    j = 5;
    mystery(&i, &j);
    printf("%d %d\n", i, j);
    i = 6;
    mystery(&i, &i);   /* Note: both args */
    printf("%d\n", i); /* are now &i      */
    return 0;
}
P1.5.

Suppose that nums is an int* pointing to the first integer of an array containing [3, 0, −1, 2, −2, −4]. Thus, *nums is 3. What is displayed by the following sequence of statements?

while (*nums != 0) {
    printf("%d\n", *nums);
    nums = nums + *nums;
}
P1.6.

Consider the below program.

#include <stdlib.h>

int* create_array(int value) {
    int ret[5]; int i;
    for (i = 0; i < 5; i++) ret[i] = value;
    return ret;
}

int main() {
    int *nums;  int i;
    nums = create_array(5);
    for (i = 0; i < 5; i++) printf(" %d", nums[i]);
    return 0;
}

When executed, the program displays the following. Explain why.

 5 5 5 4875171 134513144
P2.1.

What does each of the following C programs display?

a.#include <stdio.h>

int mystery(char *s) {
    int count = 0;
    for (; *s != '\0'; s++) {
        if (*s == 'r') count++;
    }
    return count;
}

int main() {
    printf("%d\n", mystery("redder rudder"));
    return 0;
} 		b.#include <stdio.h>

void mystery(char *dst, char *src) {
    char *p;

    for (p = src; *p != '\0'; p++) {
        *dst = '0'; dst++;
    }
    *dst = '\0'; dst--;
    for (p = src; *p != '\0'; p++) {
        if (*p != '0') {
            *dst = *p; dst--;
        }
    }
}

int main() {
    char out[100];
    mystery(out, "1002");
    printf("%s\n", out);
    return 0;
}
P2.2.

What will the following C program display?

#include <stdlib.h>

void mystery(char *s, char *t) {
    while (*s = *t) { /* note: using = rather than == */
        s++;
        t++;
    }
}

int main() {
    char s[5] = "back";
    char t[5] = "tick";
    mystery(s, t);
    printf("%s %s\n", s, t);
    return 0;
}
P2.3.

Complete the following function so that it returns the index of the first occurrence of find within search. If it does not occur, the function should return −1.

int strchr(char *search, char find) {
P2.4.

Complete the following function so that it displays its parameter string in reverse. For example, printr("straw") should display warts onto the screen. (Recall that you can use printf("%c", s[0]) to display the first character of a string s. You can feel free to use standard C functions like strcpy.)

void printr(char *letters) {
P2.5.

Complete the below C function so that it removes the rightmost spaces in the parameter string by placing ASCII 0 in place of each such space. For example, if the parameter string is “  a b  c   ”, then the function should replace the final three spaces (after the c) with ASCII 0.

void rtrim(char *line) {
P2.6.

Complete the following C function so that it appends the letter a to the end of its parameter string. For example, given a pointer to the string Michael, the function should change the string to Michaela. You can assume there is room in the memory alocation for the extra letter. You may not call any functions from the standard C library.

void add_a(char *name) {
P2.7.

Complete the following C function which, given an array of strings as a parameter, should return the number of strings in the array containing exactly one character. Your implementation should not use strlen.

int count_length_one_words(char **words, int num_words) {
P3.1.

Below are two struct declarations.

struct point {
    int x;
    int y;
};

struct points {
    int len;
    struct point **data;
};

Given that pts is a variable declared of type struct points* whose current memory is configured as below, write a single C statement that accomplishes each of the following.

a. Decrement the len value to one less than before.

b. Change the 15 to 19.

P3.2.

As we saw, a C program's memory is divided into two region: the stack and the heap. Explain how its treatment of these two regions of memory differs.

P3.3.

Explain what a memory leak is.

P3.4.

Consider the following structure definition.

struct student {
    char *name;
    int testScore;
};

The below function's parameter is a pointer to the first element of an array of 12 pointers to student structures. Complete the function so that it displays the name of the student who earned the highest test score. (In case of ties, it doesn't matter which of the highest-scoring students is displayed. The program should display one or more names from the tying group.)

void print_highest_of_12(struct student **students) {
P3.5.

Consider the following function, which uses the standard C functions isupper for testing whether the parameter character is a capital letter and toupper that returns an upper-case equivalent of the parameter character. (For example, isupper('A') returns 1 while isupper('b') returns 0; and toupper('c') returns the capital letter C.)

 1  void print_capitalized(char *s) {
 2      char *t;
 3
 4      if (isupper(s[0])) {
 5          /* s is already capitalized, so just print s. */
 6          printf("%s", s);
 7      } else {
 8          /* create a copy of s with first letter capitalized. */
 9          t = (char*) malloc(strlen(s) * sizeof(char));
10          strcpy(t, s);
11          t[0] = toupper(s[0]);
12          printf("%s", t);
13      }
14      free(t);
15  }

This function has two bugs, identified by valgrind as below. For each bug, explain the circumstances that lead to the problem as the computer executes the code on the line identified by valgrind, and explain how to repair the code to avoid the problem (while retaining the basic structure of the function as much as possible).

  • a. Invalid write of size 1 (line 10)

  • b. Conditional jump or move depends on uninitialised value(s) (line 14)

P3.6.

In this problem and the following ones, we assume the following two struct definitions we saw for representing a linked list.

struct list {
    struct node *head;
}; 		   struct node {
    int data;
    struct node *next;
};

The following C function is meant to delete the first node containing 0 from a linked list of integers (leaving the list unchanged if it contains no zeroes). While this function compiles correctly and passes most tests, it still contains two bugs. Identify each and explain how to repair the function.

void remove_first_zero(struct list *lst) {
    struct node *prev;
    struct node *cur;

    prev = NULL;
    cur = lst->head;
    while (cur != NULL) {
        if (cur->data == 0) {
            free(cur);
            prev->next = cur->next;
            return;
        }
        prev = cur;
        cur = cur->next;
    }
}
P3.7.

The below function is supposed to delete all nodes from the parameter linked list whose data is 0. It compiles and executes correctly, and it often works, but there are several situations where it fails to do its job correctly. Describe two such situations, and explain what happens in each situation.

void remove_all_zeroes(struct list *lst) {
    struct node *cur;
    struct node *after;

    cur = lst->head;
    while (cur->next != NULL) {
        after = cur->next;
        if (after->data == 0) {
            cur->next = after->next;
            free(after);
        }
        cur = cur->next;
    }
}

(Do not attempt to correct the function — simply describe two distinct situations in which function would not correctly eliminate all 0 nodes from the list.)

P3.8.

The below C function is meant to insert a new node with the value to_add after the first node in the list whose value is query. For instance, given the list 4, 5, 6 where query is 5 and to_add is 7, the function should modify the list to instead be 4, 5, 7, 6.

While this function compiles correctly and passes most tests, it still contains some bugs. Identify two bugs, including the circumstances under which each occurs and how the function can be repaired to address the bug.

void insert_after(struct node *head, int query, int to_add) {
    struct node *cur;
    struct node *n;

    cur = head;
    while (cur->next != NULL) {
        if (cur->data == query) {
            n = (struct node*) malloc(sizeof(struct node));
            n->data = to_add;
            n->next = cur->next;
            cur->next = n;
        }
        cur = cur->next;
    }
}
P3.9.

Suppose we have declared a C struct as below for representing a linked list's node.

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

Complete the following function so that it returns a sum of all the numbers in the linked list. Your solution should not use recursion.

int list_sum(struct node *head) {
P3.10.

Suppose we have declared a C struct as below for representing a linked list's node.

struct node {
    int value;
    struct node *next;
};

Complete the following function so that it returns the final number in the linked list.

int list_get_last(struct node *head) {
P3.11.

Suppose we have declared a C struct as below for representing a linked list's node.

struct node {
    int value;
    struct node *next;
};

Complete the following function so that it displays every other number in the linked list. If the list contains 1, 2, 3, 4, 5, 6, 7, the function should display 1, 3, 5, 7 (on separate lines without commas).

void list_print_alternates(struct node *head) {
P3.12.

Suppose we have declared a C struct as below for representing a linked list's node.

struct node {
    int value;
    struct node *next;
};

Complete the following function so that finds the first node whose value is find and inserts a new node following it containing insert. Thus if our list contains three nodes whose values are 2, 3, 5, and we are told to find 3 and insert 4 after it, then after calling the function the list would containing 2, 3, 4, 5.

You may assume that find is actually present in the list. If find appears multiple times, then you would want to insert after just the first occurrence of find.

void list_insert_after(struct node *head, int find, int insert) {

Review P: C Pointers: Solutions

P1.1.
a.
9 7
7 7
b.
3 8
3 3
P1.2.
a.
5 4
4 5
b.
7 6
6 6
7
P1.3.
a.
5 6
6 5 6
b.
4 2 5
5 5
P1.4.
a.
5 7
7 7
b.
5 4
0
P1.5.
3
2
-4
P1.6.

The createArray function returns a pointer to a locally declared variable; thus, nums points into memory that has been deallocated. It happens that printf uses some of that memory, altering the contents of that memory.

P2.1.
a.4
b.0021
P2.2.
tick tick
P2.3.
int strchr(char *search, char find) {
    int i;

    for (i = 0; search[i] != '\0'; i++) {
        if (search[i] == find) return i;
    }
    return -1;
}
P2.4.
void printr(char *letters) {
    int i;

    for (i = strlen(letters) - 1; i >= 0; i--) {
        printf("%c", letters[i]);
    }
}
P2.5.
void rtrim(char *line) {
    int i;

    i = strlen(line);
    while (i > 0 && line[i - 1] == ' ') {
        line[i - 1] = '\0';
        i--;
    }
}
P2.6.
void add_a(char *name) {
    int i;

    i = 0;
    while (name[i] != '\0') {
        i++;
    }
    name[i] = 'a';
    name[i + 1] = '\0';
}
P2.7.
int count_length_one_words(char **words, int num_words) {
    int count;
    int i;

    count = 0;
    for (i = 0; i < num_words; i++) {
        if (words[i][0] != '\0' && word[i][1] == '\0') {
            count++;
        }
    }
    return count;
}
P3.1.

a. (pts->len)-- ?>

b. pts->data[2]->y = 19

P3.2.

Space for functions' local variables are allocated from the stack, and the space for each local variable is deallocated when the function owning the variable returns.

We allocate space on the heap only through the malloc function; space allocated in this way remains allocated until the program later calls free.

P3.3.

A memory leak is a block of memory allocated by a program that then loses any references into the block. As a result, the memory is unused but still allocated.

P3.4.
void print_highest_of_12(struct student **students) {
    int max;
    int i;

    max = 0;
    for (i = 1; i < 12; i++) {
        if (students[i]->testScore > students[max]->testScore) {
            max = i;
        }
    }
    printf("%s\n", students[max]->name);
}
P3.5.

  • a. When the parameter s does not start with a capital letter, we enter the else clause and allocate in line 9 an array holding space for each of the characters of s — but we do not include enough room for the terminating NUL character. Then, in line 10, when s is copied into this array, strcpy will attempt to place a NUL character after the final character it copies into t; but this is beyond the length of the allocated array.

    The solution is to change line 9 to include space for this extra character:

    t = (char*) malloc((strlen(s) + 1) * sizeof(char));

  • b. When the parameter s starts with a capital letter, we enter the if clause, which does not alter t from its value, and so t remains uninitialized. Then we continue to line 14, which asks free to deallocate based on the value of this uninitialized variable t. The message indicates that free uses the value of this uninitialized variable.

    The solution is to move line 14 so that it only occurs after t has been given a value — i.e., in the else clause. Thus, we should move line 14 to be just after line 12.

P3.6.

The first problem is that the assignment to prev->next accesses cur->next, which is part of memory that has just been deallocated. We can repair this by swapping this assignment with the previous line, “free(cur)”.

The second problem is that the function simply doesn't work if the first value in the list is 0. In this case, we want to change lst->head; and in fact prev is NULL, so we certainly don't want to assign to prev->next. The solution is to replace the assignment to prev->next with the following if statement.

if (prev == NULL) {
    lst->head = cur->next;
} else {
    prev->next = cur->next;
}
P3.7.

  • If the list starts with a 0, then the program will simply not remove it, since it begins looking for 0's starting from the node after the first node.

  • If the list has more than two consecutive 0 nodes, then it will keep every other one of these 0 nodes.

  • If the list is empty, the program will lead to a segmentation fault: We set cur to NULL, and the while test will attempt to access cur->next.

  • If the list ends with a 0, then the program can lead to a segmentation fault: In the if for the final node, cur->next changes to NULL, then then the statement at the while loop's end changes cur to NULL, and then the while loop's test will attempt to access cur->next.

P3.8.

One problem is that if query appears multiple times in the list, this code will end up inserting to_add after each occurrence rather than only the first one. We can repair this by inserting break or return at the end of the if statement's body.

Another problem is that if query occurs in the last node of the list, this function will not identify it; it will leave the list unchanged, since the while loop will terminate once cur is pointing to the last node (where cur->next is NULL). This can be addressed by changing the while condition to “while (cur != NULL)”.

Another problem, closely related to the previous one, is that the function will lead to an invalid memory access if head is NULL, as it would be when the list is empty. In this case, the access to cur->next to evaluate the while condition will be dereferencing the NULL pointer. Fixing the code as indicated in the previous paragraph, though, will also fix this problem.

P3.9.
int list_sum(struct node *head) {
    int ret;
    node *cur;

    ret = 0;
    cur = head;
    while (cur != NULL) {
        ret += cur->data;
        cur = cur->next;
    }
    return ret;
}
P3.10.
int list_get_last(struct node *head) {
    struct node *n;
    n = head;
    while (n->next != NULL) {
        n = n->next;
    }
    return n->value;
}
P3.11.
void list_print_alternates(struct node *head) {
    struct node *cur;

    cur = head;
    while (cur != NULL) {
        printf("%d\n", cur->value);
        cur = cur->next;
        if (cur != NULL) {
            cur = cur->next;
        }
    }
}
P3.12.
void list_insert_after(struct node *head, int find, int insert) {
    struct node *cur;
    struct node *after;
    while (cur->value != find) {
        cur = cur->next;
    }
    after = (struct node*) malloc(sizeof(struct node));
    after->value = insert;
    after->next = cur->next;
    cur->next = after;
}