Review P: C Pointers
printable version
P1: [1] [2] [3] [4] [5] [6] // P2: [1] [2] [3] [4] [5] [6] [7] // P3: [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]
Problem P1.1
What does each of the following C programs display?
| a. | #include <stdio.h> | b. | #include <stdio.h> |
| a. | 9 7 7 7 | b. | 3 8 3 3 |
Problem P1.2
What does each of the following C programs display?
| a. | #include <stdio.h> | b. | #include <stdio.h> |
| a. | 5 4 4 5 | b. | 7 6 6 6 7 |
Problem P1.3
What does each of the following C programs display?
| a. | #include <stdio.h> | b. | #include <stdio.h> |
| a. | 5 6 6 5 6 | b. | 4 2 5 5 5 |
Problem P1.4
What does each of the following C programs display?
| a. | #include <stdio.h> | b. | #include <stdio.h> |
| a. | 5 7 7 7 | b. | 5 4 0 |
Problem 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;
}
2
-4
Problem 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
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.
Problem P2.1
What does each of the following C programs display?
| a. | #include <stdio.h> | b. | #include <stdio.h> |
| a. | 4 |
| b. | 0021 |
Problem 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;
}
Problem 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) {
int strchr(char *search, char find) {
int i;
for (i = 0; search[i] != '\0'; i++) {
if (search[i] == find) return i;
}
return -1;
}
Problem 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) {
void printr(char *letters) {
int i;
for (i = strlen(letters) - 1; i >= 0; i--) {
printf("%c", letters[i]);
}
}
Problem 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) {
void rtrim(char *line) {
int i;
i = strlen(line);
while (i > 0 && line[i - 1] == ' ') {
line[i - 1] = '\0';
i--;
}
}
Problem 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) {
void add_a(char *name) {
int i;
i = 0;
while (name[i] != '\0') {
i++;
}
name[i] = 'a';
name[i + 1] = '\0';
}
Problem 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) {
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;
}
Problem 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.
a. (pts->len)-- ?>
b. pts->data[2]->y = 19
Problem 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.
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.
Problem P3.3
Explain what a memory leak is.
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.
Problem 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) {
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);
}
Problem 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)
a. When the parameter
sdoes not start with a capital letter, we enter theelseclause and allocate in line 9 an array holding space for each of the characters ofs— but we do not include enough room for the terminating NUL character. Then, in line 10, whensis copied into this array,strcpywill attempt to place a NUL character after the final character it copies intot; 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
sstarts with a capital letter, we enter theifclause, which does not altertfrom its value, and sotremains uninitialized. Then we continue to line 14, which asksfreeto deallocate based on the value of this uninitialized variablet. The message indicates thatfreeuses the value of this uninitialized variable.The solution is to move line 14 so that it only occurs after
thas been given a value — i.e., in theelseclause. Thus, we should move line 14 to be just after line 12.
Problem 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 { |
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;
}
}
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;
}
Problem 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.)
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
curtoNULL, and thewhiletest will attempt to accesscur->next.If the list ends with a 0, then the program can lead to a segmentation fault: In the
iffor the final node,cur->nextchanges toNULL, then then the statement at thewhileloop's end changescurtoNULL, and then thewhileloop's test will attempt to accesscur->next.
Problem 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;
}
}
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.
Problem 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) {
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;
}
Problem 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) {
int list_get_last(struct node *head) {
struct node *n;
n = head;
while (n->next != NULL) {
n = n->next;
}
return n->value;
}
Problem 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) {
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;
}
}
}
Problem 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) {
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;
}