Week 09 Laboratory Exercises

Objectives

  • More complex linked lists
  • Practice working with lists of lists

Activities To Be Completed

The following is a list of all the activities available to complete this week...

Worth one mark in total:

  • list_increasing
  • books
  • list_delete_first

Worth half a mark in total:

  • list_delete_contains
  • library

Worth half a mark in total:

  • lists_diagonal
  • musical_chairs

For your interest, but not for marks:

  • student_becomes_teacher_week9

Preparation

Before the lab you should re-read the relevant lecture slides and their accompanying examples.

Exercise
(●◌◌)
:

Check whether a Linked List is in Increasing Order

Download list_increasing.c here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/21T3/activities/list_increasing/list_increasing.c .

Your task is to add code to this function in list_increasing.c:

int increasing(struct node *head) {

    // PUT YOUR CODE HERE (change the next line!)
    return 42;

}
increasing is given one argument, head, which is the pointer to the first node in a linked list.

Add code to increasing so that its returns 1 if the list is in increasing order - the value of each list element is larger than the element before.

For example if the linked list contains these 8 elements:

1, 7, 8, 9, 13, 19, 21, 42

increasing should return 1 because is is increasing order

Testing

list_increasing.c also contains a main function which allows you to test your increasing function.

This main function:

  • converts the command-line arguments to a linked list
  • assigns a pointer to the first node in the linked list to head
  • calls list_increasing(head)
  • prints the result.

Do not change this main function. If you want to change it, you have misread the question.

Your list_increasing function will be called directly in marking. The main function is only to let you test your list_increasing function

Here is how you use main function allows you to test list_increasing:

dcc list_increasing.c -o list_increasing
./list_increasing 1 2 4 8 16 32 64 128 256
1
./list_increasing 2 4 6 5 8 9
0
./list_increasing 13 15 17 17 18 19
0
./list_increasing 2 4
1
./list_increasing 42
1
./list_increasing
1

Assumptions/Restrictions/Clarifications.

increasing should return a single integer.

increasing should not change the linked list it is given. Your function should not change the next or data fields of list nodes.

increasing should not use arrays.

increasing should not call malloc.

increasing should not call scanf (or getchar or fgets).

You can assume the linked list only contains positive integers.

increasing should not print anything. It should not call printf.

Do not change the supplied main function. It will not be tested or marked.

You can run an automated code style checker using the following command:
1511 style list_increasing.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest list_increasing

When you are finished working on this exercise, you and your lab partner must both submit your work by running give:

give cs1511 lab09_list_increasing list_increasing.c

Note, even though this is a pair exercise, you both must run give from your own account before Monday 15 November 20:00 to obtain the marks for this lab exercise.

Exercise
(●◌◌)
:

Maintain a List of Books

Complete the C program books.c which implements the header file books.h. You can use main.c to test your program.

You must not change books.h and main.c. You will only be submitting books.c.

Download books.h here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/21T3/activities/books/books.h .

Download books.c here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/21T3/activities/books/books.c .

Download main.c here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/21T3/activities/books/main.c .

To complete this activity, you must read the descriptions of each function in books.h and then complete these functions in books.c. All assumptions and clarifications will be found in the H file.

When complete, your program will behave like this.

dcc -o books books.c main.c
./books
Enter command: i Lightning-Thief Rick-Riordan 377
Enter command: i Sea-of-Monsters Rick-Riordan 279
Enter command: i Titans-Curse Rick-Riordan 312
Enter command: i Battle-of-the-Labyrinth Rick-Riordan 361
Enter command: i Last-Olympian Rick-Riordan 461
Enter command: p
Lightning-Thief by Rick-Riordan (377 pages)
Sea-of-Monsters by Rick-Riordan (279 pages)
Titans-Curse by Rick-Riordan (312 pages)
Battle-of-the-Labyrinth by Rick-Riordan (361 pages)
Last-Olympian by Rick-Riordan (461 pages)
Enter command: q
./books
Enter command: p
Enter command: i Jane-Eyre Charlotte-Bronte 536
Enter command: p
Jane-Eyre by Charlotte-Bronte (536 pages)
Enter command: i Emma Jane-Austen 544
Enter command: p
Jane-Eyre by Charlotte-Bronte (536 pages)
Emma by Jane-Austen (544 pages)
Enter command: q
You can run an automated code style checker using the following command:
1511 style books.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest books

