讲解 Assignment 2辅导 C/C++程序

Assignment 2 100 marks possible

When submitting, zip up your entire Netbeans projects (Try to create and include your “.jar” files of your Noise Removing and Maze projects) into a folder with the following structured file name:

lastname_firstname_studentID.zip (using your own name and ID)

Assignment 2.zip contains (see the image on the side):

•     studentapp folder (for entire question 1 project)

•     noiseremoving folder (for entire question 2 project)

•     maze folder (for the entire question 3 project)

and submit the Assignment 2 zipped folder on Canvas BEFORE the

due date and time. Late submissions will incur a penalty. Antiplagiarism software will be used on all assignment submissions, so make sure you submit YOUR work and DO NOT SHARE your answer with others. The project's source code templates are given. Please DO NOT change the package name.

Question 1: Binary Tree and Student Sorting (50%)

The purpose of this question is to have an opportunity of understanding and manipulate a binary tree and utilize the binary tree to create a program that sorts elements by different fields and can search  an element by a searching key. The binary tree is built by a key of the node (Key can be different

types)

Student Class

Create a Student Class that stores student’s name, score, and comments.

Name and comments are String type and score is Float type.

Student Class has a “toString” method which returns the name, score, and comments of the student and each of the details should be on separate lines. Such as:

Student07

Score: 25.759476 Comments 6

//name

//score

//comments

Node Class

Create a Node Class that has element, key, and linkers parts.

The “element” of a Node class is a generic type. It references any type of object. This project, it references a Student object.

The “key” is used to compare different nodes. It must be a Comparable Object and generic type.

If the key is a String type, then the tree must be built by the name of the students.

If the key is a Float type, then the tree must be built by the score of students.

Node Class has a node linker named “left” which references to a node that has a smaller key value.

Node Class has a node linker named “Right” which references a node that has a greater key value.

Node Class has a “compareTo” method. “compareTo” method takes a Node object in and compares it to the current node by their keys.

It returns:

= 0: if current node’s element equals to the argument node’s element.

< 0: if current node’s element is less than the argument node’s element.

> 0: if current node’s element is greater than the argument node’s element.

BinaryTree Class

Create a BinaryTree Class which builds and manages a binary tree.

BinaryTree Class has a Node reference named “root” to reference to the root node of a binary tree.

BinaryTree Class has an int variable named “number_of_nodes” to store the number of nodes that a

binary tree has.

BinaryTree Class has a Node array named “nodeList” to store sorted nodes. (The assignment was

designed to output the sorted a txt file. Now, to make it simple, the binaryTree provides a node array to store sorted nodes instead of a text file)

BinaryTree Class has an “addElement” method. It takes an element and a key then it creates a Node object. The Node object loads element and key then is passed to addNode() method to attach on the tree.

BinaryTree Class has an “addNode” method. It takes a root and a new node to create a tree when the tree is empty or adds a new node to the binary tree.

BinaryTree Class has a “reverseOrder” method. It manipulates the binary tree. By default, if we call in-order traversal method, it displays nodes’ details in the order of from smallest key value to the   largest key value.  If reverseOrder method has been called, then traversal method displays nodes’ details in the order of from largest key value to the smallest key value.

The time complexity (Big O) of “reverseOrder” method must be n. Please do not rebuild your tree （ Big O of rebuild a tree is nlog2 n）. Comment your solution, please.

BinaryTree Class has a “searchElement” method. It takes a key which is a generic type then creates a target node object which is a Node object and loads key to the target node. The target node is passed to the searchNode() method to do the searching job. “searchElement” method returns a

generic type element if searchNode() returns a Node object. Otherwise, it returns null. The target node only contains a key value for searching.

An example of how searchNode() method is called in the searchElement() method: Node targetNode = new Node(); targetNode.key = “Student01”;

Node resultNode = tree.searchNode(tree.root, targetNode);

…

BinaryTree Class has a “searchNode” method. It takes a root and target node. It returns a node if it finds the node. Otherwise, it returns null.

In this assignment, the searchingResultNode.element references a Student object which contains all the details of that student.

For a better understanding of adding and searching students, please see the diagrams after StudentManager class.

BinaryTree Class has a “toSortedList” method. It travels each node of the current tree and stores the nodes to the “nodeList” array.

BinaryTree Class has a “traversal” method. It travels each node on the current tree and display

node.elements’ details in the order of from the smallest key value to the largest key value, or from the largest key value to the smallest key value (it depends on whether reverseOrder() has been

called).

You are welcome to add more methods or fields if you need them.

Fully comments on the methods of addNode(), searchNode(), reverseOrder() and traversal().

You may lose 20% of the marks if you don’t give the comments to those methods.

StudentManager Class

StudentManager class has a BinaryTree object named “bTreeScore” which stores Nodes. All nodes are arranged by the students’ scores (node.key is Float type).

StudentManager class has a BinaryTree object named “bTreeName” which stores Nodes. All nodes are arranged by the students’ names (node.key is String type).

