50008. Pointer Chasing

I'm a slow walker, but I never walk backwards.

Problem description

You need to collect a set of non-zero integers from memory. Unfortunately these non-zero integers are scattered so we use a special structure to know where they are. The basic element of this structure is called a set. Each set is stored in consecutive memory locations, and ends with a 0. As a result when you know the starting address of a set, you can get all of them by keep getting the next integer, and repeat until you reach a 0.

The next level of this structure is an integer pointer array called set array. Each element of this array is a pointer to the starting address of a set describe earlier. Similar to the set, a set array ends in NULL.

The next level of this structure is a pointer array called set matrix. Each element of this array is a pointer to the starting address of a set array earlier. Similar to the set, a set matrix ends in NULL.

Now given the starting address of a set matrix, please print all numbers. You must output numbers one set array after one set array. Within a set array it is one set after one set. Within a set it is from low address to high address.

image
               +-----+-----+-----+-----+-----+-----+-----+
set matrix ptr | [0] | [1] | [2] | [3] | [4] | [5] | NULL|
               +--+--+-----+-----+-----+-----+-----+-----+
                  |
                  |
                  v
                  +-----+-----+-----+-----+-----+-----+
set array ptr[0]  | [0] | [1] | [2] | [3] | [4] | NULL|
                  +-----+-----+--+--+-----+-----+-----+
                                 |
                                 |
                                 v
                             +---+-+-----+-----+-----+-----+-----+
              set ptr[0][2]  | [0] | [1] | [2] | [3] | [4] |  0  |
                             +-----+-----+-----+-----+-----+-----+

The prototype of the function you need to implement is as follows.

void processSetMatrix(int ***ptr);

main.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "setmatrix.h"
 
int main() {
    int n;
    scanf("%d", &n);
    {
        int ***setmtx = (int ***) malloc(sizeof(int**) * (n + 1));
        int setarr_sz, set_sz;
        setmtx[n] = NULL;
        for (int i = 0; i < n; i++) {
            scanf("%d", &setarr_sz);
            setmtx[i] = (int **) malloc(sizeof(int *) * (setarr_sz + 1));
            setmtx[i][setarr_sz] = NULL;
            for (int j = 0; j < setarr_sz; j++) {
                scanf("%d", &set_sz);
                setmtx[i][j] = (int *) malloc(sizeof(int) * (set_sz + 1));
                setmtx[i][j][set_sz] = 0;
                for (int k = 0; k < set_sz; k++) {
                    scanf("%d", &setmtx[i][j][k]);
                    assert(setmtx[i][j][k] != 0);
                }
            }
        }
        processSetMatrix(setmtx);
 
    }
    return 0;
}

setmatrix.c

1
2
3
4
5
6
#include <stdio.h>
#include "setmatrix.h"
 
void processSetMatrix(int ***ptr) {
    // add your code
}

Technical Specification and constraints

  • 10 pt. There is only one set array, which has only one set, which has one number.
  • 40 pt. There is only one set array, which may have multiple sets.
  • 50 pt. There could be multiple set arrays.

Sample Input

2
3
  3 1 3 5
  2 2 8
  1 8
4
  4 1 3 5 2
  3 1 2 8
  1 7
  4 5 5 6 6

Sample Output

1 3 5 2 8 8 1 3 5 2 1 2 8 7 5 5 6 6

Discussion