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

typedef struct pair {        int key, value;    } pair;

typedef struct sparse {
        int size, pos;
        pair *p;
}  sparse;

void sparse_free(sparse *s);
sparse *sparse_create(void);
int sparse_get(sparse *s, int key);
int sparse_set(sparse *s, int key, int value);

int main(void)
{
        int n;
        sparse *s=sparse_create();

        // Add a bunch of random elements to the sparse array
        // Keys will be numbers 0 through 7.  Values will be 0 through 10.
        for(n=0; n<10; n++)     sparse_set(s,rand()%8, n);
        // Find everything that was set.  Absent items will show as -1
        for(n=0; n<8; n++)      printf("key %d value %d\n", n, sparse_get(s, n));

        // Print the literal contents of the array raw
        printf("\nContents of sparse array\n");
        for(n=0; n<s->pos; n++)
                printf("I %d\tK %d\tV %d\n", n, s->p[n].key, s->p[n].value);

        sparse_free(s);
        return(0);
}

sparse *sparse_create(void)
{
        sparse *s=malloc(sizeof(sparse));
        if(s == NULL) return(NULL);

        s->size=16;     s->pos=0;
        s->p=malloc(sizeof(pair)*16);
        return(s);
}

int sparse_get(sparse *s, int key)
{
        int n;
        for(n=0; n<s->pos; n++) if(s->p[n].key == key) return(s->p[n].value);

        return(-1);
}

int sparse_set(sparse *s, int key, int value)
{
        int n;

        // Hunt for key.  If found, just update and return.
        for(n=0; n<s->pos; n++)
        if(s->p[n].key == key)
        {
                s->p[n].value=value;
                return(0);
        }

        // Add 16 more elements if full
        if(s->pos >= (s->size - 1))
        {
                pair *p=realloc(s->p, sizeof(pair) * (s->size+16));
                if(p == NULL) return(-1);
                s->size += 16;
                s->p=p;
        }

        // Add to end.
        s->pos++;
        s->p[s->pos].key=key;
        s->p[s->pos].value=value;
        return(0);
}

void sparse_free(sparse *s){ if(s) { free(s->p); free(s); } }

$ gcc sparse.c
$ ./a.out

key 0 value 0
key 1 value 8
key 2 value 6
key 3 value 3
key 4 value 7
key 5 value -1
key 6 value 1
key 7 value 5

Contents of sparse array
I 0     K 0     V 0
I 1     K 7     V 5
I 2     K 6     V 1
I 3     K 1     V 8
I 4     K 3     V 3
I 5     K 2     V 6
I 6     K 4     V 7

$