StudentManager class has a method named “addStudent” which takes a String name, a Float score, and a String comments to create a Student object then calls addToTree() twice and passes the

Student object with different keys (name or score) to add on different trees.

StudentManager class has a method named “addToTree” which takes a Student object and a key (the type of key can be Float or String) to add to the bTreeScore or bTreeName (put a node on different

trees)

StudentManager class has a method named “findStudent” which takes a searching key and returns a student that matches the searching key by calling binaryTree. searchElement(key). If the student

does not exist, it returns null.

StudentManager class has a method named “getSortedStudentList” which takes a key (the type of key can be Float or String) and returns a Student array. The elements in the Student array must be sorted by the key.

StudentManager class has a method named “reverseOrder” which calls the BinaryTree objects to reverse the order of the trees.

You can add more methods or fields as you wish, but you must pass the testing code (StudentApp.java).

Question 2 Sorting: Noise Removing Application (20%)

Problem: Salt-and-pepper noise, also known as impulse noise, is a form of noise sometimes seen on digital images. This noise can be caused by sharp and sudden disturbances in the image signal. It

presents itself as sparsely occurring white and black pixels.

See more information:

https://en.wikipedia.org/wiki/Salt-and-

pepper_noise#:~:text=Salt%2Dand%2Dpepper%20noise%2C,occurring%20white%20and%20black%2 0pixels.)

Example (image with Salt-and-pepper noise)

An effective noise reduction method for this type of noise is a median filter.

Median Filter:

A program reads a pixel and its 8 surrounding pixels (This 3x3 block of pixels is called a sliding window in digital image processing) from an image and then finds the median of these 9 pixels. Finally, the

median replaces the central pixel. The sliding window moves onto the next pixel and repeats this process until all pixels have been changed (To make the assignment simple, it excludes the bound pixels).

Median: the middle score when all the scores are arranged in order of size from the smallest to the highest. If there is an even number of scores, then it is the average of the two middle scores (It will not be the case in this assignment).

The code of reading the image, getting pixels, and saving pixels to an image has been done for you. Your task is to find the median for given pixels. To find the median, you need to sort an array of 9  pixels. Example (output image after removing noise)

Your task:

Please download the “NoiseRemoving.zip” file and extract it to a folder. The project contains

two .java files. “ImageProcess.java” and “NoiseRemoving.java”. If you run the project, it loads an   image and generates a .jpg file, named “noise_removed.jpg”, but the generated image still contains noise for now. You need to complete the method of “cleanNoise” to clean the noise in the

ImageProcess class.

“ImageProcess.java” deals with an image. It has a method named “cleanNoise”. There is a gap in the method. You need to add your ArraySort Class to the project and fill the gap to complete the

ImageProcess Class (3%).

You need to write an “ArraySort” Class. It takes a generic Comparable type of array and sorts array in order.

ArraySort Class has an “array” field. It stores a reference of an array. (1%)

ArraySort Class has a “setArray” method. It takes a reference of an array and passes the reference to the “array” field. (1%)

ArraySort Class has a “quickSort” method. It runs a quick sort algorithm and sorts arrays in order.(3%) DO NOT COPY THE CODE FROM THE CHAPTER 3 EXAMPLES

PLEASE FULLY COMMENT YOUR CODE OF quickSort() (3%)

Answer following questions in your Comments at the beginning of your ArraySort Class code.

1.    Is quick sort the best way of finding median? Why? (3%)

2.   What is another good way of finding median? Please provide your explanation. (3%)

Finally, you need to design a GUI of noise removing application (2%). So, the application can load an image, clean the noise, and save to a new image. And produce a .jar file of this project. (1%)

*If you are interested in image process, you may try some open-source library. OpenCV for C/C++ or JavaCV for Java.

Question 3: Maze (30%)

You are going to design a program. It loads a maze from a maze text file then the program walks through the maze and finds the path from the starting node to the exiting node.

Maze text file format:

Number of linkers, Number of columns, number of rows (Header of maze)

Node’s name, x position, y position, next linked node name, next linked node name

…

Node’s name, x position, y position, next linked node name, next linked node name Example:

22,7,6

START,0,2,B,A B,1,2,C,K

C,1,3,D,E

…

V,4,1,N,A

EXIT,6,2,A,A

“A” is the same as null. It means not next linked node on this path (this path has no exit).

“W” links to exit.

Your task is to write a program. The program does:

•     Loads a maze txt files (there are two txt files in the project folder. Please do not move them to somewhere else) (3%)

•     Draws a maze on the panel (You are going to decide how to label the nodes). (3%)

•    Walk through the maze and find a path from start to exit. (5%) You need to show an animation of how your program finds a path from start to exit. (3%)

•     Highlight the trail from “Start” to “Exit” on the panel (see image below). (3%)

•     Display the path from “Start” to “Exit”. (5%)

•     make sure your program works for both txt files. (7%) GUI is provided. (1%)

A jar file is created.

A demonstration is available during the lecture. If you missed the lecture, please ask the lecturer to run a demonstration in the lab.