Linked lists #1
- Learn how to create code that uses linked lists (a kind of dynamic structure)
- Learn C99 compound struct initializer syntax
- Practice creating test cases
- 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)
This assignment includes a warm-up exercise to help you get ready. This accounts for 20% of your score for HW08. Scoring will be relatively light, but the usual base requirements apply.
To get the starter files, type this:
For the warm-up, you will create a doubly-linked linked list of integers. Your
struct Node should have three attributes:
/* TODO */ comment with the appropriate code. The only output
is as shown in the comments.
In a hurry, and don't need the practice? This warm-up is here to help you learn what you need to succeed on the rest of this assignment—not to add additional work. Therefore, we give you an option. Those who feel that they do not need the practice may "opt out". by modifying warmup.c so that it does nothing but print the following message exactly and then exit:
I already know this and do not need to practice.
If you do that, then your score for HW08 will be based solely on the rest of this assignment. If you leave the warmup.c undone, if you do not turn in a warmup.c, or if the message it prints does not match perfectly, then you will receive 0 for the warmup portion of this assignment (20%).
For this assignment, you will write a version of most of the code from HW07 but using a doubly-linked list.
See the Requirements table below for more detail on what you will create.
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 expected.txt and an empty main in test_team.c.
- Compile and use diff to check that the output agrees perfectly. The
following command should suffice:
gcc -o test_team test_team.c team.c && ./test_team | diff expected.txt -
- Add the smallest possible subset of new functionality at each step.
Here is a possible sequence in which to work:
create_team(…)for an empty team. Print the name using fprintf(stdout, team.name) from your main.
fprint_team(…)just enough so that it works for your empty team. Add it to your main.
add_person(…)just enough so that it works for a single person. Use
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 each of the following files, as specified:
file contents team.c functions
create team(char✶Xname,XintXpopulation,XstructXPerson✶Xpeople)→ return type: structXTeamReturn a
nameis the name of the team and is a non-empty string
populationis the number of people in the team, and is always ≥0.
peopleis an array of size
struct Personobjects with their
favoriteattributes already set.
• Everything the team refers to—the
struct Personobjects, their
nameattributes, and the
struct PersonNodeobjects—will all be on the heap.
• In case of an empty team (
tailwill both be
struct Teamobject this returns will be on the stack, even though the objects it refers to will be on the heap.
free team(structXTeam✶Xteam)→ return type: voidFree all heap memory referred to by the team, directly or indirectly, including the
struct Personobjects it refers to, and the
nameattribute of each. Assume the
struct Teamobject itself is on the stack; do not attempt to free the
struct Teamobject itself.
find person(structXTeam✶Xteam,Xchar✶Xname)→ return type: structXPerson✶return the address of the first person with the given name, or NULL if not found
add person(structXTeam✶Xteam,Xchar✶Xname,Xchar✶Xfavorite name)→ return type: structXPerson✶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.)
detach person(structXTeam✶Xteam,Xchar✶Xname)→ return type: structXPerson✶detach and return the address of the first person with the given name, or NULL if not found;
free person(structXPerson✶Xperson)→ return type: voidfree the struct Person object and all heap memory that it is responsible for (i.e., the name)
fprint team(structXTeam✶Xteam,XFILE✶Xstream)→ return type: voidprint the team's name and members to stdout in the following format:
Modern Jazz Quartet - members: Milt Jackson (favorite: John Lewis) John Lewis (favorite: Percy Heath) Percy Heath (favorite: John Lewis) Connie Kay (favorite: Milt Jackson)
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.
team.h struct type definitionsstructXPerson=2 fields:
favorite(address of a struct Person)structXPersonNode=3 fields:
value(address of a
next(address of a
prev(address of a
struct PersonNode)structXTeam=3 fields:
head(of the linked list of people), and
tail(of the same linked list)
forward declarationsforwardXdeclarationsXofXallXfunctionsXinXyourXteam.c test_team.c functions
main(intXargc,Xchar✶Xargv)→ return type: intTest all of the code in your team.c. Reminder: Do not copy test cases from the screenshot or anywhere else.create test team()→ return type: structXTeamcreate 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 Teamobject; limit: 2 statements; a basic outline is shown in the screenshot; the first statement must declare/initialize an array of
struct Personobjects. The second statement must call
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.)
expected.txt functions Expected output from running your test_team.c warmup.c type definitionsstructXNode functionsappend(intXvalue,XstructXNode✶✶Xa head,XstructXNode✶✶Xa tail)→ return type: voidCreate a new node with the specified value and append it to the tail of the list. Update the head and tail of the list, as needed.delete(structXNode✶Xvictim,XstructXNode✶✶Xa head,XstructXNode✶✶Xa tail)→ return type: voidDelete the specified node. Update the head and tail of the list, if needed.empty list(structXNode✶✶Xa head,XstructXNode✶✶Xa tail)→ return type: voidprint list(structXNode✶Xhead)→ return type: voidWe provide this. Do not modify it.main(intXargc,Xchar✶Xargv)→ return type: intWe provide this. Do not modify it, except where it says
/* TODO */.
Only the following externally defined functions and constants are
allowed in your .c files. (You may put the corresponding
#include <…>statements in the .c file or in your team.h, at your option.)
header functions/symbols allowed in… stdbool.h
- All data referenced by a Team structure must be on the heap. That includes all
struct Personobjects, their names, and the team name. The
struct Teamobject 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 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_test_team.c) and do not copy-paste from that into your own test_team.c.
- Struct types may not have any additional fields, other than those shown above.
- Submissions must meet the code quality standards and the policies on homework and academic integrity.
How much work is this?
This assignment will take some time to write and debug. Linked lists can be tricky to debug.
When you are finished, it will look like this:
Do we need to implement
Can a person be their own favorite?
create_team(…), may we may assume that
peopleis the right size?
Yes. You may assume that it is of size population.
How can we test the case of an empty team?
create_team(…), pass 0 for population and NULL for people.
detach_person(…), should return NULL if population==0.
add_person(…)should work normally.
fprint_team(…)should print "(none)" for the members. For example:
Some Empty Team - members: (none)
Can we add additional fields to the struct types?
struct Teamhave a population?
Why can't we use regular
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?
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
From bash, type
man strcmp(and similar for the others). The basic parameters are listed on the course reference sheet.
How do I pass the names to
create_test_team(…)always returns the same team.
What should be the names for
Anything you want. It should be your own idea, not copied from the screenshots.
What is a
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.
assert(…)statements are there to help you catch bugs in your code. An
assert(…)simply checks if the condition is true, and forces your program to crash if it is not. They are widely used in real-world development to make code self-testing.
IMPORTANT: Never use an
assert(…)to check for regular error conditions (e.g., user entered the wrong thing, missing file, etc.). An
assert(…)should never fail (i.e., cause your program to crash) unless your code has a bug.
Here's what each one does:In
assert(*a_head != NULL);
assert(*a_tail != NULL);If you have appended a node, then the list must not be empty, so neither the head nor the tail can be
assert((*a_head) -> prev == NULL);The
prevattribute of the head should always be
NULLsince there can be nothing before the head.
assert((*a_tail) -> next == NULL);The
nextattribute of the tail should always be
NULLsince there can be nothing after the tail.In
assert(*a_head == NULL);
assert(*a_tail == NULL);In an empty list, the head and tail must be
NULL, by definition.
Do I need to use
No. You may use it if you like, as long as you use it properly. Use it only to check intermediate values in your code for conditions that will never happen unless your code is faulty. In particular, it should never be used to check input from the user, files, system status, the arguments passed from calling code, or anything else external.
A good use of
assert(…)is to check that the output of your function is sane. Similarly, before writing a character to a string, you might use an
assert(…)to make sure you are not writing out of bounds.
add_person(…)return a value?
It returns the address of the
Personit just created. This doesn't serve very much purpose in this assignment, but it can enhance your ability to test your code, by checking your assumptions about the node that was just added.
In other libraries,
add…(…)functions often return the thing they just added for convenience. It can make some of the calling code more elevant.
YES. Free the
PersonNodebut do not free the
Person. (This was changed 10/3/2016.)
One could imagine using that to enable moving people from one team to another. You don't have to test that for this assignment, but that is part of the spirit. It also aids in testing your code.
#include <…> statements may appear
in the .c files that use them, or in your team.h, at your option;
main(…) should return
10/3: Clarified that
add_person(…) return the address of the
Person not the
PersonNode in Q&; clarified other subtleties in requirements