Tableau épars en C! Comment l’accomplir? Puis-je allouer seulement des parties d’un tableau?

La première question est: “Comment faire un tableau fragmenté simple en C (avec une seule dimension)?” {avec mes propres mains, sans bibliothèques.}

Et le dernier: “Puis-je allouer seulement des parties d’un tableau?”

comme * array;

Ensuite, utilisez malloc pour allouer quelques membres à cela; alors, nous libérons l’index que nous ne voulons pas.

Puis-je le faire?

Merci beaucoup!

Non, tu ne peux pas le faire.

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

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

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

évidemment, si endIndex - beginIndex = 0 vous avez une seule cellule (isolée dans le tableau), sinon vous avez un bloc de cellules, ce qui vous permet d’allouer la quantité de mémoire appropriée.

Cette approche est simple pour les vecteurs rares immuables, sinon vous devriez vous occuper de

  • restructurer les blocs chaque fois qu’un trou est rempli ou généré
  • juste stocker des cellules simples

En outre, vous devez décider comment indexer ces blocs, les classer dans une liste chaînée ou les utiliser sur une carte pour obtenir un temps constant O (1) permettant de récupérer un nième bloc (bien sûr, vous aurez insérer plusieurs clés égales pour le même bloc s’il s’agit d’une plage ou réduire l’index à l’index le plus proche disponible).

Les solutions sont nombreuses, il suffit d’exprimer votre créativité! 🙂

Il n’est pas rare de les implémenter 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à évoqué une implémentation bidimensionnelle dans un autre contexte.

Vous perdez ainsi O (1) du temps d’access, mais la victoire sur l’espace peut être considérable si la structure est vraiment rare.