When you are finished working on this exercise, you and your lab partner must both submit your work by running give:

give cs1511 lab09_books books.c

Note, even though this is a pair exercise, you both must run give from your own account before Monday 15 November 20:00 to obtain the marks for this lab exercise.

Exercise
(●◌◌)
:

Delete First Element from a Linked List

Download list_delete_first.c here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/21T3/activities/list_delete_first/list_delete_first.c .

Your task is to add code to this function in list_delete_first.c:

//
// Delete the first node in list.
// The deleted node is freed.
// The head of the list is returned.
//
struct node *delete_first(struct node *head) {

    // PUT YOUR CODE HERE (change the next line!)
    return NULL;
}
Note list_delete_first.c uses the following familiar data type:
struct node {
    struct node *next;
    int          data;
};
delete_first is given one argument, head, which is the pointer to the first node in the linked list.

Add code to delete_first so that it deletes the first node from list.

delete_first should return a pointer to the new first node in the list.

If the list is now empty delete_first should return NULL.

delete_first should call free to free the memory of the node it deletes.

For example if the linked list contains these 8 elements:

16, 7, 8, 12, 13, 19, 21, 12

delete_first should return a pointer to a list with these elements:

7, 8, 12, 13, 19, 21, 12

Hint: this is a simple task requiring only a few lines of code.

Testing

list_delete_first.c also contains a main function which allows you to test your delete_first function. It converts command-line arguments to a linked list, calls delete_first, and then prints the result.

Do not change this main function. If you want to change it, you have misread the question.

Your delete_first function will be called directly in marking. The main function is only to let you test your delete_first function

Here is how you the main function allows you to test delete_first:

cp -n /web/cs1511/21T3/activities/list_delete_first/list_delete_first.c .
dcc list_delete_first.c -o list_delete_first
./list_delete_first 16 7 8 12 13 19 21 12
[7, 8, 12, 13, 19, 21, 12]
./list_delete_first 2 4 6 2 4 6
[4, 6, 2, 4, 6]
./list_delete_first 42
[]
./list_delete_first
[]

Assumptions/Restrictions/Clarifications.

delete_first should call free to free the memory for the node it deletes

delete_first should not change the data fields of list nodes.

delete_first should not use arrays.

delete_first should not call malloc.

delete_first should not call scanf (or getchar or fgets).

delete_first should not print anything. It should not call printf.

Do not change the supplied main function. It will not be tested or marked.

You can run an automated code style checker using the following command:
1511 style list_delete_first.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest list_delete_first

When you are finished working on this exercise, you and your lab partner must both submit your work by running give:

give cs1511 lab09_list_delete_first list_delete_first.c

Note, even though this is a pair exercise, you both must run give from your own account before Monday 15 November 20:00 to obtain the marks for this lab exercise.

Exercise
(●●◌)
:

Delete First Element Containing A Value from a Linked List

Download list_delete_contains.c here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/21T3/activities/list_delete_contains/list_delete_contains.c .

Your task is to add code to this function in list_delete_contains.c:

//
// Delete the first node in the list containing the value `value`.
// The deleted node is freed.
// If no node contains `value`, the list is not changed.
// The head of the list is returned.
//
struct node *delete_contains(int value, struct node *head) {

    // PUT YOUR CODE HERE (change the next line!)
    return NULL;

}
Note list_delete_contains.c uses the following familiar data type:
struct node {
    struct node *next;
    int          data;
};
delete_contains is given two argument, value and head. value is an int. head is the pointer to the first node in a linked list.

Add code to delete_contains so that it deletes the first node in the linked list that whose data field equals value.

If value does not occur in the linked list, the list should not be changed.

If value occurs more than once in the linked list, only the first occurrence should be deleted.

delete_contains should return a pointer to the new list.

If the list is now empty delete_contains should return NULL.

delete_contains should call free to free the memory of the node it deletes.

For example if value is 12 and the linked list contains these 8 elements:

16, 7, 8, 12, 13, 19, 21, 12

delete_contains should return a pointer to a list with these elements:

16, 7, 8, 13, 19, 21, 12

Testing

list_delete_contains.c also contains a main function which allows you to test your delete_contains function.

