Week 09 Tutorial Questions

    Assignment 2 Checkin

  1. How are you progressing with the assignment?

  2. Do you have any questions? Have you learned anything that would be useful to share with the rest of the tutorial?

    3. Memory Allocation Revision

  3. 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.

  4. What does free do?

    What is the input to free and how does it help it do what it needs to do?

  5. 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.

  6. What is a memory leak?

    What does dcc --leak-check do?

    7. More Linked Lists

    When tackling a linked list exercise, it's a good idea to consider the following questions:

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.