Linked lists #1

Goals

Prepare

Do the following before you attempt to code this assignment.

1. Write some tiny programs using the following, to make sure you understand each completely. Do not simply read existing examples. If you see something online that you want to try, type it instead of copy-pasting it in.
   1. linked list: add, find, detach, delete
   2. doubly linked list
   3. anything from the last homework that you didn't master 100%
2. As always… read this assignment description carefully.

Practicing before you start the assignment will make your life easy. Not doing so will make this assignment take longer.

Overview

For this assignment, you will modify your code from the last one to use linked lists for the people in the teams. There are a few modifications to the function signatures, and a few new functions to add.

Unlike the linked lists we discussed in class, you will be creating a doubly linked list for this assignment. That means that each list node contains the address of the previous node, as well as the next node and the value.

Here is what you will create. There are no starter files. (Some notable changes from hw05 are highlighted.)

Modern Jazz Quartet
- leader:  John Lewis
- members: Milt Jackson (favorite: John Lewis)
           John Lewis   (favorite: Percy Heath)
           Percy Heath  (favorite: John Lewis)
           Connie Kay   (favorite: Milt Jackson)

Type all declarations into your program manually. Do not copy-paste. (You learn more from typing code manually.)

Doing the assignment

Use test-driven development to do this assignment incrementally.

1. Start with blank teamtest.txt and an empty main in teamtest.c.
2. Compile and use diff to check that the output agrees perfectly. The following command should suffice:
   gcc -o teamtest teamtest.c team.c && ./teamtest | diff teamtest.txt -
3. Add the smallest possible subset of new functionality at each step. Here is a possible sequence in which to work:
   1. Implement create_team(…) for an empty team. Print the name using fprintf(stdout, team.name) from your main.
   2. Implement fprint_team(…) just enough so that it works for your empty team. Add it to your main.
   3. Implement add_person(…) just enough so that it works for a single person. Use fprintf(…) from your main(…) to test print the person's name via the team object.
   4. Make your fprint_team(…) work sufficiently to handle your team with one person.

Your code should never be broken for more than about 10-15 minutes. If you are not doing this, you are taking longer than necessary to do the assignment.

Requirements

How much work is this?

This assignment is will take some time to write and debug. Linked lists can be tricky to debug.

Once you get a few parts of it working, the rest should go faster. Your create_team(…) and copy_team(…) will be a little similar. Your find_person(…) and detach_person(…) will also be a little similar. Practice on toy programs before you start this assignment. Go slow and think through your algorithm for each function before you attempt to code it. Look for ways to keep your code short.

Screenshots

When you are finished, it will look like this:

Q&A

1. What should pick_leader(…) do in case of a tie?
   Among those that are tied for the most number of “favorite” votes, pick the one closest to the beginning of the list.
2. Can a person be their own favorite?
   Yes.
3. In create_team(…), may we may assume that people is the right size?
   Yes. You may assume that it is of size population.
4. How can we test the case of an empty team?
   When calling create_team(…), pass 0 for population and NULL for people. pick_leader(…), find_person(…), detach_person(…), should return NULL if population==0. add_person(…) and copy_team(…) should work normally. fprint_team(…) should print "(none)" for the leader and members. For example:
   

   Some Empty Team
   - leader:  (none)
   - members: (none)

5. Can we use nested loops?
   Yes.
6. Can we add additional fields to the struct types?
   No.
7. Do we need to make a get_population(…) function?
   No.
8. Should struct Team have a population?
   No.
9. Will there be lab hours over the weekend before the deadline?
   No.
10. Why can't we use regular printf(…)?
    This is just a gentle way to get ready for the future unit on files and streams. fprintf(…) looks a little different, but it works exactly the same. The only difference is that it lets you specify where you want to send the output.
11. What's the best way to check if two strings are equal?
    Use strcmp(…). If the strings are equal, strcmp(…) will return 0 (zero). For example, strcmp("abc", "abc") == 0. Be careful. That is easy to forget.
12. Where can I get more information about strcmp(…), strlen(…) and strcpy(…)?
    From bash, type man strcmp (and similar for the others). The basic parameters are listed on the course reference sheet.
13. Why does strdup_(…) have an underscore at the end?
    We are making our own version of a commonly used function called strdup(…). The original one had no underscore. We can't use it because in this class, we are using the -std=c99 compiler flag to force gcc to use only standard C99. The original strdup(…) is actually an extension provided by gcc, and not part of the official C language specification. However, just in case this code were ever compiled with different flags, we don't want to use exactly the same name. One convention used by some people is to add an underscore to the end, when you are trying to avoid conflict with a reserved word or commonly used built-in function.
14. How do I pass the names to create_test_team()?
    You don't. create_test_team(…) always returns the same team.
15. What should be the names for create_test_team()?
    Anything you want. It should be your own idea, not copied from the screenshots.
16. What is the purpose of copy_team(…)?
    The primary purpose of copy_team(…) is as an exercise in “deep copy”. However, it will also allow you to create more interesting tests, in which you start with a big team and then detach some of the members to form a new, separate team. It is primarily there as an exercise in “deep copy”. There is a chance the next assignment may make use of your copy_team(…), as well.
17. What is a FILE*?
    FILE* is the type of stdout. In order to pass stdout to a function, you have to give a type. You don't need to understand this deeply (yet).
    
    If you are curious… Later in the course, we will cover files and streams, and you will learn that the code for writing/reading to/from files on disk is very similar to writing characters to the console or reading characters from the keyboard. A FILE* can be a stream, such as stdout, stderr, or stdin. It can also be an open file. Thus, you would be able to very easily use your code in this assignment to write the team information to files instead of to the console.

Updates

10/10: Added screenshots, removed create_test_team_array, modified create_test_team, added free_person and free_team, extended deadline to 10/18

10/11: Clarification: create_test_team(…) returns a struct Team; add_person(…) adds to the end of the team; in create_team(…) people should be in the same order as they were in the array

10/12: Added Q17 ("What is a FILE*") to the Q&A.