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

[Partial Judge Problem]

Problem description:

We define a Josephus game as follows:

1. There are n people , numbered as 1 to n, in a circle and arranged in clockwise.

2. The person with ID = 1 is the killer at the beginning of the game.

3. If the number of survivor is even :

     The killer will kill the person who is oppisite from himself .

     The person next to the victim in clockwise direction will be the new killer.

     Ex: If there are 4 people in the game , the 1st victim will be 3 .

          4 will become the new killer.

                     1(killer)                                                      1

              4                   2               ----->              4(killer)            2

                     3(victim)

4. If the number of survivor is odd :

    The killer will kill the person next to himself in counter-clockwise direction.

    The person next to the victim in counter-clockwise direction will be the new killer.

         Ex:

                         1                                                         1(killer)

           4(killer)          2(victim)       ----->            4

 

5. The winner is the one survive at the end of the game.

Judge language : C

Your task is to implement following functions  :

1.  (Required) Node* createList(int n, Node*);
2.  (Required) int solveJosephus(int numOfPeople , Node* head);
3. (Optional) other functions you will need

Submit format:

#include <stdio.h>
#include <stdlib.h>
#include "function.h"

//------------------------------------------

/*Other functions*/

//------------------------------------------

int solveJosephus(int n , Node* head){

      /*your code here*/

}

Node* createList(int n , Node* head){

    /*your code here*/

}

Input

There are multiple lines in an input testcase .

Each line represents a Josephus game

Each line contains an integer indicates the number of people joining the josephus game.

The input format is determined by the judge code

You don't have to worry about it.

Output

Show the winner of each josephus game.

The output format is determined by the judge code.

You don't have to worry about it . 

Sample Input  Download

Sample Output  Download

Partial Judge Code

11380.c

Partial Judge Header

11380.h

Tags

Discuss

Description

This is a partial judge problem (Judge Language :  C)

Please download the partial judge code and header.

Then, implement 2 functions : buildTree() and showPreorder()

You have to build the binary tree according to its inorder and postorder.

Next , print out the preorder of the binary tree!

 

Submit format:

#include <stdio.h>

#include <stdlib.h>

#include "function.h"

Node* buildTree(int* inorder, int* postorder, int inorder_start, int inorder_end){

        /*YOUR CODE HERE*/

}

void showPreorder(Node* root){
      /*YOUR CODE HERE*/

}

Input

There are 3 lines for inputs.

The first line contains an integer N , which indicates the number of nodes of the binary tree.

The second line is the inorder traversal of the binary tree

The third line is the postorder traversal of the binary tree

※Note that there are not duplicated integers in the binary tree

Output

Print out the preorder traversal of the binary tree.

Note that :

1.There is an whitespace between each integer. 

2.There is an whitespace after the last integer.

3.Threre is no need to add "\n" at last 

 

Sample Input  Download

Sample Output  Download

Partial Judge Code

11381.c

Partial Judge Header

11381.h

Tags

Discuss

Description

Give a postfix expression, which only has 2 operators, ‘+’ and ‘-’,and positive integers. Print the result.

Input

The input contains exactly 1 sequences of postfix expression. It contains operators, ‘+’ and ‘-’,and positive integers separated by a space.

The length of input sequence is smaller than or equal to 40

Output

The output is the result of the expression. (Without a newline symbol)

Sample Input  Download

Sample Output  Download

Tags

Discuss