| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11010 | List class |
|
| 11014 | Encoding and decoding |
|
| 11020 | Binary search trees using polymorphism |
|
| 11439 | Word Manipulator |
|
Description
Let’s implement a list class.
- Task 1:
First you are asked to implement class OWList (standing for “one-way list”). You have definitions of classes ListNode and OWList as follows:
class ListNode
{
friend class OWList; //make OWList a friend
friend class TWList; //make TWList a friend
public:
ListNode( const int &info ) //constructor
: data( info ), nextPtr( NULL )
{
} //end ListNode constructor
private:
int data; //data
ListNode *nextPtr; // next node in list
}; //end class ListNode
class OWList
{
public:
//default constructor
OWList();
//destructor
~OWList();
//insert node at front of list
void insertAtFront( const int &value );
//remove node from front of list
void removeFromFront();
//is List empty?
bool isEmpty() const;
//display contents of List
void print() const;
protected:
ListNode *firstPtr; //pointer to first node
ListNode *lastPtr; //pointer to last node
}; // end class OWList
Requirement: Implement the member functions
1. “OWList::OWList();”: initializes the two pointers firstPtr and lastPtr as NULL.
2. “OWList::~OWList();”: deletes allocated dynamic memory space.
3. “void OWList::insertAtFront( const int &value );”
4. “int OWList::removeFromFront();”
5. “bool OWList::isEmpty() const;”
6. “void OWList::print() const;”
- Task 2:
Implement another class TWList (standing for “two-way list”), which is derived from class OWList:
class TWList:public OWList
{
public:
//default constructor
TWList()
:OWList()
{
/*It will still work correctly if you omit the constructor call of the base class in the above member initializer list. The compiler will invoke this default constructor of OWList implicitly.*/
}
//destructor
~TWList()
{
/*You don't need to delete the list again because the
compiler will invoke the destructor of the base class OWList to do this.*/
}
//insert node at back of list
void insertAtBack( const int &value );
//delete node from back of list
void removeFromBack();
};
Besides the functions inherited from OWList, TWList has two more functions: insert a node at the end of the list and remove a node from the end of the list.
Requirement: Implement the member functions
7. “void TWList:: insertAtBack( const int &value );”
8.“int TWList:: removeFromBack();”
Note:
1. This problem involves three files.
- function.h: Class definitions.
- function.cpp: Member-function definitions.
- main.cpp: A driver program to test your class implementation.
You will be provided with main.cpp and function.h, and asked to implement function.cpp.
#ifndef FUNCTION_H
#define FUNCTION_H
#include <iostream>
class ListNode
{
friend class OWList; //make OWList a friend
friend class TWList; //make TWList a friend
public:
ListNode( const int &info ) //constructor
: data( info ), nextPtr( NULL )
{
} //end ListNode constructor
private:
int data; //data
ListNode *nextPtr; // next node in list
}; //end class ListNode
class OWList
{
public:
//default constructor
OWList();
//destructor
~OWList();
//insert node at front of list
void insertAtFront( const int &value );
//remove node from front of list
void removeFromFront();
//is List empty?
bool isEmpty() const;
//display contents of List
void print() const;
protected:
ListNode *firstPtr; //pointer to first node
ListNode *lastPtr; //pointer to last node
}; // end class OWList
class TWList:public OWList
{
public:
//default constructor
TWList()
:OWList()
{
/*It will still work correctly if you omit the constructor call of the base
class in the above member initializer list. The compiler will invoke this
default constructor of OWList implicitly.*/
}
//destructor
~TWList()
{
/*You don't need to delete the list again because the compiler
will invoke the destructor of the base class OWList to do this.*/
}
//insert node at back of list
void insertAtBack( const int &value );
//delete node from back of list
void removeFromBack();
};
#endif
#include <iostream>
#include <string>
#include "function.h"
using namespace std;
int main()
{
TWList integerList;
int command;
int value; // store node value
while (cin >> command)
{
switch(command)
{
case 1: // insert at beginning
cin >> value;
integerList.insertAtFront(value);
break;
case 2: // insert at end
cin >> value;
integerList.insertAtBack(value);
break;
case 3: // remove from beginning
integerList.removeFromFront();
break;
case 4: // remove from end
integerList.removeFromBack();
break;
}
}
integerList.print();
cout<<endl;
}
2. For OJ submission:
Step 1. Submit only your function.cpp into the submission block.
Step 2. Check the results and debug your program if necessary.
Input
There are four types of command:
- “1 integerA” represents inserting a node with int value A at the head of the list.
- “2 integerB” represents inserting a node with int value B at the end of the list.
- “3” represents removing the node at the head of the list
- “4” represents removing the node at the end of the list
Each command is followed by a new line character.
Input terminated by EOF.
Output
The output should consist of the final state of the list.
Sample Input Download
Sample Output Download
Partial Judge Code
11010.cppPartial Judge Header
11010.hTags
Discuss
Description
The task is to define the class ‘RleCodec’ for run-length encoding.
About implementing the virtual function:
We have the base class ‘Codec’ as an interface. The member functions in ‘Codec’ are pure virtual functions. Therefore we need to implement those virtual functions in the derived class ‘RleCodec’. The functions ‘decode’, ‘show’, ‘is_encoded’ are already done. The only function you need to complete is ‘RleCodec::encode’ in ‘function.cpp’.
In ‘main.cpp’, we see two functions having an argument of type ‘Codec&’:
std::ostream& operator<<(std::ostream& os, Codec& data);
void encode_decode(Codec& data);
Since ‘RleCodec’ is a derived class of ‘Codec’, we may pass an object of ‘RleCodec’ to the above two functions by reference as if it is an object of ‘Codec’. Calling ‘data.show(os);’ will invoke the virtual function of the corresponding derived class.
About run-length encoding:
The rule of run-length encoding is simple: Count the number of consecutive repeated characters in a string, and replace the repeated characters by the count and a single instance of the character. For example, if the input string is ‘AAADDDDDDDBBGGGGGCEEEE’, its run-length encoding will be ‘3A7DBB5GC4E’, because there are three A’s, seven D’s, … etc. Note that we do not need to encode runs of length one or two, since ‘2B’ and ‘1C’ are not shorter than ‘BB’ and ‘C’.
In ‘function.h’, we add the class ‘DummyCodec’ as a sample of implementing a derived class of the base class ‘Codec’. You do not need to change anything in ‘function.h’. The only function you need to write for this problem is the function ‘RleCodec::encode’ in ‘function.cpp’.
Hint: std::stringstream could be useful in solving this problem. Please refer to ‘RleCodec::decode’ for how to use std::stringstream.
You only need to submit ‘function.cpp’. OJ will compile it with ‘main.cpp’ and ‘function.h’.
We have already provided partial function.cpp belowed.
Note that if you can't use "auto".
For codeblock, go to the codeblock menu Settings --> Compiler ... --> Compiler flags and check Have g++ follow the C++11 ISO C++ language standard [-std=c++11]
For command line compiler, use g++ myprog.cpp -std=c++11 -o myprog
main.cpp
function.h
function.cpp
Input
A line contains of several characters .
Output
There are four lines.
The first and second lines are dummy encoding and decoding. You don't need to implement it.
The third and forth lines are RLE encoding and decoding.
Each line is followed by a new line character.
Sample Input Download
Sample Output Download
Partial Judge Code
11014.cppPartial Judge Header
11014.hTags
Discuss
Description
If you are not familiar with partial judge , please check this handout
A. Definition of Binary Search Trees
A binary search tree (BST) is a binary tree, whose internal nodes each store a key and each have two sub-trees, commonly denoted left and right. The tree additionally satisfies the property: the key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in the right sub-tree.
Based on the above property of BSTs, when a node is to be inserted into an existing BST, the location for the node can be uniquely determined. For example, if a node with key 6 needs to be inserted into the following BST
the BST will become
B. Implementation of the BST Data Structure
There are two approaches to BST implementation: array and linked list.
1. Array:
An approach to storing a BST is to use a single, contiguous block of memory cells, i.e., an array, for the entire tree. We store the tree’s root node in the first cell of the array. (Note that, for ease of implementation, we ignore the 0th cell and start from the 1st cell.) Then we store the left child of the root in the second cell, store the right child of the root in the third cell, and in general, continue to store the left and right children of the node found in cell n in the cells 2n and 2n+1, respectively. Using this technique, the tree below
would be stored as follows
2. Linked list:
We set a special memory location, call a root pointer, where we store the address of the root node. Then each node in the tree must be set to point to the left or right child of the pertinent node or assigned the NULL value if there are no more nodes in that direction of the tree.
C. Detailed C++ Implementation for BST
Let’s see how the BST data structure can be realized in C++.We have two different approaches to BST implementation: array and linked list. Thus, we define four classes and use polymorphism as follows:
function.h
main.cpp
REQUIREMENTS:
Implement the constructor, insert(), search() member functions of both the Array_ BST and List_ BST classes and createLeaf(), deleteTree() of List_ BST class.
Note:
1. This problem involves three files.
- function.h: Class definitions.
- function.cpp: Member-function definitions.
- main.cpp: A driver program to test your class implementation.
You will be provided with main.cpp and function.h, and asked to implement function.cpp.
2. For OJ submission:
Step 1. Submit only your function.cpp into the submission block.
Step 2. Check the results and debug your program if necessary.
Input
There are four kinds of commands:
- “I A”: insert a node with int value A into the BST
- “S A”: if the integer A exists in the BST, print “yes”; otherwise, print “no”.
- “P”: show the current content of the BST.
- “H”: print the BST’s height.
Each command is followed by a new line character.
Input terminated by EOF.
Output
The output shows the result of each command.
When the BST is empty, you don’t need to print anything except a new line character.
Sample Input Download
Sample Output Download
Partial Judge Code
11020.cppPartial Judge Header
11020.hTags
Discuss
Description
In this problem, a user can input some “words”, set their formats, and change their contents.
The program architecture is explained as follows.
A. Definition of class Formatter
- Consider a Formatter as a capability to format a string.
- Different Formatters will use different ways to format a string.
- Derived classes
- Uppercase
- After formatted, the resultant string will be uppercase.
- Lowercase
- After formatted, the resultant string will be lowercase.
- Marked
- After formatted, the resultant string will be [given string].
- Uppercase
B. Definition of class Word
- A Word contains a string and a Formatter.
C. Definition of class Handler
- Consider a Handler as a capability to operate two Words.
- Different Handlers will use different ways to operate two Words.
- Derived classes
- Swap Handler
- After operation, two Words will exchange their strings and Formatters.
- Attach Handler
- After operation, the second Word’s string will be appended to the first Word’s string.
- Swap Handler
D. Definition of class Word Manipulator
- A Word Manipulator maintains a doubly linked list of several Words.
- A Word Manipulator has a Swap Handler and an Attach Handler. We can switch the mode of a Word Manipulator to change the current Handler.
Note:
1. This problem involves three files.
- function.h: Class definitions.
- function.cpp: Member-function definitions.
- main.cpp: A driver program to test your class implementation.
You will be provided with main.cpp and function.h, and asked to implement function.cpp.
2. You need to implement
- Uppercase:
- string format(const string &str)
- Lowercase:
- string format(const string &str)
- Marked:
- string format(const string &str)
- Word:
- const Word &operator=( const Word &w)
- SwapHandler:
- void handle(Word &w1,Word &w2)
- AttachHandler:
- void handle(Word &w1,Word &w2)
- WordManipulator:
- void switchMode()
- void readWords()
3. For OJ submission:
Step 1. Submit only your function.cpp into the submission block.
Step 2. Check the results and debug your program if necessary.
Input
First part:
- Each line has a command and a string. You have to read the string to a Word and set a corresponding Formatter to it according to the command.
- A command e means the end of the first part.
- Commands
- u
Use Uppercase
- l
Use Lowercase
- m
Use Marked
Second part:
There are two kinds of commands
- s
- Switch the mode of Word Manipulator.
- o n m
- Let Word Manipulator operate (n, m) where n and m are the indices of two Words.
Output
Show the result of Word Manipulator.