Set difference
Back to JHAVEPOP exercises
Linked list representation of a set
For this exercise, each set is represented by a linked list. A
set is a collection of elements (in this case, characters) that
never contains more than one occurrence of each element. Even though a
linked list imposes an order on its elements, this order is not
relevant when the collection is treated as a set. Therefore, the
linked lists in this exercise are not ordered in any way. For example,
the set {1, 2} may be represented with the linked list 1 -> 2, or
by the linked list 2 -> 1. An empty linked list represents the
empty set.
Problem statement
Write a C++ program that, given two sets s1 and s2, modifies s1 to
represent the difference s1 - s2 and leaves s2 unchanged, where
the difference s1 - s2 of two sets s1 and s2 is the set
containing all the elements of s1 except those that are also in s2.
As shown in the test cases below, your code may assume that the two
sets s1 and s2 are given as linked lists and that three additional
pointers p1, p2, and prev1 are declared. For this exercise, you may
not declare any additional pointers.
Make sure that your code works with all possible sets. The following
10 test cases are provided to help you test your code.
Test case #1
Description: s1 is the empty set.
Initial setup:
Final configuration:
Ready to test your program?
Test case #2
Description: s2 is the empty set.
Initial setup:
Final configuration:
Ready to test your program?
Test case #3
Description: Both sets s1 and s2 are empty.
Initial setup:
Final configuration:
Ready to test your program?
Test case #4
Description: Set s1 contains only one element that is also in
s2.
Initial setup:
Final configuration:
Ready to test your program?
Test case #5
Description: Set s1 contains only one element that is not in s2.
Initial setup:
Final configuration:
Ready to test your program?
Test case #6
Description: Sets s1 and s2 have no elements in common; that
is, the difference is the set s1 itself.
Initial setup:
Final configuration:
Ready to test your program?
Test case #7
Description: The sets s1 and s2 are equal.
Initial setup:
Final configuration:
Ready to test your program?
Test case #8
Description: The last element in set s1 is in the difference but its first element is not.
Initial setup:
Final configuration:
Ready to test your program?
Test case #9
Description: The first element in set s1 is in the difference but its last element is not.
Initial setup:
Final configuration:
Ready to test your program?
Test case #10
Description: Random general case.
Initial setup:
Final configuration:
Ready to test your program?
Back to JHAVEPOP exercises
