Find and fix a loop that reads a list node after it has been freed.
What to build
A corrected version of a program that frees a linked list wrongly.
Requirements
- The starter builds a list, prints the sum of its values, and then frees it. Its freeing loop has a bug.
- Fix the loop so that no node is read after it has been freed.
- The output must stay the same:
sum S, thenfreed N.
Input
The first line has n. The second line has the n numbers.
Output
Two lines: the sum, then the number of nodes freed.
Constraints
0 ≤ n ≤ 100.
Example
Input:
3
4 5 6
Output:
sum 15
freed 3
Why it works
After free(p), the node no longer belongs to the program, so p->next must not be read. Copying it out first keeps the way forward. Compiled C often hides this bug, and StepVioz stops on it.
Examples
Example 1 · Input
3 4 5 6
Expected output
sum 15 freed 3
Example 2 · Input
1 -2
Expected output
sum -2 freed 1
Hints
Hint 1
Look at the loop that frees the list. What does it read after calling free?
Hint 2
Save the pointer to the next node in a variable before you free the current one.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int value;
struct node *next;
} Node;
int main(void) {
int n;
scanf("%d", &n);
Node *head = NULL;
for (int i = 0; i < n; i++) {
Node *p = malloc(sizeof(Node));
scanf("%d", &p->value);
p->next = head;
head = p;
}
int sum = 0;
for (Node *p = head; p != NULL; p = p->next) sum += p->value;
printf("sum %d\n", sum);
int freed = 0;
while (head != NULL) {
Node *next = head->next; /* save the way forward before freeing */
free(head);
head = next;
freed++;
}
printf("freed %d\n", freed);
return 0;
}