Do you have any questions? Have you learned anything that would
be useful to share with the rest of the tutorial?
Memory Allocation Revision
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?
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:
structnode{intdata;structnode*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.
Implement a function copy which returns a copy of a linked list.
copy should have this prototype.
structnode*copy(structnode*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:
intidentical(structnode*head1,structnode*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.
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:
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: