讲解：JavaIntroduction to AlgorithmsJava

Introduction本次课程主要是讲解c++的课程的算法，这次作业主要是实现BST（二叉搜索树），需要实现树的排序，搜索，建立树，插入元素等操作RequirementProgramming Project 3Introduction to Algorithms,Data Structures, and Program Development0. Introduction.In this programming project, you will write a program called a cross-reference generator that uses binary search trees (BST’s) and linear linked lists. The program reads names from a Java source file, then produces a cross-reference table (also called a concordance table) that shows where each name appears in that file. Cross-reference tables are sometimes used when making paper listings of programs, like those that appear in textbooks. The easiest way to describe a cross-reference table is to show an example. Suppose we have the following Java program. It prints a table of factorials from 0 to 10. Its lines have numbers so we can refer to them later.00001 // FACTORIALS. Print some factorials.0000200003 class Factorials00004 {0000500006 // FACTORIAL. Return the factorial of N.0000700008 private static int factorial(int n)00009 {00010 if (n == 0)00011 {00012 return 1;00013 }00014 else00015 {00016 return n * factorial(n - 1);00017 }00018 }0001900020 // MAIN. Write the factorials of 0 through 10.0002100022 public static void main(String [] args)00023 {00024 for (int k = 0; k 00025 {00026 System.out.println(k + “! = “ + factorial(k));00027 }00028 }00029 }The following is a cross-reference table for the program. It shows all the names in the program. After each name is a list of numbers, showing the lines where that name appears. For example, the table says that the name factorial appears on lines 8, 16, and 26.Factorials 00003String 00022System 00026args 00022class 00003else 00014factorial 00008 00016 00026for 00024if 00010int 00008 00024k 00024 00026main 00022n 00008 00010 00016out 00026println 00026private 00008public 00022return 00012 00016static 00008 00022void 00022Here are some things to notice about the cross-reference table.•Lines are numbered starting from 1. They increase in increments of 1.•Names in the table are sorted in lexicographic order. The entry for each name starts on a new line.•Both reserved names (like if) and unreserved names (like factorial) appear in the table.•Names in comments, in string constants, etc., do not appear in the table.•Upper and lower case letters are different from each other. As a result, the name Factorial is different from the name factorial.•Names that start with upper case letters (like Factorial) appear before names that start with lower case letters (like factorial). This is because the names are sorted by character codes: the codes for upper case letters are less than those for lower case letters. For details, visit or type the command man ascii to the shell in a Macintosh, Linux, or Unix system.•Each line number is written using exactly five digits, and is padded on the left with 0’s. This may make a long series of line numbers easier to read. We assume that no line number will ever exceed five digits.•A line number appears at most once after each name. For example, the name int appears twice on line 8, but the number 8 appears only once after int in the table.•The line numbers after each name appear in strictly increasing order.We can use a cross-reference table to find out what names appear in a program, and how they are used. This may be helpful if you’re reading an unfamiliar program, trying to learn how it works. Although a table isn’t needed for a small program like the one in the example, it might be needed for a larger program—perhaps one that’s hundreds of pages long, with thousands of different names.1. Theory.Since the cross-reference generator might be used with very large programs, it must use efficient data structures. It must use a BST that associates a set of keys with a set of values. Each key must be a name, represented as a String. Each value must be a sequence of the line numbers where the name appears, represented as a linear singly-linked list of nodes. Each node in the list must contain a line number, represented as an int. It must also contain a pointer to the next node in the list (or to null).When a name is read for the first time, it must be added to the BST. Its list must have one node, containing the first line number where the name appears. If there are n nodes in the BST, then adding a name and its line number must take O(log n) time. If the same name is read later from the Java source file, then the list of nodes associated with that name must be retrieved from the BST. This must also take O(log n) time. If the line number where the name appears is not already in the list, then a new node containing that number must be added to the end of the list. In either case, adding a new node must take O(1) time.Names are read in order of the line numbers where they appear. As a result, do not search lists to test if Java代写课程算法Introduction to Algorithms帮做二叉搜索树Java编程作业a line number is already there, since that can’t be done in O(1) time. Just test the last node in the list.After all the names have been read, you must print the cross reference table by traversing its BST. The names in the table must appear in lexicographic order, as in the example of the previous section. Each time you visit a node in the BST, you must print its name, followed by the line numbers where the name appears. The output doesn’t have to be pretty, but it must be easily readable.2. Implementation.You don’t need to know how to read names from a Java source program: I’ve provided a Java class called Nomenclator that does it for you. Java source code for Nomenclator is available on Moodle, in the file Nomenclator.java. The word Nomenclator means ‘‘an announcer of names.’’You also don’t need to know how Nomenclator works internally. You do have to know how Nomenclator’s public methods are called. The class Nomenclator acts something like an iterator, but it has two next methods: one that returns a line number, and another that returns a name. Here are the details.public Nomenclator(String path, boolean listing)Constructor. Initialize a new instance of Nomenclator that reads a Java source file whose name is the parameter path. It throws an exception if the file doesn’t exist, or if it can’t be read for some reason. The parameter listing is described below.public boolean hasNext()Test if there are more names to be read from the Java source file.public String nextName()If hasNext() is true, then return the next name from the Java source file, as a String. Otherwise, return an undefined String that might be null.public int nextNumber()If hasNext() is true, then return the line number where the name appears. Otherwise, return an undefined integer.public static void main(String [] args)Test the hasNext, nextName, and nextNumber methods of the class Nomenclator. You don’t need this main method when you use Nomenclator in your cross-referencer! It just provides an example of how Nomenclator’s methods work.If listing is true when you call Nomenclator’s constructor, then Nomenclator will produce a listing of the program it reads, with five-digit line numbers, like the one in the example. Iflisting is false, then Nomenclator will not produce such a listing.Do not modify Nomenclator! If you think you need to do that, then you are getting ready to make a bad mistake. If you find bugs in Nomenclator, then please let me know as soon as possible, either by email or in person, so I can fix them.Using Nomenclator, your cross-reference generator might have a code fragment that looks something like this. It reads names from a file, adds them to a BST, and then prints a sorted table by traversing the BST.BinarySearchTree tree = new BinarySearchTree();Nomenclator nomenclator = new Nomenclator(path, true);while (nomenclator.hasNext()){tree.add(nomenclator.nextNumber(), nomenclator.nextName());}traverse(tree);When adding names and line numbers to a BST, you must compare Strings lexicographically. You can do that by calling the method compareTo. If S₁ and S₂ are expressions that return Strings, then the Java expression S₁.compareTo(S₂) returns an integer. It’s less than 0 if S₁ is less than S₂. It’s 0 if S₁ is equal to S₂. It’s greater than 0 if S₁ is greater than S₂. The method compareTo may require O(k) character comparisons if there are k characters in s₁ and s₂. Since this is potentially slow, you must call compareTo as few times as possible. For example, you might call compareTo, save its value in a variable, and then use the variable instead of calling compareTo again.The call System.out.format(“%05d”, n) writes an integer n using five digits with leading 0’s, like the line numbers in the example. The method format is predefined by Java as part of the stream System.out.Since this is the final project of the course, I’ve given you less guidance here than in past projects. There are no specific classes you must write, and no specific methods you must implement. However, you are not allowed to use predefined classes from the Java library that implement data structures like BST’s, hash tables, linked lists, etc.3. Deliverables.Unlike the lab assignments, you are not allowed to work with a partner on this project. IT MUST BE COMPLETED BY YOURSELF ALONE. Although you can discuss the project in a general way with others, you are not allowed to get help from anyone, except Prof. Moen or the course TA’s. You must submit the following on Moodle.•The source code for your program (50 points).•An example Java source file that is used as input to your program.•The cross-reference table produced for the example source file, with the listing option turned on.This project is due on Wednesday, December 13, 2017 at 11:55 PM, the last day of instruction for this semester. You must submit only one file containing the source code for your program. The example Java source file, and its cross reference table, must appear in comments at the end of that file. If you do not know how to submit your work, then please ask one of the TA’s.& 转自：http://ass.3daixie.com/2018052610496776.html