Due 10/6

Linked lists #1

Goals

This assignment has the following objectives:

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)

Warm-up exercises

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: 264get hw08

For the warm-up, you will create a doubly-linked linked list of integers. Your struct Node should have three attributes: value (type: int), prev, and next. Replace each /* TODO */ comment with the appropriate code. The only output is as shown in the comments.

Opt out.

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%).

Overview

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:
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

Your submission must contain each of the following files, as specified:

file	contents
team.c	functions	`create team(char✶ name, int population, struct Person✶ people)` → return type: struct Team Return a `struct Team` object. • `name` is the name of the team and is a non-empty string • `population` is the number of people in the team, and is always ≥0. • `people` is an array of size `population` containing `struct Person` objects with their `favorite` attributes already set. • Everything the team refers to—the `struct Person` objects, their `name` attributes, and the `struct PersonNode` objects—will all be on the heap. • In case of an empty team (`population==0`), the `head` and `tail` will both be `NULL`. • The `struct Team` object this returns will be on the stack, even though the objects it refers to will be on the heap.
		`free team(struct Team✶ team)` → return type: void Free all heap memory referred to by the team, directly or indirectly, including the `struct Person` objects it refers to, and the `name` attribute of each. Assume the `struct Team` object itself is on the stack; do not attempt to free the `struct Team` object itself.
		`find person(struct Team✶ team, char✶ name)` → return type: struct Person✶ return the address of the first person with the given name, or NULL if not found
		`add person(struct Team✶ team, char✶ name, char✶ favorite name)` → return type: struct Person✶ add a struct Person to the end of the team; for `add_person(…)` you may assume the person's favorite is already in 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(struct Team✶ team, char✶ name)` → return type: struct Person✶ detach and return the address of the first person with the given name, or NULL if not found; free the `PersonNode` only; assume the caller will take care of freeing the detached `Person` after they are done using the Team (e.g., right before `main(…)` ends)
		`free person(struct Person✶ person)` → return type: void free the struct Person object and all heap memory that it is responsible for (i.e., the name)
		`fprint team(struct Team✶ team, FILE✶ stream)` → return type: void print 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) 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.
team.h	struct type definitions	struct Person =2 fields: `name` (string), `favorite` (address of a struct Person)
		struct PersonNode =3 fields: `value` (address of a `struct Person`), `next` (address of a `struct PersonNode`), `prev` (address of a `struct PersonNode`)
		struct Team =3 fields: `name` (string), `head` (of the linked list of people), and `tail` (of the same linked list)
	forward declarations	forward declarations of all functions in your team.c
test_team.c	functions	`main(int argc, char✶ argv[])` → return type: int Test all of the code in your team.c. Reminder: Do not copy test cases from the screenshot or anywhere else.
test_team.c	functions	create test team() → return type: struct Team 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.)
expected.txt	functions	Expected output from running your test_team.c
warmup.c	type definitions	struct Node
	functions	append(int value, struct Node✶✶ a head, struct Node✶✶ a tail) → return type: void Create 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(struct Node✶ victim, struct Node✶✶ a head, struct Node✶✶ a tail) → return type: void Delete the specified node. Update the head and tail of the list, if needed.
		empty list(struct Node✶✶ a head, struct Node✶✶ a tail) → return type: void
		print list(struct Node✶ head) → return type: void We provide this. Do not modify it.
		main(int argc, char✶ argv[]) → return type: int We 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	`bool`, `true`, `false`	`team.c`, `test_team.c`, `warmup.c`
stdio.h	`fprintf`, `stdout`, `FILE`	`team.c`, `test_team.c`, `warmup.c`
stdio.h	`printf`	`test_team.c`
stdlib.h	`malloc`, `free`, `NULL`, `EXIT_SUCCESS`, `EXIT_FAILURE`	`team.c`, `test_team.c`, `warmup.c`
string.h	`strlen`, `strcmp`, `strcpy`	`team.c`, `test_team.c`, `warmup.c`
assert.h	`assert`	`team.c`, `test_team.c`, `warmup.c`

All others are prohibited unless approved by the instructor. Feel free to ask if there is something you would like to use.

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 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. It is okay to use the same basic pattern for some of your tests, but your test_team.c should not look like a copy (or near-copy) of the one in the screenshot.
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.

Screenshots

When you are finished, it will look like this:

team.c

team.h

test_team.c

expected.txt

warmup.c

The test_team.c in the screenshot would be inadequate by itself. Your test must be your own, and must be more thorough. Your test should cover edge cases that this doesn't cover. It is your responsibility to think through what edge cases might be possible. Feel free to ask on Blackboard if you're wondering if something is too absurd. It is okay to use the same basic pattern for some of your tests, but your test_team.c should not look like a copy (or near-copy) of the one in the screenshot.

Q&A

Do we need to implement pick_leader(…)?
No.
Can a person be their own favorite?
Yes.
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. find_person(…), 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?
No.
Should struct Team have a population?
No.
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.
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 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.
What is assert(…)?

The 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 append(…):

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 NULL.

assert((*a_head) -> prev == NULL);

The prev attribute of the head should always be NULL since there can be nothing before the head.

assert((*a_tail) -> next == NULL);

The next attribute of the tail should always be NULL since there can be nothing after the tail.

In empty_list(…):

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 assert(…) anywhere else?
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.
Why does add_person(…) return a value?
It returns the address of the Person it 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.
Should detach_person(…) free the PersonNode(…)?
YES. Free the PersonNode but 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.

Updates

10/2: #include <…> statements may appear in the .c files that use them, or in your team.h, at your option; main(…) should return EXIT_SUCCESS; added Q13-Q16

10/3: Clarified that detach_person(…) and add_person(…) return the address of the Person not the PersonNode in Q&; clarified other subtleties in requirements

Advanced C Programming

Autumn 2016 :: ECE 264 :: Purdue University