Description

Linked list

typedef struct _Node {
    int data;
    struct _Node *next;
} Node;

 

/* print the content of the linked list.*/

void printList(Node *head)
{
    Node *temp;
    for(temp=head; temp!=NULL; temp=temp->next) {
        printf("%d ", temp->data);
    }
}

/*Insert a node after the node pointed by nd.

Return 1 if insertion succeeds.
Otherwise, return 0.*/

int insertNode(Node* nd, int data)
{
    if (nd != NULL) {

        Node* temp = (Node*)malloc(sizeof(Node));
        temp->data = data;
        temp->next = nd->next;
        nd->next = temp;
        return 1;
    }
    return 0;
}

 

/*Delete a node after the node pointed by nd.

Return 1 if insertion succeeds. 

Otherwise, return 0.*/

int deleteNode(Node* nd)
{
    if (nd != NULL) {
        Node* temp = nd->next;
        if (temp != NULL) {
            nd -> next = temp->next;
            free(temp);
            return 1;
        }
    }
    return 0;
}

 

Binary tree

typedef struct _node {
     int data;
     struct _node *left, *right;
} BTNode;

 

Tree traversal

• Pre-order: visit root, left subtree, and right subtree
• In-order: visit left subtree, root, and right subtree
• Post-order: visit left subtree, right subtree, and root

 

Expression order

• Prefix:  operator, left operand,and right operand
• Infix:  left operand, operator, and right operand
• Postfix: left operand, right operand, and operator

 

Syntax tree

The internal nodes are operators, and the leaves are operands.

Recursive evaluation of prefix expression

/*It is a pseudo code */

int evalBoolExpr(){

char c = getchar();

If c is an operator

   op1 = evalBoolExpr();

   op2 = evalBoolExpr();

   return op1 c op2;

Else if c is a variable

   return the value of c;

}

Grammar of infix expression with parenthesis

• EXPR = FACTOR| EXPR OP FACTOR
• FACTROR = ID | (EXPR)

 

/*Suppose expr[] is an array of expression and pos is the current position, which initially is strlen(expr)-1. */

/*-------------------------------------*/

BTNode* makeNode(char c)
{
    int i;
    BTNode *node = (BTNode*)malloc(sizeof(BTNode));
    set node->data
    node->left = NULL;
    node->right = NULL;
    return node;
}

 

/*-------------------------------------*/

BTNode* FACTOR()
{
    char c;
    BTNode *node = NULL;
    if (pos>=0) {
        c = expr[pos--];
        if (c is an ID) {
            node = makeNode(c);
        } else if (c==‘)’) {
            node = EXPR();
            if(expr[pos--]!= '(') {
                printf("Error!\n");
                freeTree(node);
            }
        }
    }
    return node;
}

 

/*-------------------------------------*/

BTNode* EXPR()
{

    char c;

    BTNode *node = NULL, *right=NULL;

    if (pos>=0) {

        node = right = FACTOR();

        if (pos>0) {

            c = expr[pos];

            if (c is an operator) {

                node = makeNode(c);

                node->right = right;

                pos--;

                node->left = EXPR();

            }

        }

    }

    return node;

}

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Create a class Matrix to represent an N * N matrix.

 

Provide public member functions that perform or derive:

     1) Matrix(const Matrix &);  // copy constructor

 

     2) Overload the stream extraction operator (>>) to read in the matrix elements.

 

    3)  Overload the stream insertion operator (<<) to print the content of the matrix row by row.

 

     4)  Default constructor

 

    5)  Overload the operator (=) to assign value to matrix.

         Note that all of the integers in the same line are separated by a space, and there is a new line character at the end of each line.

 

Note:

1.  This problem involves three files.

• function.h: Class definition of Matrix.
• function.cpp: Member-function definitions of Matrix.
• main.cpp: A driver program to test your class implementation.

You will be provided with function.h and main.cpp, and asked to implement 

 

2. For OJ submission:

       Step 1. Include function.h into function.cpp and then implement your function.cpp. (You don’t need to modify function.h and main.cpp)

       Step 2. Submit the code of function.cpp into submission block.

       Step 3. Check the results and debug your program if necessary.

Input

The first line has an integer N (1<=N<=50), which means the size of the matrix. The total number of elements in the matrix is thus N * N.

 

For the next N lines specify the elements of the matrix a. All of the integers in the same line are separated by a space.

Output

Your program should print the corresponding results followed by a new line character.

Sample Input  Download

Sample Output  Download

Partial Judge Code

12286.cpp

Partial Judge Header

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

 

Let’s see how the BST data structure can be realized in C++ using a linked structure. We define three classes and use polymorphism as follows:

 

function.h

#ifndef function_h #define function_h #include <iostream> #include <math.h> using namespace std; class BST{ public: BST():Height(0){} virtual ~BST() {} virtual void insert(const int &) = 0; virtual void print() const = 0; int height() const { return Height; }// An empty tree has height of 0. A tree with only root node has height of 1. protected: int Height; }; class ListNode{ friend class List_BST; //make List_BST a friend public: ListNode(const int &info):key( info ),left( NULL ),right( NULL ) //constructor { }//end ListNode constructor private: int key; ListNode *left; ListNode *right; };//end class ListNode class List_BST : public BST{ public: List_BST() : BST(), root(NULL) { } virtual ~List_BST() {} virtual void insert(const int &) override; virtual void print() const override{ printIncOrder(root); } private: ListNode *root; // private member functions ListNode* createLeaf(int key) const; //new a ListNode and return its address void printIncOrder(ListNode* Ptr) const { if(Ptr!=NULL) { printIncOrder(Ptr->left); cout<<Ptr->key<<" "; printIncOrder(Ptr->right); } } }; #endif /* function_h */

main.cpp

#include <iostream> #include <string.h> #include "function.h" using namespace std; void BSTManipulator(BST& bstobj, char cmd ){ int n; if (cmd == 'I') { cin >> n; bstobj.insert(n); }else if (cmd == 'H'){ cout << bstobj.height() << endl;; }else if (cmd == 'P'){ bstobj.print(); cout << endl; } } int main(){ List_BST bst; char cmd; while (cin >> cmd) BSTManipulator(bst, cmd); return 0; }

 

where

1. Class BST serves as the abstract base class for realizing polymorphism
2. List_ BST provide an approach to implementing the BST data structure

 

REQUIREMENTS:

1. Implement the insert and createLeaf member functions of the 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 three kinds of commands:

• “I A”: insert a node with int value A(A>0) into the BST. If the key already exists, you simply do nothing.
• “P”: show the current content of the BST.
• “H”: print the BST’s height. Remember if the BST is empty, the height is 0 and you should print “0”.

Each command is followed by a new line character.

Input terminated by EOF.

Output

The output shows the result of each command.

Sample Input  Download

Sample Output  Download

Partial Judge Code

12287.cpp

Partial Judge Header

12287.h

Tags

Discuss