Lab 2

Deadline: EOL (End Of Lab) Friday, September 20th

Setup

To get the starter files for this lab, run the following command in your labs directory.

git pull starter master

If you get an error like the following:

fatal: 'starter' does not appear to be a git repository
fatal: Could not read from remote repository.

make sure to set the starter remote as follows:

git remote add starter https://github.com/61c-teach/fa19-lab-starter.git

and run the original command again.

Objectives

  • TSW will become comfortable with C structs, pointer manipulation, and memory management in C.

Exercise 1: Linked Lists

Here’s another exercise to help you in your interviews! For this exercise, you will fill in the functions append_node() and reverse_list() in list.c. Don’t forget to look at list.h to see the definition of the node struct and also to see the general format of a simple .h (header) file!

In append_node(), you will append a node to the end of a linked list.

In reverse_list(), you will reverse a linked list in place (i.e. without creating a new list). For example, the list 1->2->3->4->5 would become 5->4->3->2->1. HINT: In each iteration of your loop to traverse the linked list, think about what information you need to store in variables before reversing the link so that you can still successfully keep iterating through the list and reversing links. This is a fairly difficult exercise in C; we recommend that you draw a picture if you get stuck because doing so tends to make double pointers seem less intimidating. Please write up what you think the algorithm should be before asking a TA for help. You can think of the double pointer as simply a pointer to a list of pointers to nodes.

Why do both of these functions take in a node** and not a node*? Think about memory management; if the input was a node*, would it be possible to modify the pointer that was passed into the function from, say, the main() function? Remember that C is pass-by-value!

ACTION ITEM: Finish implementing append_node() and reverse_list().

Once you complete these functions, you can compile and run your code using the following commands. If you make any changes, make sure to run ALL of the following commands again, in order.

If you compile and run locally, the test may print out that the next attributes of your nodes are 0x0 and that your test failed. This is completely fine; your tests will pass the autograder. If you’d like to be completely sure that your test passes locally, compile and run your code on the hive machines.

$ gcc -c list.c
$ gcc -c test_list.c
$ gcc -g -o test_list test_list.o list.o       //This will create an executable by linking test_list.o and list.o. 
$ ./test_list

This will print out the results of the test. To debug, you can run CGDB and step through the test in test_list.c.

Exercise 2: Work on Homework 2 and Project 1

This isn’t a graded exercise; however, we highly encourage you to work on the homework and/or project. As a reminder, Homework 2 (both the Gradescope component and the Cellular Automata component) is due this Friday, 9/13. Project 1 is due 9/27, but it’ll only benefit you to get started early :)

Checkoff

Please submit to the Lab Autograder assignment (same as last week!).

After submitting to the autograder, you and your lab partner must get individual tokens to be properly checked off!