代写一个自排序的双向链表，实现一个Fruit Store的应用程序。List StructureIn this project, you are asked to implement a sorted linked list structure to help a fruit store update its inventory. To simplify this task, we make the following assumptions:The store sells fruits by unit (e.g., an apple, a bunch of grapes, etc.) not by weight.Every type of fruit, regardless of its quantity on stock, is displayed in exactly one storage bin.Storage bins are numbered consecutively starting at 1, and as many bins as needed are available.The names of fruits from the input or passed as arguments to method calls will always be from the list given in Appendix A. (These names are in lower case English letters.)A doubly-sorted list (DSL) consists of two doubly-linked lists (DLLs), which share the same set of nodes, and are sorted respectively by two different data fields. In the DSL, exactly one node N is created for every type of fruit currently on stock. Shown in the top row of Fig. 1, such a node has three data fields: fruit, quantity, and bin, which respectively store the name of the fruit (as a String object), its quantity in units, and the number of its storage bin. At the bottom of the figure displays two nodes with actual data values. They record 50 apples stored in bin 5, and 100 bunches of grapes in bin 8.In addition to the three data fields, a node N also has two pairs of links: nextN and previousN, and nextB and previousB. The first pair locates the two nodes created for the fruits whose names immediately precede and succeed, in the alphabetical order, the name N.fruit of the fruit represented by N. All the nextN and previousN links thus form a doubly-linked list (DLL) which orders the nodes by fruit name. The list, referred to as the N-list, is accessed via a dummy node headN. Fig. 2 shows an N-list for four different types of fruits. Note that the last node (“pear”) has its nextN link reference the dummy node headN.At the node N, the other two links nextB and previousB respectively reference the nodes for the fruits stored in the previous and next non-empty bins in the numerical order. For instance, suppose N references the “apple” node in Fig. 2. As the node shows, all apples are displayed in bin 5 at the fruit store. The last non-empty bin is bin 3, which stores pears, so the link N.previousB references the “pear” node. Meanwhile, the next non-empty bin is bin 8. Therefore, N.nextB references the “grape” node. All the nextB and previousB links induce a second DLL sorted by bin number. It is called the B-list accessed via a dummy node headB. Fig. 3 displays the B-list formed by the same four nodes from Fig. 2.To distinguish between the N- and B-lists, all the nextN and previousN links will be colored green as in Fig. 2, while all the nextB and previousB links will be colored blue as in Fig. 3. The DSL is now displayed compactly in Fig. 4 by simply merging the two DLLs from Figs. 2 and 3.ConstructorsThere are three constructors:123public DoublySortedList()public DoublySortedList(String inventoryFile) throws FileNotFoundExceptionpublic DoublySortedList(int size, Node headN, Node headB)& The first one is a default constructor which initializes an empty DSL. Fruits will be added to the list later using addition methods introduced later. The second constructor builds a DSL over an inventory file, of which an example is given below:pear 40 3 apple 50 5 banana 20 9 grape 100 8 An input inventory file is assumed to always meet the following format requirements such that there is no need to check for correctness of formatting:Fruits are listed on consecutive lines.Each line displays the name of a different fruit, its quantity, and the number of its storage bin, with at least one blank or tab in between.As in the earlier example, the fruits on an inventory list may not be in the alphabetical order. In the first stage of construction, you are asked to scan the list and create a node over every scanned line. The node’s two pairs of links (nextN, previousN) and (nextB, previousB) are initialized to represent the order of the scan. The links headN and headB both reference the first created node. The scan creates two DLLs, neither of which is sorted at the moment.In the second stage, an insertion sort is carried out on each DLL by the following method:1public void insertionSort(boolean sortNList, Comparator
comp)& Two comparator classes, NameComparator and BinComparator, are provided for the insertion sorts by name and by bin number to construct the N- and the B-lists, respectively. Please note that sorting here is performed on the nodes. You cannot first put the fruit names or their bins in an array and then sort the array instead.The third constructor has been implemented. It will be used for splitting a DSL into two (to be described in Section 6) and by the TA for testing.Stocking FruitsThe list is updated whenever new fruits are stocked. Every new fruit type leads to the creation of a node. For compactness of display, all fruits of this type should be placed into the first empty bin by number.InsertionAddition of a fruit in some specified quantity is carried out by the following method:1public void add(String fruit, int n) throws IllegalArgumentException& It starts out with a sequential search in the N-list for fruit. Two possible situations may arise:The search finds a node N housing fruit, simply increase the N.quantity field by n. This is illustrated in Fig. 5 below.If no node for fruit is found after the search, the fruit is new on the stock. In this case, a new node is created to store the fruit in the first available bin. To illustrate, suppose that add(“orange”, 70) is executed on the DSL in Fig. 4. A search of the B-list finds the first empty bin to be bin 1. Create the following node (in which the bin number is shown in red).Next, add the node to the N-list and the B-list by calling two helper methods: insertN() and insertB(). The first method determines the “orange” node to be between the “grape” and “pear” nodes, while the second method determines that it should appear right after headB on the B-list. In Fig. 6, the two links to be removed are marked with red crosses. Fig. 7 displays the DSL after addition of the new node (which is now referenced by headB).You are asked to implement two private methods below to carry out actual insertions of a node node into the N- and B-lists, respectively.12private void insertN(Node node, Node prev, Node next)private void insertB(Node node, Node prev, Node next)& Each method inserts node between two nodes prev and next via updating either some previousN and nextN links or some previousB and nextB links.RestockingRegularly the store is restocked with fruits of multiple types. This is implemented by the following method:1public void restock(String fruitFile) throws FileNotFoundException, IllegalArgumentException& The parameter fruitFile is the name of a file which lists fruits line by line, where each line starts with the fruit name, follows with one or more blanks or , and ends with its quantity. Below is an example file.pear 40 apple 50 grape 100 banana 20 Selling FruitsSelling of fruits results in updates of their corresponding nodes. When fruits of one type are sold out, the node representing the fruit type must be deleted.RemovalThere are two removal methods, by fruit name and by bin number:12public void remove(String fruit)public void remove(int bin) throws IllegalArgumentException& A removal starts by searching either in the N-list with the name fruit or in the B-list with the number bin. If no matching node is found, simply return. Otherwise, suppose the matching node is N. Call the following private method on N to remove it.1private void remove(Node node)& This method deletes the node from both the N-list and the B-list. An example of removal by fruit name is shown in Fig. 8. Another example, of removal by storage bin, is shown in Fig. 9.SaleThe shop does single sale and bulk sale, which are implemented by the two methods below:12public void sell(String fruit, int n) throws IllegalArgumentExceptionpublic void bulkSell(String fruitFile) throws FileNotFoundException, IllegalArgumentException& The method sell() first searches the N-list to see if the fruit is on stock. Nothing needs to be done if the answer is no. Otherwise, a node N is located for the fruit.While no check is needed for the correctness of the parameter fruit, an exception needs to be thrown if the parameter n is less than zero.The method bulkSell() accepts a file with fruit names and quantities in exactly the same format accepted by the method restock() (see Section 3.2). Assumptions e) from Section 2 and g) from Section 3.2 both hold, so there is no need for file format checking. This method bulkSell() processes an order of multiple types of fruits in specified quantities. It executes the following steps:Sort the purchased fruits and their quantities by name using the private method quickSort(), in a similar way as described for sorting in implementing restock().Simultaneously traverse the N-list and the sorted list of the fruits to be purchased. If the next fruit on the list is not on stock, just ignore its order. Otherwise, a node N with the next purchased fruit will be encountered. Let m be the ordered quantity of this fruit.Inquiry and Storage ManagementQueries for fruit availability can be performed. Every once in a while, the fruit store checks its inventory. Periodically, it compacts the space by re-arranging the bins with fruits next to eachother. Occasionally, it needs to clear all the fruits on stock (due to deterioration of unsold fruits, for instance).Inquiry and Output MethodsThis category has three methods:123public int inquire(String fruit)public String printInventoryN()public String printInventoryB()& The first method checks the quantity of a fruit on stock. The second method outputs a string that is printed out to be an inventory listing fruits in the alphabetical order. Here is sample output of the method from the DSL in Fig. 4.The following formatting rules apply to the output.Entries within each column must be left-aligned.The first characters in two adjacent columns are 16 character spaces apart.You may use the length of a fruit name (which is at most 11 according to the fruit list in Appendix A). You can make the following assumption:The values in the quantity and bin fields will not exceed 3 digits.The method printInventoryB() outputs a string that is printed out to be an inventory sorted by the bin number.Storage MethodsThere are two methods to deal with storage bins:12public void compactStorage()public void clearStorage()& The first method rearranges the bins containing fruits to be consecutive, starting at 1, while maintaining their original storage order. To implement this method, you need only traverse the B-list. See Fig. 12 for an example.The method clearStorge() clears up the N-list and the B-list by setting the predecessors and successors of headN and headB to themselves.本团队核心人员组成主要包括BAT一线工程师，精通德英语！我们主要业务范围是代做编程大作业、课程设计等等。我们的方向领域：window编程 数值算法 AI人工智能 金融统计 计量分析 大数据 网络编程 WEB编程 通讯编程 游戏编程多媒体linux 外挂编程 程序API图像处理 嵌入式/单片机 数据库编程 控制台 进程与线程 网络安全 汇编语言 硬件编程 软件设计 工程标准规等。其中代写编程、代写程序、代写留学生程序作业语言或工具包括但不限于以下范围:C/C++/C#代写Java代写IT代写Python代写辅导编程作业Matlab代写Haskell代写Processing代写Linux环境搭建Rust代写Data Structure Assginment 数据结构代写MIPS代写Machine Learning 作业 代写Oracle/SQL/PostgreSQL/Pig 数据库代写/代做/辅导Web开发、网站开发、网站作业ASP.NET网站开发Finance Insurace Statistics统计、回归、迭代Prolog代写Computer Computational method代做因为专业，所以值得信赖。如有需要，请加QQ：99515681 或邮箱：99515681@qq.com 微信：codehelp
网友评论