placer une valeur dans la position triée immédiatement

Question

J'ai une question pour une affectation de laboratoire C++ que j'ai. La tâche consiste à implémenter une fonction pour ajouter des valeurs, supprimer des valeurs d'un tableau et ainsi de suite. Je l'ai fait la plupart du temps maintenant, mais j'ai un problème avec la fonction d'insertion. L'affectation nécessite que j'insère des valeurs flottantes dans ce tableau sans utiliser d'algorithme pour le trier après chaque insertion. Je ne peux pas utiliser quoi que ce soit de STL non plus. Cela supposera que j'insère immédiatement toutes les valeurs en position triée

Je me demande si quelqu'un pourrait me donner une idée de la façon dont ce problème peut être résolu?

EDIT Cette affectation Je ne vais pas l'implémenter avec une liste chaînée. Ce sera pour ma prochaine affectation.

J'ai essayé d'écrire une fonction d'insertion en fonction de votre pseudo code. Je ne l'ai pas compris correctement. Voici le code de toute façon.

void array_insert(data_t list[], int& space_used, data_t value) 
{ 

    if(space_used == 0) 
    { 
     list[space_used] = value;  
    } 
    else 
    { 

     for(int i = space_used+1; i >= 0; i--) 
     { 
     if(value > list[i]) 
     { 
      list[i+1] = value; 
      break; 
     } 
     else 
     { 
      list[i+1] = list[i]; 
     } 
     if(i == 0) 
     { 
      list[i] = value; 
     } 
     } 
    } 
    space_used++; 
} 

enfin terminé, voici le code complet. Merci pour l'aide de Mark et Casablanca

Answer 1

Vous devez décaler tous les éléments pour faire de la place pour le nouvel élément. C'est une opération O (n). Puisque vous ne pouvez pas faire mieux que O (n) Je pense qu'il est raisonnable d'utiliser ce simple O (n) algorithme:

• Set i à l'index du dernier élément du tableau
• Si la l'élément à insérer est plus grand qu'un [i] puis insère l'élément à l'index i + 1 et s'arrête.
• Sinon, réglez [i + 1] = a [i] puis diminuez i et répétez l'étape précédente.
• Si i atteint 0, insérez l'élément au début.

Cela suppose que votre tableau dispose d'espace pour insérer un élément supplémentaire.

Answer 2

Vous pouvez trouver la position d'insertion en utilisant binary search.

Answer 3

Pensez à des tâches distinctes qui doivent être fait pour insérer:

1. Trouver l'indice n où le nouvel élément doit être
2. déplacer tous les éléments de la dernière à n (y compris) jusqu'à une fente dans le tableau (uniquement s'il y a des cellules non utilisées dans le tableau, sinon donner et signaler une erreur)
3. mettre le nouvel élément dans array[n]

le f IRST deux étapes pourraient facilement être leurs propres fonctions et pourraient vous aider à séparer mentalement les tâches:

1. n = index_to_put(float new_element, float *array, int array_max, int last_used);
2. new_last_used = move_cells_up(float *array, n, int array_max, int last_used);
3. array[n] = new_element; last_used = new_last_used;