” CMPSCI 187程序 写作、 辅导Java课程设计程序、Java程序CMPSCI 187 (Sec 02) / Fall 2020Implementing Sets Using Linked ListsCMPSCI 187 (Sec 02) / Fall 2020 Implementing Sets Using Linked ListsContentsOverview 3Learning Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3General Information [Common] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3Problem 1 4Review of the Concept of Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4Immutability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4Generics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4Iterators and the Iterable Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5Import Project into Eclipse [Common] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6Starter Code and Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6Useful Tips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7Export and Submit [Common] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7Page 2 of 7CMPSCI 187 (Sec 02) / Fall 2020 Implementing Sets Using Linked ListsOverviewIn this assignment you will build a class to represent a set; as in the mathematical concept of a set, a collection that hasno duplicates. The class will be immutable (more later), generic, and will use Iterators. It will be implementedwith 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 anynew classes or interfaces.CMPSCI 187作业 写作、 辅导Java课程设计作业、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 ofthe 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 whatconstitutes academic dishonesty you should re-read the course policies. We assume you have read the course policiesin 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 beplaced in the provided src directory of your Eclipse project. When submitting your project, be sure to remove all compilation errors. Any compilation errors will causethe 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 certainaspect of your program, such as does it generate the expected output for a given input. We recommend you run thetests often and use them as starting points to test your project. In addition, some of the java files come with their ownmain 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 yourproject. 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. Manymethods 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 outthe 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 7CMPSCI 187 (Sec 02) / Fall 2020 Implementing Sets Using Linked ListsProblem 1Review of the Concept of Sets(This is just a simple review. To find out more, visit https://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, forinclusion, and for equality. These are illustrated below:Given:A = {a, b, c, d, e}, B = {c, a}, C = {3, 1, 4, 5, 9}thena 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 BB C = {3, 1, c, a, 4, 9, 5} set union, include all elements from both setsA A = A sets dont have duplicatesA B = B A = B set intersection, those elements that are elements of both setsA C = set intersection with no common elements gives the empty setA B = {b, d, e} set difference, those elements in A but not in BWe will be implementing all of these operations on our sets.ImmutabilitySome classes represent immutable objects, i.e., objects whose state cannot be changed. You are already familiar withat least one such class, the String class. Instances of that class cannot be changed in any way. If you look carefullyyou will notice That any String method that could be construed as changing the String actually returns a newString; the original is unchanged. Other immutable classes include Boolean, Integer, and Float. Immutableobjects 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 oneto change an instance, they only return new instances. Your implementation of the Set interface must maintain thatimmutability. Once an instance is created it never changes.GenericsIn class we covered generics, which provides a convenient way to create a family of classes by parametrizing thedata type. For example, you have learned to define LLStringNode and LLIntegerNode, which are linked listnodes that store string and integer data respectively. What if you need to define other types of linked list nodes thatstore other types of data, including custom data types such as Apple and Dog? Generics allows you to define theentire family of such classes by replacing the specific data types with type variables. Figure 1 shows three differentclasses, LLStringNode, LLDogNode, and LLNodeT, the last being a generic class. For simplicity we omittedthe method bodies to Highlight the differences in data types. Figure 2 shows typical uses of the LLNodeT class.Problem 1 continued on next page. . . Page 4 of 7CMPSCI 187 (Sec 02) / Fall 2020 Implementing Sets Using Linked Lists Problem 1 (continued)1 class LLStringNode {2 String info;3 LLStringNode link;45 LLStringNode(String s){6 info = s;7 link = null;8 }910 String getInfo();1112 LLStringNode getLink();1314 void SetInfo(String info);1516 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 LLNodeT {T info;LLNodeT link;LLNode(T data) {info = data;link = null;}T getInfo();LLNodeT getLink();void setInfo(T info);void setLink(LLNodeT link);}Figure 1: Definitions of LLStringNode, LLDogNode, and LLNode classes.1 LLNodeDog DogNode = new LLNodeDog(dog1);2 dogNode.setInfo(dog2);3 dogNode.setLink(new LLNodeDog(dog3));4 Dog dog = dogNode.getInfo(); // dog == dog256 LLNodeString sNode = new LLNodeString(abc);7 sNode.setInfo(xyz);8 sNode.setLink(new LLNodeString(xyz));9 String s = sNode.getInfo(); // s == xyzFigure 2: Using the LLNode class.The major change is the inclusion of T in the LLNode definition. This declares that LLNode is generic, andhas a type variable named T. When you use the LLNodeT class, for instance by using LLNodeString, youare specifying That you want a version of LLNode created by replacing the type variable with a specific data typeStrings. Thus LLNodeString together becomes the name of the class. It is perfectly possible, as Figure 2shows, to have several different instantiations of the generic class.Iterators and the Iterable InterfaceIn class we have also covered the IteratorT and IterableT interfaces. An iterator is a object that allowsyou to visit the elements of some collection one-by-one. For example, if array is an instance of a class thatimplements the IterableT interface, you can use the following code to visit every element in it one-by-one:1 IteratorType 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 IterableT interface specifies only one method, the IteratorT iterator() method, which returnsan iterator object for the collection. This iterator object must belong to a class that implements the IteratorTProblem 1 continued on next page. . . Page 5 of 7CMPSCI 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 anUnsupportedOperationException to indicate that this operation is not supported (because our set representsan 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 notrename this project as its name is used during the autograding process. If the project is renamed, your assignment willnot 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 thisfolder (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). Youmust not change or add anything in this folder. To help ensure that, we suggest that you set the support folderto be read-only. You can do this by right-clicking on it in the package explorer, choosing Properties from themenu, choosing Resource from the list on the left of the pop-up Properties window, unchecking the Permissionscheck-box for Owner-Write, and clicking the OK button. A dialog box will show with the title Confirm recursivechanges, 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 TestsRequirements: for this project, you must implement linked list on your own. You may NOT use Java array of anytype, nor any Java class that implements the Collection interface (e.g. ArrayList, Vector etc.). The list of theseclasses is included in the API documentation, available at: httpss://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, asit defines exactly what your implementation must do. You will also find LinkedNode.java, which defines theLinkedNode class. It is an immutable, generic class, and is a generalization of the LLxxxNode classes you haveseen 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 requireyour 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 implementationas required in order to Pass the tests.Problem 1 continued on next page. . . Page 6 of 7CMPSCI 187 (Sec 02) / Fall 2020 Implementing Sets Using Linked Lists Problem 1 (continued)The version of LinkedSetE we have given you has one attribute, head, which is intended to be the head ofa linked list of elements in the set. It also has three constructors; two public, one which creates an empty set, andthe other of which creates a set containing a single element; and one private which creates a set from a linked listof LinkedNodeEs. This last constructor is the one that you will call from your methods to create the newLinkedSet object to be returned. There are ten methods that you will need to supply implementations for. Wesuggest that you start by implementing the iterator method; because many of the other methods can use it to goodeffect; for an example see the hashCode() method.To implement the iterator method you will need to finish the LinkedNodeIteratorT class. This classhas two methods you will need to complete, hasNext() and next(). You will also need to choose appropriatedata variables and build An appropriate constructor. If you remember that you are iterating over a linked list ofLinkedNodes 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 firstLinkedNode in the list; Once you have completed LinkedNodeIteratorT and the iterator() method, you can use it (in theform 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 youve already written when implementing new method.For example, you can easily implement isSuperset by using isSubset.TestingWe provide public JUnit tests (in LinkedSetPublicTest.java) you should use to test your implementation. Feelfree to write additional tests yourself to make sure your code runs as expected. For full credit, you must correctlyimplement each method in LinkedSet.java and LinkedNodeIterator.java. Make sure that you have doneeverything 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 thewindow that appears, under General choose Archive File. Then choose Next and enter a destination for the outputfile. Be sure that the project is named sets-student (otherwise you may be exporting the wrong project!). Savethe 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 coursewebsite and/or documentation Explaining how to use the online autograder. If you have any questions please beprompt in asking the course staff before it is too late to submit your solution. If you encounter any errors that look likethe autograder failed and not your project, please let the instructors know.Page 7 of 7如有需要，请加QQ：99515681 或邮箱：99515681@qq.com
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