This main function:

  • converts the command-line arguments to a linked list
  • assigns a pointer to the first node in the linked list to head
  • reads a single integer from standard input and assigns it to value
  • calls delete_contains(value, head)
  • prints the result.

Do not change this main function. If you want to change it, you have misread the question.

Your delete_contains function will be called directly in marking. The main function is only to let you test your delete_contains function

cp -n /web/cs1511/21T3/activities/list_delete_contains/list_delete_contains.c .
dcc list_delete_contains.c -o list_delete_contains
./list_delete_contains 16 7 8 12 13 19 21 12
12
[16, 7, 8, 13, 19, 21, 12]
./list_delete_contains 16 7 8 12 13 19 21 12
42
[16, 7, 8, 12, 13, 19, 21, 12]
./list_delete_contains 4 6 2 4 6
2
[4, 6, 4, 6]
./list_delete_contains 42
42
[]
./list_delete_contains
42
[]

Assumptions/Restrictions/Clarifications.

delete_contains should call free to free the memory for the node it deletes

delete_first should not change the data fields of list nodes.

delete_contains should not use arrays.

delete_contains should not call malloc.

delete_contains should not call scanf (or getchar or fgets).

delete_contains should not print anything. It should not call printf.

Do not change the supplied main function. It will not be tested or marked.

You can run an automated code style checker using the following command:
1511 style list_delete_contains.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest list_delete_contains

When you are finished working on this exercise, you and your lab partner must both submit your work by running give:

give cs1511 lab09_list_delete_contains list_delete_contains.c

Note, even though this is a pair exercise, you both must run give from your own account before Monday 15 November 20:00 to obtain the marks for this lab exercise.

Exercise
(●●◌)
:

Maintain a 2D linked list in a Library

Implement the functions, detailed in library.h, in library.c. You can use main.c to test your program.

You can only change library.c and books.c. You will be submitting both of these. You cannot change library.h, books.h or main.c.

For this exercise you will be implementing a 2D linked list much like that of assignment 2. The struct library will contain a linked list of genres which themselves contain a linked list of books. The definition of a book is the exact same as that in the previous Books exercise.

This exercise will require you to compile a multi-file project with 5 files in total.

Download books.h here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/21T3/activities/library/books.h .

Download books.c here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/21T3/activities/library/books.c .

Download library.h here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/21T3/activities/library/library.h .

Download library.c here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/21T3/activities/library/library.c .

Download main.c here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/21T3/activities/library/main.c .

The files above are structured with their #include's to form the links in this image below. Each red arrow represents a file #including another.

To complete this activity, you must read the descriptions of each function in library.h and then complete these functions in library.c. This is similar to how we expect you to complete assignment 2. All assumptions and clarifications will be found in the H file.

When complete, your program will behave like this.

dcc -o library library.c books.c main.c
./library

Welcome to the COMP1511 Library!

Commands:
- g <genre-name> ~ Add a Book Genre
- b <genre-name> <book-name> <author> <#pages> ~ Add a Book
- p <genre-name> ~ Print all Books in a Genre

--> g Fantasy
Added Fantasy to genres!
--> b Fantasy School-for-Good-and-Evil Soman-Chainani 544
Added School-for-Good-and-Evil to genre Fantasy!
--> p Fantasy
School-for-Good-and-Evil by Soman-Chainani (544 pages)
--> q
Exiting
./library

Welcome to the COMP1511 Library!

Commands:
- g <genre-name> ~ Add a Book Genre
- b <genre-name> <book-name> <author> <#pages> ~ Add a Book
- p <genre-name> ~ Print all Books in a Genre

