Linked lists #1
- Learn how to create code that uses linked lists (a kind of dynamic structure)
- Learn C99 compound struct initializer syntax
- Practice using structures for data encapsulation
- Practice programming with dynamic memory (i.e., malloc)
- Practice debugging memory errors
- Practice using struct syntax (including a semicolon (";") after your struct statement)
Do the following before you attempt to code this assignment.
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.
- linked list: add, find, detach, delete
- doubly linked list
- anything from the last homework that you didn't master 100%
- 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.
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.)
=3 fields: name (string), head (of the linked list of people), and tail (of the same linked list)
=2 fields: name (string), favorite (address of a struct Person)
=3 fields: value (address of a struct Person), next (address of a struct PersonNode), previous (address of a struct PersonNode)
one for each of the required functions in test.c (but not teamtest.c)
create＿team(char✶ name, int population, struct Person✶ people)
create an instance of struct Team with population people
find＿person(struct Team✶ team, char✶ name)
return the address of the first person with the given name, or NULL if not found
detach＿person(struct Team✶ team, char✶ name)
detach and return the address of the first person with the given name, or NULL if not found
free the struct Person object and all heap memory that it refers to (i.e., the name)
free all heap memory referred to by the struct Team object, directly or indirectly; this should call your free_person(…) function; assume the struct Team object itself is on the stack; do not attempt to free the struct Team object itself
add a struct Person to the end of the team; you will need to copy the name; you can use strdup_ for that if you like; (Hint: Your find_person(…) might come in handy.)
copy＿team(struct Team✶ team)
make a deep copy of a team; not only will the struct Team object be a copy, but every struct Person (including their name fields) will be a new copy
return the person who is the favorite of the greatest number of others on the same team; in case of a tie choose the one who was added to the list first
main(int argc, char✶ argv)
test your functions in team.c; must be comprehensive and original
create an array (on the stack) of ≥4 people (struct Person) using C99 compound initializer syntax and then pass that to your create_team(…) to create a new struct team object; limit: 2 statements; a basic outline is shown in the screenshot; the first statement must declare/initialize an array of struct Person objects. The second statement must call create_team(…); your create_test_team(…) will return a struct Team; people should be in the same order as in the array (Hint: You can refer to the name of a struct object even within its initializer.)
fprint＿team(struct Team✶, FILE✶ stream)
print the team's name, leader's name, and members to stdout in the following format:
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)
This will need to call pick_leader(…) since the leader is not stored in the struct Team. Use fprintf(stream, …) in this function. When you test in your main(…), test with fprint_team(&team, stdout). (Note that fprintf(stdout, …) is equivalent to printf(…).) Use spaces, not tabs. Exactly one space should separate the end of the longest name (e.g., "Milt Jackson") and "(favorite: …)". Each line ends with "\n" and. Additional spaces before the "\n" are not allowed. Display members in the order they were added to the team. This specification is precise. Your output should match exactly.
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.
- Start with blank teamtest.txt and an empty main in teamtest.c.
- 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 -
- Add the smallest possible subset of new functionality at each step.
Here is a possible sequence in which to work:
- Implement create_team(…) for an empty team. Print the name using fprintf(stdout, team.name) from your main.
- Implement fprint_team(…) just enough so that it works for your empty team. Add it to your main.
- 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.
- 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.
- Your submission must contain the files specified in the overview and screenshot above and your teamtest.txt (as usual).
- All data referenced by a Team structure must be on the heap. That includes all struct Person objects, their names, and the team name. The struct Team object itself may be on the stack.
- Make no assumptions about the number of people on a team, or the length of a person's name.
- Your teamtest.c must be your own, and must test all functionality. The one in the screenshot would be inadequate.
- Your code must work with the example code shown in the screenshot. You are welcome and encouraged to test with it, but give it a different name (e.g., example_teamtest.c) and do not copy-paste from that into your own teamtest.c.
- Struct types may not have any additional fields, other than those shown above.
Only the following external header files, functions, and symbols are
allowed. (All others are prohibited.)
header functions/symbols allowed in… stdlib.h malloc(…), free(…) team.c, team.h, teamtest.c stdbool.h true, false team.c, team.h, teamtest.c string.h strlen(…), strcmp(…), strcpy(…) team.c, team.h, teamtest.c stdio.h fprintf(…), stdout teamtest.c
- As usual…
- Do not use dynamic arrays (C99 feature, e.g., char s[n];)
- Code must successfully compile and run with your teamtest.c and any other valid test file.
- Code must meet all requirements in the Course Policies.
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.
When you are finished, it will look like this:
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.
Can a person be their own favorite?
In create_team(…), may we may assume that people is the right size?
Yes. You may assume that it is of size population.
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)
Can we use nested loops?
Can we add additional fields to the struct types?
Do we need to make a get_population(…) function?
Should struct Team have a population?
Will there be lab hours over the weekend before the deadline?
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.
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.
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.
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.
How do I pass the names to create_test_team()?
You don't. create_test_team(…) always returns the same team.
What should be the names for create_test_team()?
Anything you want. It should be your own idea, not copied from the screenshots.
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.
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.
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.