Sparse Array en C! Comment l'accomplir? Puis-je attribuer uniquement des parties d'un tableau?

Question

La première question est: "Comment je fais un tableau clairsemé simple en C (avec une seule dimension)?" {avec mes propres mains, sans bibliothèques.}

Et le dernier: "Puis-je attribuer uniquement des parties d'un tableau?"

comme * tableau;

puis utilisez malloc pour allouer des mem pour cela; donc, nous libérons l'index que nous ne voulons pas.

Puis-je le faire?

Merci beaucoup!

Answer 1

Il n'est pas rare de les mettre en œuvre dans des structures liées d'un type ou d'un autre. Dans une dimension, vous pouvez simplement générer une liste chaînée de régions occupées, et j'ai déjà discuté de a two dimensional implementation dans un autre contexte.

Vous perdez O (1) temps d'accès de cette façon, mais la victoire sur l'espace peut être considérable si la structure est vraiment clairsemée.

Answer 2

Non, vous ne pouvez pas le faire.

Ce que vous pouvez faire est d'allouer des blocs, mais vous devez le concevoir avec soin.

Probablement la meilleure optimisation consiste à utiliser des plages de cellules. Vous pouvez donc utiliser une liste chaînée (ou une carte) des gammes disponibles:

struct SparseBlock 
{ 
    void *blockData; 
    int beginIndex; 
    int endIndex; 
    struct SparseBlock *next; 
} 

évidemment, si endIndex - beginIndex = 0 vous avez une seule cellule (qui est isolé à l'intérieur du tableau), sinon vous avez un bloc de cellules, ce qui permet vous pour allouer la bonne quantité de mémoire pour cela.

Cette approche est simple pour les vecteurs rares immuables, sinon vous devez prendre soin de

• restructuration des blocs à chaque fois qu'un trou est rempli ou généré
• simplement stocker des cellules individuelles

En plus vous devez décider comment indexer ces blocs, vous pouvez les garder dans une liste chaînée, ou vous pouvez utiliser une carte pour avoir un temps O (1) constant pour récupérer un nième bloc (bien sûr, vous devrez insérer de nombreuses touches égales pour le même bloc si c'est un varier ou réduire l'indice à l'indice inférieur le plus proche disponible).

Les solutions sont nombreuses, exprimez simplement votre créativité! :)