CMPSCI 187代做、代写Java设计、Java程序语言调试

日期：2020-09-17 11:02

CMPSCI 187 (Sec 02) / Fall 2020

Implementing Sets Using Linked Lists

CMPSCI 187 (Sec 02) / Fall 2020 Implementing Sets Using Linked Lists

Contents

Overview 3

Learning Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

General Information [Common] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

Problem 1 4

Review of the Concept of Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Immutability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Generics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Iterators and the Iterable Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Import Project into Eclipse [Common] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Starter Code and Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Useful Tips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

Export and Submit [Common] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

Page 2 of 7

CMPSCI 187 (Sec 02) / Fall 2020 Implementing Sets Using Linked Lists

Overview

In this assignment you will build a class to represent a set; as in the mathematical concept of a set, a collection that has

no duplicates. The class will be immutable (more later), generic, and will use Iterators. It will be implemented

with linked lists. We will give you (in the support directory) the Set interface, and the LinkedNode class, and

(in the src directory) skeletons for the LinkedSet and LinkedNodeIterator classes which you will complete.

You will be starting from initial code provided to you, and adding to and modifying it. You should NOT create any

new classes or interfaces.

Learning Goals

? Continue to exercise your understanding of linked lists.

? Introduce the concept of generics and iterators.

? Show ability to write a class that implements a given interface, and read specifications in a Java interface.

? Continue to practice using JUnit tests and Java debugging tools.

Note: sections marked [Common] below are shared among all projects. We include them here for the completeness of

the description, but they present the same information across all projects.

General Information [Common]

Reminder: Copying partial or whole solutions, obtained from other students or elsewhere, is academic dishonesty.

Do not share your code with your classmates, and do not use your classmates’ code. If you are confused about what

constitutes academic dishonesty you should re-read the course policies. We assume you have read the course policies

in detail and by submitting this project you have provided your virtual signature in agreement with these policies.

? For some projects, it may be useful for you to write additional java files. Any java file you write MUST be

placed in the provided src directory of your Eclipse project.

? When submitting your project, be sure to remove all compilation errors. Any compilation errors will cause

the autograder to fail to run, and consequently you will receive a zero for your submission. No Exceptions!

In the test directory, we provide several JUnit tests that we refer to as the public tests. Each test checks a certain

aspect of your program, such as does it generate the expected output for a given input. We recommend you run the

tests often and use them as starting points to test your project. In addition, some of the java files come with their own

main functions. You can run them as Java applications to interact with the project.

Be aware that the autograder will use a more comprehensive set of tests (referred to as private tests) to grade your

project. These tests are hidden from you. We recommend that you actively think about your own test (by adding new

@Test) cases to your public test files to help you debug the program. In particular, you should consider:

? Do your methods handle edge cases such as integer arguments that may be positive, negative, or zero. Many

methods only accept arguments that are in a particular range.

? Does your code handle cases such as when an array or list is empty, or has reached full capacity?

More complex tests will be project-specific. To build good test cases, think about ways to exercise methods. Work out

the correct result for a call of a method with a given set of parameters by hand, then add it as a test case.

Page 3 of 7

CMPSCI 187 (Sec 02) / Fall 2020 Implementing Sets Using Linked Lists

Problem 1

Review of the Concept of Sets

