Week 09 Tutorial Questions
-
How are you progressing with the assignment?
-
Do you have any questions? Have you learned anything that would be useful to share with the rest of the tutorial?
-
What does
malloc
do?What are its inputs and output and what do they mean?
Describe a function that will allocate memory for a struct and assign a pointer to the result.
-
What does
free
do?What is the input to
free
and how does it help it do what it needs to do? -
What is a use after free error?
Give an example.
Discuss why these are extremely dangerous, one of the worst causes of bugs in C programs and a major source of security vulnerabilities.
-
What is a memory leak?
What does
dcc --leak-check
do?
Assignment 2 Checkin
Memory Allocation Revision
More Linked Lists
When tackling a linked list exercise, it's a good idea to consider the following questions:
-
What cases do I need to consider? Some of the common cases to
consider are:
- Number of nodes (ie empty list, list with one node, list with many nodes)
- Location in the list (ie, at the start/middle/end of the list)
-
Do I need to iterate through a linked list?
- What loop condition(s) should I use?
- How many iterators do I need?
- Do I need to
malloc
/free
memory?
The rest of the tutorial questions are linked list exercises.
Your tutor will choose to cover some of these exercises, but likely will not have time to cover all of the exercises. Any exercises that are not covered can be used as revision questions for linked lists.
For these questions, struct node
has this definition:
struct node {
int data;
struct node *next;
};
Implement a function list_append
which appends its second
argument to its first. Treat both inputs as if they are lists and may have
more than one node.
list_append
should have this prototype:
struct node *list_append(struct node *list1, struct node *list2);
list_append
should not create (malloc
) any new
list elements.
list_append
should just change the appropriate next field
in the first list.
Implement a function delete_last
which deletes the last node
from a given list.
delete_last
should have this prototype:
struct node *delete_last(struct node *head);
delete_last
should call free
to free the memory
of the node it deletes.
delete_last
should return a pointer to the head of the list.
list_empty.c and list.h contain the starter code for the final three questions, and test_list.c can be used for testing. Alternatively download all three files as tut_list_files.zip.
Implement a function copy
which returns a copy of a linked list.
copy
should have this prototype.
struct node *copy(struct node *head);
copy
should call malloc
to create a new linked
list of the same length and which contains the same data.
Implement a function identical
that returns 1 if the contents
of the two linked lists are identical (same length, same values in data fields)
and otherwise returns 0.
identical
should have this prototype:
int identical(struct node *head1, struct node *head2);
identical
should not create (malloc
) any new
list elements.
Implement a function set_intersection
which given two linked
lists in strictly increasing order returns a new linked list containing a copy
of the elements found in both lists.
set_intersection
should have this prototype:
struct node *set_intersection(struct node *set1, struct node *set2);
The new linked list should also be in strictly increasing order. It should include only elements found in both lists.
set_intersection
should call malloc
to create
the nodes of the new linked list.
Revision questions
The remaining tutorial questions are primarily intended for revision - either this week or later in session.
Your tutor may still choose to cover some of the questions time permitting.
The remaining tutorial questions are primarily intended for revision - either this week or later in session.
Your tutor may still choose to cover some of the questions time permitting.
The function merge_sorted
is used to merge two ordered lists.
It will combine two sorted list into a new sorted list (non-decreasing).
It has this prototype:
struct node *merge_sorted(struct node *list1, struct node *list2);
It should not create (malloc) any list elements. It should change the appropriate next fields to combined the lists.
Implement this function both iteratively (using a while/for loop) and recursively.
Write a function strings_to_list
which takes an array
of pointers to strings and converts it to a linked list.
It should have this prototype:
struct node *strings_to_list(int len, char *strings[]);
Assume the strings contain only digit characters,
It might be called like this:
char *powers[] = {"2", "4", "8", 16"}; struct node *head = strings_to_list(4, powers);
How would you use strings_to_list
to convert a program's
command line arguments to a linked list?
How would you use strings_to_list
to convert a program's
command line arguments to two linked lists?
Assume, a command line argument of "-" separates the arguments to be converted.
The function insert_ordered
is used to construct ordered lists.
It will insert the supplied value at the appropriate point in the list remains
sorted (non-decreasing).
It has this prototype:
struct node *insert_ordered(int item, struct node *list);
It should create (malloc
) just 1 list element and
change the appropriate next field in the list to insert it.
Implement this function.