Porject 4
From LL to Tree Project4 By S. Pham Instructions 1. Goals: Computerize the company transactions between all stores using insertion sort on linked lists with stack as garbage collection. When an item has no quantity (quantity=0), the node must be removed out of store and dumped into stack. On the other hand, when an item does NOT in the store linked list, a node in Stack is used. In the case the stack is empty, a new node is requested. 2. Scores: 200 points 3. Due date: Midnight on May 13, 2021. Beyond that time the submission will NOT be graded. 4. Submission: – a zip file includes: • must contain ONLY JAVA files and • a description txt-file(see example below) – Email zip file to
[email protected] – Format of zip filename: [YourLastname]-[YourFirstname]-P4 mailto:
[email protected] Instructions –Page 2 5. Before the submission, you need to compile with instruction: javac Test.java to detect any errors. If this compilation is failed, the submission will NOT be graded. 6. Please pay attention that the class names and the filenames must be identical. 7. The identical / similar codes will NOT be graded. They will get no points and/or be reported to Vice President for solutions. Example: description txt-file 1. All source codes are in Java class files. List all of them. Under each, there will be a sub-list of their attributes, constructors, and methods (in title only) 2. Example of P2-Solution: (see next page) Example: description txt-file P3-Solution Description 1. Test.java: - public static void main(String[] args) 2. Node.java - int item; //attributes - Node link; - Node(int input) //constructors - Node() - public String toString() //method 3. Utility.java - static String keyBoardInput() 4. LL.java - Node head; //attributes - LL() //constructors - LL(int i) - public String toString() //methods - void insert(int n) 5. SortLL.java - String s; //attributes - LL top - SortLL(String s) //constructors - Void insertionSort(LL) //methods - public String toString() input vs. output 1. Input can be entered via keyboard or hard codes as a string in Test.java 2. EX: Company hd = new Company(); hd.insertH(5, "5:3 4:200 3:45 2 1:90"); hd.insertH(9, “7:3 4:100 5:45 2:30 1:90"); 3. Output will display all stores. Each store will have an id followed by a sequence of items sorted in increasing order. Output also displays the content of stack. System.out.println ("HD1="+hd); Store 9 = 1(90) 2(30) 4(100) 5(45) 7(3) Store 5 = 1(90) 2(1) 3(45) 4(100) 5(3) Stack = empty 4. Transaction: it is a process to move an item(with quantity) around the stores, supplier, and buyers (SEE NEXT PAGE) input of Transaction Source or destination can be: - S9 as Store with id=5 - B as a buyer - D as a distributor (supplier) Example of Input: “s9,s5, 5:3 4:200 3:45 2 1:90” //use comma to split it into Source, Destination, and Sequence //use space(s) to split sequence into the items //use colon to separate item to be id and quantity S5S9 “5:3 4:200 3:45 2 1:90" Source(From) Destination(To) Sequence of items Approach: item to Object Item See Handle Duplicates Node with item as an integer: class Node{ int item; //attributes Node link; Node(int input){ //constructor item = input; link = null; //x } //method public String toString(){ return (“”+item); } } Node with Item as an object: 25 x item link class Item { int value; int quantity; Item(int v){ value =v; quantity =1; } Item(int v, int q){ value =v; quantity =q; } public String toString(){ return “” + value + ”(“ + quantity + ”)”; } } x Item link 17 2 value quantity class Node{ Item item; //attributes Node link; Node(int input){ //constructor item = new Item( input); link = null; //x } //method public String toString(){ return (“”+item); } } Another Approach: Add a new attribute Node with item as an integer: class Node{ int item; //attributes Node link; Node(int input){ //constructor item = input; link = null; //x } //method public String toString(){ return (“”+item); } } Node with 2 integers: 25 x item link class Node{ int item; //attributes int quantity; Node link; Node(int input){ //constructor item = new Item( input); quantity =1; link = null; //x } //method public String toString(){ return (“”+item+”:”+quantity); } } 125 x item quantity link The classes 1. class Node or (class Item & class Node) – Handout: Handle Duplicates 2. class LinkedList 3. class Stack extends LinkedList Handout: LL to Stack 4. class SortLinkedList – P3-solution Handout: Handle Duplicates 5. (bonus) class Company (see next page): sequence of CNodes . Class CNode 6. Class Utility (not an object class) class Company class Company{ CNode cHead ; //attributes Stack st; Company (){ //constructor cHead = new CNode(); st = new Stack(); } //method(s) public String toString(){ return (“”+cHead + “\n”+ st); } } cHead class CNode { int id; // store id SortLinkedList down; //sorted items CNode next ; //next store // constructors // toString() } x1 x id down next 5 id down next x11 x id down next 101 item quantity link 10 x item quantity link st 2 stack