(This is just a simple review. To find out more, visit http://en.wikipedia.org/wiki/Set_(mathematics).)

Mathematically, a set Q represents a collection of distinct elements. For example:

Q = {a, b, c, d, e}

is a set with five elements: a, b, c, d, and e. Note that the elements are unordered, so the following sets are the same:

{a, b, c, d, e} = {a, e, c, b, d} = {c, b, e, d, a} = . . .

There are various operations on sets, such as the union, intersection, difference; as well as tests for membership, for

inclusion, and for equality. These are illustrated below:

Given:

A = {a, b, c, d, e}, B = {c, a}, C = {3, 1, 4, 5, 9}

then

a ∈ A membership (i.e. a is an element of A)

B ? A subset (i.e. B is a subset of A)

A ? B A is a superset of B

B ∪ C = {3, 1, c, a, 4, 9, 5} set union, include all elements from both sets

A ∪ A = A sets don’t have duplicates

A ∩ B = B ∩ A = B set intersection, those elements that are elements of both sets

A ∩ C = ? set intersection with no common elements gives the empty set

A ? B = {b, d, e} set difference, those elements in A but not in B

We will be implementing all of these operations on our sets.

Immutability

Some classes represent immutable objects, i.e., objects whose state cannot be changed. You are already familiar with

at least one such class, the String class. Instances of that class cannot be changed in any way. If you look carefully

you will notice that any String method that could be construed as changing the String actually returns a new

String; the original is unchanged. Other immutable classes include Boolean, Integer, and Float. Immutable

objects have some nice properties, such as they are much safer to use in a multi-threaded environment.

The Set interface described in this project specifies an immutable class. Note that none of the methods allows one

to change an instance, they only return new instances. Your implementation of the Set interface must maintain that

immutability. Once an instance is created it never changes.

Generics

In class we covered generics, which provides a convenient way to create a family of classes by parametrizing the

data type. For example, you have learned to define LLStringNode and LLIntegerNode, which are linked list

nodes that store string and integer data respectively. What if you need to define other types of linked list nodes that

store other types of data, including custom data types such as Apple and Dog? Generics allows you to define the

entire family of such classes by replacing the specific data types with type variables. Figure 1 shows three different

classes, LLStringNode, LLDogNode, and LLNode<T>, the last being a generic class. For simplicity we omitted

the method bodies to highlight the differences in data types. Figure 2 shows typical uses of the LLNode<T> class.

Problem 1 continued on next page. . . Page 4 of 7

CMPSCI 187 (Sec 02) / Fall 2020 Implementing Sets Using Linked Lists Problem 1 (continued)

1 class LLStringNode {

2 String info;

3 LLStringNode link;

4

5 LLStringNode(String s){

6 info = s;

7 link = null;

8 }

9

10 String getInfo();

11

12 LLStringNode getLink();

13

14 void setInfo(String info);

15

16 void setLink(

17 LLStringNode link);

18 }

class LLDogNode {

Dog info;

LLDogNode link;

LLDogNode(Dog d){

info = d;

link = null;

}

Dog getInfo();

LLDogNode getLink();

void setInfo(Dog info);

void setLink(

LLDogNode link);

}

class LLNode<T> {

T info;

LLNode<T> link;

LLNode(T data) {

info = data;

link = null;

}

T getInfo();

LLNode<T> getLink();

void setInfo(T info);

void setLink(

LLNode<T> link);

}

Figure 1: Definitions of LLStringNode, LLDogNode, and LLNode classes.

1 LLNode<Dog> dogNode = new LLNode<Dog>(dog1);

2 dogNode.setInfo(dog2);

3 dogNode.setLink(new LLNode<Dog>(dog3));

4 Dog dog = dogNode.getInfo(); // dog == dog2

5

6 LLNode<String> sNode = new LLNode<String>("abc");

7 sNode.setInfo("xyz");

8 sNode.setLink(new LLNode<String>("xyz"));

9 String s = sNode.getInfo(); // s == "xyz"

Figure 2: Using the LLNode class.

The major change is the inclusion of <T> in the LLNode definition. This declares that LLNode is generic, and

has a type variable named T. When you use the LLNode<T> class, for instance by using LLNode<String>, you

are specifying that you want a version of LLNode created by replacing the type variable with a specific data type

Strings. Thus LLNode<String> together becomes the name of the class. It is perfectly possible, as Figure 2

shows, to have several different instantiations of the generic class.

Iterators and the Iterable Interface

In class we have also covered the Iterator<T> and Iterable<T> interfaces. An iterator is a object that allows

you to visit the elements of some collection one-by-one. For example, if array is an instance of a class that

implements the Iterable<T> interface, you can use the following code to visit every element in it one-by-one:

1 Iterator<Type> iter = array.iterator();

2 while (iter.hasNext()) {

3 Type variable = iter.next();

4 ...

5 }

You can make it even simpler by using the following special for loop:

1 for (Type variable : array) { ... }

The Iterable<T> interface specifies only one method, the Iterator<T> iterator() method, which returns

an iterator object for the collection. This iterator object must belong to a class that implements the Iterator<T>

Problem 1 continued on next page. . . Page 5 of 7

CMPSCI 187 (Sec 02) / Fall 2020 Implementing Sets Using Linked Lists Problem 1 (continued)

interface, which requires implementing three methods: boolean hasNext(), T next(), and void remove

(). For our purposes we are going to ignore the remove() method. The definition you are given will simply throw an

UnsupportedOperationException to indicate that this operation is not supported (because our set represents

an immutable collection).

Import Project into Eclipse [Common]

Begin by downloading the starter project and importing it into your workspace. It is very important that you do not

rename this project as its name is used during the autograding process. If the project is renamed, your assignment will

not be graded, and you will receive a zero.

The imported project may have some compilation errors, but these should not prevent you from getting started. Specifically,

we may provide JUnit tests for classes that do not yet exist in your code. You can still run the other JUnit tests.

After completing your code, the compilation errors should be gone.

The project should normally contain the following root items:

src This is the source folder where all code you are submitting must go. You can change anything you want in this

folder (unless otherwise specified), you can add new files, etc.

support This folder contains support code that we encourage you to use (and must be used to pass certain tests). You

must not change or add anything in this folder. To help ensure that, we suggest that you set the support folder

to be read-only. You can do this by right-clicking on it in the package explorer, choosing Properties from the

menu, choosing Resource from the list on the left of the pop-up Properties window, unchecking the Permissions

check-box for Owner-Write, and clicking the OK button. A dialog box will show with the title “Confirm recursive

changes”, and you should click on the “Yes” button.

test The test folder where all of the public unit tests are available. You can feel free to add your own tests here.

JUnit 4 A library that is used to run the test programs.

JRE System Library This is what allows Java to run; it is the location of the Java System Libraries.

If you are missing any of the above or if errors are present in the project (other than as specifically described below),

seek help immediately so you can get started on the project right away.

Starter Code and Tests

Requirements: for this project, you must implement linked list on your own. You may NOT use Java array of any

type, nor any Java class that implements the Collection interface (e.g. ArrayList, Vector etc.). The list of these

classes is included in the API documentation, available at: https://docs.oracle.com/javase/8/docs/

api/java/util/Collection.html. The autograder will assign you a grade of 0 if you use any of them. Also,

do NOT create new files as the autograder will ignore any new file you create.

In the support/sets directory you will find Set.java, which defines the Set interface. Read that file closely, as

it defines exactly what your implementation must do. You will also find LinkedNode.java, which defines the

LinkedNode class. It is an immutable, generic class, and is a generalization of the LLxxxNode classes you have

seen before. As with all files in the support directory you must NOT modify either of these files.

In the src directory you will find two files: LinkedSet.java and LinkedNodeIterator.java. Places that require

your work are clearly marked by //TODO. Note that the starter code you receive is NOT a working implementation.

Right at start you may see errors. You can run the tests, but most of which will fail. You must complete the implementation

as required in order to pass the tests.

Problem 1 continued on next page. . . Page 6 of 7

CMPSCI 187 (Sec 02) / Fall 2020 Implementing Sets Using Linked Lists Problem 1 (continued)

The version of LinkedSet<E> we have given you has one attribute, head, which is intended to be the head of

a linked list of elements in the set. It also has three constructors; two public, one which creates an empty set, and

the other of which creates a set containing a single element; and one private which creates a set from a linked list

of LinkedNode<E>s. This last constructor is the one that you will call from your methods to create the new

LinkedSet object to be returned. There are ten methods that you will need to supply implementations for. We

suggest that you start by implementing the iterator method; because many of the other methods can use it to good

effect; for an example see the hashCode() method.

To implement the iterator method you will need to finish the LinkedNodeIterator<T> class. This class

has two methods you will need to complete, hasNext() and next(). You will also need to choose appropriate

data variables and build an appropriate constructor. If you remember that you are iterating over a linked list of

LinkedNodes you should not have too much difficulty with this.

Useful Tips

? Read the Set interface in Set.java carefully, as it specifies exactly what each method is supposed to do

? An appropriate parameter for the constructor of the LinkedNodeIterator class is a reference to the first

LinkedNode in the list;

? Once you have completed LinkedNodeIterator<T> and the iterator() method, you can use it (in the

form of the special for loop) everywhere appropriate, such as the size, contains, isSubset, union,

intersect, subtract methods.

? Similarly, think about how to maximally reuse methods you’ve already written when implementing new method.

For example, you can easily implement isSuperset by using isSubset.

Testing

We provide public JUnit tests (in LinkedSetPublicTest.java) you should use to test your implementation. Feel

free to write additional tests yourself to make sure your code runs as expected. For full credit, you must correctly

implement each method in LinkedSet.java and LinkedNodeIterator.java. Make sure that you have done

everything that is clearly marked by //TODO in those files.

Export and Submit [Common]

When you have completed this project, you should export an archive file containing the entire Java project. To do this,

click on the sets-student project in the package explorer. Then choose “File → Export” from the menu. In the

window that appears, under “General” choose “Archive File”. Then choose “Next” and enter a destination for the output

file. Be sure that the project is named sets-student (otherwise you may be exporting the wrong project!). Save

the exported file with the zip extension.

Once you have the zip file ready, you can submit it to the online autograder (Gradescope). Please see the course

website and/or documentation explaining how to use the online autograder. If you have any questions please be

prompt in asking the course staff before it is too late to submit your solution. If you encounter any errors that look like

the autograder failed and not your project, please let the instructors know.

Page 7 of 7