--> g Fantasy
Added Fantasy to genres!
--> g Adventure
Added Adventure to genres!
--> g Tragedy
Added Tragedy to genres!
--> b Fantasy School-for-Good-and-Evil Soman-Chainani 544
Added School-for-Good-and-Evil to genre Fantasy!
--> b Fantasy World-Without-Princes Soman-Chainani 512
Added World-Without-Princes to genre Fantasy!
--> b Adventure Treasure-Island Robert-Louis-Stevenson 292
Added Treasure-Island to genre Adventure!
--> b Adventure Percy-Jackson-Lightning-Thief Rick-Riordan 377
Added Percy-Jackson-Lightning-Thief to genre Adventure!
--> b Fantasy Last-Ever-After Soman-Chainani 704
Added Last-Ever-After to genre Fantasy!
--> b Tragedy King-Lear William-Shakespeare 138
Added King-Lear to genre Tragedy!
--> p Fantasy
School-for-Good-and-Evil by Soman-Chainani (544 pages)
World-Without-Princes by Soman-Chainani (512 pages)
Last-Ever-After by Soman-Chainani (704 pages)
--> p Adventure
Treasure-Island by Robert-Louis-Stevenson (292 pages)
Percy-Jackson-Lightning-Thief by Rick-Riordan (377 pages)
--> p Tragedy
King-Lear by William-Shakespeare (138 pages)
--> q
Exiting
You can run an automated code style checker using the following command:
1511 style library.c books.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest library

When you are finished working on this exercise, you and your lab partner must both submit your work by running give:

give cs1511 lab09_library library.c books.c

Note, even though this is a pair exercise, you both must run give from your own account before Monday 15 November 20:00 to obtain the marks for this lab exercise.

Exercise
(●●●)
:

Determine whether a list of lists contains a diagonal line of identical values

Download lists_diagonal.c here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/21T3/activities/lists_diagonal/lists_diagonal.c .

Your task is to add code to this function in lists_diagonal.c:

// Treat the linked lists like they're a 2D array
// and return 1 if the first element is repeated
// diagonally through the lists
int has_diagonal(struct list_node *head) {
    return 0;
}
lists_diagonal is written using the following structs that cannot be changed:

struct node {
    int data;
    struct node *next;
};

struct list_node {
    struct node *my_list;
    struct list_node *next;
};

The node struct is a normal linked list node.

The list_node struct is used to make a linked list where each element contains a list of nodes.

has_diagonal should take a pointer to the head of a list_node list and return a 1 if it finds a diagonal or a 0 if it doesn't. A diagonal in this exercise means that the first number in the first list is the same as the second number in the second list and the third number in the third list and so on.

For example if the list of lists looks like this:

list_node 0 contains the list {5, 0, 0}
list_node 1 contains the list {0, 5, 0}
list_node 2 contains the list {0, 0, 5}

has_diagonal should return 1.

However, if the list of lists looks like this:

list_node 0 contains the list {5, 0, 0, 0}
list_node 1 contains the list {0, 4, 0, 0}
list_node 2 contains the list {0, 0, 5, 0}
list_node 3 contains the list {0, 0, 0, 5}

has_diagonal should return 0, because the 2nd element of the second list does not equal the value of the first element of the first list.

Assumptions/Restrictions/Clarifications.

struct node and struct list_node cannot be edited. They must be used as they are.

You may not use arrays in this solution. Arrays are not necessary to complete this task.

You can assume that you'll never receive an empty list of list_nodes.

You can assume that all lists of nodes are also not empty.

You can assume that there will always be the same number of nodes in each list and that will be the same number of list_nodes. That is to say, the 2D grid formed by the lists will always be square. Your submitted file may contain a main function. It will not be tested or marked.

You can run an automated code style checker using the following command:
1511 style lists_diagonal.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest lists_diagonal

When you are finished working on this exercise, you and your lab partner must both submit your work by running give:

give cs1511 lab09_lists_diagonal lists_diagonal.c

Note, even though this is a pair exercise, you both must run give from your own account before Monday 15 November 20:00 to obtain the marks for this lab exercise.

Exercise
(●●●)
:

Play the Game of Chairs. Win or die.

Download musical_chairs.c here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/21T3/activities/musical_chairs/musical_chairs.c .

Your task is to add code to this function in musical_chairs.c:

// Make music for a certain number of turns.
// Each turn of music makes the players move
// one chair along the list.
// After they've moved that many times, the
// first chair in the list is removed, along
// with the person sitting in it.
struct chair *make_music(int turns, struct chair *chairs) {
    // IMPLEMENT THIS FUNCTION
    return chairs;
}

Welcome to the Game of Chairs, where you either win or have your memory freed.

musical_chairs is written using the following structs that cannot be changed:

// player in the game of chairs
struct player {
    char name[MAX_NAME_LENGTH];
};

