python代写 CSI213 Data Structures

COLLEGE OF ENGINEERING AND APPLIED SCIENCES DEPARTMENT OF COMPUTER SCIENCE
Fall 2018 – CSI213 Data Structures

Project 2
Instructions:
1. All projects are individual projects unless it is notified otherwise.

If one of the following is true, no credits will be given:

• The project is late.
• The class design is missing.
• Wrong files are submitted or part of the source codes is submitted.
• The project has errors.
• The comments are not completely written in Javadoc format.
• The project is a copy and modification of another student’s project. (Both will

  receive 0.)

• The project is copied from internet or other resource.

2. All projects must be submitted via email on time. No late projects will be accepted. Documents:

UML class diagram(s)
Java source file(s)
Supporting files if any (For example, files containing all testing data)

Emails:
ZR170102: Email Ms. Lin and me

lilin1@cqupt.edu.cn

qwang3@albany.edu ZR170304: Email Mr. Jiangping and me

huangjp@cqupt.edu.cn qwang3@albany.edu

Due:
ZR170102: 11/02/2018 ZR170304: 11/02/2018

1

Software Development General Project Rubric: Analysis:

•   Does the software meet the exact specification?
•   Does each class include all corresponding data and functionalities?

  Design:

•   Is the design (in UML class diagram(s)) efficient?

  Code:

•   Are there errors in the software?
•   Are code conventions and name conventions followed?
•   Does the software use the minimum computer resource (computer memory and processing time)?
•   Is the software reusable?

  Debug:

 Are there bugs in the software?
Documentation: There will be no credit if comments are not included.

•   More inline comments must be included in either single line format or block format inside each method body.
•   All comments must be complete in correct format.
  The following contains additional information on coding conventions and Javadoc. The project

  description starts on page 5.

  A Java source file can contain a class. Each class is made up of the following components:

  Inside a class,

