Description

Related Topics: ADT, list.
A “list” is a sequence of zero or more numbers in no particular order. A list is well-formed if: a) It is the empty list, or
b) It is an integer followed by a well‐formed list.
A list is an example of a linear‐recursive structure: it is “recursive” because the definition refers to itself. It is “linear” because there is only one such reference.
Here are some examples of well‐formed lists:

int dot(list_t v1, list_t v2);
// REQUIRES: Both “v1” and “v2” are non-empty
//
// EFFECTS: Treats both lists as vectors. Returns the dot
// product of the two vectors. If one list is longer // than the other, ignore the longer part of the vector.
list_t filter(list_t list, bool (*fn)(int));
// EFFECTS: Returns a list containing precisely the elements of “list” // for which the predicate fn() evaluates to true, in the // order in which they appeared in list.
//
// For example, if predicate bool odd(int a) returns true
// if a is odd, then the function filter(list, odd) has // the same behavior as the function filter_odd(list).
list_t filter_odd(list_t list);
// EFFECTS: Returns a new list containing only the elements of the
// original “list” which are odd in value,
// in the order in which they appeared in list.
//
// For example, if you apply filter_odd to the list // ( 3 4 1 5 6 ), you would get the list ( 3 1 5 ).
Since filter_odd is a special case of filter , you can use filter_odd as a function to test filter if you implement it with filter .
Hint
You can think in the way that recursive.h provides an ADT for you and you need to implement the new functions declared in ex1.h using the methods provided.
Problem
1. Implement the functions in ex1.cpp .
Requirements
1. If you define any helper functions yourself, be sure to declare them “static”, so that they are not visible outside this file.
Testing
Since you are only required to implement new methods, there is no IO requirements. However ex1Test.cpp is provided for you to test your correctness but you still need to design you own
test cases to get full score.
Ex2. Quadratic Functions in Standard Form
Related Topics: ADT.
Problem: Roddy wants to represent a quadratic function in a standard form, which is
( ). He decides that the following operations should be allowed on
quadratic functions:
1. Evaluate at a given int value.
2. Get the root(s) of , which is the value of such that
3. Check if two quadratic functions ( and ) intersects, which means whether there exists some real such that .
Therefore, he designed this interface to represent a quadratic function

Requirements:
1. Look through file rootType.h , to make the output simple, we make the following restrictions:
if has two different real roots, then the smaller should be in roots[0] and the bigger should be in roots[1] .
If has one real root, then should be in both roots[0] and roots[1] .
If has two complex roots, then should be in root[0] and should be in roots[1] , where .
2. Look through standardForm.h and implement the methods for QuadraticFunction class in standardForm.cpp .
3. ex2.cpp is used to test your ADT, you can just read it and run it.
Input Format: Since you only need to implement the methods of this ADT, we just provide a

Output Format: Since you only need to implement the methods of this ADT, we just provide a

1 .

Ex3. Quadratic Functions in Factored Form
Related Topics: ADT.
Problem: Roddy realizes that a quadratic function can also be represented in a factored form, which is ).
This time, the interface looks the same, but the data members are different:

transformation so that they can fit into the new data members. Again, the output method is provided. So you needn’t implement it.
Requirements:
1. Look through factoredForm.h and implement the TODOs in factoredForm.cpp
2. Run ex3.cpp to test the ADT. Note that ex3.cpp includes factoredForm.h , but it uses the same code as in ex2.cpp to test the ADT.

Input Format: Same as ex2
Output Format: Same as ex2
Testing & Submitting
ex1Test.cpp , ex2.cpp and ex3.cpp are provided for your test. Please only compress ex1.cpp , standardFrom.cpp and factoredForm.cpp and submit each of them to the corresponding
exercises on the online judge.

Created by Zhuoer Zhu
Updated by Yanjun Chen
@UM-SJTU Joint Institute