// A node in a linked list of chairs
struct chair {
    struct player *sitting;
    struct chair *next;
};

The chair struct is a linked list node.

The player struct represents a player that can sit on a chair (represented by the chair's pointer aiming at the player).

make_music is given a pointer to a chair, which is the first element in a list of chairs. It is also given an int turns which represents how many turns of movement there will be before the music stops.

Like the game of Musical Chairs, this program will have players move along the linked list, changing which chair they're sitting in.

In make_music, every player moves turns spaces along the linked list. Anyone who moves off the end of the linked list, should then move to the head of the list, so the players will end up rotating through the list as if it's a loop. This would be similar to if the next of the last chair was aimed at the first chair.

Once all the players have finished moving, the head of the list of chairs is removed. This means both that chair and the player sitting in it are removed from the game.

make_music should then print out the name of the player that was removed.

Be careful to make sure you free all memory used in this game!

For example if a list of chairs called thrones looks like this:

throne points at the player named "Spoiler Alert"
throne points at the player named "Eddard Stark"
throne points at the player named "Joffrey Baratheon"
throne points at the player named "Cersei Lannister"
throne points at the player named "Robert Baratheon"

Then the following function is called:

make_music(3, thrones);

The output would be:

Joffrey Baratheon

and the resulting linked list would look like this:

(throne pointed at "Joffrey Baratheon" but was removed)
throne points at the player named "Cersei Lannister"
throne points at the player named "Robert Baratheon"
throne points at the player named "Spoiler Alert"
throne points at the player named "Eddard Stark"

In this list, all the players have moved down 3 chairs and are now sitting in different chairs. Anyone that moved past the end of the chairs was moved back to the top of the list of chairs.

Assumptions/Restrictions/Clarifications.

You can assume the list provided to make_music will not be empty. You can assume the number of turns will not be negative.

struct player and struct chair cannot be edited. They must be used as they are.

The be_seated function will help you create chairs. It cannot be edited and must be used as it is.

You may not use arrays in this solution. Arrays are not necessary to complete this task.

You must free all memory used in your program. Use dcc --leak-check if you need to check for memory leaks. Autotest will also check your code for leaks Your submitted file may contain a main function. It will not be tested or marked.

You can run an automated code style checker using the following command:
1511 style musical_chairs.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest musical_chairs

When you are finished working on this exercise, you and your lab partner must both submit your work by running give:

give cs1511 lab09_musical_chairs musical_chairs.c

Note, even though this is a pair exercise, you both must run give from your own account before Monday 15 November 20:00 to obtain the marks for this lab exercise.

Exercise
(☠)
:

The Student Becomes The Teacher

Welcome to Week 9 of COMP1511. The end of term is in sight!

If you've come this far in this week's lab, you're probably feeling pretty confident in some aspects of the course! So, why not help yourself and your peers by creating a resource that teaches a concept in COMP1511?

Details

For this exercise, create content that helps teach a concept in COMP1511. This could be a video, a program, a blog, or anything else you can think of.

If you're not sure what to do, chat to your tutor for inspiration!

When you're done, post your creation on the forum. We may also post some of the resources you share in one place, so everyone can benefit from them!

If you're interested in becoming a tutor for a COMP course, this can also be great practice, as one requirement we have for tutoring applicants is making a short explainer video.

This is the last challenge exercise for the term! Next week, we will have this exercise as well; so you'll have two weeks to complete this :)

You can run an automated code style checker using the following command:
1511 style student_becomes_teacher_week9.c

Submission

When you are finished each exercises make sure you submit your work by running give.

You can run give multiple times. Only your last submission will be marked.

Don't submit any exercises you haven't attempted.

If you are working at home, you may find it more convenient to upload your work via give's web interface.

Remember you have until Week 10 Monday 20:00 to submit your work.

You cannot obtain marks by e-mailing your code to tutors or lecturers.

You check the files you have submitted here.

Automarking will be run by the lecturer several days after the submission deadline, using test cases different to those autotest runs for you. (Hint: do your own testing as well as running autotest.)

After automarking is run by the lecturer you can view your results here. The resulting mark will also be available via give's web interface.

Lab Marks

When all components of a lab are automarked you should be able to view the the marks via give's web interface or by running this command on a CSE machine:

1511 classrun -sturec