Description

Qsort, Linked List, Binary Tree, Tree Traversal, Expression Order, Syntax Tree, and Recursive Parsing

---

1. qsort

To use qsort, you have to include <stdlib.h>.

---

Usage

void qsort(void *array, size_t count, size_t size, comparison_fn_t compare);

---

qsort an int array

int compare_int(const void *a, const void *b)
{
    const int *va = (const int *)a;
    const int *vb = (const int *)b;

    return *va - *vb;
}

---

qsort a double array

int compare_double(const void *a, const void *b)
{
    const double *da = (const double *)a;
    const double *db = (const double *)b;

    return (*da > *db) - (*da < *db);
}

---

2. Linked List

Node Definition

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 deletion 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;
}

---

3. Binary Tree

Binary Tree Node Definition

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

---

4. Tree Traversal

Traversal Type	Visit Order
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

---

5. Expression Order

Expression Type	Order
Prefix	Operator, left operand, and right operand
Infix	Left operand, operator, and right operand
Postfix	Left operand, right operand, and operator

---

6. Syntax Tree

In a syntax tree, the internal nodes are operators, and the leaves are operands.

---

7. Recursive Evaluation of Prefix Expression

The following is pseudo code for evaluating a prefix Boolean expression.

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;
    }
}

---

8. Grammar of Infix Expression with Parentheses

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

---

9. Syntax Tree Construction from Infix Expression

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

---

Create a New Tree Node

BTNode* makeNode(char c)
{
    int i;

    BTNode *node = (BTNode*)malloc(sizeof(BTNode));

    /* set node->data */
    node->data = c;

    node->left = NULL;
    node->right = NULL;

    return node;
}

---

Parse FACTOR

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;
}

---

Parse EXPR

BTNode* EXPR()
{
    char c;

    BTNode *node = NULL;
    BTNode *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

Discuss