# C Program - 2
## 275. Set
### Task Description
Build a library to process set of numbers from 0 to 63 Since a long long int has 64 bits, we can use a bit to present a number in the set. If the bit is 1 then the corresponding number is in the set, otherwise it is not in the set. You need to implement the following functions for set.

void init(Set *set)
This function set the set to be empty.
void add(Set *set, int i)
This function adds i into the set.
void has(Set set, int i)
This function prints a message to indicate if i
is in a set. For example, if a
is {3,5,2}
and i
is 3
, then it will print set has 3. If a
is {3,5,2}
and i
is 13
, then it will print set does not have 13.
Set setUnion(Set a, Set b)
This function returns the union of sets a
and b
. For example, if a
is {3,5,2}
and b
is {3,7,9}
, then the union of a
and b
is {3,5,2,7,9}
.
Set setIntersect(Set a, Set b)
This function returns the intersection of sets a
and b
. For example, if a
is {3,5,2}
and b
is {3,7,9}
, then the intersection of a
and b
is {3}
.
Set setDifference(Set a, Set b)
This function returns the difference between sets a
and b
. For example, if a
is {3,5,2}
and b
is {3,7,9}
, then the difference of a
and b
is {5,2,7,9}
.
### main.c

#include <stdio.h>
#include "set.h"
 
int main()
{
  Set a, b, c;
 
  init(&a);
  add(&a, 3);
  add(&a, 5);
  add(&a, 2);
 
  init(&b);
  add(&b, 3);
  add(&b, 7);
  add(&b, 9);
 
  c = setUnion(a, b);
  has(c, 2);
  has(c, 3);
  has(c, 5);
  has(c, 7);
  has(c, 9);
 
  c = setIntersect(a, b);
  has(c, 2);
  has(c, 3);
  has(c, 5);
  has(c, 7);
  has(c, 9);
 
  c = setDifference(a, b);
  has(c, 2);
  has(c, 3);
  has(c, 5);
  has(c, 7);
  has(c, 9);
 
  return 0;
}

### set.h

typedef unsigned long long Set;
void init(Set *set);
void add(Set *set, int i);
void has(Set set, int i);
Set setUnion(Set a, Set b);
Set setIntersect(Set a, Set b);
Set setDifference(Set a, Set b);

### Sample output

set has 2
set has 3
set has 5
set has 7
set has 9
set does not have 2
set has 3
set does not have 5
set does not have 7
set does not have 9
set has 2
set does not have 3
set has 5
set has 7
set has 9****

## 224. Supervisors and Subordinates
### Task Description
寫一個程式決定兩個員工的關係。程式的主程式和初始化的函數已寫好，因此你要做的是實作三個輔助函數和判斷關係的函數。三個輔助函數分別是：以名字找員工、以員工編號找員工、找一名員工最頂層的的老闆。

員工的資料我們定義如下：每一個員工有一個唯一的員工號碼 id，姓 last_name，名 first_name，及直屬上司的員工號碼 boss_id。每個員工只有一個直屬上司，而且可以是自己。在這份作業中，我們以一個結構來定義員工資料。
### employee.h

#ifndef _EMPLOYEE_H
#define _EMPLOYEE_H
 
struct employee{
    int id;
    char first_name[32];
    char last_name[32];
    int boss_id;
};
typedef struct employee Employee;
 
void init_storage(Employee **storage, int n);
void free_storage(Employee **storage);
Employee* find_employee_by_id( Employee *set, int n, int id );
Employee* find_employee_by_name( Employee *set, int n, const char *first_name, const char *last_name );
Employee* find_root_boss( Employee *set, int n, Employee *employee );
int check_relationship(Employee *set, int n, Employee *A, Employee *B);
 
#endif

### employee.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "employee.h"
 
void init_storage(Employee **storage, int n)
{
    // allocate memory space to store employee data
    // no need to understand this function now.
 
    (*storage) = (Employee *)malloc(sizeof(Employee) * n);
}
 
void free_storage(Employee **storage)
{
    free(*storage);
    *storage = 0;
}

### main.c
#include <stdio.h>
#include "employee.h"

int main()
{
int n, m;
int i;
Employee *set = NULL;

scanf("%d", &n);
init_storage(&set, n);
for ( i = 0 ; i < n ; i++ )
scanf("%d %s %s %d", &(set[i].id), set[i].first_name, set[i].last_name, &(set[i].boss_id));
char first_name_A[32], first_name_B[32];
char last_name_A[32], last_name_B[32];
Employee *A, *B;
int type;

scanf("%d", &m);
for ( i = 0 ; i < m ; i++ )
{
scanf("%s %s", first_name_A, last_name_A);
A = find_employee_by_name(set, n, first_name_A, last_name_A);

scanf("%s %s", first_name_B, last_name_B);
B = find_employee_by_name(set, n, first_name_B, last_name_B);

type = check_relationship(set, n, A, B);
switch(type){
case 1:
printf("subordinate\n"); break;
case 2:
printf("supervisor\n"); break;
case 3:
printf("colleague\n"); break;
default:
printf("unrelated\n"); break;
}
}
free_storage(&set);
return 0;
}
兩個員工 A 和 B 的關係定義如下：

