代写Java编程、代做program程序语言
NOTE: For this assignment, you need to refrain from using built-in implementations of
data structures (e.g., Java Collections Framework) and instead focus on manual
implementations using primitives or arrays. This approach is intended to deepen your
understanding of the underlying algorithms and enhance your problem-solving skills.
Project Overview:
In this project, students will implement a library of basic data structures using Java (or C++).
The library should include (at least 3 of) the following data structures and provide interfaces for
accessing their methods:
1. Linked List: Implement a singly linked list with basic operations such as insertion,
deletion, and traversal. Your linked list needs to have integer keys. (10 points)
2. Stack: Implement a stack with its defining operations: push, pop, top. Your stack needs
to save integer keys. (10 points)
3. Queue: Implement a queue with its defining operations: enqueue and dequeue. Your
queue needs to save integer keys. (10 points)
4. Min Heap: Implement a min heap with its defining operations: insert and extractMin. Your
heap needs to save integer keys. (12 points)
5. Binary Search Tree: Implement a binary search tree (BST) with the operations: insert,
delete, find, and inorder traversal. (13 points)
Project Requirements:
For each of the above data structures, students should:
● Provide a well-documented and organized codebase, following best practices for coding
style and commenting.
● Follow the Object-Oriented Programming (OOP) Approach: Implement each data
structure using a class-based approach. Each data structure should be encapsulated
within its own class with an interface to access the main methods, promoting code
modularity and reusability. Ensure proper use of class members (attributes and methods)
for encapsulation.
● Ensure Loose Coupling: Design your classes in a way that promotes loose coupling
between different data structures. Minimize dependencies between classes to make your
codebase modular and maintainable.
● User-Friendly Menu: Implement a guiding menu within your program that explains the
available options to the user. The menu should provide clear descriptions of each
operation the user can perform with the data structure(s). It should also handle user
input gracefully and provide meaningful output.
● Sample Output: Your program's menu system should resemble the sample provided in
the project description, as illustrated in the sample test cases. This means that the user
should interact with the program by selecting options, inputting data, and receiving
output in a structured and easily understandable format.
Sample Test Cases:
To demonstrate the data structures your program supports and guiding the user to the right
commands, your program needs to provide a menu of items that the user needs to do. This
menu can be similar to what is shown below:
1. Linked List: You can view a sample input and output of the required program here
below. This example demonstrates an interactive session where the user can add and
remove data from the Linked List and view its contents step by step.
Program: Please select the data structure you want to work with:
Enter 1 for Linked List
Enter 2 for Stack
Enter 3 for Queue
Enter 4 for Min Heap
Enter 5 for Binary Search Tree (BST)
You've selected Linked List.
What do you want to do with the Linked List?
1. Add Data
2. Remove Data
3. Display Linked List
4. Exit
Enter your choice (1/2/3/4): 1
Enter the data to add to the Linked List (-1 to end): 5
Enter the data to add to the Linked List (-1 to end): 10
Enter the data to add to the Linked List (-1 to end): 20
Enter the data to add to the Linked List (-1 to end): -1
What do you want to do with the Linked List?
1. Add Data
2. Remove Data
3. Display Linked List
4. Exit
Enter your choice (1/2/3/4): 3
Your Linked List looks like this:
5 -> 10 -> 20
What do you want to do with the Linked List?
1. Add Data
2. Remove Data
3. Display Linked List
4. Exit
Enter your choice (1/2/3/4): 2
Enter the data to remove from the Linked List (-1 to end): 10
Enter the data to remove from the Linked List (-1 to end): -1
What do you want to do with the Linked List?
1. Add Data
2. Remove Data
3. Display Linked List
4. Exit
Enter your choice (1/2/3/4): 3
Your Linked List looks like this:
5 -> 20
What do you want to do with the Linked List?
1. Add Data
2. Remove Data
3. Display Linked List
4. Exit
Enter your choice (1/2/3/4): 4
2. You can view a sample input and output of the required program here below. This
example demonstrates an interactive session where the user can push, pop and view
the top element from the Stack step by step.
Program: Please select the data structure you want to work with:
Enter 1 for Linked List
Enter 2 for Stack
Enter 3 for Queue
Enter 4 for Min Heap
Enter 5 for Binary Search Tree (BST)
You've selected Stack.
What do you want to do with the Stack?
1. Push Element
2. Pop Element
3. Top Element
4. Exit
Enter your choice (1/2/3/4): 1
Enter the data to push onto the Stack (-1 to end): 5
Enter the data to push onto the Stack (-1 to end): 10
Enter the data to push onto the Stack (-1 to end): 20
Enter the data to push onto the Stack (-1 to end): -1
What do you want to do with the Stack?
1. Push Element
2. Pop Element
3. Top Element
4. Exit
Enter your choice (1/2/3/4): 2
Popped element: 20
What do you want to do with the Stack?
1. Push Element
2. Pop Element
3. Top Element
4. Exit
Enter your choice (1/2/3/4/5): 3
Top element: 10
What do you want to do with the Stack?
1. Push Element
2. Pop Element
3. Top Element
4. Exit
Enter your choice (1/2/3/4): 4
3. You can view a sample input and output of the required program here below. This
example demonstrates an interactive session where the user can enqueue and dequeue
elements in a queue step by step.
Program: Please select the data structure you want to work with:
Enter 1 for Linked List
Enter 2 for Stack
Enter 3 for Queue
Enter 4 for Min Heap
Enter 5 for Binary Search Tree (BST)
You've selected Queue.
What do you want to do with the Queue?
1. Enqueue
2. Dequeue
3. Exit
Enter your choice (1/2/3): 1
Enter the data to enqueue (-1 to end): 5
Enter the data to enqueue (-1 to end): 10
Enter the data to enqueue (-1 to end): 20
Enter the data to enqueue (-1 to end): -1
What do you want to do with the Queue?
1. Enqueue
2. Dequeue
3. Exit
Enter your choice (1/2/3): 2
Dequeued element: 5
What do you want to do with the Queue?
1. Enqueue
2. Dequeue
3. Exit
Enter your choice (1/2/3): 1
Enter the data to enqueue (-1 to end): 25
Enter the data to enqueue (-1 to end): 30
Enter the data to enqueue (-1 to end): -1
What do you want to do with the Queue?
1. Enqueue
2. Dequeue
3. Exit
Enter your choice (1/2/3): 2
Dequeued element: 10
What do you want to do with the Queue?
1. Enqueue
2. Dequeue
3. Exit
Enter your choice (1/2/3): 3
4. You can view a sample input and output of the required program here below. This
example demonstrates an interactive session where the user can insert elements into
the Min Heap or extract the element with highest priority (extractMin) from the Min Heap
step by step.
Program: Please select the data structure you want to work with:
Enter 1 for Linked List
Enter 2 for Stack
Enter 3 for Queue
Enter 4 for Min Heap
Enter 5 for Binary Search Tree (BST)
You've selected Min Heap.
What do you want to do with the Min Heap?
1. Insert
2. ExtractMin
3. Exit
Enter your choice (1/2/3): 1
Enter the key to insert into the Min Heap (-1 to end): 15
Enter the key to insert into the Min Heap (-1 to end): 10
Enter the key to insert into the Min Heap (-1 to end): 20
Enter the key to insert into the Min Heap (-1 to end): -1
What do you want to do with the Min Heap?
1. Insert
2. ExtractMin
3. Exit
Enter your choice (1/2/3): 2
Min element extracted: 10
What do you want to do with the Min Heap?
1. Insert
2. ExtractMin
3. Exit
Enter your choice (1/2/3): 1
Enter the key to insert into the Min Heap (-1 to end): 5
Enter the key to insert into the Min Heap (-1 to end): 8
Enter the key to insert into the Min Heap (-1 to end): 12
Enter the key to insert into the Min Heap (-1 to end): -1
What do you want to do with the Min Heap?
1. Insert
2. ExtractMin
3. Exit
Enter your choice (1/2/3): 2
Min element extracted: 5
What do you want to do with the Min Heap?
1. Insert
2. ExtractMin
3. Exit
Enter your choice (1/2/3): 3
5. You can view a sample input and output of the required program here below. This
example demonstrates an interactive session where the user can insert new nodes,
delete nodes, find a node, and do inorder traversals on the elements from the Binary
Search Tree (BST) step by step.
Program: Please select the data structure you want to work with:
Enter 1 for Linked List
Enter 2 for Stack
Enter 3 for Queue
Enter 4 for Min Heap
Enter 5 for Binary Search Tree (BST)
You've selected Binary Search Tree (BST).
What do you want to do with the BST?
1. Insert Node
2. Delete Node
3. Find Node
4. Inorder Traversal
5. Exit
Enter your choice (1/2/3/4/5): 1
Enter the key to insert into the BST (-1 to end): 15
Enter the key to insert into the BST (-1 to end): 10
Enter the key to insert into the BST (-1 to end): 20
Enter the key to insert into the BST (-1 to end): -1
What do you want to do with the BST?
1. Insert Node
2. Delete Node
3. Find Node
4. Inorder Traversal
5. Exit
Enter your choice (1/2/3/4/5): 4
Inorder Traversal of the BST:
10 -> 15 -> 20
What do you want to do with the BST?
1. Insert Node
2. Delete Node
3. Find Node
4. Inorder Traversal
5. Exit
Enter your choice (1/2/3/4/5): 2
Enter the key to delete from the BST (-1 to end): 15
Enter the key to delete from the BST (-1 to end): -1
What do you want to do with the BST?
1. Insert Node
2. Delete Node
3. Find Node
4. Inorder Traversal
5. Exit
Enter your choice (1/2/3/4/5): 3
Enter the key to find in the BST: 20
Node found in the BST.
What do you want to do with the BST?
1. Insert Node
2. Delete Node
3. Find Node
4. Inorder Traversal
5. Exit
Enter your choice (1/2/3/4/5): 4
Inorder Traversal of the BST:
10 -> 20
What do you want to do with the BST?
1. Insert Node
2. Delete Node
3. Find Node
4. Inorder Traversal
5. Exit
Enter your choice (1/2/3/4/5): 5
Deadline and Presentation:
Students are expected to complete each piece of the Data Structure Library after it is posted on
eClass. All students must submit their completed work before November 30th, 2023. Students
need to present their work to the Course Director or the TAs, the details of which will be shared
later on eClass.
Marking Criteria:
Completeness:
For a successful completion of your project, you need to implement 3 working and sound data
structures of your choice from the list provided with a menu to interact with them. (30% of your
final mark)
You can choose to provide more data structures, any 5 extra points over the initial 30 points
required for your assignment will be counted as 2 bonus points towards your final mark. For
example, if you choose to implement all the data structures and they all work properly, you can
get a maximum of 10 extra marks added to your final mark of the course. The bonus points are
contingent on the additional data structures being implemented correctly and soundly.
Partial marks will be awarded as per instructor’s judgment.
Soundness:
If you choose to implement any of the data structures below, please make sure they are
satisfying all the requirements for the code and that data structure specifically.
● The Linked List needs to work properly and have the functions: insertion, deletion, and
traversal.
● The Stack needs to work properly and have the functions: push, pop, and top.
● The queue needs to work properly and have the functions: enqueue and dequeue.
● The Min Heap needs to work properly and have the functions: insert and extractMin.
● The Binary Search Tree needs to be working properly and have the functions: insert,
find, delete, and inorder traversal.
● The menu (user interface) does not need to be following the example, but it should
provide the means to work with the data structures implemented properly.
● A graphical user interface is not required and implementation of one does not grant extra
marks.
You can refer to the examples provided and test your program before presentations with the
sample input. You need to think about the scenarios that might end in an error. For example,if
you choose to implement a stack using arrays, a stack overflow error should be raised by the
program in case of an overflow.
Code Structure:
Code structure will be reviewed in the marking and presentation session. Therefore, you should
not be using any compiled code or built-in implementation of the data structures. Failure to
provide this requirement can lead to losing marks for the entire project. Please also make sure:
● Object Oriented Programming Approach is followed. Each data structure needs to be
enclosed in a class and interacted with using an interface.
● No implementation of the data structures should be in the main class.