Advanced C Programming

Autumn 2016 :: ECE 264 :: Purdue University

This is for Fall 2016 (last year)
Due 10/6

Linked lists #1

Goals

This assignment has the following objectives:
  1. Learn how to create code that uses linked lists (a kind of dynamic structure)
  2. Learn C99 compound struct initializer syntax
  3. Practice creating test cases
  4. Practice using structures for data encapsulation
  5. Practice programming with dynamic memory (i.e., malloc)
  6. Practice debugging memory errors
  7. 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.

  1. Start with blank expected.txt and an empty main in test_team.c.
  2. 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 -
  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

  1. 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: structXTeam
    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(structXTeam✶Xteam)
    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(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; 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(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 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(structXPerson✶Xperson)
    return type: void
    free 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: 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
    structXPerson
    =2 fields: name (string), favorite (address of a struct Person)
    structXPersonNode
    =3 fields: value (address of a struct Person), next (address of a struct PersonNode), prev (address of a struct PersonNode)
    structXTeam
    =3 fields: name (string), head (of the linked list of people), and tail (of the same linked list)
    forward declarations
    forwardXdeclarationsXofXallXfunctionsXinXyourXteam.c
    test_team.c functions
    main(intXargc,Xchar✶Xargv[])
    return type: int
    Test 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: structXTeam
    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
    structXNode
    functions
    append(intXvalue,XstructXNode✶✶Xa head,XstructXNode✶✶Xa 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(structXNode✶Xvictim,XstructXNode✶✶Xa head,XstructXNode✶✶Xa tail)
    return type: void
    Delete the specified node. Update the head and tail of the list, if needed.
    empty list(structXNode✶✶Xa head,XstructXNode✶✶Xa tail)
    return type: void
    print list(structXNode✶Xhead)
    return type: void
    We provide this. Do not modify it.
    main(intXargc,Xchar✶Xargv[])
    return type: int
    We provide this. Do not modify it, except where it says /* TODO */.
  2. 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
    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.
  3. 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.
  4. Make no assumptions about the number of people on a team, or the length of a person's name.
  5. 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.
  6. Struct types may not have any additional fields, other than those shown above.
  7. 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
initial state of project files
team.h
initial state of project files
test_team.c
initial state of project files
expected.txt
initial state of project files
warmup.c
initial state of project files
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

  1. Do we need to implement pick_leader(…)?
    No.
  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. 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)
  5. Can we add additional fields to the struct types?
    No.
  6. Should struct Team have a population?
    No.
  7. 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.
  8. 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.
  9. 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.
  10. How do I pass the names to create_test_team(…)?
    You don't. create_test_team(…) always returns the same team.
  11. What should be the names for create_test_team(…)?
    Anything you want. It should be your own idea, not copied from the screenshots.
  12. 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.
  13. 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.
  14. 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.

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

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