•   package statement
•   import statements if any
•   Javadoc class comments
•   a class header and its body. The open {of a class body must be at the end of the header. Inside a class body,

•   instance/static variables with Javadoc comments above each variable
•   instance/static methods with Javadoc comments above each method header. The open { of a method

  body must be at the end of the header

  Inside a method body,

 more comments are included in each method body. These comments can be written in single line or block format.

Readability:

To enforce program readability, consistent indentations must be used to show containment hierarchy. Readability is very important. Poor readability of a source file will be ignored or misinterpreted. This will definitely affect a software developer’s performance. Please read the following, and careful exam your source file.

1. Align Javadoc comments with its source codes.
2. Use consistent indentations to enhance readability:

 Class comments must be written in Javadoc format before a class header.

 Method comments must be written in Javadoc format before a method header.

 Javadoc comments must be written before each instance/static variable.

2

•   Indent each instance/static variable of a class.
•   Indent each method of a class.
•   Indent each statements in a block statement or a method.

3. Use required spaces, not excess spaces to enhance readability:

•   No spaces between comments and the corresponding method header.
•   One space after * at the beginning of each line in Javadoc comments.
•   Align first * of each line in Javadoc comments.
•   One line in between two sections of codes is needed.

  Comments are required almost everywhere in a source file. Double check to make sure they are completed in the required formats. Code conventions must be followed.

package dog;

import java.util.Random;

/**
 * Representing a dog with a name.
 * @author Qi Wang
 * @version 1.0
 */

package statement is required.

import statements if any

public class Dog{ /**

open {

TAB

TAB

/**
* Constructs a newly created Dog object with * @param name The name of this dog
*/

public Dog(String name){ this.name = name;

}

      /**
       * Returns the name of this dog.
       * @return The name of this dog
       */

public String getName(){ return this.name;

}

      /**
       * Changes the name of this dog.
       * @param name The name of this dog
       */

public void setName(String name){ this.name = name;

}

      /**
       * Returns a string representation of this dog. The returned string contains the type of

        * this dog and the name of this dog.
       * @return A string representation of this dog
       */

 * The name of this dog

*/

private String name;

required

/**
 * Constructs a newly created Dog object that represents a dog with an empty name.
 */

public Dog(){

open {

TAB

TAB

this(“”);

}

3

public String toString(){
return this.getClass().getSimpleName() + “: ” + this.name;

}

/**
 * Indicates if this dog is "equal to" some other object. If the other object is a dog,
 * this dog is equal to the other dog if they have the same names. If the other object is
 * not a dog, this dog is not equal to the other object.
 * @param obj A reference to some other object
 * @return A boolean value specifying if this dog is equal to some other object
 */

public boolean equals(Object obj){
//The specific object isn’t a dog. if(!(obj instanceof Dog)){

return false;

}

      //The specific object is a dog.

Dog other = (Dog)obj;
return this.name.equalsIgnoreCase(other.name);

} }

More inline comments can be included in single line or block comments format in a method.

4

Project 2 ADT Character String What to submit?

•   All source files
•   UML class diagram(s)
•   Supporting files if any (For example, files containing all testing data)

  Implement the ADT character string type, LinkedString , as another implementation of class String in Java. A doubly linked list must be used to store a list of characters (there is ONLY one external reference, head, to the linked list). This class must be implemented as an immutable class as class String.

  In Java, String is an immutable object (its internal states, such as data structures, cannot be changed once it’s created). Immutable means that once the constructor for an object has completed execution that instance can’t be altered. This is useful as it means you can pass references to the object around, without worrying that someone else is going to change its contents. Any method that is invoked which seems to modify the value, will actually create another String. Your LinkedString class must be immutable as well. For example, three String objects, a, b, and ab, are involved in the following code segment.

           String a = new String(“AA”);
           String b = new String(“BB”);
           String ab = a.concat(b);
  

After String

After String

a = new

a

b = new

String(“AA”);

“AA”

String(“BB”);

“BB”

is executed, a new String object a is created.

is executed, another new String object b is created.

b

After String ab = a.concat(b);is executed, another new String object ab is created. String a(this string) and String b( a string passed into method concat) are not changed due to String immutability. Method concat simply copies the contents of both a and b, and use them to make a new string object.

ab

“AABB”

The LinkedString class uses a different data structure, a doubly linked list. This data structure is LinkedString ‘s internal state. An immutable LinkedString object means its linked list can’t be altered once the object is created. All characteristics and behaviors of LinkedString objects must be the same as String objects. When a LinkedString object calls a method, this LinkedString object and LinkedString object(s) passed into this method must be unchanged during invocation of this method. If the method returns a LinkedString object, a new LinkedString object must be made without changing this LinkedString object and other LinkedString existing objects. The following shows how object immutability can be enforced when implementing method concat.

5

For example, three LinkedString objects, a, b, and ab, are involved in the following code segment. LinkedString a = new LinkedString (“AA”);
LinkedString b = new LinkedString (“BB”);
LinkedString ab = a.concat(b);

After LinkedString a = new LinkedString(“AA”);is executed, a new LinkedString object a is created with all characters stored in a linked list.

null

head

d

with all characters stored in a linked list.

null

head

d

null

a
After LinkedString b = new LinkedString(“BB”);is executed, another new LinkedString object b is created

null

b

After LinkedString ab = a.concat(b);is executed, another new LinkedString object ab is created with all characters stored in a linked list.

null

head

d

null

ab

Method concat must be implemented in a way in which a new linked string is made without modifying this linked string a and the other linked string b to enforce object immutability. In order to do this, method concat can simply copy characters in order like this.

null

head

d

null

head

null null

head

d

copy

null

a

ab

b

copy copy

copy

null

d

6

Modifying like this would violates object immutability.

null

head

d

null null

head

d

null

a

ab

b

Carefully implement each method, and make sure object immutability is maintained. Otherwise, the project will be returned with no credits.

ADT Character String Specification:

Specify operations to (DON’T change the names of the operations.) Three overloading constructors:

•   create an empty LinkedString instance.
  A new character linked list is allocated so that it represents the sequence of 0 characters currently contained in the character list argument. (LinkedString()).
•   create a LinkedString instance containing a sequence of characters.
  A new character linked list is allocated so that it represents the sequence of characters currently contained in the character list argument. (LinkedString(char[])).
•   create a LinkedString instance containing same sequence of characters as a String instance.
  A new character linked list is initialized so that it represents the same sequence of characters as the String argument (LinkedString(String)).

  Other methods (MUST be implemented to enforce object immutability):

•   return the char value at the specified index. The first character in this linked character string is in position zero. (char charAt(int)). Note: This linked string must be kept immutable.
•   concatenate the specified linked character string to the end of this linked character string (LinkedString concat(LinkedString)). Note: This linked string and the specified linked string must be kept immutable.
•   returns true if, and only if, length() is 0. (boolean isEmpty()). Note: This linked string must be kept immutable.
•   return the length of this linked character string (int length()). Note: This linked string must be kept immutable.
•   return a new linked character string that is a substring of this linked character string (LinkedString substring(int, int)). Note: This linked string must be kept immutable.

  ADT Character String Design:

  Complete a UML diagram to include all classes that are needed to meet the specifications. An interface class is usually defined to include all operations. A class implementing this interface provides implementation details Exceptions should to be considered when operations are designed.

  ADT Character String Reference-based Implementation:

7

Implement all classes included the design. Javadoc comments should be included during this activity. Data structure doubly linked list must be used to store a sequence of characters in LinkedString objects. All characters should be linked each other. Implement LinkedString so that it is consistent with the String class. A LinkedString object must be an immutable object.

ADT Character String Test/Debug:

Note: It is required to store all testing data in a file. No credit will be given if not.
It is required to use decomposition design technique. No credit will be given if not.

To test LinkedString design, all operations in the design must be tested. This can be done as follows:

}



 







Create an array list of LinkesString objects using testing data stored in a text file, and check emptiness of all linked strings.
Display all linked strings and their lengths in the array list.
Retrieve the last character or mid character of each LinkedString object from the array list, and display them. Display all linked strings in the array list again to make sure that all objects are not changed.

Concatenate a linked string with next linked string, and display the concatenated string, repeat for the entire array list. Display all linked strings in the array list again to make sure that all objects are not changed.
Get sub strings and display both substrings and original strings.
Test other methods.

It is not
should invoke a method (start) that is decomposed into more methods (createList, displayList,…) in a separate class. Every method should be designed as a single-minded method. For example, Class LinkedStringTest contains method main; class LinkedStringUtility is a helper class. Both classes are used for testing purposes.

public class LinkedStringTest{

public static void main(String[] args){ LinkedStringUtility.start();

}

Note: This class shows only two methods. You must design/implement the rest of the class.

public class LinkedStringUtility {

/**
* Creates a list of LinkedString objects and operates on them. */

public static void start(){

} }

efficient to let main to do all. Method main should be very small and should be the only method in the class. It

ArrayList<LinkedString> stringList = new LinkedString<LinkedString>(); /**

* Create an array list of LinkesString objects using testing data * stored in a text file.
*/

… createList(…);

/**
 * Display all linked strings in the array list.
 */

… displayList(…);
//The rest of the testing methods must be completed by yourself.

8

ADT Character String Documentation:

Check the entire project, and complete /revise Javadoc comments if needed. Class comments must be included right above the corresponding class header. Method comments must be included right above the corresponding a method header. All comments must be written in Javadoc format. There will be no credits if comments are not complete, and/or not written in Javadoc format.

9