如果 A 可藉由一連串的「直屬上司」關係連結到 B，則稱 A 是 B 的部屬 (subordinate) 。
如果 B 可藉由一連串的「直屬上司」關係連結到 A，則稱 A 是 B 的長官 (supervisor) 。
如果 A 與 B 並非部屬/長官關係，但存在另一個 C，且 A 與 B 皆為 C 的部屬，則 A 和 B 互為同事(colleague) 關係。
如果以上皆非，則 A 與 B 為無關係 (unrelated)。
### input
輸入的第一行為 n
，代表員工數目。以下 n
行都為員工號碼、姓、名及直屬上司的員工號碼。接下來會有一個數字 m
代表查詢次數，以下 m
行為想查詢的兩個員工姓名。員工的姓名保證存在於輸入中，且代表兩個不同的員工。
### output
輸出有 m
行，每一行為想查詢的兩個員工姓名之間的關係。關於輸入輸出的處理和分工，以及初始化函數的使用，請參閱主程式。
### Limits
0<n≤32,0 < m
### Sample input

6
100 John Smith 200
200 Adam Johnson 300
300 Jane Washington 300
400 Mary Miller 300
500 Eric Page 500
600 James Clark 500
4
John Smith Adam Johnson
Jane Washington Adam Johnson
Adam Johnson Mary Miller
Mary Miller James Clark

### Sample output

subordinate
supervisor
colleague
unrelated

## 109. Tree Path Printing
### Problem Description
Given a binary tree please print all paths from the root to all leaves. A leaf is a node without any child node, and a path is a sequence of node connecting two nodes. For example, in the figure below there are three leaves -- 1, 8 and 15. The path from the root to the leaf 1 is 9 7 1.
You need to implement a function print_all_paths with the following prototype, where you will be given a pointer to the root of the tree.
`void print_all_paths(struct node *root);`
The declaration of struct node is as follows. You do not need to declare it -- you only need to include a node.h header file to use it.
### node.h

#ifndef _NODE_H
#define _NODE_H
 
struct node {
    struct node *left;
    struct node *right;
    int data;
};
 
void print_all_paths(struct node *root);
 
#endif

Note that we will separately compile your submission so you should include stdio.h, node.h, and any other header that you will use. Also you are free to write any helper function in your submission.

The constraints on the parameters are as follow.

The length of a path, i.e., the depth of the tree, is no more than 1000
.
### Input
The input tree will be given as a pointer to the root.

### Output
The output are paths from the root to all leaves. You should output a path as a sequence of nodes (indicated by their data) from the root to the leaf. Two adjacent nodes in a path should be separated by a space character. You should print paths in a left-to-right order.
### main.c

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "node.h"
 
void print_all_paths(struct node *root);
 
struct node *insert_bs_tree(struct node *root, int data)
{
    struct node *current;
    if (root == NULL)
    {
        current = (struct node *)malloc(sizeof(struct node));
        assert(current != NULL);
        current->data = data;
        current->left = NULL;
        current->right = NULL;
        return current;
    }
 
    if (data < root->data)
        root->left = insert_bs_tree(root->left, data);
    else
        root->right = insert_bs_tree(root->right, data);
    return root;
}
 
int main(void)
{
    int n;
    struct node *root = NULL;
 
    while (scanf("%d", &n) != EOF)
        root = insert_bs_tree(root, n);
 
    print_all_paths(root);
}

### Sample input

9 7 1 8 15

### Sample output

9 7 1
9 7 8
9 15

## 87. Merge Lists
### Task Description
Write a program to merge two linked lists. The node of the list has two members -- a data value of type int, and a pointer next pointing to the next node. We assume that there will be no two nodes in the lists having the same data, and the two lists are sorted such that the data in them are in increasing order. Now you need to merge these two lists by reordering nodes in them so that that they appear as one sorted list. That is, when you are given two list (2, 4, 6, 9) and (1, 3, 10), the final list will be (1, 2, 3, 4, 6, 9, 10). The prototype of this function is as follows:

struct node *merge(struct node *list1, struct node *list2);

The two lists are list1 and list2. The head of the final list will be the return value of merge, and it will always be either list1 or list2. We assume that both list1 and list2 are not NULL, and they are both null terminated. Note that you need to sort the list by reordering only, so you are not allowed to declare array or use malloc().
### node.h

#ifndef _NODE_H
#define _NODE_H
 
struct node {
    int value;
    struct node * next;
};
 
struct node * merge(struct node *, struct node *);
 
#endif

### main.c

#include <stdio.h>
#include <stdlib.h>
#include "node.h"
 
#define LEN 1000
 
struct node * build(int v[], int n) {
    struct node * head, * ptr;
    int i;
 
    if (!n)
        return 0;
 
    head = (struct node *) malloc(sizeof(struct node));
    ptr = head;
    head -> value = v[0];
    for (i = 1; i < n; i++) {
        ptr -> next = (struct node *) malloc(sizeof(struct node));
        ptr = ptr -> next;
        ptr -> value = v[i];
    }
    ptr -> next = 0;
    return head;
}
 
void print(struct node * ptr) {
    printf("%d", ptr -> value);
    if (ptr -> next) {
        putchar(' ');
        print(ptr -> next);
    }
}
 
int main() {
    int n1, n2;
    int v1[LEN], v2[LEN];
    int i;
    struct node * list1, * list2;
 
    scanf("%d", &n1);
    for (i = 0; i < n1; i++)
        scanf("%d", &v1[i]);
    scanf("%d", &n2);
    for (i = 0; i < n2; i++)
        scanf("%d", &v2[i]);
    list1 = build(v1, n1);
    list2 = build(v2, n2);
 
    print(merge(list1, list2));
    putchar('\n');
    return 0;
}

### Hint
There is a very clean recursive solution for this problem. Consider the two heads of these two lists. Which node should appear first in the final answer ?

You can download node.h and main.c here, but remember you only need to submit the code of the merge function and the include tags needed (such as node.h).