Direi che basta fare un semplice array di n elementi, ognuno dei quali è un puntatore ad una struct negozio.

In questo modo, se controlli il locale x e scopri che è NULL, significa che lo spazio è libero. Altrimenti, hai il puntatore alla struttura del negozio aperto in quel locale e puoi verificare i prezzi.
La ricerca in questa lista è semplice, in quanto basta saltare i puntatori NULL.

Questo però non credo che sia molto efficiente se si inizia ad avere n e m piuttosto alti: di che cifre stiamo parlando?