| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11020 | Binary search trees using polymorphism |
|
| 11021 | Encoding and decoding |
|
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
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 ‘QCAQGDQBBQEGQACQDE’, where QCA means that there are 3 A’s and 3 can be encoded as C (the third character in alphabet), QGD means that there are 7 D’s and 7 can be encoded as G (the 7 th character in alphabet), and QBB means we have 2 B’s and 2 can be encoded as B (the second character in alphabet) … etc. Note that every encoding segment starts with a Q.
If there are 27 A’s in a string, it is separated into two segments ‘QZAQAA’, which means the first segment ‘QZA’ represents 26 A’s, and the second segment ‘QAA’ represents 1 A.
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 .(n <= 100)
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.