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
Expression order
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
/*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;
}