Java is a popular programming language, created in 1995.
It is owned by Oracle, and more than 3 billion devices run
Java.
It is used for:
- Data P1 C Java Programming Java Is A Popular Programming Language Created In 1995 It Is Owned By Oracle And More Tha 1 (70.16 KiB) Viewed 71 times
- Data P1 C Java Programming Java Is A Popular Programming Language Created In 1995 It Is Owned By Oracle And More Tha 2 (20.2 KiB) Viewed 71 times
* Copyright 2014, Michael T. Goodrich, Roberto Tamassia, Michael H.
Goldwasser
*
* Developed for use with the book:
*
* Data Structures and Algorithms in Java, Sixth
Edition
* Michael T. Goodrich, Roberto Tamassia, and
Michael H. Goldwasser
* John Wiley & Sons, 2014
*
* This program is free software: you can redistribute it and/or
modify
* it under the terms of the GNU General Public License as published
by
* the Free Software Foundation, either version 3 of the License,
or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be
useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty
of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See
the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public
License
* along with this program. If not, see .
*/
package net.datastructures;
/**
* A basic singly linked list implementation.
*
* @author Michael T. Goodrich
* @author Roberto Tamassia
* @author Michael H. Goldwasser
*/
public class SinglyLinkedList implements Cloneable {
//---------------- nested Node class ----------------
/**
* Node of a singly linked list, which stores a
reference to its
* element and to the subsequent node in the list (or
null if this
* is the last node).
*/
private static class Node {
/** The element stored at this node */
private E
element;
// reference to the element stored at this node
/** A reference to the subsequent node in the
list */
private Node
next; // reference
to the subsequent node in the list
/**
* Creates a node with the given element
and next node.
*
* @param e the element to be stored
* @param n reference to a node that should
follow the new node
*/
public Node(E e, Node n) {
element = e;
next = n;
}
// Accessor methods
/**
* Returns the element stored at the
node.
* @return the element stored at the
node
*/
public E getElement() { return element; }
/**
* Returns the node that follows this one
(or null if no such node).
* @return the following node
*/
public Node getNext() { return next; }
// Modifier methods
/**
* Sets the node's next reference to point
to Node n.
* @param n the node that
should follow this one
*/
public void setNext(Node n) { next = n; }
} //----------- end of nested Node class -----------
// instance variables of the SinglyLinkedList
/** The head node of the list */
private Node head =
null;
// head node of the list (or null if empty)
/** The last node of the list */
private Node tail =
null;
// last node of the list (or null if empty)
/** Number of nodes in the list */
private int size =
0;
// number of nodes in the list
/** Constructs an initially empty list. */
public SinglyLinkedList() {
}
// constructs an initially empty list
// access methods
/**
* Returns the number of elements in the linked
list.
* @return number of elements in the linked list
*/
public int size() { return size; }
/**
* Tests whether the linked list is empty.
* @return true if the linked list is empty, false
otherwise
*/
public boolean isEmpty() { return size == 0; }
/**
* Returns (but does not remove) the first element of
the list
* @return element at the front of the list (or null if
empty)
*/
public E first()
{
// returns (but does not remove) the first element
if (isEmpty()) return null;
return head.getElement();
}
/**
* Returns (but does not remove) the last element of
the list.
* @return element at the end of the list (or null if
empty)
*/
public E last()
{
// returns (but does not remove) the last element
if (isEmpty()) return null;
return tail.getElement();
}
// update methods
/**
* Adds an element to the front of the list.
* @param e the new element to add
*/
public void addFirst(E e)
{
// adds element e to the front of the list
head = new Node<>(e,
head);
// create and link a new node
if (size == 0)
tail =
head;
// special case: new node becomes tail also
size++;
}
/**
* Adds an element to the end of the list.
* @param e the new element to add
*/
public void addLast(E e)
{
// adds element e to the end of the list
Node newest = new Node<>(e,
null); // node will eventually be the tail
if (isEmpty())
head =
newest;
// special case: previously empty list
else
tail.setNext(newest);
// new node after existing tail
tail =
newest;
// new node becomes the tail
size++;
}
/**
* Removes and returns the first element of the
list.
* @return the removed element (or null if empty)
*/
public E removeFirst()
{
// removes and returns the first element
if (isEmpty()) return
null;
// nothing to remove
E answer = head.getElement();
head =
head.getNext();
// will become null if list had only one node
size--;
if (size == 0)
tail =
null;
// special case as list is now empty
return answer;
}
@SuppressWarnings({"unchecked"})
public boolean equals(Object o) {
if (o == null) return false;
if (getClass() != o.getClass()) return
false;
SinglyLinkedList other = (SinglyLinkedList)
o; // use nonparameterized type
if (size != other.size) return false;
Node walkA =
head;
// traverse the primary list
Node walkB =
other.head;
// traverse the secondary list
while (walkA != null) {
if
(!walkA.getElement().equals(walkB.getElement())) return false;
//mismatch
walkA = walkA.getNext();
walkB = walkB.getNext();
}
return true; // if we reach this,
everything matched successfully
}
@SuppressWarnings({"unchecked"})
public SinglyLinkedList clone() throws CloneNotSupportedException
{
// always use inherited Object.clone() to create
the initial copy
SinglyLinkedList other = (SinglyLinkedList)
super.clone(); // safe cast
if (size > 0)
{
// we need independent chain of nodes
other.head = new
Node<>(head.getElement(), null);
Node walk =
head.getNext(); // walk through
remainder of original list
Node otherTail =
other.head; // remember most recently
created node
while (walk != null)
{
// make a new node storing same element
Node newest = new
Node<>(walk.getElement(), null);
otherTail.setNext(newest); // link previous
node to this one
otherTail =
newest;
walk =
walk.getNext();
}
}
return other;
}
public int hashCode() {
int h = 0;
for (Node walk=head; walk != null; walk =
walk.getNext()) {
h ^=
walk.getElement().hashCode(); //
bitwise exclusive-or with element's code
h = (h << 5) | (h >>>
27);
// 5-bit cyclic shift of composite code
}
return h;
}
/**
* Produces a string representation of the contents of
the list.
* This exists for debugging purposes only.
*/
public String toString() {
StringBuilder sb = new StringBuilder("(");
Node walk = head;
while (walk != null) {
sb.append(walk.getElement());
if (walk != tail)
sb.append(", ");
walk = walk.getNext();
}
sb.append(")");
return sb.toString();
}
}
In this project you will simulate the operating system's selection of processes to send to the CPU. The operating system will select the next process from the of awaiting processes. Each process will require 1 or more the resources A, B and C. Some processes will require only B for example, while another might require A and B. yet another B and C. If the resource is available, the process can be started. If one or more of the resources are unavailable, then the process must wait one cycle. A process that is started will only use a resource for one cycle. A process can only start if all the previous processes have been started. Here is a chart describing a possible scenario: P1(A); P2(B); P3(B,C);P4(C);P5(A,B,C); P6(B,C) Starting process list with resources in (): ;P7(A);P8(A);P9(B);P10(C) Cycle Processes Running Comment 1 P1, P2 P3 must wait - Resource B in use Notice P4 can not start ahead of P3 though its resource is available 2 P3 3 P4 P4 must wait - Resource C used by P3 4 P5 P5 must wait - Resource C used by P4 P6,P7 P6 must wait - Resource C used by P5. P7 can run at same time as P6 P8, P9,P10 P8, P9,P10 all can run together as no resources are shared. Total number of cycles needed: 6 There are 2 parts to the assignment, both parts have the same output of the number of cycles, and final length of the queue. Part A: Read a one line from the Console where the line has the format shown here (and above): P1(A);P2(B); P3(B,C);P4(C);P5(A,B,C); P6(B,C) ;P7(A);P8(A);P9(B);P10(C) For each input string from the Console, assign the processes to a list, then execute the list and determine the number of cycles to completely execute the processes. In our example the answer is 6
Part B: Randomly generate a list of 20 processes. Start executing processes as before. Randomly select 1,2 or 3 resources (A,B,C) for each process. But at the end of each cycle (regardless of how many processes were run), add 2 more process to the end of the list with 1,2,3 random resources. Output the number of cycles needed to empty the list of processes, but if the list does not empty by cycle 1000, then output the number of processes left (length of the list). Output the length of the list of processes every 100th cycle to watch its growth: Length of processes at cycle 100: 104 Length of processes at cycle 200: 107 Length of processes at cycle 300: 63 Length of processes at cycle 400: 139 Number are samples only, your numbers should be different. The goal of the exercise to understand how to simulate the operating system's selection of processes to run. Objectives The goal of this programming project is for you to master (or at least get practice on) the following tasks: • Read input files • Work with singly linked list • Utilize random numbers
P1(C); P2(B); P3(A,B); P4(C); P5(A); P6(A,B); P7 (B); P8(A); P9(B,C); P10(A) P1(A); P2(B,C); P3 (C); P4 (A,B); P5(A,B,C); P6(A,C); P7 (B); P8(A); P9 (B); P10 (C) P1(B); P2(B,C); P3(A,C); P4(B);P5(A,B); P6(A); P7(C); P8(B,C);P9 (B); P10(A,C) P1(A,B,C); P2 (B,C); P3 (B); P4 (A,C); P5(A,B); P6(A,B); P7 (B,C); P8(B,C); P9(A); P10 (A) P1(A); P2(B); P3 (C); P4(B); P5(A); P6(C); P7(A,B,C); P8(C); P9 (B); P10 (A) P1(B,A,C); P2(C,B);P3(A);P4(B,A);P5(B);P6(C); P7(C,A); P8(C,B,A); P9(C,A); P10 (B) P1(B,C); P2(C,B); P3(A,B); P4 (A,B); P5(A,B,C); P6(C,B,A); P7 (B,A); P8(C); P9(A); P10(C,B) P1(A,C); P2(B,C); P3(A,B); P4 (A,C); P5(A,B); P6(B,C); P7 (B,A); P8(C,B); P9(A,C); P10(C,A) P1(C,A,B); P2(A,B,C); P3(B,A,C); P4(B,C,A); P5(A,C,B); P6(C,B,A); P7(A,C); P8(B); P9(B,C); P10 (A) P1(A); P2(A,B); P3 (A,B,C); P4(C); P5(B,C); P6(A,B,C); P7 (B); P8(A,B); P9 (A,B,C); P10(A,B,C)