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.
Round 1 | Azuma's favorites: | Ihara, Azuma, Edo |
Baba's favorites: | Azuma, Ihara, Edo | |
Doko's favorites: | Doko, Azuma, Hata, Edo | |
Edo's favorites: | Doko, Azuma, Baba | |
Fujita's favorites: | Azuma, Doko, Baba | |
Gima's favorites: | Doko, Azuma, Baba | |
Hata's favorites: | Ihara, Azuma, Baba | |
Ihara's favorites: | Doko, Baba | |
Kami's favorites: | Fujita, Baba, Azuma | |
Maeda's favorites: | Gima, Azuma |
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. Baba, Edo, Kami, and Maeda are also eliminated since they got no votes at all.
Round 2 | Azuma's favorites: |
Ihara, Azuma, |
Baba's favorites: |
Azuma, Ihara, |
|
Doko's favorites: |
Doko, Azuma, Hata, |
|
Edo's favorites: |
Doko, Azuma, |
|
Fujita's favorites: |
Azuma, Doko, |
|
Gima's favorites: |
Doko, Azuma, |
|
Hata's favorites: |
Ihara, Azuma, |
|
Ihara's favorites: |
Doko, |
|
Kami's favorites: |
|
|
Maeda's favorites: |
|
Doko and Azuma each get 4 votes (40%). Ihara gets 2 votes (20%). Ihara will be eliminated.
Round 3 | Azuma's favorites: |
|
Baba's favorites: |
Azuma, |
|
Doko's favorites: |
Doko, Azuma, Hata, |
|
Edo's favorites: |
Doko, Azuma, |
|
Fujita's favorites: |
Azuma, Doko, |
|
Gima's favorites: |
Doko, Azuma, |
|
Hata's favorites: |
|
|
Ihara's favorites: |
Doko, |
|
Kami's favorites: |
|
|
Maeda's favorites: |
|
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.
criteria PASSED by instant runoff
- majority criterion - “if one candidate is preferred by an absolute majority of voters, then that candidate must win”
- later-no-harm criterion - “if a voter alters the order of candidates lower in his/her preference (e.g. swapping the second and third preferences), then that does not affect the chances of the most preferred candidate being elected”
- resolvability criterion - “the probability of an exact tie must diminish as more votes are cast”
- Condorcet loser criterion - “if a candidate would lose a head-to-head competition against every other candidate, then that candidate must not win the overall election”
- independence of clones criterion - “the election outcome remains the same even if an identical candidate who is equally preferred decides to run”
criteria FAILED by instant runoff
- Condorcet winner criterion - “if a candidate would win a head-to-head competition against every other candidate, then that candidate must win the overall election”
- consistency criterion - “if dividing the electorate into two groups and running the same election separately with each group returns the same result for both groups, then the election over the whole electorate should return this result”
- monotonicity criterion - “a voter can't harm a candidate's chances of winning by voting that candidate higher, or help a candidate by voting that candidate lower, while keeping the relative order of all the other candidates equal”
- participation criterion - “the best way to help a candidate win must not be to abstain”
- reversal symmetry criterion - “if candidate A is the unique winner, and each voter's individual preferences are inverted, then A must not be elected”
- independence of irrelevant alternatives criterion - “the election outcome remains the same even if a candidate who cannot win decides to run”
// 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).
- 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.h struct type definitions struct Person=2 fields:name
(string),favorites
(Favorites
)name
is a non-empty string.favorites
is an instance ofFavorites
, a type which you get to define usingtypedef
.
struct PersonNode=3 fields:value
(struct Person*
),next
(struct PersonNode*
),prev
(struct PersonNode*
)struct Team=3 fields:name
(string),head
(of the linked list of people), andtail
(of the same linked list)FavoritesA type for one person's favorites.- Create using
typedef
. - This could be an alias for
struct PersonNode*
or something else of your choice.
forward declarations forward declarations of all functions in your team.cteam.c functions create team(char✶ name, int population, struct Person✶ people)
→ return type: struct TeamReturn astruct Team
object.
name
is the name of the team and is a non-empty stringpopulation
is the number of people in the team, and is always ≥0.- If
population
is 0 (i.e., empty team), thehead
andtail
must be set toNULL
. people
is an array of sizepopulation
containingstruct Person
objects with theirfavorites
already set.- The resulting
struct Team
object this returns will be on the stack, but everything it refers to—thestruct Person
objects, theirname
attributes, and thestruct PersonNode
objects—will all be on the heap. - This will not call
create_favorites(…)
. Instead, use thefavorites
frompeople
and connect them to the newly createdstruct Person
objects on the heap.
create favorites(struct Person✶ first choice, ...)
→ return type: FavoritesCreate a Favorites object with the specified people in the order be passed.- The returned
Favorites
will become thefavorites
field of thestruct Person
objects created bycreate_team(…)
andadd_person(…)
. - This is only for ⓐ initializing
struct Person
objects passed tocreate_team(…)
and ⓑ callingadd_person(…)
. - Any memory allocated by this function must be freed by your
free_person(…)
and/orfree_team(…)
(not yourmain(…)
, for example). - The last argument must be
NULL
.
create test team()
→ return type: struct TeamCreate astruct Team
with at least 4 people (struct Person
object) for use in testing.- limit: 2 statements
- The first statement will create an array of ≥4
struct Person
objects. - The second statement will then pass that array to your
create_team(…)
to create a newstruct Team
object. - You may use the example in Q11 as a starting point, as long as you understand it.
copy team(struct Team✶ original)
→ return type: struct TeamCreate a deep copy of astruct Team
.- The copy should not refer to any of the same memory as the original team.
- Hint:
copy_team(…)
can be as little as 6 lines, using the_connect_all_favorites(…)
suggested in Q16. - You do not need to support copying teams with favorites that are not members (unless your code uses your
copy_team(…)
in a way that requires this).
add favorite(struct Person✶ fan, struct Person✶ favorite, int rank)
→ return type: voidAddfave
tofan
's favorites at the specified rank.rank
is 0-based.- A negative rank indicates the position relative to fan's last choice.
- This may only be called with 0 ≤ |
rank
| ≤ number offan
's favorites so far. - Examples: Call with rank=0 to set the person's top choice, with rank=1 to set their second choice, rank=-1 to set their last choice, rank=-2 to set their second to last choice, and so on.
add person(struct Team✶ team, char✶ name, Favorites favorites)
→ return type: struct Person✶Add a struct Person to the end of the team.name
is a non-empty string.- You may assume all of the person's favorites are already in the team.
- This must copy the name to the heap; you can use
_strdup(…)
if you like - Hint: Your
find_person(…)
might come in handy.
pick leader(struct Team✶ team)
→ return type: struct Person✶Return the person who is winner using the instant-runoff method of voting.- A candidate is the winner if they get greater than 50% of the votes in a given round.
- If all of a person's favorites have been eliminated (or are non-members), then the person does not vote.
- If all candidates are eliminated (i.e., unbreakable tie), return
NULL
. - Example: if A's favorites are {A, B}, B's favorite is {B}, C's favorite is {C}, and D has no favorites ({}), then A, B, and C will be eliminated as candidates in round 1. pick_leader(…) should return NULL.
- The winner is chosen only from current team members.
- Non-members (e.g., detached but still in a member's favorites) are treated as eliminated from the start.
pick_leader(…)
must not modify the team or any data that it refers to (directly or indirectly).- Hint: there are many reasonable solutions, but you may find arrays more helpful than linked lists.
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.fprint team(struct Team✶ team, FILE✶ stream)
→ return type: voidprint the team'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)
- Use
fprintf(stream, …)
in this function. (See Q19.) - When you test in your
main(…)
, test withfprint_team(&team, stdout)
. - Use spaces, not tabs.
- Exactly one space should separate the end of the longest name (e.g., "Milt Jackson") and "(favorite: …)".
- Print only the #1 favorite of each person, not the full list of favorites.
- Each line (including the last line), ends with "\n". Additional spaces before the "\n" are not allowed.
- Display members in the order they were added to the team.
- If there is no leader—i.e.,
pick_leader(…)
returned NULL—print (none) in place of the leader, like this:Small Team - leader: (none) - members: Taukelina (favorite: Apisai) Apisai (favorite: Taukelina)
. - If a person does not have any favorites, print none in place of their favorite, like this:
Another Small Team - leader: Monise - members: Monise (favorite: none) Otinielu (favorite: Monise)
. - If the team has no members, print (none) in place of the first member and leader, like this:
Some Empty Team - leader: (none) - members: (none)
- This specification is precise. Your output should match exactly.
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 beforemain(…)
ends.
free person(struct Person✶ person)
→ return type: voidFree thestruct Person object
and all heap memory that it is responsible for.- This should free the person's
name
andfavorites
. - Do not attempt to free the
struct Person
objects referred to by this person'sfavorites
.
free team(struct Team✶ team)
→ return type: voidFree heap memory referred to by the team and set itsname
,head
, andtail
toNULL
.- This will free the team name and all current team members, including the associated
struct Person
,struct PersonNode
, andFavorites
objects and each person'sname
. - Do not attempt to free the
struct Team
object itself; assume it is on the stack of the caller. - Do not attempt to free former team members, even if they are referenced as favorites of current members.
- Example: If Azuma were detached from the team, Azuma might still be included as a favorite of many team members, but calling
free_team(…)
should not free Azuma.
test_team.c functions main(int argc, char✶ argv[])
→ return type: intTest all of the code in your team.c.expected.txt test output Expected output from running test_team.c. -
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
stdio.h fprintf
,stdout
,FILE
team.c
,test_team.c
stdarg.h va_arg
,va_list
,va_copy
,va_start
,va_end
team.c
,team.h
stdio.h printf
test_team.c
stdlib.h malloc
,free
,NULL
,EXIT_SUCCESS
,EXIT_FAILURE
team.c
,test_team.c
string.h strlen
,strcmp
,strcpy
team.c
,test_team.c
assert.h assert
team.c
,test_team.c
- All data referenced by a
struct Team
object must be on the heap. That includes allstruct Person
objects, their names, and the team name. Thestruct 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.
- The
struct Person
,struct PersonNode
, andstruct Team
types 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
Favorites
type be?
It is your choice. One option is to makeFavorites
an alias forstruct 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 yourFavorites
type contains.
If you are completely confused, it may help to review howtypedef
works. Remeber that your team.h will contain exactly 4 type definitions. When referring to yourFavorites
type elsewhere, you will not use thestruct
keyword before it. See the function signature foradd_person(…)
, for example. -
Why is
create_favorites(…)
specified as a variadic function? Why not just pass an array?
This makes yourcreate_test_team(…)
a lot cleaner and shorter, and allows us to keep the requirement of two lines increate_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
Favorites
for anything else?
No. -
Can the same
struct Person
object 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 Person
objects passed (by address) tocreate_favorites(…)
will still exist whencreate_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 yourcreate_favorites(…)
create the container (e.g., a linked list) to hold thestruct Person
objects that are passed to it. However, it will not allocate memory for thestruct Person
objects themselves. -
Can I allocate the
struct Person
objects in mycreate_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 samestruct Person
obhject. Therefore, it will need to be created outsidecreate_favorites(…)
. You will do this from yourcreate_team(…)
.
This wouldn't work at all with yourcreate_test_team(…)
because it needs to be 2 statements. It is possible to pass the address of an element ofpeople
tocreate_favorites(…)
, even within the initialization ofpeople
, ifcreate_favorites(…)
tries to access that memory, it will result in an error because at the timecreate_favorites(…)
is called,people
hasn't been initialized, yet. -
Should I use
add_favorite(…)
in mycreate_favorites(…)
?
You may if you like, but it probably won't be useful. -
Should I use
create_favorites(…)
in mycreate_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 yourcreate_test_team(…)
but it could easily be done from yourmain(…)
. Just create astruct Person
object (most likely on the stack) and then, in a separate statement, pass it tocreate_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 toprintf(…)
. For now, that's all you really need to know. For those who are curious,fprintf(…)
is a more general version ofprintf(…)
that also allows printing to files, for example. We will study files later in this semester. We are usingfprintf(…)
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.Round 1 Azuma's favorites: Baba, Doko Baba's favorites: Edo, Doko Doko's favorites: Yoshio, AzumaEdo's favorites: Doko, Azuma Azuma, Baba, Edo, and Do are all eliminated.Round 2 Azuma's favorites: Baba,DokoBaba's favorites: Edo,DokoDoko's favorites: Yoshio,AzumaEdo's favorites: Doko,AzumaThere 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:Round 1 Azuma's favorites: Baba Baba's favorites: Fujita Doko's favorites: Edo, Azuma Edo's favorites: Doko, Azuma Fujita's favorites: Doko, Azuma Baba, Edo, and Fujita get 1 vote and will be eliminated. Azuma gets 0 votes and will also be eliminated.Round 2 Azuma's favorites: BabaBaba's favorites: FujitaDoko's favorites: Edo,AzumaEdo's favorites: Doko, AzumaFujita's favorites: Doko, AzumaDoko wins with 2 votes (100% of the 2 votes).
The HW08 Q&A has more answers about topics such asassert(…)
,add_person(…)
anddetach_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