Description

Array.cpp
// overloaded assignment operator;
// const return avoids: ( a1 = a2 ) = a3
const Array &Array::operator=( const Array &right )
{
   if ( &right != this ) // avoid self-assignment
   {
      // for Arrays of different sizes, deallocate original
      // left-side Array, then allocate new left-side Array
      if ( size != right.size )
      {
         delete [] ptr; // release space
         size = right.size; // resize this object
         ptr = new int[ size ]; // create space for Array copy
      } // end inner if

      for ( size_t i = 0; i < size; ++i )
         ptr[ i ] = right.ptr[ i ]; // copy array into object
   } // end outer if

   return *this; // enables x = y = z, for example
} // end function operator=

// determine if two Arrays are equal and
// return true, otherwise return false
bool Array::operator==( const Array &right ) const
{
   if ( size != right.size )
      return false; // arrays of different number of elements

   for ( size_t i = 0; i < size; ++i )
      if ( ptr[ i ] != right.ptr[ i ] )
         return false; // Array contents are not equal

   return true; // Arrays are equal
} // end function operator==

// overloaded subscript operator for non-const Arrays;
// reference return creates a modifiable lvalue
int &Array::operator[]( int subscript )
{
   // check for subscript out-of-range error
   if ( subscript < 0 || subscript >= size )
      throw out_of_range( "Subscript out of range" );

   return ptr[ subscript ]; // reference return
} // end function operator[]

// overloaded subscript operator for const Arrays
// const reference return creates an rvalue
int Array::operator[]( int subscript ) const
{
   // check for subscript out-of-range error
   if ( subscript < 0 || subscript >= size )
      throw out_of_range( "Subscript out of range" );

   return ptr[ subscript ]; // returns copy of this element
} // end function operator[]

// overloaded input operator for class Array;
// inputs values for entire Array
istream &operator>>( istream &input, Array &a )
{
   for ( size_t i = 0; i < a.size; ++i )
      input >> a.ptr[ i ];

   return input; // enables cin >> x >> y;
} // end function

// overloaded output operator for class Array
ostream &operator<<( ostream &output, const Array &a )
{
   // output private ptr-based array
   for ( size_t i = 0; i < a.size; ++i )
   {
      output << setw( 12 ) << a.ptr[ i ];

      if ( ( i + 1 ) % 4 == 0 ) // 4 numbers per row of output
         output << endl;
   } // end for

   if ( a.size % 4 != 0 ) // end last line of output
      output << endl;

   return output; // enables cout << x << y;
} // end function operator<<

Inheritance type	Public	Protected	Private
Public data/ functions in the base class	Public in the derived class	Protected in the derived class	Private in the derived class
Protected data/ functions in the base class	Protected in the derived class	Protected in the derived class	Private in the derived class
Private data/fun in the base class	Not accessible in the derived class	Not accessible in the derived class	Not accessible in the derived clas

 
 
 
 
 
 

 

 

 

 

 

Polymorphism
  In the base class
  virtual void foo();
  In the derived class
  virtual void foo() override;

Abstract class and pure virtual function
  virtual void foo() =0;

Prefix/postfix operators
  complex &operator++();  // prefix
  complex operator++(int); // postfix

Operator overloading
  Binary operators
  /*1.non-static member function */
     complex operator+ (const complex&);
  /* 2. non-member function */
     friend complex operator* (const
                      complex&, const complex&);
  Unitary operators
  /*1.non-static member function */
      complex operator-();
  /*2. non-member function */
      friend complex operator~(const complex&);

Inheritance
  class A {
  // A is a base class }
  class B: public A {
  // B inherits A.
  // B is a derived class}

Dynamic allocation
  int *ptr = new int;
  delete ptr;
  int *ptr = new int[100];
  delete [] ptr;

String object
  #include<string>
  using namespace std;
  ...
  string str1 = "Hello";
  string str2 = "World";

Standard C++ Library - <string>

operator[]	For string a, a[pos]: Return a reference to the character at position pos in the string a.
operator+=	Append additional characters at the end of current string.
operator+	Concatenate strings.
operator<	Compare string values. For string a and b, a < b: if a is in front of b in dictionary order, return 1, else return 0.
operator>	Compare string values. For string a and b, a > b: if a is in back of b in dictionary order, return 1, else return 0.
operator==	Compare string values. For string a and b, a == b: if equal, return 1, else return 0;
operator!=	Compare string values. For string a and string b, a != b: if not equal, return 1, else return 0;
compare()	Compare string. For string a and b, a.compare(b): if equal, return 0. If string a is in front of string b in dictionary order, return -1. If string a is in back of string b in dictionary order, return 1.
length()	Return length of string.
swap()	Swap string values.
push_back()	For string a, a.push_back(c): append character c to the end of the string a, increasing its length by one.

 

Standard C++ Library - <sstream>

operator<<	Retrieves as many characters as possible into the stream.
operator>>	Extracts as many characters as possible from the stream.
str	Returns a string object with a copy of the current contents of the stream.

For example(1):
stringstream ss{“Hello”};    // constructor
string str = ss.str();    // a = “Hello”

For example(2):
stringstream ss;
ss<<”75”;
ss<<”76”;
int num;
ss>>num;    // num = 7576

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Run-Length Encoding(RLE) is implemented as class "RleCodec".

 

More about RLE : 

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’.

 

As we have practiced RLE before, the functions you need to compete are "RleCodec::encode" and "RleCodec::decode".  

Functions "show" , " is_encoded " are already done for you.

 

You may take the class "DummyCodec" as a sample of implementing a derived class of the base class "Codec". You should not change anything in "function.h". 

 

Hint: std::stringstream could be useful in solving this problem. For more details, you may see cheatsheet.

 

Note : 

       1. You only need to submit ‘function.cpp’, since it's a partial judge. Partial Code is provided.

        2. Note that if you can't use "auto".

            a.) 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]

             b.) For command line compiler, use g++ myprog.cpp -std=c++11 -o myprog

        3. For OJ submission, you may choose c++ 11 as your compiler.

 

