辅导data编程设计、C++程序语言调试、program编程讲解
- 首页 >> Python编程 Question 4
(25% of DD1; 40% of DD2)
In this question, you will implement a structure that represents a mathematical set for integers. The structure definition and
its associated function signatures have already been given to you in the file a2q4.cc in your repository, and are reproduced
below:
Page 5 of 7
struct IntSet {
int *data;
int size;
int capacity;
};
void init( IntSet & i ); // Initialize to be "empty" with following field values: {nullptr,0,0}
void destroy( IntSet & i ); // Clean up the IntSet and free dynamically allocated memory.
IntSet operator| ( const IntSet & i1, const IntSet & i2 ); // Set union.
IntSet operator& ( const IntSet & i1, const IntSet & i2 ); // Set intersection.
bool operator==( const IntSet & i1, const IntSet & i2 ); // Set equality.
bool isSubset( const IntSet & i1, const IntSet & i2 ); // True if i2 is a subset of i1.
bool contains( const IntSet & i, int e ); // True if set i contains element e.
void add( IntSet & i, int e ); // Add element e to the set i.
void remove( IntSet & i, int e ); // Remove element e from the set i.
// Output operator for IntSet.
std::ostream& operator<<( std::ostream & out, const IntSet & is );
// Input operator for IntSet. Continuously read int values from in and add to the passed IntSet.
// Function stops when input contains a non-int value. Discards the first non-int character.
std::istream& operator>>( std::istream & in, IntSet & is );
You have also been given a test harness in a2q4.cc as the main function. Do not change it. Make sure you read and
understand this code, as you will need to know what it does in order to structure your test suite. It isn’t very robust and does
no error-checking. You are allowed to assume that the commands it receives are valid, so do not write test cases for it!
The commands it accepts consist of:
q terminates the program. Also invoked by Ctrl-d.
n idx initializes the set at index idx. Uses the input operator to reads in integers and store them in the set
until a non-integer is detected, which is then thrown away.
p idx prints the set at index idx using the output operator.
& idx1 idx2 prints the intersection of sets idx1 and idx2.
| idx1 idx2 prints the union of sets idx1 and idx2.
= idx1 idx2 prints true if set idx1 is equal to set idx2; otherwise, prints false.
s idx1 idx2 prints true if set idx2 is a subset of idx1; otherwise, prints false.
c idx elem prints true if set idx contains element elem; otherwise, prints false.
a idx elem adds element elem to set idx .
r idx elem removes element elem from set idx .
We have provided a sample solution to this problem in your a2/q4 directory in the form of an executable binary named
a2q4. Note that it is compiled to run on the linux.student.cs.uwaterloo.ca environment. We have also provided
a sample test input file q4/sample.in, and the corresponding output can be found in q4/sample.out. Since the
program doesn’t take command-line arguments, there is no sample.args file.
Implement the described IntSet functions. Your implementation must satisfy the following requirements:
• A set cannot contain duplicate items. Attempting to add an item already in the set does not change the set nor does it
produce an error (see add and operator&).
• init initializes both the capacity and size of the set to 0. Its array pointer is set to nullptr.
• destroy frees all dynamically allocated memory. We will be using valgrind in marmoset to check for memory leaks.
Page 6 of 7
• After add( IntSet & i, int e ) is called, e must be in the set i. When the first integer is added, the capacity
is increased to 5. If at any point the capacity is not enough, it should be doubled. The size of the set goes up by one for
every value added .
• Set intersection (operator&) returns a new set containing only the elements that are in both sets.
• Set union (operator|) returns a new set containing all of the elements from both sets, without any duplicates.
• Two sets A and B are equal (operator==) if and only if no element of one is not an element of the other. More
precisely: (@xs.t.x ∈ A ∧ x /∈ B) ∧ (@xs.t.x ∈ B ∧ x /∈ A).
• isSubset( const IntSet & i1, const IntSet & i2 ) returns true if and only if every element in i2
is an element of the set i1: otherwise it returns false.
• contains( const IntSet & i, int e ) returns true if e is an element of the set i: otherwise it returns
false.
• After remove( IntSet & i, int e ) is called, e must not be in the set i. You are not required to reduce the
array size or capacity in this implementation.
• The input operator (operator>>) initializes the set parameter, and then adds the read-in integers to the set until a
non-integer value is read. The first non-integer character is thrown away.
• The output operator (operator<<) first prints a left parenthesis ’(’, then each integer in ascending order, delimited
by a comma unless it is the last integer, and ends with a right parenthesis ’)’. For example the set containing 3, 5, and
2 is printed as (2, 3, 5). An empty set is printed as ().
(a) Due on Due Date 1: Design a test suite for this program. Submit a file called a2q4.zip that contains the test suite
you designed, called suiteq4.txt, and all of the .in and .out files.
(b) Due on Due Date 2: Write the program in C++. Save your solution in a file named a2q4.cc.
Page 7 of 7
(25% of DD1; 40% of DD2)
In this question, you will implement a structure that represents a mathematical set for integers. The structure definition and
its associated function signatures have already been given to you in the file a2q4.cc in your repository, and are reproduced
below:
Page 5 of 7
struct IntSet {
int *data;
int size;
int capacity;
};
void init( IntSet & i ); // Initialize to be "empty" with following field values: {nullptr,0,0}
void destroy( IntSet & i ); // Clean up the IntSet and free dynamically allocated memory.
IntSet operator| ( const IntSet & i1, const IntSet & i2 ); // Set union.
IntSet operator& ( const IntSet & i1, const IntSet & i2 ); // Set intersection.
bool operator==( const IntSet & i1, const IntSet & i2 ); // Set equality.
bool isSubset( const IntSet & i1, const IntSet & i2 ); // True if i2 is a subset of i1.
bool contains( const IntSet & i, int e ); // True if set i contains element e.
void add( IntSet & i, int e ); // Add element e to the set i.
void remove( IntSet & i, int e ); // Remove element e from the set i.
// Output operator for IntSet.
std::ostream& operator<<( std::ostream & out, const IntSet & is );
// Input operator for IntSet. Continuously read int values from in and add to the passed IntSet.
// Function stops when input contains a non-int value. Discards the first non-int character.
std::istream& operator>>( std::istream & in, IntSet & is );
You have also been given a test harness in a2q4.cc as the main function. Do not change it. Make sure you read and
understand this code, as you will need to know what it does in order to structure your test suite. It isn’t very robust and does
no error-checking. You are allowed to assume that the commands it receives are valid, so do not write test cases for it!
The commands it accepts consist of:
q terminates the program. Also invoked by Ctrl-d.
n idx initializes the set at index idx. Uses the input operator to reads in integers and store them in the set
until a non-integer is detected, which is then thrown away.
p idx prints the set at index idx using the output operator.
& idx1 idx2 prints the intersection of sets idx1 and idx2.
| idx1 idx2 prints the union of sets idx1 and idx2.
= idx1 idx2 prints true if set idx1 is equal to set idx2; otherwise, prints false.
s idx1 idx2 prints true if set idx2 is a subset of idx1; otherwise, prints false.
c idx elem prints true if set idx contains element elem; otherwise, prints false.
a idx elem adds element elem to set idx .
r idx elem removes element elem from set idx .
We have provided a sample solution to this problem in your a2/q4 directory in the form of an executable binary named
a2q4. Note that it is compiled to run on the linux.student.cs.uwaterloo.ca environment. We have also provided
a sample test input file q4/sample.in, and the corresponding output can be found in q4/sample.out. Since the
program doesn’t take command-line arguments, there is no sample.args file.
Implement the described IntSet functions. Your implementation must satisfy the following requirements:
• A set cannot contain duplicate items. Attempting to add an item already in the set does not change the set nor does it
produce an error (see add and operator&).
• init initializes both the capacity and size of the set to 0. Its array pointer is set to nullptr.
• destroy frees all dynamically allocated memory. We will be using valgrind in marmoset to check for memory leaks.
Page 6 of 7
• After add( IntSet & i, int e ) is called, e must be in the set i. When the first integer is added, the capacity
is increased to 5. If at any point the capacity is not enough, it should be doubled. The size of the set goes up by one for
every value added .
• Set intersection (operator&) returns a new set containing only the elements that are in both sets.
• Set union (operator|) returns a new set containing all of the elements from both sets, without any duplicates.
• Two sets A and B are equal (operator==) if and only if no element of one is not an element of the other. More
precisely: (@xs.t.x ∈ A ∧ x /∈ B) ∧ (@xs.t.x ∈ B ∧ x /∈ A).
• isSubset( const IntSet & i1, const IntSet & i2 ) returns true if and only if every element in i2
is an element of the set i1: otherwise it returns false.
• contains( const IntSet & i, int e ) returns true if e is an element of the set i: otherwise it returns
false.
• After remove( IntSet & i, int e ) is called, e must not be in the set i. You are not required to reduce the
array size or capacity in this implementation.
• The input operator (operator>>) initializes the set parameter, and then adds the read-in integers to the set until a
non-integer value is read. The first non-integer character is thrown away.
• The output operator (operator<<) first prints a left parenthesis ’(’, then each integer in ascending order, delimited
by a comma unless it is the last integer, and ends with a right parenthesis ’)’. For example the set containing 3, 5, and
2 is printed as (2, 3, 5). An empty set is printed as ().
(a) Due on Due Date 1: Design a test suite for this program. Submit a file called a2q4.zip that contains the test suite
you designed, called suiteq4.txt, and all of the .in and .out files.
(b) Due on Due Date 2: Write the program in C++. Save your solution in a file named a2q4.cc.
Page 7 of 7