text: Linked lists #3
  Goals
  - Learn how to keep data separate from containers
  - Practice designing algorithms and data structures
  - Practice using code that uses the following:
  - linked lists
  - structures for data encapsulation
  - dynamic memory (i.e., malloc)
  - struct initializer syntax (C99)
  Overview
  Your
  pick_leader(…) in
  HW07
  implemented the plurality system of voting:
  voters choose one candidate as their favorite, and the
  candidate with the most votes wins. This is the system
  used in most elections in the United States.
  Plurality has an obvious problem: a candidate can win even if they are not preferred by a majority (>50%) of the voters. This has been seen in numerous elections.
  For this assignment, you will modify your code from HW09 to follow the instant-runoff method of choosing a winner. Each person chooses one or more favorites. If one candidate receives over 50% of the vote, then that candidate is the winner. Otherwise, the candidate with the fewest number of votes is eliminated from consideration, and the process is repeated.
  Example
  In this team, each person has given a list of favorites. For example, Kami's top choice is Fujita. If Fujita doesn't win, then she would prefer Baba. If neither Fujita nor Baba wins, then she would prefer Azuma. Kami has no additional preferences.
  Doko gets 4 votes (40%) but fails to win a majority. Azuma and Ihara each get 2 votes (20%). Fujita and Gima each get 1 vote (10%). Fujita and Gima will be eliminated since they have the fewest votes.
  Doko and Azuma each get 4 votes (40%). Ihara gets 2 votes (20%). Ihara will be eliminated.
  Azuma gets 6 votes (60%). Ihara gets 4 votes (40%) each. Azuma is the winner.
  Update: The example above was modified 10/23 because it was pointed out that it was inconsistent with the other descriptions of the instant-runoff algorithm. Candidates with zero votes should be eliminated, but the original version of the example incorrectly eliminated only losers (least # of votes) with ≥1 vote. It did not affect the final result, but it did affect some of the intermediate steps. We will accept submissions that work either way. The pre-tester has accepted both from the beginning. Likewise, any further examples will either be designed so that the result is the same either way, or else we will make sure the test accepts either answer.
  Voting algorithms (This part is optional and will not be covered on any exam.)
  There are many voting algorithms, but none is perfect. They can be evaluated based on a variety of criteria.
  // Credit: This section includes text from the Wikipedia article on Instant-runoff voting (Creative Commons Attribution-ShareAlike License)
  Getting started
  There are no starter files and no warm-up for HW10.
  Doing the assignment
  Use test-driven development to do this assignment incrementally.
  - Start with your working expected.txt and test_team.c from HW09.
  - Comment out everything in your
  main(…).
  - Compile and use diff to check that the output agrees perfectly.
  gcc -o test_team test_team.c team.c && ./test_team | diff expected.txt -
  - One by one, add in each step from your
  main(…)until you have all of the functionality.
  - Create an empty team.
  - Create a team with one person who has no favorites.
  - Create a team with one person who is their own favorite.
  - Create a team with two people who are each other's favorite (but still only one favorite per person).
  - Create a team with two people who have both of the two people in their favorites (i.e., 2 favorites each).
  -
  struct Teamobject 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.
  - The
  struct Person,
  struct PersonNode, and
  struct Teamtypes may not have any additional fields.
  - Submissions must meet the code quality standards and the policies on homework and academic integrity.
  How much work is this?
  This should require less coding than HW08.
  The main work will be to find an algorithm for your new
  pick_leader(…). Before that, you will need
  to make some changes to the rest of the code to accomodate storing
  a sequence of favorites in each person, instead of just one favorite.
  If you understood HW08 well, then this part should be very
  straight-forward.
  As with all things involving dynamic memory, expect to spend some time debugging unless you have gotten very solid on these concepts and proficient using gdb and valgrind.
  Q&A
  - What should my
  Favoritestype be?
  It is your choice. One option is to make
  Favoritesan alias for
  struct PersonNode*, but you are free to set it to any other type that you think will make your work easiest for implementing the rest of this. Keep in mind that the user of your code (i.e., someone calling your functions from their program), must not need to be aware of anything about what your
  Favoritestype contains.
  If you are completely confused, it may help to review how
  typedefworks. Remeber that your team.h will contain exactly 4 type definitions. When referring to your
  Favoritestype elsewhere, you will not use the
  structkeyword before it. See the function signature for
  add_person(…), for example.
  - Why is
  create_favorites(…)specified as a variadic function? Why not just pass an array?
  This makes your
  create_test_team(…)a lot cleaner and shorter, and allows us to keep the requirement of two lines in
  create_test_team(…).
  - Doesn't the output format of
  fprint_team(…)need to change to accomodate multiple favorites per person?
  Nope. A person's "favorite" is still their first choice. Let's keep it simple and leave the format as is.
  - Can one of a person's favorite be someone outside the team?
  Yes. It is acceptable to have someone from outside the team included in a person's favorites list, but they may not win.
  pick_leader(…)will only return a person who is a member of the given team.
  - Will the caller use
  Favoritesfor anything else?
  No.
  - Can the same
  struct Personobject appear twice in another person's favorites?
  You may assume that won't happen.
  - How can I ensure that
  create_favorites(…)can access the names of the people being passed to it?
  This is not necessary. You don't need to access or copy the name of the person within create_favorites(…). That can be done in create_team(…). You may assume that the Person objects referred to when create_favorites(…) is called will still exist when create_team(…) is called.
  - May we assume the
  struct Personobjects passed (by address) to
  create_favorites(…)will still exist when
  create_team(…)is called?
  Yes.
  - Can we use Favorites* instead of Favorites in our
  struct Person?
  No.
  - Can Favorites be an address type?
  Yes. The following is one possibility. (Feel free to use/copy as is.)
  typedef struct PersonNode* Favorites;
  Here is a very simple example of using typedef to create an address type that hides the star. In this case, T is an alias for S*.
  #include <stdio.h> struct S { int x, y; }; typedef struct S* T; int main(int argc, char *argv[]) { struct S s = {.x = 4, .y = 5}; T t = &s; printf("s.x ===== %d ... s.y ===== %d\n", s.x, s.y); printf("t -> x == %d ... t -> y == %d\n", t->x, t->y); return 0; }
  - How should
  create_test_team(…)be structured?
  The basic format is very similar to the one used in HW09. (Feel free to copy/use this.)
  struct Team create_test_team() { struct Person people[] = { { .name="…", .favorites=create_favorites(&people[…], &people[…], NULL) }, { .name="…", .favorites=create_favorites(&people[…], &people[…], NULL) }, { .name="…", .favorites=create_favorites(NULL) }, // no favorites { .name="…", .favorites=create_favorites(&people[…], NULL) }, // 1 favorite }; return create_team("…", sizeof(people)/sizeof(*people), people); }
  - Where should the favorites be allocated?
  It's up to you, but you probably want to have your
  create_favorites(…)create the container (e.g., a linked list) to hold the
  struct Personobjects that are passed to it. However, it will not allocate memory for the
  struct Personobjects themselves.
  - Can I allocate the
  struct Personobjects in my
  create_favorites(…)?
  It is not directly prohibited by the requirements, but you probably wouldn't want to. This is just like in HW07. If three people vote for the same person (i.e., have that person in their favorites), you want the ultimate structure to refer to the same
  struct Personobhject. Therefore, it will need to be created outside
  create_favorites(…). You will do this from your
  create_team(…).
  This wouldn't work at all with your
  create_test_team(…)because it needs to be 2 statements. It is possible to pass the address of an element of
  peopleto
  create_favorites(…), even within the initialization of
  people, if
  create_favorites(…)tries to access that memory, it will result in an error because at the time
  create_favorites(…)is called,
  peoplehasn't been initialized, yet.
  - Should I use
  add_favorite(…)in my
  create_favorites(…)?
  You may if you like, but it probably won't be useful.
  - Should I use
  create_favorites(…)in my
  create_team(…)?
  You may if you like, but it probably won't be useful.
  - How can I reuse code?
  There are many perfectly reasonable and correct ways to structure your code for this assignment.
  You might find it useful to create a couple general purpose helper functions at the top of your team.c. Here are a couple examples. You don't have to use these, but you may use/copy if you wish.
  void _add(struct Person* p, struct PersonNode** head, struct PersonNode** tail, int idx); // Add a person at position idx in any given linked list void _connect_all_favorites(Favorites favorites, struct Team* team); // Replace every Person* in favorites with the address of the one with the // same name in the given team
  - How do we add a favorite who is not on the team?
  This can't be done from your
  create_test_team(…)but it could easily be done from your
  main(…). Just create a
  struct Personobject (most likely on the stack) and then, in a separate statement, pass it to
  create_favorites(…).
  - What if eliminating multiple losers in one round results in eliminating what would otherwise be a clear winner??
  At each round, just eliminate the candidate(s) that have the least number of votes in that round. Once a candidate has been eliminated, they are permanently eliminated, even if they were somebody's later choice.
  Example:
  - A's favorites are A and B
  - B's favorite is only B
  - C's favorite is only C
  In round 1, A, B, and C all get one vote each, so all are eliminated. Since B was eliminated in round 1, B has been permanently eliminated and is not considered in round 2. This was illustrated in the example shown at the beginning of this assignment.
  - What is
  fprintf(…)?
  fprintf(stdout, …)is equivalent to
  printf(…). For now, that's all you really need to know. For those who are curious,
  fprintf(…)is a more general version of
  printf(…)that also allows printing to files, for example. We will study files later in this semester. We are using
  fprintf(…)now, in part so that when you get to it later, it will be a little familiar. Also, it gives us more options for testing your code.
  - Should
  create_test_team(…)be in team.c or test_team.c?
  team.c
  - How do we handle favorites who are not on the team?
  Treat them as already eliminated.Example:Yoshio is not on the team and is eliminated immediately.Azuma, Baba, Edo, and Do are all eliminated.There is no winner.
  - If all of a voter's favorites are eliminated (or are outside the team), do we go by a majority of team members or votes?
  Votes.Example:Baba, Edo, and Fujita get 1 vote and will be eliminated. Azuma gets 0 votes and will also be eliminated.Doko wins with 2 votes (100% of the 2 votes).
  The HW08 Q&A has more answers about topics such as
  assert(…),
  add_person(…)and
  detach_person(…).
  Updates
  10/15:
  free_team(…) must set
  head,
  tail, and
  name to
  NULL; clarified requirements for
  fprint_team(…) and
  pick_leader(…); moved a few Q&A items into the requirements table; reformatted the requirements table for readability; removed erroneous reference to warmup;
  copy_team(…) specification is included with the rest of the functions
  10/16:
  add_favorite(…) takes a
  rank in the range 0 ≤ |rank| ≤ number of favorites so far, and returns
  void; clarified role of
  create_favorites(…) in relation to
  create_team(…) and
  add_person(…); In the last example under
  fprint_team(…) Monise is the leader.
  10/19: Memory allocated by
  create_favorites(…) is freed by
  free_person(…) or
  free_team(…); fixed compile/run command.
  10/20: Removed an errant example from Q17.
  10/23: Corrected the example to show that candidates with 0 votes are eliminated along with those receiving the least # of votes. This did not affect the final result of that example.; Added Q21 and Q22.
  10/24: Corrected Q22: Azuma should be eliminated, too; Clarified that
  copy_team(…) does not need to deal with outsider favorites; further clarified that we will accept submissions that eliminate losers with zero votes and submissions that do not