You may include these library in 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

11940.cpp

Partial Judge Header

11940.h

Tags

Discuss

Description

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

---

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.

---

REQUIREMENTS:

Implement the destructor, insert(), search(), and height() member functions of both the Array_ BST and List_ BST classes.

Input

There are four kinds of commands:

• “I A”: insert a node with int value A(A>0) 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 in Level-order.
• “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 (in both Array and LinkedList method) of each command.

When the BST is empty, you don’t need to print anything except a new line character.

But there's already a new line character in the main function, so you don't have to do anything.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11941.cpp

Partial Judge Header

11941.h

Tags

Discuss

Description

Create a class Polynomial. The internal representation of a Polynomial is an array of terms. Each term contains a coefficient and an exponent, e.g., the term 2x⁴ has the coefficient 2 and the exponent 4.

 

Provide public member functions that perform each of the following tasks:

1. Adding two Polynomial.
2. Subtracting two Polynomial.
3. Multiplying two Polynomial.

Input

 

There are four lines. 

The first two lines represent the greatest power and the corresponding coefficients of the first polynomial.

The last two lines represent the greatest power and the corresponding coefficients of the second polynomial.

The greatest power is in the range of 0-25.

Note that the coefficients are in descending order and each element is separated by a space.

Output

 

Output the coefficients of the sum, difference and product of these two polynomials in descending order.

If the result of coefficient is 0, just print it.

 

Note that there is a new line character at the end of each answer.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11942.cpp

Partial Judge Header

11942.h

Tags

Discuss

Description

A queue is an abstract data type that serves as a collection of elements, where nodes are removed only from the head of the queue and are inserted only at the tail of the queue. Two principal operations can be used to manipulate a queue: enqueue, which inserts an element at the tail, and dequeue, which removes the element at the head of the collection.

 

And now yod need to do the additional command  "empty" , that means you need to empty the queue

Let’s see how the queue data structure can be realized in C++.We have an approach to implement queue: linked list. Thus, we define a class as follows:

 class List_queue {

    public:

        List_queue();

        ~List_queue();

        void enqueue(const int &);

        void dequeue();

        void print();

        void emptys();

    private:

        ListNode *head;

        ListNode *tail;

};

where List_queue implements the queue data structure.

REQUIREMENTS:

Implement the constructor, destructor, enqueue(), dequeue() and print() member functions of the List_queue 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.

function.h

#ifndef FUNCTION_H #define FUNCTION_H #include <iostream> class ListNode { friend class List_queue; //make List_queue a friend public: ListNode( const int &info ) //constructor : data( info ), nextPtr( NULL ), prevPtr( NULL ) { } //end ListNode constructor private: int data; //data ListNode *nextPtr; // next node in list ListNode *prevPtr; }; //end class ListNode class List_queue { public: List_queue(); ~List_queue(); void enqueue(const int &); void dequeue(); void print(); void emptys(); private: ListNode *head; ListNode *tail; }; #endif

main.cpp

int main(){ List_queue L_queue; char command[10]; int n; while(cin>>command){ if(strcmp(command,"dequeue")==0){ L_queue.dequeue(); }else if(strcmp(command,"enqueue")==0){ cin >> n; L_queue.enqueue(n); } else if (strcmp(command , "empty") == 0){ L_queue.emptys() ; }else if(strcmp(command, "print") == 0){ L_queue.print(); cout << endl; } } return 0; }

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 three kinds of commands:

• “enqueue integerA” represents inserting an element with int value A at the tail of the queue.
• “dequeue” represents removing the element at the head of the queue.
• “print” represents showing the current content of the queue.
• “empty” represents empty the queue

Each command is followed by a new line character.

Input terminated by EOF.

Output

The output should consist of the current state of the queue.

When the queue is empty, you don’t need to print anything except a new line character.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11946.cpp

Partial Judge Header

11946.h

Tags

Discuss