program辅导、Python/Java程序辅导

日期：2023-05-31 07:24

EEE computing
Assignment 3 (Summer 2023)
Please read the whole page word by word from top to bottom at least once. Do not just skim through.
Before you ask a question please check again whether the answer can already be found here and give
yourself some time to think.
Context
In this assignment we are going to apply what we have seen in the second assignment to a task from data mining and
machine learning.
Let's begin with an example. Imagine someone who goes kayaking on days with different conditions and keeps a record
such as the following one, in which a certain configuration of conditions (temperature, rain, wind) is labeled with an
assessment of the quality of the experience:
temperature rain wind quality
high yes light acceptable
low yes light acceptable
low no moderate good
high yes strong poor
high yes moderate acceptable
high no moderate good
low yes strong poor
high no light good
low yes moderate poor
high no strong poor
The rows are not in any particular order and not all the possible combinations are present.
A first example of tree representation
We could for example represent this information as a tree as follows:

We consider the implementation of such trees using a variation of the implementation we have seen in the second
assignment.
As you can see, in this assignment the edges are labeled. So the EdgeNode structured data type will also have a val field to
label the edge:
struct EdgeNode{
tree_t val;
TreeNode* subtree;
EdgeNode* next;
};
You can also see that in this assignment there can be repetitions in the tree.
The tree above with a different order for the edges
In this assignment the order of the edges doesn't matter, therefore the following tree would be considered equivalent to the
previous one:
temperature
low high
rain
rain
yes no no yes
wind wind
good wind
light
acceptable
moderate strong
poorpoor
light
good
moderate strong
goodpoor
light
acceptable
moderate strong
acceptable poor

A tree representation with fewer nodes
The following tree represents the same information in fewer nodes, therefore it is more effective for our purposes:
Not a tree
The nodes of a tree cannot have several parents (otherwise it's not a tree, it's a different data structure) therefore for
example this would not be correct:
temperature
Ow high
rain rain
yes no yes no
wind good
wind wind
light moderate strong light strong
acceptable poorpoor
light
good
moderate
strongmoderate
poor good acceptableacceptable poor
no
good
lgi h t
rain
yes
acceptable
wind
moderate strong
rain poor
good
yes
temperature
low high
poor acceptable

Implementation
Write a class called A3Tree that can be used for the purpose illustrated by the example above. The following is an example
of a main with testing for the example above (header inclusions have been omitted), use this example to infer what member
functions need to be included in the class:
int main(){
// direct initialisation of a vector
// in this case it's a vector containing vectors
// each of which contains words (std::string)
std::vector> input
{
{"temperature", "rain", "wind", "quality"},
{"high", "yes", "light", "acceptable"},
{"low", "yes", "light", "acceptable"},
{"low", "no", "moderate", "good"},
{"high", "yes", "strong", "poor"},
{"high", "yes", "moderate", "acceptable"},
{"high", "no", "moderate", "good"},
{"low", "yes", "strong", "poor"},
{"high", "no", "light", "good"},
{"low", "yes", "moderate", "poor"},
{"high", "no", "strong", "poor"}
};
A3Tree t(input);
// direct initialisation of a vector:
std::vector q{"low", "yes", "strong"};
std::cout << t.query(q) << std::endl;
// this should print: poor
// assigning new content overwriting the previous content:

q = {"high", "yes", "moderate"};
std::cout << t.query(q) << std::endl;
// this should print: acceptable
std::cout << t.node_count() << std::endl;
// this depends on the actual tree generated,
// if we consider the tree in the example which
// has wind in the root node this should print: 10
std::cout << t.leaf_node_count() << std::endl;
// this depends on the actual tree generated,
// if we consider the tree in the example which
// has wind in the root node this should print: 6
}
As mentioned above, the implementation must be based on a variation of what we have seen in the second assignment, so
you will need to include (and meaningfully use) the following (include it as given, do not alter it):
struct TreeNode;
struct EdgeNode;
typedef std::string tree_t;
struct EdgeNode{
tree_t val;
TreeNode* subtree;
EdgeNode* next;
};
struct TreeNode{
tree_t val;
EdgeNode* subtree_l;
};
Within the A3Tree class definition it will therefore look like this:
class A3Tree{
// there will be other code here
private:
TreeNode* t;
// member data pointing to the root of the tree
// do not change the name or anything else regarding
// this member data declaration
};
You can define and use all the additional functions, member data, member functions, structured data types, classes you
need.
Write some comments at the beginning of each function or member function to explain what it does. Do not comment
code line by line. Remember that it is important that your code is clear and readable (minimising the need for comments).
You can include any headers from the standard library except for the algorithm header.
Submit a main that includes evidence of your testing and include some comments on the testing. For our testing we will also
replace your main with our own main.
Your implementation should work in principle on an input with any number of columns and in which any number of
distinct values may appear in each column. You can assume that the names of the columns and the values have no spaces.
For example:
int main(){

std::vector> input1
{
{"temperature", "rain", "wind", "quality"},
{"high", "yes", "light", "acceptable"},
{"low", "yes", "light", "acceptable"},
{"low", "no", "moderate", "good"},
{"high", "yes", "strong", "poor"},
{"high", "yes", "moderate", "acceptable"},
{"high", "no", "moderate", "good"},
{"low", "yes", "strong", "poor"},
{"high", "no", "light", "good"},
{"low", "yes", "moderate", "poor"},
{"high", "no", "strong", "poor"}
};
std::vector> input2
{
{"Feature_3", "feature2", "feature", "feature0", "not_a_feature"},
{"a13480", "10", "a13480", "a", "1"},
{"B_34203", "9", "1343432", "a", "a2"},
{"a13480", "8", "57657", "a", "3"},
{"B_34203", "B_34203", "4523", "a", "2"},
{"B_34203", "6", "4523", "a", "some_value"},
{"a13480", "5", "4523", "a", "1"}
};
A3Tree t1(input1);
A3Tree t2(input2);
std::vector q;
q = {"high", "yes", "moderate"};
std::cout << t1.query(q) << std::endl;
// this should print: acceptable
q = {"B_34203", "9", "1343432", "a"};
std::cout << t2.query(q) << std::endl;
// this should print: a2
}
Destructor, copy constructor, assignment operator
Remember to include a suitable destructor.
The copy constructor and assignment operator would be needed for correct design but they are outside the scope of
this assignment, do not include them.
Guidelines
You can assume that the implementation will always be tested with valid, meaningful and consistent input. The vector (of
vectors of string) passed in input to the constructor of class A3Tree will be consistent and with no repetitions (in the sense
of no repetitions of rows) and it will not be empty. Member function query will not be tested giving in input an inconsistent
or empty vector or a vector representing a row that did not appear in the input to the constructor.
Outside of the main do not add any user input or output or file input or output.
All the variables must be declared in the scope of a function (either the main or some other one). In other words, global
variables are not allowed.
All the loops must be controlled/terminated either by the loop condition or by return. Statements such as break,
continue, goto are not allowed anywhere in the code.